哲学家进餐问题(操作系统)ppt课件.ppt

哲学家进餐问题,主讲人：次仁桑珠,问题描述,设有五个哲学家,共用一张放有五把椅子的餐桌,每人坐在一把椅子上,桌子上有五个碗和五只筷子,每人两边各放一只筷子。哲学家们是交替思考和进餐,饥饿时便试图取其左右最靠近他的筷子。,(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 fork5=1，1，1，1，1; semaphore room=4; void philosopher(int i) while(true) think(); wait(room); /请求进入房间进餐 wait(forki); /请求左手边的筷子wait(fork(i+1)%5); /请求右手边的筷子eat(); signal(fork(i+1)%5); /释放右手边的筷子signal(forki); /释放左手边的筷子signal(room); /退出房间释放信号量room ,算法 B 思想,规定奇数号的哲学家先拿起他左边的筷子,然后再去拿他右边的筷子;而偶数号的哲学家则相反.按此规定,将是1,2号哲学家竞争1号筷子,3,4号哲学家竞争3号筷子.即五个哲学家都竞争奇数号筷子,获得后,再去竞争偶数号筷子,最后总会有一个哲学家能获得两支筷子而进餐。而申请不到的哲学家进入阻塞等待队列，根据FIFO原则，则先申请的哲学家会较先可以吃饭，因此不会出现饿死的哲学家。,semaphore fork5=1，1，1，1，1; void philosopher(int i) while(true) think(); if(i%2 = 0) /偶数哲学家，先右后左。 wait (fork i + 1 mod 5) ; wait (fork i) ; eat(); signal (fork i + 1 mod 5) ; signal (fork i) ; Else /奇数哲学家，先左后右。 wait (fork i) ; wait (fork i + 1 mod 5) ; eat(); signal (fork i) ; signal (fork i + 1 mod 5) ; ,综上所述,解决这一类问题的关键是找出对应的控制关系,设定相应的控制信号量。另外,产生死锁是在用信号量进行流程控制过程中常会遇到的一个问题,因此如何避免死锁就是解决该类问题的关键。,Thank you!,