首页/操作系统/03-memory/抖动与工作集 🔗 在 Obsidian 中打开
操作系统 · 03-memory

抖动与工作集

重要度 ⭐⭐⭐⭐ 难度 ⭐⭐⭐考查频率 高 操作系统/内存管理抖动工作集thrashingworking-set
速查
抖动是频繁缺页导致 CPU 利用率急剧下降的现象，根因是多道程序度太高；工作集是进程在时间窗口 $\Delta$ 内访问的页面集合，只要 $\sum WSS_i \leq$ 可用页框总数 就不会抖动。

速查 ▾

项目值
抖动（Thrashing）频繁的页面置换，CPU 利用率急剧下降
工作集进程在时间窗口 $\Delta$ 内访问的页面集合
工作集模型用于预防抖动，给进程足够的页框
局部性原理时间局部性 + 空间局部性

核心概念 ▾

抖动（Thrashing）

  • 进程频繁发生缺页，大部分时间花在页面置换上，CPU 利用率急剧下降。
  • 原因：进程获得的页框太少，无法容纳其工作集。
  • 后果：CPU 利用率随进程数增加反而下降。
抖动拐点 抖动区 缺页率↑ · CPU 利用率↓ 并发提升，CPU 利用率上升 CPU 利用率 多道程序度（并发进程数）→
图：多道程序度提高先使 CPU 利用率上升，越过拐点后各进程页框不足，缺页率暴涨，CPU 利用率急剧下滑。

工作集（Working Set）

  • 进程在时间窗口 $\Delta$ 内访问的页面集合。
  • $WSS_i$：进程 $P_i$ 的工作集大小（$\Delta$ 时间内访问的不同页面数）。
  • 所有进程的工作集之和 $\sum WSS_i \leq$ 可用页框总数 → 不会抖动。

抖动的原因

  • 多道程序度太高（进程太多）。
  • 每个进程分到的页框太少。
  • 工作集不能全部装入内存。

抖动的预防

  1. 工作集模型：给每个进程分配足够的页框覆盖其工作集。
  2. 局部置换策略：限制每个进程只能使用自己的页框。
  3. 挂起进程：当内存不足时挂起一些进程，减少多道程序度。
  4. L=S 准则：缺页间隔时间 $L$ 等于缺页处理时间 $S$ 时，CPU 利用率达最大。
为什么工作集模型有效 工作集是局部性原理的量化表达：程序在一段时间内只会集中访问少数几个页面。只要给进程的页框数 $\geq WSS$，缺页就只发生在局部性切换的时刻，而不会持续发生。

关键性质 ▾

现象原因后果
抖动多道程序度太高CPU 利用率下降
工作集过大$\Delta$ 窗口太大需要更多页框
缺页率上升页框不足频繁置换
预防方法原理
工作集模型给进程足够的页框覆盖工作集
局部置换进程只用自己分配的页框
挂起进程减少多道程序度
L=S 准则控制缺页频率

常见考法 ▾

考法解题套路
抖动的判断缺页率极高、CPU 利用率低 → 抖动
工作集计算统计 $\Delta$ 窗口内访问的不同页面
抖动的解决减少进程数或给进程更多页框
局部性原理时间局部性（最近访问的可能再访问）+ 空间局部性（附近的地址可能被访问）
工作集怎么数 题干给出访问串与窗口 $\Delta$，问 $t$ 时刻的工作集 $WS(t,\Delta)$。做法：取最近 $\Delta$ 次访问（含第 $t$ 次），去重后即为工作集；集合元素个数就是 $WSS$。下方交互动画即按此规则逐步演示。

易错点 ▾

注意
  • 抖动时 CPU 利用率下降——不是上升（大量时间花在页面置换上）。
  • 工作集大小不是固定的——随时间窗口 $\Delta$ 和程序执行阶段变化。
  • 抖动的根本原因是多道程序度太高，不是页面置换算法不好。
  • 解决抖动不能靠换更好的置换算法——要减少进程数或增加内存。
  • 局部性原理是虚拟内存有效的根本原因。

核心结论 ▾

必背
  1. 抖动是多道程序度过高的结果，导致 CPU 利用率急剧下降。
  2. 工作集是进程在 $\Delta$ 时间内访问的页面集合，反映进程的实际内存需求。
  3. 给每个进程分配覆盖其工作集的页框数，可以预防抖动。
  4. 局部性原理（时间 + 空间）是虚拟内存有效的根本原因。
  5. L=S 准则：缺页间隔 $L$ = 缺页处理时间 $S$ 时 CPU 利用率最大。

记忆卡片 ▾

什么是抖动？
频繁页面置换导致 CPU 利用率急剧下降的现象。
抖动的根本原因？
多道程序度太高，每个进程获得的页框不足以覆盖工作集。
什么是工作集？
进程在时间窗口 $\Delta$ 内访问的页面集合。
如何预防抖动？
工作集模型（给足够页框）、局部置换、挂起进程。
什么是局部性原理？
时间局部性（刚访问的可能再访问）+ 空间局部性（附近的地址可能被访问）。

交互动画 · 工作集窗口滑动 ▾

页面访问串（时间 t →），工作集窗口 Δ = 4 1 2 3 4 1 2 5 1 2 3 4 5 t1 t2 t3 t4 t5 t6 t7 t8 t9 t10 t11 t12 WS(1, Δ=4) = { 1 } 工作集大小 WSS(t)（柱高 = 窗口内不同页面数） 1 2 3 4 4 4 4 3 3 4 4 4
WS(1, Δ=4) = { 1 }，WSS = 1
窗口覆盖 t1 … t1；当前访问页面 1
窗口内页面去重后即为工作集；本例 $WSS$ 稳定在 3~4，说明只要给该进程 4 个页框 就基本不会抖动。

相关知识点

virtual-memory-management opt-page-replacement

↑ 以上为站内 HTML 相对链接（纯网页可浏览）；本页右上「在 Obsidian 中打开」跳回源笔记。