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

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

　　就餐條件是:

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

　　)提出吃飯要求並拿到支筷子後方可吃飯;

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

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

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

　　試問:

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

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

　　)在什麼情況下個哲學家全都吃不上飯?

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

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

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

　　var chopstick:array[]of semaphore;

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

　　repeat

　　wait(chopstick);

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

　　

　　eat;

　　

　　signal(chopstick);

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

　　

　　think;

　　until false;

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

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

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

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

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

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

　　具體算法如下（用類c描述）

　　#include 所有頭文件

　　#define N

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

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

　　#define think

　　#define hungry

　　#define eating

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

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

　　semaphore mutex=; //設置信號量

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

　　}

　　}

From:http://tw.wingwit.com/Article/program/c/201404/30443.html