写点什么

OS 酱:“哎呀内存太小了,人家又缺页了!”

用户头像
风骨散人
关注
发布于: 2021 年 04 月 10 日
OS酱:“哎呀内存太小了,人家又缺页了!”

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


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

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

  1. 如果要被换出的页面只被访问而没被修改,那么直接将此页面丢弃。

  2. 如果要被换出的页面被修改,那么为了使得外存中的数据保证正确,先要将内存中的数据写入外存,然后在丢弃。

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

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

OPT 算法(最佳置换算法)

算法特点:

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

算法流程:

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

举例如下:



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

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

Belady 异常:

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


实现方法:

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


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

举例如下:



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

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

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

LRU 置换算法的硬件支持

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

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


举例如下:


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

发布于: 2021 年 04 月 10 日阅读数: 15
用户头像

风骨散人

关注

还未添加个人签名 2021.03.22 加入

大学僧,ACM退役选手。 名字的含义:希望可以通过努力,能力让家人拥有富足的生活而不是为了生计而到处奔波。“世人慌慌张张,不过是图碎银几两。偏偏这碎银几两,能解世间惆怅,可让父母安康,可护幼子成长 …”

评论

发布
暂无评论
OS酱:“哎呀内存太小了,人家又缺页了!”