页面置换算法（OPT、FIFO、LRU、CLOCK、改进的时钟置换算法）

• 请求分页 存储管理与 基本分页 存储管理的主要区别&＃xff1a;
  ①、在程序执行过程中&＃xff0c;当所访问的信息不在内存时&＃xff0c;由操作系统负责将所需信息从外存调入内存【操作系统要提供请求调页功能&＃xff0c;将缺失页面从外存调入内存】&＃xff0c;然后继续执行程序。
  ②、若内存空间不够&＃xff0c;由操作系统负责将内存中暂时用不到的信息换出到外存【操作系统要提供页面置换的功能&＃xff0c;将暂时用不到的页面换出外存】。
  

&＃xff08;一&＃xff09;最佳置换算法&＃xff08;OPT&＃xff09;

• 最佳置换算法&＃xff08;OPT&＃xff0c;Optimal&＃xff09;&＃xff1a;每次选择淘汰的页面将是以后永不使用&＃xff0c;或者在最长时间内不再被访问的页面&＃xff0c;这样可以保证最低的缺页率。
• 例&＃xff1a;假设系统为某进程分配了三个内存块&＃xff0c;并考虑到有一下页面号引用串&＃xff08;会依次访问这些页面&＃xff09;&＃xff1a;7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1
  
• 最佳置换算法可以保证最低的缺页率&＃xff0c;但实际上&＃xff0c;只有在进程执行的过程中才能知道接下来会访问到的是哪个页面。操作系统无法提前预判页面访问序列。因此&＃xff0c;最佳置换算法是无法实现的。

&＃xff08;二&＃xff09;先进先出置换算法&＃xff08;FIFO&＃xff09;

• 先进先出置换算法&＃xff08;FIFO&＃xff09;&＃xff1a;每次选择淘汰的页面是最早进入内存的页面
• 实现方法&＃xff1a;把调入内存的页面根据调入的先后顺序排成一个队列&＃xff0c;需要换出页面时选择队头页面即可。
• 队列的最大长度取决于系统为进程分配了多少个内存块。
• 例&＃xff1a;假设系统为某进程分配了三个内存块&＃xff0c;并考虑到有以下页面号引用串&＃xff1a;3, 2, 1, 0, 3, 2, 4, 3, 2, 1, 0, 4
  
  
  
• 例&＃xff1a;假设系统为某进程分配了四个内存块&＃xff0c;并考虑到有以下页面号引用串&＃xff1a;3, 2, 1, 0, 3, 2, 4, 3, 2, 1, 0, 4
  
• Belady 异常——当为进程分配的物理块数增大时&＃xff0c;缺页次数不减反增的异常现象。
• 只有 FIFO 算法会产生 Belady 异常。另外&＃xff0c;FIFO算法虽然实现简单&＃xff0c;但是该算法与进程实际运行时的规律不适应&＃xff0c;因为先进入的页面也有可能最经常被访问。因此&＃xff0c;算法性能差

&＃xff08;三&＃xff09;最近最久未使用置换算法&＃xff08;LRU&＃xff09;

• 最近最久未使用置换算法&＃xff08;LRU&＃xff0c;least recently used&＃xff09;&＃xff1a;每次淘汰的页面是最近最久未使用的页面
• 实现方法&＃xff1a;赋予每个页面对应的页表项中&＃xff0c;用访问字段记录该页面自上次被访问以来所经历的时间t。
• 当需要淘汰一个页面时&＃xff0c;选择现有页面中 t 值最大的&＃xff0c;即最近最久未使用的页面。
  
• 例&＃xff1a;假设系统为某进程分配了四个内存块&＃xff0c;并考虑到有以下页面号引用串&＃xff1a;1, 8, 1, 7, 8, 2, 7, 2, 1, 8, 3, 8, 2, 1, 3, 1, 7, 1, 3, 7
  
• 该算法的实现需要专门的硬件支持&＃xff0c;虽然算法性能好&＃xff0c;但是实现困难&＃xff0c;开销大

&＃xff08;四&＃xff09;时钟置换算法&＃xff08;CLOCK&＃xff09;

