文档介绍：哲学家进餐问题问题描述设有五个哲学家,共用一张放有五把椅子的餐桌,每人坐在一把椅子上,桌子上有五个碗和五只叉子,每人两边各放一只叉子。哲学家们是交替思考和进餐,饥饿时便试图取其左右最靠近他的叉子。(1) 只有拿到两只叉子时,哲学家才能吃饭。(2) 如果叉子已被别人拿走,则必须等别人吃完之后才能拿到叉子。怎样才能保证哲学家不被饿死呢? 摘要:解决“哲学家进餐”问题首先要找出对应的控制关系,设定相应的控制信号量。避免死锁也是解决该类问题的关键。关键词:进程同步;信号量;临界资源;临界区; 死锁算法 A void philosopher(int i) / *i:哲学家编号,从 0 到4* / { while (TRUE) { think( ); / *哲学家正在思考* / take_fork(i); / *取左侧的叉子* / take_fork((i+1) % N); / *取右侧叉子;%为取模运算* / eat( ); / *吃饭* / put_fork(i); / *把左侧叉子放回桌子* / put_fork((i+1) % N); / *把右侧叉子放回桌子* / } } 算法分析: 当出现以下情形,在某一个瞬间,所有的哲学家都同时启动这个算法,拿起左侧的叉子,而看到右侧叉子不可用,又都放下左侧叉子,等一会儿,又同时拿起左侧叉子……如此这样永远重复下去。对于这种情况,所有的哲学家都吃不上饭。算法改善: 至多只允许四个哲学家同时进餐,以保证至少有一个哲学家能够进餐,最终总会释放出他所使用过的两支叉子,从而可使更多的哲学家进餐。改进后的算法 A semaphore fork[5]={1 ,1,1,1, 1}; semaphore room=4; 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); // 退出房间释放信号量 room } } 算法 B 思想规定奇数号的哲学家先拿起他左边的叉子,然后再去拿他右边的叉子;而偶数号的哲学家则相反. 按此规定,将是 1,2 号哲学家竞争 1号叉子,3,4 号哲学家竞争 ,获得后,再去竞争偶数号叉子,最后总会有一个哲学家能获得两支叉子而进餐。而申请不到的哲学家进入阻塞等待队列,根据 FIFO 原则,则先申请的哲学家会较先可以吃饭,因此不会出现饿死的哲学家。