操作系統(tǒng)教程孫仲秀第4版習題及解答

1、操作系統(tǒng)教程習題及解答 習題一(操作系統(tǒng)概論) 二應用題 有一臺計算機，具有 1MB 內(nèi)存，操作系統(tǒng)占用 200KB，每個進程各 占用 200KB。如果用戶進程等待 I/O 的時間為 80%，若增加 1MB 內(nèi) 存，則 CPU的利用率提高多少 答:設每個進程等待 I/O 的百分比為 P,則 n個進程同時等待 I/O 的概 率是 Pn,當 n 個進程同時等待 I/O 期間 CPU是空閑的 ,故 CPU的利用 率為 1- P n .由題意可知 ,除去操作系統(tǒng) ,內(nèi)存還能容納 4 個用戶進程 , 由于每個用戶進程等待 I/O 的時間為 80%,故: CPU利用率 =1-(80%)4 = 若再增加 1

2、MB內(nèi)存,系統(tǒng)中可同時運行 9個用戶進程 ,此時: CPU利用率 =1-(80%)9= 故增加 1MB 內(nèi)存使 CPU的利用率提高了 47%: 87%/59%=147% 147%-100%=47% 一個計算機系統(tǒng)， 有一臺輸入機和一臺打印機 ,現(xiàn)有兩道程序投入運 行,且程序 A先開始做,程序B后開始運行.程序A的運行軌跡為 :計算 50ms,打印 100ms,再計算 50 ms,打印 100 ms,結(jié)束 .程序 B的運行軌跡 為:計算 50 ms,輸入 80 ms,再計算 100 ms,結(jié)束.試說明(1)兩道程序運 行時,CPU 有無空閑等待若有 ,在哪段時間內(nèi)等待為什么會等待 (2)程 序

3、A,B 有無等待 CPU的情況若有 ,指出發(fā)生等待的時刻 . 答:(1)兩道程序運行期間 ,CPU存在空閑等待 ,時間為 100至 150ms之 間 (2)程序 A 無等待現(xiàn)象 , 但程序 B 有等待 . 程序 B 有等待時間段為 180ms 至 200ms 間. 3.設有三道程序 ,按 A,B,C優(yōu)先次序運行 ,其內(nèi)部計算和 I/O 操作時間 由圖給出 . A B C C11 =30 ms C21 =60 ms C31 =2 0 ms I12 =40 ms I 22 =30 ms I32 =40 ms C13 =10 ms C23 =10 ms C33 =20 ms 試畫出按多道運行的時間關

4、系圖 (忽略調(diào)度執(zhí)行時間 ).完成三道程序 共華多少時間比單道運行節(jié)省了多少時間若處理器調(diào)度程序每次 進行程序轉(zhuǎn)換花時 1 ms,試畫出各程序狀態(tài)轉(zhuǎn)換的時間關系圖 . 答:（圖略） 1）忽略調(diào)度執(zhí)行時間 ,多道運行方式 （搶占式 ）: 搶占式共用去 190 ms,單道完成時間需要 260 ms,節(jié)省 70 ms 忽略調(diào)度執(zhí)行時間 ,多道運行方式 （非搶占式 ）: 非搶占式共用去 180 ms,單道完成時間需要 260 ms,節(jié)省 80 ms 2）（略） 7. 單道時 CPU的利用率為：（ 19080）/190 多道時 CPU的利用率為：（ 14030）/140=% 11. 應時鐘中斷頻率為 6

5、0HZ，所以時鐘頻率為： 1/6050/3 ms. 在每 個時鐘周期 CPU花 2ms 執(zhí)行中斷任務。所以 CPU用于時鐘中斷處 理的時間比率為： 2/（50/3）=12% 習題二（處理器管理） 二應用題 下列指令中哪些只能在核心態(tài)運行 讀時鐘日期；（ 2）訪管指令；（ 3）設時鐘日期；（ 4）加載特殊 寄存器；（ 6）改變存儲器映象圖；（ 7）啟動 I/O 指令。 答: （3）,（4）,（5）,（6）,（7）. 8對某系統(tǒng)進行監(jiān)測后表明平均每個進程在 I/O 阻塞之前的運行時 間為 T。一次進程切換的系統(tǒng)開銷時間為 S。若采用時間片長度為 Q 的時間片輪轉(zhuǎn)法，對下列各種情況算出 CPU利用率

