本文主要是介绍操作系统理论 第五章（虚拟存储器）—第三节（页面置换算法），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
写在前面：
- 本系列笔记主要以《计算机操作系统（汤小丹…）》为参考，大部分内容出于此书，笔者的工作主要是挑其重点展示，另外配合下方视频链接的教程展开思路，在笔记中一些比较难懂的地方加以自己的一点点理解（重点基本都会有标注，没有任何标注的难懂文字应该是笔者因为强迫症而加进来的，可选择性地忽略）。
- 视频链接：操作系统（汤小丹等第四版）_哔哩哔哩_bilibili
一、概述
在进程运行过程中，若其访问的页面不在内存而需将其调入，但内存已无空闲空间时，需从内存中调出一页程序或数据，送入磁盘的对换区，但应将哪个页面调出，需根据一定的算法来确定。把选择换出页面的算法称为页面置换算法，其好坏直接影响系统的性能。
不适当的算法可能会导致进程发生“抖动”，即刚被换出的页很快又要被访问，需要将它重新调入，此时又需要再选一页调出，而此刚被调出的页很快又被访问，又需将它调入，如此频繁地更换页面，以致一个进程在运行中把大部分时间都花费在页面置换工作上，我们称该进程发生了“抖动”。
一个好的置换算法应具有较低的页面更换频率，从理论上讲，应将那些以后不会再访问的页面换出，或者把那些在较长时间内不会再访问的页面换出。
二、最佳置换算法和先进先出算法
1、最佳置换算法
（1）最佳置换算法是由Belady于1966年提出的一种理论上的算法，其所选择的被淘汰页面将是以后永不使用的，或许是在最长（未来）时间内不再被访问的页面。
（2）采用最佳置换算法通常可保证获得最低的缺页率，但由于人们目前还无法预知一个进程在内存的若干个页面中，哪一个页面是未来最长时间内不再被访问的，因而该算法是无法实现的，但可以利用该算法去评价其它算法。
（3）假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串。
①进程运行时，先将7、0、1三个页面装入内存。
②以后，当进程要访问页面2时，将会产生缺页中断，此时OS根据最佳置换算法将选择页面7予以淘汰，这是因为页面0将作为第5个被访问的页面，页面1是第14个被访问的页面，而页面7则要在第18次页面访问时才需调入。
③下次访问页面0时，因它已在内存而不必产生缺页中断。
④当进程访问页面3时，又将引起页面1被淘汰，因为它在现有的1、2、0三个页面中，将是以后最晚才被访问的。
⑤以此类推，可得到下图所示的最佳置换算法置换图。
2、先进先出算法
（1）该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。
（2）该算法实现简单，只需把一个进程已调入内存的页面按先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面。但该算法与进程实际运行的规律不相适应，因为在进程中有些页面经常被访问，比如含有全局变量、常用函数、例程等的页面，先进先出算法（FIFO）并不能保证这些页面不被淘汰。
（3）沿用上面的例子，采用FIFO算法进行页面置换。
①当进程第一次访问页面2时，将把第7页换出，因为它是最先被调入内存的。
②在第一次访问页面3时，又将把第0页换出，因为它在现有的2、0、1三个页面中是最老的页。
③以此类推，可得到下图所示的先进先出算法置换图。
（4）如果对一个进程未分配它所要求的全部页面，有时就会出现分配的页面数增多但缺页率反而提高的异常现象，这种现象发生在FIFO（先进先出）置换算法。
三、最近最久未使用和最少使用置换算法
1、最近最久未使用置换算法（LRU）
（1）LRU置换算法根据页面调入内存后的使用情况进行决策。由于无法预测各页面将来的使用情况，只能利用“最近的过去”作为“最近的将来”的近似，因此，LRU置换算法是选择最近最久未使用的页面予以淘汰。
（2）该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t，当需淘汰一个页面时，选择现有页面中其t值最大的，即最近最久未使用的页面予以淘汰。
（3）沿用上面的例子，利用LRU算法进行页面置换。
①当进程第一次对页面2进行访问时，由于页面7是最近最久未被访问的，故将它置换出去。
②当进程第一次对页面3进行访问时，第1页成为最近最久未使用的页，将它换出。
③以此类推，可得到下图所示的LRU算法置换图。
（4）LRU置换算法虽然较好，但需较多的硬件支持，为了了解一个进程在内存中的各个页面各有多少时间未被进程访问，以及如何快速地知道哪一页是最近最久未使用的页面，需有以下两类硬件之一的支持：
①寄存器：
为了记录某进程在内存中各页的使用情况，须为每个在内存中的页面配置一个移位寄存器，可表示为，当进程访问某物理块时，要将寄存器相应的
位置成1，此时定时信号将每隔定时间将寄存器右移一位，如果把n位寄存器的数看作是一个整数，那么具有最小数值的寄存器所对应的页面，就是最近最久未使用的页面。（简单说，这个寄存器的作用就是计时，记录一个页面自上次被访问以来所经历的时间）
下图示出了某进程在内存中具有8个页面、为每个内存页面配置一个8位寄存器时的LRU访问情况，把8个内存页面的序号分别定为1~8。由图可以看出，第3个内存页面的R值最小，当发生缺页时，应首先将它置换出去。
②栈：
可利用一个特殊的栈保存当前使用的各个页面的页面号，每当进程访问某页面时，便将该页面的页面号从栈中移出，将它压入栈顶，因此，栈顶始终是最新被访问页面的编号，而栈底则是最近最久未使用页面的页面号。
假定现有一进程，它分有五个物理块，所访问的页面的页面号序列如下图所示。
[1]在前三次访问时，系统将依次将4、7、0放入栈中，4是栈底，0是栈顶；第四次是访问第7页，使7成为栈顶。
[2]在第八次访问页面2时，该进程的五个物理块都已装满，在第九和十次访问时，未发生缺页。
[3]在第11次访问页面6时发生了缺页，此时页面4是最近最久未被访问的页，应将它置换出去。
2、最少使用置换算法（LFU）
（1）在采用LFU算法时，应为在内存中的每个页面设置一个移位寄存器，用来记录该页面被访问的频率。该置换算法选择在最近时期使用次数最少的页面作为淘汰页。
（2）在最少使用置换算法中采用了移位寄存器方式，每次访问某页时，便将该移位寄存器的最高位置1，再每隔一定时间右移一次，这样，在最近一段时间使用最少的页面将是最小的页。LFU置换算法的页面访问图与LRU置换算法的访问图完全相同，或者说，利用这样一套硬件既可实现LRU 算法，又可实现LFU 算法。
（3）需要说明的是，这种算法并不能真正反映出页面的使用情况，因为在每一时间间隔内只是用寄存器的一位来记录页的使用情况，因此，在该时间间隔内，对某页访问1次和访问1000次是完全等效的。
四、Clock置换算法
1、简单的Clock置换算法
（1）为每页设置一位访问位，再将内存中的所有页面都通过链接指针链接成一个循环队列，当某页被访问时，其访问位被置1。置换算法在选择一页淘汰时，只需检查页的访问位，如果是0就选择该页换出；若为1则重新将它置0，暂不换出，给予该页第二次驻留内存的机会，再按照FIFO算法检查下一个页面，当检查到队列中的最后一个页面时，若其访问位仍为1，则再返回到队首去检查第一个页面。
（2）简单的Clock置换算法又称最近未使用算法。
2、改进型Clock置换算法
（1）在改进型Clock算法中，除须考患页面的使用情况外，还须再增加一个因素——置换代价（对于修改过的页面，在换出时需要重新写回磁盘上，开销比较大），这样，选择页面换出时，既要是未使用过的页面，又要是未被修改过的页面，把同时满足这两个条件的页面作为首选淘汰的页面。
（2）由访问位A和修改位M可以组合成下面四种类型的页面：
①A=0，M=0：表示该页最近既未被访问，又未被修改，是最佳淘汰页。
②A=0，M=1：表示该页最近未被访问，但已被修改，并不是很好的淘汰页。
③A=1，M=0：表示最近已被访问，但未被修改，该页有可能再被访问。
④A=1，M=1：表示最近已被访问且被修改，该页可能再被访问。
（3）在进行页面置换时，可采用与简单 Clock算法相类似的算法，其差别在于该算法须同时检查访问位与修改位，以确定该页是四类页面中的哪一种。其执行过程可分成以下三步：
①从指针所指示的当前位置开始扫描循环队列，寻找A=0且M=0的第一类页面，将所遇到的第一个页面作为所选中的淘汰页。在第一次扫描期间不改变访问位A。
②如果第一步失败，即查找一轮后未遇到第一类页面，则开始第二轮扫描，寻找A=0且M=1的第二类页面，将所遇到的第一个这类页面作为淘汰页。在第二轮扫描期间，将所有扫描过的页面的访问位都置0。
③如果第二步也失败，亦即未找到第二类页面，则将指针返回到开始的位置，并将所有的访问位复0，然后重复第一步，即寻找A=0目M=0的第一类页面，如果仍失败必要时再重复第二步，寻找A=0且M=1的第二类页面，此时就一定能找到被淘汰的页。
五、页面缓冲算法
1、影响页面换进换出效率的若干因素
（1）页面置换算法。影响页面换进换出效率最重要的因素，无疑是页面置换算法，因为一个好的页面置换算法，可使进程在运行过程中具有较低的缺页率，从而可以减少页面换进换出的开销。
（2）写回磁盘的频率。对于已经被修改过的页面，在将其换出时应当写回磁盘。如果是采取每当有一个页面要被换出时就将它写回磁盘的策略，这意味着每换出一个页面，便需要启动一次磁盘，但如果在系统中已建立了一个已修改换出页面的链表，则对每一个要被换出的页面（已修改），系统可暂不把它们写回磁盘，而是将它们挂在已修改换出页面的链表上，仅当被换出页面数目达到一定值时，再将它们一起写回到磁盘上，这样就显著地减少了磁盘 I/O的操作次数，或者说，减少已修改页面换出的开销。
（3）读入内存的频率。在设置了已修改换出页面链表后，在该链表上就暂时有一批装有数据的页面，如果有进程在这批数据还未写回磁盘时需要再次访问这些页面时，就不需从外存上调入，而直接从已修改换出页面链表中获取，这样也可以减少将页面从磁盘读入内存的频率，减少页面换进的开销。
2、页面缓冲算法PBA的实现
（1）PBA算法的主要特点是：
①显著地降低了页面换进、换出的频率，使磁盘I/O的操作次数大为减少，因而减少了页面换进、换出的开销。
②正是由于换入换出的开销大幅度减小，才能使其采用一种较简单的置换策略，如先进先出算法，它不需要特殊硬件的支持，实现起来非常简单。
（2）VAX/NMS操作系统中所使用的页面缓冲算法，内存分配策略上采用了可变分配和局部置换方式，系统为每个进程分配一定数目的物理块，系统自己保留一部分空闲物理块。为了能显著地降低页面换进、换出的频率，在内存中设置了如下两个链表：
①空闲页面链表：
实际上该链表是一个空闲物理块链表，是系统掌握的空闲物理块，用于分配给频繁发生缺页的进程、以降低该进程的缺页率，当这样的进程需要读入一个页面时，便可利用空闲物理块链表中的第一个物理块来装入该页。
当有一个未被修改的页要换出时，实际上并不将它换出到外存，而是把它们所在的物理块挂在空闲链表的末尾，这些挂在空闲链表上的未被修改的页面中是有数据的，如果以后某进程需要这些页面中的数据时，便可从空闲链表上将它们取下，免除了从磁盘读入数据的操作，减少了页面换进的开销。
②修改页面链表：
它是由已修改的页面所形成的链表，设置该链表的目的是为了减少已修改页面换出的次数，当进程需要将一个已修改的页面换出时，系统并不立即把它换出到外存上，而是将它所在的物理块挂在修改页面链表的末尾，这样做的目的是降低将已修该页面写回磁盘的频率，降低将磁盘内容读入内存的频率。
这篇关于操作系统理论 第五章（虚拟存储器）—第三节（页面置换算法）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
