学习笔记:页式置换算法_邓泳锋

一、最优页面置换算法

最理想的状态下,我们给页面做个标记,挑选一个最远才会被再次用到的页面。当然,这样的算法不可能实现,因为不确定一个页面在何时会被用到。

二、最近未使用页面置换算法(NRU)

系统为每一个页面设置两个标志位:当页面被访问时设置R位,当页面(修改)被写入时设置M位。当发生缺页中断时,OS检查所有的页面,并根据它们当前的R和M位的值,分为四类:

(1)!R&!M(2)!R&M(3)R&!M(4)R&M

编号越小的类,越被优先换出。即在最近的一个时钟滴答内,淘汰一个没有被访问但是已经被修改的页面,比淘汰一个被频繁使用但是“clean”的页面要好。

三、先进先出页面置换算法(FIFO)及其改进

这种算法的思想和队列是一样的,OS维护一个当前在内存中的所有页面的链表,最新进入的页面在尾部,最久的在头部,每当发生缺页中断,就替换掉表头的页面并且把新调入的页面加入到链表末尾。

这个算法的问题,显然是太过于“公正了”,没有考虑到实际的页面使用频率。

一种合理的改进,称为第二次机会算法。即给每个页面增加一个R位,每次先从链表头开始查找,如果R置位,清除R位并且把该页面节点放到链表结尾;如果R是0,那么就是又老又没用到,替换掉。

四、时钟页面置换算法(clock)

这种算法只是模型像时钟,其实就是一个环形链表的第二次机会算法,表针指向最老的页面。缺页中断时,执行相同的操作,包括检查R位等。

五、最近最少使用页面置换算法(LRU)

缺页中断发生时,置换未使用时间最长的页面,称为LRU(least recently used)。

LRU是可以实现的,需要维护一个包含所有页面的链表,并且根据实时使用情况更新这个链表,代价是比较大的。

于是,需要对这个算法进行一些改进,也可以说是简化。将每一个页面与一个计数器关联,每次时钟终端,扫描所有页面,将每个页面的R位加到计数器上,这样就大致跟踪了每个页面的使用情况。这种方法称为NFU(not frequently used,最不常用)算法。

这样还是存在一个问题,即很久之前的一次使用,与最近的使用权重相等。

所以,再次改进,将计数器在每次时钟滴答时,右移一位,并把R位加在最高位上。这种算法,称为老化(aging)算法,增加了最近使用的比重。

老化算法只能采用有限的位数,所以可能在一定程度上精度会有所损失。


文章录入:邓泳锋 责任编辑:邓泳锋
分享本文: