操作系统-页面置换算法

页面置换算法

• 影响页面换进换出的若干因素
  • 页面置换算法
  • 写回磁盘的频率
    • 使用缓冲区
  • 读入内存的频率

• 最佳(Optimal)置换算法

  • 无法预知哪一个页面是未来最长时间内不再被访问的，因此无法实现

• 先进先出(FIFO)置换算法

  页面在内存里越久，越容易被换出

  • FIFO一般是最差的

• 最近最久未使用置换算法(Least Recently Used)

  • 根据历史使用情况进行预测
  • 要用硬件来实现
    • 寄存器
      • 每页的访问情况用一个寄存器来表示
        • 不断右移，若使用则置1，否则置0，则使用多的1则多，使用少的1则少
    • 栈（特殊的）
      • 比如栈为：470<-，使用7，则变成407<-
      • 栈底的元素很久没用，换走

• 最少使用置换算法(Least Frequency Used)

  • 相比LRU来说，使用相同的方法。但精度差一些，但是计算开销小一些

• Clock置换算法

  上面的LRU算法等未区分使用页的用途，事实上用途对页面置换很重要，所以Clock算法考虑到

  • 简单Clock算法

    • 为每页设置一个访问位，当访问到页A，则把页A的访问位(A)置1
    • 置换算法运行时，如果发现页访问位为0，则置换；否则将访问位置为0，给页第二次驻留内存的机会，然后再按照FIFO算法检查下一个页面

  • 改进型Clock算法

    考虑修改，如果修改过，则需要将其重新写回磁盘。所以增加一个修改位(M)

    • 分类
      • 1类： A=0,M=0，最理想的淘汰页
      • 2类：A=0,M=1，并不是最好的
      • 3类：A=1,M=0，可能再次被访问
      • 4类：A=1,M=1，可能再次被访问
    • 算法
      • 第一遍找1类
      • 第二遍找2类，将所有扫描过的页面的访问位置0（这样就使得第3类和第4类变成了第1类和第2类(上图加粗2个类的原因)）

• 其他置换算法

  • 页面缓冲算法

    要换出的页面，选择不立即存入磁盘，放入磁盘高速缓存。所以此时高速缓存越多，写回磁盘次数越少

    • PBA

      显著降低页面换进换出的频率，有此算法则可以使用简单页面置换算法如FIFO，不需要特殊硬件，同时可以满足用户需求

      • 空闲页面链表
        • 没有被修改过的被置换的页面放置于此。一旦其他进程要调入此页面则可以重新取回去
      • 修改页面链表
        • 注意断电影响
        • 部分程序会使用写入穿透

抖动和工作集

• 抖动

  请求分页式虚拟存储器系统的性能卓越，能有效减少内存碎片，提高利用率和吞吐量，但如果进程太多，会频繁发生缺页情况，又会对系统的性能产生很大的影响。CPU一直在处理缺页中断。

  注意：抖动是整体抖动，是整个系统抖动

• 抖动的预防措施
  • 采取局部置换策略
    • 进程只能在分配给自己的内存空间内进行置换
  • 把工作集算法融入到处理机调度中
    • 在调度程序从外存调入作业之前，必须先检查每个进程在内存的驻留页面是否足够多，多则调入，否则不调入。反之，如果有些程序页面不足，则应先对那些缺页率高的作业增加新的物理块
  • 利用"L=S"准则调节缺页率
    • L为缺页之间的平均时间、S是平均缺页时间
      • 如果L<S：则说明频繁缺页，处理不来
      • L>>S：则说明磁盘能力未充分利用
      • L约等于S：都可达到最大利用率
  • 选择暂停的进程

• 工作集

  PS：为了解决抖动问题

  需要知道每个进程所需要的内存帧数。最小内存帧数是由操作系统的宏定义出来的。

  • 定义
    • 是指在某段时间间隔$\Delta$里，进程实际所要访问页面的集合

• Previous
  算法-最佳二叉树(OBST)
• Next
  操作系统-内存块调度实验