哲学家进餐问题
问题描述
5个哲学家以交替思考、进餐的方式生活， 他们坐在一张圆桌旁，桌 子上有 5 个碗和 5 只筷子。当一个哲学家思考时，他与相邻的两个哲学家不会相互影响；但当他进餐时，需同时获得最靠近他的左右两只筷子，若其中一只筷子被相邻的哲学家拿走，他就必须等待。
问题分析
将哲学家看作进程，将筷子看作资源；经过分析可知，放在桌子上的筷子是临界资源，在一段时间内只允许一位哲学家使用。为了实现对筷子的互斥使用，可以用一个信号量表示一根筷子，由着五根筷子对应的五个信号量构成信号量数组，便可实现互斥访问
semaphone chopstick[5] = {1, 1, 1, 1, 1};
记录型信号量
代码实现
semaphone chopstick[5] = {1, 1, 1, 1, 1}; void philosopher(int i){ do{ wait(chopstick[i]); wait(chopstick[(i + 1) % 5]); …… eat; …… signal(chopstick[(i + 1) % 5]); signal(chopstick[i]); …… think; …… }while(TRUE); }
死锁问题
- 问题出现：
在上述的代码中，每次哲学家都是先wait(chopstick[i])：拿左边的筷子，随后wait(chopstick[(i + 1) % 5])：拿右边的筷子。但是如果五个哲学家的进程在并发的过程中全部一起执行了wait(chopstick[i])，那么此时信号量chopstick将全部为0，进程陷入死锁状态 - 解决思路：
- 至多只允许 4 个哲学家同时进餐。
semaphone chopstick[5] = {1, 1, 1, 1, 1}; semaphone count = 4 void philosopher(int i){ do{ wait(count); wait(chopstick[i]); wait(chopstick[(i + 1) % 5]); …… eat; …… signal(chopstick[(i + 1) % 5]); signal(chopstick[i]); signal(count); …… think; …… }while(TRUE); }
- 仅当哲学家左右两边的筷子都可用时， 才允许他进餐。
此处的思想便是接下来的AND信号量的实现方法 - 规定奇数号哲学家先拿左边的筷子， 再拿右边的筷子 ； 而偶数号哲学家则先拿右边的筷子，再拿左边的筷子。
semaphone chopstick[5] = {1, 1, 1, 1, 1}; void philosopher(int i){ do{ if(i % 2 != 0){ wait(chopstick[i]); wait(chopstick[(i + 1) % 5]); …… eat; …… signal(chopstick[(i + 1) % 5]); signal(chopstick[i]); }else{ wait(chopstick[(i + 1) % 5]); wait(chopstick[i]); …… eat; …… signal(chopstick[i]); signal(chopstick[(i + 1) % 5]); } …… think; …… }while(TRUE); }
AND信号量
实现思路
仅当哲学家左右两边的筷子都可用时， 才允许他进餐
代码实现
semaphone chopstick[5] = {1, 1, 1, 1, 1}; void philosopher(int i){ do{ Swait(chopstick[i], chopstick[(i + 1) % 5]) …… eat; …… Ssignal(chopstick[i], chopstick[(i + 1) % 5]); …… think; …… }while(TRUE); }
