考研全真試題分類解析(答案)

1、操作系統(tǒng)碩士研究生入學(xué)考試全真試題分類解析一、 與時(shí)間有關(guān)錯(cuò)誤類二、 進(jìn)程管理及調(diào)度類三、 同步和互斥類四、 死鎖問題類五、 存儲(chǔ)管理類六、 文件管理類七、 設(shè)備管理類一、 與時(shí)間有關(guān)錯(cuò)誤類北航2001與時(shí)間有關(guān)錯(cuò)題有兩個(gè)優(yōu)先級(jí)相同的進(jìn)程P1和P2，各自執(zhí)行的操作如下，信號(hào)量S1和S2初值均為0。試問P1、P2并發(fā)執(zhí)行后，x、y、z的值各為多少？P1： P2：begin begin y:=1; x:=1; y:=y+2; x:=x+1; V(S1); P(S1); z:=y+1; x:=x+y; P(S2); V(S2); y:=z+y z:=z+x; end. end.答：現(xiàn)對(duì)進(jìn)程語(yǔ)句進(jìn)行編

2、號(hào)，以方便描述。P1： P2：begin begin y:=1; x:=1; y:=y+2; x:=x+1; V(S1); P(S1); z:=y+1; x:=x+y; P(S2); V(S2); y:=z+y z:=z+x; end. end.、和是不相交語(yǔ)句，可以任何次序交錯(cuò)執(zhí)行，而結(jié)果是唯一的。接著無(wú)論系統(tǒng)如何調(diào)度進(jìn)程并發(fā)執(zhí)行，當(dāng)執(zhí)行到語(yǔ)句時(shí)，可以得到x=5，y=3。按Bernstein條件，語(yǔ)句的執(zhí)行結(jié)果不受語(yǔ)句的影響，故語(yǔ)句執(zhí)行后得到z=4。最后，語(yǔ)句和并發(fā)執(zhí)行，最后結(jié)果為：語(yǔ)句先執(zhí)行，再執(zhí)行：x=5，y=7，z=9。語(yǔ)句先執(zhí)行，再執(zhí)行：x=5 ，y=12，z=9。華中科技大2000

3、、國(guó)防科大1999與時(shí)間有關(guān)錯(cuò)題進(jìn)程P0，P1共享變量flag和turn。若flag和turn單元內(nèi)容的修改和訪問是互斥的，它們?nèi)缦逻M(jìn)入臨界區(qū)：var flag:array01 of Boolean; turn:01;flag0:=flag1:=false;turn:=0;process i (i=0 or 1) while truedo begin flagi:=true; . while turni . do begin while flagj=false do skip; turn:=i . end; 臨界區(qū); flagi:=false; 出臨界區(qū); end.該算法能正確實(shí)現(xiàn)互斥嗎?應(yīng)如

4、何修改?解：不能。若P0執(zhí)行到，flag0:=true;這時(shí)P0被打斷，P1開始執(zhí)行，首先執(zhí)行.，使得flag1的值為true。接著執(zhí)行，由于turn的初值為0，故進(jìn)入內(nèi)循環(huán)時(shí)turn置為1。這時(shí)調(diào)度轉(zhuǎn)向P0，P0也進(jìn)入內(nèi)循環(huán)，由于flag1的值己為true，故P0再次把turn值置為0。重復(fù)上述兩個(gè)操作，沒有進(jìn)程能進(jìn)臨界區(qū)。修改算法如下：var flag:array01 of Boolean; turn:01;flag0:=flag1:=false;turn:=0 or 1;process 0 while truedo begin flag0:=true; turn:=1; while fl

5、ag1 and turn=1 do skip; 臨界區(qū); flag0:=false; 出臨界區(qū); end;process 1 while truedo begin flag1:=true; turn:=0; while flag0 and turn=0 do skip; 臨界區(qū); flag1:=false; 出臨界區(qū); end;此算法能保證互斥，討論：1 沒有進(jìn)程在臨界區(qū)，顯然，任一進(jìn)程能進(jìn)入。 2 有一個(gè)進(jìn)程己在臨界區(qū)，另一個(gè)必將在while flagk and turn=k (k=0 or 1)上做空操作等待進(jìn)入。 3 進(jìn)程交叉執(zhí)行時(shí)，有一個(gè)也必將在while flagk and turn

