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

1、1 答案1;.2習(xí)題課： Wait.Signal 操作必須成對(duì)出現(xiàn)，有一個(gè)Wait操作就一定有一個(gè)Signal 操作 當(dāng)為互斥操作時(shí)，它們同處于同一進(jìn)程 當(dāng)為同步操作時(shí)，則不在同一進(jìn)程中出現(xiàn) 如果Wait(S1) 和 Wait(S2)兩個(gè)操作在一起，那么Wait 操作的順序至關(guān)重要,一個(gè)同步Wait 操作與一個(gè)互斥Wait 操作在一起時(shí)同步Wait 操作在互斥 Wait 操作前 而兩個(gè)Signal 操作無(wú)關(guān)緊要31、生產(chǎn)者-消費(fèi)者問(wèn)題的同步算法中，為什么顛倒生產(chǎn)者進(jìn)程中的兩個(gè)Wait 操作的次序，將導(dǎo)致進(jìn)程死鎖？（南京航空航天大學(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這是因?yàn)橛锌赡艹霈F(xiàn)這樣一種特殊情況：在某個(gè)時(shí)刻，緩沖區(qū)中已經(jīng)放滿了產(chǎn)品且沒(méi)有進(jìn)程在工作，如果此時(shí)系統(tǒng)調(diào)度生產(chǎn)者進(jìn)程運(yùn)行的話，Wait(mutex)能順利通過(guò)（此時(shí)mutex =0），但是當(dāng)它執(zhí)行Wait(E)時(shí)，由于此時(shí)的E=0-1=-10,所以生產(chǎn)者進(jìn)程只能阻塞，等待消費(fèi)者進(jìn)程取走一個(gè)產(chǎn)品后釋放緩沖單元。而此時(shí)如果有消費(fèi)者進(jìn)程過(guò)來(lái)運(yùn)行，當(dāng)它順利通過(guò)Wait(F)后，在執(zhí)行Wai

