哲學家就餐問題c語言

1. 用c語言實現哲學家進餐的問題

100分就想拿下，太難了。

2. 哲學家進餐問題（在計算機操作系統方面的相關編程）

操作系統並發和互斥：哲學家進餐問題和理發師問題

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);
}
}
2.理發師問題：一個理發店有一個入口和一個出口。理發店內有一個可站5 位顧客的站席
區、4 個單人沙發、3 個理發師及其專用理發工具、一個收銀台。新來的顧客坐在沙發上等
待；沒有空沙發時，可在站席區等待；站席區滿時，只能在入口外等待。理發師可從事理
發、收銀和休息三種活動。理發店的活動滿足下列條件：
1）休息的理發師是坐地自己專用的理發椅上，不會佔用顧客的沙發；
2）處理休息狀態的理發師可為在沙發上等待時間最長的顧客理發；
3）理發時間長短由理發師決定；
4）在站席區等待時間最長的顧客可坐到空閑的理發上；
5）任何時刻最多隻能有一個理發師在收銀。
試用信號量機制或管程機制實現理發師進程和顧客進程。
原理：
(1)customer 進程：
首先檢查站席區是否已滿（stand_capacity）,若滿選擇離開，否則進入站席區，即進入
理發店。在站席區等待沙發的空位（信號量sofa），如果沙發已滿，則進入阻塞等待隊列，
直到出現空位，在站席區中等待時間最長的顧客離開站席區（stand_capacity）。坐到沙
發上，等待理發椅(barber_chair)，如果理發椅已滿，則進入阻塞等待隊列，直到出現
空位，在沙發上等待時間最長的顧客離開沙發（釋放信號量sofa）。坐到理發椅上，釋放
准備好的信號（customer_ready），獲得該理發師的編號（0~1 的數字）。等待理發師理
發結束（finished[barber_number]）。在離開理發椅之前付款（payment），等待收據
(receipt)，離開理發椅（leave_barberchair）。最後離開理發店。
這里需要注意幾點：
a) 首先是幾個需要進行互斥處理的地方，主要包括:進入站席區、進入沙發、進入理發椅
和付款幾個地方。
b) 通過barber_chair 保證一個理發椅上最多隻有一名顧客。但這也不夠，因為單憑
baber_chair 無法保證一名顧客離開理發椅之前，另一位顧客不會坐到該理發椅上，
因此增加信號量leave_barberchair，讓顧客離開理發椅後，釋放該信號，而理發
師接收到該信號後才釋放barber_chair 等待下一位顧客。
c) 在理發的過程中，需要保證是自己理發完畢，才能夠進行下面的付款、離開理發椅的活
動。這個機制是通過customer 進程獲得給他理發的理發師編號來實現的，這樣，當
該編號的理發師釋放對應的finished[i]信號的時候，該顧客才理發完畢。
d) 理發師是通過mutex 信號量保證他們每個人同時只進行一項操作（理發或者收款）。
e) 為了保證該顧客理發完畢後馬上可以付款離開，就應該保證給該顧客理發的理發師在理
發完畢後馬上到收銀台進入收款操作而不是給下一位顧客服務。在偽碼中由以下機制實
現：即顧客在釋放離開理發椅的信號前，發出付款的信號。這樣該理發師得不到顧客的
離開理發椅的信號，不能進入下一個循環為下一名顧客服務，而只能進入收款台的收款
操作。直到顧客接到收據後，才釋放離開理發椅的信號，離開理發椅，讓理發師釋放該
理發椅的信號，讓下一位等待的顧客坐到理發椅上。
(2)barber 進程
首先將該理發師的編號壓入隊列，供顧客提取。等待顧客坐到理發椅坐好(信號量
customer_ready)，開始理發，理發結束後釋放結束信號（finished[i]）。等待顧客
離開理發椅（leave_barberchair）（期間去收銀台進行收款活動），釋放理發椅空閑信
號(barber_chair)，等待下一位顧客坐上來。
(3)cash（收銀台）進程
等待顧客付款(payment),執行收款操作，收款操作結束，給付收據（receipt）。
信號量總表：
信號量 wait signal
stand_capacity 顧客等待進入理發店 顧客離開站席區
sofa 顧客等待坐到沙發 顧客離開沙發
barber_chair 顧客等待空理發椅 理發師釋放空理發椅
customer_ready 理發師等待，直到一個顧客坐
到理發椅
顧客坐到理發椅上，給理發師
發出信號
mutex 等待理發師空閑，執行理發或
收款操作
理發師執行理發或收款結束，
進入空閑狀態
mutex1 執行入隊或出隊等待 入隊或出隊結束，釋放信號
finished[i] 顧客等待對應編號理發師理
發結束
理發師理發結束，釋放信號
leave_barberchair 理發師等待顧客離開理發椅 顧客付款完畢得到收據，離開
理發椅釋放信號
payment 收銀員等待顧客付款 顧客付款，發出信號
receipt 顧客等待收銀員收、開具收據收銀員收款結束、開具收據，
釋放信號
偽碼：
semaphore stand_capacity=5;
semaphore sofa=4;
semaphore barber_chair=3;
semaphore customer_ready=0;
semaphore mutex=3;
semaphore mutex1=1;
semaphore finished[3]={0,0,0};
semaphore leave_barberchair=0;
semaphore payment=0;
semaphore receipt=0;
void customer()
{
int barber_number;
wait(stand_capacity); //等待進入理發店
enter_room(); //進入理發店
wait(sofa); //等待沙發
leave_stand_section(); //離開站席區
signal(stand_capacity);
sit_on_sofa(); //坐在沙發上
wait(barber_chair); //等待理發椅
get_up_sofa(); //離開沙發
signal(sofa);
wait(mutex1);
sit_on_barberchair(); //坐到理發椅上
signal(customer_ready);
barber_number=dequeue(); //得到理發師編號
signal(mutex1);
wait(finished[barber_number]); //等待理發結束
pay(); //付款
signal(payment); //付款
wait(receipt); //等待收據
get_up_barberchair(); //離開理發椅
signal(leave_barberchair); //發出離開理發椅信號
exit_shop(); //了離開理發店
}
void barber(int i)
{
while(true)
{
wait(mutex1);
enqueue(i); //將該理發師的編號加入隊列
signal(mutex1);
wait(customer_ready); //等待顧客准備好
wait(mutex);
cut_hair(); //理發
signal(mutex);
signal(finished[i]); //理發結束
wait(leave_barberchair); //等待顧客離開理發椅信號
signal(barber_chair); //釋放barber_chair 信號
}
}
void cash() //收銀
{
while(true)
{
wait(payment); //等待顧客付款
wait(mutex); //原子操作
get_pay(); //接受付款
give_receipt(); //給顧客收據
signal(mutex);
signal(receipt); //收銀完畢，釋放信號
}
}
分析：
在分析該問題過程中，出現若干問題，是參閱相關資料後才認識到這些問題的隱蔽性和嚴重
性的,主要包括：
（1）在顧客進程，如果是在釋放leave_barberchair 信號之後進行付款動作的話，很
容易造成沒有收銀員為其收款的情形， 原因是： 為該顧客理發的理發師收到
leave_barberchair 信號後，釋放barber_chair 信號，另外一名顧客坐到理發椅上，
該理發師有可能為這另外一名顧客理發，而沒有為剛理完發的顧客收款。為解決這個問題，
就是採取在釋放leave_barberchair 信號之前，完成付款操作。這樣該理發師無法進入
下一輪循環為另外顧客服務，只能到收銀台收款。
（2）本演算法是通過給理發師編號的方式，當顧客坐到某理發椅上也同時獲得理發師的編號，
如此，當該理發師理發結束，釋放信號，顧客只有接收到為其理發的理發師的理發結束信號
才會進行付款等操作。這樣實現，是為避免這樣的錯誤，即：如果僅用一個finished 信
號量的話，很容易出現別的理發師理發完畢釋放了finished 信號，把正在理發的這位顧
客趕去付款,而已經理完發的顧客卻被阻塞在理發椅上的情形。當然也可以為顧客進行編
號，讓理發師獲取他理發的顧客的編號，但這樣就會限制顧客的數量，因為finished[]
數組不能是無限的。而為理發師編號，則只需要三個元素即可。
3.參考文獻：
左金平 計算機操作系統中哲學家進餐問題探究。
參考教材 操作系統—內核與設計原理
其他網路資源

