同步
引入
词汇
| English | 释义 | 拼音 |
|---|---|---|
| interleaving | 交错 | jiāo cuò |
| lock | 锁 | suǒ |
| mutual exclusion | 互斥 | hù chì |
| spin/spɪn/ | 自旋 | zì xuán |
丢失的更新
- 两个线程对
counter = 5执行counter = counter + 1。各自读、加、写；交错 interleaving R1 R2 W1 W2 留下 $6$ 而非 $7$——一次更新丢了。各加四次时，1 到 8 的每个终值都可达：七次增量可以全部消失。
{exercise:uni-cs0703-race}
练习
两线程对 counter = 5 各加一（先读后写）。无锁交错 R1 R2 W1 W2 留下——
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
两次读都是 5；两次写都存 6——丢一次加一。
锁必须保证什么
- 互斥 mutual exclusion：一次只有一个在里面。前进：空则必有人进。有界等待：无人饿死。Peterson 算法用软件三者兼备；
test-and-set用一条原子指令同样做到——但都要自旋 spin，烧着 CPU。 - 信号量与互斥锁加上 OS 队列：阻塞的等待者睡觉而不是自旋——真实系统层层叠加的原因。
{exercise:uni-cs0703-lock}
练习
自旋锁烧 CPU；互斥锁队列靠——避开。
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
阻塞的等待者睡进 OS 队列而不是自旋。
死锁四骑士
- A 持 L1 要 L2；B 持 L2 要 L1。死锁需要互斥、持有并等待、不可抢占、循环等待——破掉任何一个就不会发生。
- 工程师最爱破的是循环等待：给锁排序（永远先 L1 后 L2）。加睡眠修不了竞争，只会收窄窗口。
例子
单核机照样竞争：读与写之间被抢占就足够了。
{exercise:uni-cs0703-deadlock}
练习
给所有锁请求排序破掉的是——
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
固定次序让环不可能——最便宜的破法。