[数据结构与算法]【操作系统】Operation System-第6章-页面置换算法

操作系统—页面置换算法

功能与目标

• 功能：当缺页中断发生，需要调入新的页面而内存已满时，选择内存当中哪个物理页面被置换。

• 目标：尽可能地减少页面的换进换出次数（即缺页中断的次数）。 具体来说，把未来不再使用的或短期内较少使用的页面换出，通常只能在局部性原理指导下依据过去的统计数据来进行预测。

• 页面锁定（frame locking）：用于描述必须常驻内存的操作系统的关键部分或时间关键（time-critical）的应用进程。

  实现的方法是：在页表中添加锁定标记位（lock bit）。

实验设置与评价方法

局部页面置换算法

最优页面置换算法（OPT）

最优页面置换算法（OPT，optimal）

• 基本思路：当一个缺页中断发生时，对于保存在内存当中的每一个逻辑页面，计算在它的下一次访问之前，还需等待多长时间，从中选择等待时间最长的那个，作为被置换的页面。

• 这是一种理想情况，在实际系统中是无法实现的，因为操作系统无法知道每一个页面要等待多长时间以后才会再次被访问。

• 可用作其他算法的性能评价的依据。（在一个模拟器上运行某个程序，并记录每一次的页面访问情况，在第二遍运行时即可使用最优算法）

先进先出算法（FIFO）

先进先出算法（FIFO，First-In First-Out）

• 基本思路：选择在内存中驻留时间最长的页面淘汰。 具体来说，系统维护着一个链表，记录了所有位于内存当中的逻辑页面。 从链表的排列顺序来看，链首页面的驻留时间最长，链尾页面的驻留时间最短。 当发生一个缺页中断时，把链首页面淘汰出去，并把新的页面添加到链表的末尾。

• 性能较差，调出的页面有可能是经常要访问的页面。 并且有Belady现象。 FIFO算法很少单独使用。

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

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

• 基本思路：当一个缺页中断发生时，选择最久未使用的那个页面，并淘汰。

• 它是对最优页面置换算法的一个近似，其依据是程序的局部性原理，即在最近一小段时间）最近几条指令）内，如果某些页面被频繁地访问，那么再将来的一小段时间内，他们还可能会再一次被频繁地访问。 反过来说，如果过去某些页面长时间未被访问，那么在将来它们还可能会长时间地得不到访问。

LRU算法需要记录各个页面使用时间的先后顺序，开销比较大。

两种可能的实现方法是 :

• 系统维护一个页面链表，最近刚刚使用过的页面作为首结点，最久未使用的作为尾结点。 每一次访问内存时，找出相应的页面，把它从链表中摘下来，再移动到链表之首。 每次缺页中断发生时，淘汰链表末尾的页面。

• 设置一个活动页面栈，当访问某页时，将此页号压入栈顶，然后，考察栈内是否有与此页面相同的页号，若有则抽出。 当需要淘汰一个页面时，总是选择栈底的页面，它就是最久未使用的。

  

时钟页面置换算法（Clock）

Clock页面置换算法，LRU的近似，对FIFO的一种改进；

基本思路

• 需要用到页表项的访问位(access bit)，当一个页面被装入内存时，把该位初始化为 $0$。 然后如果这个页面被访问，则把该位置设为 $1$;

• 把各个页面组织成环形链表（类似钟表面），把指针指向最老的页面（最先进来）;

• 当发生一个缺页中断时，考察指针所指向的最老页面，

  ? 若它的访问位为 $0$，立即淘汰；

  ? 若访问位为 $1$，则访问位置为 $0$，然后指针往下移动一格。

  ? 如此下去，直到找到被淘汰的页面，然后把指针移动到下一格。

示例

• 维持一个环形页面链表保存在内存中

  ? 用一个时钟（或者使用 / 引用）位来标记一个页面是否经常被访问

  ? 当一个页面被引用的时候，这个位被设置（为1）

• 时钟头扫遍页面寻找一个带有 $usedbit=0(assessbit)$

  ? 替换在一个周转内没有被引用过的页面

流程

• 如果访问页在物理内存中，访问位置为1。

• 如果不在物理页，从指针当前指向的物理页开始，如果访问位为0，替换当前页，指针指向下一个物理页；如果访问位为1，置0以后访问下一个物理页再进行判断。 如果所有物理页的访问位都被清零了，又回到了第一次指针所指向的物理页进行替换。

二次机会算法（Enhanced Clock）

改进的Clock算法（Enhanced Clock）

