操作系統(tǒng)大題全集

1、2進(jìn)程A1，A2，Anl通過m個(gè)緩沖區(qū)向進(jìn)程B1，B2，Bn2不斷地發(fā)送消息，發(fā)送和接收工作遵循如下規(guī)則： （1）每個(gè)發(fā)送進(jìn)程一次發(fā)送一個(gè)信息，寫入一個(gè)緩沖區(qū)，緩沖區(qū)大小與消息長度一樣；（2）對(duì)每一個(gè)消息，B1，B2，Bn2都需各接收一次，讀入各自的數(shù)據(jù)區(qū)內(nèi)；（3）m個(gè)緩沖區(qū)都滿時(shí)，發(fā)送進(jìn)程等待，沒有可讀的消息時(shí)，接收進(jìn)程等待。試用P、V操作組織正確的發(fā)送和接收操作。解答：這是一個(gè)變形的生產(chǎn)和消費(fèi)問題。每個(gè)緩沖區(qū)只需寫一次，但需讀n2次?？梢园岩唤M緩沖區(qū)看做n2組緩沖區(qū)，這樣，每個(gè)生產(chǎn)者需要同時(shí)寫n2個(gè)緩沖區(qū)組中相應(yīng)的n2個(gè)緩沖區(qū)，而每一個(gè)消費(fèi)者只需讀它自己對(duì)應(yīng)的那組緩沖區(qū)中的單元。生產(chǎn)者須在

2、n2個(gè)緩沖區(qū)都為空閑是方可寫入，這時(shí)，就可以用n2組信息量（avail,free ）來實(shí)現(xiàn)這一流程，具體流程如下：BEGIN integer mutex,availn2,fulln2; integer I; mutex : =1; for I :=1 to n2 do begin avail I := m; full I := 0; end; procedure sendM integer I ; begin for I :=1 to n2 do begin P( avail I); end ; P (metux); 將消息放入緩沖區(qū); for I :=1 to n2 do begin V(f

3、ull I); end ; V (metux)end ; procedure receive(M,I) begin P (fullI); P (metux); 從緩沖區(qū)中取消息; V (avail I); V (mutex);end ; Cobegin Ai:begin . send M end Bi;begin.Receive(M,i);end;Coend;end;3設(shè)系統(tǒng)中僅有一類數(shù)量為M的獨(dú)占型資源，系統(tǒng)中有N個(gè)進(jìn)程競爭該類資源，其中各進(jìn)程對(duì)該類資源的最大需求數(shù)為W，當(dāng)M，N，W分別取下列值時(shí)，試判斷哪些情況會(huì)發(fā)生死鎖，為什么？（1） M=2，N=2，W=1（2） M=3，N=2 W=2

4、（3） M=3，N=2，W=3（4） M=5 N=3 W=2（5） M=6 N=3 W=3 解答： （1） 不會(huì)發(fā)生死鎖。因?yàn)橄到y(tǒng)中只有兩個(gè)進(jìn)程，每個(gè)進(jìn)程的最大需求量為1，且系統(tǒng)中資源總數(shù)為2，系統(tǒng)能夠滿足兩個(gè)進(jìn)程的最大資源需求量，故不會(huì)發(fā)生死鎖。（2） 不會(huì)發(fā)生死鎖。因?yàn)橄到y(tǒng)中有兩個(gè)進(jìn)程，每個(gè)進(jìn)程的最大資源需求量為2，且系統(tǒng)中資源總數(shù)為3，無論如何分配，兩個(gè)進(jìn)程中必有一個(gè)進(jìn)程可以獲得兩個(gè)資源，該進(jìn)程將順利完成，從而可以將分配給它的資源歸還給系統(tǒng)，使另一個(gè)進(jìn)程也能順利執(zhí)行完成，故不會(huì)發(fā)生死鎖。（3） 可能發(fā)生死鎖。因?yàn)橄到y(tǒng)中有兩個(gè)進(jìn)程，每個(gè)進(jìn)程的最大資源需求量為3，且系統(tǒng)中資源總量為3，若系統(tǒng)