3、t(mutex)，此時(shí)的 mutex=-1，因此消費(fèi)者進(jìn)程也被阻塞了，這樣消費(fèi)者進(jìn)程和生產(chǎn)者進(jìn)程都處于等待狀態(tài)，從而產(chǎn)生了死鎖。52、兄弟倆共同使用一個(gè)賬號(hào) , 每次限存或取 10 元 , 存錢(qián)與取錢(qián)的進(jìn)程分別如下所示 :( 南京大學(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;由于兄弟倆可能同時(shí)存錢(qián)和取錢(qián) , 因此兩個(gè)進(jìn)程是并發(fā)的。若哥哥先存了兩次錢(qián) , 但在第三次存錢(qián)時(shí) , 弟弟在取錢(qián)。請(qǐng)問(wèn)最后賬號(hào) amount 上面可能出現(xiàn)的值 ? 如何用 Wait 、 Signal 操作, 實(shí)現(xiàn)兩并發(fā)進(jìn)程的互斥執(zhí)行 ?7答 : 哥哥存了兩次錢(qián)后,共享變量 amount 的值為 20 。哥哥的第三次存錢(qián)與弟弟的取錢(qián)同時(shí)進(jìn)行 ,如果兩者順序執(zhí)行 , 則最后賬號(hào) amount 的值為 20； 如果在一個(gè)進(jìn)程的執(zhí)行過(guò)程 中 , 進(jìn)行 CPU 調(diào)度 , 轉(zhuǎn)去執(zhí)行另一進(jìn)程 , 則最后 amount 的值取決于 amount:=m1及amount:=m

5、2 的執(zhí)行先后次序 , 若前者先執(zhí)行 ,則最后 amount 的值為 10, 若后者先執(zhí)行 ,則最后 amount 的值為 30 。因此 , 最后賬號(hào) amount 上面可能出現(xiàn)的值有 10、20、30。上述問(wèn)題中 , 共享變量 amount 是一個(gè)臨界資源 , 為了實(shí)現(xiàn)兩并發(fā)進(jìn)程對(duì)它的互斥訪問(wèn) ,為它設(shè)置一初值為 1 的互斥信號(hào)量 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è)公共汽車(chē)上 , 有一位司機(jī)和一位售票員 , 它們的活動(dòng)如下： 司機(jī) : 售票員 : 啟動(dòng)車(chē)輛； 關(guān)車(chē)門(mén)； 正常行車(chē)； 售票；到站停車(chē)； 開(kāi)車(chē)門(mén)； 請(qǐng)分析司機(jī)與售票員之間的同步關(guān)系 , 如何用信號(hào)量和 wait sig

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

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

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

10、結(jié)束后離開(kāi)。13在這兩個(gè)活動(dòng)中 , 從資源的角度來(lái)看 , 理發(fā)師是顧客爭(zhēng)用的資源 , 用信號(hào)量 barber 表 示 , 初值為 0; 除此以外 , 顧客還要爭(zhēng)用 n 張椅子 , 信號(hào)量 customers 表示等候理發(fā)的顧客數(shù) , 初值為 0；最后設(shè)置信號(hào)量 mutex 用于這兩個(gè)活動(dòng)對(duì)資源 barber 、 customers 的互斥 ,初值為1。使用三個(gè)信號(hào)量 ；customers 用于記錄等候的顧客的數(shù)量；barbers 用于表示理發(fā)師是否在理發(fā)；mutex用于進(jìn)程之間的互斥。 另外還需使用一個(gè)變量 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é)家就餐問(wèn)題 有五個(gè)哲學(xué)家圍坐在一圓桌旁，桌中央有一盤(pán)通心粉，每人面前有一只空盤(pán)子，每?jī)扇酥g放一只筷子 每個(gè)哲學(xué)家的行為是思考，感到饑餓，然后吃通心粉 為了吃通心粉，每個(gè)哲學(xué)家必須拿到兩只筷子，并且每個(gè)人只能直接從自己的左邊或右邊去取筷子17一個(gè)簡(jiǎn)單的解法是，用一個(gè)信號(hào)量表示一支筷子，這五個(gè)信號(hào)量構(gòu)成信號(hào)量數(shù)組，其描述為： var chopstick:array04 of semaphore;所有信號(hào)量初始值為1，第

13、I個(gè)哲學(xué)家的活動(dòng)課描述為：Repeatwait(chopsticki);wait(chopstick(i+1) mod 5); eat; signal(chopsticki);signal(chopstick(i+1) mod 5); think;until false;18為防止死鎖發(fā)生可采取的措施：最多允許4個(gè)哲學(xué)家同時(shí)就餐；僅當(dāng)一個(gè)哲學(xué)家左右兩邊的筷子都可用時(shí)，才允許他拿筷子（）；給所有哲學(xué)家編號(hào)，奇數(shù)號(hào)的哲學(xué)家必須首先拿左邊的筷子，偶數(shù)號(hào)的哲學(xué)家則反之 為了避免死鎖，把哲學(xué)家分為三種狀態(tài)，思考，饑餓，進(jìn)食，并且一次拿到兩只筷子，否則不拿19設(shè)一個(gè)信號(hào)量Sm來(lái)限制同時(shí)進(jìn)餐的人數(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. 有一閱覽室，讀者進(jìn)入時(shí)必須先在一張登記表上進(jìn)行登記，該表為每一座位列一表目，包括座號(hào)和讀者姓名。讀者離開(kāi)時(shí)要消掉登記信號(hào)，閱覽室中共有100個(gè)座位，請(qǐng)問(wèn)：(1) 為描述讀者的動(dòng)作，應(yīng)編寫(xiě)幾個(gè)程序？設(shè)置幾個(gè)進(jìn)程？進(jìn)程與程序間的對(duì)應(yīng)關(guān)系如何？(2) 用類Pascal語(yǔ)言和Wait, Signal操作寫(xiě)出這些進(jìn)程間的同步算法。22答：(1) 應(yīng)編寫(xiě)1個(gè)程序；設(shè)置2個(gè)進(jìn)程；進(jìn)程與