• 这里有一个巨大的代价来替换“脏”页

• 修改Clock算法，使它允许脏页总是在一次时钟头扫描中保留下来

  ? 同时使用脏位和使用位来指导置换

因为考虑到时钟页面置换算法，有时候会把一些 $dirtybit$ 为 $1$（有过写操作）的页面进行置换，这样的话，代价会比较大。

因此，可以结合使用位和脏位一起来决定应该置换哪一页。

相当于说，替换的优先级，没有读写也没写过，那么直接走；如果写过或者访问过，那么给你一次机会；如果又写过，又访问过，那么就给你两次机会。

最不常用算法（LFU）

最不常用算法（LFU，Least Frequently used）

• 基本思路：当一个缺页中断发生时，选择访问次数最少的那个页面，并淘汰。

• 实现方法：对每一个页面设置一个访问计数器，每当一个页面被访问时，该页面的访问计数器加1。 当发生缺页中断时，淘汰计数值最小的那个页面。

• LRU和LFU的对比：LRU考察的是多久未访问，时间越短越好；而LFU考察的是访问的次数或频度，访问次数越多越好。

问题：

一个页面在进程开始时使用得很多，但以后就不使用了，LFU统计的是整体的访问次数，所以此时这个页面还会被保留在内存中。

实现也费时费力，需要对每一个页面加一个计数器。

解决方法：

定期把次数寄存器右移一位（二进制 >> 1 相当于 / 2）。

它最主要的问题是只考虑频率而没考虑时间，我们可以隔一段时间砍掉一半的次数，进而改善这个问题。

Belady现象

• 在采用FIFO算法时，有时会出现分配的物理页面数增加，缺页率反而提高的异常现象；

• 原因：FIFO算法的置换特征与进程访问内存的动态特征是矛盾的，与置换算法的目标是不一致的）即替换较少使用的页面），因此，被他置换出去的页面不一定是进程不会访问的。

FIFO算法有Belady现象

gif示例，物理页面数为 $3$：

此时缺页数为 $9$。

假设我们把物理页面数增加，那么缺页中断数应该少了吧？

gif示例，物理页面数+1为 $4$：

我们的缺页中断数变成了 $10$，并没有减少，反而增加了！

这并不是我们预期的，我们给了更多的物理资源，可产生的缺失次数变得更多了，这就是Belady现象。

LRU算法没有Belady现象

LRU算法是符合我们预期的。

• 时钟 / 改进的时钟页面置换是否有Belady现象？

  ? 没有。

• 为什么LRU页面置换算法没有Belady现象？

  ? 简单解释：LRU符合一类叫称之为 栈算法 的特点。

LRU、FIFO和Clock的比较

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

  ? LRU依据页面的最近访问时间排序。

  ? LRU需要在每一次页面访问的时候动态地调整各个页面之间的先后顺序（有一个页面的最近访问时间变了）。

  ? FIFO依据页面进入内存的时间排序。

  ? FIFO的页面进入时间是固定不变的，各个页面之间的先后顺序是固定的。

• LRU可退化成FIFO

  ? 如果一个页面进入内存后没有被访问，那么它的最近访问时间就是它进入内存的时间。

  ? √ 换句话说，如果内存当中的所有页面都未曾访问过，那么LRU算法就退化为了FIFO算法。

  ? 例如：给进程分配3个物理页面，逻辑页面的访问顺序为 1、2、3、4、5、6、1、2、3…

• LRU算法性能较好， 但系统开销较大。

• FIFO算法系统开销较小，但会发生Belady现象。

• Clock算法是它们的折衷

  ? 页面访问时，不动态调整页面在链表中的顺序，仅做标记。

  ? 缺页时，再把它移动到链表末尾。

• 对于未被访问的页面，Clock和LRU算法的表现一样好。

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

Clock模仿LRU，LRU在某种状态下会退化为FIFO，也意味着Clock也可能会退化为FIFO，从这点可以看出来算法只是我们页替换的一个环节，如果要有效减少缺页产生的次数，除了算法本身之外，我们还要对访问序列有一定的要求，访问序列最好是具有局部性的访问特征，那么LRU、Clock算法才会发挥特征，如果序列不具有局部性，那么LRU、Clock、FIFO就没什么区别了。

全局页面置换算法

局部页替换算法的问题

局部置换算法没有考虑进程访存差异。

由上图可以看到 物理页帧的大小确实会对页面置换算法的效果产生很大影响，我们如果对一个程序分配固定的物理页帧制定算法，其实在某种程度上限制了程序产生缺页的特点；

