孫鐘秀 OS習(xí)題講解

OS習(xí)題講解(孫鐘秀第四版)P581、有一臺計算機，具有IMB內(nèi)存，操作系統(tǒng)占用200KB，每個用戶進程各占200KB。如果用戶進程等待I/O的時間為80%，若增加1MB內(nèi)存，則CPU的利用率提高多少？習(xí)題一答：設(shè)每個進程等待I/O的百分比為P，則n個進程同時等待I/O的概率是Pn，當(dāng)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

故增加1MB內(nèi)存使CPU的利用率提高了47%:

87％/59％=147%

147％-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ā)生等待的時刻。（1）兩道程序運行期間，CPU存在空閑等待，時間為100至150ms之間（見圖中有色部分）（2）程序A無等待現(xiàn)象，但程序B有等待。程序B有等待時間段為180rns至200ms間（見圖中有色部分）在單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(40ms)

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è)備利用率。(1)Job1從投入到運行完成需110ms,Job2從投入到運行完成需90ms,Job3從投入到運行完成需110ms.CPU空閑時間段為：60ms至70ms,80ms至90ms,100ms至110ms。所以CPU利用率為（110-30）/10=72.7％。設(shè)備I1空閑時間段為：20ms至40ms,90ms至100ms,故I1的利用率為(110-30)/l10=72.7％。設(shè)備I2空閑時間段為：30ms至50ms，故I2的利用率為(110-20)/110=81.8％。11.在某計算機系統(tǒng)中，時鐘中斷處理程序每次執(zhí)行的時間為2ms（包括進程切換開銷）。若時鐘中斷頻率為60HZ，試問CPU用于時鐘中斷處理的時間比率為多少？答：因時鐘中斷頻率為60HZ，所以，時鐘周期為：l/60s=50/3ms。在每個時鐘周期中，CPU花2ms執(zhí)行中斷任務(wù)。所以，CPU用于時鐘中斷處理的時間比率為：2/(50/3)=6/50=12％。第二章習(xí)題P155第5題答：采用短作業(yè)優(yōu)先算法調(diào)度時，三個作業(yè)的總周轉(zhuǎn)時間為：

T1=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-T1=b-a>0可見，采用短作業(yè)優(yōu)先算法調(diào)度才能獲得最小平均作業(yè)周轉(zhuǎn)時間。P155第7題采用FCFS算法調(diào)度作業(yè)，運作情況：執(zhí)行次序執(zhí)行時間等待時間開始時間完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)110001010121101011111132111113136.541131314141455141419193.8作業(yè)平均周轉(zhuǎn)時間T=(10+11+13+14+19)/5=13.4作業(yè)平均帶權(quán)周轉(zhuǎn)時間W=(1+11+6.5+14+3.8)/5=7.26

采用RR算法調(diào)度作業(yè)，若令時間片長=1，各作業(yè)執(zhí)行情況為、1、2、3、4、5、1、3、5、1、5、1、5、1、5、1、1、1、1、1。作業(yè)執(zhí)行時間提交時間完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間110019191.9210222320773.541044455014142.8

作業(yè)平均周轉(zhuǎn)時間T=(19+2+7+4+14)/5=9.2作業(yè)平均帶權(quán)周轉(zhuǎn)時間W=(1.9+2+3.5+4+2.8)/5=2.84

采用SJF算法調(diào)度作業(yè)，運作情況：執(zhí)行次序執(zhí)行時間等待時間開始完成周轉(zhuǎn)帶權(quán)周轉(zhuǎn)2100111411122232224425544991.81109919191.9作業(yè)平均周轉(zhuǎn)時間T=(1+2+4+9+19)/5=7作業(yè)平均帶權(quán)周轉(zhuǎn)時間W=(1+2+2+1.8+1.9)/5=1.74采用非剝奪優(yōu)先權(quán)算法調(diào)度作業(yè)，運作情況

執(zhí)行次序優(yōu)先數(shù)執(zhí)行等待周轉(zhuǎn)帶權(quán)周轉(zhuǎn)211011525161.213106161.633216189441181919

