操作系统第九章.

1、u第第8章内存管理（实存）要求：将整个进程放在章内存管理（实存）要求：将整个进程放在内存中（虽然覆盖和交换可以减轻这一限制，但内存中（虽然覆盖和交换可以减轻这一限制，但需额外操作）。但下列情况下并不需要将整个程需额外操作）。但下列情况下并不需要将整个程序放入内存中序放入内存中:u程序中通常的处理异常错误条件的代码程序中通常的处理异常错误条件的代码u数组、链表和表通常分配了比实际所需要更多的内数组、链表和表通常分配了比实际所需要更多的内存存u程序的某些选项或特点可能很少使用程序的某些选项或特点可能很少使用u允许执行只有部分在内存中的程序允许执行只有部分在内存中的程序u程序不再受现有的物理内存空间

2、限制。用户只有对程序不再受现有的物理内存空间限制。用户只有对一个大的虚拟地址空间写程序，简化了编程操作一个大的虚拟地址空间写程序，简化了编程操作u提高了程序执行的并发性、提高了程序执行的并发性、CPU利用率利用率u局部性原理局部性原理(principle of locality)：指程序在执行指程序在执行过程中的一个过程中的一个较短时期较短时期，所执行的，所执行的指令地址指令地址和指和指令的令的操作数地址操作数地址，分别，分别局限于一定区域局限于一定区域。还可以。还可以表现为：表现为：u时间局部性：时间局部性：一条一条指令指令的一次执行和下次执行的一次执行和下次执行，一个，一个数据数据的一次访

3、问和下次访问都集中在一的一次访问和下次访问都集中在一个较短时期内（一条指令被执行了，则在不久个较短时期内（一条指令被执行了，则在不久的将来它可能再被执行）的将来它可能再被执行）u空间局部性：空间局部性：当前指令和当前指令和邻近的几条指令邻近的几条指令，当，当前访问的数据和前访问的数据和邻近的数据邻近的数据都集中在一个较小都集中在一个较小区域内。（区域内。（ 若某一存储单元被使用，则在一若某一存储单元被使用，则在一定时间内，与该存储单元相邻的单元可能被使定时间内，与该存储单元相邻的单元可能被使用用)u局部性原理的具体体现局部性原理的具体体现u程序在执行时，大部分是程序在执行时，大部分是顺序执行顺

4、序执行的指令，的指令，少部分是转移和过程调用指令。少部分是转移和过程调用指令。u过程调用的嵌套深度一般不超过过程调用的嵌套深度一般不超过5，因此执，因此执行的范围不超过行的范围不超过这组嵌套的过程。这组嵌套的过程。u程序中存在相当多的程序中存在相当多的循环结构循环结构，它们由少量，它们由少量指令组成，而被多次执行。指令组成，而被多次执行。u程序中存在相当多对一定程序中存在相当多对一定数据结构的操作数据结构的操作，如数组操作，往往局限在较小范围内。如数组操作，往往局限在较小范围内。u虚拟内存虚拟内存u将内存看成一个巨大的、统一的存储数组；将内存看成一个巨大的、统一的存储数组；总容量不超过物理内存

5、和外存交换区容量之总容量不超过物理内存和外存交换区容量之和和u虚拟内存的实现途径虚拟内存的实现途径u请求页面调度请求页面调度 （ Demand paging ）u请求分段调度（请求分段调度（Demand segmentation）u在程序装入时，不必将其全部读入到内存，而在程序装入时，不必将其全部读入到内存，而只需只需将当前需要执行的部分页或段读入到内存将当前需要执行的部分页或段读入到内存，就可让，就可让程序开始执行。程序开始执行。u在程序执行过程中，如果需执行的指令或访问的数在程序执行过程中，如果需执行的指令或访问的数据尚未在内存（称为据尚未在内存（称为缺页或缺段缺页或缺段），则由处理器通）

