操作系統(tǒng)作業(yè)講解

1、第二章 習(xí)題講解1、進(jìn)程之間存在著哪幾種制約關(guān)系？各是什么原因引起的？下列活動分別屬于哪種制約關(guān)系？（1）若干同學(xué)去圖書館借書；（2）兩隊(duì)舉行籃球比賽；（3）流水線生產(chǎn)的各道工序；（4）商品生產(chǎn)和社會消費(fèi)。答：進(jìn)程之間存在著直接制約與間接制約這兩種制約關(guān)系，其中直接制約（同步）是由于進(jìn)程間的相互合作而引起的，而間接制約（互斥）則是由于進(jìn)程間共享臨界資源而引起的。（1）若干同學(xué)去圖書館借書，是間接制約，其中書是臨界資源；（2）兩隊(duì)舉行籃球比賽，是間接制約，其中藍(lán)球是臨界資源；（3）流水線生產(chǎn)的各道工序，是直接制約，各道工序間需要相互合作，每道工序的開始都依賴于前一道工序的完成；（4）商品生產(chǎn)和社

2、會消費(fèi)，是直接制約，兩者也需要相互合作：商品生產(chǎn)出來后才可以被消費(fèi)；商品被消費(fèi)后才需要再生產(chǎn)。2、試寫出相應(yīng)的程序來描述下圖所示的前趨圖var a,b,c,d,e,f:semaphore:=0,0,0,0,0,0;begin S1; signal(a); signal(b); signal(c); end;begin wait(a); S2; end;begin wait(b); S3; signal(d); end;begin wait(c); S4; end;begin wait(d); S5; signal(e); signal(f); end;begin wait(e); S6; en

3、d;begin wait(f); S7; end;3、已知一個求值公式(A23B)/(B+5A)，若A、B已賦值，試畫出該公式求值過程的前趨圖，并使用信號量描述這些前趨關(guān)系。 答：根據(jù)求值公式，假設(shè)：S1: X1=A*AS2: X2=3*BS3: X3=5*AS4: X4=X1+X2S5: X5=B+X3 S6: X6=X4/X5var a,b,c,d,e:semaphore:=0,0,0,0,0;begin S1; signal(a); end;begin S2; signal(b); end;begin S3; signal(c); end;begin wait(a); wait(b);

4、S4; signal(d); endbegin wait(c); S5; signal(e); endbegin wait(d); wait(e); S6; end4、桌上有一只能容納一個水果的盤子；爸爸專向盤子中放蘋果(apple)，媽媽專向盤子中放桔子(orange)，一個兒子專等吃盤子中的桔子，一個女兒專等吃盤子里的蘋果，1）試用信號量實(shí)現(xiàn)他們的同步關(guān)系；2）如果有兩個家庭的爸爸、媽媽、兒子、女兒和二只盤子呢？會需要專門的實(shí)現(xiàn)嗎？ var empty,apple,orange:semaphore:= 1,0,0; 說明：empty與apple表示盤子為空與盤子中放入了蘋果，用于表示爸爸與

5、女兒間的同步關(guān)系；empty與orange表示盤子為空與盤子中放入了桔子，用于表示媽媽與兒子間的同步關(guān)系；答案：1）使用記錄型信號量father:begin repeat producer an apple; wait(empty); Put an apple to the dish;signal(apple); Until falseenddaughter:begin repeatwait(apple); Get an apple from dish;signal(empty);Eat an apple; Until falseendmother:begin repeat producer

6、an orange; wait(empty); Put an orange to the dish;signal(orange); Until falseendson:begin repeatwait(orange); Get an orange from dish;signal(empty);Eat an orange; Until falseend2）使用記錄型信號量var mutex,empty,apple,orange:semaphore:=1,2,0,0;dish: array0,1 of fruit;in, out:integer:= 0,0;father:begin repeat

7、 producer an apple; wait(empty);wait(mutex); if dishin=apple or dishin=orange then in:=(in+1) mod 2; diskin:=apple; in:=(in+1) mod 2; signal(mutex);signal(apple); Until falseenddaughter:begin repeatwait(apple);wait(mutex); if dishout=orange then out:=(out+1) mod 2;get an apple from dishout; out:=(ou

8、t+1) mod 2; signal(mutex);signal(empty);Eat an apple; Until falseEndmother:begin repeat producer an orange; wait(empty);wait(mutex); if dishin=apple or dishin=orange then in:=(in+1) mod 2; diskin:=orange; in:=(in+1) mod 2; signal(mutex); signal(orange); Until falseendson:begin repeatwait(orange);wai

9、t(mutex); if dishout=apple then out:=(out+1) mod 2; get an orange from dishout; out:=(out+1) mod 2; signal(mutex);signal(empty);Eat an apple; Until falseend5、試用信號量實(shí)現(xiàn)課件92頁，司機(jī)與售票員進(jìn)程的同步關(guān)系var stop, door :semaphore:=0,0;driver:begin repeat drive a bus;arrive at bus station;signal(stop); rest; wait(door);

