哲学家就餐问题

哲学家就餐问题(Dining Philosophers Problem)是由艾兹赫尔·迪杰斯特拉(Edsger Dijkstra)提出的一个经典并发编程问题,用于说明在多个进程共享有限资源时,如何避免死锁和饥饿,是操作系统同步理论的代表性案例。

概述

问题设定为:五位哲学家围坐圆桌,每人面前有一盘意面,相邻两人之间共放一支餐叉,总共五支。哲学家在思考与进餐之间交替,进餐时必须同时拿起左右两支餐叉,吃完后放下。由于每支餐叉被两人共享,若所有人同时拿起左手边的餐叉并等待右手边的,就会陷入谁也无法进餐的僵局,即死锁。

核心原理

• 资源竞争:餐叉是共享资源,哲学家需同时获得两个相邻资源才能工作。
• 死锁:所有哲学家各持一叉互相等待,形成循环等待,导致全体阻塞。
• 饥饿:某些哲学家可能因始终抢不到餐叉而长期无法进餐。
• 解决思路:限制同时就餐人数、规定拿叉顺序打破循环、引入服务生仲裁、或用信号量协调。

应用场景

该问题是操作系统与并发编程课程的必讲内容,用来演示信号量、互斥锁的使用以及死锁的四个必要条件。它的抽象模型对应现实中许多资源竞争场景,如多线程争抢多把锁、数据库事务争抢多条记录的行锁等。理解并解决它,有助于设计出既不死锁又不饥饿、还能保持较高并发度的同步方案。

常见问题

问:如何用最简单的方式避免死锁?答:一种经典办法是给餐叉编号,规定所有哲学家都先拿编号较小的餐叉,这样打破了循环等待条件,从而避免死锁。

问:避免死锁后就没问题了吗?答:不一定,还需防止饥饿,即保证每个哲学家最终都能进餐,好的方案要同时兼顾无死锁、无饥饿和较高的并发效率。