哲学家就餐问题
背景:假设5位哲学家住在一起(可以推广到n),每天生活就是思考和吃饭,每位哲学家需要2把叉子来吃意大利面.就餐安排:一张圆桌,5个板凳,5个盘子,5把叉子,每个想吃饭的哲学家做到椅子上,使用盘子2侧的叉子来吃面条,问题: 设计算法保证互斥(2位哲学家不能使用相邻的叉子),同时还要避免死锁(每个哲学家都在等待叉子,且占用了叉子)和饥饿
信号量解决方案
规定:每位哲学家首先拿起左边的叉子,然后拿起右边的叉子semaphore fork[5] = {1};int i;void philosopher (int i) {while (true) {think();wait(fork[i]); //等待左边的叉子wait(fork[(i+1) % 5]; // 等待右边的叉子eat();signal(fork[(i+1) % 5]); // 放回右边的叉子signal(fork[i]; //放回左边的叉子 (增加信号量)}}void mian() {parbegin(philosopher(0),philosopher(1).....philosopher(4)); }
此方案会导致死锁:所有哲学家同时坐下来,都拿起左边的叉子,都去伸手拿右边的叉子,却都没有拿到
对上面死锁危险的解决方案:
再增加5把叉子,哲学家学会只使用一把叉子吃面增加服务员：限制每次最多只能4个哲学家坐下来,那么至少有一个哲学家能够拿到2把叉子增加服务员方案
一个信号量room表示 : 限制每次哲学家同时坐下的数量semaphore fork[5] = {1};semaphore room = 4;int i;void philosopher (int i) {while (true) {think();wait(room);wait(fork[i]);wait(fork[(i+1) % 5]);eat();signal(fork[(i+1) % 5]);signal(fork[i]);signal(room);}}void main() {parbegin(philosopher(0),philosopher(1).....philosopher(4));}
基于管程的解决方案
定义5个管程的条件变量, 每把叉子对应一个条件变量,用来标识哲学家 等待 的叉子可用情况,
开一个
bool数组记录每把叉子是否可用(true/false)管程包含2个过程：
get_forks : 表示取哲学家左右的叉子, 如果至少有1把不可以用,那么在条件变量队列中等待,使得其他哲学家进程进入管程release_forks : 标识2把叉子可用
与信号量方案类似,都是首先拿起左边的叉子,然后拿起右边的叉子
monitor dining_controller; // 声明管程cron ForkReady[5]; // 管程的条件变量bool fork[5] = {true}; // 标记叉子是否可用void get_forks(int pid) {// pid既代表哲学家又代表叉子int left = pid;int right = (pid + 1) % 5;if (!fork[left]) // 左边叉子被使用,则等待条件变量cwait(ForkReady[left]);fork[left] = false;//左边叉子现在可以归我们用了,再次标记为不能用if (!fork[right])cwait(ForkReady[right]);fork[right] = false;}void release_forks(int pid) {int left = pid;int right= (pid + 1) % 5;if (empty(ForkReady[left])) // 没有哲学家在该队列上等待,则该叉子可以使用fork[left] = true;else //如果还有等待,增加信号量csignal(ForkReady[left]);/* 释放右边的叉子 */if (empty(ForkReady[right]))fork[right] = true;elsecsignal(ForkReady[right]);}void philosopher(int i) {while (true) {think();get_forks(i);eat();release_forks(i);}}void main() {parbegin(philosopher(0),philosopher(1).....philosopher(4));}
如果觉得《死锁和饥饿-哲学家就餐问题》对你有帮助，请点赞、收藏，并留下你的观点哦！
