页面置换算法概念

本节强烈建议看视频：课程第九讲。其中给出了大量的动画示例，有助于理解。

处理缺页异常（需要调入新页面而内存已满）时，用于选择被置换的物理页面的算法。

设计目标：减少调入调出次数，寻找未来不再访问或短期内不访问的页面调出

在给出页面置换的结构之前，我们有一类特例，即不被替换的页面：
页面锁定（frame locking）

  • 操作系统的关键部分，描述必须常驻的逻辑页面，这部分页面对响应速度有要求
  • 利用页表中的锁定标志位来实现

评价方法：页面轨迹统计，模拟页面置换行为，记录缺页次数

页面置换算法分类：

  • 局部页面置换算法（选择范围仅限当前进程占用的物理页面）

    • 最优算法：全知全能，量身定制
    • 先进先出算法：先调入的页先调出
    • 最近最久未使用算法：一个统计方法，实现较麻烦
    • 时钟算法，最不常用算法

  • 全局置换算法（选择防卫是所有可换出的物理页面）

    • 工作集算法
    • 缺页率算法

局部页面置换算法

最优置换算法（OPT）

置换在未来最长时间不访问的页面。

缺页时计算内存中每个逻辑页面的下一次访问时间。全知全能，缺页次数最少，是理想情况。

  • 实际系统中无法实现
  • 无法预制每个页面在下次访问前的等待时间
  • 但具有理论意义：用于评定置换算法的性能

先进先出算法（FIFO）

由于上述以未来情况为依据的算法不可实现，所以我们要使用如下的基于过去情况的算法。

选择在内存中驻留时间最长的页面进行置换，即FIFO算法。

具体实现过程通过维护一个记录所有位于内存中的逻辑页面队列（双向链表）实现。

  • 实现简单
  • 性能较差，调出的页面可能是经常访问的
  • Belady现象：进程分配物理页面数增加时，缺页并不一定减少，例子可看之后的章节-Belady现象
  • 很少单独使用

最近最久未使用算法（LRU）

Least Recently Used（LRU），选择最长时间没有被引用的页面进行置换。局部性原理表明，如某些页面长时间未被访问，则它们在将来可能会长时间不会访问。

缺页时，计算内存中每个逻辑页面的上一次访问时间，排序找最远。

LRU是最优置换算法的一种近似，但由于算法复杂度过大，仍然在实际情况中无法实施。

实际实现可以使用页面链表或者活动页面栈来构建优先队列，从而降低复杂度：

  • 队头：最久未使用的
  • 队尾：刚刚使用过的

当然维护队列维护队列所带来的复杂度也是不可小视的。

时钟算法（Clock）

前面两种算法各有优劣，FIFO考虑得太过简单，导致性能较差，而LRU的核心问题在于统计得过于仔细，所以难以实施。

所以考虑对页面访问的情况进行大致统计。

  • 在页表项中增加访问位，描述页面在过去一段时间中的访问情况。形成环形链表。
  • 缺页时，从指针处开始顺序查找未被访问（LRU因素）的第一个（FIFO因素）页面进行置换。
  • 有环、有指针，所以形象地称为时钟算法。它是LRU和FIFO的折中。
img

算法描述如下：

  • 页面装入内存时，访问位初始化为0；
  • 访问页面时，被访问页面的访问位置1；
  • 缺页时，从指针处开始顺序扫描，如果访问位为0则置换该页，如果访问位为1则修改为0并移动指针到下一个页面，直到找到可置换页面。

一个示例如下：

img

改进的clock算法

时钟置换算法缺点：

之前的时钟置换算法如果要置换的页是被修改过的，那么就会先要将修改过的页写到外存，然后才将要换入的页读入内存，这样消耗时间过长。

减少修改页的缺页处理开销 (如果要置换的页被修改了 则不置换此页 同时操作系统定期将修改过的页写到外存)

改进算法：

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

按照下面的状态转移表在指针扫过时对使用位和修改位进行修改，后续改动的页面的写出会被合并且延时，而不用在每一次修改并换出时都向外存写出。

img

最不常用算法（LFU）

算法实现：

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

算法特征：

  • 算法开销大
  • 开始时频繁使用 以后不使用的页面难换出 (因为页面在里面待的越久 访问计数越大)
    • 解决方法 较大的计数定期右移

LRU 和 LFU 的区别：

  • LRU 关注多久未使用，时间越短越好 (维护栈)
  • LFU 关注次数，次数越多越好 (稍微简单些)

Belady现象

  • Belady现象：在采用FIFO算法时，有时会出现分配的物理页数增加，缺页率反而提高的异常现象。
  • Belady现象的原因：FIFO算法的置换特征与进程访问内+存的动态特征是矛盾的。与置换算法的目标是不一致的（即替换较少使用的页面）。因此，被它置换出去的页面并不一定是进程不会访问的。为什么FIFO算法会产生Belady现象，而LRU算法不会产生Belady现象：
  • 例子：比如对于1,2,3,4,1,2,5,1,2,3,4,5这个序列，
    • 如果FIFO队列长为3，缺页次数为9，
    • 如果FIFO队列长为4，缺页次数为10

解答：因为LRU算法符合栈算法的特点，而FIFO算法不符合栈算法的特点。栈算法的特点是给与的物理页帧越多，所产生的缺页中断的次数就越少。