5、先將全部資源分配給其中一個(gè)過程，則該進(jìn)程將順利完成，從而可將分配給它的資源歸還給系統(tǒng)，使另一進(jìn)程也能順利完成，以這種方式分配資源時(shí)不會(huì)發(fā)生死鎖；若系統(tǒng)將兩個(gè)資源分配給一個(gè)過程，而剩余的一個(gè)資源分配給另一個(gè)進(jìn)程，則系統(tǒng)中沒有空閑資源，而每個(gè)進(jìn)程都需要等待資源，此時(shí)發(fā)生死鎖。（4） 不會(huì)發(fā)生死鎖。因?yàn)橄到y(tǒng)中有3個(gè)過程，每個(gè)進(jìn)程的最大資源需求量為2，且系統(tǒng)中資源總量為5，無論如何分配，3個(gè)進(jìn)程中必有一個(gè)進(jìn)程可以獲得2個(gè)資源，該進(jìn)程將順利完成，從而可以將分配給它的資源歸還給系統(tǒng)，使其他進(jìn)程也能順利執(zhí)行完成，故不會(huì)發(fā)生死鎖（5） 可能會(huì)發(fā)生死鎖。因?yàn)橄到y(tǒng)中有3個(gè)進(jìn)程，每個(gè)進(jìn)程的最大資源需求量為3，且系統(tǒng)

6、中資源總數(shù)為6 ，若系統(tǒng)先將3個(gè)資源分配給其中一個(gè)過程，則該進(jìn)程將順利完成，從而可將分配給它的資源歸還給系統(tǒng)，使其他進(jìn)程也能順利完成，以這種方式分配資源時(shí)不會(huì)發(fā)生死鎖；若系統(tǒng)給每個(gè)進(jìn)程分配兩個(gè)資源，則系統(tǒng)中沒有空間資源，而每個(gè)進(jìn)程都需要等待一個(gè)資源，此時(shí)發(fā)生死鎖。 4 設(shè)某作業(yè)占有7個(gè)頁面，如果在主存中只允許裝入4個(gè)工作頁面（即工作集為4），作業(yè)運(yùn)行時(shí)，實(shí)際訪問頁面的順序是1，2，3，6，4，7，3，2，1，4，7，5，6，5，2，1。試用FIFO與LRU頁面調(diào)度算法，列出各自的頁面淘汰順序和缺頁中斷次數(shù)，以及最后留駐主存4頁的順序（假設(shè)開始的4個(gè)頁面已裝入主存）。解答：對(duì)O算法：頁面淘汰順序

7、為，；缺頁中斷次；最后留駐主存頁的順序?yàn)椋海?。對(duì)的算法；頁面淘汰順序?yàn)?，缺頁中斷次；最后留駐主存頁的概率：，注：假定前面四頁，已在主存5在某請(qǐng)求分頁管理系統(tǒng)中，一個(gè)作業(yè)共頁，作業(yè)執(zhí)行時(shí)依次訪問如下頁面：，若分配給該作業(yè)的主存塊數(shù)為，分別采用，頁面置換算法，試求出缺頁中斷的次數(shù)及缺頁率。解答：（1）采用頁面置換算法， 缺頁中斷的次數(shù)為，缺頁率9/（）采用頁面置換短法缺頁中斷的次數(shù)為，缺頁率6設(shè)內(nèi)存中有三道 程序A，B，C，它們按A/B/C的優(yōu)先次序執(zhí)行，它們的計(jì)算和I/O操作的時(shí)間如表所1-1示（單位；MS） 表1-1 3道程序的操作時(shí)間程序操作ABC計(jì)算204010I/O302030計(jì)算10

8、1020 假設(shè)3道程序使用相同設(shè)備進(jìn)行I/O操作，即程序以串行方式使用設(shè)備，試畫出單道運(yùn)行和多道運(yùn)行的時(shí)間關(guān)系圖（調(diào)度程序執(zhí)行時(shí)間忽略不計(jì)）在兩種情況下，完成這三道程序各要花多少時(shí)間？解答 ：若采用單道方式運(yùn)行三道程序，則運(yùn)行次序?yàn)锳，B，C，即程序A先執(zhí)行20MS的計(jì)算，再完成30MS的I/O操作。最后在進(jìn)行10MS的計(jì)算。接下來程序B先執(zhí)行40MS的計(jì)算，再完成20MS的I/O操作。最后在進(jìn)行10MS的計(jì)算。然后程序C先執(zhí)行10MS的計(jì)算，再完成30MS的I/O操作。最后在進(jìn)行20MS的計(jì)算。至此，三到程序全部運(yùn)行完畢，其程序運(yùn)行的時(shí)間關(guān)系如圖1-1所示 總的運(yùn)行時(shí)間為 20+30+ 10

