页面置换算法


文中部分图片来自于学堂在线清华大学的操作系统公开课,链接

概念

置换算法的功能和目标

功能
  • 当出现却也异常,需调入新页面而内存已满时,置换算法选择被置换的物理页面
设计目标
  • 尽可能减少页面的调入调出册数
  • 把未来不再访问或短期内不访问的页面调出

页面锁定

  • 描述必须常驻内存的逻辑页面,不能换出
  • 操作系统的关键部分
  • 或者是要求响应速度的代码和数据
  • 页表中加入锁定标志位(lock bit)

置换算法的评价方法

  • 记录进程访问内存的页面轨迹
  • 评价方法:模拟页面置换的行为,记录产生缺页的次数;更少的缺页意味着更好的性能

置换算法的分类

局部页面置换算法:

  • 置换算法的选择仅限于当前进程占用的物理页面内
  • 最优算法、先进先出算法、最近最久未使用算法
  • 时钟算法、最不常用算法

全局页面置换算法:

  • 置换页面的选择范围是所有可换出的物理页面
  • 工作集算法、缺页率算法

局部页面置换算法

最优页面置换算法(OPT)

基本思路:置换在未来最长时间不访问的页面

算法实现

  • 缺页时,计算内存中每个逻辑页面的下一次访问时间
  • 选择未来最长时间不访问的页面

特征

  • 缺页最少,是理想情况

  • 实际系统中无法实现

  • 无法预知每个页面在下次访问前的等待时间

  • 可以作为其他置换算法的性能评价依据

    在模拟器上运行某个程序,并记录每一次的页面访问情况

    第二遍运行时使用最优算法

最优算法示例:

最后一次访问d时产生缺页,因为后面没有了访问,因此此时置换哪一个页面都可以,最优页面置换算法一共缺页2次。

先进先出算法(FIFO)

思路:选择在内存中驻留时间最长的页面进行置换

实现;

  • 维护一个记录所有位于内存中的逻辑页面链表
  • 链表元素按驻留内存的时间排序,链首最长,链尾最短
  • 出现缺页时,选择链首页面进行置换,新页面添加到链尾

特征:

  • 实现简单
  • 性能较差,调出的页面可能是经常访问的
  • 进程分配物理页面数增加时,缺页并不一定减少(Belady现象)
  • 很少单独使用

最近最久未使用算法(LRU)

思路:

  • 选择最长时间没有被引用的页面进行置换
  • 如果某些页面长时间未被访问,则他们在将来还可能会长时间不会访问(局部性原理)

实现:

  • 缺页时,计算内存中每个逻辑页面的上一次访问时间
  • 选择上一次使用到当前时间最长的页面

特征:

  • 是最优置换算法的一种近似,通过统计过去来预测未来
  • 非常复杂,开销很大

实现方法:

1.页面链表

  • 系统维护一个按最近一次访问时间排序的页面链表,链表的首节点是最近刚刚使用过的页面,链表尾结点是最久未使用的页面
  • 访问内存时,找到相应的页面,并把它移到链表之首
  • 缺页时,置换链表尾结点的页面

2.活动页面栈

  • 访问页面时,将次页号压入栈顶,并将栈内相同的页号抽出
  • 缺页时,置换栈底的页面

####时钟置换算法(Clock)

思路:仅对页面的访问情况进行大致统计

数据结构:

  • 在页表项中增加访问位,描述页面在过去一段时间内的访问情况
  • 各页面组织成环形链表
  • 指针指向最先调入的页面

算法:

  • 访问页面时,在页表项记录页面的访问情况
  • 缺页时,从指针处开始顺序查找未被访问的页面进行置换

特征:

  • 时钟算法是LRU和FIFO的折中,对过去的访问情况进行了统计,但又没有LRU统计的那么详细

算法实现:

  • 页面装入内存时,访问位初始化为0

  • 访问页面(读/写)时,访问位置1

  • 缺页时,从指针当前位置顺序检查环形链表

    访问位为0,则置换该页

    访问位为1,则访问位置为0,并且指针移动到下一个页面,直到找到可置换的页面

改进的Clock算法

思路:减少修改页的缺页处理开销

算法:

  • 在页面中增加修改位,并在访问时进行相应修改
  • 缺页时,修改页面标志位,以跳过有修改的页面

示例:

最不常用算法(LFU)

思路:缺页时,置换访问次数最少的页面

实现:

  • 每个页面设置一个访问计数
  • 访问页面时,访问计数加1
  • 缺页时,置换计数最小的页面

特征:

  • 算法开销大
  • 开始时频繁使用,但以后不使用的页面很难置换
  • 改进:对于计数比较大的页面,计数会定期右移,减小计数,使其可以被置换出去

LRU和LFU的区别:

  • LRU关注的是多久未访问,时间越短越好
  • LFU关注的是访问次数,次数越多越好

示例:

Belady现象

现象:

采用FIFO等算法时,可能出现分配的物理页面数增加,缺页次数反而升高的异常现象

原因:

  • FIFO算法的置换特征与进程访问内存的动态特征矛盾
  • 被置换出去的页面并不一定是进程近期不会访问的

结论:

如果内存中页数更小的集合是内存更大页数集合的子集,这种算法称为stack algorithm。stack algorithm(如LRU)不会出现Belady现象

LRU、FIFO和Clock的比较

1.LRU算法和FIFO本质上都是先进先出的思路

  • LRU依据页面最近访问时间排序
  • LRU需要动态调整顺序
  • FIFO依据页面进入内存的时间排序
  • FIFO的页面进入时间是固定不变的