6、，则由处理器通知操作系统将相应的页或段知操作系统将相应的页或段调入调入到内存，然后继续到内存，然后继续执行程序。执行程序。u另一方面，操作系统将内存中另一方面，操作系统将内存中暂时不使用的页或段暂时不使用的页或段调出保存在外存调出保存在外存上，从而腾出空间存放将要装入的上，从而腾出空间存放将要装入的程序以及将要调入的页或段。只需程序所需的一部程序以及将要调入的页或段。只需程序所需的一部分在内存就可执行。分在内存就可执行。u大程序：大程序：可在较小的可用内存中执行较大的用户程可在较小的可用内存中执行较大的用户程序；序；u大的用户空间：大的用户空间：提供给用户可用的虚拟内存空间通提供给用户可用的虚

7、拟内存空间通常大于物理内存常大于物理内存( (real memory)real memory)，将用户看到的逻将用户看到的逻辑内存与物理内存分开；辑内存与物理内存分开；u并发：并发：可在内存中容纳更多程序并发执行；可在内存中容纳更多程序并发执行；u易于开发：易于开发：与覆盖技术比较，不必影响编程时的程与覆盖技术比较，不必影响编程时的程序结构序结构u部分装入：部分装入：允许部分程序代码装入内存就可以执行允许部分程序代码装入内存就可以执行；u不连续性：不连续性：物理内存分配的不连续，虚拟物理内存分配的不连续，虚拟地址空间使用的不连续地址空间使用的不连续u部分交换：部分交换：与交换技术相比较，虚拟存

8、储与交换技术相比较，虚拟存储的调入和调出是对部分虚拟地址空间进行的调入和调出是对部分虚拟地址空间进行的；的；u大空间：大空间：通过物理内存和快速外存相结合通过物理内存和快速外存相结合，提供大范围的虚拟地址空间，提供大范围的虚拟地址空间u总容量不超过物理内存和外存交换区容量之和总容量不超过物理内存和外存交换区容量之和虚拟内存大于物理内存示意图虚拟内存大于物理内存示意图u虚拟页式虚拟页式-请求页面调度请求页面调度u虚拟段式虚拟段式-请求段式调度请求段式调度u虚拟段页式虚拟段页式u 思想：思想：在简单页式存储管理的基础上，增加在简单页式存储管理的基础上，增加请求调页请求调页和和页面置换页面置换功能功

9、能u 在程序装入时，不必将其全部读入到内存，而在程序装入时，不必将其全部读入到内存，而只只需将当前需要执行的部分页读入到内存（一个或需将当前需要执行的部分页读入到内存（一个或零个页面，零个页面，就可让程序开始执行。之后根据进程就可让程序开始执行。之后根据进程运行的需要，运行的需要，动态装入动态装入其它页面；其它页面；u在程序执行过程中，如果需执行的指令或访问的在程序执行过程中，如果需执行的指令或访问的数据尚未在内存（称为数据尚未在内存（称为缺页缺页），则由处理器通知），则由处理器通知操作系统将相应的页或段操作系统将相应的页或段调入调入到内存，然后继续到内存，然后继续执行程序。执行程序。u另一方

10、面，当内存空间已满，而又需要装入新的另一方面，当内存空间已满，而又需要装入新的页面时，则根据某种算法页面时，则根据某种算法淘汰淘汰某个页面某个页面（将内存将内存中中暂时不使用的页或段调出保存在外存暂时不使用的页或段调出保存在外存上）上） ，而，而腾出空间存放将要装入的程序的页。腾出空间存放将要装入的程序的页。分页的内存：页在内存与磁盘间的传递分页的内存：页在内存与磁盘间的传递u页表：页表：每个进程有一个，与简单分页相比，增加了如每个进程有一个，与简单分页相比，增加了如下位：下位：uP：表示表示该页是否在内存中该页是否在内存中。如果在主存，则页表中还包。如果在主存，则页表中还包括该页的帧号。（或

