青島理工大學(xué)操作系統(tǒng)作業(yè)答案

1、第1章 作業(yè)綜合題1、設(shè)內(nèi)存中有三道程序A、B、C，它們按A、B、C的優(yōu)先次序執(zhí)行。它們的計(jì)算和I/O操作時間如表所示（單位：ms）。三道程序的操作時間 程序操作ABC計(jì)算306020I/O403040計(jì)算101020假設(shè)三道程序使用相同設(shè)備I/O操作，即程序是以串行方式使用設(shè)備，調(diào)度程序的執(zhí)行時間忽略不計(jì)，試計(jì)算出在單道和多道兩種情況下，完成這三道程序各要花多少時間？要求畫出多道運(yùn)行的時序圖。（假定在多道方式下采用的是基于優(yōu)先級的非搶占調(diào)度程序）解：采用單道方式運(yùn)行這三道程序，運(yùn)行次序?yàn)锳、B、C，故總的運(yùn)行時間為：(30+40+10)+(60+30+10)+(20+40+20)=260ms

2、 采用多道方式運(yùn)行這三道程序，A、B、C這三道進(jìn)程的運(yùn)行存在并行，故總的運(yùn)行時間如圖所示為180ms第二章1、如圖所示，有一計(jì)算進(jìn)程和一打印進(jìn)程，它們共享一個單緩沖區(qū)，計(jì)算進(jìn)程不斷地計(jì)算出結(jié)果并將它放入單緩沖區(qū)中，打印進(jìn)程則負(fù)責(zé)從單緩沖區(qū)中取出每一個結(jié)果進(jìn)行打印。請用信號量來實(shí)現(xiàn)它們的同步關(guān)系。答：方法一：從臨界資源的角度來思考：本題中有兩類臨界資源：第一類是計(jì)算進(jìn)程爭用的空閑緩沖區(qū)，初始狀態(tài)下有一個空閑緩沖可供使用，設(shè)置信號量empty，初值為1；第二類是打印進(jìn)程爭用的已放入緩沖區(qū)中的打印結(jié)果，初始狀態(tài)下緩沖區(qū)中無結(jié)果可打印，設(shè)置信號量full，初值為0。var full, empty: s

3、emaphore:=0,1;begin parbegin cp:begin repeat computer next number; wait(empty); add the number to buffer; signal(full); until false end pp:begin repeat wait(full); take a number from buffer; signal(empty); print the number; until false end parendend2、試用信號量解決讀者寫者問題，使得寫者與讀者優(yōu)先級根據(jù)到達(dá)順序確定（讀寫平等）。然后用到達(dá)序列：R1

4、, R2, W1, R3, R4, W2進(jìn)行測試列出類似如下測試結(jié)果進(jìn)程行為rmutex=1wmutex=1Readcount=0狀態(tài)備注R1到達(dá)rmutex=0rmutex=1wmutex=0Readcount=1執(zhí)行/就緒第1位讀者1）典型錯誤代碼講解：不增加任何信號量Var rmutex, wmutex:semaphore=1,1; Readcount:integer =0; begin parbegin Reader:begin repeat wait(rmutex); if Readcount=0 then wait(wmutex); Readcount = Readcount+1;

5、 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); signal(wmutex); until false; end parend

6、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=0產(chǎn)生死鎖2）解決方案 var S, rmutex, wmutex:

7、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); signal(rmutex); until false end

8、 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執(zhí)行/就緒W1到達(dá)S=0阻塞1第一個寫者R3到達(dá)阻塞1R4到達(dá)阻塞

9、2W2到達(dá)阻塞3R1離開rmutex=0rmutex=1readcount=1R2離開rmutex=0rmutex=1wmutex=1readcount=0負(fù)責(zé)喚醒W1W1被喚醒wmutex=0執(zhí)行/就緒W1離開S=1wmutex=1負(fù)責(zé)喚醒R33、請給出一個寫者優(yōu)先的“讀者寫者”問題的算法描述。然后用到達(dá)序列：R1, R2, W1, R3, R4, W2進(jìn)行測試列出類似如下測試結(jié)果進(jìn)程行為rmutex=1wmutex=1Readcount=0狀態(tài)備注R1到達(dá)rmutex=0rmutex=1wmutex=0Readcount=1執(zhí)行/就緒第1位讀者答：為使寫者優(yōu)先，可在原來的讀優(yōu)先算法基礎(chǔ)上增