10、 Until falseendconductor:begin repeatsell tickets;wait(stop); Open the door; Close the doorsignal(door); Until falseend6、試用信號量解決讀者寫者問題，使得寫者與讀者優(yōu)先級根據(jù)到達(dá)順序確定。1）典型錯誤代碼講解：不增加任何信號量Var rmutex, wmutex:semaphore=1,1; Readcount:integer =0; begin parbegin Reader:begin repeat wait(rmutex); if Readcount=0 then wa

11、it(wmutex); Readcount = Readcount+1; signal(rmutex); perform read operation; wait(rmutex); Readcount= Readcount-1; if Readcount=0 then signal(wmutex); signal(rmutex); until false; end writer:begin repeat if readcount>0 then wait(rumtex); wait(wmutex); perform write operation; signal(rmutex); sign

12、al(wmutex); until false; end parend end到達(dá)序列：R1, R2, W1, R3, R4, W2進(jìn)程行為rmutex=1wmutex=1Readcount=0狀態(tài)備注R1到達(dá)rmutex=0rmutex=1wmutex=0Readcount=1執(zhí)行/就緒第1位讀者R2到達(dá)rmutex=0rmutex=1Readcount=2執(zhí)行/就緒W1到達(dá)rmutex=0阻塞1阻塞Readcount>0R3到達(dá)阻塞1阻塞rmutex=0R4到達(dá)阻塞2阻塞rmutex=0W2到達(dá)阻塞3阻塞rmutex=0R1離開阻塞4阻塞rmutex=0R2離開阻塞5阻塞rmutex

13、=0產(chǎn)生死鎖2）學(xué)習(xí)指導(dǎo)與題解上的解題思路答：為使寫者優(yōu)先，可在原來的讀優(yōu)先算法基礎(chǔ)上增加一個初值為1的信號量S，使得當(dāng)至少有一個寫者準(zhǔn)備訪問共享對象時，它可使后續(xù)的讀者進(jìn)程等待寫完成。初值為0的整型變量writecount用來對寫者進(jìn)行計數(shù)；初值為1 的互斥信號量mutex用來實(shí)現(xiàn)多個寫者對writecount的互斥訪問。讀者與寫者進(jìn)程算法描述如下： var S, mutex, rmutex, wmutex: semaphore:=1,1, 1,1; writecount, readcount: integer:=0,0;reader: begin repeat wait(S); wait(

14、rmutex); if readcount=0 then wait(wmutex); readcount:=readcount+1; signal(rmutex); signal(S); perform read operation; wait(rmutex); readcount:=readcount-1; if readcount=0 then signal(wmutex); signal(rmutex); until false end writer: begin repeat wait(mutex); if writecount=0 then wait(S); writecount:=

15、writecount+1; signal(mutex); wait(wmutex); perform write operation; signal(wmutex); wait(mutex); writecount:=writecount-1; if writecount=0 then signal(S); signal(mutex); until false end到達(dá)序列：R1, R2, W1, R3, R4, W2進(jìn)程行為S=1mutex=1rmutex=1wmutex=1writecount=0readcount=0備注R1到達(dá)S=0S=1rmutex=0rmutex=1wmutex=

16、0readcount=1第一個讀者執(zhí)行/就緒R2到達(dá)S=0S=1rmutex=0rmutex=1readcount=2執(zhí)行/就緒W1到達(dá)S=0mutex=0mutex=1阻塞1writecount=1第一個寫者R3到達(dá)阻塞1R4到達(dá)阻塞2W2到達(dá)mutex=0mutex=1阻塞2writecount=2R1離開rmutex=0rmutex=1readcount=1R2離開rmutex=0rmutex=1wmutex=1readcount=0負(fù)責(zé)喚醒W1W1被喚醒wmutex=0執(zhí)行/就緒W1離開mutex=0mutex=1wmutex=1writecount=1負(fù)責(zé)喚醒W23）改寫上述代碼，真

17、正實(shí)現(xiàn)讀寫平等策略 var S, rmutex, wmutex: semaphore:=1, 1,1; readcount: integer:= 0;reader: begin repeat wait(S); wait(rmutex); if readcount=0 then wait(wmutex); readcount:=readcount+1; signal(rmutex); signal(S); perform read operation; wait(rmutex); readcount:=readcount-1; if readcount=0 then signal(wmutex)

18、; signal(rmutex); until false end writer: begin repeat wait(S); wait(wmutex); perform write operation; signal(wmutex); signal(S); until false end到達(dá)序列：R1, R2, W1, R3, R4, W2進(jìn)程行為S=1rmutex=1wmutex=1readcount=0備注R1到達(dá)S=0S=1rmutex=0rmutex=1wmutex=0readcount=1第一個讀者執(zhí)行/就緒R2到達(dá)S=0S=1rmutex=0rmutex=1readcount=2