6、。 1) Q=無窮大2)QT 3)SQT CPU利用率 = T/(T+S) 3)SQ0 9.按照最短作業(yè)優(yōu)先的算法可以使平均相應時間最短 5)Q 接近于 X 的取值不 定，按照以下情況討論： x=3 次序為 x , 3 , 5 , 6 , 9 3x=5 次序為 3 , x , 5 , 6 , 9 5x=6 次序為 3 , 5 , x , 6 , 9 6x=9 次序為 3 , 5 , 6 , x , 9 9x 次序為 3 , 5 , 6 , 9 , x 11有 5個批處理作業(yè) A到 E均已到達計算中心，其運行時間分別 為 10，6， 2，4 和 8 分鐘；各自的優(yōu)先級分別規(guī)定為 3，5，2， 1

7、 和 4 ，這里 5 為最高級。若不考慮系統(tǒng)切換開銷，計算出平均作業(yè) 周轉(zhuǎn)時間。（ 1）按 FCFS（按 A，B，C，D，E）；（ 2）優(yōu)先級調(diào)度 算法，（ 3）時間片輪轉(zhuǎn)法 答: FCFS調(diào)度算法 執(zhí)行次序 執(zhí)行時間 等待時間 周轉(zhuǎn)時間 帶權周轉(zhuǎn)時間 A 10 0 10 1 3 B 6 10 16 5 C 2 16 18 9 2 D 4 18 22 1 E 8 22 30 4 作業(yè)平均周轉(zhuǎn)時間 T=(10+16+18+22+30)/5= 作業(yè)平均帶權周轉(zhuǎn)時間 W=(1+9+/5= 優(yōu)先級調(diào)度算法 執(zhí)行次序 執(zhí)行時間 等待時間 周轉(zhuǎn)時間 帶權周轉(zhuǎn)時間 A 6 0 6 1 B 8 6 14 C

8、10 14 24 D 2 24 26 13 E 4 26 30 作業(yè)平均周轉(zhuǎn)時間 作業(yè)平均帶權周轉(zhuǎn)時間 T=(6+14+24+26+30)/5=20 W=(1+13+/5= 時間片輪轉(zhuǎn)法 按次序 ABCDEABDEABEAE輪A轉(zhuǎn)執(zhí)行 . 作業(yè) 執(zhí)行時間 等待時間 周轉(zhuǎn)時間 帶權周轉(zhuǎn)時間 A 10 20 30 3 B 6 16 22 C 2 4 6 3 D 4 12 16 4 E 8 20 28 3. 5 作業(yè)平均周轉(zhuǎn)時間 T=(30+22+6+16+28)/5= 作業(yè)平均帶權周轉(zhuǎn)時間 W=(3+3+4+/5= 13請你設計一種先進的計算機體系結(jié)構，它使用硬件而不是中斷 來完成進程切換， 則

9、CPU需要哪些信息請描述用硬件完成進程切換 的工作過程。 答:該計算機有一個專用硬件寄存器 ,它始終存放指向當前運行進程 的 PCB的指針 . 當系統(tǒng)中發(fā)生了一個事件 ,如 I/O 結(jié)束事件 ,CPU便可 把運行進程的上下文保存到專用硬件寄存器指針指向的PCB中保護 起來 ,然后,CPU轉(zhuǎn)向中斷向量表 ,找到設備中斷處理程序入口 ,讓專用 硬件寄存器指針指向 （設備）中斷服務例程 ,于是 ,便可啟動中斷服務 例程工作 . 15單道批處理系統(tǒng)中，下列三個作業(yè)采用先來先服務調(diào)試算法和 最高響應比優(yōu)先算法進行調(diào)試， 哪一種算法性能較好， 請完成下表： 作 業(yè) 提交時 間 運行時 間 開始 時間 完成

10、 時間 周轉(zhuǎn) 時間 帶權周轉(zhuǎn) 時間 1 10：00 2：00 2 10：10 1：00 3 10：25 0：25 平均作業(yè)周轉(zhuǎn)時間 = 平均作業(yè)帶權周轉(zhuǎn)時間 W= FIFO 作 提交 運行 開始時 完成時 周轉(zhuǎn) 帶權周轉(zhuǎn) 業(yè) 時間 時間 間 間 時間 時間 1 10：00 2： 00 10:00 12:00 2 120/120 2 10：10 1： 00 12:00 13:00 2:50 145/60 3 10：25 0： 25 13:00 13:25 3 180/25 平均作業(yè)周轉(zhuǎn)時間 = 平均作業(yè)帶權周轉(zhuǎn)時間 W= HRN 作 提交 運行 開始時 完成時 周轉(zhuǎn) 帶權周轉(zhuǎn) 業(yè) 時間 時間 間

11、 間 時間 時間 1 10：00 2：00 10:00 12:00 2 120/120 2 10：10 1：00 12:25 13:25 3:15 195/60 3 10：25 0：25 12:00 12:25 2 120/25 平均作業(yè)周轉(zhuǎn)時間 = 平均作業(yè)帶權周轉(zhuǎn)時間 W= 可見 HRRF比 FIFO要好 . 19有一個具有兩道作業(yè)的批處理系統(tǒng)，作業(yè)調(diào)度采用短作業(yè)優(yōu)先 的調(diào)試算法，進程調(diào)度采用優(yōu)先數(shù)為基礎的搶占式調(diào)度算法，在下 表所示的作業(yè)序列，作業(yè)優(yōu)先數(shù)即為進程優(yōu)先數(shù)，優(yōu)先數(shù)越小優(yōu)先 級越高。 作業(yè)名 到達時間 估計運行時間 優(yōu)先數(shù) A 10：00 40分 5 B 10：20 30分 3

12、 C 10：30 50分 4 D 10：50 20分 6 每個作業(yè)運行將經(jīng)過兩個階段 :作業(yè)調(diào)度（SJF算法）和進程調(diào)度 （優(yōu) 先數(shù)搶占式 ）.另外,批處理最多容納 2道作業(yè) ,更多的作業(yè)將在后備隊 列等待. 作業(yè) 進入內(nèi)存時間差 運行結(jié)束時間 A 10:00 11:10 B 10:20 10:50 C 11:10 12:00 D 10:50 12:20 各作業(yè)周轉(zhuǎn)時間為 :作業(yè) A 70, 作業(yè) B 30, 作業(yè) C 90, 作業(yè) D 90. 平均作業(yè)周轉(zhuǎn)時間為 70 分鐘 24.實時任務可調(diào)度應滿足： 35/50+20/100+10/300+x/2501 x250(1-28/30)=250

13、*= 習題三（并發(fā)進程） 有三個并發(fā)進程： R 負責從輸入設備讀入信息塊， M 負責對信息塊 應用題 加工處理； P 負責打印輸出信息塊。今提供： 一個緩沖區(qū)，可放置 K 個信息塊； 二個緩沖區(qū)，每個可放置 K 個信息塊； 試用信號量和 P，V 操作寫出三個進程正確工作的流程 答: var B:array0,k-1 of item; sread:semaphore:=k; smanage:semaphore:=0; swrite:semaphore:=0; rptr:integer:=0; mptr:inerger:=0; wptr:inerger:=0; x:item cobegin pro

14、cess reader; begin L1: reader a message P(sread);V(smanage); Brptr:=x;Goto L1; rptr=(rptr +1) End; into x; mod k; process manager; V(swrite) V(stread); begin Goto L2; Print the message in L2: P(smanage); End; x; x=Bmptr; Process writer; Goto L3; mptr=(mptr+1) Begin End; mod k; L3:P(swrite); manager

15、the x=Bwptr; message in x; wptr=(wptr+1) mod Bmptr:=x k; Coend var A,B:array0,k-1 of intm; sput1:semaphore:=k; sput2:semaphore:=k; sget1:semaphore:=0; sget2:semaphore:=0; put1:integer:=0; put2:integer:=0; get1:integer:=0; get2:integer:=0; cobegin process reader; Begin Process writer; begin L1: read

16、a message into x; P(sput1); Aput1=x; Put1:=( put1+1) mod k; V(sget1); Goto L1; End; L2:P(sget1); X:=Aget1; Get1:=(get1+1) mod k; V(sput1) Manage the message into x; P(sput2); Bput2:=x Put2:=(put2+1) mod k; V(sget2); Goto L2; End; Begin L3:P(sget2); X:=Bget2; Get2:=(get2+1) mod k; V(sput2); Print the

17、 message in x; Goto L3; End; coend Process manager; 3.有兩個優(yōu)先級相同的進程 P1 和 P2，各自執(zhí)行的操作如下，信號 量 S1和 S2初值均為 0。試問 P1,P2并發(fā)執(zhí)行后， x,y,z 的值各為多 少 P2: P1: y:=1; 1 x:=1; 5 y:=y+3; 2 x:=x+5; 6 V(S1); P(S1); z:=y+1; 3 x:=x+y; 7 P(S2); V(S2); y:=z+y; 4 z:=z+x; 8 end. end. begin begin 1,2,5和 6是不相交語句，可以任何次序交錯執(zhí)行，而結(jié)果是唯一的。

18、接著無論系統(tǒng)如何調(diào)度進程并發(fā)執(zhí)行，當執(zhí)行到語句 7 時，可以得 到 x=10， y=4。按 Bernstein 條件，語句 3 的執(zhí)行結(jié)果不受語句 7 的 影響，故語句 3 執(zhí)行后得到 z=25。最后，語句 4 和 8 并發(fā)執(zhí)行，最 后結(jié)果為： 答 語句 4 先執(zhí)行 :x=10,y=9,z=15. 語句 8 先執(zhí)行 x=10， y=19，z=15 5.在一個盒子里，混裝了數(shù)量相等的黑白圍棋子?，F(xiàn)在用自動分揀 系統(tǒng)把黑子，白子分開，設分揀系統(tǒng)有二個進程 P1和P2，其中 P1 揀白子，P2 揀黑子。規(guī)定每個進程每次揀一子； 當一個進程在揀時， 不允許另一個進程去揀；當一個進程揀了一子時，必須讓另

19、一個進 程去揀。試寫出兩個進程 P1和 P2 能并發(fā)正確執(zhí)行的程序。 答:實質(zhì)上是兩個進程的同步問題 ,設信號量 S1 和 S2 分別表示可 揀白子和黑子 ,不失一般性 ,若令先揀白子 . Var S1,S2:semaphore; S1:=1,S2:=0; Cogegin process P1 begin repeat P(S1); 揀白子 V(S2); Until false; End Process p2 Begin Repeat P(S2); 揀黑子; V(S1); Until false; End coend. 17吸煙者問題 答：用信號量和 P，V 操作 Var s，s1， s2，

20、s3；semaphore； S:=1;s1=s2=s3=0; Flag1,flag2,flag3: Boolean; Flag1=flag2=flag3=TRUE ; Cobegin Process 供應者 Begin Repeat P（S）； 取兩樣香煙原料放桌上，由 flag i 標記； flag1/flag2/flag3 分別代 表煙草，紙、火 If flag2 、供應紙和火 Else if flag1 供應草和火 Else v(s3); Untile false ; end Process 吸煙者 1 Begin Repeat P(s1) 取原料，做香煙； (S); 吸香煙； Unti

21、le false; Process 吸煙者 2 Begin Repeat P(s2) 取原料，做香煙； （S） 吸香煙； Untile false; Process 吸煙者 3 Begin Repeat P（s3） 取原料，做香煙； （S）; 吸香煙； Untile false; Coend 27. 答： （1） 系統(tǒng)處于安全狀態(tài)，存在安全序列： p0,p3,p4,p1,p2; 不能分配，否則系統(tǒng)會處于不安全狀態(tài)。 33. （）系統(tǒng)四個進程需要使用的資源數(shù)為各臺， 各臺?？梢娰Y源數(shù)不足。同時各進程申請資源在先，有可能產(chǎn) 生死鎖發(fā)生的四個條件，故系統(tǒng)可能產(chǎn)生死鎖。 （）當三個進程執(zhí)行完申請資源，

22、開始申請資源 時，第四個進程會因沒有資源而被阻塞。當三個進程執(zhí)行完 申請資源后，系統(tǒng)還剩個資源。而這三個進程因執(zhí)行申 請第二個資源而全部被阻塞，系統(tǒng)進入死鎖。 習題四（存儲管理） 二應用題 3一個頁式存儲管理系統(tǒng)使用 FIFO， OPT和 LRU頁面算法，如果 一個作業(yè)的頁面走向為 4，3，2，1， 4，3，5，4，3，2，1，5。當 分配給該作業(yè)的物理塊數(shù)分別為 3和 4時，試計算訪問過程中發(fā)生 的缺頁中斷次數(shù)和缺頁中斷率。 答:作業(yè)的物理塊數(shù)為 3塊時,使用 FIFO為9次,9/12=75% 使用 LRU為 10 次 ,10/12=83% 使用 OPT為 7 次,7/12=58% 作業(yè)的物

23、理塊數(shù)為 4塊時,使用 FIFO為 10次,10/12=83% 使用 LRU為 8 次,80/12=66% 使用 OPT為 6 次,6/12=50% 其中 ,出現(xiàn)了 Belady現(xiàn)象,增加分給作業(yè)的內(nèi)存塊數(shù) ,反使缺頁中斷率 上升. 4.在可變分區(qū)存儲管理下，按地址排列的內(nèi)存空閑區(qū)為： 10K，4K， 20K，18K，7K，9K，12K，和 15K。對于下列的連續(xù)存儲區(qū)的請求： （ 1）12K，10K， 9K。（ 2）12K，10K，15K，18K 試問：使用首次 造應算法，最佳造應算法，最差適應算法和下次適應算法，哪個空 閑區(qū)被使用 答:空閑分區(qū)如圖所示 : 分區(qū)號 分區(qū)長 1 10KB 2

24、 4 KB 3 20 KB 4 18 KB 5 7 KB 6 9 KB 7 8 12 KB 15 KB 首次造應算法 12KB選中分區(qū) 3,這時分區(qū) 3 還剩選中分區(qū) 1.恰好分配故應刪去分區(qū) 1. 9KB 選中分區(qū) 4,這時分區(qū) 4 還剩 9KB. 最佳造應算法 12KB選中分區(qū) 7, 恰好分配故應刪去分區(qū) 7. 10KB選中分區(qū) 1.恰 好分配故應刪去分區(qū) 1. 9KB選中分區(qū) 6.恰好分配故應刪去分區(qū) 6. 3) 最差適應算法 12KB選中分區(qū) 3,這時分區(qū) 3還剩 8KB. 10KB選中分區(qū) 4, 這時分 區(qū) 4 還剩 8KB. 9KB 選中分區(qū) 8,這時分區(qū) 8 還剩 6KB. 4)

25、 下次適應算法 12KB選中分區(qū) 3,這時分區(qū) 3還剩 8KB. 10KB選中分區(qū) 4, 這時 分區(qū) 4還剩 8KB. 9KB選中分區(qū) 6.恰好分配故應刪去分區(qū) 6. (2)原理分區(qū)情況同上圖 1) 首次造應算法 12KB選中分區(qū) 3,這時分區(qū) 3 還剩選中分區(qū) 1.恰好分配故應刪去分區(qū) 1. 15KB選中分區(qū) 4,這時分區(qū) 4 還剩 3KB.最后無法滿足 18KB的申請, 應該等待 . 2）最佳造應算法 12KB選中分區(qū) 7, 恰好分配故應刪去分區(qū) 7. 10KB選中分區(qū) 1.恰 好分配故應刪去分區(qū)選中分區(qū) 8.恰好分配故應刪去分區(qū) 8. 18KB 選 中分區(qū) 4.恰好分配故應刪去分區(qū) 4.