因为程序在运行过程中可能会有阶段性，它可能一开始访问需要很多内存，中间时候需要很少，结束的时候又需要很多，它是动态变化的过程，它对物理页帧的需求是可变的。

在前面介绍的算法里面，都假定物理页帧是固定的，如果一个系统只跑这一个程序，那我可以把所有物理页帧都分给它；但是我们的操作系统可以跑多个程序，这时再给每个程序分配固定的页帧，其实就限制了灵活性，我们能不能根据程序的不同阶段给它动态分配，调整它物理页帧的大小，这实际上就是全局页面置换算法所考虑的问题。

思路

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

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

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

工作集模型

前面介绍的各种页面置换算法，都是基于一个前提，即程序的局部性原理。 但是此原理是否成立？

• 如果局部性原理不成立，那么各种页面置换算法就没有说明分别，也没有什么意义。 例如：假设进程对逻辑页面的访问顺序是1,2,3,4,5,6,6,7,8,9…，即单调递增，那么在物理页面数有限的前提下，不管采用何种置换算法，每次的页面访问都必然导致缺页中断。
• 如果局部性原理是成立的，那么如何来证明它的存在，如何来对它进行定量地分析？ 这就是工作集模型！

工作集

示例

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

常驻集

常驻集是指在当前时刻，进程实际驻留在内存当中的页面集合。

• 工作集与常驻集的关系

  ? 工作集是进程在运行过程中固有的性质

  ? 常驻集取决于系统分配给进程的物理页面数目和页面置换算法

• 缺页率与常驻集的关系

  ? 常驻集 $?$ 工作集时（一个进程的整个工作集都在内存当中），缺页较少

  ? 工作集发生剧烈变动（过渡）时，缺页较多

  ? 进程常驻集大小达到一定数目后，再给它分配更多的物理页面，缺页率也不会明显下降

工作集页置换算法

思路

• 换出不在工作集中的页面

窗口大小 $\tau$

• 当前时刻前 $\tau$ 个内存访问的页引用是工作集， $\tau$ 被称为窗口大小

实现方法

• 访存链表：维护窗口内的访存页面链表

• 访存时，换出不在工作集的页面；更新访存链表

• 缺页时，换入页面；更新访存链表

当工作集窗口在滑动过程中，如果页面不在集合中，那么就会直接丢失这个不在窗口中页面，而不会等待缺页中断再丢弃。

特点

• 它在当前物理内存中放哪些页，取决于是否在工作集窗口之内，这样可以确保在物理内存中始终有足够多的页存在，这样可以给其它运行程序提供更多的内存，进一步减少页面置换的次数，在整个系统层面，多个程序的缺失数会降低。

缺页率置换算法

可变分配策略：常驻集大小可变。 例如：每个进程在刚开始运行的时候，先根据程序大小给它分配一定数目的物理页面，然后在进程运行过程中，再动态地调整常驻集的大小。

• 可采用全局页面置换的方式，当发生一个缺页中断时，被置换的页面可以是在其他进程当中，各个并发进程竞争地使用物理页面。
• 优缺点：性能较好，但增加了系统开销。
• 具体实现：可以使用==缺页率算法（PFF，page fault frequency）==来动态调整常驻集的大小。

缺页率（page fault rate）

表示 “缺页次数 / 内存访问次数”（比率）或 “缺页平均时间间隔的倒数”。

影响缺页率的因素

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

算法实现

保持追踪缺失发生概率。

• 访存时，设置引用位标志

• 缺页时，计算从上次缺页时间 $t_{last}$ 到现在 $t_{current}$ 的时间间隔

  ? 如果发生页缺失之间的时间是“大”的，之后减少工作集。

  ? 如果 $t_{current}-t_{last}> T $，则置换所有在 $[t_{current},t_{last}]$ 时间内没有被引用的页。

  ? 如果这个发生页缺失的时间是“小”的，之后增加工作集。

  ? 如果 $t_{current}-t_{last}\leqslant T $，则增加缺失页到工作集中。

示例

抖动问题（thrashing）

工作集、常驻集概念的拓展

• 抖动

  ? 如果分配给一个进程的物理页面太少，不能包含整个的工作集，即常驻集 $?$ 工作集；

  ? 那么进程将会造成很多的缺页中断，需要频繁的在内存与外存之间替换页面；

  ? 从而使进程的运行速度变得很慢，我们把这种状态称为 ”抖动“。

• 产生抖动的原因

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

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

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

负载控制

整理自 【清华大学】 操作系统