操作系統(tǒng) 習(xí)題課1 答案ppt課件

1、1 答案1;.2習(xí)題課： Wait.Signal 操作必須成對出現(xiàn)，有一個Wait操作就一定有一個Signal 操作 當為互斥操作時，它們同處于同一進程 當為同步操作時，則不在同一進程中出現(xiàn) 如果Wait(S1) 和 Wait(S2)兩個操作在一起，那么Wait 操作的順序至關(guān)重要,一個同步Wait 操作與一個互斥Wait 操作在一起時同步Wait 操作在互斥 Wait 操作前 而兩個Signal 操作無關(guān)緊要31、生產(chǎn)者-消費者問題的同步算法中，為什么顛倒生產(chǎn)者進程中的兩個Wait 操作的次序，將導(dǎo)致進程死鎖？（南京航空航天大學(xué)2002年碩士入學(xué)考題）Procedure producer b

2、egtn repeat生產(chǎn)數(shù)據(jù) ; Wait(mutex); Wait(E);“分給空緩沖區(qū)并調(diào)整指針 P 的臨界段”;Signal (mutex);“向空緩沖區(qū) 裝入數(shù)據(jù)”; Signal (F); forever4這是因為有可能出現(xiàn)這樣一種特殊情況：在某個時刻，緩沖區(qū)中已經(jīng)放滿了產(chǎn)品且沒有進程在工作，如果此時系統(tǒng)調(diào)度生產(chǎn)者進程運行的話，Wait(mutex)能順利通過（此時mutex =0），但是當它執(zhí)行Wait(E)時，由于此時的E=0-1=-10,所以生產(chǎn)者進程只能阻塞，等待消費者進程取走一個產(chǎn)品后釋放緩沖單元。而此時如果有消費者進程過來運行，當它順利通過Wait(F)后，在執(zhí)行Wai

3、t(mutex)，此時的 mutex=-1，因此消費者進程也被阻塞了，這樣消費者進程和生產(chǎn)者進程都處于等待狀態(tài)，從而產(chǎn)生了死鎖。52、兄弟倆共同使用一個賬號 , 每次限存或取 10 元 , 存錢與取錢的進程分別如下所示 :( 南京大學(xué) 2000 年試題 )begin amount:integer; amout:=0;cobegin process SAVEm1:integer ; begin m1:=amount; m1:=m1+10; amout:=m1; end;6 process TAKEm2:integer ; begin m2:=amount; m2:=m2-10; amout:=m

4、2; end; coend; end;由于兄弟倆可能同時存錢和取錢 , 因此兩個進程是并發(fā)的。若哥哥先存了兩次錢 , 但在第三次存錢時 , 弟弟在取錢。請問最后賬號 amount 上面可能出現(xiàn)的值 ? 如何用 Wait 、 Signal 操作, 實現(xiàn)兩并發(fā)進程的互斥執(zhí)行 ?7答 : 哥哥存了兩次錢后,共享變量 amount 的值為 20 。哥哥的第三次存錢與弟弟的取錢同時進行 ,如果兩者順序執(zhí)行 , 則最后賬號 amount 的值為 20； 如果在一個進程的執(zhí)行過程 中 , 進行 CPU 調(diào)度 , 轉(zhuǎn)去執(zhí)行另一進程 , 則最后 amount 的值取決于 amount:=m1及amount:=m

5、2 的執(zhí)行先后次序 , 若前者先執(zhí)行 ,則最后 amount 的值為 10, 若后者先執(zhí)行 ,則最后 amount 的值為 30 。因此 , 最后賬號 amount 上面可能出現(xiàn)的值有 10、20、30。上述問題中 , 共享變量 amount 是一個臨界資源 , 為了實現(xiàn)兩并發(fā)進程對它的互斥訪問 ,為它設(shè)置一初值為 1 的互斥信號量 mutex, 并將上述算法修改為 : 8begin amount: integer; Mutex: semaphore;amout:=0;mutex=1;cobegin process SAVEm1:integer ; beginWait(mutex); m1:=

6、amount; m1:=m1+10; amout:=m1; Signal(mutex);end;process TAKEm2:integer ; beginWait(mutex); m2:=amount; m2:=m2-10; amout: = m2; Signal(mutex);end; coend; end;93、（華中理工大學(xué) 1999，哈工大2000年研究生人學(xué)試題 ) 設(shè)公共汽車上 , 有一位司機和一位售票員 , 它們的活動如下： 司機 : 售票員 : 啟動車輛； 關(guān)車門； 正常行車； 售票；到站停車； 開車門； 請分析司機與售票員之間的同步關(guān)系 , 如何用信號量和 wait sig

7、nal操作實現(xiàn)。 【分析】在汽車的行駛過程中,為了安全起見 ,顯然要求 : 只有售票員關(guān)車門后司機才能啟動車輛 ; 汽車到站停車后才能開車門。所以司機和售票員在到站、開門、關(guān)門、啟動車輛 這幾個活動之間存在著同步關(guān)系。用兩個信號量 S1 、 S2 分別表示是否可以開車和是否可以開門 ,S1 ,S2的初值為 0。用wait signal操作實現(xiàn)司機進程和售票員進程同步的關(guān)系為：10司機 : 售票員 : Wait(S1)關(guān)車門啟動車輛 Signal(S1)Signal(S1)正常行車 售票到站停車 Wait(S2)Signal(S2)Signal(S2) 開車門具體的 Wait 、 SignalS

