操作系统-页面置换算法

页面置换、抖动、工作集

Posted by MetaNetworks on November 18, 2019
本页面总访问量

页面置换算法

  • 影响页面换进换出的若干因素
    • 页面置换算法
    • 写回磁盘的频率
      • 使用缓冲区
    • 读入内存的频率
  • 最佳(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$里,进程实际所要访问页面的集合