3. 用C語言編程實現P、V原語並用P、V原語哲學家就餐問題

這個是操作系統課的問題吧，我沒做過哲學家這個程序，不過我用c語言做過生產者與消費者，大概差不多，pv操作時用windows api函數完成的。

4. 如何利用管程來解決哲學家進餐問題

利用管程機制實現（最終該實現是失敗的，見以下分析）：
原理：不是對每隻筷子設置信號量，而是對每個哲學家設置信號量。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);
}
}
有更好的答案盡快轉給你

5. 怎樣用c++實現哲學家進餐問題

#include<pthread.h>
#include<stdio.h>

#defineN5
#defineLEFT(i+N-1)%N
#defineRIGHT(i+1)%N
#defineTHINK_TIME3
#defineEAT_TIME2

enum{THINKING,HUNGRY,EATING}state[N];

pthread_mutex_tmutex=PTHREAD_MUTEX_INITIALIZER,s[N];

voidtest(inti)
{
if(state[i]==HUNGRY
&&state[LEFT]!=EATING
&&state[RIGHT]!=EATING)
{
state[i]=EATING;
pthread_mutex_unlock(&s[i]);
}
}

voidtake_forks(inti)
{
pthread_mutex_lock(&mutex);
state[i]=HUNGRY;
test(i);
pthread_mutex_unlock(&mutex);
pthread_mutex_lock(&s[i]);
}