9、+ 40+ 20+ 10+ 10+ 30+ 20=190msI/O計(jì)算時(shí)間ms 0 20 50 60 100 120 130 140 170 190 AAABBBCCC 若采用都道方式運(yùn)行三道程序，因系統(tǒng)按照A，B，C的優(yōu)先次序執(zhí)行， 則在運(yùn)行過程中，無論使用CPU還是I/O設(shè)備，A的優(yōu)先級(jí)最高，B的優(yōu)先級(jí)次之，C的優(yōu)先級(jí)最低，即程序A先執(zhí)行20MS的計(jì)算，再完成30MS的I/O操作（與此同時(shí)，程序B進(jìn)行30MS的計(jì)算），最后在進(jìn)行10MS的計(jì)算（此時(shí)程序B等待，因還繼續(xù)10MS計(jì)算）：接下來程 序B先執(zhí)行10MS的計(jì)算，再完成20MS的I/O操作（與此同時(shí)，程序C進(jìn)行10MS的計(jì)算，然后等待

10、I/O的設(shè)備），最后在進(jìn)行10MS的計(jì)算（此時(shí)程序C執(zhí)行I/O操作10MS）。然后程序C先執(zhí)行20MS的I/O操作，最后在進(jìn)行20MS的計(jì)算。至此，三到程序全部運(yùn)行完畢，其程序運(yùn)行的時(shí)間關(guān)系如圖1-2所示 總的運(yùn)行時(shí)間為 20+30+ 10+ 10+ 20+ 10+ 10+ 20+ 30=140ms CCBBBAAAI/O計(jì)算CB時(shí)間ms 0 20 50 60 70 80 90 100 120 140 7 在南京大學(xué)和天津大學(xué)的之間有一條彎曲的小路，其中從S到T一段路每次只允許一輛自行車通過，但中間有一個(gè)小的安全島M（同時(shí)允許兩輛自行車停留），可供兩輛自行車在以從兩端進(jìn)入小路情況下錯(cuò)車使用，如

11、下圖所示，試設(shè)計(jì)一個(gè)算法，使來往的自行車輛均靠順利通過。M南開大學(xué)天津大學(xué)SKLT解答：對(duì)于這一類問題，關(guān)鍵在于正確分析所需控制的對(duì)象、工作流程以及控制關(guān)系。在這一問題中，根據(jù)從S到T路段的特點(diǎn)，可以把它分為3個(gè)小段：從S到K，駛進(jìn)安全島M，從L到T。路段S到K及L到T，只允許一輛自行車通過（即一個(gè)進(jìn)程使用），而安全島M允許兩輛自行車通過（即兩個(gè)進(jìn)程使用）。對(duì)它們分別用3個(gè)信號(hào)量來管理。再注意到同時(shí)最多只能由一個(gè)方向的一輛自行車通過，因此每個(gè)方向的自行車還要用一個(gè)信號(hào)量來控制。用bikeT_to_N和bikeN _to_T分別表示從天津大學(xué)到南開大學(xué)和從南開大學(xué)到天津大學(xué)兩個(gè)方向的自行車?？刂?/p>

12、流程如下：Begin Integer: N _to_T, T_to_N,L,M,K; N _to_T:=1; T_to_N:=1;L:=1;M:=2;K:=1; Procedure bikeT_to_N()Begin P(T_to_N); P(L); Go through T to L; P(M)； Go into M； V(L); P(K); Go through K to S; V(M); V(K); V(T_to_N);End;Procedure bikeN_to_T()Begin P(N_to_T); P(K); Go through S to K; P(M)； Go into M；

