編程完成以下問題的行程調度及同步模擬的實作。（用window 或linux中C語言實作）
要求如下：
1)定義若干行程并發執行，行程數可自己定義（至少應有2個行程）
2)行程調度可任選一種調度演算法：如RR FCFS
求大神給個代碼，我是小白= =
uj5u.com熱心網友回復：
樓主早點換個專業吧，這個專業不適合你。uj5u.com熱心網友回復：
要換早換了。沒得換了。只想畢業。uj5u.com熱心網友回復：
這還不簡單，每個哲學家都在等另一只筷子，就只有餓死了uj5u.com熱心網友回復：
搜搜代碼吧，看看別人的例子uj5u.com熱心網友回復：
作業系統并發和互斥：哲學家進餐問題和理發師問題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[]
陣列不能是無限的。而為理發師編號，則只需要三個元素即可。
uj5u.com熱心網友回復：
哲學家一次性申請自己所需要的資源兩只筷子，而不是逐一申請。由資源分配者統一管理發放資源。這樣就不會餓死了。如果要先用一只筷子做其他事，然后再申請另一只筷子吃飯，可以這樣，如果申請不到另一只筷子，則釋放自己的筷子，然后同時申請兩只筷子。理發師定義收銀為優先服務。理發程序為可中斷去收銀等。已經有理發師在收銀時，其他理發師不必要也去收銀。
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/140603.html
標籤：基礎類
上一篇：我是一名大專生！請問各位，我努力學習C++，以后作業好找么？工資怎樣？請各位幫哈子忙
下一篇：老妖在嗎？