操作系统第四章4

第四章存储器管理赵恒主讲2定义：在进程运行过程中，若其访问的页面不在内存而需将其调入，但内存已无空闲空间时，需从内存中调出一页程序或数据，送入磁盘的对换区。但应将哪个页面调出，需根据一定的算法来确定。把选择换出页面的算法称为页面置换算法，其好坏直接影响系统的性能。一个好的置换算法应具有较低的页面更换频率。从理论上讲，应将那些以后不会再访问的页面换出，或者把那些在较长时间内不会再访问的页面换出。§5.3页面置换算法3抖动（颤动）现象（Thrashing）请求页式存储管理系统中，若页面置换算法不当，可能会导致下面的情形：刚被调出得页面，不久又要访问，因此要调入，调入后不久又被淘汰，再访问再调入，如此反复，整个系统的页面置换十分频繁，CPU时间主要花费在页面的交换上。这种导致系统效率急剧下降的现象称为抖动现象。缺页中断率过高4§5.3页面置换算法页面置换的过程（1）找出所需页面在磁盘上的位置；（2）找出可用空闲内存块。如果有，就立即使用，否则，就进行页面置换，选择一个老的页面置换到外存磁盘。（3）将所需页面装入内存，修改相应的数据结构。（4）继续执行用户进程。5§5.3页面置换算法最佳置换算法（OPT，Optimal）：最佳置换算法置换那些以后永不再使用的或者在最长的时间以后才会用到的页面。显然，这种算法的缺页率最低。然而，该算法只是一种理论上的算法，因为很难估计哪一个页面是以后永远不再使用或在最长时间以后才会用到的页面，所以，这种算法是不能实现的。尽管如此，该算法仍然是有意义的，可以把它作为衡量其它算法优劣的一个标准。⑴算法：淘汰永不使用的或是在最长时间内不再被访问的页。⑵通常可保证获得最低的缺页率。⑶无实现价值，作为其它算法的衡量标准。1.最佳(Optimal)置换算法6假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：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％72.先进先出(FIFO)（1）原理：该算法总是淘汰最先进入内存的页面，即选择在内存中的驻留时间最久的页面予以淘汰。该算法实现简单，只需把一个进程已调入内存的页面，按先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老页面。8（2）实现：已调入内存的页面，按先后次序链接成一队列。（3）依据:先进入的可能已经使用完毕。（4）随着物理块数的增多缺页率增大！（Belady现象）内存3个物理块：内存4个物理块：缺页率=9/12缺页率=10/12Belady异常现象：一般而言，分配给进程的物理块越多，运行时的缺页次数应该越少。但是Belady在1969年发现了一个反例，使用FIFO算法时，四个物理块时的缺页次数比三个物理块时的多，这种反常的现象称为Belady异常。举例：设进程有5页，访问顺序：0，1，2，3，0，1，4，0，1，2，3，4，分3块物理块和4块物理块时。92.先进先出(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。105.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％算法：最近最久未使用置换算以“最近的过去”作为“不久将来”的近似，选择最近一段时间内最久没有使用的页面淘汰掉。它的实质是：当需要置换一页时，选择在最近一段时间里最久没有使用过的页面予以淘汰。11LRU的实现：把LRU算法作为页面置换算法是比较好的，它对于各种类型的程序都能适用，但实现起来有相当大的难度，因为它要求系统具有较多的支持硬件。所要解决的问题有：一个进程在内存中的各个页面各有多久时间未被进程访问；如何快速地知道哪一页最近最久未使用的页面。为此，须利用以下两类支持硬件：1．移位寄存器：定时右移。2．栈：当进程访问某页时，将其移出压入“栈顶”，“栈底”换出。12最近最久未使用（LRU）置换算法LRU置换算法的硬件支持寄存器为了记录某进程在内存中各页的使用情况，须为每个在内存中的页面配置一个移位寄存器，可表示为访问时将Rn-1位置成1，定时信号每隔一时间间隔右移一位，则具有最小数值的寄存器所对应的页面，就是最近最久未使用的页面。R=Rn-1Rn-2Rn-3…R2R1R013实页R7R6R5R4R3R2R1R0101010010210101100实页R7R6R5R4R3R2R1R010010100102010101100t0t1实页R7R6R5R4R3R2R1R010001010012001010110t2实页R7R6R5R4R3R2R1R0110010100200101011访问1实页R7R6R5R4R3R2R1R010100101002000101011t314最近最久未使用（LRU）置换算法栈：进程访问某页时，将该页面的页号从栈中移出，再压入栈顶。用栈保存当前使用页面时栈的变化情况474074704170401741074210741207421074621074707101212615【例】假定系统为某进程分配了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%165.3.3Clock置换算法1.简单的Clock置换算法利用Clock算法时，只须为每页设置一位访问位，在将内存中的所有页面都通过链接指针链成一个循环队列。当某页被访问时，其访问位被置1。置换算法在选择一页淘汰时，只须检查其访问位。页号物理块号状态位P访问字段A修改位M外存地址17页号物理块号状态位P访问字段A修改位M外存地址现对其中各字段说明如下：（1）状态位(存在位)P。用于指示该页是否调入内存，供程序访问时参考。（2）访问字段A。用于记录本页在一段时间内被访问的次数，或最近已有多长时间未被访问，提供给置换算法选择换出页面时参考。（3）修改位M。表示该页在调入内存后是否被修改过。由于内存中的每一页都在外存上保留一份副本，因此，若未被修改，在置换该页时就不须将该写回到外存上，以减少系统的开销和启动磁盘的次数；若已被修改，则必须将该页重写到外存上，以保证外存中所保留的始终是最新副本。（4）外存地址。用于指出该页在外存上的地址，通常是物理块号，供调入该页时使用。18简单的CLOCK置换算法（近似的LRU算法）当采用简单的CLOCK算法时，只需为每页设置一位访问位，再将内存中的所有页面都通过链接指针链接成一个循环队列。当某页被访问时，其访问位被置1。置换算法在选择一页淘汰时，只需检查页的访问位，是0换出，是1重新置0且暂不换出，再按FIFO检查下一个页面。检查到最后一个页面，若其访问位仍为1，则再返到队首检查。由于该算法是循环地检查各页面的访问情况，故称为CLOCK算法，置换的是未使用过的页，又称为最近未用算法NRU（NotRecentlyUsed）。19简单Clock置换算法的流程和示例入口查寻指针前进一步，指向下一个表目页面访问位＝0?选择该页面淘汰是返回置页面访问位＝“0”否块号页号访问位指针0124034215650711替换指针注意：是循环队列！！20Page202020/1/1921Page212020/1/19OperatingSystemPage222020/1/192.改进型Clock置换算法在将一个页面换出时，如果该页已被修改过，便须将它重新写到磁盘上；但如果该页未被修改过，则不必将它拷回磁盘。同时满足两条件的页面作为首选淘汰的页。页号物理块号状态位P访问字段A修改位M外存地址OperatingSystemPage232020/1/19页号物理块号状态位P访问字段A修改位M外存地址现对其中各字段说明如下：（1）状态位(存在位)P。用于指示该页是否调入内存，供程序访问时参考。（2）访问字段A。用于记录本页在一段时间内被访问的次数，或最近已有多长时间未被访问，提供给置换算法选择换出页面时参考。（3）修改位M。表示该页在调入内存后是否被修改过。由于内存中的每一页都在外存上保留一份副本，因此，若未被修改，在置换该页时就不须将该写回到外存上，以减少系统的开销和启动磁盘的次数；若已被修改，则必须将该页重写到外存上，以保证外存中所保留的始终是最新副本。（4）外存地址。用于指出该页在外存上的地址，通常是物理块号，供调入该页时使用。OperatingSystemPage242020/1/19CLOCK置换算法改进型Clock置换算法考虑使用情况和置换代价，换出的最好是未使用且未被修改过的由访问位A和修改位M组合：1类(A=0,M=0)：表示该页最近既未被访问，又未被修改，是最佳淘汰页2类(A=0,M=1)：表示该页最近未被访问，但已被修改，并不是很好的淘汰页3类(A=1,M=0)：最近已被访问，但未被修改，该页有可能再被访问4类(A=1,M=1)：最近已被访问且被修改，该页可能再被访问OperatingSystemPage252020/1/19CLOCK置换算法(1)从指针所指示的当前位置开始，扫描循环队列，寻找A=0且M=0的第一类页面，将所遇到的第一个页面作为所选中的淘汰页。在第一次扫描期间不改变访问位A。(2)如果第一步失败，即查找一周后未遇到第一类页面，则开始第二轮扫描，寻找A=0且M=1的第二类页面，将所遇到的第一个这类页面作为淘汰页。在第二轮扫描期间，将所有扫描过的页面的访问位A都置0。(3)如果第二步也失败，亦即未找到第二类页面，则将指针返回到开始的位置，并将所有的访问位A复0。然后重复第一步，如果仍失败，必要时再重复第二步，此时就一定能找到被淘汰的页。A=0M=0A=0M=1A=1M=0A=1M=1NNN换出OperatingSystemPage262020/1/19改进型Clock置换算法-示例页号块号AM05001301210103111141411最佳淘汰页次佳淘汰页A=0M=0A=0M=1A=1M=0A=1M=1NNN换出000275.3.4其它置换算法1）最少使用(LFU：LeastFrequentlyUsed)置换算法选择到当前时间为止被访问次数最少的页面被置换；每页设置访问计数器，每当页面被访问时，该页面的访问计数器加1；发生缺页中断时，淘汰计数值最小的页面，并将所有计数清零；这种算法并不能真正反映出页面的使用情况，因在每一时间间隔内只是用寄存器的一位来记录页的使用情况，因此访问1次和10000次是等效的282）页面缓冲算法(PBA)被置换页面的