『操作系统』内存管理-虚页面管理之页面置换算法

『操作系统』内存管理-虚页面管理之页面置换算法

OPT 算法(最佳置换算法)

特点:

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

首先从 ==主存== 中移出==永远不再需要==的页面;如无这样的页面存在,则选择==最长时间不需要访问==的页面。

例题如下:

物理页面 2 3 2 1 5 2 4 5 3 2 5 2
物理块 1 2 2 2 2 2 2 4 4 4 4 4 4
物理块 2 3 3 3 3 3 3 3 3 2 2 2
物理块 3 1 5 5 5 5 5 5 5 5
是否缺页

缺页 9 次,总访问次数 12 次
缺页率:6/12 = 50%

FIFO 算法(先进先出置换算法)

Belady 异常:

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


==最简单==的页面置换算法,每次淘汰最先调入内存的页面。实现方式只需要一个队列即可。将所有放入内存的页面排成一队,每次淘汰队首页面。
因为先进入的页面可能已经使用完毕,所以不会再被使用的概率可能性较大,优先淘汰。但是 FIFO 容易产生 Belady 异常。

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

例题如下:

物理页面 2 3 2 1 5 2 4 5 3 2 5 2
物理块 1 2 2 2 3 1 5 2 4 3
物理块 2 3 3 1 5 2 4 3 5
物理块 3 1 5 2 4 3 5 2
是否缺页

缺页 9 次,总访问次数 12 次
缺页率:9/12 = 75%

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

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

LRU 置换算法的硬件支持

  • 寄存器
    为每个在内存中的页面配置一个移位寄存器,用来记录某进程在内存中各页的使用情况。移位寄存器表示为
    R=Rn-1Rn-2Rn-3…R2R1R0
    当进程访问某物理块时,要将相应寄存器的 Rn-1 位置成 1;
    同时,每隔一定时间将寄存器右移一位;
    如果把 n 位寄存器的数看作一个整数,那么具有最小数值的寄存器所对应的页面,就是最近最久未使用的页面。

  • 利用一个特殊的栈来保存当前使用的各个页面的页面号。每当进程访问某页面时,便将该页面的页面号从栈中移出,将它压入栈顶。因此,栈顶始终是最新被访问页面的编号,而栈底则是最近最久未使用页面的页面号
物理页面 2 3 2 1 5 2 4 5 3 2 5 2
物理块 1 2 2 2 2 2 3 3
物理块 2 3 3 5 5 5 5
物理块 3 1 1 4 4 2
是否缺页

缺页 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 替换。

例题如下:

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

改进后的 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;
缺点:几轮扫描,增加开销!


『操作系统』内存管理-虚页面管理之页面置换算法
https://chiamzhang.github.io/2024/06/29/『操作系统』内存管理-虚页面管理之页面置换算法/
Author
Chiam
Posted on
June 29, 2024
Licensed under