页面置换算法
标签: 操作系统
学习人数: 5310

页面置换算法是用来选择换出页面的算法。在请求页式存储管理方式中,由于一个进程运行时不是所有页面都在内存中,因此会出现缺页中断,此时内存没有空闲的物理块,就需要置换出内存中的一页,具体置换出哪一页面是由页面置换算法决定的,页面置换算法的优劣直接影响到系统的效率。

当发生缺页中断后,系统不一定会执行页面置换算法。因为发生缺页中断仅仅说明需要执行的页面没有在内存中,如果内存空间中还有空闲块,只需用缺页中断处理程序把需要的页面从外存调入内存即可,不需要页面置换算法。

 

1.最佳置换算法(OPT)

淘汰的页面将是以后永不使用的,或者是在最长时间内不再被访问的页面,显然,最佳置换算法是最优的,具有最低的缺页率。但由于实际操作中往往无法事先知道以后会引用到的所有页面的信息,因此最佳置算法无法实现,只能作为一个标准来衡量其他置换算法的优劣。

最佳置换算法可用来评价其他算法。假定系统为某进程分配了三个物理块,并考虑有页面号引用串7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1。进程运行时,先将7, 0, 1 三个页面依次装入内存。进程要访问页面2 时,产生缺页中断,根据最佳置换算法,选择将第18次访问才需调入的页面7淘汰。然后,访问页面0 时,因为它已在内存中,所以不必产生缺页中断。访问页面3 时,又会根据最佳置换算法将页面1淘汰……以此类推。发生缺页中断的次数为9 ,页面置换的次数为6。

利用最佳置换算法时的置换图

 

2.先进先出页面置换算法(FIFO)

FIFO 算法是最早出现的置换算法。 该算法总是淘汰最先进入内存的页面,即选择在内存中驻留时间最久的页面予以淘汰。该算法与实际运行时的规律部适应,因为在进程中,有的页面经常被访问。FIFO算法还会产生当所分配的物理块数增大而页故障数不减反增的异常现象,Belady异常。只有FIFO算法可能出现Belady异常,而LRU和OPT算法永远不会出现Belady异常。

进程访问页面2时,把最早进入内存的页面7换出。然后访问页面3时,把 2, 0, 1中最先进入内存的页面0换出。利用FIFO算法时进行了 12次页面置换,比最佳置换算法正好多一倍。

利用FIFO置换算法时的置换图

 

3.最近最久未使用置换算法(LRU)

FIFO置换算法的性能之所以较差,是因为它所依据的条件是各个页面调入内存的时间,而页面调入的先后并不能反映页面的使用情况。选择最近最长时间为访问的页面予以淘汰,它认为过去一段时间内未访问过的页面,在最近的将来可能也不会被访问。由于无法预测各页面将来的使用情况,只能利用“最近的过去”作为“最近的将来”的近似,因此,LRU置换算法是选择最近最久未使用的页面予以淘汰。

进程第一次对页面2访问时,将最近最久未被访问的页面7置换出去。然后在访问页面3时,将最近最久未使用的页面1换出。

LRU页面置换算法时的置换图

 

4.时钟置换算法(CLOCK)

LRU的性能最接近于OPT,但是实现起来比较困难,且开销大;FIFO实现简单,但性能差。所以操作系统的设计者尝试了很多算法,试图用比较小的开销接近LRU算法的性能,这类算法都是CLOCK算法的变体。因为算法要循环扫描缓冲区,像时钟的针一样转动,所以叫CLOCK算法。

当利用简单 Clock 算法时,只需为每页设置一位访问位,再将内存中的所有页面都通过链接指针链接成一个循环队列。 置换算法在选择一页淘汰时,只需检查页的访问位。如果是0,就选择该页换出;若为1,则重新将它置0,暂不换出,而给该页第二次驻留内存的机会,再按照 FIFO 算法检查下一个页面。

在使用位的基础上再增加一个修改位,则得到改进型CLOCK置换算法。这样,每帧都处于以下4种情况之一:

①最近未被访问,也未被修改(u=0, m= 0)。

②最近被访问,但未被修改(u=1,m= 0)。

③最近未被访问,但被修改(u= 0,m=1)。

④最近被访问,被修改(u=1,m=1)。

算法执行步骤如下:

①从指针的当前位置开始,扫描帧缓冲区。在这次扫描过程中,对使用位不做任何修改。选择遇到的第一个帧(u=0,m=0)用于替换。

②若第①步失败,则重新扫描,查找(u=0,m=1)的帧。选择遇到的第一个这样的帧用于替换。在这个扫描过程中,对每个跳过的帧,把它的使用位设置成0。

③若第②步失败,则将指针返回到开始的位置,且集合中所有帧的使用位均为0。重复第①步,并且若有必要,重复第②步,以便可以找到供替换的帧。



课后作业


登录后发布评论

暂无评论,来抢沙发