• 最佳置换算法性能最好&＃xff0c;但无法实现&＃xff1b;先进先出置换算法实现简单&＃xff0c;但算法性能差&＃xff1b;最近最久未使用置换算法性能好&＃xff0c;是最接近OPT算法性能的&＃xff0c;但是实现起来需要专门的硬件支持&＃xff0c;算法开销大。
• 时钟置换算法是一种性能和开销较均衡的算法&＃xff0c;又称CLOCK算法&＃xff0c;或最近未用算法&＃xff08;NRU&＃xff0c;NotRecently Used&＃xff09;
• 简单的CLOCK 算法实现方法&＃xff1a;为每个页面设置一个访问位&＃xff0c;再将内存中的页面都通过链接指针链接成一个循环队列。
  ①、当某页被访问时&＃xff0c;其访问位置为1。当需要淘汰一个页面时&＃xff0c;只需检查页的访问位。
  ②、如果是0&＃xff0c;就选择该页换出&＃xff1b;如果是1&＃xff0c;则将它置为0&＃xff0c;暂不换出&＃xff0c;继续检查下一个页面&＃xff0c;若第一轮扫描中所有页面都是1&＃xff0c;则将这些页面的访问位依次置为0后&＃xff0c;再进行第二轮扫描&＃xff08;第二轮扫描中一定会有访问位为0的页面&＃xff0c;因此简单的CLOCK 算法选择一个淘汰页面最多会经过两轮扫描&＃xff09;
  
• 例&＃xff1a;假设系统为某进程分配了五个内存块&＃xff0c;并考虑到有以下页面号引用串&＃xff1a;1, 3, 4, 2, 5, 6, 3, 4, 7
  
  
  
  

&＃xff08;五&＃xff09;改进型的时钟置换算法

• 简单的时钟置换算法仅考虑到一个页面最近是否被访问过。事实上&＃xff0c;如果被淘汰的页面没有被修改过&＃xff0c;就不需要执行I/O操作写回外存。只有被淘汰的页面被修改过时&＃xff0c;才需要写回外存。
• 因此&＃xff0c;除了考虑一个页面最近有没有被访问过之外&＃xff0c;操作系统还应考虑页面有没有被修改过。在其他条件都相同时&＃xff0c;应优先淘汰没有修改过的页面&＃xff0c;避免I/O操作。这就是改进型的时钟置换算法的思想。
• 修改位&＃61;0&＃xff0c;表示页面没有被修改过&＃xff1b;修改位&＃61;1&＃xff0c;表示页面被修改过。
• 为方便讨论&＃xff0c;用&＃xff08;访问位&＃xff0c;修改位&＃xff09;的形式表示各页面状态。如&＃xff08;1&＃xff0c;1&＃xff09;表示一个页面近期被访问过&＃xff0c;且被修改过。
• 算法规则&＃xff1a;将所有可能被置换的页面排成一个循环队列。
• ①、第一轮&＃xff1a;从当前位置开始扫描到第一个&＃xff08;0, 0&＃xff09;的帧用于替换。本轮扫描不修改任何标志位。
  
• ②、第二轮&＃xff1a;若第一轮扫描失败&＃xff0c;则重新扫描&＃xff0c;查找第一个&＃xff08;0, 1&＃xff09;的帧用于替换。本轮将所有扫描过的帧访问位设为0。
  
• ③、第三轮&＃xff1a;若第二轮扫描失败&＃xff0c;则重新扫描&＃xff0c;查找第一个&＃xff08;0, 0&＃xff09;的帧用于替换。本轮扫描不修改任何标志位。
  
• ④、第四轮&＃xff1a;若第三轮扫描失败&＃xff0c;则重新扫描&＃xff0c;查找第一个&＃xff08;0, 1&＃xff09;的帧用于替换。
  
• 由于第二轮已将所有帧的访问位设为0&＃xff0c;因此经过第三轮、第四轮扫描一定会有一个帧被选中&＃xff0c;因此改进型CLOCK置换算法选择一个淘汰页面最多会进行四轮扫描