操作系统第四章4

第四章存储器管理赵恒主讲定义：在进程运行过程中，若其访问的页面不在内存而需将其调入，但内存已无空闲空间时，需从内存中调出一页程序或数据，送入磁盘的对换区。但应将哪个页面调出，需根据一定的算法来确定。把选择换出页面的算法称为页面置换算法，其好坏直接影响系统的性能。一个好的置换算法应具有较低的页面更换频率。从理论上讲，应将那些以后不会再访问的页面换出，或者把那些在较长时间内不会再访问的页面换出。§5.3页面置换算法抖动（颤动）现象（Thrashing）请求页式存储管理系统中，若页面置换算法不当，可能会导致下面的情形：刚被调出得页面，不久又要访问，因此要调入，调入后不久又被淘汰，再访问再调入，如此反复，整个系统的页面置换十分频繁，CPU时间主要花费在页面的交换上。这种导致系统效率急剧下降的现象称为抖动现象。缺页中断率过高§5.3页面置换算法页面置换的过程（1）找出所需页面在磁盘上的位置；（2）找出可用空闲内存块。如果有，就立即使用，否则，就进行页面置换，选择一个老的页面置换到外存磁盘。（3）将所需页面装入内存，修改相应的数据结构。（4）继续执行用户进程。§5.3页面置换算法最佳置换算法（OPT，Optimal）：最佳置换算法置换那些以后永不再使用的或者在最长的时间以后才会用到的页面。显然，这种算法的缺页率最低。然而，该算法只是一种理论上的算法，因为很难估计哪一个页面是以后永远不再使用或在最长时间以后才会用到的页面，所以，这种算法是不能实现的。尽管如此，该算法仍然是有意义的，可以把它作为衡量其它算法优劣的一个标准。⑴算法：淘汰永不使用的或是在最长时间内不再被访问的页。⑵通常可保证获得最低的缺页率。⑶无实现价值，作为其它算法的衡量标准。1.最佳(Optimal)置换算法假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1。1.最佳(Optimal)置换算法7F7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1引用序列缺页标志70F701F201F201203F203243F243243203F203203201F201201201701F701701缺页9次，总访问次数20次，缺页率9/20＝45％2.先进先出(FIFO)页面置换算法（1）原理：该算法总是淘汰最先进入内存的页面，即选择在内存中的驻留时间最久的页面予以淘汰。该算法实现简单，只需把一个进程已调入内存的页面，按先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老页面。（2）实现：已调入内存的页面，按先后次序链接成一队列。（3）依据:

先进入的可能已经使用完毕。（4）随着物理块数的增多缺页率增大！（Belady现象）

内存3个物理块：内存4个物理块：缺页率=9/12缺页率=10/12

Belady异常现象：一般而言，分配给进程的物理块越多，运行时的缺页次数应该越少。但是Belady在1969年发现了一个反例，使用FIFO算法时，四个物理块时的缺页次数比三个物理块时的多，这种反常的现象称为Belady异常。举例：设进程有5页，访问顺序：0，1，2，3，0，1，4，0，1，2，3，4，分3块物理块和4块物理块时。2.先进先出(FIFO)页面置换算法7F7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1引用序列缺页标志70F701F201F201231F230F430F420F423F023F023023013F012F012012712F702F701F缺页15次，总访问次数20次，缺页率15/20＝75％假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1。5.3.2最近最久未使用(LRU)置换算法1.LRU(LeastRecentlyUsed)置换算法7F7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1引用序列缺页标志70F701F201F201203F203403F402F432F032F032032132F132102F102107F107107缺页12次，总访问次数20次，缺页率12/20＝60％算法：最近最久未使用置换算以“最近的过去”作为“不久将来”的近似，选择最近一段时间内最久没有使用的页面淘汰掉。它的实质是：当需要置换一页时，选择在最近一段时间里最久没有使用过的页面予以淘汰。LRU的实现：把LRU算法作为页面置换算法是比较好的，它对于各种类型的程序都能适用，但实现起来有相当大的难度，因为它要求系统具有较多的支持硬件。所要解决的问题有：一个进程在内存中的各个页面各有多久时间未被进程访问；如何快速地知道哪一页最近最久未使用的页面。为此，须利用以下两类支持硬件：1．移位寄存器：定时右移。2．栈：当进程访问某页时，将其移出压入“栈顶”，“栈底”换出。最近最久未使用（LRU）置换算法LRU置换算法的硬件支持寄存器为了记录某进程在内存中各页的使用情况，须为每个在内存中的页面配置一个移位寄存器，可表示为访问时将Rn-1位置成1，定时信号每隔一时间间隔右移一位，则具有最小数值的寄存器所对应的页面，就是最近最久未使用的页面。R=Rn-1Rn-2Rn-3…R2R1R0

