操作系统请求分页

会计学1操作系统请求分页虚拟存储器虚拟存储器（VirtualMemory），简称虚存，是指对内存的虚拟，一种实际并不存在的内存空间，包括一级存储器概念和作业地址空间概念。虚拟并不是无限的，取决于机器的CPU地址结构，虚存容量不能大于外存容量。第1页/共38页请求分页管理请求分页管理是动态分页管理，是在静态分页管理基础上发展而来的。在简单分页管理中，如果作业所要求的页面数比内存空闲的块数多，则该作业不能装入运行。在虚拟存储器技术的支持下，可以进行请求分页管理。那么请求分页管理的基本思想是什么？作业要访问的页面不在内存时，该如何处理？如何知道哪些页面在内存，哪些不在？如何决定把作业的哪些页面留在内存中呢？将虚页调入内存时，没有空闲块又怎么处理？在虚拟存储系统中，将对逻辑空间和物理空间的考虑截然分开，逻辑空间的容量由系统提供的有效地址长度决定。

第2页/共38页请求分页管理就能实现这种虚存空间，基本方法是在分页管理的基础上，在作业开始执行前，只装入作业的一部分页面到内存，其它的页面在作业执行过程中根据需要，动态地从辅存装入内存。当内存块已经占满时，再根据某种策略交换出部分页面到辅存。根据作业的执行情况装入作业的部分实体，显然节省了内存空间。请求分页管理和分页管理的数据结构、地址映射和存储保护、存储分配与回收等都类似，但请求分页管理的实现过程复杂很多，需要由硬件和软件的相互配合才能完成。1.请求调入及缺页中断处理2.淘汰算法3.抖动与工作集第3页/共38页请求分页存储管理铺垫作业在运行期间的各个阶段，多数作业只使用全部地址空间的一部分。例如用户编制的出错处理子程序，在作业正常运行情况下不会执行这些程序，没有必要把它们调入内存。即程序中往往会有一些彼此互斥的部分不是每次运行时都能执行到。

程序的局部性。顺序执行的指令和线性结构的数据(如数组)。它们通常被限定在某一连续区域。一旦某一位置被访问后，那么它附近的位置很快也会被访问。第4页/共38页

基于上述情况，就没有必要把一个作业一次性全部装入内存再开始运行。而是可以把程序当前执行所涉及的信息放入内存中，其余部分可根据需要临时调入，由操作系统和硬件相配合来完成主存和辅存之间信息的动态调度。这样的计算机系统好像为用户提供了一个存储容量比实际主存大得多的存储器，就称为虚拟存储器。第5页/共38页虚拟存储器的概念P61虚拟存储技术的基本思想是利用大容量的外存来扩充内存，产生一个比有限的实际内存空间大得多的、逻辑的虚拟内存空间，以有效地支持多道程序设计的实现和大型程序运行的需要，增强系统的处理能力。请求分页系统支持虚拟存储技术第6页/共38页

请求分页存储管理名词作业的逻辑地址空间划分的页，称为虚页主存称为实存实存中的块称为实页第7页/共38页

请求分页存储管理基本原理请求分页系统对地址空间和内存空间的管理采用与分页存储管理系统相同的方式，但是它只将作业的部分页面装入内存，便可开始运行作业，作业的其他部分被存放在辅助存储器上。第8页/共38页请求分页存储管理必须解决的问题一个作业不全部装入，该作业能否开始运行，并运行一段时间？当程序要访问的某页不在内存时，如何发现这种缺页情况？发现后应如何处理？缺页时，所需的页面从何处装入？装入到何处？若此时实存中没有空闲块应怎么办？第9页/共38页一个作业不全部装入，该作业能否开始运行，并运行一段时间？作业在运行期间的各个阶段，多数作业只使用全部地址空间的一部分。例如用户编制的出错处理子程序，在作业正常运行情况下不会执行这些程序，没有必要把它们调入内存。即程序中往往会有一些彼此互斥的部分不是每次运行时都能执行到。

程序的局部性。顺序执行的指令和线性结构的数据(如数组)。它们通常被限定在某一连续区域。一旦某一位置被访问后，那么它附近的位置很快也会被访问。因此，没有必要把一个作业一次性全部装入内存再开始运行。而是可以把程序当前执行所涉及的信息放入内存中，其余部分可根据需要临时调入，由操作系统和硬件相配合来完成主存和辅存之间信息的动态调度。第10页/共38页当程序要访问的某页不在内存时，如何发现

这种缺页情况？发现后应如何处理？地址变换机构检测到虚页的状态为1，由硬件产生缺页中断，转去中断处理第11页/共38页

所需的页面从何处装入？

在请求分页管理系统中，当一个作业完成编译链接后，所形成的装配模块通常以文件形式存入作为辅存的磁盘上，当该页需要装入实存时，就从磁盘上调进来。为此，需建立一个作业的辅助页表，也称为外页表。虚页号辅存地址第12页/共38页新调入的页面装入何处？实存中有空闲实页，直接将其装入。空闲已满，则必须淘汰（页面置换算法）实存中的某一页。

被淘汰的页，以后可能还要用，是否需要写回辅存，这取决于该页进入实存后是否被修改，如未被修改，因辅存上已有副本则不必写回辅存。否则，要重新写回辅存。因此页表中还可以增加一个“修改位”，以反映该页是否已被修改过。为了便于系统管理页面置换，增加“引用位”，表示该页最近是否被访问过。第13页/共38页虚页号主存块号改变位引用位状态位辅存地址0/11该页已被修改过0该页未被修改0/11最近已被访问过主存块号0/10在内存1不在内存辅助页表虚页号辅存地址保护信息扩充后的PMT表第14页/共38页图缺页中断的发生及其处理抖动/系统颠簸第15页/共38页抖动/系统颠簸出页：将某一页从实存移到辅存入页：将某一页从辅存调入实存这种反复进行入页和出页的现象称为“抖动/系统颠簸”第16页/共38页