26、 3）最差適應算法 12KB選中分區(qū) 3,這時分區(qū) 3 還剩 8KB. 10KB選中分區(qū) 4, 這時分 區(qū) 4 還剩 8KB. 15KB 選中分區(qū) 8, 恰好分配故應刪去分區(qū) 8. 最后無 法滿足 18KB的申請,應該等待 . 4）下次適應算法 12KB選中分區(qū) 3,這時分區(qū) 3還剩 8KB. 10KB選中分區(qū) 4, 這時 分區(qū) 4還剩 8KB. 15KB選中分區(qū) 8, 恰好分配故應刪去分區(qū) 8. 最后無法滿足 18KB的 申請 ,應該等待 . 5，給定內(nèi)存空閑分區(qū)，按地址從小到大為： 100K， 500K，200K， 300K 和 600K?，F(xiàn)有用戶進程依次分別為 212K，417K，112

27、K和 426K， （ 1）分別用 first-fit,best-fit 和 worst-fit 算法將它們裝入到內(nèi)存的哪 個分區(qū)（ 2）哪個算法能最有效利用內(nèi)存 答 :按題意地址從小到大進行分區(qū)如圖所示 : 分區(qū)號 分區(qū)長 1 100KB 2 500KB 3 200KB 4 300KB 5 600KB (1) 1) first-fit 212KB選中分區(qū) 2 ,這時分區(qū) 2 還剩 288KB. 417KB選中 分區(qū) 5, 這時分區(qū) 5還剩 183KB. 112KB選中分區(qū) 2 ,這時分區(qū) 2還剩 176KB. 426KB無分區(qū)能滿足 ,應該等待 . 2) best-fit 212KB選中分區(qū)