实页R7R6R5R4R3R2R1R0101010010210101100实页R7R6R5R4R3R2R1R010010100102010101100t0t1实页R7R6R5R4R3R2R1R010001010012001010110t2实页R7R6R5R4R3R2R1R0110010100200101011访问1实页R7R6R5R4R3R2R1R010100101002000101011t3最近最久未使用（LRU）置换算法栈：进程访问某页时，将该页面的页号从栈中移出，再压入栈顶。

用栈保存当前使用页面时栈的变化情况4740747041704017410742107412074210746210747071012126

【例】假定系统为某进程分配了3个物理块，页面访问序列为：5、0、1、2、0、3、0、4、2、3、0、3、2、1、2、0、1、5、0、1。采用最近最久未使用置换算法，计算缺页中断次数和缺页中断率。解：页面置换过程如下表所示：页面访问序列50120304230321201501501203042303212015015012030423032120150501223042203312015++++-+-++++--+-+-+--缺页中断次数=12缺页中断率=12/20=60%

5.3.3Clock置换算法1.简单的Clock置换算法利用Clock算法时，只须为每页设置一位访问位，在将内存中的所有页面都通过链接指针链成一个循环队列。当某页被访问时，其访问位被置1。置换算法在选择一页淘汰时，只须检查其访问位。页号物理块号状态位P访问字段A修改位M外存地址页号物理块号状态位P访问字段A修改位M外存地址现对其中各字段说明如下：（1）状态位(存在位)P。用于指示该页是否调入内存，供程序访问时参考。（2）访问字段A。用于记录本页在一段时间内被访问的次数，或最近已有多长时间未被访问，提供给置换算法选择换出页面时参考。（3）修改位M。表示该页在调入内存后是否被修改过。由于内存中的每一页都在外存上保留一份副本，因此，若未被修改，在置换该页时就不须将该写回到外存上，以减少系统的开销和启动磁盘的次数；若已被修改，则必须将该页重写到外存上，以保证外存中所保留的始终是最新副本。（4）外存地址。用于指出该页在外存上的地址，通常是物理块号，供调入该页时使用。简单的CLOCK置换算法（近似的LRU算法）当采用简单的CLOCK算法时，只需为每页设置一位访问位，再将内存中的所有页面都通过链接指针链接成一个循环队列。当某页被访问时，其访问位被置1。置换算法在选择一页淘汰时，只需检查页的访问位，是0换出，是1重新置0且暂不换出，再按FIFO检查下一个页面。检查到最后一个页面，若其访问位仍为1，则再返到队首检查。由于该算法是循环地检查各页面的访问情况，故称为CLOCK算法，置换的是未使用过的页，又称为最近未用算法NRU（NotRecentlyUsed）。