11、称括该页的帧号。（或称“有效无效位有效无效位”：“有效有效”时：时：页既合法、也在内存中；页既合法、也在内存中；“无效无效”时：页不在进程的逻辑时：页不在进程的逻辑地址空间、或者在磁盘上）地址空间、或者在磁盘上）uM：修改位，表示相应页的内容从上次装入主存到现在是修改位，表示相应页的内容从上次装入主存到现在是否已经改变。否已经改变。u如果没有改变，则该页换出时，不需要重新写回到磁盘上如果没有改变，则该页换出时，不需要重新写回到磁盘上u如果改变了，则该页换出时，需要重新写回到磁盘上如果改变了，则该页换出时，需要重新写回到磁盘上u还有其它一些用于还有其它一些用于保护和共享的位保护和共享的位。Vir

12、tual AddressPage Table EntryPage NumberOffsetP MFrame NumberOther Control Bits虚地址虚地址页表项页表项有些页不在内存中时的页表有些页不在内存中时的页表u在地址映射过程中，在页表中发现所要访问的在地址映射过程中，在页表中发现所要访问的页不在内存，则产生页不在内存，则产生缺页中断缺页中断(page Fault)。u操作系统接到此中断信号后，就调出操作系统接到此中断信号后，就调出缺页中断缺页中断处理程序处理程序，根据页表中给出的外存地址，根据页表中给出的外存地址，将该将该页调入内存页调入内存，使作业继续运行下去，使作业继续

13、运行下去u如果内存中有空闲块，则分配一页，将新调入页如果内存中有空闲块，则分配一页，将新调入页装入内存，并修改页表中相应页表项目的驻留位装入内存，并修改页表中相应页表项目的驻留位及相应的内存块号及相应的内存块号u 若此时内存中没有空闲块，则要淘汰某页，若该若此时内存中没有空闲块，则要淘汰某页，若该页在内存期间被修改过，则要将其写回外存页在内存期间被修改过，则要将其写回外存u分页硬件，在通过页表转换地址时，如果发现非法分页硬件，在通过页表转换地址时，如果发现非法位，则陷入到位，则陷入到OS中，中，执行下列过程：执行下列过程：u 检查进程的页表，以确定该引用是合法还是非法的地址检查进程的页表，以确

14、定该引用是合法还是非法的地址访问；访问；u如果应用非法，则终止进程；如果引用有效但是尚未调如果应用非法，则终止进程；如果引用有效但是尚未调入页面，那么现在应调入；入页面，那么现在应调入；u 找到一个空闲帧；找到一个空闲帧；u 执行一个磁盘操作，以便将所需页调入刚分配的帧中执行一个磁盘操作，以便将所需页调入刚分配的帧中u 当磁盘读操作结束后，修改进程页表，表示该页已在内当磁盘读操作结束后，修改进程页表，表示该页已在内存中存中u 恢复程序的执行恢复程序的执行缺页中断处理缺页中断处理u缺页中断在指令执行期间产生和进行处理，而不是在一条指令执行完毕之后。所缺的页面调入之后，重新执行被中断的指令。u一条

15、指令的执行可能产生多次缺页中断，如：swap A, B,指令本身和两个操作数A, B都跨越相邻外存页的分界处，则产生6次缺页中断。swap A,BABPagexx+1yy+1zz+1u定义：定义：u在必须取进一个页时，应该在必须取进一个页时，应该选择替换主存中的选择替换主存中的哪个页哪个页。当主存中的所有页都被占据，并且需。当主存中的所有页都被占据，并且需要取进一个新页以满足一次缺页时，要取进一个新页以满足一次缺页时，替换策略替换策略决定当前在主存中的哪个页将被置换。决定当前在主存中的哪个页将被置换。u目标：目标：u把未来不再使用的或短期内较少使用的页面调把未来不再使用的或短期内较少使用的页面

