設有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);
}
}
*