10、加一個初值為1的信號量S，使得當(dāng)至少有一個寫者準(zhǔn)備訪問共享對象時，它可使后續(xù)的讀者進(jìn)程等待寫完成。初值為0的整型變量writecount用來對寫者進(jìn)行計(jì)數(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(rmutex); if readcount=0 then wait(wmutex); r

11、eadcount:=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:=writecount+1; signal(mutex); wait(wmutex); p

12、erform 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=0readcount=1第一個讀者執(zhí)行/就緒R2到達(dá)S=0S=1rmutex=0rmut

13、ex=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、假設(shè)一個系統(tǒng)中有4個進(jìn)程，它們的到達(dá)時間和服務(wù)時間如表所示，忽略I/O以及其他開銷時間，若分別按先來先服

14、務(wù)（FCFS）、非搶占及搶占的短進(jìn)程優(yōu)先（SPF）、高響應(yīng)比優(yōu)先（HRRN）、時間片輪轉(zhuǎn)（RR，時間片=1）、多級反饋隊(duì)列調(diào)度算法（MFQ，第i級隊(duì)列的時間片=2i-1）進(jìn)行CPU調(diào)度，請給出各進(jìn)程的完成時間、周轉(zhuǎn)時間、帶權(quán)周轉(zhuǎn)時間、平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間，填入下表中（搶占式算法要求畫出調(diào)度時序圖，HRRN算法要求列出調(diào)度時的響應(yīng)比）。30”進(jìn)程到達(dá)時間服務(wù)時間A05B12C39D67算法時間進(jìn)程平均時間ABCDFCFS完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間SPF（非搶占）完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間SPF（搶占）完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間RR（q=1）完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間MFQ（q=

15、2i-1）完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間作業(yè)號到達(dá)時間運(yùn)行時間開始時間完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間調(diào)度依據(jù)平均周轉(zhuǎn)時間為：平均帶權(quán)周轉(zhuǎn)時間為：算法時間進(jìn)程平均時間ABCDFCFS完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間55176316131.4423172.4310.251.97SPF（非搶占）完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間55176323202.221481.149.751.835SPF（搶占）完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間771.432123202.221481.149.251.435RR（q=1）完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間12122.4431.523202.2222162.2912.752.1MFQ（q

16、=2i-1）完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間13132.6652.523202.2221152.1413.252.365作業(yè)號到達(dá)時間運(yùn)行時間開始時間完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間調(diào)度依據(jù)A050551就緒隊(duì)列中只有AB125763RPB=3RPC=11/9=1.22C39716131.44RPC=15/9=1.67RPD=10/7=1.43D671623172.43就緒隊(duì)列中只有D平均周轉(zhuǎn)時間為：10.25平均帶權(quán)周轉(zhuǎn)時間為：1.974、在一個軟實(shí)時系統(tǒng)中有四個周期性任務(wù)，任務(wù)A、B、C、D分別要求每50ms、100ms、200ms、250ms執(zhí)行一次，假定A、B、C、D的執(zhí)行時間分別為35ms、

17、20ms、10ms與x ms，那么要使得這個實(shí)時系統(tǒng)為可調(diào)度的，x的最大值為多少？（要求列出計(jì)算公式）10”答：實(shí)時系統(tǒng)可調(diào)度的條件為： ，其中Ci 表示處理時間，Pi表示周期時間根據(jù)題目所列條件，必須滿足35/50 + 20/100 + 10/200 + x/250<=1，所以x的最大值為12.5ms5、什么是最低松弛度優(yōu)先調(diào)度算法？它采用何種調(diào)度方式？搶占時機(jī)是什么？10”答：LLF算法根據(jù)實(shí)時任務(wù)的松弛度（松弛度 = 必須完成的時間 其本身的運(yùn)行時間 - 當(dāng)前時間）來確定任務(wù)的優(yōu)先級，即任務(wù)的松弛度愈低，其優(yōu)先級愈高。在實(shí)現(xiàn)該算法時，要求系統(tǒng)中有一個按松弛度排序的實(shí)時任務(wù)就緒隊(duì)列。

18、該算法主要用于可搶占調(diào)度方式中，當(dāng)一任務(wù)的最低松弛度減為0時，它便立即搶占CPU，以保證按截止時間的要求完成任務(wù)。6、若有4個周期性任務(wù)，任務(wù)A要求每30ms執(zhí)行一次，執(zhí)行時間為15ms；任務(wù)B要求每50ms執(zhí)行一次，執(zhí)行時間為5ms；任務(wù)C要求每50ms執(zhí)行一次，執(zhí)行時間為15ms；任務(wù)D要求每100ms執(zhí)行一次，執(zhí)行時間為10ms，應(yīng)如何按最低松弛度優(yōu)先算法對它們進(jìn)行CPU調(diào)試？ （要求畫出0-150ms時段的調(diào)度時序圖，并列出每次切換時每個任務(wù)的松弛度）20”對于上面的4個周期性任務(wù)，利用最低松弛度優(yōu)先算法進(jìn)行調(diào)度的情況如圖所示：13014015012011009080706040302

19、01010050B2,C2A6,B4C4A5A4A3A2A1,B1C1,D1B3,C3D2到達(dá)時間必須完成時間A5,B3C3A4A3A2A1B2,C2D1B1,C180651401451251109095503530150松弛度D2=45A5=10B3=20D2=65A4=10D1=10B2=15B2=45C2=35D1=40A2=15B1=15D1=60A1=15B1=45C1=35D1=90B3=5D2=60B3=35C3=25D2=80A4=15B2=5A3=10B2=30D1=25A2=10D1=55B1=30C1=20D1=75D1B3A3C2D2A5C3A4B2A2B1C1A1任務(wù)

20、執(zhí)行8065155140110145125955035301509010、在銀行家算法中，若出現(xiàn)下面的資源分配情況： 30”ProcessAllocationNeedAvailableP00 0 3 20 0 1 21 5 2 2P11 0 0 01 6 5 0P21 3 5 42 3 5 6P30 1 3 20 5 5 2P40 0 1 40 6 5 8試問：1）該狀態(tài)是否安全（要求列出安全性算法檢查表）？ 2）若進(jìn)程P2提出請求Request(1,2,2,2)后，系統(tǒng)能否將資源分配給它（要求根據(jù)分配算法列出檢查過程）？ 3）如果系統(tǒng)立即滿足P2的上述請求，請問，系統(tǒng)是否立即進(jìn)入死鎖狀態(tài)，請

21、說明原因？答：1）利用安全性算法對上面的狀態(tài)進(jìn)行分析，找到了一個安全序列P0、P3、P1、P2、P4，故系統(tǒng)是安全的。資源情況進(jìn)程WorkA B C DNeedA B C DAllocationA B C DWork+AllocationA B C DFinishP0P3P1P2P41 5 2 21 5 5 41 6 8 62 6 8 63 9 13 100 0 1 20 5 5 21 6 5 02 3 5 60 6 5 80 0 3 20 1 3 21 0 0 01 3 5 4 0 0 1 41 5 5 41 6 8 62 6 8 63 9 13 103 9 14 14TrueTrueTrueTrueTrue2）P2發(fā)出請求向量Request(1,2,2,2)后，系統(tǒng)按銀行家算法進(jìn)行檢查：Request2(1,2,2,2)<=Need2(2,3,5,6)Request2(1,2,2,2)<=Available(1,5,2,2)系統(tǒng)先假定可為P2分配資源，并修改Available，Allocation2和Need2向量： Available=（0，3，0，0） Allocation2=(2,5,7,6) Need2=（1，1，3，4）進(jìn)行安全性檢