抖动与工作集

概念

抖动（thrashing，也叫"颠簸"）指刚换出的页马上又要换入、刚换入的页马上又要换出，系统把绝大部分时间花在"页面在内存与磁盘之间来回搬"上，实际有效工作几乎停滞。

一句话说清它是什么：抖动就是"内存不够分，每个进程都在疯狂缺页"——它是 os/23-virtual.md 里那条"缺页率必须压到 ${10}^{-5}$"的账彻底还不上时的后果。

⚠️ 抖动的直观特征（三条，缺一不可）：

特征	说明
缺页率极高	往往在 50% 以上，甚至接近"每访问一次就缺一次"
CPU 利用率急剧下降	CPU 大部分时间在等待磁盘 I/O，看起来"很闲"
磁盘 I/O 极其繁忙	页面换入换出把磁盘带宽占满

⚠️ 抖动最反直觉的一点：它会被"提高多道程序度"这个动作加重，而不是缓解——见下节的倒挂曲线。 "CPU 利用率低 → 再塞一道程序进来"这个直觉动作，恰好是抖动最常见的触发机制。

原理

一、抖动的成因：缺页率与多道程序度的倒挂

  CPU 利用率
    100%│              ╭──────╮
        │            ╭─╯      ╰─╮
        │          ╭─╯            ╰╮
        │        ╭─╯                ╰──╮
        │      ╭─╯                     ╰───╮
        │    ╭─╯                            ╰────────
        │  ╭─╯        ★ 抖动的起点
        └──┴──────────────────────────────────────▶ 多道程序度
           ①            ②  ③(峰值)                  ④

  ① 太少: CPU 空闲 (并发度不足)
  ② 刚好: CPU 利用率接近峰值
  ③ 超过某个临界点: 缺页率开始上升
  ④ ★ 完全抖动: 多塞进一道程序 -> CPU 利用率反而暴跌

机制链条：

   多塞一道程序
        ↓
   每个进程分到的页框变少
        ↓
   进程的"工作集"装不下 (实际需要的页 > 分到的页框)
        ↓
   本地性被破坏 -> 缺页率飙升
        ↓
   系统忙于换页, 分给各进程的 CPU 时间更少, 缺页处理更慢
        ↓
   ★ 所有进程的缺页率进一步升高 -> 正反馈 -> 抖动

⚠️ 关键概念：触发抖动的根本条件不是"内存不够"，而是"分配给每个进程的页框数 < 它的工作集大小"。 内存再大，若平均分给几百个进程，照样抖动。

二、工作集模型（本章核心）

工作集（working set）= 某进程在"最近 $\tau$ 个访问"（或最近 $\tau$ 时间内）实际引用过的页的集合。

   引用串:  7  0  1  2  0  3  0  4  2  3  0  3  2  1  2  0  1  7  0  1
   时间:    0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19

   设窗口 tau = 4, 看 t = 8:
       窗口覆盖 t = 5,6,7,8  ->  引用 3, 0, 4, 2  ->  工作集 = {0,2,3,4}, 大小 4

术语	定义	与"抖动"的关系
工作集 WS	窗口内实际访问过的页集合	"进程真正需要多少页"
工作集大小 $W(t,\tau )$	这个集合的势（多少页）	决定了要分多少页框
驻留集	操作系统实际分配给该进程的物理页框集合	"实际给了多少页"
抖动判据	驻留集 < 工作集	★ 这就是判据本身

⚠️ 驻留集 ≠ 工作集（最高频的混淆点）：

• 工作集是"需求"（进程要用多少）——由程序行为决定，OS 只能观测、不能更改。
• 驻留集是"供给"（OS 给了多少）——由 OS 的分配策略决定。
• 供 ≥ 求 → 平稳；供 < 求 → 缺页率飙升 → 抖动。

三、工作集窗口 $\tau$ 的选择（一个权衡）