16、调出出。通常只能在局部性原理指导下依据过去的。通常只能在局部性原理指导下依据过去的统计数据进行预测（移出最近最不可能访问的统计数据进行预测（移出最近最不可能访问的页。）页。）u由于局部性原理，最近的访问历史和最近将要由于局部性原理，最近的访问历史和最近将要访问的模式间是有很大的相关性。大多数策略访问的模式间是有很大的相关性。大多数策略都基于过去的行为力图都基于过去的行为力图预测预测将来的行为。将来的行为。n查找所需页在磁盘上的位置查找所需页在磁盘上的位置n查找一个空闲帧（查找一个空闲帧（frame）- 如果有空闲帧，就使用它如果有空闲帧，就使用它；- 如果没有空闲帧，就使用一个替换算法以选如果

17、没有空闲帧，就使用一个替换算法以选 n 择一个择一个“牺牲牺牲”帧（帧（victim frame）；）；n 3.将将“牺牲牺牲”帧的内容写到磁盘上；改变页表和空帧的内容写到磁盘上；改变页表和空闲页表闲页表.n 4. 将所需页读入（新）空闲帧，改变页表和帧表将所需页读入（新）空闲帧，改变页表和帧表.n 5.重启用户进程重启用户进程.u最佳算法（最佳算法（OPT）u先进先出算法先进先出算法(First in First Out，FIFO)u最近最久未使用算法最近最久未使用算法(LRU, Least Recently Used)uClock算法算法u近似近似LRU算法算法u最佳算法（最佳算法（Opt

18、imal，OPT）u选择替换选择替换下次访问下次访问距当前时间最长的那些页。距当前时间最长的那些页。u特点特点u缺页错误率最低，没有缺页错误率最低，没有Belady现象；现象；u要求要求OS必须知道引用串的未来知识，必须知道引用串的未来知识，不可能不可能实现实现。uOPT仅能仅能作为一种标准作为一种标准，用于测试其他算法，用于测试其他算法的性能的性能。Belady异常（异常（Belady Anomaly）：）：有些情况下，页故障率有些情况下，页故障率（缺页率）可能会随着所分配的帧数的增加而增加。（缺页率）可能会随着所分配的帧数的增加而增加。示例：示例：最佳算法（最佳算法（Optimal，OPT

19、）u先进先出算法（先进先出算法（FIFO）u替换驻留在主存中时间最长的页。替换驻留在主存中时间最长的页。u实现实现u将分配给进程的页帧看作是一个将分配给进程的页帧看作是一个FIFO队列，按队列，按循环方式移动页循环方式移动页:置换队列的首页，当需要调入置换队列的首页，当需要调入新页时，将它加入到队列的尾部。新页时，将它加入到队列的尾部。u存在问题存在问题uFIFO策略实现简单，但性能相对较差。策略实现简单，但性能相对较差。uBelady异常（异常（Belady Anomaly）：）：有些情况下有些情况下，页故障率（缺页率）可能会随着所分配的帧，页故障率（缺页率）可能会随着所分配的帧数的增加而增

20、加。数的增加而增加。示例：示例：FIFO算法算法u最近最久未使用算法（最近最久未使用算法（LRULeast Recently Used) ）u替换主存中替换主存中上次使用距离当前最远的页（最长上次使用距离当前最远的页（最长时间没有使用的页）时间没有使用的页）。可以理解为。可以理解为向后看最优向后看最优置换算法。根据局部性原理，这也是最近最不置换算法。根据局部性原理，这也是最近最不可能访问到的页。可能访问到的页。LRU性能接近于性能接近于OPT，被认被认为是比较好的算法为是比较好的算法u问题：问题：是如何确定最后访问以来所经历时间的是如何确定最后访问以来所经历时间的顺序。顺序。LRU页置换算法页

21、置换算法u实现方法实现方法2种种：u计数器：计数器：给每个页添加一个最后一次访问的时给每个页添加一个最后一次访问的时间标签，为间标签，为CPU增加一个逻辑时钟或计数器增加一个逻辑时钟或计数器,每进行一次访问存储器时，该时钟都加每进行一次访问存储器时，该时钟都加1。时。时钟寄存器的内容就被复制到相应页表项的使用钟寄存器的内容就被复制到相应页表项的使用时间字段中。在淘汰时，选择该时间值最小的时间字段中。在淘汰时，选择该时间值最小的页面。开销大。页面。开销大。u堆栈：堆栈：维护一个关于访问页的栈，很昂贵。每维护一个关于访问页的栈，很昂贵。每当引用一个页，该页就从堆栈中删除并放在顶当引用一个页，该页就