思考：Clock algorithm 和 Enhanced Clock algorithm 是否会产生Belady现象？

会

几种算法的对比

LRU、FIFO和Clock的比较：

  • LRU算法和FIFO算法本质上都是先进先出的思路。只不过LRU针对页面最近访问的时间来进行排序。所以需要在每一次页面访问的时候动态地调整各个页面之间的先后顺序（有一个页面最近访问的时间变了）；而FIFO是针对页面进入内存的时间来进行排序，这个时间是固定不变的。所以页面之间的先后顺序是固定的。如果一个页面在进入内存后没有被访问。那么它最近访问的时间就是它进入内存的时间。换句话说，如果内存当中所有的页面都未曾访问过，那么LRU算法就退化为FIFO算法。

  • LRU算法性能比较好，但系统的开销比较大；FIFO算法系统的开销比较小，但有可能会发生Belady现象。

    因此，折中的办法就是Clock算法，在每一次页面访问时，它不必动态的区调整页面在链表中的顺序，而仅仅是做一个标记，然后等到发生缺页中断的时候，再把它移动到链表尾端。对于内存中那些未被访问的页面，Clock算法的表现和LRU一样好；而对于那些曾经被访问过的页面，它不能像LRU算法那样，记住它们准确的位置。6.3 全局页面置换算法

全局置换算法

背景

很多时候，很少量的页面数限制成为算法的瓶颈，比如这个例子：

img img

增加一个物理页面之后，整个置换过程中缺页数量都大大减小。

因而我们思考，可以通过进程之间的物理页面数目的均衡，来改善不同进程的置换算法的表现。

全局置换算法要解决的问题

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

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

CPU_process

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

  • 进程数少时，提高并发进程数可提高CPU利用率
  • 并发进程导致内存访问增加
  • 并发进程的内存访问会降低访存局部性特征 (两个进程所做的事情不相干 局部性原理不适用)
  • 局部性特征下降会导致缺页率上升和CPU利用率下降

工作集

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

  • t 是当前的执行时刻
  • Δ 为工作集窗口(Working-set window) 一个定长的页面访问时间窗口
  • W(t, Δ) 为在当前时刻t前的 Δ 时间窗口中所有访问页面所组成的集合
  • | W(t, Δ) | 为工作集大小 页面数量

工作集的变化

Working_set
  • 进程开始执行后 随着访问新页面逐步建立较稳定的工作集
  • 当内存访问的局部性区域的位置大致稳定时(只访问那几个页面 没有大的改变时) 工作集大小也大致稳定
  • 局部性区域的位置改变时(进程前一项事情做完 去做下一项事情时) 工作集快速扩张和快速收缩过渡到下一个稳定值

常驻集

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

  • 工作集和常驻集的关系
    • 工作集是进程运行过程中固有的性质 (进程在一段时间访问的页面集合)
    • 常驻集 取决于 系统分配给进程的物理页面数 和 页面置换算法 (实际在内存中的页)
  • 缺页率和常驻集的关系
    • 常驻集 包含 工作集时 缺页较少 (进程访问的页都在内存里)
    • 工作集发送剧烈过渡时 缺页较多
    • 进程常驻集大小达到一定数目后 缺页率不会明显下降 (内存够进程功能使用了 再去加内存 反而效率下降)

工作集置换算法

换出不在工作集中的页面 (并不一定是在缺页时才做 因此开销大)

具体实现：窗口大小 τ，则 当前时刻前τ个内存访问的页引用是工作集

  • 访存链表 维护窗口内的访存页面链表
  • 访存时 换出不在工作集的页面 (开销大)
  • 缺页时 换入页面

工作集置换算法和LRU相似，但是是在访存时将不在工作集内的页面换出。在缺页时直接补入。

缺页率置换算法

缺页率 (Page fault rate) = 缺页次数 / 内存访问次数 或 缺页平均时间间隔的倒数 （一般使用后者）

  • 影响缺页率因素
    • 页面置换算法 (只有这个能自己控制)
    • 分配给进程的物理页面数
    • 页面大小
    • 程序的编写方法 (局部性特征)

缺页率算法实现

通过调节常驻集的大小 使每个进程的缺页率保持在一个合理的范围

  • 若进程缺页率过高 则增加常驻集以分配更多物理页面数
  • 若进程缺页率过低，则会降低并发度，使CPU利用率下降。因此要减少常驻集，将一些页面置换到外存
PFF_process
  • 访存时 设置引用位标记
  • 缺页时 计算从上次缺页时间 t_last 到现在 t_current 的时间间隔
    • 如果 t_current - t_last > T 缺页率低，则置换 所有在[t_last, t_current]中没有被引用的页 使其用在更有意义的地方(CPU并发率提高)
    • 如果 t_current - t_last <= T 缺页率高 则增加缺失页到常驻集中

抖动和负载控制

抖动

抖动的产生是因为随着驻留内存的进程数目增加，分配给每个进程的物理页面数不断减小，缺页率不断上升。
抖动问题(Thrashing)：

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

因此操作系统需在 并发水平 和 缺页率之间达到一个平衡，需要选择一个适当的进程数目和进程所需要的物理页面数（即进行负载控制）。

负载控制

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

  • 我们希望平均缺页间隔时间（MTBF）大于等于缺页异常处理时间（PFST）（若小于，则cpu处于满负荷）。因此下图中两条虚线夹着的范围就是平衡点所在范围。
thrashing