计算机操作系统18

第十八课：哲学家进餐问题（Dining Philosophers Problem）

一、故事背景

有：

5 位哲学家

围坐在一张圆桌旁。

桌子中间没有食物限制。

但是：

每两位哲学家之间：

只有：

1 根筷子

所以：

总共：

5 根筷子

示意图：

P0
筷0 筷1

P4 P1

筷4 筷2

P3 P2
筷3

每位哲学家：

左右各有一根筷子。

二、吃饭规则

规定：

思考

↓

饿了

↓

拿左筷子

↓

拿右筷子

↓

吃饭

↓

放下两根筷子

↓

继续思考

注意：

必须同时拿到左右两根筷子才能吃饭。

只有一根：

不能吃。

三、开始模拟

假设：

五个人：

同时：

饿了。

于是：

每个人：

都先拿：

左边的筷子。

结果：

P0：

拿到：

左筷

P1：

拿到：

左筷

……

一直到：

P4。

现在：

发生了什么？

四、桌上的状态

P0 拿着左筷

P1 拿着左筷

P2 拿着左筷

P3 拿着左筷

P4 拿着左筷

于是：

所有筷子：

都被拿走了。

然后：

每个人：

都准备：

拿：

右边：

那根。

但是：

右边：

已经：

被邻居拿走了。

例如：

P0：

想拿：

右筷。

发现：

P1：

已经拿走。

P1：

想拿：

右筷。

发现：

P2：

已经拿走。

……

一直：

循环。

五、最后发生什么？

每个人：

都在等待：

别人：

放筷子。

但是：

谁都：

不会：

主动：

放。

于是：

整个系统：

永远：

停住。

这就是：

死锁（Deadlock）

六、为什么会死锁？

因为：

形成了：

一个等待环。

例如：

P0 等 P1

↓

P1 等 P2

↓

P2 等 P3

↓

P3 等 P4

↓

P4 等 P0

是不是：

形成：

一个圈？

这个：

就叫：

循环等待（Circular Wait）

这是死锁最典型的表现。

七、死锁四个必要条件（★★★★★）

教材中：

这是必考内容。

只要：

四个条件：

同时满足。

就：

可能：

发生死锁。

条件①：互斥（Mutual Exclusion）

资源：

一次：

只能：

一个人：

使用。

例如：

一根筷子：

不能：

两个人：

一起拿。

满足。

条件②：请求并保持（Hold and Wait）

什么意思？

已经：

拿着：

左筷。

还继续：

等待：

右筷。

是不是：

一边占有。

一边申请？

满足。

条件③：不可剥夺（No Preemption）

别人：

能不能：

强行：

把筷子：

抢走？

不能。

必须：

哲学家：

自己：

放下。

满足。

条件④：循环等待（Circular Wait）

刚才：

画过：

等待环。

满足。

四个：

全部：

满足。

于是：

死锁。

八、怎么解决？

方法很多。

我们先讲：

教材：

最经典：

三种。

方法一：最多允许四个人同时吃（★★★★★）

这是：

最经典。

为什么？

假设：

只有：

4个人：

允许：

拿筷子。

总有：

一个人：

没进去。

于是：

一定：

有一根筷子：

没人拿。

是不是：

总有人：

能拿到：

两根筷子？

吃完：

放下。

别人：

继续。

于是：

不会：

形成：

完整：

等待环。

方法二：一次拿两根

规定：

要么：

同时拿到

左右两根

↓

进去吃

否则：

一根：

都不能拿。

这样：

不会：

出现：

拿着：

左边：

一直等。

所以：

破坏：

请求并保持。

方法三：奇偶规则

例如：

规定：

偶数号：

先拿左。

奇数号：

先拿右。

例如：

P0：

左→右

P1：

右→左

P2：

左→右

P3：

右→左

P4：

左→右

这样：

等待：

方向：

不同。

不会：

形成：

完整：

环。

于是：

不会：

死锁。

九、为什么限制四个人可以？

很多同学：

第一次：

不理解。

我们：

画一下。

假设：

只有：

四个人：

进入。

第五个人：

门外：

等。

那么：

至少：

有：

一根：

筷子：

没人拿。

于是：

总有人：

可以：

同时：

拿到：

左右。

吃饭。

放下。

整个系统：

继续。

所以：

不会：

卡死。

十、哲学家问题到底想说明什么？

它：

不是：

真的：

讲哲学家。

而是：

告诉我们：

多个线程：

如果：

各自：

占有：

部分资源。

再：

等待：

其他资源。

就：

容易：

死锁。

例如：

数据库：

两个事务。

网络：

两个锁。

文件：

两个进程。

全部：

一样。

十一、死锁四条件口诀（★★★★★）

一定：

背。

互斥

↓

请求并保持

↓

不可剥夺

↓

循环等待

口诀：

互斥、保持、不可抢、循环等待死锁现。

十二、考试最喜欢问

问：

为什么：

哲学家：

会死锁？

答案：

因为：

四个必要条件：

同时：

满足。

问：

如何：

避免？

答案：

破坏：

任意：

一个：

必要条件。

例如：

• 一次申请所有资源（破坏请求并保持）
• 按固定顺序申请资源（破坏循环等待）
• 允许资源被抢占（破坏不可剥夺，注意这种方法并不适用于所有资源）

十三、本课重点（★★★★★）

必须掌握

死锁：

四个必要条件：

哲学家问题：

本质：

多个进程竞争多个资源导致死锁。

解决：

知道：

三种：

经典：

方法。

十四、和上一课联系起来

生产者消费者：

主要：

考：

同步与互斥。

哲学家：

主要：

考：

死锁。

所以：

两道题：

虽然：

都用：

P/V。

但是：

重点：

完全：

不同。