22、从堆栈中删除并放在顶部。部。栈底是目前最少使用的页（栈底是目前最少使用的页（LRU页）。页）。堆堆栈需要是双向链表。栈需要是双向链表。堆栈法堆栈法u简单时钟算法：简单时钟算法：u将所有内存中的页面保存在一个类似时钟表盘的将所有内存中的页面保存在一个类似时钟表盘的循环循环链链表中，由一个指针指向最老的页面，置换时从当前指针表中，由一个指针指向最老的页面，置换时从当前指针位置开始按地址先后检查各页，位置开始按地址先后检查各页，寻找引用位寻找引用位=0的页面的页面作为被置换页。作为被置换页。u当发生缺页时当发生缺页时，首先检查指针指向的页面：，首先检查指针指向的页面：u如果它的如果它的引用位为引用位

23、为0则淘汰该页则淘汰该页，且将新页插入到此，且将新页插入到此位置，然后将指针向前移动一个位置。位置，然后将指针向前移动一个位置。u如果如果引用位为引用位为1，则清，则清0 ，且将指针前移一个位置，且将指针前移一个位置；重复这个过程，直到找到引用位为重复这个过程，直到找到引用位为0的页面为止。（的页面为止。（指针经过的指针经过的user bit=1的页都修改的页都修改user bit=0，最后最后指针停留在被置换页的下一个页。）指针停留在被置换页的下一个页。）u优点是：优点是：在进行页面比较时不发生页面移动，而只是移动在进行页面比较时不发生页面移动，而只是移动指针，可以提高检测效率。指针，可以提

24、高检测效率。当页当页727要要进入时，进入时，在从缓冲在从缓冲区中替换区中替换一页之前，一页之前，下一帧指下一帧指针指向含针指向含有页有页45的的帧。帧。替换前：替换前：替换后：替换后：u最不经常使用页面置换算法最不经常使用页面置换算法LFUu要求：置换计数最小的页要求：置换计数最小的页u问题：一个页在进程开始时使用得很多，但问题：一个页在进程开始时使用得很多，但以后就不再使用以后就不再使用u解决方法：定期将次数寄存器右移一位，形解决方法：定期将次数寄存器右移一位，形成指数衰减的平均使用次数成指数衰减的平均使用次数u最常使用页面置换算法最常使用页面置换算法MFUu具有最小次数的页可能刚刚调进来

25、，且还没具有最小次数的页可能刚刚调进来，且还没有使用有使用u系统颠簸：系统颠簸：刚刚被淘汰出去的页很快又被访问，需要重刚刚被淘汰出去的页很快又被访问，需要重新调入；但是，调入不久又再次被淘汰出去。如此反复新调入；但是，调入不久又再次被淘汰出去。如此反复，使得整个系统的页面替换非常频繁，使大部分机器时，使得整个系统的页面替换非常频繁，使大部分机器时间都用在来回进行的页面调度上，这种局面称为系统颠间都用在来回进行的页面调度上，这种局面称为系统颠簸（簸（thrashing)u结果：结果：缺页率急剧增加，内存有效存取时间加长，系统缺页率急剧增加，内存有效存取时间加长，系统吞吐量骤减；系统已基本不能完成

26、什么任务。吞吐量骤减；系统已基本不能完成什么任务。u产生原因：产生原因：如果如果CPU利用率太低，调度程序就会增加多利用率太低，调度程序就会增加多道程序度，将新进程引入系统中。新进程启动运行，导道程序度，将新进程引入系统中。新进程启动运行，导致缺页，从其他进程中取帧，进行换入换出。致缺页，从其他进程中取帧，进行换入换出。u防止系统颠簸防止系统颠簸(抖动抖动)方法：方法：u采用局部置换策略：采用局部置换策略：如果一个进程出现抖动，它不能从另外的进程取如果一个进程出现抖动，它不能从另外的进程取帧帧,不会引发其它进程出现抖动，使抖动局限于一个小范围内。不会引发其它进程出现抖动，使抖动局限于一个小范围

