操作系統(tǒng)課后習題1-9答案.docVIP

練習11.1-1.10題解見書1.11 有一臺輸入設(shè)備和一臺輸出設(shè)備的計算機系統(tǒng)上，運行有兩道程序。兩道程序投入運行情況如下： 程序1先開始運行，其運行軌跡為：計算50ms、輸出100ms、計算50ms、輸出100ms，結(jié)束； 程序2后開始運行，其運行軌跡為：計算50ms、輸入100ms、計算100ms、結(jié)束。 1. 忽略調(diào)度時間，指出兩道程序運行時，CPU是否有空閑？在哪部分空閑？指出程序1和程序 2. 有無等待CPU的情況？如果有，發(fā)生在哪部分？題解:由題畫出CPU利用圖如下： 由圖可知，1.CPU有空閑，在100ms150ms時間段是空閑的。 2.程序1無等待時間，而程序2在一開始的0ms50ms時間段會等待。1.12 在計算機系統(tǒng)上運行三道程序，運行次序為程序1、程序2、程序3。程序1的運行軌跡為：計算20ms、輸入40ms、計算10ms。程序2的運行軌跡為：計算40ms、輸入30ms、計算10ms。程序3的運行軌跡為：計算60ms、輸入30ms、計算20ms。忽略調(diào)度時間，畫出三道程序運行的時間關(guān)系圖；完成三道程序共花多少時間？與單道程序比較，節(jié)省了多少時間？解答：三道程序運行，完成三道程序共花170ms。與單道程序（260ms）比較，節(jié)省了90ms。（始終按照1-2-3的次序，即程序1程序2程序3程序1程序2（在程序3運行前會停10ms等待輸入完成）程序3。（如果不是按照程序1、2、3的次序完成則會有多種情況。）1.13 在計算機系統(tǒng)上有兩臺輸入/輸出設(shè)備，運行兩道程序。 程序1的運行軌跡為：計算10ms、輸入5ms、計算5ms、輸出10ms、計算10ms。 程序2的運行軌跡為：輸入10ms、計算10ms、輸出5ms、計算5ms、輸出10ms。 在順序環(huán)境下，先執(zhí)行程序1，再執(zhí)行程序2，求總的CPU利用率為多少？題解：由題畫出CPU利用圖如下：由圖可知，在總共80ms的時間里，CPU空閑時間為40ms，即： CPU利用率=40ms/80ms*100%=50%1.14 一個計算機系統(tǒng)有足夠的內(nèi)存空間存放3道程序，這些程序有一半的時間在空閑等待I/O操作。問多大比例的CPU時間被浪費掉了。題解：由題畫圖如下：因為每個程序有一半的時間在等待I/O操作，所以在并發(fā)狀態(tài)下，程序1、程序2、程序3所占時間比依次減半（如上圖），所以浪費的時間比例為1/8。 練習2218 某系統(tǒng)中進程狀態(tài)變化如圖2.22所示，當對系統(tǒng)中的進程進行觀察時，發(fā)現(xiàn)某一進程產(chǎn)生的一次狀態(tài)變化會引起另一進程發(fā)生狀態(tài)變化。（1）在什么情況下，一個進程的狀態(tài)變化3能夠立即引起另一進程的狀態(tài)變化1？（2）在什么情況下，一個進程的狀態(tài)變化2能夠立即引起另一進程的狀態(tài)變化1？（3）進程的狀態(tài)變化3是否可能引起另一進程的狀態(tài)變化2？進程的狀態(tài)變化3是否可能引起另一進程的狀態(tài)變化1？解答：（1）當就緒隊列中還存在其它進程的情況下，一個進程的狀態(tài)變化3能夠立即引起另一進程的狀態(tài)變化2。（2）當就緒隊列中還存在其它進程的情況下，一個進程從運行狀態(tài)變化到就緒狀態(tài)后，另一個就緒進程能夠從就緒狀態(tài)變?yōu)檫\行狀態(tài)。（3）不可能，可能。219分別寫出相應的程序來描述圖2.23中的前趨圖。解答S1S2S3S4S5S6S7程序：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 S1S2S3S4S5S6S7程序：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+e2.20 假設(shè)在一個系統(tǒng)中，新進程以每分鐘8個進程的速率到達，每個進程請求服務(wù)的平均時間為6s，估計在一個單處理器系統(tǒng)中CPU忙的時間比率。 如果新進程以每分鐘10個進程的速率到達，每個進程請求服務(wù)的平均時間也為6s，估計在一個單處理器系統(tǒng)中CPU忙的時間比率。 如果新進程創(chuàng)建以每分鐘超過10個進程的速率到達，每個進程請求服務(wù)的平均時間為6s，估計在一個單處理器系統(tǒng)中CPU忙得時間比率，并解釋此時的情況。解答： 因為新進程每分鐘8個進程的速率到達，每個進程之間達到的時間間隔為7.5s。由于每個進程占用6s的CPU時間。所以，1分鐘之內(nèi)CPU的空間時間為8*1.5s=12s。CPU的利用率為48/60=0.8，即80%。 因為新進程每分鐘10個進程的速率到達，每個進程之間達到的時間間隔為6s。由于每個進程占用6s的CPU時間。所以，1分鐘之內(nèi)CPU的空間時間為0s。CPU的利用率為100%。 如果新進程創(chuàng)建以每分鐘超過10個進程的速率到達，每個進程請求服務(wù)的平均時間為6s，則請求服務(wù)時間會大于1分鐘，CPU一直會處于繁忙，所以 CPU忙的時間比率同樣為100%。2.21 一個系統(tǒng)中有4個進程，進程P1要求20s后運行，經(jīng)過40s后再次運行；進程P2要求25s后運行；進程P3要求35s后運行，經(jīng)過35s后再次運行；進程P4要求60s后運行。進程在阻塞隊列等待被喚醒后運行，試創(chuàng)建進程的喚醒隊列。解答：進程的喚醒隊列為P1P2P3P4P1P3注意：“經(jīng)過40s后再次運行”表示第1次運行完成后再過40s。2.22 如果線程是在用戶空間線程庫中實現(xiàn)，解釋為什么當進程中的一個線程阻塞時，進程內(nèi)的所有其它線程都會阻塞？如果線程是在內(nèi)核空間中實現(xiàn),而進程內(nèi)的一個線程阻塞不會引起進程內(nèi)的其他線程被阻塞，為什么？解答： 用戶級線程由用戶空間運行的用戶級線程庫實現(xiàn)。當一個應用程序提交給操作系統(tǒng)后，操作系統(tǒng)首先為該應用程序建立一個內(nèi)核管理進程，然后用戶級線程庫為該進程創(chuàng)建一個或多個用戶級線程，但內(nèi)核并不知道用戶空間線程的活動，內(nèi)核只是以進程為單位，實現(xiàn)進程狀態(tài)的轉(zhuǎn)換，因此當進程中的一個線程阻塞時，進程內(nèi)的所有其它線程都會阻塞。 如果線程是在內(nèi)核空間中實現(xiàn)的，這些內(nèi)核級線程都由內(nèi)核創(chuàng)建和控制管理，內(nèi)核為整個進程及進程中的所有線程維護現(xiàn)場信息，內(nèi)核的調(diào)度是在線程的基礎(chǔ)上進行的，因而進程的一個線程阻塞不會引起進程內(nèi)的其他線程被阻塞。練習33.13 證明作業(yè)調(diào)度算法中短作業(yè)優(yōu)先調(diào)度算法具有最小平均等待時間。證明:假設(shè)在作業(yè)隊列中等待運行的作業(yè)有N道,分別為N0，N1，N2，Nn-1，它們的運行時間分別為t0，t1，tn-1，且滿足t0t10說明任何一種作業(yè)調(diào)度順序的作業(yè)的平均等待時間都大于按照短作業(yè)優(yōu)先的作業(yè)的平均等待時間。3.14 假設(shè)在一個處理器上執(zhí)行5個作業(yè)，作業(yè)到達的次序和需要執(zhí)行的時間分別為：J0（75ms）、J1（15ms）、J2（5ms）、J3（15ms）、J4（45ms），假定系統(tǒng)中使用FCFS調(diào)度算法，作業(yè)J3的周轉(zhuǎn)時間是多少？作業(yè)的平均等待時間是多少？答：周轉(zhuǎn)時間(ms)等待時間（ms）J0750J19075J29590J311095J4155110平均等待時間（ms）743.15在單道批處理系統(tǒng)中，三個作業(yè)的提交時間分別為：10：00、10：10、10：20，需要執(zhí)行時間分別為：2小時、1小時、0.5小時，分別按照短作業(yè)優(yōu)先調(diào)度算法和高響應比優(yōu)先調(diào)度算法進行調(diào)度，比較哪一種調(diào)度算法更好？解：(1) 不搶占：執(zhí)行順序為A，C，B平均周轉(zhuǎn)時間：（120+130+200）/3=150（min）平均帶勸周轉(zhuǎn)時間：（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)時間：（210+90+30）/3=110（min）平均帶勸周轉(zhuǎn)時間：（210/120+90/60+30/30）/3 =510/360=17/12(2) 響應比高者優(yōu)先調(diào)度算法不會搶占，因此，只存在這樣一種情況：執(zhí)行順序為A，C，B平均周轉(zhuǎn)時間：（120+130+200）/3=150（min）平均帶勸周轉(zhuǎn)時間：（120/120+130/30+200/60）/3 =26/9 所以，如果要比較哪一種算法好自然針對不搶占的情況。根據(jù)比較結(jié)果，它們的平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)相同，這主要是該應用正好發(fā)生了這樣湊巧的情況。3.16假設(shè)在具有一個處理器的系統(tǒng)上執(zhí)行下面的作業(yè)，假如采用搶占式短作業(yè)優(yōu)先調(diào)度算法，作業(yè)需要處理時間T和到達時間A分別如下：那么：IT到達時間A050013510220103255544095作業(yè)1的周轉(zhuǎn)時間是多少？作業(yè)的平均等待時間是多少？答：1。執(zhí)行順序為：0（10），2（30），1（65），3（90），0（130），4（170）作業(yè)0的周轉(zhuǎn)時間為：130，作業(yè)1的周轉(zhuǎn)時間為：55，作業(yè)2的周轉(zhuǎn)時間為：20，作業(yè)3的周轉(zhuǎn)時間為：35作業(yè)4的周轉(zhuǎn)時間為：65平均周轉(zhuǎn)時間=305/5=61作業(yè)0的等待時間為：130-50=80，作業(yè)1的等待時間為：55-35=20，作業(yè)2的等待時間為：10-10=0，作業(yè)3的等待時間為：，35-25=10作業(yè)4的等待時間為：，65-40=253.17假如在具有一個處理器系統(tǒng)中，采用優(yōu)先級高者優(yōu)先的進程調(diào)度算法，優(yōu)先數(shù)小代表優(yōu)先級高，進程達到順序I和需要處理時間T、優(yōu)先數(shù)分別如下：IT優(yōu)先級0753115125431554452（1）沒有優(yōu)先級搶占情況下，寫出進程的執(zhí)行先后序列，進程2的周轉(zhuǎn)時間是多少？進程的平均等待時間是多少？（3）有優(yōu)先級搶占情況下，寫出進程的執(zhí)行先后序列，進程2的周轉(zhuǎn)時間是多少？進程的平均等待時間是多少？答：（1）無搶占：執(zhí)行順序為：1（15），4（60），0（135），2（140），3（155）進程0的周轉(zhuǎn)時間為：135進程1的周轉(zhuǎn)時間為：15進程2的周轉(zhuǎn)時間為：140進程3的周轉(zhuǎn)時間為：155進程4的周轉(zhuǎn)時間為：60進程的平均等待時間=（135-75）+（15-15）+（140-5）+（155-15）+（60-45）/5 = 70（2）有搶占：優(yōu)先級搶占同上一樣。3 18 假如在具有一個處理器的系統(tǒng)中，采用時間片輪轉(zhuǎn)調(diào)度算法，時間片大小為10。進程需要處理時間T和到達時間A分別如下：IT到達時間A050013510220103158044085寫出進程的執(zhí)行序列，進程3的周轉(zhuǎn)時間是多少？進程的平均等待時間是多少？答：進程的執(zhí)行序列為：0，1，2，0，1，2，0，1，3，4，0，1，3，4，0，4進程0的周轉(zhuǎn)時間 T0= 140進程1的周轉(zhuǎn)時間 T1= 105進程2的周轉(zhuǎn)時間 T1= 50進程3的周轉(zhuǎn)時間 T1= 40進程4的周轉(zhuǎn)時間 T1= 75 進程的平均等待時間為：（140-50）+（105-35）+（50-20）+（40-15）+（75-40）/5=503.18 在時間片輪轉(zhuǎn)調(diào)度算法中，有 n個進程共享CPU。（1）如果進程切換的時間不可忽略，每次進程切換用去時間為s秒，在保證每個進程至少每t秒內(nèi)能夠在CPU上輪回一次的前提下，確定時間片大小q使得進程切換所造成的負載最小。 (2) 如果n=100，t=1，s=0.001，那么q的大小應該是多少？答：（1）時間片大小q =（t-ns）/n （2）q=（1-100*0.001）/100 = 0.0093.19 有一個四道作業(yè)的操作系統(tǒng)，若在一段時間內(nèi)先后到達6個作業(yè)，它們的提交時間和估計運行時間由下表給出： 作業(yè) 提交時間 估計運行時間（分鐘） 1 8：00 60 2 8：20 353 8：25 204 8：30 255 8：35 56 8：40 10系統(tǒng)采用短作業(yè)優(yōu)先調(diào)度算法，作業(yè)被調(diào)度進入系統(tǒng)后中途不得退出。但作業(yè)運行時可被更短的作業(yè)搶占。分別給出6個作業(yè)的執(zhí)行時間序列，作業(yè)的周轉(zhuǎn)時間， 平均周轉(zhuǎn)時間。答：作業(yè)的執(zhí)行順序為：1（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)時間 = 155 min作業(yè)2的周轉(zhuǎn)時間 = 95 min作業(yè)3的周轉(zhuǎn)時間 = 20 min作業(yè)4的周轉(zhuǎn)時間 = 55 min作業(yè)5的周轉(zhuǎn)時間 = 15 min作業(yè)6的周轉(zhuǎn)時間 = 20 min作業(yè)的平均周轉(zhuǎn)時間為：360/6=603.20 在一個實時系統(tǒng)中有4個周期性事件，周期分別為50、100、150、200ms。假設(shè)其處理時間分別需要30、25、20和xms，則該系統(tǒng)可調(diào)度允許的x值最大為多少？解:30/50 + 25/100 +150/20 +200/x =1X = 10/33.21 某系統(tǒng)的進程狀態(tài)變化如圖3.23所示，該系統(tǒng)的進程調(diào)度為非搶占方式，根據(jù)該狀態(tài)圖敘述系統(tǒng)的調(diào)度策略、調(diào)度效果。圖3.23 狀態(tài)變化圖阻塞運行低優(yōu)先級就緒首先選擇100ms高優(yōu)先級就緒其次選擇100msy答：首先采用優(yōu)先權(quán)高者優(yōu)先調(diào)度算法，然后采用時間片為100ms的調(diào)度算法。 該調(diào)度算法如果調(diào)度效果考慮更周到的話，應該讓阻塞隊列上的進程喚醒后進入低優(yōu)先級就緒隊列，這樣能夠保證優(yōu)先級高的進程及時調(diào)度，優(yōu)先級低的進程能夠合理的得到調(diào)度。第4章4.13 如果有n個進程共享一個互斥段 （1）如果每次只允許一個進程進入互斥段。 （2）如果每次最多允許m個進程同時進入互斥段（m10) （2） V(s); （5） x;（3） y=x2; （6） else P(s); x ; 分別說明（1）、（2）、（3）、（4）、（5）、（6）語句之后的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=84.18 三個進程：輸入、計算、輸出。它們通過兩個緩沖區(qū)傳遞數(shù)據(jù)，如圖4.11所示。每個緩沖區(qū)一次只能放入一條數(shù)據(jù)。寫出用信號量進行同步。解：var empty1,full1,empty2,full2:semaphore:=1,0,1,0;begin parbeginI: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;第5章5.1什么是死鎖？引起死鎖的原因和必要條件是什么？ 死鎖是指多個進程因為競爭資源造成的一種僵局。 原因：并發(fā)進程對臨界資源的競爭和并發(fā)進程推進順序不當。 必要條件：互斥條件，占有并請求條件，不剝奪條件，環(huán)路等待條件。5.2 比較解決死鎖的方法中，那種方法最容易實現(xiàn)？那種方法使得資源的利用率最高？ 解決死鎖的方法：預防死鎖，避免死鎖，檢測死鎖，解除死鎖。 預防死鎖是通過設(shè)計協(xié)同資源管理程序，在進程運行期間，柏懷死鎖產(chǎn)生的四個條件之中的任何一個，是指不成立。 是最容易實現(xiàn)的方法。 解除死鎖是在發(fā)現(xiàn)死鎖后，解除死鎖，釋放資源。是資源利用率最高的方法。5.3預防死鎖的方法有哪些？ 破壞互斥條件，破壞占有并請求，阻止環(huán)路等待，允許剝奪5.8系統(tǒng)中有3個進程共享4個資源，每個進程每次只能申請或釋放一個資源，每個進程最多需要2個資源，給進程是否會發(fā)生死鎖，為什么？ 解:不會發(fā)生死鎖。3個進程共享4個資源，每個進程最多需要2個資源。 總有一個進程的請求會滿足，運行并釋放資源。不會形成環(huán)路等待。5.9系統(tǒng)中有20個進程，每個進程最多使用3個資源，每個進程逐個申請并競爭使用60個同類資源。一旦某進程獲得所需要的資源，完成后立即釋放全部資源。系統(tǒng)是否會發(fā)生死鎖？為什么？ 系統(tǒng)不會發(fā)生死鎖。以最壞的情況來考慮，20個進程都需要使用3個資源。當前，每個進程都持有2個資源。（20*2=40）.都在申請第3個資源（60-40=20）對于剩余的20個資源，每個進程多會得到一個資源。不會形成環(huán)路等待。5.10 一臺計算機有8臺打印機，被N個進程競爭使用，每個進程最多需 要3臺。 請問N為多少時，系統(tǒng)沒有死鎖的危險，說明原因。 解: N=3時，沒有死鎖的危險。 對于N個進程，都持有2臺打印機時，申請第3臺打印機，只要有一臺的多余的打印機能被申請到，則系統(tǒng)就沒有死鎖的危險。即N*2+1=8 ，得 N=3。5.11 考慮圖5.9所示的資源分配圖，哪個進程會發(fā)生死鎖？進程P3,P4會發(fā)生死鎖。 對于進程P1,P2，進程的推進不需要等待其他進程的完成。進程P3,P4。P3要等P4完成并釋放資源后方能推進。而P4要等到P3完成后才能。結(jié)果是P3,P4都不能完成。形成死鎖。5.12 假定有3個人排隊等候上電梯。當電梯門打開的時候，3個人都朝門口沖去，但是門不夠大，他們3人不能同時進門。描述解決這種死鎖的方法，可以讓3個人都上電梯。說明你的解決方案清除了哪個死鎖的必要條件。答：讓3個人輪流進電梯。 破壞了死鎖發(fā)生的4個必要條件中的“不剝奪條件”。5.13 假定一個系統(tǒng)具有四種資源類型，分別為：R=3，7，2，3，最大資源需求數(shù)表如圖5.10所示。資源分配器根據(jù)圖5.11中的表來分配資源，這個狀態(tài)安全嗎？為什么？圖5.10圖5.11 答：這個狀態(tài)安全。存在安全執(zhí)行序列P4,P0,P1,P3,P2；6.9 如果一個分頁系統(tǒng)能夠向用戶提供的邏輯地址最大為16頁，頁面大 小為2K，內(nèi)存總共有8個存儲塊。請問邏輯地址應該為多少位？內(nèi) 存空間為多大？解：邏輯地址應該為4+11=15（位） 內(nèi)存空間為8*2K =16K6.10 如果一個分頁系統(tǒng)的頁表存放在內(nèi)存。 （1）若對內(nèi)存的一次存取需要1.2ms，請問一次頁面訪問的存取需 要花多少時間？ （2）若系統(tǒng)配置了聯(lián)想寄存器，對快表的命中率為70%，假如查詢 聯(lián)想寄存器的時間忽略不計，請問實現(xiàn)一次頁面訪問的存取 時間是多少？解：（1）訪問一次頁面的存取需要花費的時間為2*1.2ms=2.4ms （2）實現(xiàn)一次頁面訪問的存取時間=0.3*1.2ms+1.2ms=1.56ms6.11 如果一個分頁系統(tǒng)邏輯地址長度為16位，頁面大小為4KB，第0、1、2頁對應10、12、14號物理塊， 請問邏輯地址為2F6AH對應的物理地址為多少？解：邏輯地址為2F6AH對應的二進制碼為：0010 1111 0110 1010，頁號為：2，頁內(nèi)偏移為F6AH。 查詢頁表2號頁面對應14號塊，所以，物理地址為 1110 1111 0110 1010，最終物理地址為：EF6AH6.12 如果內(nèi)存中有4個空閑塊，每個空閑塊的大小為10MB。有10個請求，每次請求1MB的內(nèi)存大小，對于下面列出的內(nèi)存分配方法中的每一種，確定所有10個請求都被滿足之后剩余空閑塊的大小。 （a）首次適應算法 （b）循環(huán)首次適應算法 （c）最佳適應算法 （d）最壞適應算法解：（a）首次適應算法：塊1用完，塊2，3，4剩余10MB。 （b）循環(huán)首次適應算法：塊1，2余7MB，塊3.4余8MB。 （c）最佳適應算法：塊1用完，塊2，3，4余10MB。 （d）最壞適應算法：塊1，2余7MB，塊3，4余8MB。6.13 如果一個系統(tǒng)的段表為：段 號始 址段 長0200510190030210080312005004180080求下列邏輯地址相應的物理地址。如果越界請指明。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)越界。7.5 在分頁虛擬存儲器管理中，如果已知時間利用率為：CPU20%、分頁 磁盤92%、外設(shè)50%，請問采取哪些措施可以改善CPU的利用率？解：增大分頁磁盤空間。7.6 一個32位地址的計算機系統(tǒng)使用二級頁表，虛擬地址為9位頂級頁 表，11位二級頁表和偏移。請問：頁面長度為多少？虛擬地址空間 有多少個頁面？解：頁面占用的位數(shù)=32-9-11=12位，頁面長度為4K。虛擬地址空間有1M個頁面。7.7 如果分頁虛擬存儲系統(tǒng)向用戶提供的邏輯地址空間最大為16頁，每 頁2KB，內(nèi)存總共有8個存儲塊，請問邏輯地址至少應為多少位？內(nèi) 存空間多大？解：解：邏輯地址應該為4+11=15（位） 內(nèi)存空間為8*2K =16K7.8 在一個請求分頁的虛擬存儲器管理中，一個程序的運行頁面走向為： 1、2、3、4、2、3、5、6、3、1、4、6、7、5、2、4