本文将介绍页面置换算法中的 全局 页面置换算法。首先，介绍了局部页面置换算法的局限性；然后，介绍了工作集模型和工作集、常驻集；最后，介绍了两个全局页面置换算法——工作集页面置换算法和缺页率页面置换算法。

局部置换算法的问题

物理页帧分配角度

假设一：
给一个程序分配了一个大小固定为 3 的物理页帧（如 a, b, c），而现在程序 A 需要访问 a, b, c, d, a, b, c, d, ... 的物理页帧。那么，在使用 FIFO 页面置换算法的情况下，从时刻 4（第一次访问 d）开始，每一次访问都会产生一个缺页中断。

假设二：
给一个程序分配了一个大小固定为 4 的物理页帧（如 a, b, c, b），而现在程序 B 需要访问 a, b, c, d, a, b, c, d, ... 的物理页帧。那么，在使用 FIFO 页面置换算法的情况下，不会产生缺页中断。

由此可以看出：物理页帧的大小确实会对同一个页面置换算法的效果产生很大影响。这说明，如果对一个程序分配固定的物理页帧、使用指定页面置换算法，其实在某种程度上限制了程序产生缺页的灵活性。

程序内存访问角度

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

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

全局 Vs. 局部

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

进程在不同阶段的内存需求是变化的，这就需要解决以下问题：

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

工作集与常驻集

工作集模型

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

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

工作集

什么是工作集

工作集：一个进程当前（过去一段时间内）正在使用的逻辑页面集合，可表示为二元函数 $W(t, \Delta)$。

• $t$ 是当前的执行时刻；
• $\Delta$ 称为工作集窗口（working-set window），即一个定长的页面访问时间窗口；
• $W(t, \Delta)$ 是指 在当前时刻 $t$ 前的 $\Delta$ 时间窗口中的所有访问页面所组成的集合；
• $|W(t, \Delta)|$ 指工作集的大小，即页面数目。

工作集示例

假设一个进程有如下的页面访问顺序，工作集窗为 $\Delta = 10$：

1
2
3

2 6 1 5 7 7 7 7 5 1 6 3 4 4 4 3 4 3 4 4 4 1 3 2 7
                   |                     |
<---- Delta ----> t1  <---- Delta ----> t2

• 在 $t_{1}$ 时刻的工作集为：$W(t_{1}, \Delta) = \{1,2,5,6,7\}$。
• 在 $t_{2}$ 时刻的工作集为：$W(t_{2}, \Delta) = \{3,4\}$。

工作集访问与程序访问的关联

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

常驻集

常驻集：在当前时刻（那一瞬间），进程实际驻留在内存当中的页面集合。

工作集与常驻集的关系：

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

缺页率与工作集、常驻集的关系：

• 常驻集 $\supseteq$ 工作集时，即一个进程的整个工作集都在内存当中时，缺页较少；
• 工作集发生剧烈变动（过渡）时，缺页较多；
• 进程常驻集大小达到一定数目后，再给它分配更多的物理页面，缺页率也不会明显下降。

全局页面置换算法

工作集页面置换算法（Working-set）

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

思路：在每次的内存访问时，换出不在工作集窗口范围内的页面。

实现方式：维护工作集窗口内的访存页面链表（访存链表）。

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

工作集页面置换算法示例：

上图中，在时刻 0，程序已经访问了内存中的 e, d, a 三个物理页面，假设 $\Delta = 4$，此时的工作集为 {e, d, a}：

• 在时刻 1，访存 c 不在工作集中，产生缺页中断，换入页面 c，工作集更新为 {e, d, a, c}；
• 在时刻 2，访存 c 在工作集中，工作集更新为 {d, a, c}；
• 在时刻 3，访存 d 在工作集中，工作集更新为 {a, c, d}；
• 在时刻 4，访存 b 不在工作集中，产生缺页中断，换入页面 b，工作集更新为 {c, d, b}；
• …

可以看出：

