操作系統(tǒng)經(jīng)典算法題匯總-分章節(jié)

操作系統(tǒng)計(jì)算題匯總2013.12謹(jǐn)以此獻(xiàn)給計(jì)科11級JAVA同學(xué)：學(xué)習(xí)不是為了考試內(nèi)容進(jìn)程管理涉及到計(jì)算題內(nèi)存管理涉及到計(jì)算題外設(shè)管理涉及到計(jì)算題文件系統(tǒng)涉及到計(jì)算題（一）、進(jìn)程管理涉及到計(jì)算題進(jìn)程同步問題理發(fā)店里有一位理發(fā)師、一把理發(fā)椅子和五把供等候理發(fā)的顧客坐的椅子。如果沒有顧客，理發(fā)師便在理發(fā)椅上睡覺。當(dāng)一個顧客到來時(shí)，他必須先叫醒理發(fā)師，如果理發(fā)師正在理發(fā)時(shí)又有顧客來到，而如果有空椅子可坐，他們就坐下來等，如果沒有空椅子，他就離開。這里的問題是為理發(fā)師和顧客各編寫一段程序來描述他們行為，并用wait和signal原語操作實(shí)現(xiàn)其同步。睡眠理發(fā)師問題Processcustomer{

P(seat);

V(customers);//向理發(fā)師發(fā)信號wait_for_haircut();

}睡眠理發(fā)師問題方法1Varcustomers,seat:Semaphore:=0,5Processbarber{While(1){P(customers);//接收顧客信號Cut_hair();V(seat);}}Processcustomer{

P(seat);

V(customers);//向理發(fā)師發(fā)信號P(barbers);//接收理發(fā)師信號

V(seat);Get_haircut();}睡眠理發(fā)師問題方法2Varcustomers,barbers,seat:Semaphore:=0,0,5Processbarber{While(1){P(customers);//接收顧客信號V(barbers);//向顧客發(fā)信號Cut_hair();}}Processcustomer{P(mutex);If(waiting<CHAIRS)then{waiting=waiting+1;V(customers);//向理發(fā)師發(fā)信號V(mutex);P(barbers);//接收理發(fā)師信號Get_haircut();}else{V(mutex);}}睡眠理發(fā)師問題方法3#defineCHAIRS=5Varcustomers,barbers,mutex:Semaphore:=0,0,1intwaiting=0;Processbarber{While(1){P(customers);//接收顧客信號P(mutex);waiting=waiting-1;V(barbers);//向顧客發(fā)信號V(mutex);Cuthair();}}類似問題：吸煙者問題（1971,Patil）：在一個房間內(nèi)有三位吸煙者、一位材料供應(yīng)者。其中：

a)吸煙者：需要擁有三種材料“煙草（Tobacco）、卷煙紙（Cigarette-paper）、火柴（Match）”才能吸煙：

第一位吸煙者有豐富的煙草；

第二位吸煙者有豐富的卷煙紙；

第三位吸煙者有豐富的火柴；

;當(dāng)吸煙者拿到所需要的材料后，喚醒供應(yīng)者進(jìn)行下一次投放；

b)材料供應(yīng)者：不吸煙，且有豐富的Tobacco、Cigarette-paper、Match三種材料；

每次隨機(jī)地將三種材料中的兩種投放到桌子上；

允許擁有另一種材料的吸煙者吸煙。

【要求】編寫算法用信號量和P、V操作實(shí)現(xiàn)它們之間的同步關(guān)系。用信號燈及P、V操作來描述右圖1、說明進(jìn)程的同步關(guān)系：2、設(shè)置信號燈，說明含義、初值。3、寫出程序描述（用P、V操作描述P1、P2、P3）。主函數(shù)如下：main(){ints13=0,s23=0;cobeginp1;p2;p3;coend}兩個并發(fā)執(zhí)行的進(jìn)程A和B的程序如下：

進(jìn)程A

Repeat

N=N+5;

Untilfalse;

進(jìn)程B

Repeat

打印N的值；

N=0；

Untilfalse;

其中N為整數(shù)，初值為4。若進(jìn)程A先執(zhí)行了三個循環(huán)后，進(jìn)程A和進(jìn)程B又并發(fā)執(zhí)行了一個循環(huán)，寫出可能出現(xiàn)的打印值。正確的打印值應(yīng)該是多少？請用P、V操作進(jìn)行管理，使進(jìn)程A和B并發(fā)執(zhí)行時(shí)不會出現(xiàn)與時(shí)間有關(guān)的錯誤。答：因?yàn)镹初值為4，若進(jìn)程A先執(zhí)行了三個循環(huán)，此時(shí)N的值為19。當(dāng)進(jìn)程A和進(jìn)程B并發(fā)執(zhí)行時(shí)可能會有如下兩種執(zhí)行次序，即進(jìn)程A先執(zhí)行一次循環(huán)，然后再進(jìn)程B執(zhí)行一次循環(huán)，此時(shí)打印的是正確值24，執(zhí)行后N中的值為0。但若進(jìn)程B先執(zhí)行一次循環(huán)，然后再進(jìn)程A執(zhí)行一次循環(huán)，則打印的值是19，執(zhí)行后N中的值是5。這是錯誤的，即發(fā)生了與時(shí)間有關(guān)的錯誤。用P、V操作進(jìn)行管理，使進(jìn)程A和B并發(fā)時(shí)不會出現(xiàn)與時(shí)間有關(guān)的錯誤的程序如下：（S為互斥信號量，初值為1），

進(jìn)程A

Repeat

P(S);

N=N+5;

V(S);

Untilfalse;

進(jìn)程B

Repeat

P(S);

打印N的值；

N=0；

V(S);

Untilfalse;假定在單道批處理環(huán)境下有5個作業(yè)，各作業(yè)進(jìn)入系統(tǒng)的時(shí)間和估計(jì)運(yùn)行時(shí)間如下表所示：（1）如果應(yīng)用先來先服務(wù)的作業(yè)調(diào)度算法，試將下面表格填寫完整。（2）如果應(yīng)用最短作業(yè)優(yōu)先的作業(yè)調(diào)度算法，試將下面表格填寫完整。

作業(yè)

進(jìn)入系統(tǒng)時(shí)間

估計(jì)運(yùn)行時(shí)間/分鐘

開始時(shí)間

結(jié)束時(shí)間

周轉(zhuǎn)時(shí)間/分鐘1

8:00

402

8:20

303

8:30

124

9:00

18

5

9:10

5作業(yè)

進(jìn)入系統(tǒng)時(shí)間

估計(jì)運(yùn)行時(shí)間/分鐘

開始時(shí)間

結(jié)束時(shí)間

周轉(zhuǎn)時(shí)間/分鐘

1

8:00

40

8：00

8：40

40

2

8:20

30

8：40

9：10

50

3

8:30

12

9：10

9：22

52

4

9:00

18

9：22

9：40

40

5

9:10

5

9：40

9：45

35作業(yè)平均周轉(zhuǎn)時(shí)間T=43.4

217作業(yè)

進(jìn)入系統(tǒng)時(shí)間

估計(jì)運(yùn)行時(shí)間/分鐘

開始時(shí)間

結(jié)束時(shí)間

周轉(zhuǎn)時(shí)間/分鐘

1

8:00

40

8：00

8：40

40

2

8:20

30

8：52

9：22

62

3

8:30

12

8：40

8：52

22

4

9:00

18

9：27

9：45

45

5

9:10

5

9：22

9：27

17作業(yè)平均周轉(zhuǎn)時(shí)間T=37.2

186進(jìn)程調(diào)度問題：就緒隊(duì)列中有4個進(jìn)程P1，P2，P3，P4同時(shí)進(jìn)入就緒隊(duì)列，它們進(jìn)入就緒隊(duì)列10秒之后開始進(jìn)程調(diào)度，它們需要的處理器時(shí)間如表所示。進(jìn)程處理器時(shí)間（秒）進(jìn)程處理器時(shí)間（秒）P1P21015P3P445忽略進(jìn)行調(diào)度等所花費(fèi)的時(shí)間，且進(jìn)程執(zhí)行過程中不會發(fā)生阻塞，請回答下列問題：分別寫出采用時(shí)間片輪轉(zhuǎn)調(diào)度算法（時(shí)間片為4秒）、響應(yīng)比高者優(yōu)先調(diào)度算法選中進(jìn)程執(zhí)行的次序。在單機(jī)系統(tǒng)中，系統(tǒng)中各個進(jìn)程到達(dá)就緒隊(duì)列的時(shí)刻、執(zhí)行時(shí)間和優(yōu)先級如下表所示。假設(shè)進(jìn)程的調(diào)度時(shí)間忽略不計(jì)。請分別給出采用下面不同的進(jìn)程調(diào)度算法時(shí)各個進(jìn)程的調(diào)度次序，畫出執(zhí)行時(shí)間圖，并計(jì)算平均周轉(zhuǎn)時(shí)間、平均帶權(quán)周轉(zhuǎn)時(shí)間。進(jìn)程到達(dá)就緒隊(duì)列的時(shí)刻執(zhí)行時(shí)間（ms）優(yōu)先級P1033P2265P3441（高）P4652P5824（1）先來先服務(wù)調(diào)度算法；（2）時(shí)間片輪換調(diào)度算法（時(shí)間片為1ms）；（3）搶占式短進(jìn)程優(yōu)先調(diào)度算法；（4）搶占式優(yōu)先級調(diào)度算法；（5）非搶占式優(yōu)先級調(diào)度算法。

例1：系統(tǒng)中有五個進(jìn)程P1、P2、P3、P4、P5，有三種類型的資源：R1、R2、和R3。在T0時(shí)刻系統(tǒng)狀態(tài)如表所示。若采用銀行家算法實(shí)施死鎖避免策略，回答下列問題：（1）T0時(shí)刻是否為安全狀態(tài)？為什么？（2）若這時(shí)P4請求資源（1，2，0），是否能實(shí)施資源分配？為什么？（3）在上面的基礎(chǔ)上，若進(jìn)程P3請求資源（0，1，0），是否能實(shí)施資源分配？為什么？

T0時(shí)刻系統(tǒng)狀態(tài)如下所示：已分配資源數(shù)量最大資源需求量

R1R2R3R1R2R3P1001001P2200275P3003665P4115435P5033065

R1R2R3剩余資源數(shù)330解：（1）T0時(shí)刻是安全的，安全序列為：P1，P4，P5，P2，P3（2）P4請求資源（1，2，0），根據(jù)銀行家算法，預(yù)分配后系統(tǒng)是安全的，安全序列為：P1，P4，P5，P2，P3（3）P3請求資源（1，1，0），根據(jù)銀行家算法，預(yù)分配后系統(tǒng)不安全，所以不能實(shí)施資源分配。

設(shè)系統(tǒng)中有3種類型的資源A、B、C和5個進(jìn)程P0、P1、P2、P3、P4，A資源的數(shù)量為10，B資源的數(shù)量為5，C資源的數(shù)量為7。在T0時(shí)刻系統(tǒng)狀態(tài)如下表所示。系統(tǒng)采用銀行家算法實(shí)施死鎖避免策略。 MaxAllocationNeedAvailableABCABCABCABCP0P1P2P3P4753010743332322200122902302600222211011433002431（1）T0時(shí)刻是否為安全狀態(tài)？若是，請給出安全序列。（2）在T0時(shí)刻若進(jìn)程P1發(fā)出資源請求Request（1，0，2），是否能夠?qū)嵤┵Y源分配？（3）在②的基礎(chǔ)上P4發(fā)出資源請求Request（3，3，0），是否能夠?qū)嵤┵Y源分配？（4）在③的基礎(chǔ)上P0發(fā)出資源請求Request（0，2，0），是否能夠?qū)嵤┵Y源分配?（二）、內(nèi)存管理計(jì)算一個進(jìn)程的大小占5個頁面，每頁的大小為1K，系統(tǒng)為它分配了3個物理塊。當(dāng)前進(jìn)程的頁表如圖所示：塊號 存在位P訪問位R修改位M0x1C1100x3F111-0000x5D100-000（1）有那些頁面不在內(nèi)存？（2分）（2）請分別計(jì)算進(jìn)程中虛地址為0x3B7、0x12A5、0x1432單元的物理地址（用十六進(jìn)制表示），并說明理由。（6分）解：（1）不在內(nèi)存的是2和4頁（按頁號），或第3和5頁（按序號）。（2）0x3B7的物理地址=0x73B70x12A5的物理地址=0x176A5，缺頁，換出第三頁。0x1432地址越界，出錯。在一分頁存儲管理系統(tǒng)中，邏輯地址長度為16位，頁面大小為4096字節(jié)，現(xiàn)有一邏輯地址為2F6AH，且第0、1、2頁依次存放在物理塊5、10、11中，問相應(yīng)的物理地址為多少？根據(jù)如下段表：

