首页 > 编程笔记 > 操作系统笔记 阅读:4,871

哲学家就餐问题分析(含解决方案)

假设有 5 个哲学家,他们的生活只是思考和吃饭。这些哲学家共用一个圆桌,每位都有一把椅子。在桌子中央有一碗米饭,在桌子上放着 5 根筷子(图 1 )。


图 1 就餐哲学家的情景

当一位哲学家思考时,他与其他同事不交流。时而,他会感到饥饿,并试图拿起与他相近的两根筷子(筷子在他和他的左或右邻居之间)。一个哲学家一次只能拿起一根筷子。显然,他不能从其他哲学家手里拿走筷子。当一个饥饿的哲学家同时拥有两根筷子时,他就能吃。在吃完后,他会放下两根筷子,并开始思考。

哲学家就餐问题是一个经典的同步问题,这不是因为其本身的实际重要性,也不是因为计算机科学家不喜欢哲学家,而是因为它是大量并发控制问题的一个例子。这个代表型的例子满足:在多个进程之间分配多个资源,而且不会出现死锁和饥饿。

一种简单的解决方法是每只筷子都用一个信号量来表示。一个哲学家通过执行操作 wait() 试图获取相应的筷子,他会通过执行操作 signal() 以释放相应的筷子。

因此,共享数据为:

semaphore chopstick[5];

其中,chopstick 的所有元素都初始化为 1。哲学家 i 的结构如下所示:
do {
    wait(chopstick[i]);
    wait(chopstick[(i+1) % 5]);
    /* eat for awhile */
    signal(chopstick[i]);
    signal(chopstick[(i+1) % 5]);
    /* think for awhile */
} while (true);
虽然这一解决方案保证两个邻居不能同时进食,但是它可能导致死锁,因此还是应被拒绝的。假若所有 5 个哲学家同时饥饿并拿起左边的筷子。所有筷子的信号量现在均为 0。当每个哲学家试图拿右边的筷子时,他会被永远推迟。

死锁问题有多种可能的补救措施:

所有教程

优秀文章