13、V(K); P(L); Go through L to T; V(M); V(L); V(N_to_T);End;End;8例：在銀行家算法中，若出現(xiàn)表2-4所示的資源分配情況，試問：1 該狀態(tài)是否安全？2 如果進(jìn)程P2提出請(qǐng)求Request2(1,2,2,2)后，系統(tǒng)能否將資源分配給它。表2-4 資源分配表資源情況進(jìn)程AllocationNeedAvailableA B C DA B C DA B C DP00 0 3 20 0 1 21 6 2 2P11 0 0 01 7 5 0P21 3 5 42 3 5 6P30 3 3 20 6 5 2P40 0 1 40 6 5 6解答：（1）利用

14、銀行家算法對(duì)此時(shí)刻的資源分配情況進(jìn)行分析，可得表2-5所示的安全性分析情況。表2-5 安全性檢查表資源情況進(jìn)程WorkNeedAllocationWork+AllocationFinishA B C DA B C DA B C DA B C DP01 6 2 20 0 1 20 0 3 21 6 5 4truetruetruetruetrueP31 6 5 40 6 5 20 3 3 21 9 8 6P41 9 8 61 7 5 00 0 1 41 9 9 10P11 9 9 100 6 5 61 0 0 02 9 9 10P22 9 9 102 3 5 61 3 5 43 12 14 14從

15、以上情況分析可以看出，此時(shí)存在一個(gè)安全序列p0,p3,p4,p1,p2,故該狀態(tài)是安全的。（2）P2提出請(qǐng)求Request2(1,2,2,2)。按銀行家算法進(jìn)行檢查：Request2(1,2,2,2)<=need(2,3,5,6)Request2(1,2,2,2)<=available(1,6,2,2)試分配并修改相應(yīng)數(shù)據(jù)結(jié)構(gòu)，資源分配情況如表2-6所示。表2-6 P2申請(qǐng)資源后的資源分配表資源情況進(jìn)程AllocationNeedAvailableA B C DA B C DA B C DP00 0 3 20 0 1 20 4 0 0P11 0 0 01 7 5 0P21 3 5

16、41 1 3 4P30 3 3 20 6 5 2P40 0 1 40 6 5 6再利用安全性檢查算法檢查系統(tǒng)是否安全，可用資源available(0,4,0,0)已不能滿足任何進(jìn)程的需要，此時(shí)系統(tǒng)不能將資源分配給P2。9有橋如圖2-7所示。北南橋車流如箭頭所示，橋上不允許兩車交會(huì)，但允許同方向多輛車依次通行（即橋上可以有多個(gè)同方向的車）。用P、V操作實(shí)現(xiàn)交通管理以防止橋上阻塞。解答：由于橋上不允許兩車相會(huì)，故橋應(yīng)該互斥訪問，而同一方向上允許多輛車一次通過，即臨界區(qū)允許多個(gè)實(shí)例訪問。用同一信號(hào)量來互斥訪問臨界區(qū)。由于不能允許某一方向的車完全“控制橋”，應(yīng)保證最多某一方向上連續(xù)通過一定數(shù)量的車后，

17、必須讓另一方向的車通過，可以通過3個(gè)信號(hào)量來控制。具體程序如下： Begin Integer:mutex,availn,abails; Mutes:=0;avialn:=m;avails:=m; Cobegin South: begin P(avails); P(mutex); 過橋； V(mutex); V(avails); End; North: begin P(availn); P(mutex); 過橋； V(mutex); V(availn); End;Coend;End;10 設(shè)系統(tǒng)中有三類資源A、B和C，又設(shè)系統(tǒng)中有5個(gè)進(jìn)程P1，P2，P3，P4和P5.在T0時(shí)刻系統(tǒng)狀態(tài)如下：最大

18、需求量已分配資源量剩余資源量A B CA B CA B C P1 8 6 41 2 12 1 1 P2 4 3 33 1 1 P3 10 1 34 1 3 P4 3 3 33 2 2 P5 5 4 61 1 3(1) 系統(tǒng)是否處于安全狀態(tài)？如是，則給出進(jìn)程安全序列.(2) 如果進(jìn)程P5申請(qǐng)1個(gè)資源類A、1個(gè)資源類B和1個(gè)資源類C，能否實(shí)施分配？為什么？答案：（1） 最大需求量已分配資源量剩余資源量 尚需要量A B CA B CA B C A B C P1 8 6 41 2 12 1 1 7 4 3 P2 4 3 33 1 1 1 2 2 P3 10 1 34 1 3 6 0 0 P4 3 3

