操作系统第九章

第9章虚拟内存9.1虚拟内存-研究背景第8章内存管理（实存）要求：将整个进程放在内存中（虽然覆盖和交换可以减轻这一限制，但需额外操作）。但下列情况下并不需要将整个程序放入内存中:程序中通常的处理异常错误条件的代码数组、链表和表通常分配了比实际所需要更多的内存程序的某些选项或特点可能很少使用允许执行只有部分在内存中的程序程序不再受现有的物理内存空间限制。用户只有对一个大的虚拟地址空间写程序，简化了编程操作提高了程序执行的并发性、CPU利用率9.1虚拟内存-局部性原理局部性原理(principleoflocality)：指程序在执行过程中的一个较短时期，所执行的指令地址和指令的操作数地址，分别局限于一定区域。还可以表现为：时间局部性：一条指令的一次执行和下次执行，一个数据的一次访问和下次访问都集中在一个较短时期内（一条指令被执行了，则在不久的将来它可能再被执行）空间局部性：当前指令和邻近的几条指令，当前访问的数据和邻近的数据都集中在一个较小区域内。（

若某一存储单元被使用，则在一定时间内，与该存储单元相邻的单元可能被使用)9.1虚拟内存--局部性原理局部性原理的具体体现程序在执行时，大部分是顺序执行的指令，少部分是转移和过程调用指令。过程调用的嵌套深度一般不超过5，因此执行的范围不超过这组嵌套的过程。程序中存在相当多的循环结构，它们由少量指令组成，而被多次执行。程序中存在相当多对一定数据结构的操作，如数组操作，往往局限在较小范围内。9.1虚拟内存--概念虚拟内存将内存看成一个巨大的、统一的存储数组；总容量不超过物理内存和外存交换区容量之和虚拟内存的实现途径请求页面调度（Demandpaging）请求分段调度（Demandsegmentation）9.1虚拟内存—原理在程序装入时，不必将其全部读入到内存，而只需将当前需要执行的部分页或段读入到内存，就可让程序开始执行。在程序执行过程中，如果需执行的指令或访问的数据尚未在内存（称为缺页或缺段），则由处理器通知操作系统将相应的页或段调入到内存，然后继续执行程序。另一方面，操作系统将内存中暂时不使用的页或段调出保存在外存上，从而腾出空间存放将要装入的程序以及将要调入的页或段。只需程序所需的一部分在内存就可执行。9.1虚拟内存—技术特征大程序：可在较小的可用内存中执行较大的用户程序；大的用户空间：提供给用户可用的虚拟内存空间通常大于物理内存(realmemory)，将用户看到的逻辑内存与物理内存分开；并发：可在内存中容纳更多程序并发执行；易于开发：与覆盖技术比较，不必影响编程时的程序结构部分装入：允许部分程序代码装入内存就可以执行；9.1虚拟内存—好处不连续性：物理内存分配的不连续，虚拟地址空间使用的不连续部分交换：与交换技术相比较，虚拟存储的调入和调出是对部分虚拟地址空间进行的；大空间：通过物理内存和快速外存相结合，提供大范围的虚拟地址空间总容量不超过物理内存和外存交换区容量之和虚拟内存大于物理内存示意图9.1虚拟内存—实现方法(种类)

虚拟页式-请求页面调度虚拟段式-请求段式调度虚拟段页式9.2请求页面调度－基本思想

思想：在简单页式存储管理的基础上，增加请求调页和页面置换功能

