最近恰好在學習操作系統(tǒng)，所以分享一下操作系統(tǒng)的題解，(有些是搜題得來的結(jié)果，就可能直接用啦,還有些是手畫的圖，我字丑，不要嫌棄哈哈哈哈)。最后整理,碼字不易，幫忙點個贊哈哈哈，如果有錯誤的，可以在評論區(qū)交流，請原諒我的錯誤！

第一章 操作系統(tǒng)概論

1.有一臺計算機，具有IMB 內(nèi)存，操作系統(tǒng)占用200KB ，每個用戶進程各占200KB 。如果用戶進程等待I/O 的時間為80 % ，若增加1MB 內(nèi)存，則CPU 的利用率提高多少？

答：
設(shè)每個進程等待I/O 的百分比為P ，則n 個進程同時等待刀O 的概率是Pn ，當n 個進程同時等待I/O 期間CPU 是空閑
的，故CPU 的利用率為1-Pn。由題意可知，除去操作系統(tǒng)，內(nèi)存還能容納4 個用戶進程，由于每個用戶進程等待I/O
的時間為80 % , 故：
CPU利用率＝l-（80%)4 = 0.59 
若再增加1MB 內(nèi)存，系統(tǒng)中可同時運行9 個用戶進程，此時：
cPu 利用率＝l-（1-80%)9 = 0.87 
故增加IMB 內(nèi)存使CPU 的利用率提高了: 
87％ / 59％ - 100% = 47% 