27、内。u利用工作集策略防止抖动利用工作集策略防止抖动u挂起某些进程：挂起某些进程：优先级低、缺页进程、最大的进程等优先级低、缺页进程、最大的进程等u工作集工作集:就是一个进程在某一小段时间就是一个进程在某一小段时间 内访问页面的集合。如内访问页面的集合。如用用WS(ti)表示在表示在ti 到到ti之间所访问的不同页面，则它就是进之间所访问的不同页面，则它就是进程在时间程在时间ti的工作集。的工作集。u如果页面正在使用，它就落在工作集中；如果不再使用，它将如果页面正在使用，它就落在工作集中；如果不再使用，它将不出现在相应的工作集中，所以，工作集是程序局部性的近似不出现在相应的工作集中，所以，工作集

28、是程序局部性的近似表示。表示。 2 6 1 5 7 7 7 7 5 1 6 2 3 4 1 2 3 4 4 4 3 4 3 4 4 4 1 3 2 3 4 4 4 3 4 4 对于给定的页面走向，如果对于给定的页面走向，如果 10次存储访问，在次存储访问，在t1时刻的工作集是时刻的工作集是WS(t1)=(1,2,5,6,7)，在在t2时刻，工作时刻，工作集是集是WS(t2)=(3,4)t1t2u工作集精确度与工作集精确度与 的选择有关。如果的选择有关。如果 太小，那么它太小，那么它不能包含整个局部；如果不能包含整个局部；如果 为无穷大，那么工作集合为无穷大，那么工作集合是进程执行所碰到的所有页

29、的集合。是进程执行所碰到的所有页的集合。u利用工作集模型可以进行页面置换。利用工作集模型可以进行页面置换。工作集页面置换工作集页面置换法法基本思想：找出一个不在工作集中的页面，把它淘基本思想：找出一个不在工作集中的页面，把它淘汰。汰。u利用工作集模型可以防止抖动。利用工作集模型可以防止抖动。uOS监视每个进程的工作集，并且给它分配工作集所需监视每个进程的工作集，并且给它分配工作集所需的内存块。的内存块。u若有足够多的额外内存块，就可装入另一个进程。若有足够多的额外内存块，就可装入另一个进程。u如果所有工作集之和增加以至于超过了可用内存块的如果所有工作集之和增加以至于超过了可用内存块的总数，则总

30、数，则OS就会选择挂起一个进程，把它就会选择挂起一个进程，把它 的页写出去的页写出去，将它的内存块分配给其它其它进程。，将它的内存块分配给其它其它进程。u挂起的进程可以在以后重启。挂起的进程可以在以后重启。u 在简单段式存储管理的基础上，增加在简单段式存储管理的基础上，增加请求调段请求调段和和段置换功能。段置换功能。u段表：段表：需要在进程段表中添加若干项：需要在进程段表中添加若干项：u标志位：标志位：存在位存在位(present bit) 修改位修改位(modified bit/dirty bit)u访问统计：访问统计：如使用位如使用位(use bit)u存取权限：存取权限：如读如读R，写写W，执行执行Xu外存地址外存地址u动态地址变换和缺段中断：动态地址变换和缺段中断：指令和操作数必定不会指令和操作数必定不会跨越在段边界上跨越在段边界上段号段号始址始址长度长度存取方式存取方式内外内外访问位访问位u原理：原理：一个进程只有部分分段放在内存就可运一个进程只有部分分段放在内存就可运行。程序运行时，先把当前需要的一段或者几行。程序运行时，先把当前需要的一段或者几段装入内存，其它段仅仅在调用时才装入。段装入内存，其它段仅仅在调用时才装入。u过程