8、ignal 原語算法描述如下:int S1=O ; int S2=O;Main( ) cobegin driver( ) /*司機的活動*/ Busman( ) /*售票員的活動*/ coend 11Driver( ) while (true)Wait(S1);啟動車輛 ; 正常行車 ; 到站停車 ; Signal(S2);busman ( ) while (true)關(guān)車門 ；Signal(S1);售票 ; Wait(S2);開車門 ; 124、有一個理發(fā)師 , 一把理發(fā)椅和 n 把供等候理發(fā)的顧客坐的椅子。如果沒有顧客 , 則理發(fā)師便在理發(fā)椅上睡覺 ; 當一個顧客到來時 , 必須叫醒理發(fā)師

9、進行理發(fā) ; 如果理發(fā)師正在理發(fā)時有別的顧客來到 , 則如果有空椅子可坐 , 他就坐下來等 , 如果沒有空椅子,他就離開。為理發(fā)師和顧客各編一段程序描述他們的行為。 ( 西安電子科技大學(xué)2000年研究生試題 ) 【分析】考慮一下理發(fā)師 (barber) 重復(fù)的下列活動：睡覺 為顧客理發(fā)； 顧客 (customers) 重復(fù)的下列活動 : 在椅子上等候；理發(fā)；離開；顯然 , 理發(fā)師在處要考查是否有顧客等候理發(fā) ,如果沒有,理發(fā)師睡覺；在處理發(fā)師等待最先進入理發(fā)店的顧客喚醒 , 開始理發(fā)。顧客在處先看是否有座位 ,沒有則離開；等候理發(fā)的顧客在處被理發(fā)師喚醒 ( 最先理發(fā)的顧客要喚醒理發(fā)師 )；理發(fā)

10、結(jié)束后離開。13在這兩個活動中 , 從資源的角度來看 , 理發(fā)師是顧客爭用的資源 , 用信號量 barber 表 示 , 初值為 0; 除此以外 , 顧客還要爭用 n 張椅子 , 信號量 customers 表示等候理發(fā)的顧客數(shù) , 初值為 0；最后設(shè)置信號量 mutex 用于這兩個活動對資源 barber 、 customers 的互斥 ,初值為1。使用三個信號量 ；customers 用于記錄等候的顧客的數(shù)量；barbers 用于表示理發(fā)師是否在理發(fā)；mutex用于進程之間的互斥。 另外還需使用一個變量 waiter, 也是用于記錄等候的顧客的數(shù)量。14include”prototypes

11、.h”define CHAIRS nType defintsemaphore;customers=0barbers=0Mutex=1;Waiter=0; /*等待理發(fā)的人數(shù)*/15Void Customer(void)wait(mutex);If(waiterCHAIRS)waiter=waiter+1;signal(customers);signal(mutex);wait(barbers);get_haircut();Elsesignal(mutex);Void Barber(void) while(ture)Wait(customers); /*是否有等候理發(fā)的顧客*/Wait(mute

12、x);Waiter=water-1; /*等候理發(fā)的顧客數(shù)減1*/Signal(mutex);Signal(barbers);Cut_hair(); /*理發(fā)師理發(fā)*/165、哲學(xué)家就餐問題 有五個哲學(xué)家圍坐在一圓桌旁，桌中央有一盤通心粉，每人面前有一只空盤子，每兩人之間放一只筷子 每個哲學(xué)家的行為是思考，感到饑餓，然后吃通心粉 為了吃通心粉，每個哲學(xué)家必須拿到兩只筷子，并且每個人只能直接從自己的左邊或右邊去取筷子17一個簡單的解法是，用一個信號量表示一支筷子，這五個信號量構(gòu)成信號量數(shù)組，其描述為： var chopstick:array04 of semaphore;所有信號量初始值為1，第

13、I個哲學(xué)家的活動課描述為：Repeatwait(chopsticki);wait(chopstick(i+1) mod 5); eat; signal(chopsticki);signal(chopstick(i+1) mod 5); think;until false;18為防止死鎖發(fā)生可采取的措施：最多允許4個哲學(xué)家同時就餐；僅當一個哲學(xué)家左右兩邊的筷子都可用時，才允許他拿筷子（）；給所有哲學(xué)家編號，奇數(shù)號的哲學(xué)家必須首先拿左邊的筷子，偶數(shù)號的哲學(xué)家則反之 為了避免死鎖，把哲學(xué)家分為三種狀態(tài)，思考，饑餓，進食，并且一次拿到兩只筷子，否則不拿19設(shè)一個信號量Sm來限制同時進餐的人數(shù)，Sm=4

14、.Pi:Repeatthink for while;wait(Sm);wait(chopsticki);wait(chopstick(i+1) mod 5);eat;signal(chopsticki);signal(chopstick(i+1) mod 5);signal(Sm); until false20Pi:Repeatthink;if (i mod 2)=1 then beginwait(chopsticki);wait(chopstick(i+1) mod 5);endelse beginwait(chopstick(i+1) mod 5);wait(chopsticki);endeatsignal(chopsticki);signal(chopstick(i+1) mod 5); until false216. 有一閱覽室，讀者進入時必須先在一張登記表上進行登記，該表為每一座位列一表目，包括座號和讀者姓名。讀者離開時要消掉登記信號，閱覽室中共有100個座位，請問：(1) 為描述讀者的動作，應(yīng)編寫幾個程序？設(shè)置幾個進程？進程與程序間的對應(yīng)關(guān)系如何？(2) 用類Pascal語言和Wait, Signal操作寫出這些進程間的同步算法。22答：(1) 應(yīng)編寫1個程序；設(shè)置2個進程；進程與