19、執(zhí)行/就緒W1到達(dá)S=0阻塞1第一個寫者R3到達(dá)阻塞1R4到達(dá)阻塞2W2到達(dá)阻塞3R1離開rmutex=0rmutex=1readcount=1R2離開rmutex=0rmutex=1wmutex=1readcount=0負(fù)責(zé)喚醒W1W1被喚醒wmutex=0執(zhí)行/就緒W1離開S=1wmutex=1負(fù)責(zé)喚醒R37、試說明PCB的作用，為什么說PCB是進(jìn)程存在的唯一標(biāo)志？（課本第7題）答：進(jìn)程控制塊的作用，是使一個在多道程序環(huán)境下不能獨(dú)立運(yùn)行的程序，成為一個能獨(dú)立運(yùn)行的基本單位，即一個能與其他進(jìn)程并發(fā)執(zhí)行的進(jìn)程。 在創(chuàng)建進(jìn)程時，系統(tǒng)將為它配置一個PCB；在進(jìn)行進(jìn)程調(diào)度時，系統(tǒng)將根據(jù)PCB中的狀態(tài)

20、和優(yōu)先級等信息來選擇新進(jìn)程，然后將老進(jìn)程的現(xiàn)場信息保存到它的PCB中，再根據(jù)新進(jìn)程PCB中所保存的處理機(jī)狀態(tài)信息來恢復(fù)運(yùn)行的現(xiàn)場；執(zhí)行中的進(jìn)程，如果需要訪問文件或者需要與合作進(jìn)程實(shí)現(xiàn)同步或通信，也都需要訪問PCB；當(dāng)進(jìn)程因某種原因而暫停執(zhí)行時，也必須將斷點(diǎn)的現(xiàn)場信息保存到它的PCB中；當(dāng)進(jìn)程結(jié)束時，系統(tǒng)將回收它的PCB。可見，在進(jìn)程的整個生命周期中，系統(tǒng)總是通過其PCB對進(jìn)程進(jìn)行控制和管理，亦即，系統(tǒng)是根據(jù)其PCB而不是任何別的什么而感知到進(jìn)程的存在，所以說，PCB是進(jìn)程存在的唯一標(biāo)志。8、同步機(jī)構(gòu)應(yīng)遵循哪些基本準(zhǔn)則？為什么？（課本第18題）答：空閑讓進(jìn)、忙則等待、有限等待、讓權(quán)等待。這樣才能

21、保證多個進(jìn)程對臨界資源的互斥訪問，不會造成系統(tǒng)的混亂、程序執(zhí)行結(jié)果的不確定性或死鎖的產(chǎn)生。9、試從物理概念上說明記錄型信號量wait和signal。（課本第19題）答：一個信號量通常對應(yīng)一類臨界資源，在使用前，信號量必須經(jīng)過定義并賦適當(dāng)?shù)某踔?。每次對它進(jìn)行wait操作意味著申請一個單位的該資源，signal操作操作意味著歸還一個單位的該類資源。當(dāng)S.value>0時，它的值表示系統(tǒng)中該類資源當(dāng)前可用的數(shù)目；S.value<=0時，表示該類資源已經(jīng)分配完畢，其絕對值表示系統(tǒng)中因申請資源而阻塞在S.L隊(duì)列上的進(jìn)程數(shù)目。10、在生產(chǎn)者消費(fèi)者問題中，如果缺少了signal(full)或si

22、gnal(empty)，對執(zhí)行結(jié)果將會有何影響？（課本第23題）答：如果生產(chǎn)者進(jìn)程中缺少了signal(full)，生產(chǎn)者一開始是不斷往緩沖池送消息，而消費(fèi)者一開始就因?yàn)閒ull為0而處于阻塞狀態(tài)，當(dāng)所有緩沖區(qū)裝滿之后，由于empty由n減為0，而消費(fèi)者已經(jīng)阻塞，生產(chǎn)者也會因?yàn)閣ait(empty)而處于阻塞狀態(tài)。產(chǎn)生死鎖。消費(fèi)者進(jìn)程中缺少了signal(empty)，緩沖區(qū)指針in從0指向了n-1后，生產(chǎn)者就會因?yàn)閳?zhí)行wait(empty)處于阻塞狀態(tài)；生產(chǎn)者阻塞后，消費(fèi)者消費(fèi)掉所有的產(chǎn)品，即緩沖區(qū)指針out從0指向了n-1后，也會因?yàn)閳?zhí)行wait(full) 處于阻塞狀態(tài)。產(chǎn)生死鎖。11、我們?yōu)槟撑R界資源設(shè)置一把鎖W，當(dāng)W=1時表示關(guān)鎖；當(dāng)W=0時表示鎖已經(jīng)打開，試寫出開鎖和關(guān)鎖原語，并利用它們?nèi)?shí)現(xiàn)互斥。（課本第25題）答：相應(yīng)的關(guān)鎖原語lock(W)和開鎖原語unlock(W)可描述如下： lock(W): while W=1 do no-op; W:=1; unlock(W): W:=0; 在利用關(guān)鎖原語和開鎖原語實(shí)現(xiàn)進(jìn)程互斥時，可將臨界區(qū)CS放在其間，即： lock(W);