CHAPTER 02 · 2.6 经典同步问题 三个可操作模拟 · 可单步、可自动、可制造死锁 ← 上一节:进程同步与互斥

五根筷子与一只空槽

生产者-消费者、读者-写者、哲学家进餐,三个问题共用同一套零件:计数信号量、互斥信号量、等待队列。 下面把三个模型都做成可推演的实验台——你可以按正确顺序走完 P/V,也可以把顺序反过来,亲眼看到死锁是怎么被凑齐的。

自定义实验参数 容量 · 速度 · 默认实验 · 哲学家 / 读者策略 展开 ▾
预设

预设只载入字段,点击“应用并重新开始”才生效。应用会停止所有自动运行、清空三份日志并重置三个实验,然后切到所选标签页;页面里原有的容量滑块、策略开关和速度按钮会同步更新。

经典问题实验台SYNC LAB · 3 SIMULATIONS

信号量实时记账

有界缓冲区BOUNDED BUFFER

0 / 4 槽
占用 0 / 4
PRODUCER生产者
空闲
CONSUMER消费者
空闲

临界区执行序列TRACE

每次单步按当前顺序完整记账

P 失败的一步会停在原地并阻塞,不会继续执行后面的 V——这正是“抱着锁睡觉”与“在锁外排队”的分界。记录型信号量允许负值;V 先加 1,结果 ≤ 0 时唤醒一个等待者,被唤醒者直接接管这次 V 移交的资源,所以在它继续执行前,信号量可能暂时为 0。

empty空闲槽位
4无等待
full产品数量
0无等待
mutex临界区锁
1无等待

阻塞队列WAIT QUEUES

记录型信号量:负值 = 等待进程数

顺序对照ORDER MATTERS

切到错误顺序,把缓冲区填满试试
正确 P(empty) → P(mutex)

先排队等空槽,拿到空槽再进临界区;阻塞发生在锁外,mutex 不会被占着睡觉。

错误 P(mutex) → P(empty)

先拿锁再等空槽;满缓冲区时抱着 mutex 阻塞,消费者无法进入临界区 → 死锁。

共享文件 / 数据库SHARED DB

空闲
SHARED FILE DB 没有进程访问

读者区 · 可并发 0

写者区 · 必须独占 0

FIRST READER · P(wmutex) 尚未发生 readcount 0 → 1 时锁住数据库
LAST READER · V(wmutex) 尚未发生 readcount 1 → 0 时释放数据库
readcount读者计数
0正在读的读者数
rmutex计数锁
1保护 readcount
wmutex数据库锁
1无进程持有

等待队列WAIT QUEUES

负值 = 该信号量上的等待人数

三种优先级POLICY

本页实现前两种,第三种仅作说明
读者优先

新读者只要 readcount > 0 就进入;写者可能长期等待,读者密集时饥饿。

写者优先

写者一排队就关闭读者闸门,新读者不能越过写者;本页用闸门简化实现。

公平

读写请求按到达顺序排队,任何一方都不能插队;需要额外的请求队列与计数。

圆桌 · 5 位哲学家 / 5 根筷子DINING PHILOSOPHERS

思考中
ROUND TABLE 0 / 5 同时进食
  • 思考
  • 饥饿 / 等待
  • 进食
  • 筷子被占

把三个模型拆到同一副骨架上

同步问题没有三套解法,只有一套零件在不同资源结构上的组合。

2.6 / 核心
01 / 生产者-消费者

同步与互斥叠加,P 的顺序不能反

有界缓冲区同时受两种约束:满时不能放、空时不能取(同步);同一时刻只能有一个进程读写槽位(互斥)。所以需要 empty 计空槽、full 计产品、mutex 保护缓冲区。

  • 正确顺序:P(empty) → P(mutex) → 放入 → V(mutex) → V(full)
  • 反序时,生产者先拿到 mutex,再在 empty 上阻塞,消费者无法进入临界区取走产品
  • 满时生产者在 empty 上等,空时消费者在 full 上等;记录型信号量变成负值
  • V(mutex) 放在 V(full) 前,被唤醒的消费者可以立刻进入临界区
02 / 读者-写者

readcount 自己是共享变量,也要上锁