段號

基地址

長度

合法（0）/非法（1）

0

300

200

1

7500

540

2

3000

1010

3

2000

100（1）求出邏輯地址為0，100的物理地址并將其的合法性填入上表適當(dāng)位置；（2）求出邏輯地址為3，100的物理地址并將其的合法性填入上表適當(dāng)位置；(1)答：物理地址為：300+100=400(2)答：物理地址為：2000+100=2100

段號

基地址

長度

合法（0）/非法（1）

0

300

200

0

1

7500

540

2

3000

1010

3

2000

100

1給定下面的段表，已知下面的邏輯地址(其中方括號中的第一個元素為段號，第二個元素為段內(nèi)地址)求其對應(yīng)的物理地址：(1)[0,430]；(2)[3,400]；(3)[l,10]；(4)[2,2500]；(5)[4,42]；(6)[1,11]。段號段長段首地址06002191142300210090358013274961954在一個請求分頁系統(tǒng)中，采用LRU頁面置換算法時(shí)，假如一個作業(yè)的頁面走向?yàn)?、3、2、1、4、3、5、4、3、2、1、5，當(dāng)分配給該作業(yè)的物理內(nèi)存塊數(shù)M分別為3和4時(shí)，分別計(jì)算在訪問過程中所發(fā)生的缺頁次數(shù)和缺頁率，并畫出頁面置換圖。

當(dāng)M=3時(shí)，缺頁次數(shù)為10次，缺頁率為10/12=0.83=83%。當(dāng)M=4時(shí)，缺頁次數(shù)為8次，缺頁率為8/12=0.66=66%。某程序在邏輯地址100處有一條取數(shù)指令LOADl，500，而500單元內(nèi)存放數(shù)據(jù)51888。假設(shè)程序被分配到內(nèi)存起始地址5000單元時(shí)，試用圖示意，采用下述各種方式下的該指令及數(shù)據(jù)地址的物理地址及相應(yīng)地址的變換過程。(1)靜態(tài)重定位。(2)采用重定位寄存器實(shí)現(xiàn)動態(tài)重定位。(3)采用頁表映像(映射)方式，假定頁面大小為100單元，其負(fù)表各頁映射到50，51、52，53，54，55，…，59物理頁上。對于一個使用快表的頁式虛存，設(shè)快表的命中率為70%，內(nèi)存的存取周期為1ns；缺頁處理時(shí)，若內(nèi)存有可用空間或被置換的頁面在內(nèi)存未被修改過，則處理一個缺頁中斷需8000ns，否則需20000ns。假定被置換的頁面60%是屬于后一種情況，為了保證有效存取時(shí)間不超過2ns，問可接受的最大缺頁率是多少？答：設(shè)可接受的最大缺頁率位p，則有1ns×0.7+2ns×(1-0.7-p)+0.4p×8000ns+0.6p×20000ns=2ns即

0.7+0.6-2p+3200p+12000p=2

15198p=0.7

P=0.000046在分頁存儲管理系統(tǒng)中，存取一次內(nèi)存的時(shí)間是8ns，查詢一次快表的時(shí)間是1ns，缺頁中斷的時(shí)間是20ns。假設(shè)頁表的查詢與快表的查詢同時(shí)進(jìn)行，當(dāng)查詢頁表時(shí)，如果該頁在內(nèi)存但快表中沒有頁表項(xiàng)，系統(tǒng)將自動把該頁頁表項(xiàng)送入快表。一個作業(yè)最多可保留3個頁面在內(nèi)存。現(xiàn)在開始執(zhí)行一作業(yè)，系統(tǒng)連續(xù)對作業(yè)的2，4，5，2，7，6，4，8頁面的數(shù)據(jù)進(jìn)行一次存取，如分別采用FIFO算法和最優(yōu)頁面置換算法，求每種上存取這些數(shù)據(jù)需要的總時(shí)間。答：（1）FIFO

