操作系统中10种页面置换算法的总结

   页面置换算法总结

当发生缺页中断时，操作系统必须将内存中选择一个页面置换出去为要调入的新页面腾出空间。

   那究竟选择哪一个淘汰哪一个一面比较好呢？

1.      最优页面置换算法

选择最长时间内不会被访问的页面丢掉。越久越好。但是理论上不能实现。

2.      最近未使用页面置换算法(NRU)算法

找到最久没有使用的页面置换出去，页面被访问时设置R位，修改时设置M位，R位定期清0；

把页面分四类

0类.未被访问，未被修改的R=M=0

1类未被访问，被修改R=0,M=1

2类被访问，未被修改R=1,M=0

3类被访问，被修改R=1，M=1

系统从类类编号最小的非空类随机挑选一个置换

3．先进先出FIFO

   维持一个保存当前所有页面的链表，新使用的插在链表尾，从头部淘汰老旧页面，使得最久进入的排在头部，

4 .第二次机会置换算法

   改进版FIFO，淘汰旧页面时先从检查头部页面的R位，若为1，则说明此页面最近被使用过，置R=0，把它加到尾部去，重新设置其装入时间为当前时刻，继续搜寻，若为0，如果此页面被写过，把它写回磁盘再淘汰，若未被写，直接淘汰

5.时钟页面置换算法

   维持一个保存所有页面的环形链表，一个指针指向最老页面，发生缺页中断时，检查指针指向页面，若R=0，则更新它，若R=1,清除R位，指针前移，继续搜索

6.最近最少使用页面置换算法LRU

  找到最久没有使用过的置换之。需要特殊硬件实现（如利用一个n*n的矩阵）

7.最不常用算法NFU

为每个页面维持一个初值0的计数器，每次时钟中断，由操作系统扫描所有页面，把计数器加上当前的R位更新，这样每个计数器的值大概反映了被访问的频繁程度。缺页中断时，置换计数器数值最小的页面

8. 老化算法-改进的LRU

  在R位加进之前，先把计数器值右移一位，把R位加到计数器最左边，

特点：每次时钟滴答只能记下一位，因此如果两个页面在同一个时钟滴答期间被访问是不能分出的，而且由于计数器是有限位数，假设是8位，如果很多页面在8个时钟滴答都未被访问的话，就都是全零位无法区分，但实际情况是，若已经这么久没有被访问了，该页面一般也不是很重要了

9.工作集页面置换算法

   定义一个工作集：在过去t秒内被访问的页面的集合。

扫描所有页面，若R==1，说明在这个时钟滴答被访问了，它应该是工作集的一部分，把当前时间写入页表项的“上次使用时间“ 。若R==0，且生存时间（当前时间-上次使用时间）>t,置换它，如果<t,记住最小时间

10.工作集时钟页面置换算法

  维持一个以页框为元素的循环表，形成一个环，每个表项包括上次使用时间，R位M位

缺页中断时，首先检查指针指向的页面，若R位==1，则说明它最近被访问了，把R位置为0，指针指向下一个位置，若R==0，若它的生存时间>t且此页面干净，置换之、

如果不干净，继续往前走。（因为可能前方存在旧的又干净的页面）。

   页面置换算法小结：

1.      最优算法

不可能实现，可作为基准

2.       NRU算法

最近未使用算法，LRU粗糙的近似

3.      FIFO先进先出

 通过维护一个页面的链表来记录页面被装入内存的顺序，淘汰最老的页面。但可能会置换重要的页面

4二次机会算法

  FIFO‘较大改进，淘汰最老且最近没有使用过的页面

5时钟算法

   二次机会的实现，避免移动链表元素

6．LRU算法

   优秀但实现成本高

7. NFU算法

   LRU近似，效率不高

8.老化算法

  LRU的高效率实现

9.工作集算法

  开销大

10.工作集时钟算法

  有效