計(jì)算機(jī)操作系統(tǒng) 課后答案(劉循 朱敏 文藝 著) 人民郵電出版社.pdf

練習(xí)答案 練習(xí) 1 1.1-1.10 題解見(jiàn)書(shū) 1.11有一臺(tái)輸入設(shè)備和一臺(tái)輸出設(shè)備的計(jì)算機(jī)系統(tǒng)上，運(yùn)行有兩道程序。兩道 程序投入運(yùn)行情況如下： 程序 1 先開(kāi)始運(yùn)行，其運(yùn)行軌跡為：計(jì)算 50ms、輸出 100ms、計(jì)算 50ms、 輸出 100ms，結(jié)束； 程序 2 后開(kāi)始運(yùn)行，其運(yùn)行軌跡為：計(jì)算 50ms、輸入 100ms、計(jì)算 100ms、 結(jié)束。 1. 忽略調(diào)度時(shí)間， 指出兩道程序運(yùn)行時(shí)， cpu 是否有空閑？在哪部分空閑？ 2. 有無(wú)等待 cpu 的情況？如果有，發(fā)生在哪部分？ 題解: 由題畫(huà)出 cpu 利用圖如下： 由圖可知，1.cpu 有空閑，在 100ms150ms 時(shí)間段是空閑的。 2.程序 1 無(wú)等待時(shí)間， 而程序 2 在一開(kāi)始的 0ms50ms 時(shí)間段會(huì)等待。 1.12在計(jì)算機(jī)系統(tǒng)上運(yùn)行三道程序，運(yùn)行次序?yàn)槌绦?1、程序 2、程序 3。 程序 1 的運(yùn)行軌跡為：計(jì)算 20ms、輸入 40ms、計(jì)算 10ms。 程序 2 的運(yùn)行軌跡為：計(jì)算 40ms、輸入 30ms、計(jì)算 10ms。 程序 3 的運(yùn)行軌跡為：計(jì)算 60ms、輸入 30ms、計(jì)算 20ms。 忽略調(diào)度時(shí)間，畫(huà)出三道程序運(yùn)行的時(shí)間關(guān)系圖；完成三道程序共花多少時(shí)間？ 與單道程序比較，節(jié)省了多少時(shí)間？ 解答：三道程序運(yùn)行，完成三道程序共花 170ms。與單道程序（260ms）比較， 節(jié)省了 90ms。 （始終按照 1-2-3 的次序，即程序 1程序 2程序 3程序 1程序 2（在程 序 3 運(yùn)行前會(huì)停 10ms 等待輸入完成）程序 3。 （如果不是按照程序 1、2、3 的次序完成則會(huì)有多種情況。 ） 1.13在計(jì)算機(jī)系統(tǒng)上有兩臺(tái)輸入/輸出設(shè)備，運(yùn)行兩道程序。 程序 1 的運(yùn)行軌跡為： 計(jì)算 10ms、 輸入5ms、 計(jì)算5ms、 輸出10ms、 計(jì)算10ms。 程序 2 的運(yùn)行軌跡為： 輸入 10ms、 計(jì)算10ms、 輸出5ms、 計(jì)算5ms、 輸出10ms。 在順序環(huán)境下，先執(zhí)行程序 1，再執(zhí)行程序 2，求總的 cpu 利用率為多少？ 題解：由題畫(huà)出 cpu 利用圖如下： 由圖可知，在總共 80ms 的時(shí)間里，cpu 空閑時(shí)間為 40ms，即： cpu 利用率=40ms/80ms*100%=50% 1.14一個(gè)計(jì)算機(jī)系統(tǒng)有足夠的內(nèi)存空間存放 3 道程序， 這些程序有一半的時(shí)間 在空閑等待 i/o 操作。問(wèn)多大比例的 cpu 時(shí)間被浪費(fèi)掉了。 題解：由題畫(huà)圖如下： 因?yàn)槊總€(gè)程序有一半的時(shí)間在等待 i/o 操作，所以在并發(fā)狀態(tài)下，程序 1、程序 2、程序 3 所占時(shí)間比依次減半（如上圖） ，所以浪費(fèi)的時(shí)間比例為 1/8。 練習(xí) 2 2.1-2.17 題解見(jiàn)書(shū) 218 某系統(tǒng)中進(jìn)程狀態(tài)變化如圖 2.22 所示，當(dāng)對(duì)系統(tǒng)中的進(jìn)程進(jìn)行觀察時(shí)， 發(fā)現(xiàn)某一進(jìn)程產(chǎn)生的一次狀態(tài)變化會(huì)引起另一進(jìn)程發(fā)生狀態(tài)變化。 （1） 在什么情況下， 一個(gè)進(jìn)程的狀態(tài)變化 3 能夠立即引起另一進(jìn)程的狀態(tài)變化1？ （2） 在什么情況下， 一個(gè)進(jìn)程的狀態(tài)變化 2 能夠立即引起另一進(jìn)程的狀態(tài)變化1？ （3）進(jìn)程的狀態(tài)變化 3 是否可能引起另一進(jìn)程的狀態(tài)變化 2？進(jìn)程的狀態(tài)變化 3 是否可能引起另一進(jìn)程的狀態(tài)變化 1？ 解答： （1）當(dāng)就緒隊(duì)列中還存在其它進(jìn)程的情況下，一個(gè)進(jìn)程的狀態(tài)變化 3 能夠立即 引起另一進(jìn)程的狀態(tài)變化 2。 （2）當(dāng)就緒隊(duì)列中還存在其它進(jìn)程的情況下，一個(gè)進(jìn)程從運(yùn)行狀態(tài)變化到就緒 狀態(tài)后，另一個(gè)就緒進(jìn)程能夠從就緒狀態(tài)變?yōu)檫\(yùn)行狀態(tài)。 （3）不可能，可能。 219 分別寫(xiě)出相應(yīng)的程序來(lái)描述圖 2.23 中的前趨圖。 解答 s1 s2 s3 s4 s5 s6 s7 程序：s1:a:=x+1 s2:b:=a+2 s3:c:=a+3 s4:d:=b+4 s5:e:=b+c s6:f:=e+5 s7:g=e+6 s1 s2 s3 s4 s5 s6 s7 程序：s1:a:=x+1 s2:b:=a+2 s3:c:=a+3 s4:d:=b+4 s5:e:=b+c s6:f:=d+e s7:g:=c+e 2.20假設(shè)在一個(gè)系統(tǒng)中，新進(jìn)程以每分鐘 8 個(gè)進(jìn)程的速率到達(dá)，每個(gè)進(jìn)程請(qǐng) 求服務(wù)的平均時(shí)間為 6s，估計(jì)在一個(gè)單處理器系統(tǒng)中 cpu 忙的時(shí)間比率。 如果新進(jìn)程以每分鐘 10 個(gè)進(jìn)程的速率到達(dá)，每個(gè)進(jìn)程請(qǐng)求服務(wù)的平均時(shí)間 也為 6s，估計(jì)在一個(gè)單處理器系統(tǒng)中 cpu 忙的時(shí)間比率。 如果新進(jìn)程創(chuàng)建以每分鐘超過(guò) 10 個(gè)進(jìn)程的速率到達(dá)， 每個(gè)進(jìn)程請(qǐng)求服務(wù)的 平均時(shí)間為 6s，估計(jì)在一個(gè)單處理器系統(tǒng)中 cpu 忙得時(shí)間比率，并解釋此時(shí)的 情況。 解答： 因?yàn)樾逻M(jìn)程每分鐘 8 個(gè)進(jìn)程的速率到達(dá)，每個(gè)進(jìn)程之間達(dá)到的時(shí)間間隔為 7.5s。由于每個(gè)進(jìn)程占用 6s 的 cpu 時(shí)間。所以，1 分鐘之內(nèi) cpu 的空間時(shí)間為 8*1.5s=12s。cpu 的利用率為 48/60=0.8，即 80%。 因?yàn)樾逻M(jìn)程每分鐘 10 個(gè)進(jìn)程的速率到達(dá)，每個(gè)進(jìn)程之間達(dá)到的時(shí)間間隔為 6s。由于每個(gè)進(jìn)程占用 6s 的 cpu 時(shí)間。所以，1 分鐘之內(nèi) cpu 的空間時(shí)間為 0s。 cpu 的利用率為 100%。 如果新進(jìn)程創(chuàng)建以每分鐘超過(guò) 10 個(gè)進(jìn)程的速率到達(dá)，每個(gè)進(jìn)程請(qǐng)求服務(wù)的 平均時(shí)間為 6s，則請(qǐng)求服務(wù)時(shí)間會(huì)大于 1 分鐘，cpu 一直會(huì)處于繁忙，所以 cpu 忙的時(shí)間比率同樣為 100%。 2.21一個(gè)系統(tǒng)中有 4 個(gè)進(jìn)程， 進(jìn)程 p1 要求 20s 后運(yùn)行， 經(jīng)過(guò) 40s 后再次運(yùn)行 ； 進(jìn)程 p2 要求 25s 后運(yùn)行；進(jìn)程 p3 要求 35s 后運(yùn)行，經(jīng)過(guò) 35s 后再次運(yùn)行；進(jìn)程 p4 要求 60s 后運(yùn)行。進(jìn)程在阻塞隊(duì)列等待被喚醒后運(yùn)行，試創(chuàng)建進(jìn)程的喚醒隊(duì) 列。 解答：進(jìn)程的喚醒隊(duì)列為 p1p2p3p4p1p3 注意：“經(jīng)過(guò) 40s 后再次運(yùn)行”表示第 1 次運(yùn)行完成后再過(guò) 40s。 2.22如果線程是在用戶(hù)空間線程庫(kù)中實(shí)現(xiàn)，解釋為什么當(dāng)進(jìn)程中的一個(gè)線程 阻塞時(shí)，進(jìn)程內(nèi)的所有其它線程都會(huì)阻塞？如果線程是在內(nèi)核空間中實(shí)現(xiàn),而進(jìn) 程內(nèi)的一個(gè)線程阻塞不會(huì)引起進(jìn)程內(nèi)的其他線程被阻塞，為什么？ 解答： 用戶(hù)級(jí)線程由用戶(hù)空間運(yùn)行的用戶(hù)級(jí)線程庫(kù)實(shí)現(xiàn)。 當(dāng)一個(gè)應(yīng)用程序提交給操 作系統(tǒng)后，操作系統(tǒng)首先為該應(yīng)用程序建立一個(gè)內(nèi)核管理進(jìn)程，然后用戶(hù)級(jí)線程 庫(kù)為該進(jìn)程創(chuàng)建一個(gè)或多個(gè)用戶(hù)級(jí)線程，但內(nèi)核并不知道用戶(hù)空間線程的活動(dòng)， 內(nèi)核只是以進(jìn)程為單位， 實(shí)現(xiàn)進(jìn)程狀態(tài)的轉(zhuǎn)換， 因此當(dāng)進(jìn)程中的一個(gè)線程阻塞時(shí) ， 進(jìn)程內(nèi)的所有其它線程都會(huì)阻塞。 如果線程是在內(nèi)核空間中實(shí)現(xiàn)的，這些內(nèi)核級(jí)線程都由內(nèi)核創(chuàng)建和控制管 理，內(nèi)核為整個(gè)進(jìn)程及進(jìn)程中的所有線程維護(hù)現(xiàn)場(chǎng)信息，內(nèi)核的調(diào)度是在線程的 基礎(chǔ)上進(jìn)行的，因而進(jìn)程的一個(gè)線程阻塞不會(huì)引起進(jìn)程內(nèi)的其他線程被阻塞。 練習(xí) 3 3.1-3.12 題解見(jiàn)書(shū) 3.13 證明作業(yè)調(diào)度算法中短作業(yè)優(yōu)先調(diào)度算法具有最小平均等待時(shí)間。 證明:假設(shè)在作業(yè)隊(duì)列中等待運(yùn)行的作業(yè)有 n 道,分別為 n0，n1，n2，nn-1， 它們的運(yùn)行時(shí)間分別為 t0，t1，tn-1，且滿足 t0t10 說(shuō)明任何一種作業(yè)調(diào)度順序的作業(yè)的平均等待時(shí)間都大于按照短作業(yè)優(yōu)先的作 業(yè)的平均等待時(shí)間。 3.14 假設(shè)在一個(gè)處理器上執(zhí)行 5 個(gè)作業(yè)，作業(yè)到達(dá)的次序和需要執(zhí)行的時(shí)間分 別為：j0（75ms） 、j1（15ms） 、j2（5ms） 、j3（15ms） 、j4（45ms） ， 假定系統(tǒng)中使用 fcfs 調(diào)度算法，作業(yè) j3 的周轉(zhuǎn)時(shí)間是多少？作業(yè)的平均等 待時(shí)間是多少？ 答： 3.15 在單道批處理系統(tǒng)中，三個(gè)作業(yè)的提交時(shí)間分別為：10：00、10：10、10： 20，需要執(zhí)行時(shí)間分別為：2 小時(shí)、1 小時(shí)、0.5 小時(shí)，分別按照短作業(yè)優(yōu)先調(diào) 度算法和高響應(yīng)比優(yōu)先調(diào)度算法進(jìn)行調(diào)度，比較哪一種調(diào)度算法更好？ 解： (1) 不搶占： 執(zhí)行順序?yàn)?a，c，b 平均周轉(zhuǎn)時(shí)間： （120+130+200）/3=150（min） 平均帶勸周轉(zhuǎn)時(shí)間： （120/120+130/30+200/60）/3 =26/9 搶占： a（10：10） ，b（10：20） ，c(10:50),b(11:40),a(13:30) 平均周轉(zhuǎn)時(shí)間： （210+90+30）/3=110（min） 平均帶勸周轉(zhuǎn)時(shí)間： （210/120+90/60+30/30）/3 =510/360=17/12 (2) 響應(yīng)比高者優(yōu)先調(diào)度算法不會(huì)搶占，因此，只存在這樣一種情況： 執(zhí)行順序?yàn)?a，c，b 平均周轉(zhuǎn)時(shí)間： （120+130+200）/3=150（min） 平均帶勸周轉(zhuǎn)時(shí)間： （120/120+130/30+200/60）/3 =26/9 所以，如果要比較哪一種算法好自然針對(duì)不搶占的情況。根據(jù)比較結(jié)果， 它們的平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)相同， 這主要是該應(yīng)用正好發(fā)生了這樣湊巧 周轉(zhuǎn)時(shí)間(ms)等待時(shí)間（ms） j0750 j19075 j29590 j311095 j4155110 平均等待時(shí)間（ms）74 的情況。 3.16 假設(shè)在具有一個(gè)處理器的系統(tǒng)上執(zhí)行下面的作業(yè)，假如采用搶占式短作業(yè) 優(yōu)先調(diào)度算法，作業(yè)需要處理時(shí)間 t 和到達(dá)時(shí)間 a 分別如下：那么： 作業(yè) 1 的周轉(zhuǎn)時(shí)間是多少？作業(yè)的平均等待時(shí)間是多少？ 答： 1。執(zhí)行順序?yàn)椋?（10） ，2（30） ，1（65） ，3（90） ，0（130） ，4（170） 作業(yè) 0 的周轉(zhuǎn)時(shí)間為：130， 作業(yè) 1 的周轉(zhuǎn)時(shí)間為：55，作業(yè) 1 的周轉(zhuǎn)時(shí)間為：55， 作業(yè) 2 的周轉(zhuǎn)時(shí)間為：20， 作業(yè) 3 的周轉(zhuǎn)時(shí)間為：35 作業(yè) 4 的周轉(zhuǎn)時(shí)間為：65 平均周轉(zhuǎn)時(shí)間=305/5=61 作業(yè) 0 的等待時(shí)間為：130-50=80， 作業(yè) 1 的等待時(shí)間為：55-35=20， 作業(yè) 2 的等待時(shí)間為：10-10=0， 作業(yè) 3的等待時(shí)間為： ，35-25=10 作業(yè) 4的等待時(shí)間為： ，65-40=25 3.17 假如在具有一個(gè)處理器系統(tǒng)中，采用優(yōu)先級(jí)高者優(yōu)先的進(jìn)程調(diào)度算法，優(yōu) 先數(shù)小代表優(yōu)先級(jí)高，進(jìn)程達(dá)到順序 i 和需要處理時(shí)間 t、優(yōu)先數(shù)分別如下： （1）沒(méi)有優(yōu)先級(jí)搶占情況下，寫(xiě)出進(jìn)程的執(zhí)行先后序列，進(jìn)程 2 的周轉(zhuǎn)時(shí)間是 多少？進(jìn)程的平均等待時(shí)間是多少？ （3）有優(yōu)先級(jí)搶占情況下，寫(xiě)出進(jìn)程的執(zhí)行先后序列，進(jìn)程 2 的周轉(zhuǎn)時(shí)間是多 少？進(jìn)程的平均等待時(shí)間是多少？ 答： （1）無(wú)搶占： 執(zhí)行順序?yàn)椋?（15） ，4（60） ，0（135） ，2（140） ，3（155） 進(jìn)程 0 的周轉(zhuǎn)時(shí)間為：135 it到達(dá)時(shí)間 a 0500 13510 22010 32555 44095 it優(yōu)先級(jí) 0753 1151 254 3155 4452 進(jìn)程 1 的周轉(zhuǎn)時(shí)間為：15 進(jìn)程 2 的周轉(zhuǎn)時(shí)間為：140進(jìn)程 2 的周轉(zhuǎn)時(shí)間為：140 進(jìn)程 3 的周轉(zhuǎn)時(shí)間為：155 進(jìn)程 4 的周轉(zhuǎn)時(shí)間為：60 進(jìn)程的平均等待時(shí)間=（ （135-75）+（15-15）+（140-5）+（155-15）+（60-45） /5 = 70 （2）有搶占： 優(yōu)先級(jí)搶占同上一樣。 318 假如在具有一個(gè)處理器的系統(tǒng)中，采用時(shí)間片輪轉(zhuǎn)調(diào)度算法，時(shí)間片大小 為 10。進(jìn)程需要處理時(shí)間 t 和到達(dá)時(shí)間 a 分別如下： 寫(xiě)出進(jìn)程的執(zhí)行序列，進(jìn)程 3 的周轉(zhuǎn)時(shí)間是多少？進(jìn)程的平均等待時(shí)間是多 少？ 答： 進(jìn)程的執(zhí)行序列為：0，1，2，0，1，2，0，1，3，4，0，1，3，4，0，4 進(jìn)程 0 的周轉(zhuǎn)時(shí)間t0= 140 進(jìn)程 1 的周轉(zhuǎn)時(shí)間t1= 105 進(jìn)程 2 的周轉(zhuǎn)時(shí)間t1= 50 進(jìn)程 3 的周轉(zhuǎn)時(shí)間t1= 40進(jìn)程 3 的周轉(zhuǎn)時(shí)間t1= 40 進(jìn)程 4 的周轉(zhuǎn)時(shí)間t1= 75 進(jìn)程的平均等待時(shí)間為： （ （140-50）+（105-35）+（50-20）+（40-15）+（75-40） /5=50 3.19 在時(shí)間片輪轉(zhuǎn)調(diào)度算法中，有 n 個(gè)進(jìn)程共享 cpu。 （1）如果進(jìn)程切換的時(shí)間不可忽略，每次進(jìn)程切換用去時(shí)間為 s 秒，在保 證每個(gè)進(jìn)程至少每 t 秒內(nèi)能夠在 cpu 上輪回一次的前提下，確定時(shí)間片大小 q 使得進(jìn)程切換所造成的負(fù)載最小。 (2) 如果 n=100，t=1，s=0.001，那么 q 的大小應(yīng)該是多少？ 答： （1）時(shí)間片大小 q =（t-ns）/n （2）q=（1-100*0.001）/100 = 0.009 3.20 有一個(gè)四道作業(yè)的操作系統(tǒng)，若在一段時(shí)間內(nèi)先后到達(dá) 6 個(gè)作業(yè)，它們的 提交時(shí)間和估計(jì)運(yùn)行時(shí)間由下表給出： 作業(yè)提交時(shí)間估計(jì)運(yùn)行時(shí)間（分鐘） it到達(dá)時(shí)間 a 0500 13510 22010 31580 44085 18：0060 28：2035 38：2520 48：3025 58：355 68：4010 系統(tǒng)采用短作業(yè)優(yōu)先調(diào)度算法，作業(yè)被調(diào)度進(jìn)入系統(tǒng)后中途不得退出。但作 業(yè)運(yùn)行時(shí)可被更短的作業(yè)搶占。分別給出 6 個(gè)作業(yè)的執(zhí)行時(shí)間序列，作業(yè)的 周轉(zhuǎn)時(shí)間， 平均周轉(zhuǎn)時(shí)間。 答： 作業(yè)的執(zhí)行順序?yàn)椋?（8：20） ，2（8：25） ，3（8：45） ，5（8：50） ，6 （9：00） ，4（9：25） ，2（9：55） ，1（10：35） 作業(yè) 1 的周轉(zhuǎn)時(shí)間 = 155 min 作業(yè) 2 的周轉(zhuǎn)時(shí)間 = 95 min 作業(yè) 3 的周轉(zhuǎn)時(shí)間 = 20 min 作業(yè) 4 的周轉(zhuǎn)時(shí)間 = 55 min 作業(yè) 5 的周轉(zhuǎn)時(shí)間 = 15 min 作業(yè) 6 的周轉(zhuǎn)時(shí)間 = 20 min 作業(yè)的平均周轉(zhuǎn)時(shí)間為：360/6=60作業(yè)的平均周轉(zhuǎn)時(shí)間為：360/6=60 3.21 在一個(gè)實(shí)時(shí)系統(tǒng)中有 4 個(gè)周期性事件，周期分別為 50、100、150、200ms。 假設(shè)其處理時(shí)間分別需要 30、25、20 和 xms，則該系統(tǒng)可調(diào)度允許的 x 值最大 為多少？ 解: 30/50 + 25/100 +20/150+x/200 =1 x = 10/3 3.22 某系統(tǒng)的進(jìn)程狀態(tài)變化如圖 3.23 所示，該系統(tǒng)的進(jìn)程調(diào)度為非搶占方式， 根據(jù)該狀態(tài)圖敘述系統(tǒng)的調(diào)度策略、調(diào)度效果。 圖 3.23 狀態(tài)變化圖 阻塞 運(yùn)行低優(yōu)先級(jí)就緒 首先選擇 100ms 高優(yōu)先級(jí)就緒 其次選擇 100ms 答：首先采用優(yōu)先權(quán)高者優(yōu)先調(diào)度算法，然后采用時(shí)間片為 100ms的調(diào)度算法。 該調(diào)度算法如果調(diào)度效果考慮更周到的話， 應(yīng)該讓阻塞隊(duì)列上的進(jìn)程喚醒后 進(jìn)入低優(yōu)先級(jí)就緒隊(duì)列，這樣能夠保證優(yōu)先級(jí)高的進(jìn)程及時(shí)調(diào)度，優(yōu)先級(jí)低的進(jìn) 程能夠合理的得到調(diào)度。 第 4 章 4.1-4.12 題解見(jiàn)書(shū) 4.13如果有n個(gè)進(jìn)程共享一個(gè)互斥段 （1）如果每次只允許一個(gè)進(jìn)程進(jìn)入互斥段。 （2）如果每次最多允許m個(gè)進(jìn)程同時(shí)進(jìn)入互斥段（m10) （2）v(s);（5）x- - ; （3）y=x- 2;（6）else p(s); x- -; 分別說(shuō)明（1）、（2）、（3）、（4）、（5）、（6）語(yǔ)句之后的 x、y 值為多少？ 答： （1）x=11,y=2(2) x=11,y=2(3) x=11,y=9 (4)x=11,y=9(5) x=10,y=9(6) x=10,y=8 4.18三個(gè)進(jìn)程：輸入、計(jì)算、輸出。它們通過(guò)兩個(gè)緩沖區(qū)傳遞數(shù)據(jù)，如圖 4.11 所示。 每個(gè)緩沖區(qū)一次只能放入一條數(shù)據(jù)。寫(xiě)出用信號(hào)量進(jìn)行同步。 解：var empty1,full1,empty2,full2:semaphore:=1,0,1,0; begin parbegin i:begin repeat wait(empty1); put to buffer1; signal(full1); until false; end; p:begin repeat wait(full1); get from buffer1; signal(empty1); wait(empty2); put to buffer2; signal(full2); until false; end; o:begin repeat wait(full2) get from buffer2; signal(empty2); until false; end; parend; end; 練習(xí) 5 5.1 什么是死鎖？引起死鎖的原因和必要條件是什么？ 死鎖是指多個(gè)進(jìn)程因?yàn)楦?jìng)爭(zhēng)資源造成的一種僵局。 原因：并發(fā)進(jìn)程對(duì)臨界資源的競(jìng)爭(zhēng)和并發(fā)進(jìn)程推進(jìn)順序不當(dāng)。 必要條件：互斥條件，占有并請(qǐng)求條件，不剝奪條件，環(huán)路等待條件。 5.2 比較解決死鎖的方法中， 那種方法最容易實(shí)現(xiàn)？那種方法使得資源的利用率 最高？ 解決死鎖的方法：預(yù)防死鎖，避免死鎖，檢測(cè)死鎖，解除死鎖。 預(yù)防死鎖是通過(guò)設(shè)計(jì)協(xié)同資源管理程序，在進(jìn)程運(yùn)行期間，柏懷死鎖產(chǎn)生 的四個(gè)條件之中的任何一個(gè)，是指不成立。是最容易實(shí)現(xiàn)的方法。 解除死鎖是在發(fā)現(xiàn)死鎖后，解除死鎖，釋放資源。是資源利用率最高的方 法。 5.3 預(yù)防死鎖的方法有哪些？ 破壞互斥條件，破壞占有并請(qǐng)求，阻止環(huán)路等待，允許剝奪 5.4-5.7 題解見(jiàn)書(shū) 5.8 系統(tǒng)中有 3 個(gè)進(jìn)程共享 4 個(gè)資源，每個(gè)進(jìn)程每次只能申請(qǐng)或釋放一個(gè)資源， 每個(gè)進(jìn)程最多需要 2 個(gè)資源，給進(jìn)程是否會(huì)發(fā)生死鎖，為什么？ 解: 不會(huì)發(fā)生死鎖。3 個(gè)進(jìn)程共享 4 個(gè)資源，每個(gè)進(jìn)程最多需要 2 個(gè)資源。 總有一 個(gè)進(jìn)程的請(qǐng)求會(huì)滿足，運(yùn)行并釋放資源。不會(huì)形成環(huán)路等待。 5.9 系統(tǒng)中有 20 個(gè)進(jìn)程，每個(gè)進(jìn)程最多使用 3 個(gè)資源，每個(gè)進(jìn)程逐個(gè)申請(qǐng)并競(jìng) 爭(zhēng)使用 60 個(gè)同類(lèi)資源。一旦某進(jìn)程獲得所需要的資源，完成后立即釋放全部資 源。系統(tǒng)是否會(huì)發(fā)生死鎖？為什么？ 系統(tǒng)不會(huì)發(fā)生死鎖。以最壞的情況來(lái)考慮，20 個(gè)進(jìn)程都需要使用 3 個(gè)資 源。 當(dāng)前， 每個(gè)進(jìn)程都持有2個(gè) 資 源 。（20*2=40）.都在申請(qǐng)第 3個(gè)資源 （60-40=20） 對(duì)于剩余的 20 個(gè)資源，每個(gè)進(jìn)程多會(huì)得到一個(gè)資源。不會(huì)形成環(huán)路等待。 5.10一臺(tái)計(jì)算機(jī)有 8 臺(tái)打印機(jī)，被n個(gè)進(jìn)程競(jìng)爭(zhēng)使用，每個(gè)進(jìn)程最多需 要 3 臺(tái)。 請(qǐng)問(wèn)n為多少時(shí)，系統(tǒng)沒(méi)有死鎖的危險(xiǎn)，說(shuō)明原因。 解: n=3 時(shí)，沒(méi)有死鎖的危險(xiǎn)。 對(duì)于 n 個(gè)進(jìn)程，都持有 2 臺(tái)打印機(jī)時(shí)，申請(qǐng)第 3 臺(tái)打印機(jī)，只要有一臺(tái) 的多余的打印機(jī)能被申請(qǐng)到，則系統(tǒng)就沒(méi)有死鎖的危險(xiǎn)。即 n*2+1=8，得 n=3。 5.11考慮圖 5.9 所示的資源分配圖，哪個(gè)進(jìn)程會(huì)發(fā)生死鎖？ 解答:考慮圖 5.9 所示的資源分配圖，哪個(gè)進(jìn)程會(huì)發(fā)生死鎖？ 進(jìn)程 p3,p4 會(huì)發(fā)生死鎖。 對(duì)于進(jìn)程 p1,p2，進(jìn)程的推進(jìn)不需要等待其他進(jìn)程的完成。 進(jìn)程 p3,p4。p3 要等 p4 完成并釋放資源后方能推進(jìn)。而 p4 要等到 p3 完成后才 能。結(jié)果是 p3,p4 都不能完成。形成死鎖。 5.12假定有 3 個(gè)人排隊(duì)等候上電梯。當(dāng)電梯門(mén)打開(kāi)的時(shí)候，3 個(gè)人都朝門(mén)口 沖去，但是門(mén)不夠大，他們 3 人不能同時(shí)進(jìn)門(mén)。描述解決這種死鎖的方法，可以 讓 3 個(gè)人都上電梯。說(shuō)明你的解決方案清除了哪個(gè)死鎖的必要條件。 解答: 讓 3 個(gè)人輪流進(jìn)電梯。 破壞了死鎖發(fā)生的 4 個(gè)必要條件中的“不剝奪條件”。 5.13假定一個(gè)系統(tǒng)具有四個(gè)系統(tǒng)類(lèi)型，c=3，7，2，3，最大資源需求數(shù)表 如圖 5.10 所示。資源分配器根據(jù)圖 5.11 中的表來(lái)分配資源，這個(gè)狀態(tài) 安全嗎？ 為什么？ 圖5.10圖5.11 解答: 這個(gè)狀態(tài)安全。存在安全執(zhí)行序列p4,p0,p1,p3,p2； 練習(xí) 6 6.1-6.8 題解見(jiàn)書(shū) 6.9如果一個(gè)分頁(yè)系統(tǒng)能夠向用戶(hù)提供的邏輯地址最大為 16 頁(yè)，頁(yè)面大 小為 2k，內(nèi)存總共有 8 個(gè)存儲(chǔ)塊。請(qǐng)問(wèn)邏輯地址應(yīng)該為多少位？?jī)?nèi) 存空間為多大？ 解：邏輯地址應(yīng)該為 4+11=15（位） 內(nèi)存空間為 8*2k =16k 6.10如果一個(gè)分頁(yè)系統(tǒng)的頁(yè)表存放在內(nèi)存。 （1）若對(duì)內(nèi)存的一次存取需要 1.2s，請(qǐng)問(wèn)一次頁(yè)面訪問(wèn)的存取需 要花多少時(shí)間？ （2）若系統(tǒng)配置了聯(lián)想寄存器，對(duì)快表的命中率為 70%，假如查詢(xún) 聯(lián)想寄存器的時(shí)間忽略不計(jì)，請(qǐng)問(wèn)實(shí)現(xiàn)一次頁(yè)面訪問(wèn)的存取 時(shí)間是多少？ 解： （1）訪問(wèn)一次頁(yè)面的存取需要花費(fèi)的時(shí)間為 2*1.2s=2.4s （2）實(shí)現(xiàn)一次頁(yè)面訪問(wèn)的存取時(shí)間=0.3*2.4s+0.7*1.2s=1.56s 6.11如果一個(gè)分頁(yè)系統(tǒng)邏輯地址長(zhǎng)度為 16 位，頁(yè)面大小為 4kb，第 0、1、2 頁(yè)對(duì)應(yīng) 10、12、14 號(hào)物理塊， 請(qǐng)問(wèn)邏輯地址為 2f6ah 對(duì)應(yīng)的物理地址為多少？ 解：邏輯地址為 2f6ah 對(duì)應(yīng)的二進(jìn)制碼為：0010 1111 0110 1010，頁(yè)號(hào)為：2， 頁(yè)內(nèi)偏移為 f6ah。 查詢(xún)頁(yè)表 2 號(hào)頁(yè)面對(duì)應(yīng) 12號(hào)塊， 所以， 物理地址為1100 1111 0110 1010， 最終物理地址為：cf6ah 6.12如果內(nèi)存中有 4 個(gè)空閑塊，每個(gè)空閑塊的大小為 10mb。有 10 個(gè)請(qǐng)求，每 次請(qǐng)求 1mb 的內(nèi)存大小， 對(duì)于下面列出的內(nèi)存分配方法中的每一種， 確定所有 10 個(gè)請(qǐng)求都被滿足之后剩余空閑塊的大小。 （a）首次適應(yīng)算法 （b）循環(huán)首次適應(yīng)算法 （c）最佳適應(yīng)算法 （d）最壞適應(yīng)算法 解： （a）首次適應(yīng)算法：塊 1 用完，塊 2，3，4 剩余 10mb。 （b）循環(huán)首次適應(yīng)算法：塊 1，2 余 7mb，塊 3.4 余 8mb。 （c）最佳適應(yīng)算法：塊 1 用完，塊 2，3，4 余 10mb。 （d）最壞適應(yīng)算法：塊 1，2 余 7mb，塊 3，4 余 8mb。 6.13如果一個(gè)系統(tǒng)的段表為： 求下列邏輯地址相應(yīng)的物理地址。如果越界請(qǐng)指明。 0,380、1,20、1,24、2,200、3,500、4,120。 解：0,380表示為 0 段，段內(nèi)偏移為 380，物理地址為 580； 1,20表示為 1 段，段內(nèi)偏移為 20，物理地址為 920； 1,24表示為 1 段，段內(nèi)偏移為 24，物理地址為 924； 2,200表示為 2 段，段內(nèi)偏移為 200，已經(jīng)越界； 3,500表示為 3 段，段內(nèi)偏移為 500，物理地址為 1700； 4,120表示為 4 段，段內(nèi)偏移為 120，已經(jīng)越界。 練習(xí) 7 7.1-7.4 題解見(jiàn)書(shū) 7.5在分頁(yè)虛擬存儲(chǔ)器管理中，如果已知時(shí)間利用率為：cpu20%、分頁(yè) 磁盤(pán) 92%、外設(shè) 50%，請(qǐng)問(wèn)采取哪些措施可以改善 cpu 的利用率？ 解：增大分頁(yè)磁盤(pán)空間。 7.6一個(gè) 32 位地址的計(jì)算機(jī)系統(tǒng)使用二級(jí)頁(yè)表，虛擬地址為 9 位頂級(jí)頁(yè) 表，11 位二級(jí)頁(yè)表和偏移。請(qǐng)問(wèn)：頁(yè)面長(zhǎng)度為多少？虛擬地址空間 有多少個(gè)頁(yè)面？ 解：頁(yè)面占用的位數(shù)=32-9-11=12 位，頁(yè)面長(zhǎng)度為 4k。虛擬地址空間有 1m 個(gè)頁(yè) 面。 7.7如果分頁(yè)虛擬存儲(chǔ)系統(tǒng)向用戶(hù)提供的邏輯地址空間最大為 16 頁(yè)，每 頁(yè) 2kb，內(nèi)存總共有 8 個(gè)存儲(chǔ)塊，請(qǐng)問(wèn)邏輯地址至少應(yīng)為多少位？?jī)?nèi) 存空間多大？ 解：解：邏輯地址應(yīng)該為 4+11=15（位） 內(nèi)存空間為 8*2k =16k 7.8在一個(gè)請(qǐng)求分頁(yè)的虛擬存儲(chǔ)器管理中，一個(gè)程序的運(yùn)行頁(yè)面走向?yàn)椋?1、2、3、4、2、3、5、6、3、1、4、6、7、5、2、4、1、3、2 段號(hào)始址段長(zhǎng) 0200510 190030 210080 31200500 4180080 如果為程序分配頁(yè)框?yàn)?3 個(gè)、4 個(gè)，請(qǐng)分別用 fifo、opt 和 lru 算法求 出缺頁(yè)中斷次數(shù)和缺頁(yè)率。 解：頁(yè)框?yàn)?3： fifo 缺頁(yè)中斷次數(shù)為 14；缺頁(yè)率為 14/19。 opt 缺頁(yè)中斷次數(shù)為 8；缺頁(yè)率為 8/19。 lru 缺頁(yè)中斷次數(shù)為 13；缺頁(yè)率為 13/19。 頁(yè)框?yàn)?4： fifo 缺頁(yè)中斷次數(shù)為 7；缺頁(yè)率為 7/19。 opt 缺頁(yè)中斷次數(shù)為 5；缺頁(yè)率為 5/19。 lru 缺頁(yè)中斷次數(shù)為 10；缺頁(yè)率為 10/19。 練習(xí) 8練習(xí) 8 8.1-8.8 題解見(jiàn)書(shū) 練習(xí) 9 9.1-9.8 題解見(jiàn)書(shū) 9.9若采用字長(zhǎng)為 16 位的位示圖管理磁盤(pán)空間， 某操作系統(tǒng)的磁盤(pán)文件空間共 有 500 塊，問(wèn)位示圖需要多少個(gè)字？第i列第j行對(duì)應(yīng)的塊號(hào)為多少？ 解答：500/16 取整為 32。 塊號(hào)=16*i+j 9.10一個(gè)鏈接文件由 5 個(gè)邏輯記錄組成， 每個(gè)邏輯記錄的大小與磁盤(pán)塊大小都 為 512 字節(jié)，一次存放在 25，70，98，83，60 號(hào)磁盤(pán)上。若要存取文件的第 1 769 邏輯字節(jié)處的信息，問(wèn)需要訪問(wèn)哪個(gè)磁盤(pán)塊？ 解答:1769 位于第 3 個(gè)邏輯記錄(從 0 開(kāi)始)。所以,需要訪問(wèn)第 83 號(hào)磁盤(pán)塊。 9.11在 unix 操作系統(tǒng)中，如果一個(gè)盤(pán)塊的大小為 1kb，每個(gè)盤(pán)塊號(hào)占用 4 個(gè) 字節(jié)，即每塊可放 256 個(gè)地址，如果進(jìn)程要訪問(wèn)偏移為 143140 處的數(shù) 據(jù)，問(wèn)需要幾次尋址？ 解答：unix 操作系統(tǒng)中前面 0-9 個(gè)塊為直接尋址，后面分別為 1 次間接尋址，2 次間接尋址，3 次間接尋址。 由于 1 個(gè)盤(pán)塊為 1kb 大小，可尋址范圍為 10kb，即 10*1024=10，240。顯 然，143140 已經(jīng)超過(guò)了直接尋址。 1 次間接尋址范圍為 256*1024=262144，所以，143140 就在 1 次間接尋 址中。 故需要通過(guò) 1 次間接尋址。 9.12從磁盤(pán)高速緩存讀取數(shù)據(jù)需要 1ms，從磁盤(pán)讀取數(shù)據(jù)需要 40ms，如果命中 率為 50%，計(jì)算出讀取數(shù)據(jù)的平均時(shí)間。 解答：1*