在程序装入时，不必将其全部读入到内存，而只需将当前需要执行的部分页读入到内存（一个或零个页面，就可让程序开始执行。之后根据进程运行的需要，动态装入其它页面；在程序执行过程中，如果需执行的指令或访问的数据尚未在内存（称为缺页），则由处理器通知操作系统将相应的页或段调入到内存，然后继续执行程序。另一方面，当内存空间已满，而又需要装入新的页面时，则根据某种算法淘汰某个页面（将内存中暂时不使用的页或段调出保存在外存上），而腾出空间存放将要装入的程序的页。分页的内存：页在内存与磁盘间的传递9.2请求页面调度－示例9.2请求页面调度－对进程页表的修改页表：每个进程有一个，与简单分页相比，增加了如下位：P：表示该页是否在内存中。如果在主存，则页表中还包括该页的帧号。（或称“有效－无效位”：“有效”时：页既合法、也在内存中；“无效”时：页不在进程的逻辑地址空间、或者在磁盘上）M：修改位，表示相应页的内容从上次装入主存到现在是否已经改变。如果没有改变，则该页换出时，不需要重新写回到磁盘上如果改变了，则该页换出时，需要重新写回到磁盘上还有其它一些用于保护和共享的位。虚地址页表项9.2请求页面调度－对进程页表的修改有些页不在内存中时的页表9.2请求页面调度－地址转换9.2请求页面调度－缺页中断处理在地址映射过程中，在页表中发现所要访问的页不在内存，则产生缺页中断(pageFault)。操作系统接到此中断信号后，就调出缺页中断处理程序，根据页表中给出的外存地址，将该页调入内存，使作业继续运行下去如果内存中有空闲块，则分配一页，将新调入页装入内存，并修改页表中相应页表项目的驻留位及相应的内存块号若此时内存中没有空闲块，则要淘汰某页，若该页在内存期间被修改过，则要将其写回外存9.2请求页面调度－缺页中断处理分页硬件，在通过页表转换地址时，如果发现非法位，则陷入到OS中，执行下列过程：

检查进程的页表，以确定该引用是合法还是非法的地址访问；如果应用非法，则终止进程；如果引用有效但是尚未调入页面，那么现在应调入；找到一个空闲帧；执行一个磁盘操作，以便将所需页调入刚分配的帧中当磁盘读操作结束后，修改进程页表，表示该页已在内存中恢复程序的执行缺页中断处理缺页中断的特殊性缺页中断在指令执行期间产生和进行处理，而不是在一条指令执行完毕之后。所缺的页面调入之后，重新执行被中断的指令。一条指令的执行可能产生多次缺页中断，如：swapA,B,指令本身和两个操作数A,B都跨越相邻外存页的分界处，则产生6次缺页中断。9.3页面置换算法（Replacement）定义：在必须取进一个页时，应该选择替换主存中的哪个页。当主存中的所有页都被占据，并且需要取进一个新页以满足一次缺页时，替换策略决定当前在主存中的哪个页将被置换。目标：把未来不再使用的或短期内较少使用的页面调出。通常只能在局部性原理指导下依据过去的统计数据进行预测（移出最近最不可能访问的页。）由于局部性原理，最近的访问历史和最近将要访问的模式间是有很大的相关性。大多数策略都基于过去的行为力图预测将来的行为。查找所需页在磁盘上的位置查找一个空闲帧（frame）

-如果有空闲帧，就使用它；

-如果没有空闲帧，就使用一个替换算法以选择一个“牺牲”帧（victimframe）；

3.将“牺牲”帧的内容写到磁盘上；改变页表和空闲页表.

4.将所需页读入（新）空闲帧，改变页表和帧表.

5.重启用户进程.9.3页面置换－基本工作过程9.3页面置换－基本工作过程9.4置换策略－基本算法最佳算法（OPT）先进先出算法(FirstinFirstOut，FIFO)最近最久未使用算法(LRU,LeastRecentlyUsed)Clock算法近似LRU算法9.4替换策略－最佳算法OPT最佳算法（Optimal，OPT）选择替换下次访问距当前时间最长的那些页。特点缺页错误率最低，没有Belady现象；要求OS必须知道引用串的未来知识，不可能实现。OPT仅能作为一种标准，用于测试其他算法的性能。Belady异常（BeladyAnomaly）：有些情况下，页故障率（缺页率）可能会随着所分配的帧数的增加而增加。示例：最佳算法（Optimal，OPT）9.4替换策略－最佳算法OPT9.4替换策略－先进先出算法FIFO先进先出算法（FIFO）替换驻留在主存中时间最长的页。实现将分配给进程的页帧看作是一个FIFO队列，按循环方式移动页:置换队列的首页，当需要调入新页时，将它加入到队列的尾部。存在问题FIFO策略实现简单，但性能相对较差。Belady异常（BeladyAnomaly）：有些情况下，页故障率（缺页率）可能会随着所分配的帧数的增加而增加。9.4替换策略－先进先出算法FIFO示例：FIFO算法9.4替换策略－LRU最近最久未使用算法（LRU－LeastRecentlyUsed)）替换主存中上次使用距离当前最远的页（最长时间没有使用的页）。可以理解为向后看最优置换算法。根据局部性原理，这也是最近最不可能访问到的页。LRU性能接近于OPT，被认为是比较好的算法问题：是如何确定最后访问以来所经历时间的顺序。LRU页置换算法9.4替换策略－LRU实现方法2种：计数器：给每个页添加一个最后一次访问的时间标签，为CPU增加一个逻辑时钟或计数器,每进行一次访问存储器时，该时钟都加1。时钟寄存器的内容就被复制到相应页表项的使用时间字段中。在淘汰时，选择该时间值最小的页面。开销大。堆栈：维护一个关于访问页的栈，很昂贵。每当引用一个页，该页就从堆栈中删除并放在顶部。栈底是目前最少使用的页（LRU页）。堆栈需要是双向链表。9.4替换策略－LRU实现9.4替换策略－

