3.4 页面置换算法_nfu算法

作者：盐析白兔 | 2024-02-29 03:45:17

踩

nfu算法

  3.4 页面置换算法 

  1. 最优页面置换算法 

  将每个页面在接下来首次被访问前要执行的指令数作为标记，每次置换标记最大的页面。但是它不可能实现，因为与最短作业优先调度算法一样，无法知道各个页面下一次在什么时候被访问。 

  2. 最近未使用页面置换算法（NRU） 

  页表项中有页面的访问位R位和修改位M位。 

  当启动一个进程时，它的所有页面两个位都初始化成0，且R位会被定期清零（如每次时钟中断）以区别最近没有被访问的页面和被访问的页面。 

  缺页中断时，操作系统检查页面的R位和M位，分为4类： 

  第一类可能是第三类页面R位被时钟中断清零后得到。 

  NRU每次随机地从类编号最小的非空类中挑选一个页面淘汰。 

  3. 先进先出页面置换算法（FIFO） 

  操作系统维护一个所有当前在内存中的页面的链表，最新进入的放表尾。缺页中断时淘汰表头页面。 

  4. 第二次机会页面置换算法 

  改进FIFO，每次检查表头页面的R位，如果R位为0则淘汰，如果R位为1则将R位清零，并将该页面放到表尾，之后继续搜索。 

  如果所有页面的R位都为1，则退化成FIFO算法。 

  5. 时钟页面置换算法 

  第二次机会页面置换算法组织成环形链表（时钟），用一个指针，每次检查指针指向的页面，若R为0则淘汰，并在此处插入新页面，若R为1则清零并指针下移。 

  6. 最近最少使用页面置换算法（LRU，想法好难实现） 

  发生缺页中断时，置换未使用时间最长的页面。 

  如要在内存中维护一个所有页面的链表，最近最多使用的页面在表头，反之在表尾，困难在每次方位内存都要重新更新整个链表，找到一个页面删除并移动到表头，非常耗时。 

  有一些使用特殊硬件实现LRU，硬件有一个64位计数器，在每条指令执行完自动加一。每次访问内存后，把当前计数值保存到被访问页面的页表项。中断时，找到值最小的页面淘汰。 

  还有一种是硬件维持一个n*n的矩阵（假设n个页框），访问页框k时，把第k行全设为1，第k列全设为0.任何时刻，二进制数值最小的行就是最近最少使用的。依此类推。 

  7. 软件模拟LRU（NFU算法） （粗糙地近似LRU） 

  每个页面与一个软件计数器关联，初始化为0。每次时间中断由操作系统扫描所有页面，把每个页面的R位加到计数器上。这样计数器大体上跟踪了各个页面的被访问频繁程度。 

  缺点是：从来不忘记任何事情。 

  8. 老化算法： （良好的近似LRU） 

  是NFU算法的改良，它同样是缺页中断时置换计数器最小的页面。 

  R位被加进去之前，计数器右移一位，并将R位加到计数器最左端的位。 

  与LRU算法区别是它只有有限位数，而且越recent的影响越大。 

  9.工作集页面置换算法 

  请求调页：页面在需要时被调入，而不预先装入 

  预先调页：跟踪工作集，在进程运行前预先装入其工作集，减少缺页中断率 

  工作集：一个进程当前正在使用的页面集合 

  颠簸：每执行几条指令程序就发生一次缺页中断 

  算法：缺页中断时，淘汰一个不在工作集中的页面。 

  key：确定哪些页面在工作集 

方案一：维护移位寄存器保存最近使用的k个页面号，每次使用新页面就更新，但开销特别大。
方案二：近似，不是向后找最近k次内存访问，而是最近10ms等的内存访问用到的页面集合。该时间是进程实际占用CPU的时间。该时间设为t。

  同时会用硬件来预先设置R位和M位为0，同时每个时钟中断后也会有一个定期时钟中断来清除R位。 

  这样算法就可以： 

  每次，检查R位，若R位为1，明显在工作集中，则把当前实际时间更新进页表项的“上次使用时间”。若R位为0，则计算它的生存时间（当前实际时间-上次使用时间），若它大于t则表示不在工作集，因此可以置换它（但扫描还要继续，因为扫描同时有更新时间的作用），若小于t则要记录这些小于t的生存时间最长的（“上次使用时间”最小的），如果扫描完都找不到就淘汰这么一个生存时间最长的。 

  特别地，如果R位全为1，就随机选一个，但优先选一个干净页面。 

  缺点：缺页中断时要扫描整个页表才能确定淘汰的页面，比较费时。 

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

  组织成循环表（环） 

  同样用一个指针，具体算法同上面的算法，只是在发现一个R位为0且生存时间大于t的页面时，如果它是脏的（被修改过的），为了避免由于调度写磁盘操作引起进程切换，所以指针继续走，对下一个页面操作。（最后没有符合的就只能~咯！） 

  11. 总结 

  最好的两种应该是老化算法（基于LRU）和工作集时钟算法（基于工作集）。 

  2018/03/14 23:53 

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/盐析白兔/article/detail/163549