窗口 $\tau$	工作集大小	后果
$\tau$ 太小	偏小（甚至只含当前页）	容不下真实的局部性 → 缺页率被高估 → 页框分配不足 → 抖动
$\tau$ 太大	偏大（跨越多个局部性阶段）	把已过时的页也算进去 → 需求被高估 → 页框浪费
$\tau$ 合适	恰好覆盖一个"局部性阶段"	既不抖动也不浪费

⚠️ "局部性阶段"这个概念很关键：进程的行为往往分成若干个阶段（如先跑初始化、再跑主循环、最后清理），每个阶段访问一个固定的页集合。$\tau$ 应当大致等于"一个阶段的长度"——这是"窗口大小靠经验调，且只能用定长时间片近似"的原因（真实系统无法预知阶段长度）。

四、驻留集管理：页错误频率 PFF 法

页错误频率（PFF，page fault frequency）直接盯住"缺页率"这个结果指标，反过来调页框数：

   设上界 U (如 60%)、下界 L (如 20%)

   缺页率 > U  ──▶ 再给这个进程加页框 (它缺页太频繁, 需求没被满足)
   缺页率 < L  ──▶ 从这个进程收回页框 (它内存富余)
   L ≤ 缺页率 ≤ U ──▶ 保持不动

   ★ 若"加不出页框" -> 说明系统总内存不足 -> 应当 ★ 挂起(换出)某个进程

⚠️ PFF 与工作集法的分工：

• 工作集法：先算出"要用多少"（观测窗口），再据此分配——属于"预测供给"。
• PFF 法：先分配，再看"缺不缺"，用缺页率反馈调整——属于"结果反馈"。
• 两者是"前馈 vs 反馈"的关系，教材常作为并列方法出现。

五、抖动的处理手段

手段	做法	副作用
降低多道程序度	挂起（换出）若干进程，把内存让给还在跑的	牺牲了并发度，但这是最直接有效的手段
工作集法分配页框	按各进程的实际工作集大小分配，不足则不加新进程	要持续观测窗口，有开销
PFF 调节	按缺页率反馈加/减页框	阈值要调；可能震荡
为进程预留"局部性空间"	一次性给够，宁可少几道程序	并发度降低
改进置换算法	用 LRU / 改进型 CLOCK 替代 FIFO	算法开销变大

⚠️ 一句话总结：抖动的根治办法是"少塞几道程序"或"给每道多分点页框"——两者本质相同：让"驻留集 ≥ 工作集"重新成立。

示例

例 1：工作集逐时刻轨迹

引用串：7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1（20 次），窗口 $\tau =4$。 求每一时刻的工作集与大小。

$t$	引用	窗口覆盖（$t-3\sim t$）	工作集	大小
0	7	7		1
1	0	7 0		2
2	1	7 0 1		3
3	2	7 0 1 2		4
4	0	0 1 2 0		3
5	3	1 2 0 3		4
6	0	2 0 3 0		3
7	4	0 3 0 4		3
8	2	3 0 4 2		4
9	3	0 4 2 3		4
10	0	4 2 3 0		4
11	3	2 3 0 3		3
12	2	3 0 3 2		3
13	1	0 3 2 1		4
14	2	3 2 1 2		3
15	0	2 1 2 0		3
16	1	1 2 0 1		3
17	7	2 0 1 7		4
18	0	0 1 7 0		3
19	1	1 7 0 1		3

工作集最大 = 4，平均 = 3.2000。

★ 结论：该进程只要分到 4 个页框就足够了——若系统只给它 3 个，那三个"工作集大小为 4"的时刻（$t=3,5,8,9,10,13,17$）就会缺页——这就是"驻留集 < 工作集 → 抖动"的具体样子。

例 2：C 实现——工作集大小计算

#include <stdio.h>

#define NR  20      /* 引用串长度 */
#define TAU 4       /* 工作集窗口 */

static int ref[NR] = {7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1};

/* t 时刻的工作集大小 = 窗口 [t-TAU+1, t] 内出现过的不同页数 */
static int ws_size(int t) {
    int seen[16], lo, k, cnt = 0;
    for (k = 0; k < 16; k++) seen[k] = 0;
    lo = t - TAU + 1;
    if (lo < 0) lo = 0;
    for (k = lo; k <= t; k++) {
        if (!seen[ref[k]]) { seen[ref[k]] = 1; cnt++; }
    }
    return cnt;
}