读者共享只读,写者必须独占。readcount 记录读者数,rmutex 保护 readcount,wmutex 是数据库的独占锁:第一个读者 P(wmutex),最后一个读者 V(wmutex)。

  • readcount++ / -- 必须放在 rmutex 临界区内,否则两个读者可能同时看到 0,或最后一个读者漏掉 V
  • 读者优先:只要还有读者在读,新读者直接进入,写者继续等 → 可能饥饿
  • 写者优先:写者排队后关闭读者闸门;公平策略按到达顺序放行
  • 写者优先不是把正在读的读者赶走,而是阻止新读者继续越过等待的写者
03 / 哲学家进餐

死锁的四个条件在圆桌上同时成立

5 人 5 筷,每人需要左右两根,朴素策略先左后右。当 5 人同时拿起左筷再等右筷时,四个必要条件一个不少。

  • 互斥:一根筷子一次只能被一个人使用
  • 占有并等待:拿着左筷,等右筷
  • 不可剥夺:筷子只能由持有者自己放下
  • 循环等待:P1 等 P2 手里的筷,…,P5 等 P1 手里的筷
  • 三种破解:限制 4 人、奇偶不同顺序、一次性原子地拿两根
04 / 共同骨架

计数信号量 + 互斥信号量 + 等待队列

三个问题看起来是三套代码,其实结构完全一致:计数信号量表示“可用资源数”,互斥信号量保护共享变量,P 失败时进程挂到该信号量的等待队列上。只要能把问题里的“资源”和“共享变量”分开,就能写出正确的 P/V 序列。

生产者-消费者 empty=N,full=0,mutex=1
读者-写者   wmutex=1,rmutex=1,readcount=0
哲学家     chop[5]=1,seat=4

记录型信号量的值是“资源余量减去等待人数”:值小于 0 时,绝对值就是等待队列长度;V 先把值加 1,若结果仍 ≤ 0,就从队列里唤醒一个等待者。所以负值不是 bug,而是“有人在排队”的另一种写法。

05 / 常见误区

临界区越大越安全?V 的顺序无所谓?

把 mutex 扩大到包住整个生产流程,结果不会错,但会把并发压成串行:生产者在等空槽时也占着锁,消费者有产品也进不来。更糟的是,一旦把 P(empty) 关进锁里,缓冲区满时直接死锁。

  • 临界区只包住真正共享的数据(槽位数组、readcount、筷子状态),不要包住等待
  • V 不阻塞,顺序通常不影响正确性,但影响唤醒路径与上下文切换次数
  • 读者优先不保证写者“一定”饥饿,但读者不断到达时,写者可能无限期等待

课堂追问

为什么必须 P(empty) 在 P(mutex) 之前?反过来会怎样?

P(empty) 申请的是“空槽”资源,失败时应停在临界区外。反过来,生产者先拿到 mutex 再发现没有空槽,就会抱着锁睡眠;消费者要取走产品必须先拿 mutex,而锁在生产者手里,两个进程都推进不了,形成死锁。先 P(empty) 再 P(mutex),阻塞发生在进入临界区之前,锁不会被等待资源的进程占住。

读者优先策略下,写者一定会饥饿吗?

不一定,但可能发生。写者到达时若有读者在读,就在 wmutex 上排队;此后每个新读者只要看到 readcount > 0,就在 rmutex 里加一后直接读。只有 readcount 降到 0,最后一个读者 V(wmutex) 才会唤醒写者。因此读者到达足够密集、计数长期不归零时,写者可能无限期等待;读者之间有间隙时,写者最终能拿到锁。

限制 4 人为什么能破死锁?它破坏的是哪个条件?

死锁需要 5 根筷子同时被 5 个人各持一根,形成“每人等下一根”的环。限制同时进餐人数为 4 后,最多 4 人参与竞争,5 根筷子不可能全被占住:至少有一根空闲。一根筷子两侧最多只有一个“没座位的人”,另一侧的持筷者可以拿到它、吃完放下,环就被打破。它破坏的是“循环等待 / 全部资源被占”这一条件,而不是让筷子变成可抢占。

把 mutex 扩大到整个生产流程,会发生什么?V 的先后有关系吗?

互斥范围过大不会让结果错,但会把并发压成串行:生产者等空槽时也占着 mutex;一旦 P(empty) 在锁内失败,就直接死锁。V 的顺序一般不影响正确性,但影响唤醒路径:先 V(mutex) 再 V(full),消费者醒来时锁已空出,可立即进入;反过来它可能先醒来、再在 mutex 上阻塞一次。V 本身不阻塞,不会因此死锁。

← PREV · 2.5进程同步与互斥:临界区、信号量、P/V