6、=k (k=0 or 1)上做空操作等待進(jìn)入。復(fù)旦大學(xué)1999、浙江大學(xué)1997與時(shí)間有關(guān)錯(cuò)題下述流程是解決兩進(jìn)程互斥訪問臨界區(qū)問題的一種方法。試從“互斥”(mutual exclusion)、“空閑讓進(jìn)”(progress)、“有限等待”(bounded waiting)等三方面討論它的正確性。如果它是正確的，則證明之；如果它不正確，請(qǐng)說明理由。program attemp; var c1,c2:integer;procedure p1; (/* 對(duì)第一個(gè)進(jìn)程p1 */) beginrepeat Remain Section 1;repeat c1:=1-c2until c20;Critic

7、al Section; (/* 臨界區(qū) */)c1:=1 until false end;procedure p2; (/* 對(duì)另一個(gè)進(jìn)程p2 */) beginrepeat Remain Section 2;repeat c2:=1-c1until c10;Critical Section; (/* 臨界區(qū) */)c2:=1 until false end; begin (/* 主程序 */)c1:=1;c2:=1;cobegin p1;p2 (/* 兩進(jìn)程p1, p2開始執(zhí)行 */)coend end.答：(1)互斥己知c1和c2的初值為1，若進(jìn)程P1執(zhí)行到c1:=1-c2時(shí)，進(jìn)程P2也同

8、時(shí)執(zhí)行c2:=1-c1。這樣一來(lái)，c1和c2的值都變?yōu)?。于是，P1和P2會(huì)同時(shí)進(jìn)入臨界區(qū)，不滿足互斥條件。(2) 有空讓進(jìn)設(shè)開始無(wú)進(jìn)程在臨界區(qū)中，進(jìn)程P1執(zhí)行了c1:=1-c2，由于c2的初值為1，這使得c1的值變?yōu)?但c2仍為1，從而保證了P1進(jìn)入臨界區(qū)。當(dāng)P1退出臨界區(qū)時(shí)，執(zhí)行了c1:=1，使得P2就可進(jìn)入臨界區(qū)。進(jìn)程P2先執(zhí)行的情況相似，能保證有空讓進(jìn)的原則。(3) 有限等待不一定能實(shí)現(xiàn)。假定進(jìn)程P1離開臨界區(qū)，進(jìn)程P2申請(qǐng)進(jìn)入臨界區(qū)，但還未來(lái)得及執(zhí)行c2:=1-c1時(shí)，進(jìn)程P1又再次執(zhí)行c1:=1-c2，搶先進(jìn)入臨界區(qū)。因而，造成饑餓現(xiàn)象。北京大學(xué)1993、國(guó)防科大2001與時(shí)間有關(guān)

9、錯(cuò)舉例說明P，V操作為什么要用原語(yǔ)實(shí)現(xiàn)？操作系統(tǒng)如何實(shí)現(xiàn)這種原語(yǔ)操作？解：信號(hào)量S是P,V均要操作的共享變量，每次它們有對(duì)S的加或減1操作。若不把P,V設(shè)計(jì)成原語(yǔ)，則它們交替在同一信號(hào)量上操作時(shí)會(huì)造成S值不惟一，更為嚴(yán)重的會(huì)造成某些進(jìn)程處于永遠(yuǎn)等待狀態(tài)。例如，若S當(dāng)前值為1，第一個(gè)P操執(zhí)行后，進(jìn)程是不會(huì)阻塞的。但若在第一個(gè)P操作執(zhí)行 if S0 then之前，有另一個(gè)進(jìn)程的P操作搶先執(zhí)行S:=S-1，這時(shí)S=-1，而第一個(gè)執(zhí)行P操作的進(jìn)程被阻塞了。這是不符合P,V原定義的含義的。附：type semaphore=record value:integer; queue: list of proc

