操作系统基础17-哲学家就餐问题

2020-11-13 15:55·重学IT的老猫

哲学家就餐问题(dining-philosophers problem)是一个经典的进程之间的同步互斥问题。该问题是1965年由荷兰学者Dijkstra提出的。

问题描述

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

就餐哲学家的情景

哲学家们倾注毕生精力用于思考和进餐，哲学家在思考时，并不影响他人。只有当哲学家饥饿的时候，才试图拿起左、右两根筷子（一根一根地拿起）。如果筷子已在他人手上，则需等待。饥饿的哲学家只有同时拿到了两根筷子才可以开始进餐，当进餐完毕后，放下筷子继续思考。

问题分析

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

系统中有5个哲学家进程，5位哲学家与左右邻居对其中间筷子的访问是互斥关系。这个问题中只有互斥关系，但与此之前遇到问题的不同处是每个哲学家进程需要同时持有两个临界资源才能开始吃饭。如何避免临界资源分配不当造成死锁现象，是哲学家问题的精髓。

解决方案

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

定义互斥信号量数组为：

semaphore chopstick[5];

对哲学家按0~4编号，哲学家i左边的筷子编号为 i，右边的筷子编号为 (i+1)%5

semaphore chopstick[5] = {1,1,1,1,1};
semaphore mutex = 1;   //互斥的取筷子

哲学家i的进程结构

Pi () {        //i号哲学家进程
    while (1) {
        P(mutex);
        P(chopstick[i]);        //拿左边筷子
        P(chopstick[(i +1) % 5]);//拿右边筷子
        V(mutex);
        吃饭...
        V(chopstick[i]);        //放下左边筷子
        V(chopstick[(i +1) % 5]);//放下右边筷子
        思考...
    }
}

虽然这一解决方案保证两个邻居不能同时进食，但是它可能导致死锁，因此还是应被拒绝的。假若所有 5 个哲学家同时饥饿并拿起左边的筷子。所有筷子的信号量现在均为 0。当每个哲学家试图拿右边的筷子时，他会被永远推迟。

(关于死锁问题后续会有专题详细进行学习)

如何防止死锁的发生？

可以对哲学家进程施加一些限制条件，如最多允许四个哲学家同时进餐。这样可以保证至少有一个哲学家是可以拿到左右两只筷子的。(允许最多 4 个哲学家同时坐在桌子上)
要求奇数号哲学家先拿左边的筷子，然后再拿右边的筷子，而偶数号哲学家则刚好想反。用这种方法可以保证如果相邻的两个奇偶号哲学家都想吃饭，那么只会有其中一个可以拿起第一只筷子，另一个会直接阻塞。这就避免了占有一支后再等待另一支的情况。