哲学家进餐问题

哲学家进餐问题 作者：未知 文章来源：互联网 点击数： 22 更新时间：2008-10-26 1． 哲学家进餐问题： (1) 在什么情况下5 个哲学家全部吃不上饭？ 考虑两种实现的方式，如下： 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); /*把右侧筷子放回桌子*/ } } 分析：假如所有的哲学家都同时拿起左侧筷子，看到右侧筷子不可用，又都放下左侧筷子， 等一会儿，又同时拿起左侧筷子，如此这般，永远重复。对于这种情况，即所有的程序都在 无限期地运行，但是都无法取得任何进展，即出现饥饿，所有哲学家都吃不上饭。 B． 算法描述： 规定在拿到左侧的筷子后，先检查右面的筷子是否可用。如果不可用，则先放下左侧筷子， 等一段时间再重复整个过程。 分析：当出现以下情形，在某一个瞬间，所有的哲学家都同时启动这个算法，拿起左侧的筷 子，而看到右侧筷子不可用，又都放下左侧筷子，等一会儿，又同时拿起左侧筷子……如此 这样永远重复下去。对于这种情况，所有的程序都在运行，但却无法取得进展，即出现饥饿， 所有的哲学家都吃不上饭。 (2) 描述一种没有人饿死（永远拿不到筷子）算法。 考虑了四种实现的方式（A、B、C、D）： A．原理：至多只允许四个哲学家同时进餐,以保证至少有一个哲学家能够进餐,最终总会释 放出他所使用过的两支筷子,从而可使更多的哲学家进餐。以下将room 作为信号量，只允 许4 个哲学家同时进入餐厅就餐，这样就能保证至少有一个哲学家可以就餐，而申请进入 餐厅的哲学家进入room 的等待队列，根据FIFO 的原则，总会进入到餐厅就餐，因此不会 出现饿死和死锁的现象。 伪码： semaphore chopstick[5]={1，1，1，1，1}; semaphore room=4; void philosopher(int i) { while(true) { think(); wait(room); //请求进入房间进餐 wait(chopstick[i]); //请求左手边的筷子 wait(chopstick[(i+1)%5]); //请求右手边的筷子 eat(); signal(chopstick[(i+1)%5]); //释放右手边的筷子 signal(chopstick[i]); //释放左手边的筷子 signal(room); //退出房间释放信号量room } } B．原理：仅当哲学家的左右两支筷子都可用时,才允许他拿起筷子进餐。 方法1：利用AND 型信号量机制实现：根据课程讲述，在一个原语中，将一段代码同时需 要的多个临界资源，要么全部分配给它，要么一个都不分配，因此不会出现死锁的情形。当 某些资源不够时阻塞调用进程;由于等待队列 的存在，使得对资源的请求满足FIFO 的， 因此不会出现饥饿的情形。 伪码： semaphore chopstick[5]={1，1，1，1，1}; void philosopher(int I) { while(true) { think(); Swait(chopstick[(I+1)]%5,chopstick[I]); eat(); Ssignal(chopstick[(I+1)]%5,chopstick[I]); } } 方法2：利用信号量的保护机制实现。通过信号量mutex对eat（）之前的取左侧和右侧筷 子的操作进行保护，使之成为一个原子操作，这样可以防止死锁的出现。 伪码： semaphore mutex = 1 ; semaphore chopstick[5]={1，1，1，1，1}; void philosopher(int I) { while(true) { think(); wait(mutex); wait(chopstick[(I+1)]%5); wait(chopstick[I]); signal(mutex); eat(); signal(chopstick[(I+1)]%5); signal(chopstick[I]); } } C． 原理：规定奇数号的哲学家先拿起他左边的筷子,然后再去拿他右边的筷子;而偶数号 的哲学家则相反.按此规定,将是1,2号哲学家竞争1号筷子,3,4号哲学家竞争3号筷子.即 五个哲学家都竞争奇数号筷子,获得后,再去竞争偶数号筷子,最后总会有一个哲学家能获 得两支筷子而进餐。而申请不到的哲学家进入阻塞等待队列，根FIFO原则，则先申请的哲 学家会较先可以吃饭，因此不会出现饿死的哲学家。 伪码： semaphore chopstick[5]={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) ; } } D．利用管程机制实现（最终该实现是失败的，见以下分析）： 原理：不是对每只筷子设置信号量，而是对每个哲学家设置信号量。test()函数有以下作 用： a. 如果当前处理的哲学家处于饥饿状态且两侧哲学家不在吃饭状态，则当前哲学家通过 test()函数试图进入吃饭状态。 b. 如果通过test()进入吃饭状态不成功，那么当前哲学家就在该信号量阻塞等待，直到 其他的哲学家进程通过test()将该哲学家的状态设置为EATING。 c. 当一个哲学家进程调用put_forks()放下筷子的时候，会通过test()测试它的邻居， 如果邻居处于饥饿状态，且该邻居的邻居不在吃饭状态，则该邻居进入吃饭状态。 由上所述,该算法不会出现死锁，因为一个哲学家只有在两个邻座都不在进餐时，才允 许转换到进餐状态。 该算法会出现某个哲学家适终无法吃饭的情况，即当该哲学家的左右两个哲学家交替 处在吃饭的状态的时候，则该哲学家始终无法进入吃饭的状态，因此不满足题目的要求。 但是该算法能够实现对于任意多位哲学家的情况都能获得最大的并行度，因此具有重要 的意义。 伪码： #define N 5 /* 哲学家人数*/ #define LEFT (i-1+N)%N /* i的左邻号码 */ #define RIGHT (i+1)%N /* i的右邻号码 */ typedef enum { THINKING, HUNGRY, EATING } phil_state; /*哲学家状态*/ monitor dp /*管程*/ { phil_state state[N]; semaphore mutex =1; semaphore s[N]; /*每个哲学家一个信号量，初始值为0*/ void test(int i) { if ( state[i] == HUNGRY &&state[LEFT(i)] != EATING && state[RIGHT(i)] != EATING ) { state[i] = EATING; V(s[i]); } } void get_forks(int i) { P(mutex); state[i] = HUNGRY; test(i); /*试图得到两支筷子*/ V(mutex); P(s[i]); /*得不到筷子则阻塞*/ } void put_forks(int i) { P(mutex); state[i]= THINKING; test(LEFT(i)); /*看左邻是否进餐*/ test(RIGHT(i)); /*看右邻是否进餐*/ V(mutex); } } 哲学家进程如下： void philosopher(int process) { while(true) { think(); get_forks(process); eat(); put_forks(process); } }