设有个哲学家共享一张放油把椅子的桌子每人分得一吧椅子但是桌子上总共执友支筷子在每个人两边分开各放一支哲学家只有在肚子饑饿时才试图分两次从两边拾起筷子就餐
就餐条件是:
)哲学家想吃饭时先提出吃饭的要求;
)提出吃饭要求并拿到支筷子后方可吃饭;
)如果筷子已被他人获得则必须等待该人吃完饭之后才能获取该筷子;
)任一哲学家在自己未拿到支筷子吃饭之前决不放下手中的筷子;
)刚开始就餐时只允许个哲学家请求吃饭
试问:
)描述一个保证不会出现两个邻座同时要求吃饭的算法;
)描述一个既没有两邻座同时吃饭又没有人饿死的算法;
)在什么情况下个哲学家全都吃不上饭?
哲学家进餐问题是典型的同步问题它是由Dijkstra提出并解决的该问题是描述有五个哲学家他们的生活方式是交替地进行思考和进餐哲学家们共用一张圆桌分别坐在周围的五张椅子上在圆桌上有五个碗和五支筷子平时一个哲学家进行思考饑饿时便试图取用其左右岁靠近他的筷子只有在他拿到两支筷子时才能进餐进餐完毕放下筷子继续思考
利用记录型信号量解决哲学家进餐问题
经分析可知筷子是临界资源在一段时间只允许一个哲学家使用因此可以用一个信号量表示一支筷子由这五个信号量构成信号量数组其描述如下:
var chopstick:array[]of semaphore;
所有信号量被初始化为第i个哲学家的活动可描述为:
repeat
wait(chopstick);
wait(chopstick[(i+) mod ]);
eat;
signal(chopstick);
signal(chopstick[(i+) mod ]);
think;
until false;
在以上描述中哲学家饑饿时总是先去拿他左边的筷子即执行wait(chopstick);成功后再去拿他右边的筷子即执行wait(chopstick[(i+) mod ]);再成功后便可进餐进餐完毕又先放下他左边的筷子然后放下他右边的筷子虽然上述解法可保证不会有两个相临的哲学家同时进餐但引起死锁是可能的假如五个哲学家同时饑饿而各自拿起右边的筷子时就会使五个信号量chopstick均为;当他们试图去拿右边的筷子时都将因无筷子可拿而无限期地等待对于这样的死锁问题可采用以下集中解决方法:
()至多只允许四个哲学家同时进餐以保证至少有一个哲学家能够进餐最终总会释放出他所使用过的两支筷子从而可使更多的哲学家进餐
()仅当哲学家的左右两支筷子都可用时才允许他拿起筷子进餐
()规定奇数号的哲学家先拿起他左边的筷子然后再去拿他右边的筷子;而偶数号的哲学家则相反按此规定将是号哲学家竞争号筷子号哲学家竞争号筷子即五个哲学家都竞争奇数号筷子获得后再去竞争偶数号筷子最后总会有一个哲学家能获得两支筷子而进餐
看了整整一个上午的操作系统看得头都大了
我们老师的算法的大意好像是用一个总的信号量只有获得信号量的哲学家才可以拿筷子
具体算法如下（用类c描述）
#include 所有头文件
#define N
#define left (i)%N //i的左邻号码
#define right (i+)%N //i的右邻号码
#define think
#define hungry
#define eating
typedef int semaphore //信号量是一个特殊的整型变量
int state[N] //记录每个人的状态
semaphore mutex=; //设置信号量
semaphore s[N]; //每个哲学家一个信号量
void philosopher(int i)
{
while(true) //无限循环
{
think;
take_chopstick(i);
eat;
put_chopstick(i);
}
}
void take_chopstick(int i)
{
p(& mutex); //对信号量的p操作
state=hungry;
test(i); //试图得到两支筷子
v(&mutex); //v操作
p(&s); //得不到筷子则阻塞
}
void put_chopstick(int i)
{
p(& mutex);
state=think; //进餐结束
test(left); //看左邻是否进餐
test(right); //再看右邻
v(&mutex);
}
void test(int i)
{
if（state==hungry&&左邻没进餐&&右邻没进餐）
{
state=eating;
v(&s);
}
}