简单Clock置换算法的流程和示例注意：是循环队列！！Page202023/2/1Page212023/2/1Page222023/2/12.改进型Clock置换算法在将一个页面换出时，如果该页已被修改过，便须将它重新写到磁盘上；但如果该页未被修改过，则不必将它拷回磁盘。同时满足两条件的页面作为首选淘汰的页。页号物理块号状态位P访问字段A修改位M外存地址Page232023/2/1页号物理块号状态位P访问字段A修改位M外存地址现对其中各字段说明如下：（1）状态位(存在位)P。用于指示该页是否调入内存，供程序访问时参考。（2）访问字段A。用于记录本页在一段时间内被访问的次数，或最近已有多长时间未被访问，提供给置换算法选择换出页面时参考。（3）修改位M。表示该页在调入内存后是否被修改过。由于内存中的每一页都在外存上保留一份副本，因此，若未被修改，在置换该页时就不须将该写回到外存上，以减少系统的开销和启动磁盘的次数；若已被修改，则必须将该页重写到外存上，以保证外存中所保留的始终是最新副本。（4）外存地址。用于指出该页在外存上的地址，通常是物理块号，供调入该页时使用。Page242023/2/1CLOCK置换算法改进型Clock置换算法考虑使用情况和置换代价，换出的最好是未使用且未被修改过的由访问位A和修改位M组合：1类(A=0,M=0)：表示该页最近既未被访问，又未被修改，是最佳淘汰页2类(A=0,M=1)：表示该页最近未被访问，但已被修改，并不是很好的淘汰页3类(A=1,M=0)：最近已被访问，但未被修改，该页有可能再被访问4类(A=1,M=1)：最近已被访问且被修改，该页可能再被访问Page252023/2/1CLOCK置换算法其执行过程可分成以下三步(1)从指针所指示的当前位置开始，扫描循环队列，寻找A=0且M=0的第一类页面，将所遇到的第一个页面作为所选中的淘汰页。在第一次扫描期间不改变访问位A。(2)如果第一步失败，即查找一周后未遇到第一类页面，则开始第二轮扫描，寻找A=0且M=1的第二类页面，将所遇到的第一个这类页面作为淘汰页。在第二轮扫描期间，将所有扫描过的页面的访问位A都置0。(3)如果第二步也失败，亦即未找到第二类页面，则将指针返回到开始的位置，并将所有的访问位A复0。然后重复第一步，如果仍失败，必要时再重复第二步，此时就一定能找到被淘汰的页。Page262023/2/1改进型Clock置换算法-示例页号块号AM05001301210103111141411最佳淘汰页次佳淘汰页0005.3.4其它置换算法

1）最少使用(LFU：LeastFrequentlyUsed)置换算法选择到当前时间为止被访问次数最少的页面被置换；每页设置访问计数器，每当页面被访问时，该页面的访问计数器加1；发生缺页中断时，淘汰计数值最小的页面，并将所有计数清零；这种算法并不能真正反映出页面的使用情况，因在每一时间间隔内只是用寄存器的一位来记录页的使用情况，因此访问1次和10000次是等效的2）页面缓冲算法(PBA)被置换页面的选择和处理：用FIFO算法选择被置换页。如果页面未被修改，就将其归入到空闲页面链表的末尾否则将其归入到已修改页面链表。此时页面在内存中并不做物理上的移动，只是将页表中的表项移到上述两链表之一需要调入新的页面时，将新页面内容读入到空闲页面链表的第一项所指的页面。空闲页面和已修改页面，仍停留在内存中一段时间，如果这些页面被再次访问，只需较小开销，而被访问的页面可以返还作为进程的内存页。当已修改页面达到一定数目后，再将它们一起调出到外存，然后将它们归入空闲页面链表，这样能大大减少I/O操作的次数。页面抖动（颠簸）的定义：在页面置换过程中的一种最糟糕的情形是，刚刚换出的页面马上又要换入主存，刚刚换入的页面马上就要换出主存，这种频繁的页面调度行为称为抖动，或颠簸。如果一个进程在换页上用的时间多于执行时间，那么这个进程就在颠簸。

抖动的原因：

频繁的发生缺页中断（抖动），其主要原因是某个进程频繁访问的页面数目高于可用的物理页帧数目。虚拟内存技术可以在内存中保留更多的进程以提髙系统效率。在稳定状态，几乎主存的所有空间都被进程块占据，处理机和操作系统可以直接访问到尽可能多的进程。但如果管理不当，处理机的大部分时间都将用于交换块，即请求调入页面的操作，而不是执行进程的指令，这就会大大降低系统效率。工作集（驻留集）概念：工作集（或驻留集）是指在某段时间间隔内，进程要访问的页面集合。经常被使用的页面需要在工作集中，而长期不被使用的页面要从工作集中被丢弃。为了防止系统出现抖动现象，需要选择合适的工作集大小。

工作集模型的原理：让操作系统跟踪每个进程的工作集，并为进程分配大于其工作集的物理块。如果还有空闲物理块，则可以再调一个进程到内存以增加多道程序数。如果所有工作集之和增加以至于超过了可用物理块的总数，那么操作系统会暂停一个进程，将其页面调出并且将其物理块分配给其他进程，防止出现抖动现象。

正确选择工作集的大小，对存储器的利用率和系统吞吐量的提嵩，都将产生重要影响。5.5请求分段存储管理方式段表机制存取方式用于标识本分段存取属性是只执行、只读还是允许读/写存在位P

用于指示该段是否已调入内存访问字段A

用于记录本页在一段时间内被访问的次数，或记录本页在最近多长时间未被访问修改位M