LRU实现堆栈法9.4替换策略－轮转算法Clock简单时钟算法：将所有内存中的页面保存在一个类似时钟表盘的循环链表中，由一个指针指向最老的页面，置换时从当前指针位置开始按地址先后检查各页，寻找引用位=0的页面作为被置换页。当发生缺页时，首先检查指针指向的页面：如果它的引用位为0则淘汰该页，且将新页插入到此位置，然后将指针向前移动一个位置。如果引用位为1，则清0，且将指针前移一个位置；重复这个过程，直到找到引用位为0的页面为止。（指针经过的userbit=1的页都修改userbit=0，最后指针停留在被置换页的下一个页。）优点是：在进行页面比较时不发生页面移动，而只是移动指针，可以提高检测效率。当页727要进入时，在从缓冲区中替换一页之前，下一帧指针指向含有页45的帧。替换前：替换后：9.4替换策略－基于计数的方法LFU和MFU最不经常使用页面置换算法LFU要求：置换计数最小的页问题：一个页在进程开始时使用得很多，但以后就不再使用解决方法：定期将次数寄存器右移一位，形成指数衰减的平均使用次数最常使用页面置换算法MFU具有最小次数的页可能刚刚调进来，且还没有使用9.5系统颠簸（抖动）Thrashing系统颠簸：刚刚被淘汰出去的页很快又被访问，需要重新调入；但是，调入不久又再次被淘汰出去。如此反复，使得整个系统的页面替换非常频繁，使大部分机器时间都用在来回进行的页面调度上，这种局面称为系统颠簸（thrashing)结果：缺页率急剧增加，内存有效存取时间加长，系统吞吐量骤减；系统已基本不能完成什么任务。产生原因：如果CPU利用率太低，调度程序就会增加多道程序度，将新进程引入系统中。新进程启动运行，导致缺页，从其他进程中取帧，进行换入换出。防止系统颠簸(抖动)方法：采用局部置换策略：如果一个进程出现抖动，它不能从另外的进程取帧,不会引发其它进程出现抖动，使抖动局限于一个小范围内。利用工作集策略防止抖动挂起某些进程：优先级低、缺页进程、最大的进程等

9.5系统颠簸（抖动）－工作集（驻留集）工作集:就是一个进程在某一小段时间内访问页面的集合。如用WS(ti)表示在ti－到ti之间所访问的不同页面，则它就是进程在时间ti的工作集。如果页面正在使用，它就落在工作集中；如果不再使用，它将不出现在相应的工作集中，所以，工作集是程序局部性的近似表示。

…261577775162341234443434441323444344…对于给定的页面走向，如果＝10次存储访问，在t1时刻的工作集是WS(t1)=(1,2,5,6,7)，在t2时刻，工作集是WS(t2)=(3,4)t1t29.5系统颠簸（抖动）－工作集页面置换法工作集精确度与的选择有关。如果太小，那么它不能包含整个局部；如果为无穷大，那么工作集合是进程执行所碰到的所有页的集合。利用工作集模型可以进行页面置换。工作集页面置换法基本思想：找出一个不在工作集中的页面，把它淘汰。利用工作集模型可以防止抖动。OS监视每个进程的工作集，并且给它分配工作集所需的内存块。若有足够多的额外内存块，就可装入另一个进程。如果所有工作集之和增加以至于超过了可用内存块的总数，则OS就会选择挂起一个进程，把它的页写出去，将它的内存块分配给其它其它进程。挂起的进程可以在以后重启。9.6请求分段技术

在简单段式存储管理的基础上，增加请求调段和段置换功能。段表：需要在进程段表中添加若干项：标志位：存在位(presentbit)

修改位(modifiedbit/dirtybit)访问统计：如使用位(usebit)存取权限：如读R，写W，执行X外存地址动态地址变换和缺段中断：指令和操作数必定不会跨越在段边界上段号始址长度存取方式内外访问位原理：