用C語言實現哲學家進餐的問題

設有5個哲學家,共享一張放油把椅子的桌子,每人分得一吧椅子.但是桌子上總共執友支筷子,在每個人兩邊分開各放一支.哲學家只有在肚子饑餓時才試圖分兩次從兩邊拾起筷子就餐.

就餐條件是:

1)哲學家想吃飯時,先提出吃飯的要求;

2)提出吃飯要求,并拿到支筷子后,方可吃飯;

3)如果筷子已被他人獲得,則必須等待該人吃完飯之后才能獲取該筷子;

4)任一哲學家在自己未拿到2支筷子吃飯之前,決不放下手中的筷子;

5)剛開始就餐時,只允許2個哲學家請求吃飯.

試問:

1)描述一個保證不會出現兩個鄰座同時要求吃飯的算法;

2)描述一個既沒有兩鄰座同時吃飯,又沒有人餓死的算法;

3)在什么情況下,5個哲學家全都吃不上飯?

哲學家進餐問題是典型的同步問題.它是由Dijkstra提出并解決的.該問題是描述有五個哲學家,他們的生活方式是交替地進行思考和進餐.哲學家們共用一張圓桌,分別坐在周圍的五張椅子上.在圓桌上有五個碗和五支筷子,平時一個哲學家進行思考,饑餓時便試圖取用其左右歲靠近他的筷子,只有在他拿到兩支筷子時才能進餐.進餐完畢,放下筷子繼續思考.

利用記錄型信號量解決哲學家進餐問題

經分析可知,筷子是臨界資源,在一段時間只允許一個哲學家使用.因此,可以用一個信號量表示一支筷子,由這五個信號量構成信號量數組.其描述如下:

var chopstick:array[0,...,4]of semaphore;

所有信號量被初始化為1,第i個哲學家的活動可描述為:

repeat

wait(chopstick);

wait(chopstick[(i+1) mod 5]);

...

eat;

...

signal(chopstick);

signal(chopstick[(i+1) mod 5]);

...

think;

until false;

在以上描述中,哲學家饑餓時,總是先去拿他左邊的筷子,即執行wait(chopstick);成功后,再去拿他右邊的筷子,即執行wait(chopstick[(i+1) mod 5]);,再成功后便可進餐.進餐完畢,又先放下他左邊的筷子,然后放下他右邊的筷子.雖然,上述解法可保證不會有兩個相臨的哲學家同時進餐,但引起死鎖是可能的.假如五個哲學家同時饑餓而各自拿起右邊的筷子時,就會使五個信號量chopstick均為0;當他們試圖去拿右邊的筷子時,都將因無筷子可拿而無限期地等待.對于這樣的死鎖問題可采用以下集中解決方法:

(1)至多只允許四個哲學家同時進餐,以保證至少有一個哲學家能夠進餐,最終總會釋放出他所使用過的兩支筷子,從而可使更多的哲學家進餐.

(2)僅當哲學家的左右兩支筷子都可用時,才允許他拿起筷子進餐.

(3)規定奇數號的哲學家先拿起他左邊的筷子,然后再去拿他右邊的筷子;而偶數號的哲學家則相反.按此規定,將是1,2號哲學家競爭1號筷子,3,4號哲學家競爭3號筷子.即五個哲學家都競爭奇數號筷子,獲得后,再去競爭偶數號筷子,最后總會有一個哲學家能獲得兩支筷子而進餐.

看了整整一個上午的操作系統，看得頭都大了。

我們老師的算法的大意好像是用一個總的信號量，只有獲得信號量的哲學家才可以拿筷子。

具體算法如下(用類c描述)：

#include "所有頭文件"

#define N 5

#define left (i-1)%N //i的左鄰號碼

#define right (i+1)%N //i的右鄰號碼

#define think 0

#define hungry 1

#define eating 2

typedef int semaphore //信號量是一個特殊的整型變量

int state[N] //記錄每個人的狀態

semaphore mutex=1; //設置信號量

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);

}

}