int main(void) {
    int i, s, mx = 0, sum = 0;

    printf("引用串:");
    for (i = 0; i < NR; i++) printf(" %d", ref[i]);
    printf("\n工作集窗口 tau = %d\n\n", TAU);

    for (i = 0; i < NR; i++) {
        s = ws_size(i);
        sum += s;
        if (s > mx) mx = s;
        printf("  t=%2d 引用 %d -> 工作集大小 %d\n", i, ref[i], s);
    }

    printf("\n工作集最大 = %d, 平均 = %.4f\n", mx, sum / (double)NR);
    printf("结论: 该进程至少需要 %d 个页框, 否则就会抖动\n", mx);
    return 0;
}

c 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行

预期输出：

引用串: 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
工作集窗口 tau = 4

  t= 0 引用 7 -> 工作集大小 1
  t= 1 引用 0 -> 工作集大小 2
  t= 2 引用 1 -> 工作集大小 3
  t= 3 引用 2 -> 工作集大小 4
  t= 4 引用 0 -> 工作集大小 3
  t= 5 引用 3 -> 工作集大小 4
  t= 6 引用 0 -> 工作集大小 3
  t= 7 引用 4 -> 工作集大小 3
  t= 8 引用 2 -> 工作集大小 4
  t= 9 引用 3 -> 工作集大小 4
  t=10 引用 0 -> 工作集大小 4
  t=11 引用 3 -> 工作集大小 3
  t=12 引用 2 -> 工作集大小 3
  t=13 引用 1 -> 工作集大小 4
  t=14 引用 2 -> 工作集大小 3
  t=15 引用 0 -> 工作集大小 3
  t=16 引用 1 -> 工作集大小 3
  t=17 引用 7 -> 工作集大小 4
  t=18 引用 0 -> 工作集大小 3
  t=19 引用 1 -> 工作集大小 3

工作集最大 = 4, 平均 = 3.2000
结论: 该进程至少需要 4 个页框, 否则就会抖动

⚠️ 三点说明：

1. lo = t - TAU + 1; if (lo < 0) lo = 0;——这是"窗口向前不足 $\tau$ 时只用已有部分"的处理（$t=0$ 时窗口只有 1 个元素）。漏掉这个 if 就会读到数组负下标。
2. seen[] 用"标记数组"实现"集合去重"——比排序再数更简单，也是 $\tau$ 很小时最直观的写法（复杂度 $O(\tau )$）。
3. 本机无 C 编译器：此段代码逐行人工审查，并用等价的 Python 实现（下例同一条引用串）实跑核对过输出——最大 4、平均 3.2000，与例 1 的手算表逐行一致。

例 3：Python——窗口选择、驻留集与缺页率、PFF 判定

REF = [7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1]


def ws_sizes(ref, tau):
    """每个时刻的工作集大小"""
    return [len(set(ref[max(0, t - tau + 1):t + 1])) for t in range(len(ref))]


def lru_faults(ref, n):
    q, faults = [], 0
    for r in ref:
        if r in q:
            q.remove(r)
            q.append(r)
        else:
            faults += 1
            if len(q) < n:
                q.append(r)
            else:
                q.pop(0)
                q.append(r)
    return faults


print('=== ① 工作集窗口 tau 的选择 ===')
print('引用串 = %s' % REF)
for tau in [1, 2, 3, 4, 5, 6, 8]:
    s = ws_sizes(REF, tau)
    print('  tau=%d -> 工作集最大 %d, 平均 %.4f, 据此应驻留 %d 帧'
          % (tau, max(s), sum(s) / len(s), max(s)))
print('  tau 太小 -> 高估需求(把局部性切碎);  tau 太大 -> 把过时页也算进去(浪费)')
print()