19、33 2 2 0 1 1 P5 5 4 61 1 3 4 3 3 系統(tǒng)是處于安全狀態(tài)，安全序列為：P4，P2，P1，P3，P5 （2）P5申請(qǐng)（1，1，1） 最大需求量已分配資源量剩余資源量 尚需要量 A B CA B CA B C A B C P1 8 6 41 2 11 0 0 7 4 3 P2 4 3 33 1 1 1 2 2 P3 10 1 34 1 3 6 0 0 P4 3 3 33 2 2 0 1 1 P5 5 4 62 2 4 3 2 2 不能實(shí)施分配，因?yàn)榉峙浜笳也坏桨踩蛄?，系統(tǒng)將處于不安全狀態(tài).31 有三個(gè)進(jìn)程PA，PB和PC 合作解決文件打印問題：PA將文件記錄從磁盤讀入

20、主存的緩沖區(qū)1，每執(zhí)行一次讀一個(gè)記錄 ；PB將緩沖區(qū)1的內(nèi)容復(fù)制到緩沖區(qū)2，每執(zhí)行一次復(fù)制一個(gè)記錄；PC將緩沖區(qū)2的內(nèi)容打印出來，每執(zhí)行一次打印一個(gè)記錄。緩沖區(qū)的大小等于一個(gè)記錄大小。請(qǐng)用P，V操作來保證文件的正確打印。 解答：在本題中，進(jìn)程PA，PB和PC之間的 關(guān)系為：PA 與PB共用一個(gè)單緩沖區(qū)，而PB又 與PC共用一個(gè)單緩沖區(qū)，其合作方式可用圖2-10表示，當(dāng)緩沖區(qū)1為空時(shí)，進(jìn)程PA可將一個(gè)記錄讀入其中；若緩沖區(qū)1中有一個(gè)數(shù)據(jù)且緩沖區(qū)2為空，則進(jìn)程PB可將記錄從緩沖區(qū)1復(fù)制到緩沖區(qū)2中；若緩沖區(qū)2中有數(shù)據(jù)，則進(jìn)程PC 可以打印記錄，在其他條件下，相應(yīng)進(jìn)程必須等待。事實(shí)上，這是一個(gè)生產(chǎn)者

21、消費(fèi)者的問題打印緩沖區(qū)1緩沖區(qū)2PA從磁盤讀入PBPC復(fù)制 圖2-10 進(jìn)程間的合作方式為遵循這一同步規(guī)則。應(yīng)設(shè)置四個(gè)信號(hào)量 empty1，empty2，full1，full2，信號(hào)量 empty1及empty2分別表示緩沖區(qū)1及緩沖區(qū)2是否為空，其初值為1；信號(hào)量full1，full2分別表示緩沖區(qū)1及緩沖區(qū)2是否有記錄可供處理，其初值為0。其同步描述如下： int empty1=1； int empty2=1； int full1=0; int full2=0;main ( ) cobegin PA( ); PB( ); PC( ); coend PA( ) while( 1 ) 從磁盤讀

