《2022年存储器管理之页面置换算法 .pdf》由会员分享，可在线阅读，更多相关《2022年存储器管理之页面置换算法 .pdf（6页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第十七讲存储器管理之页面置换算法1 引言在进程运行过程中，若其访问的页面不在内存而需将其调入，但内存已无空闲空间时，需从内存中调出一页程序或数据，送入磁盘的对换区。但应将哪个页面调出，需根据一定的算法来确定。把选择换出页面的算法 称为页面置换算法，其好坏直接影响系统的性能。刚被淘汰出内存的页面，过后不久又要访问它，需要再次将其调入，而该页调入内存后不入又再次被淘汰出内存，然后又要访问它，如此反复，这种现象称为抖动（又称颠簸）。一个好的置换算法应具有较低的页面更换频率。从理论上讲，应将那些以后不会再访问的页面换出，或者把那些在较长时间内不会再访问的页面换出。2 常用的页面置换算法2.1 最佳置换
2、算法（The best optimal）最佳置换算法是由Belady 于 1966年提出的一种理论上的算法。其所选择的被淘汰页面，将是以后永不使用的，或许是在最长(未来)时间内不再被访问的页面。采用最佳置换算法，通常可保证获得最低的缺页率。由于人们无法预知一个进程在内存的若干个页面中，哪一个页面是将来最长时间内不再被访问的页面，因此该算法无法实现。但该算法可以用来评价其他算法。例：就是课本上的例子假定系统为某进程分配了三个物理块，7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1 2.2 先进先出页面置换算法(FIFO)该算法淘汰最先进入内存的页面，即选择在内存中驻
3、留时间最久的页面淘汰。Belady 现象：使用 FIFO 算法时，在未给进程或作业分配足它所要求的页面数时，有时会出现分配的页面增多，缺页次数反而增加的奇怪现象，就是Belady 现象。例：和上例一样例子：1，2，3，4，1，2，5，1，2，3，4，5 名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 6 页 -内存 3 个物理页面：缺页9 次内存 4 个物理页面：缺页10 次异常！Belady现象2.3 最近最久未使用置换算法(Least Recently Used,LRU)2.3.1 算法描述算法思想：利用“最近的过去”作为“最近的将来”。选择最近最久未使用的页面淘汰。该算法对
4、每个页面设置一个访问字段，用于记录一个页面自上次被访问以来所经历的时间t,每次淘汰 t 值最大的页面，也就是最近最久未使用的页面。例：缺页 12 次，总访问次数20 次，缺页率12/20602.3.2 硬件支持两类硬件支持：寄存器、栈。为每个在内存中的页面配置一个移位寄存器，用来记录某进程在内存中各页的使用情况。移位寄存器表示为R=012321.RRRRRRnnn当进程访问某物理块时，要将相应寄存器的1nR位置成 1。此时，定时信号将每隔一定时间将寄存器右移一位。如果把 n 位寄存器的数看作一个整数，那么具有最小数值的寄存器所对应的页面，就是最近最久未使用的页面。例：某进程在内存中具有8 个页
5、面，为每个页面配置一个8 位寄存器。如下图：2.3.3栈利用一个特殊的栈来保存当前使用的各个页面的页面号。每当进程访问某页面时，便将该页面的页面号从栈中移出，将它压入栈顶。因此，栈顶始终是最新被访问页面的编号，而栈底则是最近最久未使用页面的页面号。如下图：名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 6 页 -2.4CLOCK 置换算法4 4 4 7 7 4 7 0 0 4 0 7 7 4 0 7 1 1 4 7 1 0 0 4 7 0 1 1 4 7 0 1 2 2 4 7 0 2 1 1 4 7 0 1 2 2 7 0 1 2 6 6 设一进程访问页面的页面号序列为：4，7
6、，0，7，1，0，1，2，1，2，6 随着进程的访问，栈中页面号的变化情况：R0 R1 R2 R3 R4 R5 R6 R7 R 实页0 0 0 1 0 1 1 0 0 1 1 1 0 1 1 0 1 0 0 1 0 1 0 1 1 0 0 0 1 0 0 1 0 1 0 1 1 0 0 1 1 0 0 1 0 0 1 0 1 2 3 4 5 6 某进程具有 8个页面时的 LRU访问情况名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 6 页 -是一种最近最久未使用算法的近似算法。2.4.1 简单的 CLOCK 置换算法算法描述：每页设置一位访问位，某页被访问时，其访问位被置1。内存
7、中的所有页链接成一个循环队列；循环检查各页面的使用情况，访问位为“0”，选择该页淘汰；访问位为“1”，复位访问位为“0”，查询指针前进一步。因为该算法只有一位访问位，只能用它表示该页是否使用过，置换时只能将未使用过的页面置换出去，因此称为“最近未使用”置换算法（NRU）例子：入口查寻指针前进一步，指向下一个表目页面访问位0?选择该页面淘汰是返回置页面访问位“0”否块号页号访问位指针0124034215650711替换指针名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 6 页 -2.4.2改进型的 CLOCK 置换算法1 由访问位 A和修改位 M可以组合成下面四种类型的页面：1类(
8、A=0,M=0):表示该页最近既未被访问，又未被修改，2类(A=0,M=1)：表示该页最近未被访问，但已被修改，3类(A=1,M=0)：最近已被访问，4类(A=1,M=1):最近已被访问且被修改，该页可能再被访问。2 执行过程访问位 A，修改位 M共同表示一个页面的状态：四种状态：00 01 10 11。三轮扫描：第一轮：查找00 页面，若找到，则淘汰所找到的第一页，结束；若未找到，下一步；第二轮：查找01 页面，若找到，则淘汰所找到的第一页，结束；，若未找到，下一步；（第二轮中，所有扫描过的页面，A位复位为“0”）第三轮：所有页面A位复位为“0”，重复第一步。(1)从指针所指示的当前位置开始
9、，扫描循环队列，寻找 A=0且 M=0的第一类页面，将所遇到的第一个页面作为所选中的淘汰页。在第一次扫描期间不改变访问位A；(2)如果第一步失败，即查找一周后未遇到第一类页面，则开始第二轮扫描，寻找A=0 且M=1的第二类页面，将所遇到的第一个这类页面作为淘汰页。在第二轮扫描期间，将所有扫描过的页面的访问位都置0(3)如果第二步也失败，亦即未找到第二类页面，则将指针返回到开始的位置，并将所有的访问位复0。然后重复第一步，如果仍失败，必要时再重复第二步，此时就一定能找到被淘汰的页。2.5其他置换算法2.5.1 最少使用(LFU：Least Frequently Used)置换算法选择到当前时间为
10、止被访问次数最少的页面被置换；名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 6 页 -每页设置访问计数器，每当页面被访问时，该页面的访问计数器加1；发生缺页中断时，淘汰计数值最小的页面，并将所有计数清零；2.5.2页面缓冲算法(PBA：Page Buffering Algorithm)它是对 FIFO 算法的发展，通过被置换页面的缓冲，有机会找回刚被置换的页面.被置换页面的选择和处理：用FIFO 算法选择被置换页，把被置换的页面放入两个链表之一。?如果页面未被修改，就将其归入到空闲页面链表的末尾?否则将其归入到已修改页面链表。需要调入新的物理页面时，将新页面内容读入到空闲页面链表的第一项所指的页面，然后将第一项删除（从空闲链表摘下）。空闲页面和已修改页面，仍停留在内存中一段时间，如果这些页面被再次访问，只需较小开销，而被访问的页面可以返还作为进程的内存页。当已修改页面达到一定数目后，再将它们一起调出到外存，然后将它们归入空闲页面链表，这样能大大减少I/O 操作的次数。名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 6 页 -