作業(yè)平均周轉(zhuǎn)時間T=(1+6+16+18+19)/5=12作業(yè)平均帶權(quán)周轉(zhuǎn)時間W=(1+1.2+1.6+9+19)/5=6.36第9題1)Q=無窮大CPU利用率=T/(T+S)2）Q>TCPU利用率=T/(T+S)3)S<Q<TCPU利用率=Q/(Q+S)4)Q=SCPU利用率=Q/(Q+S)]5)Q接近于0CPU利用率—>0第10題x≤3次序為：x，3，5，6，93<x≤5次序為：3，x，5，6，95<x≤6次序為：3，5，x，6，96<x≤9次序為：3，5，6，x，99<x次序為：3，5，6，9，x第13題處理器調(diào)度算法會考慮以下因素：作業(yè)響應(yīng)時間要求；讓CPU盡量和外圍設(shè)備并行工作；限制一個計算進程長時間霸占處理器。因而：(1)I/O為主作業(yè)優(yōu)先級高。(2)輸入輸出為主作業(yè)優(yōu)先級最高，輸入輸出均勻的作業(yè)其次，而計算為主作業(yè)的優(yōu)先級最低。第18題(1)若α>β>0是什么算法？(2)若α<β<0是什么算法是先進先出算法。因為在就緒隊列中的進程比在CPU上運行的進程的優(yōu)先數(shù)提高得快，故進程切換時，先進入就緒隊列的進程優(yōu)先權(quán)就越高。是后進先出算法。因為在就緒隊列中的進程比在CPU上運行的進程的優(yōu)先權(quán)下降得快，故后進入就緒隊列的進程此先進入的進程的優(yōu)先權(quán)高。第25題每個作業(yè)運行將經(jīng)過兩個階段：作業(yè)調(diào)度(SJF算法)和進程調(diào)度(優(yōu)先數(shù)搶占式)。另外，批處理最多容納2道作業(yè)，更多的作業(yè)將在后備隊列等待。10:00，作業(yè)A到達并投入運行。10:20，作業(yè)B到達且優(yōu)先權(quán)高于作業(yè)A，故作業(yè)B投入運行而作業(yè)A在就緒隊列等待。10:30，作業(yè)C到達，因內(nèi)存中已有兩道作業(yè)，故作業(yè)C進入作業(yè)后備隊列等待。10:50，作業(yè)B運行結(jié)束，作業(yè)D到達，按SJF短作業(yè)優(yōu)先算法，作業(yè)D被裝入內(nèi)存進入就緒隊列。而由于作業(yè)A的優(yōu)先級高于作業(yè)D，故作業(yè)A投入運行。11:10，作業(yè)A運行結(jié)束，作業(yè)C被調(diào)入內(nèi)存，且作業(yè)C的優(yōu)先級高于作業(yè)D，故作業(yè)C投入運行。12:00，作業(yè)C運行結(jié)束，作業(yè)D投入運行。12:20，作業(yè)D運行結(jié)束。作業(yè)進入內(nèi)存時間運行結(jié)束時間A10:0011:10B10:2010:50C11:1012:00D10:5012:20各作業(yè)周轉(zhuǎn)時間為：作業(yè)A70，作業(yè)B30，作業(yè)C90，作業(yè)D90。平均作業(yè)周轉(zhuǎn)時間為70分鐘。第27題(1)作業(yè)調(diào)度選擇的作業(yè)次序為：作業(yè)1、作業(yè)3、作業(yè)4、作業(yè)2和作業(yè)5。(2)全部作業(yè)運行結(jié)束的時間9:35。(3)周轉(zhuǎn)時間：作業(yè)1為30分鐘、作業(yè)2為60分鐘、作業(yè)3為40分鐘、作業(yè)4為40分鐘和作業(yè)5為60分鐘。(4)平均作業(yè)周轉(zhuǎn)時間=56分鐘。(5)最大作業(yè)周轉(zhuǎn)時間為60分鐘。第四章習(xí)題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ù)和缺頁中斷率。答：頁框數(shù)FIFOLRUOPT3161511414108512876977