22、一個(gè)記錄; P (empty1）; 將記錄存入緩沖區(qū)1； V(full1); PB( ) while(1) P(full1）; 從緩沖區(qū)1中取出記錄; V(empty1); P (empty2); 將記錄存入緩沖區(qū)2； V(full2); PC( ) while(1) P(full2); 從緩沖區(qū)2中取出記錄; V(empty2); 打印記錄; 本題也是一個(gè) 典型生產(chǎn)者消費(fèi)者的問題，其中的難點(diǎn)在于PB既是一個(gè)生產(chǎn)者又是一個(gè)消費(fèi)者。11有一個(gè)虛擬存儲(chǔ)系統(tǒng), 每個(gè)進(jìn)程在內(nèi)存占有3頁數(shù)據(jù)區(qū)、1頁程序區(qū). 剛開始時(shí)數(shù)據(jù)區(qū)為空. 有以下訪頁序列: 1、5、4、1、2、3、2、1、5、4、2、4、6、5、

23、1 試給出下列情形下的缺頁次數(shù): (1)系統(tǒng)采用先進(jìn)先出(FIFO)淘汰算法. (2)系統(tǒng)采用最近最少使用(LRU)淘汰算法. 12有個(gè)一虛擬存儲(chǔ)系統(tǒng), 每個(gè)進(jìn)程在內(nèi)存占有3頁數(shù)據(jù)區(qū), 剛開始時(shí)數(shù)據(jù)區(qū)為 空. 有以下訪頁序列: 2、3、4、5、3、4、1、2、3、5、1、4、2、4、5、1、3、2、1、3 試給出下列情形下的缺頁次數(shù): (1) 系統(tǒng)采用先進(jìn)先出(FIFO)淘汰算法.(2) 系統(tǒng)采用最近最少使用(LRU)淘汰算法.用PV操作解決讀者寫者問題的正確程序如下： begin S, Sr: Semaphore; rc: integer;     &

24、#160; S:=1; Sr:=1; rc:=0; cobegin PROCESS Reader i ( i=1,2)         begin P(Sr)         rc:=rc+1;         if rc=1 then P(S);         V(Sr);    &#

25、160;    read file;         P(Sr);         rc:=rc-1       if rc=0 thenV(S);       V(Sr);       end ;     PROCESS Writer j (j=1

26、,2)     begin P(S);           Write file;           V(S)     end;   coend ; end; 請(qǐng)回答：（1）信號(hào)量 Sr的作用；（2）程序中什么語句用于讀寫互斥，寫寫互斥；（3）若規(guī)定僅允許5個(gè)進(jìn)程同時(shí)讀怎樣修改程序？答：（1）Sr用于讀者計(jì)數(shù)rc的互斥信號(hào)量； （2）if rc=

27、1 then P（S）中的P（S）用于讀寫互斥，寫者進(jìn)程中的P（S）用于寫寫互斥，讀寫互斥。（3）程序中增加一個(gè)信號(hào)量S5，初值為5，P（S5）語句加在讀者進(jìn)程P（Sr）之前，V（S5）語句加在讀者進(jìn)程第2個(gè)V（Sr）之后。  2考慮一個(gè)由8個(gè)頁面、每頁有1024個(gè)字節(jié)組成的邏輯空間，把它裝入到有32個(gè)物理塊的存儲(chǔ)器中，問：(1)邏輯地址需要多少二進(jìn)制位表示?(2)物理地址需要多少二進(jìn)制位表示?  因?yàn)轫撁鏀?shù)為823，故需要3位二進(jìn)制數(shù)表示。每頁有1024個(gè)字節(jié)，1024210，于是頁內(nèi)地址需要10位二進(jìn)制數(shù)表示。32個(gè)物理塊，需要5位二進(jìn)制數(shù)表示(3225) &

28、#160;  (1)頁的邏輯地址由頁號(hào)和頁內(nèi)地址組成，所以需要3+10=13位二進(jìn)制數(shù)表示。    (2)頁的物理地址由塊號(hào)和頁內(nèi)地址的拼接，所以需要5+10=15位二進(jìn)制數(shù)表示。    1. 某虛擬存儲(chǔ)器的用戶編程空間共32個(gè)頁面，每頁為1KB，內(nèi)存為16KB。假定某時(shí)刻一用戶頁表中已調(diào)入內(nèi)存的頁面的頁號(hào)和物理塊號(hào)的對(duì)照表如下：頁號(hào)物理塊號(hào)051102437    計(jì)算邏輯地址0A5C(H)所對(duì)應(yīng)的物理地址（要求寫出分析過程）。1解：頁式存儲(chǔ)管理的邏輯地址分為兩部分：頁號(hào)和頁內(nèi)地址。由已知條件

29、“用戶編程空間共32個(gè)頁面”，可知頁號(hào)部分占5位；由“每頁為1KB”，1K=210，可知內(nèi)頁地址占10位。由“內(nèi)存為16KB”，可知有16塊，塊號(hào)為4位。邏輯地址0A5C（H）所對(duì)應(yīng)的二進(jìn)制表示形式是：000 1010 0101 1100，根據(jù)上面的分析，下劃線部分為頁內(nèi)地址，編碼“000 10”為頁號(hào)，表示該邏輯地址對(duì)應(yīng)的頁號(hào)為2。查頁表，得到物理塊號(hào)是4（十進(jìn)制），即物理塊地址為：01 00，拼接塊內(nèi)地址10 0101 1100，得01 0010 0101 1100，即125C（H）。2.       假設(shè)一個(gè)磁盤有200個(gè)磁道，