print('=== ② 驻留集大小 vs 缺页率 (LRU, 同一引用串) ===')
print('帧数   缺页次数   缺页率     相对工作集上限(4)')
for n in range(1, 7):
    f = lru_faults(REF, n)
    rate = f / len(REF)
    bar = '#' * int(rate * 30)
    print('  %d  %7d   %6.2f%%   %s' % (n, f, rate * 100, bar))
print('  ★ 工作集最大 = 4 -> 给 4 帧缺页率降到 40%; 给 1~3 帧仍在 60~100% (抖动区)')
print()

print('=== ③ PFF 页错误频率调节法 ===')
UP, DOWN = 0.60, 0.20
print('  阈值: 上界 U=%.2f, 下界 L=%.2f' % (UP, DOWN))
for n in [2, 3, 4, 5, 6]:
    rate = lru_faults(REF, n) / len(REF)
    if rate > UP:
        act = '加页框 (缺页太频繁, 需求未满足)'
    elif rate < DOWN:
        act = '收页框 (内存富余)'
    else:
        act = '保持不变'
    print('  驻留 %d 帧, 缺页率 %.2f -> %s' % (n, rate, act))
print('  若"加不出页框" -> 总内存不足 -> 应挂起某个进程 (降低多道程序度)')
print()

print('=== ④ 抖动的判定 ===')
for resident, ws in [(4, 4), (3, 4), (2, 4), (6, 4)]:
    if resident >= ws:
        verdict = '平稳 (驻留集 >= 工作集)'
    else:
        verdict = '★ 抖动 (驻留集 < 工作集)'
    print('  驻留集 %d, 工作集 %d -> %s' % (resident, ws, verdict))

python 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行

输出对照（真实运行结果）：

=== ① 工作集窗口 tau 的选择 ===
引用串 = [7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1]
  tau=1 -> 工作集最大 1, 平均 1.0000, 据此应驻留 1 帧
  tau=2 -> 工作集最大 2, 平均 1.9500, 据此应驻留 2 帧
  tau=3 -> 工作集最大 3, 平均 2.7000, 据此应驻留 3 帧
  tau=4 -> 工作集最大 4, 平均 3.2000, 据此应驻留 4 帧
  tau=5 -> 工作集最大 4, 平均 3.5500, 据此应驻留 4 帧
  tau=6 -> 工作集最大 5, 平均 3.8000, 据此应驻留 5 帧
  tau=8 -> 工作集最大 6, 平均 4.2000, 据此应驻留 6 帧
  tau 太小 -> 高估需求(把局部性切碎);  tau 太大 -> 把过时页也算进去(浪费)

=== ② 驻留集大小 vs 缺页率 (LRU, 同一引用串) ===
帧数   缺页次数   缺页率     相对工作集上限(4)
  1       20   100.00%   ##############################
  2       17    85.00%   #########################
  3       12    60.00%   ##################
  4        8    40.00%   ############
  5        7    35.00%   ##########
  6        6    30.00%   #########
  ★ 工作集最大 = 4 -> 给 4 帧缺页率降到 40%; 给 1~3 帧仍在 60~100% (抖动区)

=== ③ PFF 页错误频率调节法 ===
  阈值: 上界 U=0.60, 下界 L=0.20
  驻留 2 帧, 缺页率 0.85 -> 加页框 (缺页太频繁, 需求未满足)
  驻留 3 帧, 缺页率 0.60 -> 保持不变
  驻留 4 帧, 缺页率 0.40 -> 保持不变
  驻留 5 帧, 缺页率 0.35 -> 保持不变
  驻留 6 帧, 缺页率 0.30 -> 保持不变
  若"加不出页框" -> 总内存不足 -> 应挂起某个进程 (降低多道程序度)

=== ④ 抖动的判定 ===
  驻留集 4, 工作集 4 -> 平稳 (驻留集 >= 工作集)
  驻留集 3, 工作集 4 -> ★ 抖动 (驻留集 < 工作集)
  驻留集 2, 工作集 4 -> ★ 抖动 (驻留集 < 工作集)
  驻留集 6, 工作集 4 -> 平稳 (驻留集 >= 工作集)

四条结论：

