5.3　页面置换算法

本节概览：先建立「页面置换算法」的框架，再依次展开下列小节。

1. 最佳置换算法和先进先出置换算法
2. 最近最久未使用和最少使用置换算法
3. Clock置换算法
4. 页面缓冲算法(Page Buffering Algorithm，PBA)
5. 访问内存的有效时间

FIFO是最早出现的置换算法，总是淘汰最先进入内存的页面，即内存中驻留时间最久的页面。

实现简单：将已调入页面按先后次序链接成队列，设替换指针指向最老页面。

但与进程实际运行规律不相适应：经常被访问的页面(全局变量、常用函数等)可能被淘汰。

最佳置换算法由Belady于1966年提出，是理论算法。

所选被淘汰页是以后永不使用或未来最长时间不再被访问的页面，可保证最低缺页率。

因无法预知未来最长时间不再访问的页面，该算法无法实现，但可用于评价其他算法。

LFU为内存中每个页面设置移位寄存器记录被访问频率，选择最近时期使用最少的页面作为淘汰页。

FIFO依据页面调入时间，不能反映使用情况。LRU根据页面调入后的使用情况决策。

LRU选择最近最久未使用的页面淘汰。

LRU 的实现：用一个特殊栈保存当前使用的各页面号。每当访问某页面时，将其页号从栈中移出并压入栈顶。栈顶是最新被访问页面，栈底是最近最久未使用页面。

以分得 5 个物理块的进程、访问页面号序列 4,7,0,7,1,0,1,2,1,2,6 为例说明 LRU 的置换过程。

LFU 算法：为内存中每个页面设置一个移位寄存器记录被访问频率，选择最近时期使用最少的页面作为淘汰页。

简单Clock算法只为每页设置一位访问位，将内存所有页面通过链接指针链接成循环队列。

需淘汰时按序扫描，访问位为0的页被淘汰；为1则改为0并跳过，直至找到0的页。

改进型Clock置换算法

在将一个页面换出时，如果该页已被修改过，便需要将该页重新写回到磁盘上；但如果该页未被修改过，则不必将它拷回磁盘。换而言之，对于修改过的页面，在换出时所付出的开销比未修改过的页面大，或者说，置换代价大。在改进型Clock算法中，除须考虑页面的使用情况外，还须再增加一个因素——置换代价。

由访问位A和修改位M可以组合成下面四种类型的页面： 1类（A=0，M=0）：表示该页最近既未被访问，又未被修改，是最佳淘汰页。 2类（A=0，M=1）：表示该页最近未被访问，但已被修改，并不是很好的淘汰页。 3类（A=1，M=0）：表示最近已被访问，但未被修改，该页有可能再被访问。 4类（A=1，M=1）：表示最近已被访问且被修改，该页可能再被访问。

1. 页面置换算法：影响换进换出效率最重要的因素
2. 写回磁盘的频率
3. 读入内存的频率

PBA算法主要特点：显著降低页面换进换出频率，减少磁盘I/O操作次数，降低换进换出开销。

由于开销大幅减小，可采用简单的FIFO置换策略，不需特殊硬件支持，实现简单。

PBA用空闲页面链表和修改页面链表管理。

请求分页管理中EAT不仅要考虑访问页表和访问物理地址数据的时间，还须考虑缺页中断处理时间。

1. 被访问页在内存且页表项在快表中
2. 被访问页在内存但页表项不在快表中
3. 被访问页不在内存中