4-1.页面置换算法
① 判断置换算法好坏的标准：
具有较低的页面置换频率。
② 内存抖动：
页面的频繁更换，导致整个系统效率急剧下降，这个现象称为内存抖动。
一、最佳置换算法
1.作用
其所选择的被淘汰页，将是以后永不使用的，或者是在最长(未来)时间内不再被访问的页面。
2.例题1：
假定系统为某进程分配了3个物理块，并考虑有以下的页面号引用串： 7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1
解析：
最佳置换算法例1.png
注意：红色是我自己标注的，代表每个页号在第几位出现。
① 进程运行时，3个物理块是空的，按照题述页号引用顺序，第一个是页号7，因为物理块是空的，也就是内存中无页号，所以页号7没在内存，就得发送缺页中断，接着调入内存占用1个物理块，同理，页号0、页号1各占一个物理块，将资源占完。此时页框内是701。 ② 这时当访问页号2时，页号同样不在内存中发送缺页中断，这时3个物理块都被占用，就需要考虑将哪个淘汰掉，根据最佳置换算法，看7，0，1这3个页面哪一个是长时间未使用到的，根据页号引用顺序页面7在第18再次使用，所以选择页面7予以淘汰。 ③ 同理，运行到页号0时，内存中已有，即命中，继续往下运行。此时页框内仍是201。 ④ 运行到页号3：内存已满，发送缺页中断。因为页号1下一次得在第14位使用。所以将其替换掉。此时页框内是203。 ⑤ 运行到页号0：内存中已有，即命中，继续往下运行 。此时页框内是203。 ⑥ 运行到页号4：内存已满，发送缺页中断。因为页号0下一次得在第11位使用。所以将其替换掉。此时页框内是243。 ⑦ 运行到页号2：内存中已有，即命中，继续往下运行 。此时页框内是243。 ⑧ 运行到页号3：内存中已有，即命中，继续往下运行 。此时页框内是243。 ⑨ 运行到页号0：内存已满，发送缺页中断。页号4在之后序列中都未出现，所以淘汰。此时页框内是203。 依次类推，最后页框内为701。
3.优缺点：
采用最佳置换算法，通常可保证获得最低的缺页率。 最佳置换算法是一种理想化得的算法，它具有较好的性能，但是实际上却是不可实现的。因为这种算法需要预先知道页面的走向次序，可实际上，程序中有分支结构，页面的实际走向是不能事先确定的。所以这种算法在实际的应用中是不可行的。
二、先进先出（FIFO）页面置换算法
1.作用
最先进来最先淘汰（即选择在内存中驻留时间最久的页面予以淘汰）。 这是最早出现的置换算法。该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单，只需把一个已调入内存的页面，按先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面。但该算法与进程实际运行的规律不相适应，因为在进程中，有些页面经常被访问，比如，含有全局变量、常用函数、例程等的页面，FIFO算法并不能保证这些页面不被淘汰。
2.例题1：
假定系统为某进程分配了3个物理块，并考虑有以下的页面号引用串：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1
解析：
先进先出页面置换算法例1解.png
① 进程最开始运行时3个物理块没有页号，所以发送缺页中断从外存调入页号7，同理，调用页号0、页号1，这时资源都已被占用。此时页框内是701。 ② 当运行到页号2时，内存没有页号2，故发送缺页中断，这时就需要考虑置换掉谁。根据先进先出（FIFO）页面置换算法，谁先进就先淘汰谁。页号7先进，就先淘汰页号7。此时页框内是201。 ③ 同理，运行到页号0时，内存中已有，即命中，继续往下运行。此时页框内仍是201。 ④ 运行到页号3：此时页框内是201，页号0在内存中存在最久，所以将页号0替换成页号3。更改页框为231。 ⑤ 运行到页号0：此时页框内是231，页号1在内存中存在最久，所以将页号1替换成页号3。更改页框为230。 ⑥ 运行到页号4：页号1在内存中存在最久，所以将页号2替换成页号4。更改页框为430。 依次类推，最后页框内为701。
3.优缺点：
FIFO 页面置换算法易于理解和编程。然而，它的性能并不总是十分理想。一方面，所置换的页面可以是很久以前使用过但现已不再使用的初始化模块。另一方面，所置换的页面可以包含一个被大量使用的变量，它早就初始化了，但仍在不断使用。
三、最近一段时间最久未使用（LRU）置换算法
1.作用
根据页面调入内存的使用情况进行决策，把最近一段时间最久未使用的页面予以淘汰。 详述： FIFO置换算法性能之所以较差，是因为它所依据的条件是各个页面调入内存的时间，而页面调入先后并不能反映页面的使用情况。最近最久未使用（LRU）的页面置换算法，是根据页面调入内存后的使用情况进行决策的。因为根据程序的局部性原理，刚刚被访问过页面，可能很快还被访问到。由于无法预测各个页面将来的使用情况，只能利用“最近的的过去”作为“最近的将来”的近似，因此，LRU置换算法是选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t，当须淘汰一个页面时，选择现有页面中其t值最大的，即最近最久未使用的页面予以淘汰。
2.例题1：
假定系统为某进程分配了3个物理块，并考虑有以下的页面号引用串：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1
解析：
① 进程最开始运行时3个物理块没有页号，所以发送缺页中断从外存调入页号7，同理，调用页号0、页号1，这时资源都已被占用。此时页框内是701。 ② 当运行到页号2时，内存没有页号2，故发送缺页中断，这时就需要考虑置换掉谁。根据最近一段时间最久未使用（LRU）置换算法，最近一段时间最久未使用的页面予以淘汰。页号7在最近一段时间内（也就是在页号之前运行的时间里）页号7最久没被使用，所以就淘汰页号7。此时页框内是201 ③ 同理，运行到页号0时，内存中已有，即命中，继续往下运行。 ④ 运行到页号3：页号0刚用过，页号2页用过不久，页号1不用的时间最久，可能很快还被访问到，所以将页号1替换。此时页框内是203。 ⑤ 运行到页号0：命中，继续往下运行。此时页框内仍是203。 ⑥ 运行到页号4：页号0刚用过，页号3页用过不久，可能很快还被访问到，所以将页号2替换。此时页框内是403。 依次类推，最后页框内为107。
3.优缺点：
① 命中率,当存在热点数据时LRU的效率很好；但偶发性的,周期性的批量操作会导致LRU命中率急剧下降，缓存污染情况比较严重 。 ② 实现相对简单。 ③ 命中时需要遍历链表,找到命中的数据块索引,然后需要将数据移到头部。
4.硬件支持
（1）寄存器LRU寄存器.png
为了记录某进程在内存中各页的使用情况，须为每个在内存中的页面配置一个移位寄存器，可表示为 当进程访问某物理块时，要将相应寄存器的Rn-1位置 置1。此时，定时信号将每隔一定时间（例如100ms）将寄存器右移一位。如果我们把n位寄存器的数看做是一个整数，那么，具有最小数值的寄存器所对应的页面，就是最近最久未使用的页面。 例： 表6-1示出了某进程在内存中具有4个页面，为每个内存页面配置一个8位寄存器时的LRU访问情况。这里，把4个内存页面的序号分别定为1～4.由表可以看出，第3个内存页面的R值最小，当发生缺页时，首先将它置换出去。
LRU寄存器.png
（2）栈
可利用一个特殊的栈来保存当前使用的各个页面的页面号。每当进程访问某页面时，便将该页面的页面号从栈中移出，将它压入栈顶。因此，栈顶始终是最新被访问页面的编号，而栈底则是最近最久未使用页面的页面号。
1）例题1：
假定现有一进程所访问的页面的页面号序列为： 4，7，0，7，1，0，1，2，1，2，6 随着进程的访问，栈中页面号的变化情况如图6-9所示。在访问页面6时发生了缺页，此时页面4是最近最久未被访问的页，应将它置换出去。
LRU-栈例1解.png
四、Clock置换算法
LRU算法是较好的一种算法，但由于它要求有较多的硬件支持，故在实际应用中，大多采用LRU的近似算法。Clock算法就是用得较多的一种LRU近似算法。
1.简单的Clock置换算法
页号 | 物理块号 | 状态位P | 访问字段A | 修改位M | 外存地址 |
|---|---|---|---|---|---|
各字段说明如下： 状态位P：用于表示该页是否已调入内存，供程序访问时判断是否应该产生缺页中断。 访问位A：用于记录本页在一段时间内被是否访问过，或记录本页最近已有多长时间未被访问，供选择换出页面时参考。 修改位M：表示该页在调入内存后是否被修改过。
（1）流程和示例
简单Clock置换算法的流程和示例.png
当采用简单的Clock算法时，只需为每页设置一位访问位，再将内存中的所有页面都通过链接指针链接成一个循环的队列。 当某页被访问时，其访问位被置1。置换算法在选择一页淘汰时，只需检查页的访问位。如果是0，就选择该页面换出；若为1，则重新将它置0，暂不换出，而给该页第二次驻留内存的机会，再按照FIFO算法检查下一个页面。 当检查到队列中最后一个页面时，若其访问位仍为1，则再返回到队首去检查第一个页面。上图示出了该算法的流程和示例。由于该算法是循环地检查各个页面的使用情况，故称为Clock算法。但因该算法只有一位访问位，只能用它表示该页是否已经使用过，而置换时是将未使用过的页面换出去，故又把该算法称为最近最久未使用算法NRU(Not Recently Used)。
2.改进型Clock置换算法
（1）由访问位A和修改位M可以组合成下面四种类型的页面：
① 1类（A=0,M=0）：
表示该页最近既未被访问，又未被修改，是最佳淘汰页。
② 2类（A=0,M=1）：
表示该页最近既未被访问，但被修改，并不是很好的淘汰页。
③ 3类（A=1,M=0）：
最近既已被访问，但未被修改，该页有可能再被访问。
④ 4类（A=1,M=1）：
最近已被访问，且又被修改，该页可能再被访问。
（2）执行流程
其执行过程可分成以下三步： 1)从指针所指示的当前位置开始，扫描循环队列，寻找A=0且M=0的第一类页面，将所遇到的第一个页面作为所选中的淘汰页。在第一次扫描期间不改变访问位A。
- 如果第一步失败，即查找一周后未遇到第一类页面，则开始第二轮扫描，寻找A=0且M=1的第二类页面，将所遇到的第一个这类页面作为淘汰页。在第二轮扫描期间，将所有扫描过的页面的访问位都置0。
- 如果第二步也失败，亦即未找到第二类页面，则将指针返回到开始的位置，并将所有的访问位复0。然后重复第一步，如果仍失败，必要时再重复第二步，此时就一定能找到被淘汰的页。
五、其它置换算法
因为存在LRU算法，所以以下这些算法都不常用。
1.最少使用(LFU： Least Frequently Used)置换算法
2.页面缓冲算法(PBA： Page Buffering Algorithm)