第6章 页面置换算法

第6章 页面置换算法

6.1 页面置换算法的概念

(1)功能目的
功能：当缺页异常发生时，需要调入新的页面而内存已满时，选择内存当中哪个物理页面被置换。
(2)设计目的：

• 尽大概淘汰页面的换入换出次数(即缺页中断的次数)。
  
• 把未来不再使用的或短期内较少使用的页面换出
  

，通常只能在局部性原理的指导下依据已往的统计数据来举行预测。
(3)页面锁定(frame locking)：

• 用于形貌必须常驻内存的逻辑页面
  
• 操纵系统的关键部分
  
• 要求响应速度的代码和数据
  
• 实现方法是，在页表中添加锁定标志位(lock bit)。
  

置换算法的评价方法：

页面置换算法分类：

• 局部页面置换算法
  
  
  
  • 置换页面的选择范围仅限于当前历程占用的物理页面
    
  • 最优算法，先进先出算法，最近最久未使用算法
    
  • 时钟算法，最不常用算法
    
  
  
• 全局页面置换算法
  
  
  
  • 置换页面的选择范围是所有可换出的物理页面
    
  • 工作集算法，缺页率算法
    
  
  

6.2 局部页面置换算法

6.2.1 最优页面置换算法

• 根本思路;置换在未来最长时间不访问的页面
  
• 算法实现：
  
  
  
  • 缺页时，计算内存中每个逻辑页面
    
  • 选择未来最长时间不访问的页面
    
  
  
• 算法特征
  
  
  
  • 缺页最少，是理想情况
    
  • 实际系统中无法实现
    
  • 无法预知每个页面在下次访问前的期待时间
    
  • 作为置换算法的性能评价依据
    
    
    
    • 在模拟器上运行某个程序，并记录每一次的页面访问情况
      
    • 第二遍运行时使用最优算法
      
      
      
      
    
    
  
  

6.2.2 先进先出算法(First-In First-Out,FIFO)

• 思路：选择在内存驻留时间最长的页面举行置换
  
• 实现：
  
  
  
  • 维护一个记录所有位于内存中的逻辑页面链表
    
  • 链表元素按驻留内存的时间排序，链首最长，链表最短
    
  • 出现缺页时，选择链首页面举行置换，新页面加到链尾
    
  
  
• 特征
  
  
  
  • 实现简单
    
  • 性能较差，调出的页面大概是经常访问的
    
  • 历程分配物理页面增加时，缺页并不一定淘汰（Belady现象）
    
  • 很少单独使用
    
    
    
    
  
  

6.2.3 最近最久未使用算法（LRU，Least Recently Used）

• 思路
  
  
  
  • 选择最长时间没有被引用的页面举行置换
    
  • 如某些页面长时间未被访问，则它们在未来还大概会长时间不会访问
    
  
  
• 实现
  
  
  
  • 缺页时，计算内存中每个逻辑页面的上一次访问时间
    
  • 选择上一次使用到当前时间最长的页面
    
  
  
• 特征
  
  
  
  • 最优置换算法的一种近似
    
  
  

LRU算法的大概实现方法

特征是开销比力大
6.2.4 时钟页面置换算法（Clock）

时钟置换算法的实现

时钟置换算法示例：

改进的Clock算法：

• 思路
  
  
  
  • 淘汰修改页的缺页处理惩罚开销
    
  
  
• 算法：
  
  
  
  • 在页面中增加修改位，并在访问时举行相应修改 （如果是读,只修改访问位，如果是写，两位都修改）
    
  • 缺页时，修改页面标志位，以跳过有修改的页面
    
  
  

执行过程：

6.2.5 最不常用算法（Least Frequently Used,LFU）

• 思路
  
  
  
  • 缺页时，置换访问次数最少的页面
    
  
  
• 实现
  
• 每个页面设置一个访问计数
  
• 访问页面时，访问计数加１
  
• 缺页时，置换计数最小的页面
  
