操作系统中的页面置换算法

最近读完了《现代操作系统》。页面置换算法的读书笔记。其他的笔记慢慢整理一下在博客做个备份。
虚拟内存的基本思想:每个程序都拥有自己的内存空间,这个空间被分割成很多块,每一块称为一页/页面,每一页有连续的地址范围,这些页被映射到物理内。
页面置换算法 1.最优页面置换算法,每个页面都可以用在该页面首次被访问前所需要执行的指令数作为标记。因此我们选择标记最大的页面,也就是把不愉快的事情往后拖延。但是,唯一的问题是无法实现。 2.最近未使用页面置换算法。系统每一个页面设置两个状态位,当页面被访问时设置R位,当被修改时设置M位,包含在页表项中,初始时,都被设置0,R被定期地清零,以区别最近没有被访问和被访问的页面。NRU算法随机的从类编号最小的非空类中挑选一个页面淘汰之, 根据R和W可以将页面分为4类 0没有被访问,没有被修改/1没有被访问,被修改/2已被访问,没有被修改/3已被访问,已被修改。第一类只有在定期清R的时候才会出现。 隐含的意思是,淘汰一个没有被访问的已修改页面要比淘汰一个被频繁使用的干净页面要好。 3.先进先出置换,找出最先进入的替换掉,很少单独使用 4.第二次机会页面置换算法。FIFO可能将经常使用的页面置换出来。为此,检查最老页面的r位,如果R为0,则既老又没有被使用,则就置换掉,如果是1,就清0,放在链表尾,修改装入时间为最新。继续搜索。 5.时钟页面置换算法,第二次机会算法经常要在链表中移动页面,更好的方法是将页面保存在一个类似钟面的环形链表中,表针指向最老的页面。发生缺页时,如果R是0就 淘汰该页面,并插入新页面,然后表针前移,如果是1,就清除R并前移,直到找到一个R位为0的页面。这也是时钟的由来 6.最近最少使用页面置换算法。在发生缺页时,置换未使用时间最长的页面,这个策略称为LRU,最简单的一个实现策略是有一个64位计数器,每条指令执行完加1.每个页表项必须有一个足够容纳这个计数器值的域,每次访问内存后,将C值保存到被访问页面的页表项,一旦中断,检查所有页面项的计数器值,找到最小的即可。 7.NFU最不常用算法,是LRU的软件模拟实现。每个页面与一个软件计数器管理。初值为0,每次时钟中断时,操作系统扫描内存中的所有页面,将每个页面中的R位值加到他的计数器上,计数器的值即为访问的频繁程度。该算法的问题是记住的事情太多,如果第一次执行扫描的时间最长。比如第一次某个页面的值很大。这个很大的值会影响到下一次扫描,结果操作系统将置换有用的页面而不是不再使用的页面。 8.修改一下NFU:R位被加进之前,将计数器右移一位,同时将R加到计数器的左端。即为老化算法 9.工作集页面置换算法。一个进程当前正在使用的页面的集合称作他的工作集。基本思路是找出一个不在工作集中的页面并淘汰它。 10.工作集时钟页面置换算法。基于时钟算法,并且使用了工作集信息。

页面调度算法总结; 最好的两种算法是老化算法和工作集时钟算法,分别基于LRU和工作集。具有良好的页面调度性能。

comments powered by Disqus