第2頁面：20＋8×3

第4頁面：20＋8×3

第5頁面：20＋8×3

第2頁面：8＋1

第7頁面：20＋8×3

第6頁面：20＋8×3

第4頁面：20＋8×3

第8頁面：20＋8×3

因此總的時(shí)間是（20＋8×3）×7＋（8＋1）ns(2)最優(yōu)頁面置換

第2頁面：20＋8×3

第4頁面：20＋8×3

第5頁面：20＋8×3

第2頁面：8＋1

第7頁面：20＋8×3

第6頁面：20＋8×3

第4頁面：8＋1

第8頁面：8＋1

因此總的時(shí)間是（20＋8×3）×5＋（8＋1）×3ns在某分頁系統(tǒng)中，測得CPU和磁盤的利用率如下，試指出每種情況下的問題和措施。（1）CPU的利用率為15%，磁盤利用率為95%。（2）CPU的利用率為88%，磁盤利用率為3%。（3）CPU的利用率為13%，磁盤利用率為5%。答：在某分頁虛存系統(tǒng)中，在題中的CPU和磁盤的利用率的情況下，出現(xiàn)的問題和應(yīng)采取的措施如下：（1）可能已出現(xiàn)了抖動現(xiàn)象，應(yīng)減少系統(tǒng)的進(jìn)程數(shù)。（2）系統(tǒng)比較正常，可考慮適當(dāng)增加進(jìn)程數(shù)以提高資源利用率。（3）CPU和磁盤的利用率都較低，必須增加并發(fā)進(jìn)程數(shù)?？紤]一個有快表的請求分頁系統(tǒng)，設(shè)內(nèi)存的讀寫周期為1ns，內(nèi)外存之間傳送一個頁面的平均時(shí)間為5000ns，快表的命中率為80%，頁面失效率為10%，求內(nèi)存的有效存取時(shí)間。答：內(nèi)存的有效存取時(shí)間EAT(EfficentAccessTime)也叫平均存取時(shí)間AAT(AverageAccessTime)，其計(jì)算公式如下：EAT＝1ns×80%+2ns×10%+(5000ns+2ns)×10%=0.8ns+0.2ns+500.2ns=501.2ns一臺計(jì)算機(jī)有一個Cache、內(nèi)存儲器和用作虛擬存儲器的磁盤，假設(shè)訪問Cache中的字需要20ns的定位時(shí)間；如果該字在內(nèi)存儲器中而不在Cache中，則需要60ns的時(shí)間載入Cache，然后在重新開始定位；如果該字不在內(nèi)存儲器中，則需要12ms的時(shí)間從磁盤中提取，然后需要60ns復(fù)制到Cache中，然后在定位。Cahce的命中率為0.9，內(nèi)存儲器的命中率為0.6，在該系統(tǒng)中訪問一個被定位的字需要的平均時(shí)間是多少ns？（三）、外設(shè)管理計(jì)算三、磁盤訪問時(shí)間：1.尋道時(shí)間：TS=m*n+sm：常量，n：磁道數(shù)，s：磁盤啟動時(shí)間。2.旋轉(zhuǎn)延時(shí)間Tr（平均旋轉(zhuǎn)延遲時(shí)間）：指定扇區(qū)旋轉(zhuǎn)到磁頭下所需時(shí)間。設(shè)每秒r轉(zhuǎn)，則Tr＝1/(2r)（均值）3.數(shù)據(jù)傳輸時(shí)間:Tt＝b/(rN)b：每次讀/寫字節(jié)數(shù)N：每道上的字節(jié)數(shù)訪問時(shí)間：Ta=Ts+1/(2r)+b/(rN)可見，由于特定磁盤，只有集中放數(shù)據(jù)，集中讀寫（b的值大）才能更好提高傳輸效率。尋道時(shí)間:20ms，磁盤通道傳輸速率:1MB/s，轉(zhuǎn)速r=3600rpm，每扇區(qū)512字節(jié)，每磁道32扇區(qū)。目標(biāo)：讀128k數(shù)據(jù)，問：訪問時(shí)間為多少？因?yàn)椋?0*16kB=960kB/s<1MB/s順序組織(20＋8.33＋16.67)＋(8.33＋16.67)×7＝220(ms)隨機(jī)組織(20＋8.33＋0.52)×256＝7385.6(ms)其中：3600轉(zhuǎn)/分=60轉(zhuǎn)/秒，0.5KB*32=16KB/道其中：1/r=1/60≈16.67ms/轉(zhuǎn)，均值=1/(2r)≈8.33ms/轉(zhuǎn)；128KB/16KB=8其中：Tt＝b/(rN)=0.5KB/(60*16KB)≈0.52(ms),128KB/0.5KB=256某磁盤組有6片盤片，每片有兩個記錄面，存儲區(qū)域內(nèi)徑為22cm，外徑為33cm，道存儲密度為40道/cm，內(nèi)層位存儲密度為400b/cm，轉(zhuǎn)速為3000r/min（轉(zhuǎn)/分），問共有多少柱面？盤組總存儲量為多少？平均等待時(shí)間為多少？假定磁盤轉(zhuǎn)速為6000r/min（轉(zhuǎn)/分），磁盤格式化時(shí)每個盤面被分為9個扇區(qū)，現(xiàn)有一個文件共有 A，B，C，D，E，F(xiàn)，G，H，I九個邏輯記錄要存放在同一磁道上供處理程序使用，假設(shè)每個記錄的大小與扇區(qū)的大小相同，處理程序每次從磁盤讀出一個記錄后要花2.5ms處理時(shí)間。若忽略其他輔助時(shí)間，請回答下列問題：（1）現(xiàn)在假設(shè)已經(jīng)順序存放好這9個記錄，那么讀出該文件需要多少時(shí)間？（2）為了使讀出文件需要的時(shí)間最短，請重新調(diào)整各個記錄的存放位置，畫出各個記錄的存放位置，計(jì)算該文件的讀出時(shí)間，并與（1）進(jìn)行比較說明。假設(shè)計(jì)算機(jī)系統(tǒng)采用CSCAN(循環(huán)掃描)磁盤調(diào)度策略,使用2KB的內(nèi)存空間記錄16384個磁盤的空閑狀態(tài)(1)、請說明在上述條件如何進(jìn)行磁盤塊空閑狀態(tài)的管理。