1. $\tau$ 从 1 增到 8，工作集上限从 1 涨到 6，平均从 1.00 涨到 4.20——窗口越大、需求估得越高。取 $\tau =4$ 时"最大 4、平均 3.2"，恰好是本题的合理档位；$\tau =1$ 会严重低估（以为只要 1 帧），$\tau =8$ 会高估（要 6 帧，其中有 2 帧其实已过时）。
2. 缺页率随驻留集增加而单调下降（100% → 85% → 60% → 40% → 35% → 30%），但在 $3\to 4$ 这一档出现了"台阶式"下降（60% → 40%）——台阶的位置正好对应"工作集最大 = 4"。这就是"给够工作集大小，缺页率才会明显回落"的直接证据。
3. PFF 法用"缺页率"这个可观测量反推页框数：本题只有 2 帧时缺页率 85% 超过上界 60%，触发"加页框"；3 帧正好压在上界（0.60 不 > 0.60，判"保持"）——注意"大于"与"大于等于"的口径，考试题里要按题目原文执行。
4. 抖动判据只有一条：驻留集 < 工作集（4/4 平稳、3/4 与 2/4 抖动、6/4 仍是平稳但浪费 2 帧）——"给多了不抖动只是浪费，给少了必然抖动"，这是本章唯一的定量判据。

考点

考点

1. 必背结论

• 抖动 = 页面频繁换入换出、缺页率极高、CPU 利用率反而暴跌。
• 抖动曲线：多道程序度先升后降——CPU 利用率在某个临界点达峰，再往里加进程就进入抖动区。
• 抖动的根本条件：分配给进程的页框数 < 它的工作集大小（不是"内存绝对不够"，而是"分给每个进程的不够"）。
• 工作集 = 某段时间窗口内实际访问过的页集合；窗口 $\tau$ 是"时间窗口长度"。
• 驻留集 = OS 实际分配的页框集合（"供"）；工作集 = 进程实际需要的页集合（"求"）。供 < 求 → 抖动。
• $\tau$ 太小 → 低估需求 → 分配不足 → 抖动；$\tau$ 太大 → 高估需求 → 页框浪费。
• $\tau$ 应当约等于"一个局部性阶段的长度"（无法预知，只能经验取值）。
• PFF 法：缺页率 > 上界 → 加页框；< 下界 → 收页框；加不出来 → 挂起进程。
• 处理抖动的手段：降低多道程序度（挂起进程）、工作集法分配、PFF 调节、改进置换算法——核心都是"让驻留集 ≥ 工作集"。
• 锚点数据（窗口 $\tau$）：$\tau$ = 1/2/3/4/5/6/8 → 工作集最大 1/2/3/4/4/5/6、平均 1.00/1.95/2.70/3.20/3.55/3.80/4.20。
• 锚点数据（缺页率）：驻留 1~6 帧 → LRU 缺页率 100%/85%/60%/40%/35%/30%。

2. 高频陷阱

• 说"多道程序度越高越好"：错。超过临界点后 CPU 利用率暴跌，这就是抖动（抖动曲线是倒 U 形，不是单调上升）。
• 把"工作集"与"驻留集"当成同一个东西：错。工作集是"要用多少"（需求），驻留集是"给了多少"（供给）——判据是驻留集 ≥ 工作集。
• 说"内存越大越不会抖动"：错。若进程数极多、平均分到的页框仍小于各自工作集，照样抖动——判据是"人均"，不是"总量"。
• 认为"窗口 $\tau$ 越大越准"：错。$\tau$ 太大就把早已不用的页也算进需求，导致页框浪费；应当匹配"局部性阶段长度"。
• 把"抖动"与"缺页"等同：错。缺页是正常现象（请求分页本就会缺页）；只有"缺页率极高且导致 CPU 利用率暴跌"才是抖动。
• 说"挂起进程是抖动的最优解"：不准确。它有效但牺牲并发度；更好的做法是"按工作集分配，一开始就不让超载的进程进来"。
• 认为"PFF 与工作集法是同一个算法"：错。工作集法是"前馈"（先观测需求再分配），PFF 是"反馈"（先分配再按缺页率调整）。
• 把"抖动的三种手段"与"页面置换算法"混为一谈：错。置换算法是"换谁"的问题，抖动处理是"给多少页框/进来几道程序"的问题——两个不同层面。
• 认为"改进型 CLOCK 能解决抖动"：错。它只是减少写回次数、提升置换质量，不能补上"页框绝对不足"这个缺口。