表示该段在调入内存后是否被修改过外存地址本段在外存上的地址，盘块块号增补位本段在运行过程中是否做过动态增长段名段长段的基址存取方式访问字段A修改位M存在位P增补位外存始址请求分段中的硬件支持

请求分段系统中的中断处理过程从中可以看出，对缺段中断的处理要比对缺页中断的处理复杂，因为段是不定长的。3.地址变换机构请求分段系统中的地址变换机构，是在分段系统地址变换机构的基础上形成的。因为被访问的段并非全在内存，因而在地址变换时，若发现所要访问的段不在内存时，必须先将所缺的段调入内存，并修改了段表之后，才能再利用段表进行地址变换。为此，在地址变换机制中又增加了某些功能，如缺段中断的请求及其处理等。图4-32示出了请求分段系统的地址变换过程。请求分段中的硬件支持

请求分段系统的地址变换过程段号S段内地址W分段的共享与保护共享段表为了实现分段共享，可在系统中配置一张共享段表所有各共享段都在共享段表中占有一表项共享进程计数count记录有多少个进程需要共享该分段存取控制字段对于一个共享段，应给不同的进程以不同的权限段号对于一个共享段，不同的进程可以各用不同的段号去共享该段分段的共享与保护段名段长内存始址状态外存始址共享进程计数count状态进程名进程号段号存取控制………………共享段表4.8.2分段的共享与保护1.共享段表图4-33共享段表项非共享段仅为一个进程所需要。当进程不再需要该段时，可立即释放该段，并由系统回收该段所占用的空间。而共享段是为多个进程所需要的，当某进程因不在需要而释放它时，系统并不回收该段所占内存区。4.8.2分段的共享与保护1.共享段表图4-33共享段表项对于同一个共享段，不同的进程可以使用不同的段号去共享该段。4.8.2分段的共享与保护1.共享段表图4-33共享段表项对于一个共享段，应给不同的进程以不同的存取权限。

分段的共享与保护共享段分配与回收共享段的分配对第一个请求使用该共享段的进程，由系统为该共享段分配一物理区，再把共享段调入该区，同时将该区的始址填入请求进程的段表的相应项中，还须在共享段表中增加一表项，填写有关数据，把count置为1；当又有其它进程需要调用该共享段时，无须再为该段分配内存，而只需在调用进程的段表中，增加一表项，填写该共享段的物理地址；在共享段的段表中，填上调用进程的进程名、存取控制等，再执行count∶=count+1操作，以表明有两个进程共享该段分段的共享与保护分段保护越界检查

存取控制检查

只读只执行读/写环保护机构

低编号的环具有高优先权，操作系统位于最核心环一个程序可以访问驻留在相同环或较低特权环中的数据一个程序可以调用驻留在相同环或较高特权环中的服务Page432023/2/13.分段保护1）越界检查在段表寄存器中放有段表长度信息；同样，在段表中也为每个段设置有段长字段。在进行存储访问时，首先，将逻辑地址空间的段号与段表长度进行比较，如果段号等于或大于段表长度，将发出地址越界中断信号；其次，还要检查段内地址是否等于或大于段长，若大于段长，将产生地址越界中断信号，从而保证了每个进程只能在自己的地址空间内运行。Page442023/2/13.分段保护2）存取控制检查在段表的每个表项中，都设置了一个“存取控制”字段，用于规定对该段的访问方式。通常的访问方式有：（1）只读。只允许程序对该段中的程序或数据进行读访问；（2）只执行。只允许程序调用该段去执行，但不准读该段的内容，也不允许对该段执行写操作；（3）读/写。允许程序对该段进行读写访问。Page452023/2/13.分段保护3）环保护机构它是一种功能较完善的保护机构。在该机制中规定：低编号的环具有高优先权，OS核心处于0环内；某些重要的实用程序和操作系统服务，占居中间环；而一般的应用程序，则被安排在外环上。在环系统中，程序的访问和调用应遵循以下规则：（1）一个程序可以访问驻留在相同环或较低特权环中的数据；（2）一个程序可以调用驻留在相同环或较高特权环中的服务。Page462023/2/13.分段保护3）环保护机构它是一种功能较完善的保护机构。在该机制中规定：低编号的环具有高优先权，OS核心处于0环内；某些重要的实用程序和操作系统服务，占居中间环；而一般的应用程序，则被安排在外环上。在环系统中，程序的访问和调用应遵循以下规则：（1）一个程序可以访问驻留在相同环或较低特权环中的数据；(内环可访问外环数据)