10、ess; end procedure P(var s:semaphore); begin s.value:= s.value 1;/* 把信號(hào)量減去1 */ if s.valueT CPU利用率=T/（T+S）下面一種情況，SQT ，也就是說，進(jìn)程完成任務(wù)運(yùn)行過程中共切換了T/Q次，浪費(fèi)時(shí)間為S(T/Q)。故CPU利用率=T/(T+ S(T/Q)，化簡(jiǎn)后得到：3）TQS CPU利用率=Q/（Q+S）南京大學(xué)本課生進(jìn)程管理及調(diào)度習(xí)題有一個(gè)四道作業(yè)的操作系統(tǒng)，若在一段時(shí)間內(nèi)先后到達(dá)6個(gè)作業(yè)，它們的提交和估計(jì)運(yùn)行時(shí)間由下表給出：作業(yè) 提交時(shí)間 估計(jì)運(yùn)行時(shí)間(分鐘) 1 8：00 60 2 8：20

11、35 3 8：25 20 4 8：30 25 5 8：35 5 6 8：40 10 系統(tǒng)采用SJF調(diào)度算法，作業(yè)被調(diào)度進(jìn)入系統(tǒng)后中途不會(huì)退出，但作業(yè)運(yùn)行時(shí)可被更短作業(yè)搶占。(1)分別給出6個(gè)作業(yè)的執(zhí)行時(shí)間序列、即開始執(zhí)行時(shí)間、作業(yè)完成時(shí)間、作業(yè)周轉(zhuǎn)時(shí)間。(2)計(jì)算平均作業(yè)周轉(zhuǎn)時(shí)間。解：作業(yè) 提交 需運(yùn)行 開始運(yùn)行 被搶占還 完成 周轉(zhuǎn)號(hào) 時(shí)間 時(shí)間 時(shí)間 需運(yùn)行時(shí)間 時(shí)間 時(shí)間J1 8:00 60 8:00 40 10:35 155J2 8:20 35 8:20 30 9:55 95J3 8:25 20 8:25 8:45 20 J4 8:30 25 9:00 25 9:25 55 J5 8:

12、35 5 8:45 8:50 15J6 8:40 10 8:50 9:00 20說明:(1) 采用SJF,J2到達(dá)時(shí)搶占J1；J3到達(dá)時(shí)搶占J2。(2) 但J4到達(dá)時(shí)，因不滿足SJF，故J4不能被運(yùn)行，J3繼續(xù)執(zhí)行5分鐘。(3) 注意，是4道的作業(yè)系統(tǒng)，故后面作業(yè)不能進(jìn)入主存而在后備隊(duì)列等待。(4) 根據(jù)進(jìn)程調(diào)度可搶占原則，J3第一個(gè)做完。而這時(shí)J5可進(jìn)入主存。(5) 因J5最短，故它第二個(gè)完成。這時(shí)J6可進(jìn)入主存。(6) 因J6最短，故它第三個(gè)完成。(7) 然后是:J4、J2和J1(8) T=608:00 8:20 8:25 8:30 8:35 8:40 8:45 8:50 9:00 9:2

13、5 9:55 10:35J1J2J3J4J5J6就 緒 隊(duì) 列就 緒 隊(duì) 列就 緒 隊(duì) 列后備隊(duì)列后備隊(duì)列CPUCPUCPUCPUCPUCPUCPUCPU三、 同步和互斥類 求解同步互斥問題的一些規(guī)律：(1) 進(jìn)程同步問題中，管理共享資源常常設(shè)兩個(gè)信號(hào)量，而進(jìn)程互斥問題中僅需設(shè)立一個(gè)信號(hào)量。(2) P、V操作要成對(duì)調(diào)用，在進(jìn)程互斥中是針對(duì)同一個(gè)信號(hào)量進(jìn)行。而在進(jìn)程同步問題中，進(jìn)入臨界區(qū)前后P、V操作是針對(duì)不同的信號(hào)量的(3) 至少有一個(gè)信號(hào)量初值大于等于1(一般指管理共享資源的信號(hào)量)，否則進(jìn)程無(wú)法被啟動(dòng)運(yùn)行。(4) 若有多個(gè)(k)共享資源，則某信號(hào)量初值可設(shè)為k。北京大學(xué)1991年同步與互斥

14、題有一個(gè)倉(cāng)庫(kù)，可以存放A和B兩種產(chǎn)品，但要求： （1）每次只能存入一種產(chǎn)品（A或B）； （2）NA產(chǎn)品數(shù)量-B產(chǎn)品數(shù)量M。其中，N和M是正整數(shù)。試用P、V操作描述產(chǎn)品A與產(chǎn)品B的入庫(kù)過程。 分析及相關(guān)知識(shí)本題給出的第一個(gè)條件是臨界資源的訪問控制，可用一個(gè)互斥信號(hào)量解決該問題。第二個(gè)條件可以分解為： NA產(chǎn)品數(shù)量B產(chǎn)品數(shù)量 A產(chǎn)品數(shù)量B產(chǎn)品數(shù)量M也就是說，A產(chǎn)品的數(shù)量不能比B產(chǎn)品的數(shù)量少N個(gè)以上，A產(chǎn)品的數(shù)量不能比B產(chǎn)品的數(shù)量多M個(gè)以上。解：在本題中，可以設(shè)置兩個(gè)信號(hào)量來(lái)控制A、B產(chǎn)品的存放數(shù)量，sa表示當(dāng)前允許A產(chǎn)品比B產(chǎn)品多入庫(kù)的數(shù)量，即在當(dāng)前庫(kù)存量和B產(chǎn)品不入庫(kù)的情況下，還可以允許sa個(gè)A

15、產(chǎn)品入庫(kù)；sb表示當(dāng)前允許B產(chǎn)品比A產(chǎn)品多入庫(kù)的數(shù)量，即在當(dāng)前庫(kù)存量和A產(chǎn)品不入庫(kù)的情況下，還可以允許sb個(gè)B產(chǎn)品入庫(kù)。初始時(shí)，sa為M1，sb為N1。當(dāng)往庫(kù)中存放入一個(gè)A產(chǎn)品時(shí)，則允許存入B產(chǎn)品的數(shù)量也增加1；當(dāng)往庫(kù)中存放入一個(gè)B產(chǎn)品時(shí)，則允許存入A產(chǎn)品的數(shù)量也增加1。var mutex：semaphore=1;/*互斥信號(hào)量*/ sa，sb：semaphore； sa=M-1; sb=N-1;mian( ) while (1) 取一個(gè)產(chǎn)品； if(取的是A產(chǎn)品) P(sa); P(mutex); 將A產(chǎn)品入庫(kù)； V(mutex); V(sb); else /*取的產(chǎn)品是B*/ P(sb);

16、 P(mutex); 將B產(chǎn)品入庫(kù)； V(mutex); V(sa); 北京大學(xué)1994年同步與互斥題進(jìn)程A1，A2，An1通過m個(gè)緩沖區(qū)向進(jìn)程B1，B2，Bn2不斷地發(fā)送消息。發(fā)送和接收工作遵循如下規(guī)則：每個(gè)發(fā)送進(jìn)程一次發(fā)送一個(gè)消息，寫入一個(gè)緩沖區(qū)，緩沖區(qū)大小等于消息長(zhǎng)度；對(duì)每一個(gè)消息，B1，B2，Bn2 都須各接收一次，讀入各自的數(shù)據(jù)區(qū)內(nèi)；m個(gè)緩沖區(qū)都滿時(shí)，發(fā)送進(jìn)程等待；沒有可讀的消息時(shí)，接收進(jìn)程等待。試用P、V操作組織正確的發(fā)送和接收工作。 分析及相關(guān)知識(shí)本題是生產(chǎn)者消費(fèi)者問題的一個(gè)變形，一組生產(chǎn)者A1，A2，An1和一組消費(fèi)者B1，B2，Bn2共用m個(gè)緩沖區(qū)，每個(gè)緩沖區(qū)只要寫一次，但需

17、要讀n2次。因此，可以把這一組緩沖區(qū)看成n2組緩沖區(qū)，每個(gè)發(fā)送者需要同時(shí)寫n2組緩沖區(qū)中相應(yīng)的n2個(gè)緩沖區(qū)，而每一個(gè)接收者只需讀它自己對(duì)應(yīng)的那組緩沖區(qū)中的對(duì)應(yīng)單元。解：在本題中，應(yīng)設(shè)置一個(gè)信號(hào)量mutex實(shí)現(xiàn)諸進(jìn)程對(duì)緩沖區(qū)的互斥訪問；兩個(gè)信號(hào)量數(shù)組emptyn2和fulln2描述n2組緩沖區(qū)的使用情況。mutex的初始值為1；empty中的元素初值為m；數(shù)組full中的元素初值為0。其同步關(guān)系描述如下：var mutex,emptyn2,fulln2：semaphore;int i;mutex=1;for(i=0;i=n2-1;i+) emptyi=m; fulli=0; main () co

18、begin A1( ); A2( ); An1 () B1 (); B2 (); Bn2( );coend send ( ) /*發(fā)送消息*/ int i;for (i=0;i=n2-1;i+) p(emptyi); p(mutex);將消息放入緩沖區(qū)； V（mutex）;for(i=0;i=n2-1;i+) V(fulli);receive(i) /*進(jìn)程Bi接收消息*/ p(fulli); p(mutex); 將消息從緩沖區(qū)取出； V(mutex); V(emtpyi);Ai ( ) /*因發(fā)送進(jìn)程A1,A2,An1的程序類似，這里只給出進(jìn)程Ai的描述*/while (1) send (

19、); Bi ( ) /*因接收進(jìn)程B1,B2,Bn2的程序類似，這里只給出進(jìn)程Bi描述*/while (1) receive(i); 北大1995年同步與互斥題有一個(gè)倉(cāng)庫(kù)可存放A、B兩種零件，最大庫(kù)容量各為m個(gè)。生產(chǎn)車間不斷地取A和B進(jìn)行裝配，每次各取一個(gè)。為避免零件銹蝕，按先入庫(kù)者先出庫(kù)的原則。有兩組供應(yīng)商分別不斷地供應(yīng)A和B，每次一個(gè)。為保證配套和合理庫(kù)存，當(dāng)某種零件比另一種零件超過n(nm)個(gè)時(shí)，暫停對(duì)數(shù)量大的零件的進(jìn)貨，集中補(bǔ)充數(shù)量少的零件。試用信號(hào)量與P、V操作正確地實(shí)現(xiàn)它們之間的同步關(guān)系。答：按照題意，應(yīng)滿足以下控制關(guān)系：A零件數(shù)量- B零件數(shù)量n；B零件數(shù)量- A零件數(shù)量n；A零

20、件數(shù)量m；B零件數(shù)量m。四個(gè)控制關(guān)系分別用信號(hào)量sa、sb、empty1和empty2實(shí)施。為遵循先入庫(kù)者先出庫(kù)的原則，A、B零件可以組織成兩個(gè)循形隊(duì)列，并增加入庫(kù)指針in1、in2和出庫(kù)指針out1、out2來(lái)控制順序。并發(fā)程序編制如下：var empty1，empty2，full1，full2：semaphore；mutex，sa，sb：semaphore；in1，in2，out1，out2：integer；buffer1，buffer2 ：array 0.m-1 of item； empty1：=empty2：=m； sa：=sb：=n； in1：=in2：=out1：=out2：=0；

21、cobeginprocess producerA repeat P(empty1)； P(sa)； P(mutex)； buffer1in1 ：=A零件； in1：=(in1+1) mod m； V(mutex)； V(sb)； V(full1)； untile false；process producerB repeat P(empty2)； P(sb)； P(mutex)； Buffer2in2 ：=B零件； in2：=(in2+1) mod m； V(mutex)； V(sa)； V(full2)； untile false；process take repeatP(full1)；P(f

22、ull2)；P(mutex)；Take from buffer1out1 and buffer2out2中的A、B零件；out1：=(out1+1) mod m；out2：=(out2+1) mod m；V(mutex)；V(empty1)；V(empty2)；把A和B裝配成產(chǎn)品；until falsecoend.北大1997年同步與互斥題某高校開設(shè)網(wǎng)絡(luò)課程并安排上機(jī)實(shí)習(xí)，如果機(jī)房共有2m臺(tái)機(jī)器，有2n個(gè)學(xué)生選課，規(guī)定：(1)每?jī)蓚€(gè)學(xué)生分成一組，并占用一臺(tái)機(jī)器，協(xié)同完成上機(jī)實(shí)習(xí)；(2)僅當(dāng)一組兩個(gè)學(xué)生到齊，并且機(jī)房機(jī)器有空閑時(shí)，該組學(xué)生才能進(jìn)機(jī)房；(3)上機(jī)實(shí)習(xí)由一名教師檢查，檢查完畢，一組學(xué)