2.LRU可以退化成FIFO

  • 如页面进入内存后没有被访问,最近访问时间与进入内存的时间相同
  • 例如:给进程分配3个物理页面,逻辑页面的访问顺序为1、2、3、4、5、6、1、2、3、…

3.LRU算法性能好,但系统开销大;FIFO算法系统开销小,会发生Belady现象,Clock算法是他们的折衷

  • 缺页访问时,不动态调整页面在链表中的顺序,仅做标记
  • 缺页时,再把它移动到链表末尾

4.对于未被访问的页面,Clock和LRU算法的表现一样好,FIFO也是如此

5.对于被访问过的页面,Clock算法不能记录准确的访问顺序,而LRU算法可以

全局页面置换算法

概述

在局部置换算法中没有考虑不同进程之间的差异,在某些情况下,给进程多增加一个物理页面,缺页率就会大幅下降

思路:全局置换算法为进程分配可变数目的物理页面

问题

  • 进程在不同阶段的内存需求是变化的
  • 分配给进程的内存也需要在不同阶段有所变化
  • 全局置换算法需要分配给进程的物理页面数

CPU利用率与并发进程数的关系

CPU利用率与并发进程数存在相互促进和相互制约的关系

  • 进程数少时,提高并发进程数,可提高CPU的利用率
  • 并发进程导致内存访问增加
  • 并发进程的内存访问会降低访存的局部性特征
  • 局部性特征的下降会导致缺页率上升和CPU利用率下降

工作集

一个进程当前正在使用的逻辑页面集合,可表示为二元函数W(t,d)

  • t是当前的执行时刻
  • d称为工作集窗口,即一个定长的页面访问时间窗口
  • W(t, d)是指在当前时刻t前(不包含t时刻)的d时间窗口中的所有访问页面所组成的集合
  • |W(t, d)|指工作集的大小,即页面数目

工作集的变化

  • 进程开始执行后,随着访问新页面逐步尽力较稳定的工作集
  • 当内存访问的局部性区域的位置大致稳定时,工作集大小也大致稳定
  • 局部性区域的位置改变时,工作集快速扩张和收缩过渡到下一个稳定值

常驻集

在当前时刻,进程实际驻留在内存当中的集合页面

工作集和常驻集的关系

  • 工作集是进程在运行过程中固有的性质
  • 常驻集取决于系统分配给进程的物理页面数目和页面置换算法

缺页率与常驻集的关系

  • 常驻集包含工作集时,缺页较少
  • 工作集发生剧烈变动(过渡)时,缺页较多
  • 进程常驻集大小达到一定数目后,缺页率也不会明显下降

工作集置换算法

思路:换出不在工作集中的页面

窗口大小d:当前时e刻前d个内存访问的页引用是工作集,d被称为窗口大小

实现方法

  • 访存链表:维护窗口内的访存页面链表
  • 访存时,换出不在工作集的页面,更新访存链表
  • 缺页时,换入页面,更新访存链表

工作集置换算法访存时的开销比较大,要进行判断和换出,在缺页时只换入页面就可以,开销较小;而局部置换算法在缺页时的开销比较大

缺页率置换算法

缺页率:

缺页次数 / 内存访问次数 或 缺页平均时间间隔的倒数

影响缺页率的因素:

  • 页面置换算法
  • 分配给进程的物理页面数目
  • 页面大小
  • 程序的编写方法

一般情况下,随着进程物理页面数的增加,缺页率是降低的。因此,可以通过调节常驻集的大小,使每个进程的缺页率保持在一个合理的范围内

  • 若缺页率过高,则增加常驻集以分配更多的物理页面
  • 若缺页率过低,则减小常驻集以减少它的物理页面

实现

  • 访存时,设置引用位标志
  • 缺页时,计算从上次缺页时间t1到现在t2的时间
  • 如果t2 - t1> T,则置换所有在[t1, t2]时间内没有被引用的页
  • 如果t2 - t1 < T,则增加确实页到常驻集中

抖动问题

抖动

  • 进程物理页面太少,不能包含工作集
  • 造成大量缺页,频繁置换
  • 进程运行速度变慢

产生抖动的原因:随着驻留内存的进程数目增加,分配给每个进程的物理页面数不断减少,缺页率不断上升

操作系统需要在并发水平和缺页率之间达到一个平衡,要选择一个适当的进程数目和进程需要的物理页面数

负载控制

通过调节并发进程数(MPL)来进行系统负载控制

  • 所有进程需要的物理页面数 = 内存大小
  • 平均缺页间隔时间(MTBF)= 缺页异常处理时间(PFST)

在这两个标准之间的进程并发数目是可以有比较高的CPU利用率,系统达到了比较均衡的繁忙状态


文章作者: likai
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 likai !
评论
 上一篇
python多进程 python多进程
Python中的multiprocessing模块支持多进程编程,主要功能有支持子进程、进程间通信、同步等,涉及到的类有Process,Queue,Pipe,Lock等。 Process类介绍定义: Process(group=None,
2020-08-12
下一篇 
虚拟存储管理(一) 虚拟存储管理(一)
虚拟存储的需求前面的物理内存管理都基于一个基本要求:执行指令必须在物理内存中。这使得程序的大小被限制在物理内存的大小以内。实际上,在程序中,并不是需要将整个程序放到内存中,比如:程序中处理异常和错误条件的代码;数组、链表和表通常分配比实际所
2020-08-04
  目录