1、哲学家进餐问题,林州，周甜，熊元元，张萍，田蝶，陈昊雯，赵建旭,1.问题描述,有五位哲学家，他们的生活方式是交替地进行思考和进餐。哲学家们共用一张圆桌，分别坐在周围的五张椅子上，在圆桌上有五个碗和五只筷子，平时一个哲学家进行思考，饥饿时便试图取用其左、右最靠近他的筷子，只有在他拿到两支筷子时才能进餐，进餐毕，放下筷子又继续思考。,从上图可知，筷子是临界资源，用一个信号量来表示一支筷子，可以用记录型信号量来描述，初值均为1：,在以上的描述中，哲学家饥饿时总是拿左边的筷子chopsticki，再去拿右边的筷子chopsticki+1 mod 5，虽然上述解法可以保证不会有两个相邻的哲学家同时进餐，
2、但是会引起死锁，假如五个哲学家同时饥饿而各自拿起左边的筷子时会使五个信号量chopstick均为0，当他们试图去拿右边的筷子时，因无法拿到筷子而无限期等待。对此类的死锁问题可以采用下面的几种解决方法：1、至多只允许四个哲学家同时用餐，以保证至少有一个哲学家能够进餐，最终总会释放他所使用的两支筷子，从而可使更多的哲学家进餐。2、仅当哲学家的左、右筷子均可用时，才允许他拿起筷子进餐。3、规定按奇数号哲学家先拿左边的筷子，然后再拿右边的筷子，偶数相反。,(1) 在什么情况下5 个哲学家全部吃不上饭？,分析：假如所有的哲学家都同时拿起左侧筷子，看到右侧筷子不可用，又都放下左侧筷子，等一会儿，又同时拿起
3、左侧筷子，如此这般，永远重复。对于这种情况，即所有的程序都在无限期地运行，但是都无法取得任何进展，即出现饥饿，所有哲学家都吃不上饭。 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); /*把右侧筷子放回桌子*/ ,(2) 描述一种没有人饿死（永远拿
4、不到筷子）算法。,A.原理： 至多只允许四个哲学家同时进餐,以保证至少有一个哲学家能够进餐,最终总会释放出他所使用过的两支筷子,从而可使更多的哲学家进餐。以下将room 作为信号量，只允许4 个哲学家同时进入餐厅就餐，这样就能保证至少有一个哲学家可以就餐，而申请进入餐厅的哲学家进入room 的等待队列，根据FIFO 的原则，总会进入到餐厅就餐，因此不会出现饿死和死锁的现象。伪码：semaphore chopstick5=1，1，1，1，1;semaphore room=4;void philosopher(int i)while(true)think(); wait(room); /请求进入房
5、间进餐 wait(chopsticki); /请求左手边的筷子 wait(chopstick(i+1)%5); /请求右手边的筷子 eat(); signal(chopstick(i+1)%5); /释放右手边的筷子 signal(chopsticki); /释放左手边的筷子 signal(room); /退出房间释放信号量room,B原理： 仅当哲学家的左右两支筷子都可用时,才允许他拿起筷子进餐。 利用AND 型信号量机制实现：根据课程讲述，在一个原语中，将一段代码同时需要的多个临界资源，要么全部分配给它，要么一个都不分配，因此不会出现死锁的情形。当某些资源不够时阻塞调用进程;由于等待队列的
6、存在，使得对资源的请求满足FIFO 的要求，因此不会出现饥饿的情形。 伪码：semaphore chopstick5=1，1，1，1，1;void philosopher(int I)while(true)think(); Swait(chopstick(I+1)%5,chopstickI); eat(); Ssignal(chopstick(I+1)%5,chopstickI);,C 原理： 规定奇数号的哲学家先拿起他左边的筷子,然后再去拿他右边的筷子;而偶数号的哲学家则相反.按此规定,将是1,2号哲学家竞争1号筷子,3,4号哲学家竞争3号筷子.即五个哲学家都竞争奇数号筷子,获得后,再去竞争
7、偶数号筷子,最后总会有一个哲学家能获得两支筷子而进餐。而申请不到的哲学家进入阻塞等待队列，根FIFO原则，则先申请的哲学家会较先可以吃饭，因此不会出现饿死的哲学家。伪码：semaphore chopstick5=1，1，1，1，1;void philosopher(int i)while(true)think(); if(i%2 = 0) /偶数哲学家，先右后左。wait (chopstick i + 1 mod 5) ; wait (chopstick i) ; eat(); signal (chopstick i + 1 mod 5) ; signal (chopstick i) ;Else /奇数哲学家，先左后右。wait (chopstick i) ; wait (chopstick i + 1 mod 5) ; eat(); signal (chopstick i) ; signal (chopstick i + 1 mod 5) ;,thank you!,林州，周甜，熊元元，张萍，田蝶，陈昊雯，赵建旭,