23、生同時(shí)離開機(jī)房。試用信號(hào)量和P、V操作模擬上機(jī)實(shí)習(xí)過程。答1：var mutex,enter:semaphore; mutex:=1;enter:=0; finish,test,rc,computercounter:integer; finish:=test:=rc:=0;computercounter:=2m;cobegin process studenti(i=1，2，)begin P(computercounter); /*申請(qǐng)計(jì)算機(jī) P(mutex); rc:=rc+1; /*學(xué)生互斥計(jì)數(shù) if rc=1 then V(mutex);P(enter); /*若只來(lái)一個(gè)學(xué)生，則在ente

24、r上等待 else rc:=0; V(mutex);V(enter); /*到達(dá)一組中第二個(gè)學(xué)生，rc清0是為下一組計(jì)數(shù)用 學(xué)生進(jìn)入機(jī)房,上機(jī)實(shí)習(xí); V(finish); /*告訴老師，實(shí)習(xí)結(jié)束 P(test); /*等待老師檢查實(shí)習(xí)結(jié)果 V(computercounter); /*歸還計(jì)算機(jī)end process teacherbegin P(finish); /*等第一個(gè)學(xué)生實(shí)習(xí)結(jié)束 P(finish); /*等第二個(gè)學(xué)生實(shí)習(xí)結(jié)束 檢查實(shí)習(xí)結(jié)果; V(test); /*第一個(gè)學(xué)生檢查完成 V(test); /*第二個(gè)學(xué)生檢查完成endcoend.答2：var student,compute

25、r,enter,finish,check:semaphore; student:=enter:=finish:=check:=0;computer:=2m;cobeginprocess student begin V(student); /*有學(xué)生到達(dá) P(computer); /*申請(qǐng)一臺(tái)計(jì)算機(jī) P(enter); /*等待允許進(jìn)入 與同伴上機(jī)實(shí)習(xí); V(finish); /*完成實(shí)習(xí) P(check); /*等教師檢查 V(computer); /*歸還計(jì)算機(jī) end;process teacher begin repeat P(finish); /*等學(xué)生完成 P(finish); /*

26、等學(xué)生伙伴完成 檢查實(shí)習(xí)結(jié)果; V(check); V(ckeck); Until false; end;process monitor begin repeat P(student); /*等學(xué)生到達(dá) P(student); /*等學(xué)生伙伴到達(dá) 檢查實(shí)習(xí)結(jié)果; V(enter); /*允許學(xué)生進(jìn)入 V(enter); /*允許學(xué)生進(jìn)入 Until false; end;coend.南京大學(xué)2000年同步與互斥題桌上有一只盤子，最多可以容納兩個(gè)水果，每次僅能放入或取出一個(gè)水果。爸爸向盤子中放蘋果(apple)，媽媽向盤子中放桔子(orange)，兩個(gè)兒子專等吃盤子中的桔子，兩個(gè)女兒專等吃盤子中的蘋果。試用PV操作或管程來(lái)實(shí)現(xiàn)爸爸、媽媽、兒子、女兒間的同步與互斥關(guān)系。 TYPE FMSD = MONITOR var plate ARRAY0,1 of (apple, orange);