【操作系统】“哲学家进餐”问题

偏执的太偏执、 2022-07-14 12:38 189阅读 0赞

# “哲学家进餐”问题 #

有五个哲学家，他们的生活方式是交替地进行思考和进餐。他们共用一张圆桌，分别坐在五张椅子上。

在圆桌上有五个碗和五支筷子，平时一个哲学家进行思考，饥饿时便试图取用其左、右最靠近他的筷子，只有在他拿到两支筷子时才能进餐。进餐完毕，放下筷子又继续思考。

![图示][SouthEast]

哲学家进餐问题可看作是并发进程并发执行时处理共享资源的一个有代表性的问题。

![图示][SouthEast 1]

此算法可以保证不会有相邻的两位哲学家同时进餐。

若五位哲学家同时饥饿而各自拿起了左边的筷子，这使五个信号量 chopstick 均为 0，当他们试图去拿起右边的筷子时，都将因无筷子而无限期地等待下去，即可能会引起死锁。

# 哲学家进餐问题的改进解法 #

*  方法一：至多只允许四位哲学家同时去拿左筷子，最终能保证至少有一位哲学家能进餐，并在用完后释放两只筷子供他人使用。
 *  方法二：仅当哲学家的左右手筷子都拿起时才允许进餐。
 *  方法三：规定奇数号哲学家先拿左筷子再拿右筷子，而偶数号哲学家相反。

## 方法一 ##

至多只允许四位哲学家同时去拿左筷子，最终能保证至少有一位哲学家能进餐，并在用完后释放两只筷子供他人使用。

设置一个初值为 4 的信号量 r，只允许 4 个哲学家同时去拿左筷子，这样就能保证至少有一个哲学家可以就餐，不会出现饿死和死锁的现象。

原理：至多只允许四个哲学家同时进餐，以保证至少有一个哲学家能够进餐，最终总会释放出他所使用过的两支筷子，从而可使更多的哲学家进餐。

![图示][SouthEast 2]

## 方法二 ##

仅当哲学家的左右手筷子都拿起时才允许进餐。

解法 1：利用 AND 型信号量机制实现。

原理：多个临界资源，要么全部分配，要么一个都不分配，因此不会出现死锁的情形。

![图示][SouthEast 3]

解法 2：利用信号量的保护机制实现。

原理：通过互斥信号量 mutex 对 eat() 之前取左侧和右侧筷子的操作进行保护，可以防止死锁的出现。

![图示][SouthEast 4]

## 方法三 ##

规定奇数号哲学家先拿左筷子再拿右筷子，而偶数号哲学家相反。

原理：按照下图，将是 2,3 号哲学家竞争 3 号筷子，4,5 号哲学家竞争 5 号筷子。1 号哲学家不需要竞争。最后总会有一个哲学家能获得两支筷子而进餐。

![图示][SouthEast 5]

![图示][SouthEast 6]

[SouthEast]: /images/20220714/af85915296794a5285dd940041322169.png
[SouthEast 1]: /images/20220714/eb2ade81b08a44919c8be05c5cb85603.png
[SouthEast 2]: /images/20220714/40f3204877eb4af393e5e051fb0cdfb4.png
[SouthEast 3]: /images/20220714/dc84c345e8ac46469782c915c670dd78.png
[SouthEast 4]: /images/20220714/cfd66193f936477c88587a335aa91ab6.png
[SouthEast 5]: /images/20220714/8e0642305d4f46849bba8a13e114f8a0.png
[SouthEast 6]: /images/20220714/9e0cf76989704ac68f96ec14c78ea8ec.png