只要把表中缺頁中斷次數(shù)除以20，便得到缺頁中斷率。4在可變分區(qū)存儲管理下，按地址排列的內(nèi)存空閑區(qū)為：10K、4K、20K、18K、7K、9K、12K和15K。對于下列的連續(xù)存儲區(qū)的請求：(1)12K、10K、9K，(2)12K、10K、15K、18K試問：使用首次適應(yīng)算法、最佳適應(yīng)算法、最差適應(yīng)算法和下次適應(yīng)算法，哪個空閑區(qū)被使用？答：(1)空閑分區(qū)如圖所示。分區(qū)號分區(qū)長110KB24KB320KB418KB57KB69KB712KB815KB1)首次適應(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。10KB選中分區(qū)1，恰好分配故應(yīng)刪去分區(qū)1。9KB選中分區(qū)6，恰好分配故應(yīng)刪去分區(qū)6。3)最差適應(yīng)算法12KB選中分區(qū)3，這時分區(qū)3還剩8KB。10KB選中分區(qū)4，這時分區(qū)4還剩8KB。9KB選中分區(qū)8，這時分區(qū)3還剩6KB。4)下次適應(yīng)算法12KB選中分區(qū)3，這時分區(qū)3還剩8KB。10KB選中分區(qū)4，這時分區(qū)4還剩8KB。9KB選中分區(qū)6，恰好分配故應(yīng)刪去分區(qū)6。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。10KB選中分區(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。10KB選中分區(qū)4，這時分區(qū)4還剩8KB。15KB選中分區(qū)8，恰好分配故應(yīng)刪去分區(qū)8。最后無法滿否18KB的申請，應(yīng)該等待。6一個32位地址的計算機系統(tǒng)使用二級頁表，虛地址被分為9位頂級頁表，11位二級頁表和偏移。試問：頁面長度是多少？虛地址空間共有多少個頁面？答：由于32-9-11=12，所以，頁面大小為4KB，頁面的個數(shù)為1M個。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/nm9某計算機有cache、內(nèi)存、輔存來實現(xiàn)虛擬存儲器。如果數(shù)據(jù)在cache中，訪問它需要20ns；如果在內(nèi)存但不在cache，需要60ns將其裝入緩存，然后才能訪問；如果不在內(nèi)存而在輔存，需要12μs將其讀入內(nèi)存，然后，用60ns再讀入cache，然后才能訪問。假設(shè)cache命中率為0.9，內(nèi)存命中率為0.6，則數(shù)據(jù)平均訪問時間是多少(ns)？答：20*0.9+（60+20）*（1-0.9）*0.6+（12000+60+20）*（1-0.9）*（1-0.6）=18+4.8+483.2=506ns。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.48=1.24微秒20在一個分頁虛存系統(tǒng)中，用戶編程空間32個頁，頁長1KB，主存為16KB。如果用戶程序有10頁長，若己知虛頁0、1、2、3，已分到頁框8、7、4、10，試把虛地址0AC5H和1AC5H轉(zhuǎn)換成對應(yīng)的物理地址。答：虛地址0AC5H對應(yīng)的物理地址為：12C5H。而執(zhí)行虛地址1AC5H會發(fā)現(xiàn)頁表中尚未有分配的頁框而發(fā)生缺頁中斷，由系統(tǒng)另行分配頁框。0AC5H=0000101011000101頁號頁內(nèi)地址頁號000010對應(yīng)塊號000100轉(zhuǎn)換為物理地址0001001011000101=12C5H1AC5H頁號為000110=6不在主存，缺頁中斷27某請求分頁存儲系統(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

28請頁式存儲管理中，進程訪問地址序列為：10,11,104,170,73,305,180,240,244,445,467，366。試問1)如果頁面大小為100，給出頁面訪問序列。2)進程若分得3個頁框，采用FIFO和LRU替換算法，求缺頁中斷率?答：1)頁面訪問序列為1，1，2，2，1，4，2，3，3，5，5，4。2)FIFO為5次，缺頁中斷率為5/12=41.6%。LRU為6次，缺頁中斷率為6/12=50%。LRU反比FIFO缺頁中斷率高。40已知某系統(tǒng)頁面為4KB，頁表項4B，采用多級頁表映射64位虛地址空間。若限定最高層頁表占1頁，問它可以采用幾級頁表？答：頁面4K，占12位，剩余52位為頁號，總共有252個頁面。頁面長4K，每個頁號占4B，則一頁中可放1K個頁號。每個頁表項指向一頁，每頁又存放頁表項1K個，依次類推，最多可以采用6級頁表。第五章習(xí)題旋轉(zhuǎn)型設(shè)備上信息的優(yōu)化分布能減少為若干個I/O服務(wù)的總時間。設(shè)磁鼓上分為20個區(qū)，每區(qū)存放一個記錄，磁鼓旋轉(zhuǎn)一周需20毫秒，讀出每個記錄平均需用1毫秒，讀出后經(jīng)2毫秒處理，再繼續(xù)處理下一個記錄。在不知當(dāng)前磁鼓位置的情況下：（1）順序存放記錄1、……，記錄20時，試計算讀出并處理20個記錄的總時間；（2）給出優(yōu)先分布20個記錄的一種方案，使得所花的總處理時間減少，且計算出這個方案所花的總時間。定位第1個記錄需10ms。讀出第1個記錄，處理花2ms，這時已到了第4個記錄，再轉(zhuǎn)過18個記錄(花18ms)才能找到記錄2，所以，讀出并處理20個記錄的總時間：10+3+(1+2+18)×19=13+21×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。當(dāng)讀出第1個記錄，花2ms處理后，恰好就可以處理記錄2，省去了尋找下一個記錄的時間，讀出并處理20個記錄的總時間：10+3+3×19=13+247=260ms5.答:使磁盤的旋轉(zhuǎn)圈數(shù)為最少的調(diào)度次序為:5,3,2,1,4.12.每柱面有20*8=160塊，606/160=3（柱面號）606%160=126126/8=15（磁道號）126%8=6（扇區(qū)號）13.（1）160字符/800字符=0.2英寸1500*0.2英寸=300英寸0.6英寸*1500=900英寸利用率為300/（300+900）=25%（2）300+900=1200英寸（3）當(dāng)間隙小于300英寸時，空間利用率不小于50%,300/0.6=5001500/500=3,至少要3個邏輯記錄為一組，才能使空間利用率不小于50%。15．非優(yōu)化存放，讀一塊數(shù)據(jù)需要時間為：13*6+100+25=203ms因而傳輸100塊的文件的時間為：20300ms優(yōu)化存放，讀一塊數(shù)據(jù)需要時間為：2*6+100+25=137ms因而傳輸100塊的文件的時間為：13700ms16.磁盤請求以10,22,20,2,40,6,38柱面的次序到達磁盤驅(qū)動器,如果磁頭當(dāng)前位于柱面20.若查找移動每個柱面要花6ms.用以下算法計算出查找時間:1)FCFS,2)最短查找優(yōu)先,3)電梯算法(正向柱面大的方向).答:1)FCFS查找時間次序為:20,10,22,20,2,40,6,38,查找時間為:876ms2)最短查找優(yōu)先查找次序為:20,20,22,10,6,2,38,40,查找時間為:360ms3)電梯算法查找次序為:20,20,22,38,40,10,6,2,.查找時間為:348ms第六章習(xí)題2.F=B/R8.1569/512=3,1569%512=33;第3個盤塊（80）33字節(jié)處。3某操作系統(tǒng)的磁盤文件空間共有500塊，若用字長為32位的位示圖管理盤空間，試問：(1)位示圖需多少個字?(2)第i字第j位對應(yīng)的塊號是多少?(3)并給出申請/歸還一塊的工作流程。答：

