部分習題答案

1、第3章 部分習題答案3.2. 為什么進程在進入臨界區(qū)之前，應先執(zhí)行"進入?yún)^(qū)"代碼，在退出臨界區(qū)后又執(zhí)行"退出區(qū)"代碼?為了實現(xiàn)多個進程對臨界資源的互斥訪問，必須在臨界區(qū)前面增加一段用于檢查欲訪問的臨界資源是否正被訪問的代碼，如果未被訪問，該進程便可進入臨界區(qū)對資源進行訪問，并設置正被訪問標志，如果正被訪問，則本進程不能進入臨界區(qū)，實現(xiàn)這一功能的代碼成為"進入?yún)^(qū)"代碼；在退出臨界區(qū)后，必須執(zhí)行"退出區(qū)"代碼，用于恢復未被訪問標志. 3.3 同步機構(gòu)應遵循哪些基本準則?為什么?a. 空閑讓進.b. 忙則等待.c. 有限

2、等待.d. 讓權(quán)等待. 3.6你認為整型信號量機制和記錄型信號量機制，是否完全遵循了同步機構(gòu)的四條準則?a. 在整型信號量機制中，未遵循"讓權(quán)等待"的準則.b. 記錄型信號量機制完全遵循了同步機構(gòu)的"空閑讓進,忙則等待,有限等待,讓權(quán)等待"四條準則.3.9 在生產(chǎn)者消費者問題中，如果缺少了signal(full)或signal(empty),對執(zhí)行結(jié)果會有何影響?生產(chǎn)者消費者問題可描述如下:var mutex,empty,full: semaphore:=1,n,0;buffer: array0,.,n-1 of item;in,out: integer

3、:=0,0;beginparbeginproducer: duce an item in nextp;.wait(empty);wait(mutex);buffer(in):=nextp;in:=(in+1) mod n;signal(mutex);/* * */signal(full);/* * */until false;endconsumer: beginrepeatwait(full);wait(mutex);nextc:=buffer(out);out:=(out+1) mod n;signal(mutex);/* * */signal(empty);/

4、* * */consume the item in nextc;until false;endparendend可見，生產(chǎn)者可以不斷地往緩沖池送消息，如果緩沖池滿，就會覆蓋原有數(shù)據(jù)，造成數(shù)據(jù)混亂.而消費者始終因wait(full)操作將消費進程直接送入進程鏈表進行等待，無法訪問緩沖池,造成無限等待. 3.10在生產(chǎn)者消費者問題中，如果將兩個wait操作即wait(full)和wait(mutex)互換位置；或者是將signal(mutex)與signal(full)互換位置結(jié)果會如何?var mutex,empty,full: semaphore:=1,n,0;buffer: array0,.

5、,n-1 of item;in,out: integer:=0,0;beginparbeginproducer: duce an item in nextp;.wait(empty);wait(mutex);buffer(in):=nextp;in:=(in+1) mod n;/* * */signal(full);signal(mutex);/* * */until false;endconsumer: beginrepeat/* * */wait(mutex);wait(full);/* * */nextc:=buffer(out);out:=(out+1)

6、mod n;signal(mutex);signal(empty);consume the item in nextc;until false;endparendend wait(full)和wait(mutex)互換位置后，因為mutex在這兒是全局變量，執(zhí)行完wait(mutex)，則mutex賦值為0，倘若full也為0，則該生產(chǎn)者進程就會轉(zhuǎn)入進程鏈表進行等待，而生產(chǎn)者進程會因全局變量mutex為0而進行等待，使full始終為0，這樣就形成了死鎖. 而signal(mutex)與signal(full)互換位置后，從邏輯上來說應該是一樣的. 3.11 我們?yōu)槟撑R界區(qū)設置一把鎖W，當W=1

7、時，表示關(guān)鎖；W=0時，表示鎖已打開.試寫出開鎖原語和關(guān)鎖原語，并利用它們?nèi)崿F(xiàn)互斥.開鎖原語:unlock(W):W=0;關(guān)鎖原語:lock(W);if(W=1) do no_op;W=1;利用開關(guān)鎖原語實現(xiàn)互斥:var W: semaphore:=0;beginparbeginprocess : beginrepeatlock(W);critical sectionunlock(W);remainder sectionuntil false;endparend 3.12試修改下面生產(chǎn)者消費者問題解法中的錯誤:producer:ducer an item in

8、nextp;wait(mutex);wait(full); /* 應為wait(empty),而且還應該在wait(mutex)的前面 */buffer(in):=nextp; /* 緩沖池數(shù)組游標應前移: in:=(in+1) mod n; */signal(mutex);/* signal(full); */until false;endconsumer:beginrepeatwait(mutex);wait(empty); /* 應為wait(full),而且還應該在wait(mutex)的前面 */nextc:=buffer(out);out:=out+1; /* 考慮循環(huán)，應改為:

9、out:=(out+1) mod n; */signal(mutex);/* signal(empty); */consumer item in nextc;until false;end 3.13 試利用記錄型信號量寫出一個不會出現(xiàn)死鎖的哲學家進餐問題的算法.設初始值為1的信號量cI表示I號筷子被拿(I=1,2,3,4,.,2n),其中n為自然數(shù).send(I):Beginif I mod 2=1 thenP(cI);P(cI-1 mod 5);Eat;V(cI-1 mod 5);V(cI);elseP(cI-1 mod 5);P(cI);Eat;V(cI);V(cI-1 mod 5);En

10、d 3.14 在測量控制系統(tǒng)中的數(shù)據(jù)采集任務，把所采集的數(shù)據(jù)送一單緩沖區(qū)；計算任務從該單緩沖中取出數(shù)據(jù)進行計算.試寫出利用信號量機制實現(xiàn)兩者共享單緩沖的同步算法.int mutex=1;int empty=n;int full=0;int in=0;int out=0;main()cobeginsend();obtain();coendsend()while(1).collect data in nextp;.wait(empty);wait(mutex);buffer(in)=nextp;in=(in+1) mod n;signal(mutex);signal(full);/sendobta

11、in()while(1)wait(full);wait(mutex);nextc:=buffer(out);out:=(out+1) mod n;signal(mutex);signal(empty);culculate the data in nextc;/while/obtain 3.19 什么是AND信號量?試利用AND信號量寫出生產(chǎn)者消費者問題的解法.為解決并行所帶來的死鎖問題，在wait操作中引入AND條件，其基本思想是將進程在整個運行過程中所需要的所有臨界資源，一次性地全部分配給進程，用完后一次性釋放.解決生產(chǎn)者消費者問題可描述如下:var mutex,empty,full: se

12、maphore:=1,n,0;buffer: array0,.,n-1 of item;in,out: integer:=0,0;beginparbeginproducer: duce an item in nextp;.wait(empty); wait(s1,s2,s3,.,sn); /s1,s2,.,sn為執(zhí)行生產(chǎn)者進程除empty外其余的條件wait(mutex);buffer(in):=nextp;in:=(in+1) mod n;signal(mutex);signal(full);signal(s1,s2,s3,.,sn);until false;endconsumer: beginrepeatwait(full);wait(k1,k2,k3,.,kn); /k1,k2,.,kn為執(zhí)行消費者進程除full外其余的條件wait(mutex);nextc:=buffer(out);out:=(out+1) mod n;signal(mutex);signal(empty);sig