您当前的位置:首页 > 计算机 > 系统应用 > 操作系统

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

时间:03-07来源:作者:点击数:

假设有 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。当每个哲学家试图拿右边的筷子时,他会被永远推迟。

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

  • 允许最多 4 个哲学家同时坐在桌子上。
  • 只有一个哲学家的两根筷子都可用时,他才能拿起它们(他必须在临界区内拿起两根 辕子)。
  • 使用非对称解决方案。即单号的哲学家先拿起左边的筷子,接着右边的筷子;而双 号的哲学家先拿起右边的筷子,接着左边的筷子。
方便获取更多学习、工作、生活信息请关注本站微信公众号城东书院 微信服务号城东书院 微信订阅号
推荐内容
相关内容
栏目更新
栏目热门