• 工作集窗口在滑动过程中，如果页面不再在工作集的窗口范围内，则会直接淘汰这个窗口，而不会等待缺页中断产生才淘汰。
• 在缺页时，会换入页面，但是更新后的工作集的页面，除了新增的换入页面外，工作集中的页面不一定会改变（因为可能换出了页面 X，但窗口内还有页面 X）。

工作集页面置换算法的特点：

工作集页面置换算法 在当前物理内存中放哪些页，取决于是否在工作集窗口之内 。这样可以确保在物理内存中始终有足够多的页存在，以便为其他运行程序提供更多的内存空间，进一步减少页面置换的次数。通过减少页面置换次数，可以降低多个程序的缺页数， 提高系统的整体性能。

缺页率页面置换算法（PFF）

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

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

缺页率（page fault rate）：表示「缺页次数 / 内存访问次数」或 「缺页平均时间间隔的倒数」。

缺页率置换算法通过动态调整常驻集大小，使每个进程的缺页率保持在一个合理的范围内。

• 若进程缺页率过高，则增加常驻集以分配更多的物理页面；
• 若进程缺页率过低，则减少常驻集以减少它的物理页面数。

影响缺页率的因素：

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

算法实现：保持追踪缺失发生概率，设预定的缺页时间阈值为 $T$。

• 访存时，设置引用位（access bit）标志；
• 缺页时，计算从上次缺页时间 $t_{last}$ 到现在 $t_{current}$ 的时间间隔：
  • 如果发生页缺失之间的时间是「大」的，之后减少常驻集：$t_{current}-t_{last}> T$，则置换出所有在 $[t_{last}, t_{current}]$ 时间内没有被引用的页，并增加缺失页到常驻集中。换句话说，就是只保留在 $[t_{last}, t_{current}]$ 时间内被引用的页面。
  • 如果这个发生页缺失的时间是「小」的，之后增加常驻集：$t_{current}-t_{last}\leqslant T$，则增加缺失页到常驻集中。

在上图中，时刻 0 的常驻集为 {a, d, e}：

• 在时刻 1 时，页面 c 不在常驻集中，且为首次发生缺页，则增加缺失页到常驻集中，当前的常驻集为 {a, c, d, e}；
• 在时刻 2, 3 时，页面 c, d 都在常驻集中，没有发生缺页，当前的常驻集为 {a, c, d, e}；
• 在时刻 4 时，页面 b 不在常驻集中，发生缺页，且 $t_{current}-t_{last} = 4 - 1 > T$，则增加缺失页到常驻集中、只保留在 $[1, 4]$ 之间被引用的页面，当前的常驻集 {c, d, b}；
• …

我个人觉得图片中的「工作集」应该是「常驻集」，所以文字描述中，也叙述成了「常驻集」。

内存抖动问题（thrashing）

什么是内存抖动？

如果分配给一个进程的物理页面太少，不能包含整个的工作集，即常驻集 $\subset$ 工作集。那么，进程将会造成很多的缺页中断，需要频繁的在内存与外存之间替换页面，从而使进程的运行速度变得很慢，我们把这种状态称为「抖动」。

产生抖动的原因？

进程过多：随着驻留内存的进程数目增加，分配给每个进程的物理页面数不断就减小，缺页率不断上升，从而产生抖动。

内存抖动为什么会导致系统性能下降？

内存抖动导致系统性能下降的原因是因为频繁的页面置换会引起磁盘 I/O 的开销，这是一个相对较慢的操作。此外，频繁的页面置换还会导致 CPU 时间被浪费在页面置换和上下文切换上，从而降低了系统的吞吐量。

如何改善内存抖动？

操作系统需要在并发水平和缺页率之间达到一个平衡，这需要调整进程的内存分配策略：选择一个恰当的并发进程数量，并为每个进程分配恰当的物理页面数（可以使用动态页面分配算法，根据进程的实时需求动态调整页面的分配情况）。

参考资料：

1. https://github.com/OXygenMoon/OperatingSystemInDepth
2. https://blog.csdn.net/weixin_53407527/article/details/125008097