voidput_forks(inti)
{
pthread_mutex_lock(&mutex);
state[i]=THINKING;
test(LEFT);
test(RIGHT);
pthread_mutex_unlock(&mutex);
}

voidthink(inti)
{
printf("philosopher%disthinking...
",i);
sleep(THINK_TIME);
}

voideat(inti)
{
printf("philosopher%diseating...
",i);
sleep(EAT_TIME);
}

void*phi(void*vargp)
{
inti=*(int*)vargp;
while(1)
{
think(i);
take_forks(i);
eat(i);
put_forks(i);
}
returnNULL;
}

intmain()
{
inti;
pthread_ttid[N];
for(i=0;i<N;i++)
pthread_create(&tid[i],NULL,phi,(void*)(&i));
for(i=0;i<N;i++)
pthread_join(tid[i],NULL);
return0;
}

6. 哲學家就餐問題的演算法實現

操作系統並發和互斥：哲學家進餐問題和理發師問題

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);
}
}
2.理發師問題：一個理發店有一個入口和一個出口。理發店內有一個可站5 位顧客的站席
區、4 個單人沙發、3 個理發師及其專用理發工具、一個收銀台。新來的顧客坐在沙發上等
待；沒有空沙發時，可在站席區等待；站席區滿時，只能在入口外等待。理發師可從事理
發、收銀和休息三種活動。理發店的活動滿足下列條件：
1）休息的理發師是坐地自己專用的理發椅上，不會佔用顧客的沙發；
2）處理休息狀態的理發師可為在沙發上等待時間最長的顧客理發；
3）理發時間長短由理發師決定；
4）在站席區等待時間最長的顧客可坐到空閑的理發上；
5）任何時刻最多隻能有一個理發師在收銀。
試用信號量機制或管程機制實現理發師進程和顧客進程。
原理：
(1)customer 進程：
首先檢查站席區是否已滿（stand_capacity）,若滿選擇離開，否則進入站席區，即進入
理發店。在站席區等待沙發的空位（信號量sofa），如果沙發已滿，則進入阻塞等待隊列，
直到出現空位，在站席區中等待時間最長的顧客離開站席區（stand_capacity）。坐到沙
發上，等待理發椅(barber_chair)，如果理發椅已滿，則進入阻塞等待隊列，直到出現
空位，在沙發上等待時間最長的顧客離開沙發（釋放信號量sofa）。坐到理發椅上，釋放
准備好的信號（customer_ready），獲得該理發師的編號（0~1 的數字）。等待理發師理
發結束（finished[barber_number]）。在離開理發椅之前付款（payment），等待收據
(receipt)，離開理發椅（leave_barberchair）。最後離開理發店。
這里需要注意幾點：
a) 首先是幾個需要進行互斥處理的地方，主要包括:進入站席區、進入沙發、進入理發椅
和付款幾個地方。
b) 通過barber_chair 保證一個理發椅上最多隻有一名顧客。但這也不夠，因為單憑
baber_chair 無法保證一名顧客離開理發椅之前，另一位顧客不會坐到該理發椅上，
因此增加信號量leave_barberchair，讓顧客離開理發椅後，釋放該信號，而理發
師接收到該信號後才釋放barber_chair 等待下一位顧客。
c) 在理發的過程中，需要保證是自己理發完畢，才能夠進行下面的付款、離開理發椅的活
動。這個機制是通過customer 進程獲得給他理發的理發師編號來實現的，這樣，當
該編號的理發師釋放對應的finished[i]信號的時候，該顧客才理發完畢。
d) 理發師是通過mutex 信號量保證他們每個人同時只進行一項操作（理發或者收款）。
e) 為了保證該顧客理發完畢後馬上可以付款離開，就應該保證給該顧客理發的理發師在理
發完畢後馬上到收銀台進入收款操作而不是給下一位顧客服務。在偽碼中由以下機制實
現：即顧客在釋放離開理發椅的信號前，發出付款的信號。這樣該理發師得不到顧客的
離開理發椅的信號，不能進入下一個循環為下一名顧客服務，而只能進入收款台的收款
操作。直到顧客接到收據後，才釋放離開理發椅的信號，離開理發椅，讓理發師釋放該
理發椅的信號，讓下一位等待的顧客坐到理發椅上。
(2)barber 進程
首先將該理發師的編號壓入隊列，供顧客提取。等待顧客坐到理發椅坐好(信號量
customer_ready)，開始理發，理發結束後釋放結束信號（finished[i]）。等待顧客
離開理發椅（leave_barberchair）（期間去收銀台進行收款活動），釋放理發椅空閑信
號(barber_chair)，等待下一位顧客坐上來。
(3)cash（收銀台）進程
等待顧客付款(payment),執行收款操作，收款操作結束，給付收據（receipt）。
信號量總表：
信號量 wait signal
stand_capacity 顧客等待進入理發店 顧客離開站席區
sofa 顧客等待坐到沙發 顧客離開沙發
barber_chair 顧客等待空理發椅 理發師釋放空理發椅
customer_ready 理發師等待，直到一個顧客坐
到理發椅
顧客坐到理發椅上，給理發師
發出信號
mutex 等待理發師空閑，執行理發或
收款操作
理發師執行理發或收款結束，
進入空閑狀態
mutex1 執行入隊或出隊等待 入隊或出隊結束，釋放信號
finished[i] 顧客等待對應編號理發師理
發結束
理發師理發結束，釋放信號
leave_barberchair 理發師等待顧客離開理發椅 顧客付款完畢得到收據，離開
理發椅釋放信號
payment 收銀員等待顧客付款 顧客付款，發出信號
receipt 顧客等待收銀員收、開具收據收銀員收款結束、開具收據，
釋放信號
偽碼：
semaphore stand_capacity=5;
semaphore sofa=4;
semaphore barber_chair=3;
semaphore customer_ready=0;
semaphore mutex=3;
semaphore mutex1=1;
semaphore finished[3]={0,0,0};
semaphore leave_barberchair=0;
semaphore payment=0;
semaphore receipt=0;
void customer()
{
int barber_number;
wait(stand_capacity); //等待進入理發店
enter_room(); //進入理發店
wait(sofa); //等待沙發
leave_stand_section(); //離開站席區
signal(stand_capacity);
sit_on_sofa(); //坐在沙發上
wait(barber_chair); //等待理發椅
get_up_sofa(); //離開沙發
signal(sofa);
wait(mutex1);
sit_on_barberchair(); //坐到理發椅上
signal(customer_ready);
barber_number=dequeue(); //得到理發師編號
signal(mutex1);
wait(finished[barber_number]); //等待理發結束
pay(); //付款
signal(payment); //付款
wait(receipt); //等待收據
get_up_barberchair(); //離開理發椅
signal(leave_barberchair); //發出離開理發椅信號
exit_shop(); //了離開理發店
}
void barber(int i)
{
while(true)
{
wait(mutex1);
enqueue(i); //將該理發師的編號加入隊列
signal(mutex1);
wait(customer_ready); //等待顧客准備好
wait(mutex);
cut_hair(); //理發
signal(mutex);
signal(finished[i]); //理發結束
wait(leave_barberchair); //等待顧客離開理發椅信號
signal(barber_chair); //釋放barber_chair 信號
}
}
void cash() //收銀
{
while(true)
{
wait(payment); //等待顧客付款
wait(mutex); //原子操作
get_pay(); //接受付款
give_receipt(); //給顧客收據
signal(mutex);
signal(receipt); //收銀完畢，釋放信號
}
}
分析：
在分析該問題過程中，出現若干問題，是參閱相關資料後才認識到這些問題的隱蔽性和嚴重
性的,主要包括：
（1）在顧客進程，如果是在釋放leave_barberchair 信號之後進行付款動作的話，很
容易造成沒有收銀員為其收款的情形， 原因是： 為該顧客理發的理發師收到
leave_barberchair 信號後，釋放barber_chair 信號，另外一名顧客坐到理發椅上，
該理發師有可能為這另外一名顧客理發，而沒有為剛理完發的顧客收款。為解決這個問題，
就是採取在釋放leave_barberchair 信號之前，完成付款操作。這樣該理發師無法進入
下一輪循環為另外顧客服務，只能到收銀台收款。
（2）本演算法是通過給理發師編號的方式，當顧客坐到某理發椅上也同時獲得理發師的編號，
如此，當該理發師理發結束，釋放信號，顧客只有接收到為其理發的理發師的理發結束信號
才會進行付款等操作。這樣實現，是為避免這樣的錯誤，即：如果僅用一個finished 信
號量的話，很容易出現別的理發師理發完畢釋放了finished 信號，把正在理發的這位顧
客趕去付款,而已經理完發的顧客卻被阻塞在理發椅上的情形。當然也可以為顧客進行編
號，讓理發師獲取他理發的顧客的編號，但這樣就會限制顧客的數量，因為finished[]
數組不能是無限的。而為理發師編號，則只需要三個元素即可。
3.參考文獻：
左金平 計算機操作系統中哲學家進餐問題探究。
參考教材 操作系統—內核與設計原理

