# 锁与死锁实验室

直接双击 `index.html`，使用浏览器打开。无需服务器、安装、登录或联网。可将 HTML 单独复制到授课电脑。

对应《计算机科学导论》Slide08 第 92–95 页：用锁变量控制互斥、测试与置位的原子性，以及死锁的四个必要条件。

## 课堂演示：约 10 分钟

第一幕以**打印室门口的“有人 / 无人”牌子**为例。主画面只展示小蓝、小绿、门口的牌子和打印室，每一步用一句话说明动作。人物进入时会从门外移动到室内。打印室一次只允许一人；出门后翻回“无人”。

### 第一幕：看牌、翻牌分两步，为什么会出问题？

打开“① 锁为什么需要原子操作”，默认选择“分两步：先看，再翻”。

1. 点两次“下一步”：小蓝、小绿都说“我看到无人”，谁也还没翻牌。停下来问：他们是不是都觉得自己可以进去？
2. 第三步：小蓝翻成“有人”，小绿仍记得之前看到的“无人”。牌子是占用标记，翻牌和实际进门是两个步骤。
3. 第四步：小绿依据之前看到的“无人”，也把牌子翻成“有人”，没有重新检查。
4. 再点两次：两个人都走进打印室，房间标红。问：问题出在哪两步之间？
5. 指出：这是互斥失效，不是死锁。两人没有互相等住，反而都进入了本该独占的区域。

人物的气泡表示之前看到的内容，不是额外两份牌子，也不是硬件缓存没有同步。看完之后已作出的判断，不会因别人翻牌而自动重做。“同时进入”表示两人都还没离开，不要求同一瞬间执行两条 CPU 指令。

### 第二幕：把看牌、翻牌合成一步

点击“改用原子操作再试”，或选择上方“合成一步（原子操作）”。

1. 第一步：小蓝看到“无人”，在同一步立即翻成“有人”。
2. 第二步：小绿再来看，只能看到“有人”，留在门外。
3. 继续：小蓝进去、出来，翻回“无人”；小绿重新看牌，才获准进入。两人最终先后完成。

只需强调：**看牌和翻牌必须合成不可被插入的一步**，只让“翻牌”本身不可分割仍然不够。

需要联系课件时，展开“查看原理、代码与执行记录”。这里保留 L=0/1 对照、执行顺序表、教学伪代码和“推进小蓝 / 小绿”的手动调度按钮。小蓝对应 P1，小绿对应 P2；主画面默认不展示这些细节。

技术说明：`atomic_exchange(L,1)` 不可分割地读取旧值并写入 1。只有读到旧值 0 才成功；读到 1 表示需要重试，失败也不会释放锁。本例为自旋重试。前一人释放后，后一人可重新读到 0；两次历史读数同为 0，不意味着同时进入。

手动先让一人完整执行、再让另一人执行，分两步也可能不出错。失败取决于交错顺序，不能用一次成功证明实现正确。

### 第三幕：明明每把锁都是原子获取，为什么仍会死锁？

切换“② 两把锁怎样形成死锁”，使用默认“相反顺序”。每次 `lock(...)` 都使用正确的单锁获取机制。

| 点击 | 发生什么 | 是否死锁 |
| --- | --- | --- |
| 1 | P1 获取 A | 否 |
| 2 | P2 获取 B | 否；先停下让学生预测 |
| 3 | P1 请求 B，但 B 被 P2 持有，P1 阻塞 | 仍未死锁：P2 还能运行 |
| 4 | P2 请求 A，但 A 被 P1 持有，P2 也阻塞 | 是：形成相互等待的环 |

此时，两人都执行不到代码后面的 `unlock`，不是“不愿意让”，而是程序顺序使他们无法走到释放锁的那一行。原子获取单把锁，并不等于一次性获取两把锁。

图中实线表示“锁 → 持有者”，虚线表示“进程 → 请求的锁”。死锁时可沿箭头走一圈：`P1 → B → P2 → A → P1`。

页面同时解释互斥、占有并等待、不可剥夺、循环等待。注意：只有一个进程等待，不足以判定死锁。

### 第四幕：统一先拿 A、再拿 B

点击“统一拿锁顺序再试”。P2 起初可能等待 A，但它没有拿着 B 来等待 A；P1 能拿到 B、完成工作并释放资源，随后 P2 被唤醒，重试获取并完成。

这里破坏的是循环等待条件。统一顺序是本例的死锁预防方案，不是让某个进程强行释放别人持有的锁。

也可以在相反顺序模式手动让 P1 全部执行完，再执行 P2：不会死锁。“相反顺序可能导致死锁”不等于“每一种执行顺序都会死锁”。

## 操作说明

- “下一步”：优先交替推进两个可运行进程；阻塞或完成的进程会跳过。
- 第一幕的“下一步”只推进一个动作；主画面用一句话说明刚才发生的事。人物气泡保留之前看到的牌子。
- 第一幕默认收起原理、顺序表、手动调度、伪代码和日志；第二幕继续显示代码和资源关系图。
- “推进 P1 / P2”：自己指定下一个执行进程，适合让学生选择交错顺序。
- “自动演示 / 暂停”：按所选间隔推进；遇到互斥失效、死锁或全部完成时自动停止。
- “重置”、切换场景或方案：清空当前状态并停止旧的自动播放。
- 死锁时不允许直接推进阻塞进程去执行后面的释放指令；应重置后换方案再试。
- 窄屏下关系图保留大字号，允许左右滚动；支持系统减少动态效果设置。

## 模型边界与参考

这是确定的教学调度模型，网页不会创建真正卡死的线程。第一幕为自旋获取一把锁；第二幕为阻塞获取两把独占锁，每种锁只有一份。所有操作由按钮选择的顺序模拟，不依赖浏览器恰好产生某种线程调度。

教学伪代码不展开真实多核内存顺序、内存屏障、公平性或饥饿问题。真实程序应使用语言或运行时提供的原子操作与锁，而不是把普通 JavaScript 变量赋值当作跨线程互斥锁。

- [OSTEP 第 28 章：Locks](https://pages.cs.wisc.edu/~remzi/OSTEP/threads-locks.pdf)
- [OSTEP 第 32 章：Common Concurrency Problems](https://pages.cs.wisc.edu/~remzi/OSTEP/threads-bugs.pdf)

逻辑检查：安装 Node.js 后，可在本目录执行 `node --test tests/engine.test.cjs`。运行网页本身无需 Node.js。