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

P(seat);

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

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

P(seat);

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

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

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

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

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

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

;當吸煙者拿到所需要的材料后，喚醒供應者進行下一次投放；

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

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

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

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

進程A

Repeat

N=N+5;

Untilfalse;

進程B

Repeat

打印N的值；

N=0；

Untilfalse;

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

進程A

Repeat

P(S);

N=N+5;

V(S);

Untilfalse;

進程B

Repeat

P(S);

打印N的值；

N=0；

V(S);

Untilfalse;假定在單道批處理環境下有5個作業，各作業進入系統的時間和估計運行時間如下表所示：（1）如果應用先來先服務的作業調度算法，試將下面表格填寫完整。（2）如果應用最短作業優先的作業調度算法，試將下面表格填寫完整。

作業

進入系統時間

估計運行時間/分鐘

開始時間

結束時間

周轉時間/分鐘1

8:00

402

8:20

303

8:30

124

9:00

18

5

9:10

5作業

進入系統時間

估計運行時間/分鐘

開始時間

結束時間

周轉時間/分鐘

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作業平均周轉時間T=43.4

217作業

進入系統時間

估計運行時間/分鐘

開始時間

結束時間

周轉時間/分鐘

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作業平均周轉時間T=37.2

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

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

T0時刻系統狀態如下所示：已分配資源數量最大資源需求量

R1R2R3R1R2R3P1001001P2200275P3003665P4115435P5033065

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

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

段號

基地址

長度

合法（0）/非法（1）

0

300

200

1

7500

540

2

3000

1010

3

2000

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

段號

基地址

長度

合法（0）/非法（1）

0

300

200

0

1

7500

540

2

3000

1010

3

2000

100

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

當M=3時，缺頁次數為10次，缺頁率為10/12=0.83=83%。當M=4時，缺頁次數為8次，缺頁率為8/12=0.66=66%。某程序在邏輯地址100處有一條取數指令LOADl，500，而500單元內存放數據51888。假設程序被分配到內存起始地址5000單元時，試用圖示意，采用下述各種方式下的該指令及數據地址的物理地址及相應地址的變換過程。(1)靜態重定位。(2)采用重定位寄存器實現動態重定位。(3)采用頁表映像(映射)方式，假定頁面大小為100單元，其負表各頁映射到50，51、52，53，54，55，…，59物理頁上。對于一個使用快表的頁式虛存，設快表的命中率為70%，內存的存取周期為1ns；缺頁處理時，若內存有可用空間或被置換的頁面在內存未被修改過，則處理一個缺頁中斷需8000ns，否則需20000ns。假定被置換的頁面60%是屬于后一種情況，為了保證有效存取時間不超過2ns，問可接受的最大缺頁率是多少？答：設可接受的最大缺頁率位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在分頁存儲管理系統中，存取一次內存的時間是8ns，查詢一次快表的時間是1ns，缺頁中斷的時間是20ns。假設頁表的查詢與快表的查詢同時進行，當查詢頁表時，如果該頁在內存但快表中沒有頁表項，系統將自動把該頁頁表項送入快表。一個作業最多可保留3個頁面在內存。現在開始執行一作業，系統連續對作業的2，4，5，2，7，6，4，8頁面的數據進行一次存取，如分別采用FIFO算法和最優頁面置換算法，求每種上存取這些數據需要的總時間。答：（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

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

第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

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

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