(1)位示圖占用字?jǐn)?shù)為500/32=16(向上取整)個字。(2)第i字第j位對應(yīng)的塊號N=32×i+j。(3)申請時自上至下、自左至有掃描位示圖跳過為1的位，找到第一個遷到的0位，根據(jù)它是第i字第j位算出對應(yīng)塊號，并分配出去。歸還時已知塊號，塊號/32算出第i字第j位并把位示圖相應(yīng)位清0。5在UNIX中，如果一個盤塊的大小為1KB，每個盤塊號占4個字節(jié)，即每塊可放256個地址。請轉(zhuǎn)換下列文件的字節(jié)偏移量為物理地址：(1)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)物理塊號。9000L1=INT(9999，1024)=9B1=MOD(9999，1024)=783其邏輯塊號為9，故直接索引addr[9]中可找到物理塊號。18000L2=INT(18000，1024)=17B1=MOD(18000，1024)=592其邏輯塊號為17，通過一次間接索引addr[10]中可找到物理塊號。420000L1=INT(420000，1024)=410B1=MOD(9000，1024)=160其邏輯塊號為410，通過二次間接索引addr[11]中可找到物理塊號。9．一個UNIX/Linux文件，如果一個盤塊的大小為1KB，每個盤塊號占4個字節(jié)，那么，若進程欲訪問偏移為263168字節(jié)處的數(shù)據(jù)，需經(jīng)過幾次間接尋址？UNIX/Linux文件系統(tǒng)中，直接尋址為10塊，一次間接尋址為256塊，二次間接尋址為2562塊，三次間接尋址為2563塊。偏移為263168字節(jié)的邏輯塊號是：263168/1024=257。塊內(nèi)偏移量=263168-257×1024=0。由于10<257<256+10，故263168字節(jié)在一次間接尋址內(nèi)。11設(shè)文件ABCD為定長記錄的連續(xù)文件，共有18個邏輯記錄。如果記錄長為512B，物理塊長為1024B，采用成組方式存放，起始塊號為12，敘述第15號邏輯記錄讀入內(nèi)存緩沖區(qū)的過程。