30、編號(hào)從0199。當(dāng)前磁頭正在143道上服務(wù)，并且剛剛完成了125道的請(qǐng)求。如果尋道請(qǐng)求隊(duì)列的順序是：86, 147, 91, 177, 94, 150, 102, 175, 130問：為完成上述請(qǐng)求，使用最短尋道時(shí)間優(yōu)先磁盤調(diào)度算法SSTF時(shí)，磁頭移動(dòng)的總量是多少？（要求寫出分析過程）采用最短尋道時(shí)間優(yōu)先磁盤調(diào)度算法SSTF，進(jìn)行調(diào)度的情況為：從143道開始下一磁道移動(dòng)磁道數(shù)147150130102949186175177432028835892磁頭移動(dòng)總量為162。一、 設(shè)某文件的物理存儲(chǔ)方式采用鏈接方式，該文件由5個(gè)邏輯記錄組成，每個(gè)邏輯記錄的大小與磁盤塊大小相等，均為512字節(jié)，并依次存

31、放在50、121、75、80、63號(hào)磁盤塊上。（10分）l 文件的第1569邏輯字節(jié)的信息存放在哪一個(gè)磁盤塊上？l 要訪問第1569邏輯字節(jié)的信息，需要訪問多少個(gè)磁盤塊？（假如該文件的FCB在內(nèi)存）答：因?yàn)椋?569=512×3+33所以要訪問字節(jié)的邏輯記錄號(hào)為3，對(duì)應(yīng)的物理磁盤塊號(hào)為80。故應(yīng)訪問第80號(hào)磁盤塊。 由于采用鏈接方式，所以要訪問第3個(gè)邏輯記錄的信息，必須訪問邏輯記錄第0、1、2后，才能訪問第3個(gè)邏輯記錄，所以要訪問第1569邏輯字節(jié)的信息，需要訪問4個(gè)磁盤塊。37.當(dāng)磁頭處于100號(hào)磁道時(shí)，有9個(gè)進(jìn)程先后提出讀寫請(qǐng)求涉及的柱面號(hào)為63、57、34、88、91、103、

32、76、18和128。要求：(1)寫出按最短尋找時(shí)間優(yōu)先算法SSTF時(shí)的調(diào)度次序;(2)計(jì)算按SSTF調(diào)度算法時(shí)的平均尋道數(shù)。答： (1)調(diào)度次序：100à103à91à88à76à63à57à34à18à128（2）總移過的道數(shù)為：3+12+3+12+13+6+23+16+110=198平均尋道數(shù)為：198/9=22(道)34. 哲學(xué)家就餐問題是一個(gè)經(jīng)典的進(jìn)程同步問題，該問題中描述有5個(gè)哲學(xué)家，他們的生活方式是交替地進(jìn)行思考和進(jìn)餐。哲學(xué)家們共用一張圓桌，分別坐在周圍的椅子上。在圓桌上有5只碗和5支筷子，平

33、時(shí)哲學(xué)家們進(jìn)行思考，饑餓時(shí)便試圖取用其左、右兩邊的筷子，只有在他拿到兩支筷子時(shí)才能進(jìn)餐。進(jìn)餐完畢，放下筷子繼續(xù)思考。為了解決哲學(xué)家就餐問題，可以用一個(gè)信號(hào)量表示一支筷子，由這5個(gè)信號(hào)量構(gòu)成信號(hào)量數(shù)組:semaphore stick5；所有信號(hào)量初值為1，第1個(gè)哲學(xué)家的活動(dòng)算法可以推述如下：semaphore stick5=1,1,1,1,1;main() cobegin Philosopehr(0); Philosopehr(1);Philosopehr(2);Philosopehr(3);Philosopehr(4); Coend; Philosopehr(int I) While(true

34、) 思考； P(stickI); P(stick(I+1)%5); 進(jìn)餐； v(stickI; v(stick(I+1)%5); 試問上述算法是否會(huì)發(fā)生死鎖？為什么？若會(huì)發(fā)生死鎖，請(qǐng)給出一個(gè)不會(huì)發(fā)生死鎖的哲學(xué)家就餐算法。34答案上述算法可能發(fā)生死鎖。例如，5個(gè)哲學(xué)家?guī)缀跬瑫r(shí)饑餓而各自拿起左邊的筷子時(shí)，使得5支筷子信號(hào)量均為0，當(dāng)他們?cè)噲D去拿右邊筷子時(shí)，都將因無筷子拿而無限期地等待下去。對(duì)于上述算法的死鎖問題有多種解決辦法，這里給出兩種解決方案。方案一：用額外的信號(hào)量mutex(初值為1)來控制對(duì)臨界資源的使用。算法如下：Semaphore mutex=1;Philosopehr(int I)