28、4 ,這時分區(qū) 4還剩 88KB. 417KB選中分 區(qū)2, 這時分區(qū) 2還剩83KB. 112KB選中分區(qū) 3 ,這時分區(qū) 3還剩88KB. 426KB選中分區(qū) 5 ,這時分區(qū) 5 還剩 174KB. 3) worst-fit212KB選中分區(qū) 5 ,這時分區(qū) 5還剩 388KB. 417KB選 中分區(qū) 2, 這時分區(qū) 2還剩83KB. 112KB選中分區(qū) 5 ,這時分區(qū) 5還 剩 176KB. 426KB無分區(qū)能滿足 , 應該等待 . (2)對于該作業(yè)序列 , best-fit 算法能最有效利用內(nèi)存 7內(nèi)存有 3 個和 4 個空閑頁框的情況下，頁面替換次數(shù)為 9 次和 10 次，出現(xiàn)了 B

29、elady 現(xiàn)象。 9某計算機有 cache,內(nèi)存，輔存來實現(xiàn)虛擬存儲器。如果數(shù)據(jù)在 cache 中，訪問它需要 20ns；如果在內(nèi)存但不在 cache ，需要 60ns 將其裝入緩存，然后才能訪問；如果不在內(nèi)存而在輔存，需要不是 12ms將其讀入內(nèi)存，然后，用 60 ns再讀入 cache，然后才能訪問。 假設 cache 命中率為，內(nèi)存命中率為，則數(shù)據(jù)平均訪問時間是多少 (ns) 答:20*+(60+20)*+(20+60+12000)*=506ns 18. 答： t1 時刻的工作集為： 1，2，3，6，7，8，9 t2 時刻的工 作集為： 3，4 20答：虛地址 0AC5H對應的物理地址為： 12C5H。而執(zhí)行虛地址 1AC5H會發(fā)現(xiàn)頁表中尚未有分配的頁框而發(fā)生缺頁中斷，由系統(tǒng)另 行分配頁框。 21答：( 1)FIFO 淘汰 page 2 LRU 淘汰 page 1 二次機會淘汰 oage 0 習題五 5. 對磁盤存在下面五個請求 請求 柱面號 磁頭號 扇區(qū)號 1 7 2 8 2 7 2 5 3 7 1 2 4 30 5 3 5 3 6