• 特征
  
• 算法开销大
  
• 开始时频仍使用，但以后不使用的页面很难置换
  　- 解决方法：计数定期右移
  
• LRU和LFU的区别
  
• LRU关注多久未访问，时间越短越好
  
• LFU关注访问次数，次数越多越好
  

6.2.5 Belady现象和局部置换算法比力

• Belady现象
  
  
  
  • 接纳FIFO等算法时，大概出现分配的物理页面数增加，缺页次数反而升高的异常现象。
    
  • 原因
    
    
    
    • FIFO算法的置换特征与历程访问内存的动态特征抵牾
      
    • 被它置换出去的页面并不一定是历程近期不会访问的
      
    
    
  • FIFO算法有Belady现象
    
  • LRU算法没有Belady现象
    
  • 两个问题？？
    
    
    
    • 时钟/改进的时钟页面置换有没有Belady现象？
      
    • 为什么 LRU算法没有Belady现象
      
    
    
  
  

LRU算法和FIFO和Clock的比力

6.3 全局页面置换算法

• 思路
  
  
  
  • 全局置换算法为历程分配可变数目的物理页面
    
  
  
• 全局置换算法要解决的问题
  
  
  
  • 历程在差异阶段的内存需求是变革的
    
  • 分配给历程的内存也需要在差异阶段有所变革
    
  • 全局置换算法需要确定分配给历程的物理页面数
    
  
  
• CPU利用率与并发历程数存在相互促进和制约的关系
  

工作集

工作集的变革

常驻集

• 常驻集是在当前时刻，历程实际驻留在内存当中的页面聚集
  
• 工作集与常驻集的关系
  
  
  
  • 工作集是历程在运行过程中固有的性质
    
  • 常驻集取决于系统分配给历程的物理页面数目和页面置换算法
    
  
  

工作集置换算法

缺页率置换算法

• 缺页率：缺页次数/内存访问次数大概缺页均匀时间间隔的倒数(经常用这个)
  
• 影响缺页率的因素：
  
  
  
  • 页面置换算法
    
  • 分配给历程的物理页面数目
    
  • 页面巨细
    
  • 程序的编写方法
    
  
  

缺页率置换算法的思路：通过调治常驻集的巨细，使每个历程的缺页率保持在一个公道的范围内。

• 若历程缺页率过高，则增加常驻集以分配更多的物理页面
  
• 若历程缺页率过低，则淘汰常驻集以淘汰它的物理页面
  
• 访存时设置引用位标志
  
• 缺页时，计算从上次缺页时间 t_{last} 到现在的时间 t_{current} 间隔，如果时间间隔 t_{current}-t_{last} 大于常量 T，则置换所有在 [ t_{last}, t_{current}] 时间内没有被引用的页，以淘汰常驻集的巨细；如果时间间隔 t_{current}-t_{last} 小于即是常量 T，则增加缺失页到常驻集。
  

缺页率置换算法示例：

6.7 抖动和负载控制

抖动

• 抖动是指历程太多，历程分配到的页面太少，不能包罗工作集，
  
• 造成大量缺页，频仍置换，
  
• 历程运行速度变慢。
  

产生抖动的原因

• 随着驻留内存的历程数目增加，分配给每个物理页面的数不断减小，缺页率不断上升。
  

操纵系统需要在并发水平与缺页率之间到达一个平衡

• 选择一个适当的历程数目和历程需要的物理页面数。
  

负载控制：

• 通过调治并发历程数(MPL)来举行系统负载控制（每个历程的页面多少就靠置换算法来确定）
  

负载平衡
我们希望均匀缺页间隔时间（MTBF）大于即是缺页异常处理惩罚时间（PFST）。因此如下图右侧虚线以左是CPU满负荷工作也满足均匀缺页间隔时间大于即是缺页异常处理惩罚时间的区域。

来源：https://blog.csdn.net/asertgh123/article/details/111330188
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！