7. 哲學家進餐問題的演算法與實現

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 ; semaphorechopstick[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(inti) { 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); } }
2.理發師問題：一個理發店有一個入口和一個出口。理發店內有一個可站5 位顧客的站席區、4 個單人沙發、3 個理發師及其專用理發工具、一個收銀台。新來的顧客坐在沙發上等待；沒有空沙發時，可在站席區等待；站席區滿時，只能在入口外等待。理發師可從事理發、收銀和休息三種活動。
理發店的活動滿足下列條件：
1）休息的理發師是坐地自己專用的理發椅上，不會佔用顧客的沙發；
2）處理休息狀態的理發師可為在沙發上等待時間最長的顧客理發；
3）理發時間長短由理發師決定；
4）在站席區等待時間最長的顧客可坐到空閑的理發上；
5）任何時刻最多隻能有一個理發師在收銀。試用信號量機制或管程機制實現理發師進程和顧客進程。
原理：
(1) customer 進程：首先檢查站席區是否已滿（stand_capacity）,若滿選擇離開，否則進入站席區，即進入理發店。在站席區等待沙發的空位（信號量sofa），如果沙發已滿，則進入阻塞等待隊列，直到出現空位，在站席區中等待時間最長的顧客離開站席區（stand_capacity）。坐到沙發上，等待理發椅(barber_chair)，如果理發椅已滿，則進入阻塞等待隊列，直到出現空位，在沙發上等待時間最長的顧客離開沙發（釋放信號量sofa）。坐到理發椅上，釋放准備好的信號（customer_ready），獲得該理發師的編號（0~1 的數字）。等待理發師理發結束（finished[barber_number]）。在離開理發椅之前付款（payment），等待收據 (receipt)，離開理發椅（leave_barberchair）。最後離開理發店。
這里需要注意幾點：
a) 首先是幾個需要進行互斥處理的地方，主要包括:進入站席區、進入沙發、進入理發椅和付款幾個地方。
b) 通過barber_chair保證一個理發椅上最多隻有一名顧客。但這也不夠，因為單憑 baber_chair 無法保證一名顧客離開理發椅之前，另一位顧客不會坐到該理發椅上，因此增加信號量leave_barberchair，讓顧客離開理發椅後，釋放該信號，而理發師接收到該信號後才釋放barber_chair 等待下一位顧客。
c) 在理發的過程中，需要保證是自己理發完畢，才能夠進行下面的付款、離開理發椅的活動。這個機制是通過customer 進程獲得給他理發的理發師編號來實現的，這樣，當該編號的理發師釋放對應的finished[i]信號的時候，該顧客才理發完畢。
d) 理發師是通過mutex 信號量保證他們每個人同時只進行一項操作（理發或者收款）。
e) 為了保證該顧客理發完畢後馬上可以付款離開，就應該保證給該顧客理發的理發師在理發完畢後馬上到收銀台進入收款操作而不是給下一位顧客服務。在偽碼中由以下機制實現：即顧客在釋放離開理發椅的信號前，發出付款的信號。這樣該理發師得不到顧客的離開理發椅的信號，不能進入下一個循環為下一名顧客服務，而只能進入收款台的收款操作。直到顧客接到收據後，才釋放離開理發椅的信號，離開理發椅，讓理發師釋放該理發椅的信號，讓下一位等待的顧客坐到理發椅上。
(2)barber 進程首先將該理發師的編號壓入隊列，供顧客提取。等待顧客坐到理發椅坐好(信號量 customer_ready)，開始理發，理發結束後釋放結束信號（finished[i]）。等待顧客離開理發椅（leave_barberchair）（期間去收銀台進行收款活動），釋放理發椅空閑信號(barber_chair)，等待下一位顧客坐上來。
(3)cash（收銀台）進程等待顧客付款(payment),執行收款操作，收款操作結束，給付收據（receipt）。信號量總表：信號量 waitsignal stand_capacity 顧客等待進入理發店顧客離開站席區 sofa 顧客等待坐到沙發顧客離開沙發 barber_chair 顧客等待空理發椅理發師釋放空理發椅 customer_ready 理發師等待，直到一個顧客坐到理發椅顧客坐到理發椅上，給理發師發出信號 mutex 等待理發師空閑，執行理發或收款操作理發師執行理發或收款結束，進入空閑狀態 mutex1執行入隊或出隊等待入隊或出隊結束，釋放信號 finished[i] 顧客等待對應編號理發師理發結束理發師理發結束，釋放信號 leave_barberchair 理發師等待顧客離開理發椅顧客付款完畢得到收據，離開理發椅釋放信號 payment 收銀員等待顧客付款顧客付款，發出信號 receipt 顧客等待收銀員收、開具收據收銀員收款結束、開具收據，釋放信號
偽碼： semaphore stand_capacity=5; semaphore sofa=4; semaphorebarber_chair=3; semaphore customer_ready=0; semaphore mutex=3; semaphoremutex1=1; semaphore finished[3]={0,0,0}; semaphore leave_barberchair=0;semaphore payment=0; semaphore receipt=0; void customer() { int barber_number;wait(stand_capacity); //等待進入理發店 enter_room(); //進入理發店 wait(sofa); //等待沙發 leave_stand_section(); //離開站席區 signal(stand_capacity); sit_on_sofa(); //坐在沙發上 wait(barber_chair); //等待理發椅 get_up_sofa(); //離開沙發 signal(sofa); wait(mutex1);sit_on_barberchair(); //坐到理發椅上 signal(customer_ready); barber_number=dequeue(); //得到理發師編號 signal(mutex1); wait(finished[barber_number]);//等待理發結束 pay(); //付款 signal(payment); //付款 wait(receipt); //等待收據 get_up_barberchair(); //離開理發椅 signal(leave_barberchair); //發出離開理發椅信號 exit_shop(); //了離開理發店 } void barber(int i) { while(true) { wait(mutex1);enqueue(i); //將該理發師的編號加入隊列 signal(mutex1); wait(customer_ready); //等待顧客准備好 wait(mutex); cut_hair(); //理發 signal(mutex); signal(finished[i]); //理發結束 wait(leave_barberchair); //等待顧客離開理發椅信號 signal(barber_chair); //釋放barber_chair 信號 } } void cash() //收銀 { while(true) { wait(payment); //等待顧客付款 wait(mutex); //原子操作 get_pay(); //接受付款 give_receipt(); //給顧客收據 signal(mutex); signal(receipt); //收銀完畢，釋放信號 } }
分析：在分析該問題過程中，出現若干問題，是參閱相關資料後才認識到這些問題的隱蔽性和嚴重性的,主要包括：
（1）在顧客進程，如果是在釋放leave_barberchair 信號之後進行付款動作的話，很容易造成沒有收銀員為其收款的情形，原因是：為該顧客理發的理發師收到 leave_barberchair 信號後，釋放barber_chair 信號，另外一名顧客坐到理發椅上，該理發師有可能為這另外一名顧客理發，而沒有為剛理完發的顧客收款。為解決這個問題，就是採取在釋放leave_barberchair 信號之前，完成付款操作。這樣該理發師無法進入下一輪循環為另外顧客服務，只能到收銀台收款。
（2）本演算法是通過給理發師編號的方式，當顧客坐到某理發椅上也同時獲得理發師的編號，如此，當該理發師理發結束，釋放信號，顧客只有接收到為其理發的理發師的理發結束信號才會進行付款等操作。這樣實現，是為避免這樣的錯誤，即：如果僅用一個finished 信號量的話，很容易出現別的理發師理發完畢釋放了finished 信號，把正在理發的這位顧客趕去付款,而已經理完發的顧客卻被阻塞在理發椅上的情形。當然也可以為顧客進行編號，讓理發師獲取他理發的顧客的編號，但這樣就會限制顧客的數量，因為finished[] 數組不能是無限的。而為理發師編號，則只需要三個元素即可。

8. 150分--哲學家就餐問題 要「C/C++」來實現的

自己搞定了 來收分數的 嘿嘿

9. 哲學家就餐問題

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