操作系统经典可视化
三大经典机制，一页全跑通：进程调度看甘特图、 页面置换数缺页率、死锁避免求安全序列。 左侧调参数，右侧实时更新，所有数值保留两位小数。
1公式与参数
进程调度关注三个时间指标：完成时间 $C_i$、周转时间 $T_i$、等待时间 $W_i$。 调度算法的目标通常是让平均等待时间最小：
$A_i$ 是到达时间，$B_i$ 是服务时间（突发时间）。带权周转时间 $T_i / B_i$ 更能反映长短作业的公平性。
时间片轮转（RR）的关键参数是时间片 $q$：每个进程最多连续运行 $q$ 个时间单位， 然后被放回队尾。若 $q \to \infty$ 则退化为 FCFS；若 $q \to 0$ 则上下文切换开销主导。
页面置换的核心指标是缺页率。设访问序列长度为 $L$，缺页次数为 $F$：
FIFO 可能出现 Belady 异常（增加页框反而缺页更多）；LRU 和 OPT 属于栈算法，不会出现该异常。
银行家算法通过判断系统能否处于安全状态来避免死锁。 令 $\text{Need} = \text{Max} - \text{Allocation}$，$\text{Work}$ 为当前可用资源：
反复执行直到所有进程都能完成（Finish 全为 true），则存在安全序列， 系统处于安全状态；否则若某时刻找不到满足条件的进程，说明可能发生死锁。
| 符号 | 数学含义 | 通俗解释 |
|---|---|---|
| Aᵢ | 到达时间 | 进程什么时候进入就绪队列。如果为 0，表示一开始就在。 |
| Bᵢ | 服务时间 / 突发时间 | 进程需要 CPU 运行多久才能完成。本页取 2~7 个时间单位。 |
| Cᵢ | 完成时间 | 进程最后一次离开 CPU 的时刻。 |
| Tᵢ / Wᵢ | 周转 / 等待时间 | 周转 = 完成 − 到达；等待 = 周转 − 服务。等待时间是调度算法的核心优化目标。 |
| q | 时间片（RR） | RR 算法每个进程一次最多运行的时间。太小开销大，太大退化为 FCFS。 |
| F | 缺页次数 | 访问的页不在内存时需要从磁盘调入，这一次访问就算一次缺页。 |
| Max / Alloc | 最大需求 / 已分配 | 银行家算法里每个进程"最多要多少"和"现在拿着多少"。 |
| Need | 尚需资源 | Need = Max − Allocation。等于 0 表示这个进程已经拿够了。 |
| Work | 当前可用资源 | 安全性检查时用来模拟"如果我手上有这些资源，能先让谁跑完"。 |
2交互模拟
调整算法与进程数，右侧甘特图会立即重画。鼠标悬停在色块上可以看到该进程的运行区间。
| 进程 | 到达 | 服务 | 优先级 | 开始 | 完成 | 周转 | 等待 |
|---|
选择置换算法与页框数，右侧会逐列展示每一步的页框状态。 红色列表示缺页，绿色列表示命中。
使用经典银行家算法示例（5 个进程、3 种资源）。点击下方按钮逐步执行安全性检查， 观察 Work 如何随着进程完成而增长，以及安全序列如何被构建出来。
Allocation 已分配
Max 最大需求
Need 尚需 = Max − Alloc
Work + Finish
3深入理解
标准介绍
进程调度是操作系统的核心职责之一，决定就绪队列中哪个进程获得 CPU。 经典算法包括 FCFS（先来先服务）、SJF（短作业优先，可抢占版本为 SRTF）、 RR（时间片轮转，现代分时系统的基础）与优先级调度。 页面置换解决虚拟内存中"内存满了该换出哪一页"的问题， FIFO 最简单但可能出现 Belady 异常；LRU 利用时间局部性，接近最优； OPT（Belady 最优）需要预知未来，只能作为理论下界。 死锁避免通过银行家算法（Dijkstra, 1965）在分配前预判系统是否仍处于安全状态， 是"死锁预防、避免、检测、恢复"四类策略中最具代表性的一种。
通俗介绍
进程调度像食堂打饭：FCFS 就是排队，先来先打； SJF 是让"只打一个菜的人"先打，提高整体吞吐； RR 是每个人最多打 30 秒，时间到了就排到队尾——分时系统靠它让每个人都能"轮得到"。 页面置换像书桌太小：只能放几本书，来了新书就要把一本拿走。 FIFO 是"最早放上桌的先拿走"，LRU 是"最近最少翻的拿走"， OPT 是"以后最久不会用到的拿走"——只有神仙才能预知未来。 银行家算法像银行贷款：在放贷前先算一笔账， 确保即使所有客户都来提款，银行也不会破产。如果算下来无法满足，就先拒绝这笔贷款。
解决了什么问题
- CPU 利用率与响应时间：让多个进程公平、高效地共享一颗 CPU。
- 内存容量不足：虚拟内存 + 页面置换让程序可以使用超过物理内存的空间。
- 并发资源竞争：银行家算法在分配前预判，避免系统进入死锁状态。
- 局部性原理的工程化：LRU、Clock 等算法把"时间/空间局部性"变成可执行的策略。
- 吞吐量与公平性的权衡：不同算法给出不同的折中方案，供不同场景选择。
为什么重要
- 它们是操作系统课程的三大经典章节，几乎每本教材都会花大量篇幅讲解。
- 它们是实际系统性能的直接决定因素：调度策略影响服务器吞吐，置换算法影响程序响应。
- 它们展示了理论与工程的结合：LRU 是理论最优的近似，Clock 是 LRU 的廉价实现。
- 它们是并发与资源管理思想的源头：现代容器调度、K8s 资源分配都能看到它们的影子。
- 它们让抽象的"公平""安全""局部性"变成了可量化、可比较的指标。
应用场景
- Linux 调度器：CFS（完全公平调度）基于红黑树，是 RR 思想的高级演化。
- 实时系统：优先级调度配合优先级继承，保证关键任务按时完成。
- 数据库缓冲池：LRU 及其变种（LRU-K、2Q）决定哪些页留在内存中。
- Web 缓存：Redis、CDN 的缓存淘汰策略大量借鉴 LRU、LFU、Clock。
- 分布式资源分配：银行家算法的思想被用于分布式事务、容器编排的资源预留。
- 编译器寄存器分配：图着色算法与"安全分配"的思想同源。
缺陷与局限
- SJF 需要预知未来：真实系统无法准确知道进程还要运行多久，只能靠历史估计。
- RR 的时间片难以调优：太小导致上下文切换开销大，太大退化为 FCFS。
- LRU 硬件实现昂贵：需要为每个页维护时间戳，实际多用 Clock 近似。
- OPT 不可实现：只能作为理论下界，用来评估其他算法的优劣。
- Belady 异常：FIFO 在某些访问序列下增加页框反而缺页更多。
- 银行家算法要求静态已知：需要预先知道每个进程的最大需求，实际中很难获取。
- 安全性检查开销大：$O(n^2 m)$ 的检查频率高时会影响性能，实际系统很少原样使用。
动手建议
把进程调度切到 FCFS，记下平均等待时间； 再切到 SJF，你会发现平均等待时间明显下降——因为短作业不再被长作业堵在后面。 再切到 RR，把时间片从 1 调到 5： 时间片很小时平均等待时间可能反而变大（切换开销），时间片太大则退化为 FCFS。 页面置换里，把帧数从 3 调到 4，观察三种算法缺页率的变化—— FIFO 有时会出现"增加帧数、缺页率反而上升"的 Belady 异常，LRU 和 OPT 则单调下降。 最后到死锁标签页，一步步跑银行家算法：注意 Work 是如何从 [3,3,2] 增长到 [10,5,7] 的， 每一步选择的进程都是"当前 Work 能满足其 Need"的那个。这就是安全序列的本质。