3. 解题模板（"抖动/工作集题"）

① 先算工作集: 给定窗口 tau, 对每个时刻取"最近 tau 次引用"的不同页数
     注意"窗口向前不足"时要缩短 (t - tau + 1 < 0 时从 0 开始)
② 求"工作集最大" -> 这就是"该进程至少要分多少页框"
③ 抖动判定: 比较"驻留集(题目给的页框数)" 与 "工作集大小"
     驻留集 < 工作集 -> 抖动;  >= -> 平稳
④ 若问 PFF: 先算缺页率, 再对照上/下界决定"加/减/保持"
     缺页率 > U -> 加页框;  < L -> 收页框;  加不出 -> 挂起进程
⑤ 若问"怎么消除抖动": 答"降低多道程序度 / 按工作集重新分配页框", 并点明
     "本质是让驻留集 >= 工作集"

4. 与相邻章节的接口

• os/23-virtual.md（虚拟内存与页面置换）：本章是该章的"反面"——那章例 4 算出"缺页率 ${10}^{-5}$ 才实用"，本章说的就是"当缺页率压不下来时会发生什么"。
• os/21-paging.md（分页）：页框（物理块）总数是本章的"总供给"；"每个进程分几个页框"就是在那章的机制上加了一层分配策略。
• os/11-scheduling.md（处理机调度）："多道程序度"是调度的输入——抖动会反过来要求"减少就绪进程数"，两章在这里交汇。
• os/10-process.md（进程与线程）：挂起（换出）一个进程正是把它的状态从"就绪/阻塞"变成"挂起"；抖动的处理手段直接落到那章的状态转换图上。
• arch/13-virtual.md（虚拟存储器）："按需分页 + 局部性"是硬件与系统合谋的结果；工作集模型是操作系统对"局部性"这一硬件事实的量化利用。
• os/32-io.md（I/O 管理）：抖动时磁盘 I/O 会被页面换入换出占满——那一章的"缓冲""SPOOLing"能缓解 I/O 拥塞，但救不了"页框不足"这个根本问题。

小结

• 抖动 = 页面频繁换入换出、缺页率极高、CPU 利用率暴跌；它是"缺页率压不下来"的终点。
• 抖动曲线是倒 U 形：多道程序度超过临界点后，CPU 利用率不升反降——"再加一道程序就好了"是最常见的误判。
• 根本判据只有一条：驻留集（给了多少）< 工作集（要用多少）。
• 工作集 = 窗口 $\tau$ 内访问过的页集合；$\tau$ 太小低估需求、太大高估需求，应约等于"一个局部性阶段"。
• 锚点（$\tau$ = 1/2/3/4/5/6/8）：工作集最大 1/2/3/4/4/5/6、平均 1.00/1.95/2.70/3.20/3.55/3.80/4.20——$\tau =4$ 时"最大 4、平均 3.2"。
• 锚点（驻留集 vs 缺页率，LRU）：1~6 帧 → 100%/85%/60%/40%/35%/30%——给到工作集上限 4 帧时出现"台阶式"下降。
• PFF 法：缺页率 > 上界（0.60）→ 加页框；< 下界（0.20）→ 收页框；加不出来 → 挂起进程。
• 处理抖动：降低多道程序度 / 按工作集分配页框 / PFF 调节 / 改进置换算法——本质都是让"驻留集 ≥ 工作集"。
• 内存管理四章到此闭环：连续分配（20）→ 分页（21）→ 分段与段页式（22）→ 虚拟内存与置换（23）→ 抖动与工作集（24）。

下一篇：文件系统：逻辑结构、目录、实现