2.一個計算機系統(tǒng)，有一臺輸入機和一臺打印機，現(xiàn)有兩道程序投入運行，且程序A 先開始做，程序B 后開始運行。程序A 的運行軌跡為：計算50ms 、打印100ms 、再計算50ms 、打印100ms ，結(jié)束。程序B 的運行軌跡為：計算50ms 、輸入80ms 、再計算100ms ，結(jié)束。試說明（1 ）兩道程序運行時，CPU有無空閑等待？若有，在哪段時間內(nèi)等待？為什么會等待？( 2 ）程序A 、B 有無等待CPU 的情況？若有，指出發(fā)生等待的時刻。

答：畫出兩道程序并發(fā)執(zhí)行圖如上:
（1）兩道程序運行期間，CPU存在空閑等待，時間為100ms - 150ms之間
（2）程序A無等待現(xiàn)象，但程序B有等待。程序B有等待時間段為180ms - 200ms

3.設(shè)有三道程序，按A 、B 、C優(yōu)先次序運行，其內(nèi)部計算和UO操作時間由圖給出:

試畫出按多道運行的時間關(guān)系圖（忽略調(diào)度執(zhí)行時間）。完成三道程序共花多少時間？比單道運行節(jié)省了多少時間？若處理器調(diào)度程序每次進行程序轉(zhuǎn)換化時lms , 試畫出各程序狀態(tài)轉(zhuǎn)換的時間關(guān)系圖。

答：① 多道運行方式（搶占式）:（如下圖）(ps:搶占式指的是，此時B進程占著CPU在運行，但是A進程優(yōu)先級更高的話，會搶占B)
結(jié)果： 搶占式共用去190ms ，單道完成需要260ms （30+40+10+60+30+10+20+40+20 = 260ms），節(jié)省70ms 。

多道運行方式（非搶占式）:（如下圖）
結(jié)果：非搶占式共用去180ms ，單道完成需要260ms ，節(jié)省80ms 。

②調(diào)度執(zhí)行時間1ms , 多道運行方式（搶占式）與多道運行方式（非搶占式）如下圖：

4.在單CPU 和兩臺 I/O( I1 , 12 ）設(shè)備的多道程序設(shè)計環(huán)境下，同時投入三個作業(yè)運行。它們的執(zhí)行軌跡如下：

Jobl : I2 ( 30ms ）、CPU ( 10ms ）、I1 ( 30ms ）、CPU ( 10ms ）、I2 ( 20ms )

Job2 : I1 ( 20ms ）、CPU ( 20ms ）、I2 ( 40 ms )

JOb3 : CPU ( 30ms ）、I1 ( 20ms ）、CPU ( 10ms ）、I1 ( 10ms )

如果CPU 、I1 和I2 都能并行工作，優(yōu)先級從高到低為Jobl 、Job2 和Job3 ，優(yōu)先級高的作業(yè)可以搶占優(yōu)先級低的作業(yè)的CPU ，但不搶占I1和I2 。試求：( l ）每個作業(yè)從投入到完成分別所需的時間。（2 ）從投入到完成CPU 的利用率。（3 ）I2設(shè)備利用率。

答：畫出三個作業(yè)并行工作圖如下:

( 1 ) Job1 從投入到運行完成需110ms , Job2 從投入到運行完成需90ms , Job3 從投入到運行完成需110ms. 
( 2 ) 從投入到完成CPU 的利用率:CPU 空閑時間段為：60ms 至70ms , 80ms 至90ms , 100ms 至110ms 。所以CPU 利用率為（110-30）/10 = 72.7 ％。
( 3 ) I2設(shè)備利用率: 設(shè)備I2 空閑時間段為：30ms 至50ms，故I2的利用率為(110-20) / 110 = 81.8 ％。

5.在單CPU 和兩臺I/O( I1 , 12 ）設(shè)備的多道程序設(shè)計環(huán)境下，同時投入三個作業(yè)運行。它們的執(zhí)行軌跡如下：

Jobl : I2 ( 30ms ）、CPU ( 10rns ）、I1 ( 30ms ）、CPU ( 10ms )

Job2 : I1 ( 20ms ）、CPU ( 20ms ）、I2 ( 40ms )

Job3 : CPU ( 30ms ）、I1 ( 20ms )

如果CPU 、I1和I2 都能并行工作，優(yōu)先級從高到低為Job1 、Job2和Job3 ，優(yōu)先級高的作業(yè)可以搶占優(yōu)先級低的作業(yè)的CPU 。

試求：

( l ）每個作業(yè)從投入到完成分別所需的時間．

( 2 ）每個作業(yè)投入到完成CPU 的利用率。

( 3 ）I/0設(shè)備利用率。

答：畫出三個作業(yè)并行工作圖如下（圖中著色部分為作業(yè)等待時間）:
( 1 ) Job1從投入到運行完成需80ms , Job2 從投入到運行完成需90ms , Job3 從投入到運行完成需90ms 。
( 2 ) CPU 空閑時間段為：60ms 至70ms , 80ms 至90ms 。所以CPU利用率為( 90-20 ) / 90 = 77.78 ％。
( 3 ）設(shè)備I1 空閑時間段為：20ms 至40ms ，故I1 的利用率為（90-20 ) / 90 = 77 . 78 ％。設(shè)備I2 空閑時間段為：30ms 至50ms ，故I2 的利用率為（90-20 ) / 90=77.78 ％。

6. 為第五題的條件，試求：（1）每個作業(yè)從投入到完成所需要的時間。 （2）每個作業(yè)從投入到完成CPU的利用率 （3）I/O設(shè)備的利用率。

答：畫出三個作業(yè)并行工作圖如下（圖中著色部分為作業(yè)等待時間）:
( 1 ) Job1從投入到運行完成需80ms , Job2 從投入到運行完成需90ms , Job3 從投入到運行完成需90ms 。
( 2 ) CPU 空閑時間段為：60ms 至70ms , 80ms 至90ms 。所以CPU利用率為( 90-20 ) / 90 = 77.78 ％。
( 3 ）設(shè)備I1 空閑時間段為：20ms 至40ms ，故I1 的利用率為（90-20 ) / 90 = 77 . 78 ％。設(shè)備I2 空閑時間段為：30ms 至50ms ，故I2 的利用率為（90-20 ) / 90=77.78 ％。

7. 若內(nèi)存中有3 道程序A 、B 、C ，它們按A 、B 、C 優(yōu)先次序運行。各程序的計算軌跡為：

A ：計算（20 ）、I/O( 30 ）、計算（10 )

B ：計算（40 ）、I/O( 20 ）、計算（10 )

c ：計算（10 ）、I/O ( 30 ）、計算（20 )

如果三道程序都使用相同設(shè)備進行I/O（即程序用串行方式使用設(shè)備，調(diào)度開銷忽略不計）。試分別畫出單道和多道運行的時間關(guān)系圖。兩種情況下，CPU 的平均利用率各為多少？

答：

8. 若內(nèi)存中有3 道程序A 、B 、C ，優(yōu)先級從高到低為A 、B 和C ，它們單獨運行時的CPU 和I/O 占用時間為：

如果三道程序同時并發(fā)執(zhí)行，調(diào)度開銷忽略不計，但優(yōu)先級高的程序可中斷優(yōu)先級低的程序，優(yōu)先級與I/O 設(shè)備無關(guān)。試畫出多道運行的時間關(guān)系圖，并問最早與最遲結(jié)束的程序是哪個？每道程序執(zhí)行到結(jié)束分別用了多少時間？計算三個程序全部運算結(jié)束時的CPU 利用率？

答：畫出三個作業(yè)并發(fā)執(zhí)行的時間圖，
( l ) 最早結(jié)束的程序為B ，最后結(jié)束的程序為C 。 
( 2 ) 程序A 為250ms 。程序B 為220ms 。程序C 為310ms 。 
( 3 ) CPU 利用率為( 310 - 120 ) / 310 = 61.3 % 

9. 在單機系統(tǒng)中，有同時到達的兩個程序A、B，若每個程序單獨運行，則使用CPU、DEV1（設(shè)備1）、DEV2（設(shè)置2）的順序和時間如下表所示：

給定下列條件：

（1）DEV1和DEV2是不同的I/O設(shè)備，他們能夠同時工作

（2）程序B的優(yōu)先級高于程序A。但是當程序A占用CPU時，即使程序B需要使用CPu，也不能打斷A的程序而等待

（3）氮肥施用CPU之后控制轉(zhuǎn)向I/O設(shè)備，或者使用I/O設(shè)之后控制轉(zhuǎn)向CPU，有控制程序執(zhí)行中斷處理，但是這段中斷處理時間可以忽略不計。、

試解答下列問題：

① 那個程序先結(jié)束

② 程序全部執(zhí)行結(jié)束需要多長時間

③ 程序全部執(zhí)行結(jié)束完畢時，CPU的利用率是多少？

④ 程序A等待CPU的累計時間是多少？

⑤ 程序B等待CPU的累計時間是多少？

答： 運行時間如上圖所示，
① B先結(jié)束
② 234ms
③ (234 - 25 - 19 - 10 ) / 234 ? 100% = 77.35%
④ 0ms - 20ms 和 199 ms - 214 ms 累計時長為 35ms
⑤ 110 ms - 119 ms 和 159 ms - 169 ms 累計時長為 19ms

10. 有兩個程序，A 程序按順序使用：( CPU)10 秒、（設(shè)備甲）5 秒、（CPU）5 秒、（設(shè)備乙）10 秒、（CPU）10 秒。B程序按順序使用：（設(shè)備甲）10 秒、（CPU）10 秒、（設(shè)備乙）5 秒、( CPU)5 秒、（設(shè)備乙）10 秒。在順序環(huán)境下先執(zhí)行A ，再執(zhí)行B ，求出總的CPU 利用率為多少？

答： CPU利用率=CPU運行時間/程序運行時間=CPU有效工作時間/（CPU有效工作時間+CPU空閑等待時間）= (10 + 5 + 10 + 10 + 5) / (10 + 5 + 5 + 10 + 10 + 10 + 10 + 5 + 5 + 10) = 50 % 

11. 在某計算機系統(tǒng)中,時鐘中斷處理程序每次執(zhí)行時間為2ms(包括進程切換開銷)。假設(shè)中斷頻率為60Hz,試問CPU用于時鐘中斷處理的時間比率為多少?

答：1/60 s = 50/3 ms 
CPU用于時鐘中斷處理的時間比率: 2 / (50 / 3) = 12% 

12. 操作系統(tǒng)：在下列例子中，區(qū)分“時分復(fù)用共享”與“空分復(fù)用共享”，并對其進行簡單解釋。

1、住宅區(qū)的土地2、個人計算機3、教室的黑板4、公共汽車上的椅子5、UNIX系統(tǒng)中的單用戶文件6、分時系統(tǒng)中的打印機7、C/C++運行時的系統(tǒng)堆棧

（2）（4）（5）（6）為時分復(fù)用共享，（1）（3）（7）為空分復(fù)用共享。

第二章 處理器管理

1.下列指令中哪些只能在核心態(tài)運行？

(l）讀時鐘日期；(2）訪管指令；(3）設(shè)時鐘日期；(4）加載PSW; (5）置特殊寄存器：(6）改變存儲器映象圖；(7）啟動I/O指令。

答：( 3 ) , ( 4 ) , ( 5 ), ( 6 ) , ( 7 ) .

2. 假設(shè)有一種低級調(diào)度算法是讓“最近使用處理器較少的進程”運行，試解釋這種算法對“I/O 繁重”型作業(yè)有利，但并不是永遠不受理“處理器繁重”型作業(yè)。

答：因為I/O繁忙型作業(yè)忙于I/O，所以它CPU 用得少，按調(diào)度策略能優(yōu)先執(zhí)行。同樣原因一個進程等待CPU 足夠久時，由于它是“最近使用處理器較少的進程”，就能被優(yōu)先調(diào)度，故不會饑餓。

3. 并發(fā)進程之間有什么樣的相互制約關(guān)系？下列日常生活中的活動是屬哪種制約關(guān)系：(1）踢足球，(2）吃自助餐，(3）圖書館借書，(4）電視機生產(chǎn)流水線工序。

答：并發(fā)進程之間的基本相互制約關(guān)系有互斥和同步兩種。其中（1）、（3）為互斥問題．(2）、(4）為同步問題。

4. 在按動態(tài)優(yōu)先數(shù)調(diào)度進程的系統(tǒng)中，每個進程的優(yōu)先數(shù)需定時重新計算。在處理器不斷地在進程之間交替的情況下，重新計算進程優(yōu)先數(shù)的時間從何而來？

答：許多操作系統(tǒng)重新計算進程的優(yōu)先數(shù)在時鐘中斷處理例程中進行，由于中斷是隨機碰到哪個進程，就插入哪個進程中運行處理程序，并把處理時間記在這個進程的賬上。

5. 若后備作業(yè)隊列中等待運行的同時有三個作業(yè)J1 、J2、J3 ，已知它們各自的運行時間為a 、b 、c，且滿足a < b ＜c，試證明采用短作業(yè)優(yōu)先算法調(diào)度能獲得最小平均作業(yè)周轉(zhuǎn)時間。

答：采用短作業(yè)優(yōu)先算法調(diào)度時，三個作業(yè)的總周轉(zhuǎn)時間為：
Tl = = a + ( a +b ) + ( a + b + c ) = 3a + 2b + c ①
若不按短作業(yè)優(yōu)先算法調(diào)度，不失一般性，設(shè)調(diào)度次序為：J2 、J1 、J3 。則三個作業(yè)的總周轉(zhuǎn)時間為：
T2=b＋(b＋a ) ＋(b＋a + c ) = 3b + 2a + c ②
令②-① 式得到：
T2 - Tl = b- a> 0 
可見，采用短作業(yè)優(yōu)先算法調(diào)度才能獲得最小平均作業(yè)周轉(zhuǎn)時間。

6.若有一組作業(yè)J1 ，… ，Jn ，其執(zhí)行時間依次為S1 ，… , Sn 。如果這些作業(yè)同時到試找出一種作業(yè)調(diào)度算法到達系統(tǒng)，并在一臺單CPU 處理器上按單道方式執(zhí)行。使得平均作業(yè)周轉(zhuǎn)時間最短。

答：首先，對n 個作業(yè)按執(zhí)行時間從小到大重新進行排序，則對n 個作業(yè)：J1 ' ，… ，Jn , 創(chuàng)門的運行時間滿足：S1≤S2 ≤……≤S (n-l ) ≤ Sn ’。那么有：

由于任何調(diào)度方式下，S1' + S2' + S3'＋…＋Sn’為一個確定的數(shù)，而當S1 ’≤S2 ’≤…≤ S( n - 1 ) ’≤Sn ’時才有：0*S1+1*S2+2*S3+…（n-1）Sn的值最大，也就是說，此時T 值最小。所以，按短作業(yè)優(yōu)先調(diào)度算法調(diào)度時，使得平均作業(yè)周轉(zhuǎn)時間最短。

7.假定執(zhí)行表中所列作業(yè)，作業(yè)號即為到達順序，依次在時刻0 按次序1 、2 、3 、4 、5 進入單處理器系統(tǒng)。

（1）分別用先來先服務(wù)調(diào)度算法、時間片輪轉(zhuǎn)算法、短作業(yè)優(yōu)先算法及非強占優(yōu)先權(quán)調(diào)度算法算出各作業(yè)的執(zhí)行先后次序（注意優(yōu)先權(quán)高的數(shù)值?。?

（2）計算每種情況下作業(yè)的平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間。

答： （1）
先來先服務(wù)算法： 1-2-3-4-5
時間片輪轉(zhuǎn)算法： (設(shè)時間片為1) 1-2-3-4-5-l-3-5-1-5-1-5-1-5-1-l-l-1-1
短作業(yè)優(yōu)先算法: 2-4-3-5-1
非強占優(yōu)先權(quán)調(diào)度算法： 4-1-3-5-2
（2） 
平均周轉(zhuǎn)時間：
先來先服務(wù)算法：(10 + 11 + 13 + 14 + 19) / 5 = 13.4
時間片輪轉(zhuǎn)算法：(19 + 2 + 7 + 4 + 14) / 5  = 9.2
短作業(yè)優(yōu)先算法: (1 + 2 + 4 + 9 + 19) / 5 = 7
非強占優(yōu)先權(quán)調(diào)度算法：(1 + 11 + 13 + 18 + 19) / 5 = 12.4
平均帶權(quán)周轉(zhuǎn)時間：
先來先服務(wù)算法：(10/10 + 11/1 + 13/2 + 14/1 + 19/5) / 5 = 7.26
時間片輪轉(zhuǎn)算法：(19/10 + 2/1 + 7/2 + 4/1 + 14/5) / 5  = 2.84
短作業(yè)優(yōu)先算法: (1/1 + 2/1 + 4/2 + 9/5 + 19/10) / 5 = 1.74
非強占優(yōu)先權(quán)調(diào)度算法：(1/1 + 11/10 + 13/2 + 18/5 + 19/1) / 5 = 6.24

8.

9. 對某系統(tǒng)進行監(jiān)測后表明平均每個進程在I/O 阻塞之前的運行時間為T 。一次進程‘切換的系統(tǒng)開銷時間為S 。若采用時間片長度為Q 的時間片輪轉(zhuǎn)法，對下列各種情況算出CPU 利用率。

10. 有5 個待運行的作業(yè)，各自預(yù)計運行時間分別是：9 、6 、3 、5 和x ，采用哪種運行次序使得平均響應(yīng)時間最短？

11.有5 個批處理作業(yè)A 到E 均己到達計算中心，其運行時間分別2 、4 、6 、8 和10 分鐘：各自的優(yōu)先級分跳狠掀完為、、飛、飛、氏積5 、這里5 為最高級。對于1) 時間片輪轉(zhuǎn)算法、2）優(yōu)先數(shù)法、3）短作業(yè)優(yōu)先算法、4）先來先服務(wù)調(diào)度算法（按到達次序C 、D 、B 、E 、A) ，在忽略進程切換時間的前提下，計算出平均作業(yè)周轉(zhuǎn)時間。(對l）每個作業(yè)獲得相同的2 分鐘長的時間片；對2）到4）采用單道運行，直到結(jié)束。）

答：( l ) FCFS 調(diào)度算法 

( 2 ）優(yōu)先級調(diào)度算法

( 3 ）時間片輪轉(zhuǎn)法 按次序ABCDEBCDECDEDEE 輪轉(zhuǎn)執(zhí)行。

( 4 ) SJF調(diào)度算法

12. 有5 個批處理作業(yè)A 到E 均已到達計算中心，其運行時間分別10 、6 、2 、4 和8 分鐘；各自的優(yōu)先級分別被規(guī)定為3 、5 、2 、1 和4 ，這里5 為最高級。若不考慮系統(tǒng)切換開銷，計算出平均作業(yè)周轉(zhuǎn)時間。（1) FCFs （按A 、B 、C 、D 、E ) ; (2) 優(yōu)先級調(diào)度算法，(3）時間片輪轉(zhuǎn)法（每個作業(yè)獲得相同的2 分鐘長的時間片）。

( 1 ) FCFS 調(diào)度算法

( 2 ）優(yōu)先級調(diào)度算法

( 3 ）時間片輪轉(zhuǎn)法

按次序ABCDEABDEABEAEA 輪轉(zhuǎn)執(zhí)行。

13. (l）假定一個處理器正在執(zhí)行兩道作業(yè)，一道以計算為主，另一道以輸入輸出為主，你將怎樣賦予它們占有處理器的優(yōu)先級？為什么？

(2）假定一個處理器正在執(zhí)行三道作業(yè)，一道以計算為主，第二道以輸入輸出為主，第三道為計算與輸入輸出均勻。應(yīng)該如何賦予它們占有處理器的優(yōu)先級使得系統(tǒng)效率較高？

答：處理器調(diào)度算法會考慮以下因素：作業(yè)響應(yīng)時間要求；讓CPU 盡量和外圍設(shè)備并行工作；限制一個計算進程長時間霸占處理器。因而，( 1 ) FO 為主作業(yè)優(yōu)先級高。（2 ) 輸入輸出為主作業(yè)優(yōu)先級最高，輸入輸出均勻的作業(yè)其次，而計算為主作業(yè)的優(yōu)先級最低。 

14. 請你設(shè)計一種先進的計算機體系結(jié)構(gòu)，它使用硬件而不是中斷來完成進程切換，則CPU 需要哪些信息？請描述用硬件完成進程切換的工作過程。

答：該計算機有一個專用硬件寄存器，它始終存放指向當前運行進程的PCB 的指針。當系統(tǒng)中發(fā)生了一個事件，如FO 結(jié)束事件，CPU 便可把運行進程的上下文保存到專用硬件寄存器指針指向的PCB 中保護起來，然后，CPU 轉(zhuǎn)向中斷向量表，找到設(shè)備中斷處理程序入口，讓專用硬件寄存器指針指向（設(shè)備）中斷服務(wù)例程，于是，便可啟動中斷服務(wù)例程工作。 

15.在單道批處理系統(tǒng)中，下列三個作業(yè)采用先來先服務(wù)調(diào)度算法和最高響應(yīng)比優(yōu)先算法進行調(diào)度，哪一種算法性能較好？請完成下表：

16.若有如表所示四個作業(yè)進入系統(tǒng)，分別計算在FCFS 、S 開和HRR 衛(wèi)算法下的平均周轉(zhuǎn)時間與帶權(quán)平均周轉(zhuǎn)時間。（時間以十進制表示）

答：

17題和16題差不多

18.Kleinrock 提出一種動態(tài)優(yōu)先權(quán)算法：進程在就緒隊列等待時，其優(yōu)先權(quán)以速率a變化；當進程在處理器上運行，時其優(yōu)先權(quán)以速率p 變化。給參數(shù)a,b 賦以不同值可得到不同算法。（l ）若a＞b＞c是什么算法？( 2 ）若a＜b＜c是什么算法

答：( l ）是先進先出算法。因為在就緒隊列中的進程比在CPU 上運行的進程的優(yōu)先數(shù)提高得快，故進程切換時，先進入就緒隊列的進程優(yōu)先權(quán)就越高。
( 2 ）是后進先出算法。因為在就緒隊列中的進程比在CPU 上運行的進程的優(yōu)先權(quán)下降得快，故后進入就緒隊列的進程此先進入的進程的優(yōu)先權(quán)高。 

19.在單處理器多到分時系統(tǒng)中，有三道作業(yè)依次提交, 其提交時刻及運行時間分別為

如果已知下列情況：

（1）每道作業(yè)的I/O等待時間占各自總運行時間的一半；

（2）分時運行兩道作業(yè)，CPU將有20%的時間空閑；

（3）除了CPU，系統(tǒng)有充足的資源供作業(yè)使用。試計算各作業(yè)運行完成時間。

分析時間段：
① 8.0~8.2時間內(nèi): 只有Job1,不會浪費時間, 在這0.2h內(nèi), 由于(1)每道作業(yè)的I/O時間占總運行時間的一半,所以有0.1h的時間用于I/O,剩余0.1用于CPU,因此 在8.2時刻, Job1還剩余0.36-0.2 = 0.16h的時間需要運行
② 8.2~8.4時間內(nèi), Job2開始運行, 同時Job1也在運行, 由于CPU同一時刻只能處理一個作業(yè), 因此會發(fā)生進程切換, 在這0.2h內(nèi), 會浪費0.2×20%=0.04h的時間, 那么實際可運行的時間就只有0.2-0.04=0.16h, 在前0.08h中,可以讓Job1運行CPU0.08h,同時, Job2可以運行I/O 0.08h, 在后0.08h中,Job1運行I/O 0.08h, Job2運行CPU0.08h, 這時,也就是8.4時刻, Job1運行完畢。Job2還剩下0.16的運行時間, 其中各占一半。
③ 8.4時刻, 此時Job3也開始運行, 同樣會發(fā)生調(diào)度, 那么在8.2~8.6這0.2h內(nèi), 可用運行時間同樣為0.16, 前0.08: Job2 CPU, Job3 I/O 后0.08: Job3CPU, Job2 I/O, 然后8.6時刻, Job2也就運行完畢
?④ 8.6時刻, 只有Job3, 不需要調(diào)度, 還剩下CPU和I/O各0.1, 也就是8.6+0.1+0.1=8.8, Job3結(jié)束
所以，job1，2，3運行完成的時刻分別為：8.4、8.6、8.8 

20.有一個四道作業(yè)的操作系統(tǒng)，若在一段時間內(nèi)先后到達6 個作業(yè)，它們的提交和估計運行時間由下表給出：

系統(tǒng)采用SJF 調(diào)度算法，作業(yè)被調(diào)度進入系統(tǒng)后中途不會退出，但作業(yè)運行時可被更短作業(yè)搶占。（l ）分別給出6 個作業(yè)的執(zhí)行時間序列、即開始執(zhí)行時間、作業(yè)完成時間、作業(yè)周轉(zhuǎn)時間。（2 ）計算平均作業(yè)周轉(zhuǎn)時間。

答： T =( 155 + 95 + 20 + 55 + 15 + 20 ) / 6 = 60 

24.有一個具有兩道作業(yè)的批處理系統(tǒng)，作業(yè)調(diào)度采用短作業(yè)優(yōu)先的調(diào)度算法，進程調(diào)度采用以優(yōu)先數(shù)為基礎(chǔ)的搶占式調(diào)度算法，在下表所示的作業(yè)序列，作業(yè)優(yōu)先數(shù)即為進程優(yōu)先數(shù)，優(yōu)先數(shù)越小優(yōu)先級越高。

( 1 ）列出所有作業(yè)進入內(nèi)存時間及結(jié)束時間。

( 2 ）計算平均周轉(zhuǎn)時間。

答：每個作業(yè)運行將經(jīng)過兩個階段：作業(yè)調(diào)度（SJF 算法）和進程調(diào)度（優(yōu)先數(shù)搶占式）。另外，批處理最多容納2 道作業(yè)，更多的作業(yè)將在后備隊列等待。

各作業(yè)周轉(zhuǎn)時間為：作業(yè)A 70 ，作業(yè)B 30 ，作業(yè)C 90 ，作業(yè)D 90 。平均作業(yè)周轉(zhuǎn)時間為70 分鐘。

27. 某多道程序設(shè)計系統(tǒng)供用戶使用的主存為100K ，磁帶機2 臺，打印機1 臺。采用可變分區(qū)內(nèi)存管理，采用靜態(tài)方式分配外圍設(shè)備，忽略用戶作業(yè)FO 時間。現(xiàn)有作業(yè)序列如下：

作業(yè)調(diào)度采用FCFS 策略，優(yōu)先分配主存低地址區(qū)且不準移動已在主存的作業(yè)，在主存中的各作業(yè)平分CPU 時間．現(xiàn)求：( l ）作業(yè)被調(diào)度的先后次序？( 2 ）全部作業(yè)運行結(jié)束的時間？( 3 ）作業(yè)平均周轉(zhuǎn)時間為多少？( 4 ）最大作業(yè)周轉(zhuǎn)時間為多少？

答：( l ）作業(yè)調(diào)度選擇的作業(yè)次序為：作業(yè)1 、作業(yè)3 、作業(yè)4 、作業(yè)2 和作業(yè)5 . 
( 2 ）全部作業(yè)運行結(jié)束的時間9 : 30 。 
( 3 ）周轉(zhuǎn)時間：作業(yè)1 為30 分鐘、作業(yè)2 為55 分鐘、作業(yè)3 為40 分鐘、作業(yè)4 為40 分鐘和作業(yè)5 為55 分鐘。 
平均作業(yè)周轉(zhuǎn)時間＝44 分鐘。 
( 4 )最大作業(yè)周轉(zhuǎn)時間為55 分鐘。 

28. 某多道程序設(shè)計系統(tǒng)采用可變分區(qū)內(nèi)存管理，供用戶使用的主存為200K ，磁帶機5 臺。采用靜態(tài)方式分配外圍設(shè)備，且不能移動在主存中的作業(yè)，忽略用戶作業(yè)I/O時間。現(xiàn)有作業(yè)序列如下：

現(xiàn)求：( l ) FIFO 算法選中作業(yè)執(zhí)行的次序及作業(yè)平均周轉(zhuǎn)時間？( 2 ) SJF 算法選中作業(yè)執(zhí)行的次序及作業(yè)平均周轉(zhuǎn)時間？（進程調(diào)度也采用FCFS )

答：( 1 ) FIFO 算法選中作業(yè)執(zhí)行的次序為：A 、B 、D 、C 和E 作業(yè)平均周轉(zhuǎn)時間為63分鐘 
( 2 ) SJF 算法選中作業(yè)執(zhí)行的次序為：A 、B 、D 、E 和C 。作業(yè)平均周轉(zhuǎn)時間為58分鐘 

29. 上題中，若允許移動己在主存中的作業(yè)，其他條件不變，現(xiàn)求：( l ) FIFO 算法選中作業(yè)執(zhí)行的次序及作業(yè)平均周轉(zhuǎn)時間？( 2 ) SJF 算法選中作業(yè)執(zhí)行的次序及作業(yè)平均周轉(zhuǎn)時間？

答：
FIFO 算法選中作業(yè)執(zhí)行的次序為：SJF 算法選中作業(yè)執(zhí)行的次序為：
（l ) A 、B 、D 、E 和C。作業(yè)平均周轉(zhuǎn)時間為58 分鐘。
( 2 ) A 、B 、E 、D 和C。作業(yè)平均周轉(zhuǎn)時間為56 分鐘。

第三章 同步、通訊與死鎖

1. 有三個并發(fā)進程：R 負責從輸入設(shè)備讀入信息塊，M 負責對信息塊加工處理；P 負責打印輸出信息塊。今提供；

( l ）一個緩沖區(qū)，可放置K 個信息塊；

( 2 ）二個緩沖區(qū)，每個可放置K 個信息塊；

試用信號量和P 、V 操作寫出三個進程正確工作的流程。

var B : array [ 0 , k-1 ] of item ; 
sread : semaPhore : = k ; 
smanage : semaPhore : = 0 ; 
swrite : semaphore : = 0 ; 
rptr : integer : = O ; 
mptr : integer : = O ; 
wptr ：integer : = 0 ; 
x : item
cobegin 
process reader ; process manager ; process writer ; 
begin begin begin 
LI : read a message intox ; L2 : P ( smanage ) ; L3 : P ( swnte ) ;
P ( sread ) ; x:=B[mptr]; x:=B[swrite];
B[rptr]:=x; mptr:=(mptr+1) mod k; wptr:=(wptr+1) mod k;
Rptr:=(rptr+1) mod k; manage the message in x; V(sread);
V(smanage); B[mptr]:=x; print the message in x;
Goto L1; V(swrite); goto L3;
End; goto L2; end;
End;
coend

var A , B :array [ 0 , k -l ] of item ; 
sPut1 : semaphore:=k; 
SPut2: semaPhore:=k; 
sget1 : semaPhore : = 0 ; 
sget2 : semaphore : = 0 ; 
put1 ：integer ：=O ; 
put2：integer : = 0 ; 
get1 ：integer ：=O ; 
get2 : integer : = O ; 
cobegin 
process reader ; processn manager; process Writer ; 
begin begin begin 
Ll : read a message into x ; L2 : P ( sgetl ) ; L3 : P ( sgetZ ) ; 
P ( SPut1 ) ; x : = A [ get1] ; x : = B [get2]; 
A [put1]:=x ; get1 ：(get1+1 ) mod k ; get2:=（get2 + l ) mod k ;
Put1:=(put1+1) mod k; V(sput1); V(sput2);
V(sget1); manage the message into x; print the message in x;
Goto L1; P(sput2); goto L3;
Put2:=(put2+1) mod k;
V(sget2);
Goto L2;
End;
Coend

2. 設(shè)有n 個進程共享一個互斥段，如果：

( 1 ）每次只允許一個進程進入互斥段；

( 2 ）每次最多允許m 個進程（m <= n ）同時進入互斥段。

試問：所采用的信號量初值是否相同？信號量值的變化范圍如何？

答：所采用的互斥信號量初值不同。
1 ）互斥信號量初值為1 ，變化范圍為［-n＋l , 1 ］。
2 ）互斥信號量初值為m ，變化范圍為［-n＋m , m ］。

3.有兩個優(yōu)先級相同的進程P1和P2，各自執(zhí)行的操作如下，信號量S1和S2初值均為0。試問Pl 、P2 并發(fā)執(zhí)行后，x 、y 、z 的值各為多少？

P1: P2:

Begin begin

y:=1; ① x:=1;⑤

y:=y+3;② x:=x+5; ⑥

V(S1); P(S1);

z:=Y+1; ③ X:X+Y; ⑦

P(s2); V(S2);

y:=z+y; ④ z:=z+x; ⑧

End End

答： 我們來分析一下，對于兩個程序的語句，我們標上①②....
1 2 3和5 6 7基本不受并發(fā)編程的影響，所以此時 x = 10 y = 4;
如果③比⑧先運行，z = 5 , 此時如果④比⑧還要先運行的話， y = 9 z = 15,否則，z = 15 y = 19
如果⑧比③先運行, 那么x = 10 y = 9 z = 5;
所以有三種情況：
x = 10 y = 9 z = 15
x = 10 y = 9 z = 19
x = 10 y = 9 z = 5

4. 現(xiàn)有語句S1: a = 5 - x；S2:　b=a*x; S3: c = 4*x; S4: d = b+c S5: e = d+ 3;使用Bernstein條件證明語句S2和S3可以并發(fā)執(zhí)行，S3和S4不可以。

答： 
R(S2) = {a,b,x}  W(S2) =   R(S3) = {c,x} W(S3) = {c}     R(S4) = {b,c,d}  W(S4) = n5n3t3z
使用Bernstein條件，因為，R(S2)∩W(S3)∪R(S3)∩W(S2)∪W(S2)∩W(S3) = ? 所以，S2和S3可以并發(fā)執(zhí)行
因為，R(S3)∩W(S4)∪R(S4)∩W(S3)∪W(S3)∩W(S4) = {c} 所以，S3和S4不可以并發(fā)執(zhí)行

5.有一閱覽室，讀者進入時必須先在一張登記表上登記，該表為每一座位列出一個表目，包括座號、姓名，讀者離開時要注銷登記信息；假如閱覽室共有100 個座位。試用：l ）信號量和P 、V 操作；2 ）管程，來實現(xiàn)用戶進程的同步算法。

答：1 ）使用信號量和P 、v 操作：
var name ：array [ l …100]of A ; 
A = record 
number ：integer ; 
name：string ; 
end 
for i : = 1 to 100 do {A [ i ].number ：i；A [ i ].name :null;} 
mutex , seatcount : semaphore ; 
i : integer ；mutex : = l ; seatcount : = 100 ; 
cobegin 
{ 
process readeri ( var readename：string ) （i=1 , 2 …) 
{ 
P ( seatcount ) ; 
P （mutex ) ; 
for i : = 1 to 100 do i++
if A [ i ].name＝null then A [ i ].name：readername； 
reader get the seat number=i；/*A[I].number
V ( mutex ) 
進入閱覽室，座位號i ，座下讀書；
P ( mutex ) ; 
A[i]name：null ; 
V （mutex ) ; 
V(seatcount);
離開閱覽室； 
}
}
coend
2 ）使用管程操作：
TYPE readbook=monitor 
VAR R: condition ; 
I,seatcount ：integer;
name：array [ l:100] of string ; 
DEFINE rcadercome, readerleave ; 
USE check , wait , signal , release ; 
Procedure readercome ( readername ) 
begin 
check ( IM ) ; 
if seatcount≥100 wait ( R,IM ) 
seatcount : = seatcount + 1 ; 
for i=1 to 100 do i++
if name[i] ==null then name[i]:= readername; 
get the seat number = i ; 
release ( IM ) ; 
end 
procedure readerleave ( readername ) 
begin 
check ( IM ) ; 
seatcount--; 
for i = 1 to 1 00 do i++
if name［i ］readername then name［i］:null;
release ( IM ) ; 
end 
begin 
seatcount : = 1OO ; name:＝null ; 
end 
cobegin 
{ 
process readeri ( i = 1 , 2 ．… ）
begin 
readercome ( readername）; 
read the book ; 
readerleave ( readername）; 
leave the readroom;
end 
}
coend.

6.在一個盒子里，混裝了數(shù)量相等的黑白圍棋子· 現(xiàn)在用自動分揀系統(tǒng)把黑子、白子分開，設(shè)分揀系統(tǒng)有二個進程P1 和P2 ，其中P1 揀白子；P2 揀黑子。規(guī)定每個進程每次揀一子；當一個進程在揀時，不允許另一個進程去揀；當一個進程揀了一子時，必須讓另一個進程去揀．試寫出兩進程P1 和P2 能并發(fā)正確執(zhí)行的程序。

答1 ：實質(zhì)上是兩個進程的同步問題，設(shè)信號量s1 和s2 分別表示可揀白子和黑子，不失一般性，若令先揀白子。
var S1 , S2 : semaphore; 
S1 : = l; S2 ：=0;
cobegin 
{ 
process P1 
begin 
repeat 
P( S1 ) ; 
揀白子
V ( S2 ) ; 
until false ; 
end 
process P2 
begin 
repeat 
P ( S2 ) ; 
揀黑子
V (S1 ) ; 
until false ; 
end 
} 
coend . 

7.管程的同步機制使用條件變量和wait 及signal ，嘗試為管程設(shè)計一種僅僅使用一個原語操作的同步機制。

答：可以采用形如waituntil ＜條件表達式＞的同步原語。如waituntil ( numbersum + number < K ) 表示進程由于條件不滿足而應(yīng)等待，當進程號累加和小于K 時，系統(tǒng)應(yīng)喚醒該進程工作．

8.設(shè)公共汽車上，司機和售票員的活動分別如下：

司機的活動：啟動車輛：正常行車；到站停車。

售票員的活動：關(guān)車門；售票；開車門。

在汽車不斷地到站、停車、行駛過程中，這兩個活動有什么同步關(guān)系？用信號量和P 、V 操作實現(xiàn)它們的同步。

在汽車行駛過程中，司機活動與售票員活動之間的同步關(guān)系為：售票員關(guān)車門后，向司機發(fā)開車信號，司機接到開車信號后啟動車輛，在汽車正常行駛過程中售票員售票，到站時司機停車，售票員在車停后開門讓乘客上下車。因此，司機啟動車輛的動作必須與售票員關(guān)車門的動作取得同步；售票員開車門的動作也必須與司機停車取得同步。應(yīng)設(shè)置兩個信號量：S1 、S2 ;S1 表示是否允許司機啟動汽車（其初值為0 ) ;S2 表示是否允許售票員開門（其初值為0 ）。用P 、v 原語描述如下：
var S1 , S2 : semaphore ; 
S1=0；S2=0；
cobegin 
{ 
driver ( ) ; 
busman ( ) ; 
} 
coend 
driver ( ) 
begin 
while ( 1 ) { 
P ( S1 )
啟動車輛；正常行車；到站停車； 
V ( S2 ) ; 
} 
end 
busman ( ) 
begin 
while ( 1 ) { 
關(guān)車門； 
V ( 51 ) 
售票;
P ( S2 ) 
開車門； 
上下乘客； 
} 
end 

9.一個快餐廳有4 類職員：( l ）領(lǐng)班：接受顧客點菜；( 2 ）廚師：準備顧客的飯菜；( 3 ) 包工：將做好的飯菜打包；( 4 ）出納員：收款并提交食品。每個職員可被看作一個進程，試用一種同步機制寫出能讓四類職員正確并發(fā)運行的程序。

答：典型的進程同步問題，可設(shè)四個信號量51 、S2 、S3 和S4 來協(xié)調(diào)進程工作。
var S1 , S2 ,S3 , S4 : semaphore ;
S1 : = 1 ;S2 ：=S3 : = S4 : = 0 ;
cobegin 
{ process P1
begin 
repeat 
有顧客到來；
P ( S1 )； 
接受顧客點菜；
V ( 52 )；
untile false； 
end 

process P2 
begin 
repeat 
P (S2 ) ; 
準備顧客的飯菜； 
v ( S3 ) ; 
untile false ; 
end 
process P3 
begin 
repeat 
P (S3 ) ; 
將做好的飯菜打包； 
V ( S4 ) ; 
untile false ; 
end 

process P4 
begin 
repeat 
P( 54 ) ; 
收款并提交食品；V ( 51 ) ; 
ufltile false ; 
end 
} 
coend. 

10.( 1 ）兩個并發(fā)進程并發(fā)執(zhí)行，其中，A 、B 、C 、D 、E 是原語，試給出可能的并發(fā)執(zhí)行路徑。

Process P（）{ Process Q（）{

begin begin

A ; D ;

B ; E ;

C ; end :

end ; }

}

( 2 ）兩個并發(fā)進程P1 和P2 并發(fā)執(zhí)行，它們的程序分別如下：

P 1 （）{ P2（）{

repeat repeat

k:=k×2 ; print k ;

k:=k+1 ; k:=0 ;

until false ; until false ;

} }

若令k 的初值為5 ，讓P1 先執(zhí)行兩個循環(huán)，然后，P1 和P2 又并發(fā)執(zhí)行了一個循環(huán)，寫出可能的打印值，指出與時間有關(guān)的錯誤。

答： 
( 1 ）共有10 種交錯執(zhí)行的路徑：
A 、B 、C 、D 、E; A 、B 、D 、E 、C; A 、B 、D 、C 、E ; 
A 、D 、B 、E 、C; A 、D 、B 、C 、E; A 、D 、E 、B 、C ; 
D 、A 、B 、E 、C; D 、A 、B 、C 、E; D 、A 、E 、B 、C ; D 、E 、A 、B 、C 。 
( 2 ）把語句編號，以便于描述：
P 1 （）{             P2（）{ 
repeat                repeat 
k:=k×2 ;①            print k ;③ 
k:=k+1 ; ②           k:=0 ;④ 
until false ;         until false ;
}                     }
首先， K 的初值為5 ，故P1 執(zhí)行兩個循環(huán)后，K = 23 。
其次，語句并發(fā)執(zhí)行有以下情況：
① 、② 、③ 、④ ，這時的打印值為：47 
③ 、④ 、① 、② ，這時的打印值為：23 
① 、③ 、② 、④ ，這時的打印值為：46 
① 、③ 、④ 、② ，這時的打印值為：46 
③ 、① 、② 、④ ，這時的打印值為：23 
③ 、① 、④ 、② ，這時的打印值為：23 
由于進程P1和P2 并發(fā)執(zhí)行，共享了變量K ，故產(chǎn)生了‘結(jié)果不唯一’。

11.證明信號量與管程的功能是等價的：

( l ）用信號量實現(xiàn)管程；

( 2 ）用管程實現(xiàn)信號量。

答：( 1 ）用信號量實現(xiàn)管程；
Hoare 是用信號量實現(xiàn)管程的一個例子，詳見課文內(nèi)容。下面介紹另一種簡單方法：每一個管程都對應(yīng)一個mutex ，其初值為1 ，用來控制進程互斥調(diào)用管程。再設(shè)一個初值為0 的信號量，用來阻塞等待資源的進程。相應(yīng)的用信號量實現(xiàn)的管程庫過程為： 
Var mutex,c:semaphore ; 
mutex:=1 ; c:=0 ; 
void enter-monitor ( ) /*進入管程代碼，保證互斥
P ( mutex ) ; 
} 
void leave-monitor-normally ( )/*不發(fā)信號退出管程
{ 
V ( mutex ) ; 
} 
void leave-with-sigal(c) /*在條件c 上發(fā)信號并退出管程，釋放一個等待c 條件的進程。｛注意這時沒有開放管程，因為剛剛被釋放的進程己在管程中。
V ( c ) ; 
} 
void wait(c) /*等待條件c ，開放管程
{ 
V ( mutex ) ; 
P (c) ; 
} 
( 2 ）用管程實現(xiàn)信號量。
TYPE semaphore=monitor 
VAR S ; condition ; 
C:integer ; 
DEFINE P , V ; 
USE check , wait , signal , release ; 
procedure P 
begin 
check ( IM ) ; 
C:= C-1 : 
if C < 0 then wait ( S,IM ) ; 
release ( IM ) ; 
end 

procedure V 
begin 
check ( IM ) : 
C : = C + 1 ; 
if C≤0 then signal ( S,IM ) ; 
release ( IM ) ; 
end 
begin 
C:=初值;
End.

12. 證明消息傳遞與管程的功能是等價的：

( 1 ）用消息傳遞實現(xiàn)管程；

( 2 ）用管程實現(xiàn)消息傳遞。

答：( 1 ）用消息傳遞實現(xiàn)管程；
用消息傳遞可以實現(xiàn)信號量（見13 ( 2 ) ) ，用信號量可以實現(xiàn)管程（見11 (1 ) ) ，那么，把兩種方法結(jié)合起來，就可以用用消息傳遞實現(xiàn)管程。
( 2 ）用管程實現(xiàn)消息傳遞。
TYPE mailbox=monitor 
VAR r , k , count:integer ; 
buffer ：array[0…n-1] of message ; 
full , empty:condition ; 
DEFINE add , get ; 
USE check , wait , signal , release ; 
procedure add ( r ) ; 
begin 
check ( IM ) ; 
if count=n then wait ( full,IM ) ; 
buffer [r]:=message ; 
r:＝(r+1) mod n 
count:=count + 1 ; 
if count = 1 then sighal ( empty , IM ) ; 
release ( IM ) ; 
end 

procedure get ( m ) ; 
begin 
check ( IM ) ; 
if count = 0 then wait ( empty , IM ) ; 
m:=buffer [ k 」；
count : = count-1 ; 
if count＝n-1 then signal ( full , IM ) ; 
release ( IM ) ; 
end 
begin 
r:= 0 ; k:= 0 ; count:=0 ; 
end 

13.證明信號量與消息傳遞是等價的：

( 1 ）用信號量實現(xiàn)消息傳遞；

( 2 ）用消息傳遞實現(xiàn)信號量。

答：( l ）用信號量實現(xiàn)消息傳遞；
1 ）把消息隊列組織成一個共享隊列，用一個互斥信號量管理對該隊列的入隊操作和出隊操作.
2 ）發(fā)送消息是一個入隊操作，當隊列存儲區(qū)滿時，設(shè)計一個同步信號量阻塞send 操作。
3 ）接收消息是一個出隊操作，當隊列存儲區(qū)空時，設(shè)計另一個同步信號量阻塞receive 操作。
( 2 ）用消息傳遞實現(xiàn)信號量。
l ）為每一個信號量建立一個同步管理進程，它包含了一個計數(shù)器，記錄信號量值；還為此信號量設(shè)立一個等待進程隊列
2 ）應(yīng)用進程執(zhí)行P 或V操作時，將會調(diào)用相應(yīng)P 、V庫過程。庫過程的功能是：把應(yīng)用進程封鎖起來，所執(zhí)行的P 、V 操作的信息組織成消息，執(zhí)行send 發(fā)送給與信號量對應(yīng)的同步管理進程，之后，再執(zhí)行receive 操作以接收同步管理進程的應(yīng)答。
3 ）當消息到達后，同步管理進程計數(shù)并查看信號量狀態(tài)。如果信號量的值為負的話，執(zhí)行P 操作的應(yīng)用進程被阻塞，掛到等待進程隊列，所以，不再要送回答消息。此后，當V 操作執(zhí)行完后，同步管理進程將從信號量相應(yīng)隊列中選取一個進程喚醒，并回送一個應(yīng)答消息。正常情況下，同步管理進程回送一個空應(yīng)答消息，然后，解鎖執(zhí)行P 、V 操作的應(yīng)用程序。

14.試利用記錄型信號量和P 、V 操作寫出一個不會出現(xiàn)死鎖的五個哲學家進餐問題的算法。

semaphore fork[5];
for (int i=0;i<5;i++)
        fork[i]=1;
semaphore mutex = 1 ; 
Cobegin
process philosopher(i) {      //i= 0,1,2,3,4
    while(true) {
        think( );
        P(metex);
          P(fork[i]);
          P(fork[(i+1)%5]);
        V(metex);
        eat( );
          V(fork[i]); 
        V(fork[(i+1)%5]);
     }
}
coend

之后的信號量和P、V操作都差不多，略過啦...

23.設(shè)當前的系統(tǒng)狀態(tài)如下：系統(tǒng)此時Available=(1,1,2):

( l ）計算各個進程還需要的資源數(shù)Cki - Aki

( 2 ）系統(tǒng)是否處于安全狀態(tài)，為什么？

( 3 ) P2 發(fā)出請求向量request2 ( 1 , 0 , 1 ) ，系統(tǒng)能把資源分給它嗎？

( 4 ）若在P2 申請資源后，若P1 發(fā)出請求向量request1( 1 ,0, 1 ) ，系統(tǒng)能把資源分給它嗎？

( 5 ）若在P1 申請資源后，若P3 發(fā)出請求向量request3 ( 0 ,0, 1 ) ，系統(tǒng)能把資源分給它嗎？

答: 
(1)各個進程還需要的資源數(shù) Need（Cki - Aki）分別為p1 = (2,2,2),p2 = (1,0,2),p3 = (1,0,3),p4 = (4,2,0)
(2) 如表格所示，系統(tǒng)處于安全狀態(tài)，存在安全序列（p2,p1,p3,p4）

(3) Request2(1,0,1) <= Need2(1,0,2) 且 Request2(1,0,1) <= Available(1,1,2),嘗試進行資源分配，Need2(0,0,1),Acolation2(6,1,2),Available(0,1,1)，如下表，存在安全序列（p2,p1,p3,p4），系統(tǒng)可以把資源分給它

(4)request1( 1 ,0, 1 ) <= Need1(2,2,2)但是 request1( 1 ,0, 1 ) > Available(0,1,1),所以資源不足，無法分配
(5) 雖然request3 ( 0 ,0, 1 ) <= Need3(1,0,3) 且 request3 ( 0 ,0, 1 ) <= Available(0,1,1) 但是下表中分配資源的時候無法分配 

24.系統(tǒng)有A 、B 、C 、D 共4 種資源，在某時刻進程PO 、Pl 、PZ 、P3 和P4 對資源的占有和需求情況如表，試解答下列問題：

（1）系統(tǒng)此時處于安全狀態(tài)嗎？

（2）若此時P2 發(fā)出request2 ( 1 、2 、2 、2 ) ，系統(tǒng)能分配資源給它嗎？為什么？

答：
(1)如下表:系統(tǒng)此時處于安全狀態(tài)，存在安全序列（P0,P3,P1,P2,P4）

(2) request2 ( 1 、2 、2 、2 ) <= Need2(2,3,5,6) 并且 request2 ( 1 、2 、2 、2 ) <= Available(1,6,2,2) 如下表進行資源分配： Available(0,4,0,0)、Need2(1,1,3,4)、Allocation(2,5,7,6),無法分配，不安全

25.用死鎖檢測算法于下面的數(shù)據(jù)，并請問：

Available=(1,0,2,0)

( l ）此時系統(tǒng)處于安全狀態(tài)嗎？

( 2 ）若第二個進程提出資源請求request2( 0 , 0 , 1 , 0 ) 系統(tǒng)能分配資源給它嗎？

(3）執(zhí)行（2）之后，若第五個進程提出資源請求request5( 0 ,0 ,1 ,0 )系統(tǒng)能分配資源給它嗎？

ps:不畫圖了，和前面的圖差不多
答：( l ）此時可以找出進程安全序列：P4 , P1 , P5 , P2 , P3 。故系統(tǒng)處于安全狀態(tài)。
( 2 ）可以分配，存在安全序列：P4 , P1 , P5, P2 , P3 。
( 3 ）不可分配，系統(tǒng)進入不安全狀態(tài)。

26.考慮一個共有巧0 個存儲單元的系統(tǒng)，如下分配給三個進程，P1 最大需求70 ，己占有25 ; 以P2 最大需求60 ，己占有40 ; P3 最大需求60 ，己占有45 。使用銀行家算法，以確定下面的任何一個請求是否安全。（l ) P4 進程到達，P4 最大需求60 ，最初請求25 個。（2 ) P4 進程到達，P4 最大需求60 ，最初請求35 。如果安全，找出安全序列；如果不安全，給出結(jié)果分配情況。

答：(l)由于系統(tǒng)目前還有150-25-40-45=40 個單元，P4 進程到達，把25 個單元分給它。這時系統(tǒng)還余15 個單元，可把15 個單元分給P3 ，它執(zhí)行完后會釋放60 個單元。于是可供P1 （還要45 個單元）, P2 （還要20 個單元）, P4(還要35 個單元)任何一個執(zhí)行。
存在安全序列為： p1,p2,p3,p4
(2)P4進程到達，P4最大需求60，最初請求35 。如果把35 個單元分給P4 ，系統(tǒng)還余5個單元，不再能滿足任何一個進程的需求，系統(tǒng)進入不安全狀態(tài)。

27.有一個倉庫，可存放X 、Y 兩種產(chǎn)品，倉庫的存儲空間足夠大，但要求：( l ）每次只能存入一種產(chǎn)品X或Y , ( 2 ）滿足-N＜X 產(chǎn)品數(shù)量-Y 產(chǎn)品數(shù)量＜M 。其中，N 和M 是正整數(shù)，試用信號量與P 、V 操作實現(xiàn)產(chǎn)品X 與Y 的入庫過程。

答：本題給出的表達式可分解為制約條件：
-N < X 產(chǎn)品數(shù)量-Y 產(chǎn)品數(shù)量
X 產(chǎn)品數(shù)量-Y 產(chǎn)品數(shù)量＜M 
也就是說，X 產(chǎn)品的數(shù)量不能比Y 產(chǎn)品的數(shù)量少N 個以上，X 產(chǎn)品的數(shù)量不能比Y 產(chǎn)品的數(shù)量多M 個以上。可以設(shè)置兩個信號量來控制X 、Y 產(chǎn)品的存放數(shù)量：
SX 表示當前允許X 產(chǎn)品比Y 產(chǎn)品多入庫的數(shù)量，即在當前庫存量和Y 產(chǎn)品不入庫的情況下，還可以允許SX個X產(chǎn)品入庫；初始時，若不放Y而僅放X產(chǎn)品，則SX最多為M-1個。 
sy 表示當前允許Y 產(chǎn)品比x 產(chǎn)品多入庫的數(shù)量，即在當前庫存量和x 產(chǎn)品不入庫的情況下，還可以允許sy 個Y 產(chǎn)品入庫．初始時，若不放X 而僅放Y 產(chǎn)品，則sy 最多為N -1 個。當往庫中存放入一個X 產(chǎn)品時，則允許存入Y 產(chǎn)品的數(shù)量也增加1 ，故信號量sy 應(yīng)加1 ：當往庫中存放入一個Y 產(chǎn)品時，則允許存入X 產(chǎn)品的數(shù)量也增加1 ，故信號量sx 應(yīng)加1 . 
var mutex : semaphore = 1 /*互斥信號量＊/ 
sx , sy : semaphore;
sx = M-1 ; sy = = N - l ; 
cobegin 
{ 
process X 
｛repeat 
P(sx ) ; 
P （mutex ) ; 
將X 產(chǎn)品入庫；
V(mutex ) ; 
V ( sy ) ; 
until false 
} 

process Y 
{ repeat 
P ( sy ) ; 
P （mutex ) ; 
將Y 產(chǎn)品入庫；
V （mutex ) ; 
V ( px ) ; 
until false 
} 
} 
coend . 

30.某系統(tǒng)有R1 設(shè)備3 臺，R2 設(shè)備4 臺，它們被P1、P2 、P3 和P4 進程共享，且己知這4 個進程均按以下順序使用設(shè)備：

一>申請R1 一>申請R2 一>申請R1 一> 釋放R1 一> 釋放R2 一> 釋放R1

( 1 ）系統(tǒng)運行中可能產(chǎn)生死鎖嗎？為什么？

( 2 ）若可能的話，請舉出一種情況，并畫出表示該死鎖狀態(tài)的進程-資源圖．

答：( l ）系統(tǒng)四個進程需要使用的資源數(shù)為Rl 各2 臺，R2 各1 臺?？梢娰Y源數(shù)不足，同時各進程申請資源在先，有可能產(chǎn)生死鎖發(fā)生的四個條件，故系統(tǒng)可能產(chǎn)生死鎖。( 2 ）當三個進程執(zhí)行完申請資源Rl ，開始執(zhí)行申請資源R2 時，第四個進程會因沒有資源Rl 而被阻塞。當三個進程執(zhí)行完申請資源R2 后，系統(tǒng)還剩1 個R2 資源。而這三個進程因執(zhí)行申請第二個資源Rl 而全部被阻塞，系統(tǒng)進入死鎖。

38.桌上有一只盤子，最多可以容納兩個水果，每次僅能放入或取出一個水果。爸爸向盤子中放蘋果(apple ) ，媽媽向盤子中放桔子(orange ) ，兩個兒子專等吃盤子中的桔子，兩個女兒專等吃盤子中的蘋果．試用：( 1 ）信號量和P 、v 操作，( 2 ）管程，來實現(xiàn)爸爸、媽媽、兒子、女兒間的同步與互斥關(guān)系．

答：( l ）用信號量和P 、v 操作．
類似于課文中的答案，擴充如下：1 ）同步信號量初值為2 ; 2 ）要引進一個互斥信號量mutex , 用于對盤子進行互斥：3 ）盤子中每一項用橘子、蘋果2 個枚舉值。
Var 
plate ARRAY [ 0 , 1] of ( apple , orange ) ; 
flag0 , fiag1:=boolean ; 
mutex : semaphore ; 
sp : semaphore; / ＊盤子里可以放幾個水果＊/ 
sg1 , sg2 : semaphore ; / ＊盤子里有桔子，有蘋果* /
sp : = 2 ; / ＊盤子里允許放入二個水果＊/ 
sg1 :=sg2 :=0 ; / ＊盤子里沒有桔子，沒有蘋果＊/ 
flag0:=flag1:=false ; mutex :=1 : 
cobegin process son 
process father begin 
begin L3 : P (sg1 ) ; 
L1 :削一個蘋果； P( mutex ) ;
P ( sp ) ; if（flag0&flte[0]==桔子） then 
If(flag0==false) then else{x:=plate[1];flag1:=false;}
{ plate[0]:＝蘋果；flag1:=true;} v(mutex);
else {plate[1]:=蘋果；flag1:=true;} V(sp) ; 
v (mutex ); 吃桔子； 
v(sg2) goto L3;
goto Ll ; end;
end ; 
process mother process daughter
begin begin
L2 ：剝一個桔子； L4 : P ( 592 ) : 
P ( sp ) ; P ( mutex )

P ( mutex ) ; if ( flag0 & plate [0]=＝蘋果）then
if ( flag0==false ）then {x:=plate [01]; flag0:=false ; }
{plate[0]:＝桔子；flag0:=true;) else { x:==plate[1] ; flag1:=false ; }
else {plate[1]:=＝桔子；flag1:＝true ; } V ( mutex ) ;
V (mutex) ; V ( sp ) ;
V (sg1) ; 吃蘋果；
goto L2 ; goto L4;
end ; end ;
coend . 
( 2 ）用管程．
TYPE FMSD = MONITOR 
VAR plate ARRAY [ 0 , 1 ] of ( apple , orange ) ;
Count:integer ; flag0，flag1:boolean ;
SP ,SS , SD : codition ; 
DEFFINE put,get ; 
USE wait,signal , check , release ; 
procedure put(var fruit:( apple ，orange ) ) ;
begin
check(IM ) ; 
if ( count=＝2 ) then wait(SP , IM ) ; 
else{if(flag0==false) then
{plate[0]:=fruit; flag0:=true;}
Else{plate[1]:=fruit;flag1:=true;}
Count:=count+1;
If(fruit==orange) then signal(ss,IM);
Else signal(SD,IM);
}
Release(IM);
End;
Procedure get(varfruit:(apple,orange),x:plate);
Begin
Check(IM);
If (count==0) or plate <>fruit
Then begin
If(fruit==orange) then wait(SS,IM);
Else wait(SD,IM);
End;
Count:=count-1;
If(flag0&plate[0]==fruit) then
{x:=plate[0];flag0:=false;}
Else{x:=plate[1];flag1:=false;}
Signal(SP,IM);
Release(IM);
End;
Begin
Count:=0;flag0:=false;flag1:=false; SP:=0;ss:=0;sd:=0;
Plate[0]:plate[1]:=null;
End;
Main()
{cobegin
Process father
Begin
While(1)
{準備好蘋果； 
Call FMSD.put(apple);
…… 
}
End;
Process mother
Begin
While(1)
{
準備好桔子； 
Call FMSD.put(orange);
…… 
}
End;
Process son
Begin
While(1)
{call FMSD.get(orange,x);
吃取到的桔子； 
…… 
}
End;
Process daughter
Begin
While(1)
{
Call FMSD.get(apple,x);
吃取到的蘋果； 
…… 
}
End;
}
Coend

50.某寺廟有小和尚和老和尚各若干人，水缸一只，由小和尚提水入缸給老和尚飲用。水缸可容水10 桶，水取自同一口水井中。水井徑窄，每次僅能容一只水桶取水，水桶總數(shù)為3 個。若每次入、取水僅為1 桶，而且不可同時進行。試用一種同步工具寫出小和尚和老和尚入水、取水的活動過程。

答：互斥資源有水井和水缸，分別用mutex1和mutex2來互斥。水桶總數(shù)僅3 只，由信號量count 控制，信號量empty 和full 控制入水和出水量。
var mutex1 , mutex2 : semaphore ; 
empty ，full : semaphore ; 
count : integer ; 
mutex1 : mutex2 : = 1 ; count : = 3 ; empty : = 10 ；full ：=0 ; 
cobegin 
{ 
process 小和尚（打水）i ( i = 1 , 2 ，… ）
begin 
repeat 
P ( e mpty ) ; / ＊水缸滿否？
P ( count ) ; / ＊取得水桶
P ( mutexl ) ; / ＊互斥從井中取水
從井中取水；
V ( mutex1) ; 
P ( mutex2) ; / ＊互斥使用水缸
倒水入缸；
V ( mutex2 ) ; 
V ( count ) ; / ＊歸還水桶
v ( full ) ; / ＊多了一桶水
untile false ; 
end 
process 老和尚（取水）j(j=1 , 2 ，… ）
begin 
repeat 
P ( full ) ; / ＊有水嗎？
P ( count ) ; / ＊申請水桶
P ( inutex2 ) ; / ＊互斥取水
從缸中取水；
V ( mutex2 ) ; 
V ( count ) ; / ＊歸還水桶
V ( empty ) ; / ＊水缸中少了一桶水
untile false ; 
end 
} 
coend . 

第四章 存儲管理

1.在一個請求分頁虛擬存儲管理系統(tǒng)中，一個程序運行的頁面走向是：

1 、2 、3 、4 、2 、1 、5 、6 、2 、1 、2 、3 、7 、6 、3 、2 、1 、2 、3 、6 。

分別用FIFO 、OPT 和LRU 算法，對分配給程序3 個頁框、4 個頁框、5 個頁框和6 個頁框的情況下，分別求出缺頁中斷次數(shù)和缺頁中斷率。

2.在一個請求分頁虛擬存儲管理系統(tǒng)中，一個作業(yè)共有5 頁，執(zhí)行時其訪問頁面次序

為：( 1 ) 1 、4 、3 、1 、2 、5 、1 、4 、2 、1 、4 、5

( 2 ) 3 、2 、1 、4 、4 、5 、5 、3 、4、3、2、1、5

若分配給該作業(yè)三個頁框，分別采用FIFO和LRU 面替換算法，求出各自的缺頁中斷次數(shù)和缺頁中斷率。

答：
( 1 ）采用FIFO 為9 次，9 / 12 = 75 ％。采用LRU 為8 次，8 / 12 = 67 ％。
( 2 ）采用FIFO 和LRU 均為9 次，9 / 13 = 69 ％。

3.一個頁式存儲管理系統(tǒng)使用FIFO 、OPT 和LRU 頁面替換算法，如果一個作業(yè)的頁面走向為：

( l ) 2 、3 、2 、l 、5 、2 、4 、5 、3 、2 、5 、2 。

( 2 ) 4 、3 、2 、l 、4 、3 、5 、4 、3 、2 、l 、5 。

( 3 ) 1 、2 、3 、4 、1 、2 、5 、l 、2 、3 、4 、5 。

當分配給該作業(yè)的物理塊數(shù)分別為3 和4 時，試計算訪問過程中發(fā)生的缺頁中斷次數(shù)和缺頁中斷率。

答：( l ）作業(yè)的物理塊數(shù)為3 塊，使用FIFO 為9 次，9 / 12 = 75 ％。使用LRU 為7 次，7 / 12 = 58 ％。使用OPT 為6 次，6 / 12 = = 50 ％。
作業(yè)的物理塊數(shù)為4 塊，使用FIFO 為6 次，6 / 12 = 50 ％。使用LRU 為6 次，6 / 12 = 50 ％。使用OPT 為5 次，5 /12 = 42 ％。 
( 2 ）作業(yè)的物理塊數(shù)為3 塊，使用FIFO 為9 次，9 / 12 = 75 ％。使用LRU 為10 次，10 / 12 = 83 ％。使用OPT 為7 次，7/12 = 58 ％。
作業(yè)的物理塊數(shù)為4 塊，使用FIFO 為10 次，10 / 12 = 83 ％。 使用LRU 為8 次，8/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ū)的請求：( l ) 12K 、10K 、9K , ( 2 ) 12K 、10K 、15K 、18K 試問：使用首次適應(yīng)算法、最佳適應(yīng)算法、最差適應(yīng)算法和下次適應(yīng)算法，哪個空閑區(qū)被使用？

答：( 1 ）空閑分區(qū)如圖所示。

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

5.給定內(nèi)存空閑分區(qū)，按地址從小到大為：100K 、500K 、200K 、300K 和600K ?，F(xiàn)有用戶進程依次分別為212K 、417K 、112K 和426K , ( l ）分別用first-fit 、best-fit 和worst-fit 算法將它們裝入到內(nèi)存的哪個分區(qū)？( 2 ）哪個算法能最有效利用內(nèi)存？

答：按題意地址從小到大進行分區(qū)如圖所示。
( 1 ) 1）first-fit 212KB 選中分區(qū)2 ，這時分區(qū)2 還剩288KB 。417KB 選中分區(qū)5 ，這時分區(qū)5 還剩183KB 。112KB 選中分區(qū)2 ，這時分區(qū)2 還剩176KB 。426KB 無分區(qū)能滿足，應(yīng)該等待。
2 ) best-fit 212KB 選中分區(qū)4 ，這時分區(qū)4 還剩88KB 。417KB 選中分區(qū)2 ，這時分區(qū)2 還剩83KB 。112KB 選中分區(qū)3 ，這時分區(qū)3 還剩88KB 。426KB 選中分區(qū)5 ，這時分區(qū)5 還剩174KB 。
3 ) worst-fit 212KB 選中分區(qū)5 ，這時分區(qū)5 還剩388KB 。417KB 選中分區(qū)2 , 這時分區(qū)2 還剩83KB 。112KB 選中分區(qū)5 ，這時分區(qū)5 還剩176KB 。426KB 無分區(qū)能滿足，應(yīng)該等待。
( 2 ）對于該作業(yè)序列，best-fit 算法能最有效利用內(nèi)存

6. 一個32 位地址的計算機系統(tǒng)使用二級頁表，虛地址被分為9 位頂級頁表，11位二級頁表和偏移。試問：頁面長度是多少？虛地址空間共有多少個頁面？

答：32-9-11＝ 12 ，所以，頁面大小為2的12次方B ＝ 4KB ，頁面的個數(shù)為2的20次方個。

7. 一進程以下列次序訪問5 個頁：A 、B 、C 、D 、A 、B 、E 、A 、B 、C 、D 、E ：假定使用FIFO 替換算法，在內(nèi)存有3 個和4 個空閑頁框的情況下，分別給出頁面替換次數(shù)。

答：如下圖進行分析,內(nèi)存有3 個和4 個空閑頁框的情況下，頁面替換次數(shù)為9 次和10 次。出現(xiàn)了Belady 即現(xiàn)象，增加分給作業(yè)的內(nèi)存塊數(shù)，反使缺頁中斷率上升。

8.某計算機有緩存、內(nèi)存、輔存來實現(xiàn)虛擬存儲器。如果數(shù)據(jù)在緩存中，訪問它需要Ans；如果在內(nèi)存但不在緩存，需要Bns 將其裝入緩存，然后才能訪問；如果不在內(nèi)存而在輔存，需要Cns 將其讀入內(nèi)存，然后，用Bns 再讀入緩存，然后才能訪問。假設(shè)緩存命中率為（n-1) / n ，內(nèi)存命中率為（m -1) / m ，則數(shù)據(jù)平均訪問時間是多少？

答：
數(shù)據(jù)在緩存中的比率為：( n - 1 ) / n 
數(shù)據(jù)在內(nèi)存中的比率為：( 1 -（n - 1 ) / n )×( m - 1 ) / m = ( m - 1 ）/nm 
數(shù)據(jù)在輔存中的比率為：( 1 -（n －1 ) / n )×( 1－（m －1 ) / m ）1/nm 
故數(shù)據(jù)平均訪問時間是＝( ( n- 1 ) / n ) × A + ( ( 1 -（n - 1 ) / n ) × ( m-1 ) / m ) × ( A + B ) + ( ( 1-（n -1 ) / n ) ×( 1-（m-1）/ m ) ) × ( A + B + C ) = A + B / n + C / nm

9. 某計算機有cache 、內(nèi)存、輔存來實現(xiàn)虛擬存儲器。如果數(shù)據(jù)在cache 中，訪問它需要20ns ；如果在內(nèi)存但不在cache ，需要60ns 將其裝入緩存，然后才能訪問；如果不在內(nèi)存而在輔存，需要12us將其讀入內(nèi)存，然后，用60ns 再讀入cache ，然后才能訪問。假設(shè)cache 命中率為0 .9 ，內(nèi)存命中率為0.6 ，則數(shù)據(jù)平均訪問時間是多少（ns )

20*0.9+0.1*0.6*(60+20)+0.1*0.4*(12000+60+20) = 506 ns

10.有一個分頁系統(tǒng)，其頁表存放在主存里，( 1 ）如果對內(nèi)存的一次存取要1.2 微秒，試問實現(xiàn)一次頁面訪問的存取需花多少時間？( 2 ）若系統(tǒng)配置了聯(lián)想存儲器，命中率為80 % ，假定頁表表目在聯(lián)想存儲器的查找時間忽略不計，試問實現(xiàn)一次頁面訪問的存取時間是多少？

答：(1) 2.4 微秒 （2 )0.8 × 1.2 + 0.2 × 2.4 = 0.76 + 0.45 = 1.24 微秒

11.給定段表如下：

給定地址為段號和位移：

(1) [ 0 , 430]

(2) [ 3 , 400 ］

(3) [ 1 , 1 ］

(4) [ 2 , 500 ］

(5) [ 4 , 42 )

試求出對應(yīng)的內(nèi)存物理地址。

答：(1) 649 (2) 1727 (3) 2301 (4)越界 (5) 1994

12、 某計算機系統(tǒng)提供24 位虛存空間，主存為2 18 B ，采用分頁式虛擬存儲管理，頁面尺寸為1KB 。假定用戶程序產(chǎn)生了虛擬地址11123456 （八進制），而該頁面分得塊號為100 ( 八進制），說明該系統(tǒng)如何產(chǎn)生相應(yīng)的物理地址及寫出物理地址。

答：虛擬地址11123456 （八進制）轉(zhuǎn)化為二進制為：
001 001 001 010 011 100 101 110
其中前面為頁號，而后10 位為位移：001 001 001 010 01-------1 100 101 110 。由于主存大小為218 B，頁面尺寸為1KB ，所以，主存共有256 塊。所以，塊號為100 （八進制）是合法地址，于是，物理地址為100 （八進制）與位移1 100 101 110 并接，得到：八進制物理地址001000000 1 100 101 110 = 201456 （八進制）。

13.主存中有兩個空間區(qū)如圖所示，

現(xiàn)有作業(yè)序列依次為：Job1 要求30K ; Job2 要求70K ; Job3 要求50K ；使用首次適應(yīng)、最壞適應(yīng)和最佳適應(yīng)算法處理這個作業(yè)序列，試問哪種算法可以滿足分配？為什么？

答：首次適應(yīng)、最壞適應(yīng)算法處理這個作業(yè)序列可以滿足分配，最佳適應(yīng)算法不行。因為后者會分割出無法使用的碎片，浪費內(nèi)存，從而，不能滿足所有作業(yè)的內(nèi)存需求。

14.設(shè)有一頁式存儲管理系統(tǒng)，向用戶提供的邏輯地址空間最大為16 頁，每頁2048 字節(jié)，內(nèi)存總共有8 個存儲塊。試問邏輯地址至少應(yīng)為多少位？內(nèi)存空間有多大？

答： 
邏輯地址211×24 ，故為15 位。內(nèi)存大小為23×211 = 214B = 16KB 

15.在一分頁存儲管理系統(tǒng)中，邏輯地址長度為16 位，頁面大小為4096 字節(jié)，現(xiàn)有一邏輯地址為ZF6AH ，且第0 、1 、2 頁依次存在物理塊10 、12 、14 號中，問相應(yīng)的物理地址為多少？

答：因為邏輯地址長度為16 位，而頁面大小為4096字節(jié)，所以，前面的4 位表示頁號。把ZF6AH 轉(zhuǎn)換成二進制為：00 10 1 1 11 0110 1010 ，可知頁號為2 。故放在14 號物理塊中，寫成十六進制為：EF6AH 

16.有矩陣：VAR A : ARRAY [ 1 …100 , 1 …100 ] OF integer；元素按行存儲。在一虛存系統(tǒng)中，采用LRU 淘汰算法，一個進程有3 頁內(nèi)存空間，每頁可以存放200 個整數(shù)。其中第1 頁存放程序，且假定程序已在內(nèi)存。

程序A :

FOR i : = 1 TO 100 DO

FOR j : = 1 TO 100 DO

A [i，j ] : = 0 ;

程序B :

FOR j : = 1 TO 100 DO

FOR i : = 1 TO 100 DO

A [ i,j ] : = 0 ;

分別就程序A 和B 的執(zhí)行進程計算缺頁次數(shù)。

答：100 * 100 = 10000 個數(shù)據(jù)，每頁可以存放200 個整數(shù)，故一共存放在50 個第99 行、第100 行缺頁中斷為5000 次。由于元素按行存儲，第1 行、第2 行放在第1 頁，… 第99行、第100行放在第50 頁。故對于程序A ，缺頁中斷為50 次。對于程序B，缺頁中斷為5000次。 

17.一臺機器有48 位虛地址和32 位物理地址，若頁長為8KB ，問頁表共有多少個頁表項？如果設(shè)計一個反置頁表，則有多少個頁表項？

答：因為頁長8KB = 2的13次方 占用13 位，所以，頁表項有2的35次方個。反置頁表項有2的19次方個。

18.

答：t1 時刻的工作集為：{ l , 2 , 3 , 6 , 7 , 8 , 9 ｝。t 時刻的工作集為：{ 3 , 4 ｝。

19.有一個分頁虛存系統(tǒng)，測得CPU 和磁盤的利用率如下，試指出每種情況下的存在問題和可采取的措施：( 1 ) CPU 利用率為13 % ，磁盤利用率為97 % ( 2 ) CPU 利用率為87 % ，磁盤利用率為3 % ( 3 ) CPU 利用率為13 % ，磁盤利用率為3 ％。

答：( 1 )系統(tǒng)可能出現(xiàn)抖動，可把暫停部分進程運行。( 2 )系統(tǒng)運行正常，可增加運行進程數(shù)以進一步提高資源利用率。( 3 )處理器和設(shè)備和利用率均很低，可增加并發(fā)運行的進程數(shù)。

20.在一個分頁虛存系統(tǒng)中，用戶編程空間32 個頁，頁長IKB ，主存為16KBo 如果用戶程序有10 頁長，若己知虛頁0 、1 、2 、3 ，己分到頁框8 、7 、4 、10 , 試把虛地址OACSH 和IACSH 轉(zhuǎn)換成對應(yīng)的物理地址。

答：虛地址OACSH 對應(yīng)的物理地址為：12CSH 。而執(zhí)行虛地址IACSH 會發(fā)現(xiàn)頁表中尚未有分配的頁框而發(fā)生缺頁中斷，由系統(tǒng)另行分配頁框。

21 某計算機有4 個頁框，每頁的裝入時間、最后訪問時間、訪問位R 、修改位D 如下所示（時間用時鐘點數(shù)表示）:

page loaded last ref R D

0 126 279 0 0

1 230 260 1 0

2 120 272 1 1

3 160 280 1 1

分別用FIFO 、LRU 、二次機會算法分別淘汰哪一頁？

答：( 1 ) FIFO 淘汰page2 。
( 2 ) LRU 淘汰page1 。
( 3 )二次機會淘汰page1

22.考慮下面的程序：for ( i = 0;i < 20; i++）

For(j=0;j<10;j++)

a [ i ] : = a [i] ×j

試舉例說明該程序的空間局部性和時間局部性。

答：當數(shù)組元素a [0] , a[1] ，… ，a [ 19 ] 存放在一個頁面中時，其空間局部性和時間局部性較好，也就是說，在很短時間內(nèi)執(zhí)行都掛行循環(huán)乘法程序，而且數(shù)組元素分布在緊鄰連續(xù)的存儲單元中。當數(shù)組元素存放在不同頁面中時，其時間局部性雖相同，但空間局部性較差，因為處理的數(shù)組元素分布在不連續(xù)的存儲單元中。

23.一個有快表的請頁式虛存系統(tǒng)，設(shè)內(nèi)存訪問周期為1 微秒，內(nèi)外存?zhèn)魉鸵粋€頁面的平均時間為5 毫秒。如果快表命中率為75 % ，缺頁中斷率為10 ％。忽略快表訪問時間，試求內(nèi)存的有效存取時間。

答：快表命中率為75 % ，缺頁中斷率為10 % ，所以，內(nèi)存命中率為15％。故內(nèi)存的有效存取時間＝1×75 % + 2*15%+( 5000+2) *10%=501.25 微秒。

24.假設(shè)某虛存的用戶空間為IO24KB ，頁面大小為4KB ，內(nèi)存空間為512KB 。已知用戶的虛頁10 、11 、12 、13 頁分得內(nèi)存頁框號為62 、78 、25 、36 ，求出虛地址OBEBC ( 16 進制）的實地址（16 進制）是多少？

答：虛地址0BEBC ( 16 進制）的二進制形式為：0000 1 011 1110 10111100 。由于頁面大小為4KB ，故其中后12 位是位移，所以，虛地址的頁號為：11 。查頁表分得內(nèi)存對應(yīng)頁框號為：78 。己知內(nèi)存空間為512KB ，故內(nèi)存共有128 個頁框，78 是合法物理塊。把78 化為16 進制是4E ，虛地址OBEBC ( 16 進制）的實地址（16 進制）是：4EEBC 。

25.某請求分頁存儲系統(tǒng)使用一級頁表，假設(shè)頁表全部放在主存內(nèi)，:

1 ）若一次訪問主存花120ns ，那么，訪問一個數(shù)據(jù)的時間是多少？

2 ）若增加一個快表，在命中或失誤時需有20ns 開銷，如果快表命中率為80 % ，則

訪問一個數(shù)據(jù)的時間為

答：
( 1 ) 120ns*2 = 240ns 
( 2 ) ( 120 + 20 ) *80 % +(120+120+20)*20%=174ns

26 設(shè)某系統(tǒng)中作業(yè)J . , JZ , J3 占用主存的情況如圖。今有一個長度為20k 的作業(yè)J4 要裝入主存，當采用可變分區(qū)分配方式時，請回答：

( l ) J4 裝入前的主存己分配表和未分配表的內(nèi)容。

( 2 ）寫出裝入J4 時的工作流程，并說明你采用什么分配算法。

10k 18k 30k 40k 54k70k

答：( 1 ）主存已分配表共有三項，由作業(yè)j1 、j2 、j3 占用，長度依次為：10k 、30k 和54k 未分配表共有三項：空閑區(qū)1 、空閑區(qū)2 和空閑區(qū)3 ，長度依次為18k 、40k 和70k 。( 2 ）作業(yè)J4 裝入時，采用直接分配，搜索未分配表，空閑區(qū)1 不能滿足。所以，要繼續(xù)搜索未分配表，空閑區(qū)2 可以滿足J4 的裝入要求。

27.考慮下列的段表：

段號始址段長: 段號 始址 段長

0 200 500

1 890 30

2 120 100

3 1250 600

4 1800 88

對下面的邏輯地址，求物理地址，如越界請指明。( l ) ＜0,480 > ( 2 ) < l ,25 > ( 3 ) < l ,14 > ( 4 ) < 2 , 200>( 5 ) < 3 ,500 > ( 6 ) < 4 ,100 > .

答：( l ) 680 ( 2 ) 915 ( 3 ) 904 ( 4 ）越界 ( 5 ) 1750 ( 6 ）越界。

28.請頁式存儲管理中，進程訪問地址序序列為：10 , 11 , 104 , 170 , 73 , 305 , 180 , 240 , 2 科，科5 , 467 , 366。試問( 1 ）如果頁面大小為100 ，給出頁面訪問序列。(2 )進程若分3個頁框采用

FIFO 和LRU 替換算法，求缺頁中斷率？

答：( l ）頁面訪問序列為l , l , 2 , 2 , 1 , 4, 2 , 3 , 3 , 5 , 5 , 4 。
2 ) FIFO 為5 次，缺頁中斷率為5 / 12 科41.6 ％。LRU 為6 次，缺頁中斷率為6 / 12 = 50 ％。LRU 反比FIFO 缺頁中斷率高。

29.假設(shè)計算機有2M 內(nèi)存，其中，操作系統(tǒng)占用512K ，每個用戶程序也使用512K 內(nèi)存。如果所有程序都有70 ％的I/O 等待時間，那么，再增加1M 內(nèi)存，吞吐率增加多少？

答：由題意可知，內(nèi)存中可以存放3 個用戶進程，而CPU 的利用率為：1-（70 % )3 , = 1 一（0 . 7 )3 = 65 . 7 ％。再增加1M 內(nèi)存，可增加2 個用戶進程，這時CPU 的利用率為：1 -（70 % )5 , = 1 一（0 ．7）5＝83 . 2 ％。故再增加1M 內(nèi)存，吞吐率增加了：83 . 2 ％/65 . 7 ％-100 % =27 ％。

30.一個計算機系統(tǒng)有足夠的內(nèi)存空間存放4 道程序，這些程序有一半時間在空閑等待I/O 操作。問多大比例的CPU 時間被浪費掉了？

答：( 500 % )＝( l / 2 ) = 1 / 16 。

31.如果一條指令平均需1 微秒，處理一個缺頁中斷另需n 微秒，給出當缺頁中斷每k 條指令發(fā)生一次時，指令的實際執(zhí)行時間。

答：( 1 +n/k)微秒。

32.一臺計算機的內(nèi)存空間為1024 個頁面，頁表放在內(nèi)存中，從頁表中讀一個字的開銷是50Ons 。為了減少開銷，使用了有32 個字的快表，查找速度為10Ons 。要把平均開銷降到20Ons 需要的快表命中率是多少？

答：設(shè)快表命中率是x ，則內(nèi)存命中率為1-x。于是：500 ( 1-x）+ 100x = = 2 00 ，解方程得x=75 ％。

33.假設(shè)一條指令平均需花1 微秒，但若發(fā)生了缺頁中斷就需2001 微秒。如果一個程序運行了60 秒，期間發(fā)生了15000 次缺頁中斷，若可用內(nèi)存是原來的兩倍，這個程序壇行需要多少時間？

答：一個程序運行期間發(fā)生了15000 次缺頁中斷，由于缺頁中斷處理花2000 微秒（1 微秒是指令執(zhí)行時間，于是這個程序缺頁中斷處理花了：2000 微秒米1 5000 = 30 秒。占了運行時間60 秒的一半。當可用內(nèi)存是原來的兩倍時，缺頁中斷次數(shù)減為一半，故有巧秒就能處理完。所以，這個程序運行需要時間為：45 秒。

34.在分頁式虛存管理中，若采用FIFO替換算法，會發(fā)生：分給作業(yè)頁面越多，進程執(zhí)行時缺頁中斷率越高的奇怪現(xiàn)象。試舉例說明這個現(xiàn)象。

答：見本章應(yīng)用題7 。

35.假設(shè)一個任務(wù)被劃分成4 個大小相等的段，每段有8 項的頁描述符表，若頁面大小一為ZKB 。試問段頁式存儲系統(tǒng)中：( a ）每段最大尺寸是多少？偽）該任務(wù)的邏輯地址空間最大為多少？( c ）若該任務(wù)訪問到邏輯地址空間5ABCH 中的一個數(shù)據(jù)，試給出邏輯地址的格式。

答：段數(shù)2 2 = 4 ，每段有23 = 8 頁，頁大小為211= ZKB 。（a ）故每段最大為214B = 16KB 。偽）邏輯她曳匕勿風爆七尺4 又、曰KB = 64KB 。
( c ）若該任務(wù)訪問到邏輯地址空間SABCH ，其二進制表示為：
0 101 1010 1011 1100 
所以，邏輯地址表示為：01 011 010 1011 1100 
SABCH 的邏輯地址為：第1 段第3 頁，位移由后11 位給出。

36.對已知某系統(tǒng)頁面長4KB ，頁表項4B ，采用多級頁表映射64 位虛地址空間。若限定最高層頁表占1 頁，問它可以采用幾級頁表？

答：由于頁面長4KB ，頁表項4B ，故每頁可· 包含IKB 個頁表項。由于限定最高層頁表占1 頁，即它的頁表項為210個；而每個頁表項指向一頁，每頁又存放頁表項個數(shù)為210 個，依此類推，最多可以采用硯巧取整為6 級頁表。

37.在請求分頁虛存管理系統(tǒng)中，若駐留集為m 個頁框，頁框初始為空，在長為p 的引用串中具有n 個不同頁面n＞m ) ，對于FIFO、LRU 兩種頁面替換算法，試給出缺頁中斷的上限和下限，并舉例說明。

答：對于FIFO 、LRU 兩種頁面替換算法，缺頁中斷的上限和下限：為p 和n 。因為有n 個不同頁面，無論怎樣安排，不同頁面進入內(nèi)存至少要產(chǎn)生一次缺頁中斷，故下限為n 次。由于m<n ，引用串中有些頁可能進入內(nèi)存后又被調(diào)出，而多次發(fā)生缺頁中斷。極端情況，訪問的頁都不在內(nèi)存，這樣共發(fā)生了p 次缺頁中斷。例如，當vm =3 ，p=12 , n =4 時，有如下訪問中：1 , 1 , 1 , 2 , 2 , 3 , 3 , 3 , 4 , 4 , 4 , 4 。缺頁中斷為下限4 次。而訪問串：2 , 3 , 4 , 1 , 2 , 3, 4 , 1 , 2 , 3 , 4 , 1 。缺頁中斷為上限12 次。

38.在請求分頁虛存管理系統(tǒng)中，頁表保存在寄存器中。若替換一個未修改過頁面的缺頁中斷處理需8 毫秒，若替換一個己修改過頁面的缺頁中斷處理需另加寫盤時間12 毫秒，內(nèi)存存取周期為1 微秒。假定70 ％被替換的頁面被修改過，為保證有效存取時間不超過2 微秒，允許的最大缺頁中斷率為多少？

答：設(shè)最大缺頁中斷率為x ，則有：
( l - x ) *1 微秒＋( 1 -70 % ) *X*8 毫秒＋70 % *X *( 8 + 12 ) = 2 微秒
即得到-x +2400x + 14000x =1 ，解得：x 約為0 .00006 。

39.若內(nèi)存按地址遞增次序有三個不鄰接的空閑區(qū)Fl 、F2 、F3 ，它們的大小分別是：50K 、120K 和25K 。請給出后備作業(yè)序列，使得實施分配時：( l ）采用最佳適應(yīng)算法效果好，但采用首次適應(yīng)與最壞適應(yīng)算法效果不好。（2 ）采用最環(huán)適應(yīng)算法效果好，但采用首次適應(yīng)與最佳適應(yīng)算法效果不好。

答:
( 1 ）采用最佳適應(yīng)算法效果好，120 , 50 。
( 2 ）采用最環(huán)適應(yīng)算法效果好，80 , 50 , 25 。
但采用首次適應(yīng)與最壞適應(yīng)算法效果不好。作業(yè)序列：25 
但采用首次適應(yīng)與最佳適應(yīng)算法效果不好。作業(yè)序列：40 

40.有兩臺計算機P1 和P2，它們各有一個硬件高速緩沖存儲器Cl 和CZ ，且各有一個主存儲器Ml 和M2。其性能為：

C1 C2 Ml M2

存儲容量 4KB 4KB 2MB 2MB

存取周期 60ns 80ns 1 us 0.9 us

若兩臺機器指令系統(tǒng)相同，它們的指令執(zhí)行時間與存儲器的平均存取周期成正比。如果在執(zhí)行某個程序時，所需指令或數(shù)據(jù)在高速緩沖存儲器中存取到的概率P 是0 . 7 ，試問：這兩臺計算機哪個速度快？當P = 0 .9 時，處理器的速度哪個快？答：CPU 平均存取時間為：T = = T1+（1 -p）*T2 ,T1 為高速緩沖存儲器存取周期，T2 為主存儲器存取周期，p 為高速緩沖存儲器命中率。

答：( 1 ）當p=0 . 7 時，
Pl 平均存取時間為：60 + ( 1 -0 . 7 ) * 1 us = 360ns 
PZ 平均存取時間為：80 + ( 1 -0 . 7 ) *0.9 us= 350ns 
故計算機P2比P1 處理速度快。
( 2 ）當p = 0 . 9 時，
P1 平均存取時間為：60 + ( 1 -0.9 ) * 1 us = 160ns 
PZ 平均存取時l ' ed 為：80 + ( l -0 .9 ) *0 .9 us = 170ns 
故計算機P1 比P2處理速度快。 

第五章 設(shè)備管理

1.旋轉(zhuǎn)型設(shè)備上信息的優(yōu)化分布能減少為若干個拍服務(wù)的總時間．設(shè)磁鼓上分為20 V 個區(qū)，每區(qū)存放一個記錄，磁鼓旋轉(zhuǎn)一周需20 毫秒，讀出每個記錄平均需用1 毫秒，讀出后經(jīng)2 毫秒處理，再繼續(xù)處理下一個記錄。在不知當前磁鼓位置的情況下：

( 1 ）順序存放記錄1 、… … ，記錄20 時，試計算讀出并處理20 個記錄的總時間；

( 2 ）給出優(yōu)先分布20 個記錄的一種方案，使得所花的總處理時間減少，且計算出這個方案所花的總時間。

答：定位第1個記錄需10m s 。讀出第1 個記錄，處理花2ms ，這時已到了第4個記錄，再轉(zhuǎn)過18 個記錄（花18ms ）才能找到記錄2 ，所以，讀出并處理20 個記錄的總時間：10 + 3 + ( l + 2 + 18 ) * 19 = 13 + 2 1 * 19 =412ms
如果給出優(yōu)先分布20 個記錄的方案為：1 , 8 , 15 ,2 , 9 , 16 , 3 , 10 , 17 , 4 , 11 , 18 , 5 , 12 , 19 , 6 , 13 , 20 , 7 , 14 。當讀出第1 個記錄，花2ms 處理后，恰好就可以處理記錄2 ，省去了尋找下一個記錄的時間，讀出并處理20 個記錄的總時間：
10+3+3*19=13+247=260ms 

2.現(xiàn)有如下請求隊列：8 , 18 , 27 , 129 , 110 , 186 , 78 , 147 ,41 , 10 , 64 , 12 ：試用查找時間最短優(yōu)先算法計算處理所有請求移動的總柱面數(shù)。假設(shè)磁頭當前位置下在磁道1000

答：處理次序為：100 -110 -129 -147 -186 -78 -64 -41 -27 -18 -12-10 -8 。移動的總柱面數(shù)：264。

3.上題中，分別按升序和降序移動，討論電梯調(diào)度算法計算處理所有存取請求移動的總柱面數(shù)。

答：升序移動次序為：100 -110 -129 -147 -186 -78 -64 -41 -27 -18-12 -10 -8 。移動的總柱面數(shù)：264 。
降序移動次序為：100 -78 -64 -4l -27 -18 -12 -10 -8 -110 -129 -147 -186 。移動的總柱面數(shù)：268

4.某文件為連接文件，由5 個邏輯記錄組成，每個邏輯記錄的大小與磁盤塊大小相等，均為512 字節(jié)，并依次存放在50 、121、75 、80 、63 號磁盤塊上?，F(xiàn)要讀出文件的1569 字節(jié)，問訪問哪一個磁盤塊？

答：80 號磁盤塊

5.對磁盤存在下面五個請求：假如當前磁頭位于1號柱面，試分析對這5個請求如何調(diào)度可使得磁盤的旋轉(zhuǎn)圈數(shù)最少？

答:最少調(diào)度次序 :5.3.2.1.和4

6.有一具有40 個磁道的盤面，編號為0-39 ，當磁頭位于第n 磁道時，順序來到如下磁道請求：磁道號：1 、36 、16 、34 、9 、12 ；試用l ）先來先服務(wù)算法FCFS 、2 ) 最短查找時間優(yōu)先算法SSTF、3 ）掃描算法SCAN 等三種磁盤驅(qū)動調(diào)度算法，計算出它們各自要來回穿越多少磁道？

答：(1 ) FCFs 為111 (2 ) SSTF 為61 (3 ) SCAN 為60 （先掃地址大的請求），為45 （先掃地址小的請求）。

7.假定磁盤有200 個柱面，編號O - 199 ，當前存取臂的位置在143 號柱面上，并剛剛完成了125 號柱面的服務(wù)請求，如果請求隊列的先后順序是：86 , 147 , 91 , 177 , 94 , 150 , 102 , 175 , 130 ；試問：為完成上述請求，下列算法存取臂移動的總量是多少？并算出存取臂移動的順序。

( 1 ）先來先服務(wù)算法FCFS;

( 2 ）最短查找時間優(yōu)先算法SSTF :

( 3 ）掃描算法SCAN 。

( 4 ）電梯調(diào)度。

答：( l ）先來先服務(wù)算法FCFS 為565 ，依次為143 -86 -147 -91 -177 -94 -150 -102-175 -130 。( 2 ）最短查找時間優(yōu)先算法SSTF 為162 ，依次為143 -147 -150 -130 -102 -94 -91 -86-175 -177 。
( 3 ）掃描算法SCAN 為169 ，依次為143 -147 -150 -175 -177 -199 -130 -102 -94 -91 -86 。( 4 ）電梯調(diào)度為125，依次為143-147 -150 -175 -177 -130-102 -94 -91 -86 。

8.除FCFS 外，所有磁盤調(diào)度算法都不公平，如造成有些請求饑餓，試分析：( l ）為什么不公平？( 2 ）提出一種公平性調(diào)度算法。（3 ）為什么公平性在分時系統(tǒng)中是一個很重要的指標？

答：( l ）對位于當前柱面的新請求，只要一到達就可得到服務(wù)，但對其他柱面的服務(wù)則不然。如SST 下算法，一個離當前柱面遠的請求，可能其后不斷有離當前柱面近的請求到達而得不到服務(wù)（饑餓）。
( 2 ）可劃定一個時間界限，把這段時間內(nèi)尚未得到服務(wù)的請求強制移到隊列首部，并標記任何新請求不能插到這些請求前。對于SSTF 算法來說，可以重新排列這些老請求，以優(yōu)先處理。
( 3 ）可避免分時進程等待時間過長而拉長響應(yīng)時間。

9.若磁頭的當前位置為100 柱面，磁頭正向磁道號減小方向移動?，F(xiàn)有一磁盤讀寫請求隊列，柱面號依次為：190 , 10 , 160 , 80 , 90 , 125 , 30 , 20 , 29 , 140 , 25 ．若采用最短尋道時間優(yōu)先和電梯調(diào)度算法，試計算出各種算法的移臂經(jīng)過的柱面數(shù)？

答：采用SSTF 處理次序為：100 - 90 一80 一125 一140 一160 一190 一30 一29 一5 一20 一10 ，總柱面數(shù)為：3 10 。采用電梯調(diào)度處理次序為：100 - 90 一80 一30 一29 一25 一20 。10 一125 一140 一160 一190 ，總柱面數(shù)為：270 。

10.若磁頭的當前位置為100 柱面，磁頭正向磁道號增加方向移動。現(xiàn)有一磁盤讀寫請求隊列，柱面號依次為：23 , 376 , 205 , 132 , 19 , 61 , 190 , 398 , 29 , 4 , 18 , 40 。若采用先來先服務(wù)、最短尋道時間優(yōu)先和掃描算法，試計算出各種算法的移臂經(jīng)過的柱面數(shù)？

答：采用先來先服務(wù)處理次序為：100 一3 一376 一05 一132 一19 一61 一190 一398 - 29 -4-18 -40 ，總柱面數(shù)為：15960 
采用SSTF 處理次序為：100 一132 一190 一05 一61 -40 一9 一3 一19 一18 -4 一376 一398 ，總柱面數(shù)
處理次序為：100 -132 一190 一205 一376 一398 一140 一29 一23 一19 一18 -4，總柱面數(shù)

11.設(shè)有長度為L 個字節(jié)的文件存到磁帶上，若規(guī)定磁帶物理塊長為B字節(jié)，試問：存放該文件需多少塊？( 2 ）若一次啟動磁帶機交換K塊，則存取這個文件需執(zhí)行操作多少次？

( l ）求IJB ，如整除則需”商”個塊數(shù)，否則為”商＋l ”個塊數(shù)．
( 2 ）把上述結(jié)果再除以K ，可求出存取這個文件需執(zhí)行的拍操作次數(shù)。

12.某磁盤共有200 個柱面，每個柱面有20 個磁道，每個磁道有8 個扇區(qū)，每個扇區(qū)為1024B ．如果驅(qū)動程序接到訪求是讀出606 塊，計算該信息塊的物理位置。

答:（ l ）每個柱面的物理塊數(shù)為20 XS = 160 塊。
( 2 ) 606 / 160。得到商為3 ，余數(shù)為126 。故可知訪求的物理位置在：第3 個柱面（0 柱面開始編號）的126 物理塊中。

13.假定磁帶記錄密度為每英寸800 字符，每一邏輯記錄為160個字符，塊間隙為0 . 6 英寸。今有1 500 個邏輯記錄需要存儲，嘗試：( 1 ）計算磁帶利用率？( 2 ）1500個邏輯記錄占用多少磁帶空間？( 3 ）若要使磁帶空間利用率不少于50 % ，至少應(yīng)以多少個邏輯記錄為一組？

( 1 ）間隙可以存放的字符數(shù)是：800 x 0 . 6 = 480 個字符。這時磁帶的利用率為：160 / ( 48 +160 ) = 25 % 
( 2 ) 1500* ( 480+160 ) / 800 = 1200 英寸。
( 3 ）設(shè)成組塊因子為x ，則有：
( 160x ) / ( 480 + 160x ) >=50 % 
x >3 ，因而，記錄成組的塊因子至少為3 。

14.假定磁帶記錄密度為每英寸800 字符，每一邏輯記錄為200字符，塊間隔為0 . 6 英寸?，F(xiàn)有3200 個邏輯記錄需要存儲，如果不考慮存儲記錄，則不成組處理和以8 個邏輯記錄為一組的成組處理時磁帶的利用率各是多少？兩種情況下，3200 個邏輯記錄需要占用多少磁帶空間？

間隙可以存放的字符數(shù)是：800 *0.6=480 個字符。
( l ）記錄不成組時，一個邏輯記錄占用一個物理塊存儲，這時磁帶的利用率為：
200 / ( 480+200 )=29 % 占用磁帶空間為：3200* ( 4 800 + 200 ）/800 = 2720 英寸．( 2 ）記錄成組的塊因子為8 時，這時磁帶的利用率為：200 *8 / ( 4 800 + 200 *8 ) =?76 . 9 % 占用磁帶空間為：3200 /8*( 480+200*8）/800 = l 040 英寸。

15.一個軟盤有40 個柱面，查找移過每個柱面花6ms ．若文件信息塊零亂存放，則相鄰邏輯塊平均間隔13 個柱面．但優(yōu)化存放，相鄰邏輯塊平均間隔為2 個柱面．如果搜索延遲為100ms ，傳輸速度為每塊25ms ，現(xiàn)問在兩種情況下傳輸100 塊文件信息各需多長時間。

答：非優(yōu)化存放，讀一塊數(shù)據(jù)需要時間為：13 *6 十100 十25 = = 203ms 因而，傳輸100 塊文件需：2O300ms 。優(yōu)化存放，讀一塊數(shù)據(jù)需要時間為：2*6 十100 + 25 = = 137ms 因而，傳輸100 塊文件需：13700ms 。

16.磁盤請求以10 、22 、20 、2 、40 、6 、38 柱面的次序到達磁盤驅(qū)動器，如果磁頭當前位于柱面20 。若查找移過每個柱面要花6ms ，用以下算法計算出查找時間：1 ) F CFS , 2 )

最短查找優(yōu)先，3 ）電梯調(diào)度（正向柱面大的方向）.

答：
(1)FCFS 查找時間次序為：20 、10 、22 、2 、40、6、38、、查找時間為867ms
(2)最短查找優(yōu)先查找次序為：20 、20 、22 ??10 、6 、2 、38 、40、查找時間為360ms
(3)電梯調(diào)度查找次序為：20 、20 、22 、38 、40 、10 、6 、2 ，查找時間為：348ms . 

17.今假定在某移動臂磁盤上，剛剛處理了訪問一信息，并且有下述請求序列等待訪問磁盤

75 號柱面的請求，目前正在80 號柱面讀信息,并且有下請求序列等待訪問磁盤:

試用：( l ）電梯調(diào)度算法( 2 ）最短尋找時間優(yōu)先算法分別列出實際處理上述請求的次序。

答：( l ）電梯調(diào)度算法查找次序為：80 、90 、102 、160 、188 、190 、58 、40 、32 ，總柱面數(shù)為：268 . 
( 2 ）最短查找優(yōu)先查找次序為：80 、90 、102 、58 、40 、32 、160 、188 、190總柱面數(shù)為：250 。

18.計算機系統(tǒng)中，屏幕顯示分辨率為640x 480 ，若要存儲一屏256 彩色的圖像，需要多少字節(jié)存儲空間？

答：屏幕信息顯示以象素為單位，分辨率為640x 480 時，屏幕象素有640X480 = = 300 x 210 個。當用256 彩色顯示時，每個象素用8 位二進數(shù)表示（2 、256 ) ．因而，存儲一屏
彩色的圖像需要：8*300*210 位＝300*210 字節(jié)＝= 300K 字節(jié)。

19 .磁盤組共有n 個柱面，編號順序為O 、1 、2 、…、n-1 ；共有m 個磁頭，編號順序為0 、1 、2 、…、m -1 ：每個磁道內(nèi)的k 個信息塊從1 開始編號，依次為1 、2 、…、k ?，F(xiàn)用x 表示邏輯磁盤塊號，用a ,b , c 分別表示任一邏輯磁盤塊的柱面號、磁頭號、磁道內(nèi)塊號，則x 與a 力，?？赏ㄟ^如下公式進行轉(zhuǎn)換：

x = k*m*a 十k*b + c

a = = ( x -l ) DIV (K*M )

b = ( ( x -l ) MOD (K*m ) ) DIVk

c = ( ( x -l ) MOD (K*m ) )MOD k + l

若某磁盤組為n = 200 , m =20 , k =10 ，問：

( 1 ）柱面號為185 ，磁頭號為12 ，道內(nèi)塊號為5 的磁盤塊的邏輯磁盤塊號為多少？( 2 ）邏輯磁盤塊號為1200 ，它所對應(yīng)的柱面號、磁頭號及磁道內(nèi)塊號為多少？( 3 ）若每一磁道內(nèi)的信息塊從。開始編號，依次為。、1 、… 、k -1 ，其余均同題設(shè)，試寫出x 與a 、b 、c 之間的轉(zhuǎn)換公式．

答：( 1 ）由上述公式可知，邏輯磁盤塊號x 為：
x = k*m*a+k*b+c =10*20*185+120+5= 37125 
所以，柱面號為185 ，磁頭號為12 ，道內(nèi)塊號為5 的磁盤塊的邏輯磁盤塊號為：37125 。( 2 ）由上述公式可知，
a=（X-1 ) DIV ( k *m )=（1200-l )DIV ( 10*20=1199 DIV 200 = 5 
b = ( ( x 一1 ) MOD ( k * m) ) DIV K=（( 1200 -1 ) MOD ( 10*20 ) ) DIV 10 
= = ( 1199 MOD 200 ) DIV 10 = =199 DIV 10 = 10 
c = ( ( x-l ) MOD ( k *m ) ) MOD k + l = ( ( 1200 一1 )MOD ( 10X20 ) ) MOD 10 + 1 = = ( 1 199 MOD 200 ) MOD 10 + 1 = 199 MOD 10 + l =9 + l = = 10 
所以，邏輯磁盤塊號為1200 ，它所對應(yīng)的柱面號是5 、磁頭號是19 及磁道內(nèi)塊號為
( 3 ）轉(zhuǎn)換公式為：
x = k*m*a 十k*b + c + 1 
A=(x-1)DIV(k*m)
b = ( ( x 一1 ) MOD (k*m ) ) DIV K? 
c = ( ( x 一1 ) MOD ( k*m ）MOD k

第六章 文件管理

1 ．磁帶卷上記錄了若干文件，假定當前磁頭停在第j 個文件的文件頭標前，現(xiàn)要按名讀出文件i ，試給出讀出文件i 的步驟。

答：由于磁帶卷上的文件用“帶標”隔開，每個文件的文件頭標前后都使用了三個帶標。
正常情況磁頭應(yīng)停在文件頭標的前面，所以，只要計算帶標的個數(shù)，就可找到所要文件。
1 ）當i>=j 時，要正走磁帶，
步1 組織通道程序正走磁帶，走過“帶標”個數(shù)為3* ( i –j)個
步2 組織通道程序讀文件i 的文件頭標。
步3 根據(jù)文件i 的文件頭標信息，組織讀文件信息。
2 ）當i < j 時，要反走磁帶，
步1 組織通道程序反走磁帶，走過“帶標”個數(shù)為3 *(j-i)個，同時還要后退一塊，到達文件i 頭標前。
步2 組織通道程序讀文件i 的文件頭標。
步3 根據(jù)文件i 的文件頭標信息，組織讀文件信息。

2.假定令B ＝物理塊長、R = ＝邏輯記錄長、F ＝塊因子。對定長記錄（一個塊中有整數(shù)個邏輯記錄），給出計算F 的公式。

答：F = [B/R]

3.某操作系統(tǒng)的磁盤文件空間共有500 塊，若用字長為32 位的位示圖管理盤空間，試問：( 1 ）位示圖需多少個字？( 2 ）第i 字第j 位對應(yīng)的塊號是多少？( 3 ）并給出申諭歸還一塊的工作流程。

答:（1 ）位示圖占用字數(shù)為500 / 32 = 16 （向上取整）個字。
( 2 ）第i 字第j 位對應(yīng)的塊號卜32*i + j 。
( 3 ）申請時自上至下、自左至有掃描位示圖跳過為1 的位，找到第一個遷到的0 位，根據(jù)它是第i 字第j 位算出對應(yīng)塊號，并分配出去。歸還時已知塊號，塊號／32 算出第i 字第j 位并把位示圖相應(yīng)位清O 。

4.若兩個用戶共享一個文件系統(tǒng)，用戶甲使用文件A 、B 、C 、D 、E ；用戶乙要用到文件A 、D 、E 、F 。己知用戶甲的文件A 與用戶乙的文件A 實際上不是同一文件；甲、乙兩用戶的文件D 和E 正是同一文件。試設(shè)計一可以采用二級目錄或樹形目錄結(jié)構(gòu)來解決難題。文章來源地址http://www.zghlxwxcb.cn/news/detail-411259.html

5.在UNIX 中，如果一個盤塊的大小為IKB ，每個盤塊號占4 個字節(jié)，即每塊可放256 個地址。請轉(zhuǎn)換下列文件的字節(jié)偏移量為物理地址：( l ) 9999 ; ( 2 ) 18000 ; ( 3 )420000 。

答：步1 將邏輯文件的字節(jié)偏移量轉(zhuǎn)換為文件的邏輯塊號和塊內(nèi)偏移。方法是：將邏輯文件的字節(jié)偏移量／盤塊大小，商為文件的邏輯塊號，余數(shù)是塊內(nèi)偏移。二步2 將文件的邏輯塊號轉(zhuǎn)換為物理塊號。使用多重索引結(jié)構(gòu)，在索引節(jié)點中根據(jù)氰邏輯塊號通過直接索引或間接索引找到對應(yīng)物理塊號。
（1 、9000 LI ＝INT（9999 , 1024 ) = 9 Bl= MOD（9999 , 1024 ）783 
履其邏輯塊號為9 ，故直接索引addrr81 中可找到物理塊號。
（2 、15000 L2 = INT ( 15000, 1024 )17 BI = = MOD（15000 , 1024 ) = = 592 會其邏輯塊號為17 ，通過一次間接索引addr [10]中可找到物理塊號。
嚓（3 、420000 LI = ＝INT(420000 , 1024 )＝4 10 Bl MOD（9000 , 1024 ）=160 露其邏輯塊號為410 ，通過二次間接索引addr [ ll ］中可找到物理塊號．

6.在UNIX/LINUX系統(tǒng)中，如果當前目錄是／usr / wang ，那么，相對路徑為..／ast/xx文件的絕對路徑名是什么？

答：在U NIX/Linux 系統(tǒng)中，" / ' ’表示根目錄，" . ”是指當前目錄，“..”是指父目錄。在本題中當前目錄是lusr / wang，故相對路徑為..／ast /xxx 文件實際上是usr 目錄下的文件，故絕對路徑名是呀厄叫沁以。

7.一個UNIX 文件F 的存取權(quán)限為：rwxr-x...,該文件的文件主uid = 12 , gid=1 ，另一個用戶的uid = = 6 , gid = = 1，是否允許該用戶執(zhí)行文件F

答：F 的存取權(quán)限為：rwxr-x...，表示文件主可對F 進行讀、寫及執(zhí)行操作，同組用戶可
對F 進行讀及執(zhí)行操作，但其他用戶不能對F 操作。因為另一用戶的組標識符gid 相同所以，允許訪問。

8.設(shè)某文件為連接文件，由5 個邏輯記錄組成，每個邏輯記錄的大小與磁盤塊大小相等，均為512 字節(jié)，并依次存放在50 、121 、75 、80 、63 號磁盤塊上。若要存取文件的第1569 邏輯字節(jié)處的信息，問要訪問哪一個磁盤塊？

1569 / 512 得到商為：3 ，余數(shù)為：33 。所以，訪問的是互磁盤塊的第33 個字節(jié)。

9.一個UNIX/Linux 文件，如果一個盤塊的大小為1KB ，每個盤塊占4 個字節(jié)，那么，若進程欲訪問偏移為263 168 字節(jié)處的數(shù)據(jù)，需經(jīng)過幾次間接？

答：UNIX 口Linux 文件系統(tǒng)中，直接尋址為10 塊，一次間接尋址為256 塊，二次間接尋址為2562三次間接尋址為2563 塊。 偏移為263 168 字節(jié)的邏輯塊號是：263168 / 1024 = = 257．塊內(nèi)偏移量＝263168 -257*l024 = 0 。由于10 < 257 < 256+ 10 ，故263168 字節(jié)在一次間接尋址內(nèi)．

10.設(shè)某個文件系統(tǒng)的文件目錄中，指示文件數(shù)據(jù)塊的索引表長度為13 ，其中0 到9 項為直接尋址方式，后3 項為間接尋址方式。試描述出文件數(shù)據(jù)塊的索引方式；給出對文件第n 個字節(jié)（設(shè)塊長512 字節(jié)）的尋址算法．

答：索引表長度為13 ，其中O 到9 項為直接尋址方式，后3 項為一次、二次和三次間接尋址。
步1 將邏輯文件的字節(jié)偏移量轉(zhuǎn)換為文件的邏輯塊號和塊內(nèi)偏移。方法是：將邏輯文件的字節(jié)偏移量可盤塊大小（5 12 ) ，商為文件的邏輯塊號，余數(shù)是塊內(nèi)偏移．步2 將文件的邏輯塊號轉(zhuǎn)換為物理塊號。使用多重索引結(jié)構(gòu)，在索引節(jié)點中根據(jù)邏輯塊號通過直接索引或間接索引找到對應(yīng)物理塊號。再判別邏輯塊號在10 塊以內(nèi)或以上，分別采用可直接尋址，一次、二次和三次間接尋址。

11.設(shè)文件ABCD 為定長記錄的連續(xù)文件，共有18 個邏輯記錄。如果記錄長為5 12B , 物理塊長為1024B ，采用成組方式存放，起始塊號為12 ，敘述第巧號邏輯記錄讀入內(nèi)存緩沖區(qū)的過程。

答：采用成組方式存放，塊因子為2 。由于共有18 個邏輯記錄，故占用了9 個物理塊，而巧號邏輯記錄占用的是第1512 = 8 （向上取整）物理塊。因為，是連續(xù)文件物理塊也是連續(xù)，所以，該邏輯記錄占用的是12 + 8 -1 = 19 塊．所以，第15 號邏輯記錄讀入內(nèi)存緩沖區(qū)的過程如下：根據(jù)塊因子，計算占用的相對物理塊號8 ：根據(jù)起始塊號為12 ，計算出絕對物理塊號19 ；把物理塊號19 讀入內(nèi)存緩沖區(qū)；把所要的邏輯記錄分解出來。

12.若某操作系統(tǒng)僅支持單級目錄，但允許該目錄有任意多個文件，且文件名可任意長，試問能否模擬一個層次式文件系統(tǒng)？如能的話，如何模擬。

答：可以，文件名中可以用插入多個“/ ”來模擬文件分層。例如/usul /datafile/ data1和/user/datafil/data2但在此操作系統(tǒng)中，這些僅僅是包含“/ ' ’的單個文件名。

13.文件系統(tǒng)的性能取決于高速緩存的命中率，從高速緩存讀取數(shù)據(jù)需要lms ，從磁盤讀取數(shù)據(jù)需要40Ins 。若命中率為h ，給出讀取數(shù)據(jù)所需平均時間的計算公式，并畫出h 從0 到l 變化時的函數(shù)曲線。

答:讀取數(shù)據(jù)所需平均時間T=h*l + 4* ( 1 - h )= h + 40* ( 1 -h ）。

14.有一個磁盤組共有10 個盤面，每個盤面有100 個磁道，每個磁道有16 個扇區(qū)。若以扇區(qū)為分配單位，現(xiàn)問：答:( 1 ）用位示圖管理磁盤空間，則位示圖占用多少空間？( 2 ) 若空白文件目錄的每個目錄項占5 個字節(jié)，則什么時候空白文件目錄大于位示圖？

( 1 ）磁盤扇區(qū)總數(shù)為：10* 16* 100 = 16000 個，故位示圖占用16000 / 8 = 2000 字節(jié)。( 2 ）己知空白文件目錄的每個目錄項占5 個字節(jié)，而位示圖占用2000 字節(jié)，也就是說2000 字節(jié)可容納400 個文件目錄項。當空白文件目錄＞400 時，空白文件目錄大于位示圖。

15.某磁盤共有100 個柱面，每個柱面有8 個磁頭，每個盤面分4 個扇區(qū)。若邏輯記錄與扇區(qū)等長，柱面、磁道、扇區(qū)均從。起編號?，F(xiàn)用16 位的200 個字（0-199 ）來組成位示圖來管理盤空間。現(xiàn)問：( 1 ）位示圖第15 個字的第7 位為。而準備分配給某一記錄，該塊的柱面號、磁道號、扇區(qū)號是多少？( 2 ）現(xiàn)回收第56 柱面第6 磁道第3 扇區(qū)，這時位示圖的第幾個字的第幾位應(yīng)清0

( 1 ）位示圖第15 個字的第7 位對應(yīng)的塊號＝15 * 16 （字長）+ 7 = 247 ，而塊號247 對應(yīng)的：柱面號＝= 247 / ( 8 *4 )7 （從。編號，向下取整）
磁頭號＝( 247 MOD 32 ) / 4 == 5 
扇區(qū)號＝= 2 47 MOD 32 MOD =3 
( 2 ）塊號＝柱面號x 柱面扇區(qū)數(shù)＋磁道號x 盤扇區(qū)＋盤扇區(qū)＝5 6* ( 8 *4+6 *4 + 3= 1819 
字號＝ 1819 /16=113 
位號＝= 1819 MOD 16 = = 11 
所以，回收第56 柱面第6 磁道第3 扇區(qū)時，位示圖的第113 字的第n 位應(yīng)清0

16.如果一個索引節(jié)點為128B ，指針長4B ，狀態(tài)信息占用68B ，而每塊大小為8KB 。問在索引節(jié)點中有多大空間給指針？使用直接、一次間接、二次間接和三次間接指針分別可表示多大的文件？

答：由于索引節(jié)點為128B ，而狀態(tài)信息占用68B ，故索引節(jié)點中用于磁盤指針的空間大小為：128-68 = 60 字節(jié)。
一次間接、二次間接和三次間接指針占用三個指針項，因而直接指針項數(shù)為：60 / 4 -3 = 12 個。每塊大小為8KB ．所以，直接指針時：12 *8192 = 98304B 。
一次間接指針時：8192 / 4 = 2 048 ，即一個磁盤塊可裝2048 個盤塊指針，2048*8192 = 16MB 。二次間接指針時：2048 * 2048 = 4M ，即二次間接可裝4M 個盤塊指針，4M* 8192 = 32GB 。三次間接指針時：2048 x 2048 *2048 = 8G ，即三次間接可裝8G 個盤塊指針,8G* 8 192 = 16TB 。

17 ．設(shè)一個文件由100 個物理塊組成，對于連續(xù)文件、連接文件和索引文件，分別計算執(zhí)行下列操作時的啟動磁盤I/O 次數(shù)（假如頭指針和索引表均在內(nèi)存中）: ( l ）把一塊加在文件的開頭；( 2 ）把一塊加在文件的中間（第51 塊）; ( 3 ）把一塊加在文件的末尾；( 4 ）從文件的開頭刪去一塊；( 5 ）從文件的中間（第51 塊）刪去一塊；( 6 ）從文件的未尾刪去一塊。

答:
操作名稱 連續(xù)文件 鏈接文件 索引文件
加一塊到文件開頭 201 1 1
加一塊到文件中間 101 51 1
加一塊到文件末尾 1 2 1
從文件頭刪去一塊 0 1 1
刪去文件中間塊 98 52 1
從文件尾刪去一塊 0 100 1

第七章 操作系統(tǒng)安全與保護

1.有三種不同的保護機制：存取控制表、權(quán)能表和UNIX/Linux 的～位。下面的各種問題分別適用于哪些機制？( l ）形RICK 希望除Jenfer以外，任何人都能讀取他的文件．( 2 ) H elen 和Anna希望共享某些秘密文件．( 3 ) Cathy 希望公開她的一些文件．對于UNIX /Linux 假設(shè)用戶被分為：教職工、學生、秘書等。

答：( 1 ）可采用存取控制表ACL (2)可采用存取控制表ACL或權(quán)能表（3 ）可采用存取控制表ACL或rwx 形式。

2.考察下面的保護機制：給每個對象和進程賦予一個號碼，規(guī)定僅當對象號大于進程號時，進程才可以存取對象，這種保護機制有什么特點？

答：這種保護機制的特點是：進程沒有權(quán)力使用內(nèi)層的對象，而只能使用外層的對象，對不同進程可賦予不同權(quán)力，起到保護系統(tǒng)資源，限制進程的權(quán)限的作用。

3.如果從26 個英文字母表中選4 個字符形成一個口令，一個攻擊者的每秒鐘一個的速度試探口令，直到試探結(jié)束再反饋給攻擊者，那么，找到正確口令的時間是多少？

答：n ! / ( n –K)！= 26 ! / ( 26 -4）! = 26 *25 *24 * 23 = = 5980秒。

4.考慮一個有5000 個用戶的系統(tǒng)，假如只允許這些用戶中的4990個用戶能存取一個文件?，F(xiàn)問：( 1 ）如何實現(xiàn)？( 2 ）給出更有效的另一種保護方案。

答：( l ）建立一個包含4990 個用戶名的存取控制表，或者把這4990 個用戶合為一組，再對該組設(shè)相應(yīng)存取權(quán)限。
( 2 ）可把余下10 個用戶名放入該存取控制表但不給任何存取權(quán)。

第八章 操作系統(tǒng)技術(shù)新進展

1.在一個分布式系統(tǒng)中，如果P ：的邏輯時鐘在它向P ：發(fā)送消息時為10 ，進程P ：收到來自P ，的消息時邏輯時鐘為8 ，下一個局部事件幾的邏輯時鐘為多少？如果接收時P ：的邏輯時鐘為16 ，下一個局部事件P：的邏輯時鐘為多少？

答:11 17

2.在圖8 -8 (b）中，加入一條與消息A 并發(fā)的新消息，而且它不發(fā)生在A 之前，也不發(fā)生在A 之后。

新消息f ，它不發(fā)生在A 之前，也不發(fā)生在A 之后．

答:新消息f,它不發(fā)生在A 之前,也不發(fā)生在A 之后.

3.由于在網(wǎng)絡(luò)中可以通過不同路由發(fā)送消息，因而，可能出現(xiàn)后發(fā)送的消息先到達的亂序情況（如圖）．試設(shè)計一種邏輯時鐘算法對消息進行排序。

答：PZ 接收來自同一進程的消息，而發(fā)生亂序。在P1 發(fā)出的消息中除了給出邏輯時鐘外，還給出所發(fā)消息序號．當接收方收到一個亂序消息時，它將一直等待直到該消息前的所有消息到達為止。例如，若P2收到了Pl 發(fā)給它的2 號消息，那么，它會等待1 號消息到達.

4 .試設(shè)計一種邏輯時鐘算法對來自不同進程的亂序消息（如圖）進行排序。

答：當來自不同進程的因果關(guān)聯(lián)的消息到達接收方亂序時，情況變得更為復(fù)雜。圖中，對于P3 來說，來自Pl 的消息1 比來自P2 的消息2 先發(fā)出，但晚到達。設(shè)計一種邏輯時鐘算法需要有全局性的進展知識，用LC2[1] 〕 代表P2 對于P1 的進展知識。由于LC2 [ l ］在消息2 中捎帶給進程P3 ，所以當P3 收到來自進程P2 的消息2 時，它知道P1 的情況。P3 在接受P2 的消息2 之前將將會等待來自P1 的消息1 ，如果發(fā)生亂序，P3 先收到P2的消息2 后會等待直到Pl 的消息1 到達。