（2）一个程序可以调用驻留在相同环或较高特权环中的服务。3.分段保护3）环保护机构它是一种功能较完善的保护机构。在该机制中规定：低编号的环具有高优先权，OS核心处于0环内；某些重要的实用程序和操作系统服务，占居中间环；而一般的应用程序，则被安排在外环上。在环系统中，程序的访问和调用应遵循以下规则：（1）一个程序可以访问驻留在相同环或较低特权环中的数据；(内环可访问外环数据)

（2）一个程序可以调用驻留在相同环或较高特权环中的服务。(外环可请求内环服务)

分段的共享与保护

环保护机构一进程刚获得三个主存块的使用权，若该进程访问页面的次序是{1321215123}，当采用先进先出调度算法时，发生缺页次数是___次，而采用LRU算法时，缺页数是___次。A.1B.3C.4D.5E.6在请求分页存储管理系统中，设一个作业访问页面的序列为{432143543215}，设分配给该作业的存储空间有4块，且最初未装入任何页。试计算FIFO和LRU算法的失页率。(1)采用FIFO页面置换算法时,该作业运行时缺页情况如下表所示:缺页中断次数为F=10;失页率为f=10/12=83%。(2)采用LRU页面置换算法时,该作业运行时缺页情况如下表所示:缺页中断次数为F=8;失页率为f=8/12=67%。现有一请求调页系统，其页表保存在寄存器中。若有一个可用的空页或被替换的页未被修改，则它处理一个缺页中断需要8ms。若被替换页已被修改，则处理一个缺页中断需要20ms。内存存取时间为1us。假定70%被替换页被修改过，为保证有效存取时间不超过2us，可接受的最大缺页中断率是多少？参考答案：设最大缺页率为p，则

0.3p×8ms+0.7p×20ms+(1-p)×1us<=2us2400p+14000p+1-p<=2(1ms=1000us)16399p<=1p<=0.00006补充：存储保护在多道程序设计的环境下，系统中有系统程序和多个用户程序同时存在，如何保证用户程序不破坏系统程序，用户程序之间不相互干扰？这就是存储保护所要解决的问题。什么是存储保护？把系统程序空间与用户程序空间（由不同的用户空间组成）分隔开来。使多个用户程序之间隔离，保证每道程序只能在给定的区域内活动。常用的存储保护有两种：用户1用户2用户3OS系统空间用户空间120k下界寄存器130k上界寄存器程序120k130k0120k≤D<130kD——物理地址

存储保护——上下界保护存储保护——上下界保护下界寄存器：存放程序装入内存后的开始地址（首址）上界寄存器：存放程序装入内存后的末地址判别式：下界寄存器≤

物理地址

＜上界寄存器存储保护——基址、限长寄存器保护例：有一程序装入内存的首地址是500，末地址是1400，访问内存的逻辑地址是500、345、1000。

下界寄存器：500

上界寄存器：1400

逻辑地址＋装入内存的首地＝物理地址

1、500＋500＝1000500≤1000＜1400√2、345＋500＝845500≤845＜1400√

3、1000＋500＝1500500≤1500＜1400×基址限长寄存器

120k基址寄存器10k限长寄存器程序120k130k0D<10kD——逻辑地址判别式：0≤逻辑地址<限长寄存器存储保护——基址、限长寄存器保护存储保护——基址、限长寄存器保护例：有一程序装入内存的首地址是500，末地址是1400，访问内存的逻辑地址是500、345、1000。 限长寄存器：900=1400-5001、0≤500＜900√2、0≤345＜900√

3、0≤1000＜900×两种存储保护技术的区别区别：1、寄存器的设置不同；2、判别式中用的判别条件不同上下界寄存器保护法用的是物理地址基址、限长寄存器保护法用的是程序的逻辑地址对于合法的访问地址这两者的效率是相同的，对不合法的访问地址来说，上下界存储保护浪费的CPU时间相对来说要多些。华中科技大学2001某系统采用基址、限长寄存器防护方法显现存储保护，在这些方法中判断是否越界的判别式是：A0≤被访问的物理地址<基址寄存器的内容B0≤被访问的物理地址≤基址寄存器的内容C0≤被访问的逻辑地址<限长寄存器的内容D0≤被访问的逻辑地址≤限长寄