(2)、設(shè)某單面磁盤的旋轉(zhuǎn)速度為每分鐘6000轉(zhuǎn)，每個磁道有100個扇區(qū)，相臨磁道間的平均移動的時(shí)間為1ms。若在某時(shí)刻，磁頭位于100號磁道處，并沿著磁道號增大的方向移動，磁道號的請求隊(duì)列為50，90，30，120對請求隊(duì)列中的每個磁道需讀取1個隨機(jī)分布的扇區(qū)，則讀完這個扇區(qū)點(diǎn)共需要多少時(shí)間？需要給出計(jì)算過程。假設(shè)一個可移動磁頭的磁盤具有200個磁道，其編號為0～199，當(dāng)它剛剛結(jié)束了125道的存取后，現(xiàn)正在處理143道的服務(wù)請求，假設(shè)系統(tǒng)當(dāng)前I/O請求序列以FIFO順序排列如下：86，147，91，177，94，150，102，175，130。試問對以下幾種磁盤I/O請求調(diào)度算法而言，滿足以上請求序列，磁頭將分別如何移動，請列出磁道訪問次序，并計(jì)算出移動距離？假設(shè)有一個磁盤組共有100個柱面，每個柱面上有8個磁道，每個盤面被分成8個扇區(qū)?，F(xiàn)有一個含有6400邏輯記錄的文件，邏輯記錄的大小與扇區(qū)一致，該文件以順序結(jié)構(gòu)的形式被存儲到磁盤上。柱面、磁道、扇區(qū)的編號從“0”開始，邏輯記錄的編號也從“0”開始。文件信息從0柱面、0磁道、0扇區(qū)開始存放，試問：（1）該文件的3680個邏輯記錄應(yīng)該存放在什么位置？（2）78柱面