35、While(true) 思考； P(mutex); P(stickI); P(stick(I+1)%5); 進(jìn)餐； v(stickI; v(stick(I+1)%5);改進(jìn)的算法實(shí)質(zhì)上是對(duì)資源申請(qǐng)過程進(jìn)行限制，即要求一次申請(qǐng)完所有的資源，也就是在申請(qǐng)兩個(gè)資源的過程中不被其他進(jìn)程打斷。且在系統(tǒng)滿足該進(jìn)程要求之前別的進(jìn)程無法申請(qǐng)資源，因而也就可以避免死鎖。方案二：對(duì)申請(qǐng)資源（筷子）的進(jìn)程（哲學(xué)家）進(jìn)行限制，要求至多允許4個(gè)哲學(xué)家同時(shí)進(jìn)餐，以保證至少有一個(gè)哲學(xué)家能夠拿到兩支筷子進(jìn)餐，最后總會(huì)進(jìn)餐完畢并釋放他占有的兩支筷子，以使其他哲學(xué)家可以進(jìn)餐。算法如下： Semaphore s=4; /用于控制同

36、時(shí)進(jìn)餐的人數(shù)Philosopehr(int I) While(true) 思考； P(s); P(stickI); P(stick(I+1)%5); 進(jìn)餐； v(stickI; v(stick(I+1)%5); v(s);16. 在一個(gè)系統(tǒng)中采用分頁存儲(chǔ)管理，頁的大小為4KB，允許用戶進(jìn)程的存儲(chǔ)映像最大為16頁，物理內(nèi)存共有512內(nèi)存塊，試問：虛擬地址寄存器和內(nèi)存地址寄存器的長度各是多少位？ 答：（1）頁的大小為4KB=212B,頁面數(shù)為16=24，所以虛擬地址寄存器需要12+4=16位。（2）頁的大小為4KB=212B,物理塊數(shù)為512=29，所以內(nèi)存地址寄存器需要12+9=21位。17.

37、考慮一個(gè)由8個(gè)頁面、每頁1024字節(jié)組成的存儲(chǔ)空間，把它映射到容量為32個(gè)物理塊的存儲(chǔ)器中，試問邏輯地址和物理地址分別是多少位？為什么？ 答：因?yàn)槊宽摯笮?024字節(jié)，故頁內(nèi)地址需要10個(gè)二進(jìn)制位描述；作業(yè)的邏輯地址有8頁，頁號(hào)需要3個(gè)二進(jìn)制位。由此可知，物理地址共需要15位。因?yàn)槊總€(gè)物理塊與頁大小相同，即大小為1024字節(jié)，故塊內(nèi)地址需要10個(gè)二進(jìn)制位描述；內(nèi)存空間容量為32塊，塊號(hào)需要個(gè)二進(jìn)制位。由此可知，物理地址共需要15位。18. 假定某頁式存儲(chǔ)器管理系統(tǒng)中，主存為128KB，分為32塊，塊號(hào)為0、1、2、3、.、31；某作業(yè)有5塊，其頁號(hào)為0、1、2、3、4，被分別裝入主存的3、8、4、6、9塊中。有一邏輯地址為3,70。試求出相應(yīng)的物理地址（其中方括號(hào)中的第一個(gè)元素為頁號(hào)，第二個(gè)元素為頁內(nèi)地址，按十進(jìn)制計(jì)算），并畫圖說明地址變換過程。答：由已知可得，塊大小為128KB/32=4KB,因?yàn)閴K與頁面大小相同，因此每頁大小為4KB。再由題目可知，第3頁被裝入到主存第6塊中，故邏輯地址3,70對(duì)應(yīng)的物理地址為：4KB*6+70=24646。其地