OS酱：“哎呀内存太小了，人家又缺页了！”

曾经终败给现在 2023-01-16 12:26 56阅读 0赞

# ![53f56a2a6acca267509306fe393d7130.png][] #

# 操作系统--虚页面管理之页面置换算法 #

系统的内存并不是无限大，操作系统会为每个程序分配内存，当访问的地址块不在内存中，就要从外存（即硬盘，U盘等）调入，这就是所说的缺页异常。

当发生缺页异常时，操作系统会选择一个页面进行换出从而为新进来的页面腾出空间。对于被置换的页面有以下情况：

1.  如果要被换出的页面只被访问而没被修改，那么直接将此页面丢弃。
2.  如果要被换出的页面被修改，那么为了使得外存中的数据保证正确，先要将内存中的数据写入外存，然后在丢弃。

虽然，被置换页面的可以随机选择，但是不同的选择，所导致后续系统访存开销是不一样，甚至会出现很极端的情况，每次访存都发生缺页中断，极大的增加系统额外的访存开销。

很多的页面置换算法被提出用于操作系统，但是在其他各类应用，无论是数学还是经济学都有类似的涉猎，今天我们就来讨论一下这些算法。

# OPT算法（最佳置换算法） #

**算法特点：**

最佳置换算法是由 **Belady** 于1966年提出的一种理论上的算法。每次选择以后永不使用的， 或许是在最长(未来)时间内不再被访问的页面的页面被淘汰。显然OPT算法是最优的，但是在实际操作往往无法预知未来，所以OPT只存在理论而不能真的实现，通常用于衡量其他置换算法的优劣。

**算法流程：**

在缺页中断发生时，首先从 *主存*中移出永远不再需要的页面；如无这样的页面存在，则选择最长时间不需要访问的页面。

举例如下：

![5456d2fc4a315e0ef87d94ffdcbe0337.png][]

缺页9次，总访问次数12次缺页率：6/12 = 50%

# FIFO算法（先进先出置换算法） #

## Belady异常： ##

采用FIFO算法时，如果对一个进程未分配它所要求的全部页面，有时就会出现分配的页面数增多但缺页率反而提高的异常现象。

**实现方法：**

最简单的页面置换算法，每次淘汰最先调入内存的页面。由操作系统维护一个所有在当前内存中的页面的链表，最早进入的放在表头，最新进入的页面放在表尾，每次淘汰队首页面。因为先进入的页面可能已经使用完毕，所以不会再被使用的概率可能性较大，优先淘汰。但是FIFO容易产生Belady异常。

该算法实现比较简单，对具有线性顺序访问的程序比较合适，而对其他情况效率不高。因为经常被访问的页面，往往在内存中停留最久，结果这些常用的页面却因变老而被淘汰。

## 举例如下： ##

![dda9741258fa156c5bbf937620c2f30b.png][]

缺页9次，总访问次数12次缺页率：9/12 = 75%

# LRU算法 (最近最久未使用算法) #

利用局部性原理，根据一个作业在执行过程中过去的页面访问==历史来推测未来==的行为。它认为过去一段时间里不曾被访问过的页面，在最近的将来可能也不会再被访问。所以，这种算法的实质是：当**需要淘汰一个页面时，总是选择在最近一段时间内最久不用的页面予以淘汰**。 即淘汰最近最长时间未访问过的页面。

LRU置换算法的硬件支持

*  **寄存器**为每个在内存中的页面配置一个移位寄存器，用来记录某进程在内存中各页的使用情况。移位寄存器表示为R=Rn-1Rn-2Rn-3…R2R1R0当进程访问某物理块时，要将相应寄存器的Rn-1位置成1;同时，每隔一定时间将寄存器右移一位；如果把n位寄存器的数看作一个整数，那么具有最小数值的寄存器所对应的页面，就是最近最久未使用的页面。
 *  **栈**利用一个特殊的栈来保存当前使用的各个页面的页面号。每当进程访问某页面时，便将该页面的页面号从栈中移出，将它压入栈顶。因此，**栈顶始终是最新被访问页面的编号，而栈底则是最近最久未使用页面的页面号**。

## 举例如下： ##

![9f9016dff1de7cb157484a1977af406e.png][]

缺页7次，总访问次数12次缺页率：7/12 = 58.3%

实际上，LRU算法根据各页以前的情况，是“向前看”的，而最佳置换算法则根据各页以后的使用情况，是“向后看”的。**LRU性能较好，但需要寄存器和栈的硬件支持**。

LRU是堆栈类的算法。理论上可以证明，堆栈类算法不可能出现Belady异常。

FIFO算法基于队列实现，不是堆栈类算法。

**LRU算法的性能接近于OPT，但是实现起来比较困难，且开销大；FIFO算法实现简单，但性能差。**

# Clock算法（时钟置换算法） #

也称为NRU算法（最近未使用算法）是LRU和FIFO的折中算法。

**实现：**CLOCK算法是给每一个页面设置一个访问位，用来标识是否最近被访问过，Clock维护的是内存中页面组成的循环链表。当页面被装入内存时，或是内存中的页面被访问时，访问位被置为1。若内存已被装满，那就需要淘汰一个页面，于是指针就从上一个被淘汰的页面的下一个位置开始，顺序去遍历这循环列表，访问到访问位为1的页面时，就把该访问位置0，继续遍历，只要遇到访问位为0的页面时，淘汰该页面。其实调入内存也是访问，那么上面就变成了：

1.  访问则置1
2.  替换则遍历
3.  遍历遇1置0，遇0替换。
4.

![211e6463e3976155257103f7bc8da3d1.png][]

## 举例如下： ##

内存中共分配3个页面资源

![2501f1da01a3f40a0c445806db3da503.png][]

# 改进后的Clock算法(二次机会法） #

由 访问位A 和 修改位M 可以组合成下面四种类型的页面：

1.  最近既未被访问，又未被修改(Visit=0, Modify=0) ：是最佳淘汰页。
2.  最近未被访问，但已被修改(Visit=0, Modify=1)：并不是很好的淘汰页。
3.  最近已被访问， 但未被修改(Visit=1, Modify=0)：该页有可能再被访问。
4.  最近已被访问且被修改(Visit=1, Modify=1)：该页可能再被访问。

**执行过程：**5. 查找00，有，淘汰，算法结束！继续循环直到一圈结束，未找到则下一步；6. 查找01，有，淘汰，算法结束！未找到继续循环遍历直到一圈结束，在此过程中将Visit位置为“0”，未找到则下一步；7. 重复第一步。

优点：减少磁盘I/O；缺点：几轮扫描，增加开销！

[53f56a2a6acca267509306fe393d7130.png]: /images/20221022/dd3dd0243bad44cba0703af2709df8c3.png
[5456d2fc4a315e0ef87d94ffdcbe0337.png]: /images/20221022/61ae560d470742f988b11e24db27ca76.png
[dda9741258fa156c5bbf937620c2f30b.png]: /images/20221022/4c6f273cacd84d99847adc4173e57e8d.png
[9f9016dff1de7cb157484a1977af406e.png]: /images/20221022/fc13398fd9204cd4aeb5b396a3cb6da0.png
[211e6463e3976155257103f7bc8da3d1.png]: /images/20221022/277efc5f4bad4bee98c2b6ba250468ee.png
[2501f1da01a3f40a0c445806db3da503.png]: /images/20221022/ee0a9c268c7d48af9400857bec4f5b00.png