Appearance
哲学家进餐问题
第三个经典问题：一个人要同时拿到两样东西
前两个问题里，一个进程一次只需要一份资源：生产者要一个空格子，读者要那把读锁。
哲学家进餐换了个条件：每个人必须同时拿到左右两根筷子才能吃。
这一条改动带来的麻烦是全新的。两次 wait 之间有缝隙—— 拿到左筷、还没拿到右筷的那一刻，这个人已经持有了一部分资源， 同时还在请求另一部分。而这正是死锁四个必要条件里的"请求并保持"。
于是朴素写法（先拿左、再拿右）会出现一个极端情形：五个人同时拿起左筷， 然后每个人都在等右边那个人手里的筷子——转成了一个环，谁也不放手。
⚠️ 这个死锁态有且只有一个：五人各握一根。把可达状态穷举一遍就能确认。 由此得到一条统一判据：只要"同时只握一根"的人数达不到 5，环就成不了。
四种解法全都是这一条的实现，只是把人数压到了不同的值：
最多允许四人同时就座（压到 4）、奇偶号哲学家取筷顺序相反（压到 3）、 用 AND 信号量把"两根一起拿"变成一个原子动作（压到 0）、 加一把互斥锁让取筷这段串行（压到 1）。
⚠️ 还有一处常被误用：四种方案的最大同时进餐人数都是 2。 那是五根筷子决定的物理上限（每人要两根），不能拿来比较方案优劣。
交互可视化
一、问题与朴素方案
5 位哲学家共用一张圆桌，桌上有 5 个碗和 5 只筷子，每两位哲学家之间放一只。他们交替地进行思考和进餐：饥饿时试图取用左右最靠近他的筷子，只有拿到两只筷子时才能进餐，进餐毕放下筷子继续思考。
P0
C4 C0
P4 P1
C3 C1
P2
C2semaphore chopstick[5] = {1, 1, 1, 1, 1};
philosopher(i) {
do {
wait(chopstick[i]); // 拿左边的筷子
wait(chopstick[(i+1) % 5]); // 拿右边的筷子
eat();
signal(chopstick[i]); // 放左边的筷子
signal(chopstick[(i+1) % 5]); // 放右边的筷子
think();
} while (TRUE);
}假如五位哲学家同时饥饿而各自拿起左边的筷子，五个 chopstick 信号量全部变为 0；再去拿右边的筷子时都将因无筷子可拿而无限期地等待。
二、四种解法
方案一：限制人数（至多 4 人同时取筷）
教材表述：至多只允许有四位哲学家同时去拿左边的筷子，最终能保证至少有一位哲学家能够进餐，并在用毕时释放出他用过的两只筷子，从而使更多的哲学家能够进餐。
semaphore limit = 4;
philosopher(i) {
do {
P(limit);
wait(chopstick[i]);
wait(chopstick[(i+1) % 5]);
eat();
signal(chopstick[i]);
signal(chopstick[(i+1) % 5]);
V(limit);
think();
} while (TRUE);
}方案二：AND 信号量（两根同时拿）
教材表述：仅当哲学家的左、右两只筷子均可用时，才允许他拿起筷子进餐。这在本质上就是 AND 同步问题，故用 AND 信号量机制可获得最简洁的解法：
semaphore chopstick[5] = {1, 1, 1, 1, 1};
philosopher(i) {
do {
think();
Sswait(chopstick[(i+1) % 5], chopstick[i]); // 两根一起申请：要么都拿到，要么一根不拿
eat();
Ssignal(chopstick[(i+1) % 5], chopstick[i]); // 两根一起放回
} while (TRUE);
}方案三：奇偶策略
奇数号哲学家先拿左边再拿右边，偶数号哲学家先拿右边再拿左边：
philosopher(i) {
do {
think();
if (i % 2 == 1) { // 奇数号：先左后右
wait(chopstick[i]);
wait(chopstick[(i+1) % 5]);
} else { // 偶数号：先右后左
wait(chopstick[(i+1) % 5]);
wait(chopstick[i]);
}
eat();
signal(chopstick[i]);
signal(chopstick[(i+1) % 5]);
} while (TRUE);
}教材给出的是一条计数论证：按此规定，相邻的两位哲学家会竞争同一只筷子，五位哲学家都先竞争奇数号筷子，获得后再去竞争偶数号筷子，最后总会有一位哲学家能获得两只筷子而进餐。落到数上就是：五个人的"第一根"目标只落在 3 只筷子上（本文 0 起编号下是 0、1、3 号；教材按 1 起编号叙述，说的是同一件事），3 只筷子最多让 3 个人各握一根，成环前提根本达不到。穷举验证也给出同一个数：奇偶策略下"同时只握一根"的最大人数是 3，死锁态 0。
方案四（变体）：用 mutex 包住两次 P
semaphore mutex = 1;
philosopher(i) {
do {
think();
P(mutex);
wait(chopstick[i]);
wait(chopstick[(i+1) % 5]);
V(mutex);
eat();
signal(chopstick[i]);
signal(chopstick[(i+1) % 5]);
} while (TRUE);
}三、四种方案对比
穷举五位哲学家的全部交错后得到的实测数据：
| 方案 | 破坏的必要条件 | 死锁态 | 最大"只握一根"人数 | 最大同时进餐 | 额外代价 |
|---|---|---|---|---|---|
| 朴素（全部先左后右） | 无 | 1 | 5 ← 正是死锁态 | 2 | — |
| 一、限制人数 ≤ 4 | 循环等待 | 0 | 4 | 2 | 多一个信号量；第 5 人即使邻座筷子都空着也进不来 |
| 二、AND 信号量 | 请求并保持 | 0 | 0 | 2 | 需要系统提供 Sswait／Ssignal |
| 三、奇偶策略 | 循环等待 | 0 | 3 | 2 | 不需要任何额外信号量 |
| 四、mutex 包两次 P | 请求并保持 | 0 | 1 | 2 | 取筷阶段完全串行；可能持锁阻塞 |
真正的差别在"最大只握一根人数"这一列——它把每个方案防死锁的机制量化了：只要这个数 < 5，死锁态就是 0。方案二、四没有改变每个人的取筷顺序（环的形状还在），它们改的是"两次申请不能被拆开"，所以消除的是请求并保持而不是循环等待。
四、三大经典同步问题横向对比
| 问题 | 信号量与初值 | 最关键的一行 | 最容易写错的地方 |
|---|---|---|---|
| 生产者-消费者 | mutex=1, empty=N, full=0 | P 操作先同步后互斥：P(empty); P(mutex); 不能反 | P(mutex) 提前 → 缓冲池满时持锁阻塞 → 死锁 |
| 读者-写者（读优先） | rw_mutex=1, mutex=1, readcount=0 | 第一个读者 P(rw_mutex)、最后一个读者 V(rw_mutex) | 把 readcount++ 放到 mutex 外 → 两人都以为自己是第一个 |
| 哲学家进餐 | chopstick[5]={1,1,1,1,1} | 五人同时各握一根 = 唯一的死锁态 | 不限人数 / 不奇偶 / 不把两次 P 合并 |
考点速记
- 哲学家进餐的特点是"一个进程需要同时持有两份资源"（AND 同步问题）。朴素方案能保证相邻两人不同时进餐，但五人同时拿起左筷即全部无限期等待。
- ⚠️根源是两次
wait之间的缝隙——那一刻进程"持有一部分、请求另一部分"，正是死锁四条件里的请求并保持。 - ⚠️死锁态有且只有一个：五人各握一根。 由此得统一判据——只要"同时只握一根"的人数达不到 5，环就成不了。
- 四种解法都是这一条的实现，把人数分别压到 4 / 3 / 0 / 1：
- 最多允许四人同时就座（压到 4）；
- 奇偶号哲学家取筷顺序相反（压到 3）；
- AND 信号量
Swait把"两根一起拿"变成原子动作（压到 0）； - 加互斥锁让取筷这段串行（压到 1）。
- ⚠️破坏的条件不同：方案一与二破坏循环等待（改的是取筷顺序或人数），方案三与四破坏请求并保持（后者没改取筷顺序，改的是两次申请不能被拆开）。
- ⚠️四种方案的最大同时进餐人数都是 2——那是五根筷子决定的物理上限，不能用来比较方案优劣。
这一节在真题里被考过的形式：
出过一道大题，而且题面把课本原题改了。
位哲学家（ ）交替思考与进餐，写出不会死锁的 PV 方案（2019-43，挂在 deadlock标签下）。⚠️ 与课本原题最大的差别是人数是不是 5，所以答案里的常数必须跟着变——比如"最多允许 人同时就座"。照抄课本的 5 会直接失分。 - 判分点通常有三处：信号量的定义与初值（筷子数组初值全 1，若用"最多
人"方案则再加一个初值 的信号量）、取筷与放筷的完整代码、说明为什么不会死锁——最后这一处要答到速记第三条那个判据上，而不是只说"因为限制了人数"。
复习优先级：必须能动手写，且要能说清理由。 速记第三条那个统一判据是 "为什么不死锁"的标准答法；第五条（各方案破坏哪个必要条件）在 死锁的概念与预防会被再问一次。 第六条（最大进餐人数都是 2）是选项里的陷阱，要单独记。
易错：
位哲学家的题里照抄课本的"最多 4 人"。要写成 。
易错：认为四种方案的最大同时进餐人数不同。都是 2——那是筷子数决定的物理上限。
易错：把"奇偶号取筷顺序相反"当成破坏请求并保持。它改的是取筷顺序，破坏的是循环等待。
易错：认为朴素方案总会死锁。只有五人同时拿起左筷这一个状态才死锁，其余状态都能推进。
易错：答"为什么不死锁"时只说限制了人数。要答到"同时只握一根的人数达不到
，环就成不了"。
教材出处
- 问题描述与记录型信号量方案：汤小丹《计算机操作系统》2.5.2 节，印刷 p63—p64——"只有在他拿到两只筷子时才能进餐"；
semaphore chopstick[5]={1,1,1,1,1};与先左后右的wait/signal序列；"虽然，上述解法可保证不会有两个相邻的哲学家同时进餐，但却有可能引起死锁"。 - 三种解决方法：同书印刷 p64——(1) "至多只允许有四位哲学家同时去拿左边的筷子"；(2) "仅当哲学家的左、右两只筷子均可用时，才允许他拿起筷子进餐"；(3) 奇偶策略，并给出计数论证"将是 1、2 号哲学家竞争 1 号筷子；3、4 号哲学家竞争 3 号筷子。即五位哲学家都先竞争奇数号筷子，获得后，再去竞争偶数号筷子，最后总会有一位哲学家能获得两只筷子而进餐"。
- AND 信号量解法：同书印刷 p64—p65——"在本质上就是前面所介绍的 AND 同步问题，故用 AND 信号量机制可获得最简洁的解法"，代码为
Sswait(chopstick[(i+1)%5], chopstick[i]); ... Signal(chopstick[(i+1)%5], chopstick[i]);。