先进先出算法(FIFO)淘汰驻留主存时间最长的页面最近最久未用置换算法(LRU)淘汰在最近一段时间最久未用的页面最近最不常用算法最近未使用算法页面置换算法/淘汰算法第17页/共38页1.先进先出算法（FIFO算法）

这种算法的基本思想是：总是先淘汰那些驻留在内存时间最长的页面，即先进入内存的页面先被置换掉。理由是：最先进入内存的页面不再被访问的可能性最大。

第18页/共38页2．最近最久未使用页面置换算法（LeastRecentlyUsed/LRU算法）这种算法的基本思想是，如果某一页被访问了，那么它很可能马上又被访问；反之，如果某一页很长时间没有被访问，那么最近也不太可能会被访问。这种算法考虑了程序设计的局部性原理。其实质是，当需要置换一页时，选择在最近一段时间最久未使用的页面予以淘汰。实现这种算法可通过周期性地对“引用位”进行检查，并利用它来记录一页面自上次被访问以来所经历的时间t，淘汰时选择t最大的页面。

不太实用第19页/共38页

性能分析为了尽可能地减少缺页中断的次数，应从程序设计的质量页面的大小主存的容量页面置换算法等几方面来考虑。第20页/共38页程序设计的质量(主要指程序的局部化程度)程序的局部化程度包括时间局部化和空间局部化时间局部化是指一旦某个位置----数据或指令----被访问了，它常常很快又要再次被访问。这可通过循环、经常用到的变量和子程序等程序结构来实现。空间局部化是指一旦某个位置被访问到，那么它附近的位置很快也要用到。这可以尽量采用顺序的指令列、线形的数据结构来实现。局部化程度随程序而异，一般来说，总希望编制的程序具有较高的局部化程度。这样，程序执行时可经常集中在几个页面上进行访问，以减少缺页中断的次数。第21页/共38页页面的大小页面大小应根据实际情况来确定，它和计算机的性能以及用户的要求都有关系。页面大，页表小，占用空间小，缺页中断次数少，但换页时间长，页内碎片也大，浪费空间页面小时，正好相反第22页/共38页主存的容量一个作业的执行所产生缺页的次数是存放页面的实际存储容量的函数。当存储容量达到某一程度时，缺页中断的次数的减少就不明显了。试验分析表明：对所有程序来说，要使之有效地工作，它在主存中的页面数不低于它的总页面数的一半。第23页/共38页图存储容量与缺页中断次数的关系第24页/共38页4．页面置换算法性能三个参数：页面走向：每个作业的虚页调入实存的顺序，称为页面轨迹，或页面走向，用P表示。主存容量：是指分配给作业的主存块数，M表示。置换算法：包括FIFO，LRU等第25页/共38页例1

设页面走向为P=4,3,2,1,4,3,5,4,3,2,1,5，主存容量M=3，置换算法采用FIFO，求访问过程中发生缺页中断的次数和缺页率？假设开始时，主存未装入任何块。表1FIFO性能分析例(M=3)缺页中断次数F=9缺页率f=9/12=75%P行表示页面走向，M行表示在主存中的页面号，其中带有+的表示新调入页面，在M行的各列按调入的顺序排列，带有圆圈的数字表示下一时刻将被淘汰页面，F行表示是否引起缺页中断，带+号的表示引起缺页中断。第26页/共38页

例2

设M=4，其余同例1。则缺页中断次数和缺页率？表2FIFO性能分析例(M=4)缺页中断次数F=10缺页率f=10/12=83%第27页/共38页由表1，表2得出：对于FIFO算法，内存增加，缺页率反而增加！异常现象（Belady异常）第28页/共38页

例3

设页面走向如上，M=3，置换算法为LRU，则缺页中断次数和缺页率？由于采用LRU算法，M中各列按访问的时间顺序排列，最近被访问的页面在最前。表3LRU性能分析例(M=3)缺页中断次数F=10，缺页率f=10/12=83%。第29页/共38页例4

设M=4，其余同例3，则缺页中断次数和缺页率？表4LRU性能分析例(M=4)第30页/共38页34第31页/共38页

由表3，表4可得如下事实：设G(P,M,t)表示当页面走向为P，主存容量为M，在时刻t的页面集合，对于LRU算法，存在如下关系，即成立。即对于任何时刻t(t=1,2,…,12),G(P,M,t)所选中的页号必定包含在G(P,M+1,t)之中。这种关系说明了增加主存容量不会增加缺页中断次数，然而对FIFO算法，此关系并不成立。第32页/共38页

请求分页存储管理方案的评价它提供了大容量的多个虚拟存储器，作业地址空间不再受实存容量的限制；更有效地利用了主存，一个作业的地址空间不必全部同时都装入主存，只装入其必要部分，其它部分根据请求装入，或者根本就不装入(如错误处理程序等)；更加有利于多道程序的运行，从而提高了系统效率；方便了用户，特别是大作业用户。

第33页/共38页

缺点为处理缺页中断，增加了处理机时间的开销，即请求分页系统是用时间的代价换取了空间的扩大；可能因作业地址空间过大或多道程序道数过多以及其它原因而造成系统抖动；为防止系统抖动所采取的各种措施会增加系统的复杂性。第34页/共38页复习LRU页面调度算法是选择（）的页面先调出。A．最近才使用B．最久未被使用

C．驻留时间最长D．驻留时间最短若进程执行到某条指令时发生了缺页中断，经