操作系統(tǒng)碩士研究生入學(xué)考試

1、操作系統(tǒng)碩士研究生入學(xué)考試全真試題分類(lèi)解析一、 與時(shí)間有關(guān)錯(cuò)誤類(lèi)二、 進(jìn)程管理及調(diào)度類(lèi)三、 同步和互斥類(lèi)四、 死鎖問(wèn)題類(lèi)五、 存儲(chǔ)管理類(lèi)六、 文件管理類(lèi)七、 設(shè)備管理類(lèi)一、 與時(shí)間有關(guān)錯(cuò)誤類(lèi)北航2001與時(shí)間有關(guān)錯(cuò)題有兩個(gè)優(yōu)先級(jí)相同的進(jìn)程P1和P2，各自執(zhí)行的操作如下，信號(hào)量S1和S2初值均為0。試問(wèn)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)容的修改和訪問(wèn)是互斥的，它們?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開(kāi)始執(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è)操作，沒(méi)有進(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 沒(méi)有進(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)程互斥訪問(wèn)臨界區(qū)問(wèn)題的一種方法。試從“互斥”(mutual exclusion)、“空閑讓進(jìn)”(progress)、“有限等待”(bounded waiting)等三方面討論它的正確性。如果它是正確的，則證明之；如果它不正確，請(qǐng)說(shuō)明理由。program attemp; var c1,c2:integer;procedure p1; (/* 對(duì)第一個(gè)進(jìn)程p1 */) beginrepeat Remain Section 1;repeat c1:=1-c2until c2<>

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

8、c1:=1-c2時(shí)，進(jìn)程P2也同時(shí)執(zhí)行c2:=1-c1。這樣一來(lái)，c1和c2的值都變?yōu)?。于是，P1和P2會(huì)同時(shí)進(jìn)入臨界區(qū)，不滿(mǎn)足互斥條件。(2) 有空讓進(jìn)設(shè)開(kāi)始無(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離開(kāi)臨界區(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é)19

9、93、國(guó)防科大2001與時(shí)間有關(guān)錯(cuò)舉例說(shuō)明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 S<0 then之前，有另一個(gè)進(jìn)程的P操作搶先執(zhí)行S:=S-1，這時(shí)S=-1，而第一個(gè)執(zhí)行P操作的進(jìn)程被阻塞了。這是不符合P,V原定義的含義的。附：type semaphore=record value:integer;

10、 queue: list of process; end procedure P(var s:semaphore); begin s.value:= s.value 1;/* 把信號(hào)量減去1 */ if s.value< 0 then W(s.queue);/* 若信號(hào)量小于0，則執(zhí)行P(s)的進(jìn)程調(diào)用 W(s.queue) 進(jìn)行自我封鎖，被置成等待信號(hào)量s的狀態(tài)，進(jìn)入信 號(hào)量隊(duì)列queue*/ end; procedure V(var s:semaphore); begin s.value:= s.value + 1; /* 把信號(hào)量加1 */if s.value 0 then R(s

11、.queue); /* 若信號(hào)量小于等于0，則調(diào)用R(s.queue) 從信號(hào)量s隊(duì)列queue中釋放一個(gè)等待信號(hào)量s的進(jìn)程并置成就緒態(tài)*/ end;二、 進(jìn)程管理與調(diào)度類(lèi)中山大學(xué)1996進(jìn)程管理題在UNIX系統(tǒng)中運(yùn)行以下程序，最多可產(chǎn)生出多少進(jìn)程?畫(huà)出進(jìn)程家屬樹(shù)。main( ) fork( ); /*pc(程序計(jì)數(shù)器)，進(jìn)程A fork( ); fork( );解：首先采用fork( )創(chuàng)建的子進(jìn)程，其程序是復(fù)制父進(jìn)程的；其次，父、子進(jìn)程都從調(diào)用后的那條語(yǔ)句開(kāi)始執(zhí)行。當(dāng)進(jìn)程A執(zhí)行后，派生出子進(jìn)程B，其程序及狀態(tài)如下：main( ) main( ) fork( ); fork( ); fork

12、( ); /*pc(程序計(jì)數(shù)器)，進(jìn)程A fork( ); /*pc(程序計(jì)數(shù)器)，進(jìn)程Bfork( ); fork( ); 當(dāng)進(jìn)程A、B執(zhí)行后，各派生出子進(jìn)程C、D，其程序及狀態(tài)如下：main( ) main( ) fork( ); fork( ); fork( ); fork( ); fork( ); /*pc(程序計(jì)數(shù)器)，進(jìn)程A fork( ); /*pc(程序計(jì)數(shù)器)，進(jìn)程B main( ) main( ) fork( ); fork( ); fork( ); fork( ); fork( ); /*pc(程序計(jì)數(shù)器)，進(jìn)程C fork( ); /*pc(程序計(jì)數(shù)器)，進(jìn)程D 當(dāng)進(jìn)程

13、A、B、C、D執(zhí)行后，各派生出子進(jìn)程E、F、G、H，且所有進(jìn)程的PC均指向程序結(jié)束處。這時(shí)進(jìn)程A共派生出7個(gè)子進(jìn)程。ABCEDFGH電子科技大學(xué)2001進(jìn)程管理及調(diào)度題如圖，系統(tǒng)進(jìn)程分4類(lèi)排入隊(duì)列，各類(lèi)之間采用優(yōu)先級(jí)調(diào)度，各類(lèi)內(nèi)部采用時(shí)間片輪轉(zhuǎn)調(diào)度。簡(jiǎn)述進(jìn)程P1-P8的調(diào)度過(guò)程。優(yōu)先級(jí)4優(yōu)先級(jí)3優(yōu)先級(jí)2優(yōu)先級(jí)1高低P1P2P3P4P5P6P7P8答：系統(tǒng)首先調(diào)度優(yōu)先級(jí)4隊(duì)列中的進(jìn)程，P1、P2和P3按時(shí)間片輪轉(zhuǎn)依次占用CPU。若某進(jìn)程在時(shí)間片內(nèi)執(zhí)行未結(jié)束，將被排到隊(duì)列末尾，等待下個(gè)時(shí)間片到來(lái)。若P1、P2和P3均運(yùn)行結(jié)束，或均進(jìn)入了等待態(tài)，系統(tǒng)會(huì)調(diào)度優(yōu)先級(jí)3隊(duì)列中的P4、P5執(zhí)行，執(zhí)行過(guò)程同上

14、。若有處等待態(tài)的P1或P2或P3有個(gè)變成就緒態(tài)，則當(dāng)前時(shí)間片耗盡后又回到優(yōu)先級(jí)4執(zhí)行。只有當(dāng)優(yōu)先級(jí)4或優(yōu)先級(jí)3隊(duì)列中進(jìn)程空或全進(jìn)入等待態(tài)時(shí)，才調(diào)度優(yōu)先級(jí)2隊(duì)列中的進(jìn)程P6、P7和P8執(zhí)行，過(guò)程如上不贅。復(fù)旦大學(xué)大學(xué)2002進(jìn)程管理及調(diào)度題對(duì)基本的進(jìn)程狀態(tài)轉(zhuǎn)換圖中的狀態(tài)轉(zhuǎn)換編號(hào)1，2，3和4。令i和j取值1，2，3和4（ji）。請(qǐng)分別討論在狀態(tài)轉(zhuǎn)換i和狀態(tài)轉(zhuǎn)換j之間是否存在因果關(guān)系：若存在，請(qǐng)指出這種關(guān)系是必然的，或是有條件的，條件是什么？ 運(yùn)行就緒阻塞1423解：12 存在因果關(guān)系。時(shí)間片到。 13 不存在。 14 不存在。 21 不存在。 23 不存在。 24 不存在。 31 不存在。 32

15、 存在。僅當(dāng)發(fā)生在優(yōu)先權(quán)剝奪式調(diào)度算法中。 34 不存在。 41 不存在。 42 存在。運(yùn)行進(jìn)程等待必引起另一進(jìn)程被調(diào)度。43 不存在。南京大學(xué)1999進(jìn)程調(diào)度題在單CPU和兩臺(tái)I/O(I1,I2)設(shè)備的多道程序設(shè)計(jì)環(huán)境下，同時(shí)投入三個(gè)作業(yè)運(yùn)行。它們的執(zhí)行軌跡如下：Job1：I2(30ms)、CPU(10ms)、I1(30ms)、CPU(10ms)Job2：I1(20ms)、CPU(20ms)、I2(40ms)Job3：CPU(30ms)、I1(20ms)如果CPU、I1和I2都能并行工作，優(yōu)先級(jí)從高到低為Job1、Job2和Job3，優(yōu)先級(jí)高的作業(yè)可以搶占優(yōu)先級(jí)低的作業(yè)的CPU，但不搶占I1

16、和I2。試求：(1)每個(gè)作業(yè)從投入到完成分別所需的時(shí)間。(2) 從投入到完成CPU的利用率。(3)I/O設(shè)備利用率。答：畫(huà)出三個(gè)作業(yè)并行工作圖如下(圖中著色部分為作業(yè)等待時(shí)間)：CPUI1I2Job1Job2Job3時(shí)間(ms)CPU CPU0 10 20 30 40 50 60 70 80 90 I1 I1CPUCPU I2 I2CPU I1CPU Job1 Job2 Job3Job2Job1Job2Job3Job1 Job2 Job1Job3(1) Job1從投入到運(yùn)行完成需80ms，Job2從投入到運(yùn)行完成需90ms，Job3從投入到運(yùn)行完成需90ms。(2) CPU使用時(shí)間為10+10

17、+10+10+20+10=70。所以CPU利用率為70/90=77.8%。(3) 設(shè)備I1空閑時(shí)間段為：20ms至40ms，故I1的利用率為70/90=77.8%。設(shè)備I2空閑時(shí)間段為：30ms至50ms，故I2的利用率為70/90=77.8%。東南大學(xué)1996進(jìn)程調(diào)度題某多道程序設(shè)計(jì)系統(tǒng)供用戶(hù)使用的主存為100K，磁帶機(jī)2臺(tái)，打印機(jī)1臺(tái)。采用可變分區(qū)內(nèi)存管理，采用靜態(tài)方式分配外圍設(shè)備，忽略用戶(hù)作業(yè)I/O時(shí)間?，F(xiàn)有作業(yè)序列如下：作業(yè)號(hào) 進(jìn)入輸入井時(shí)間 運(yùn)行時(shí)間 主存需求量 磁帶需求 打印機(jī)需求 1 8:00 25分鐘 15K 1 1 2 8:20 10分鐘 30K 0 1 3 8:20 20分

18、鐘 60K 1 0 4 8:30 20分鐘 20K 1 0 5 8:35 15分鐘 10K 1 1 作業(yè)調(diào)度采用FCFS策略，優(yōu)先分配主存低地址區(qū)且不準(zhǔn)移動(dòng)已在主存的作業(yè)，在主存中的各作業(yè)平分CPU時(shí)間。現(xiàn)求：(1)作業(yè)被調(diào)度的先后次序?(2)全部作業(yè)運(yùn)行結(jié)束的時(shí)間?(3)作業(yè)平均周轉(zhuǎn)時(shí)間為多少?(4)最大作業(yè)周轉(zhuǎn)時(shí)間為多少?答：(1)作業(yè)調(diào)度選擇的作業(yè)次序?yàn)椋鹤鳂I(yè)1、作業(yè)3、作業(yè)4、作業(yè)2和作業(yè)5。 (2)全部作業(yè)運(yùn)行結(jié)束的時(shí)間9:30。 (3)周轉(zhuǎn)時(shí)間：作業(yè)1為30分鐘、作業(yè)2為55分鐘、作業(yè)3為40分鐘、作業(yè)4為40分鐘和作業(yè)5為55分鐘。 (4)平均作業(yè)周轉(zhuǎn)時(shí)間=44分鐘。 (5) )

19、最大作業(yè)周轉(zhuǎn)時(shí)間為55分鐘。分析：本題綜合測(cè)試了作業(yè)調(diào)度、進(jìn)程調(diào)度、及對(duì)外設(shè)的競(jìng)爭(zhēng)、主存的競(jìng)爭(zhēng)。8:00 作業(yè)1到達(dá)，占有資源并調(diào)入主存運(yùn)行。8:20 作業(yè)2和3同時(shí)到達(dá)，但作業(yè)2因分不到打印機(jī)，只能在后備隊(duì)列等待。作業(yè)3資源滿(mǎn)足，可進(jìn)主存運(yùn)行，并與作業(yè)1平分CPU時(shí)間。8:30 作業(yè)1在8:30結(jié)束，釋放磁帶與打印機(jī)。但作業(yè)2仍不能執(zhí)行，因不能移動(dòng)而沒(méi)有30KB的空閑區(qū)，繼續(xù)等待。作業(yè)4在8:30到達(dá)，并進(jìn)入主存執(zhí)行，與作業(yè)3分享CPU。8:35 作業(yè)5到達(dá)，因分不到磁帶機(jī)/打印機(jī)，只能在后備隊(duì)列等待。9:00 作業(yè)3運(yùn)行結(jié)束，釋放磁帶機(jī)。此時(shí)作業(yè)2的主存及打印機(jī)均可滿(mǎn)足，投入運(yùn)行。作業(yè)5到

20、達(dá)時(shí)間晚，只能等待。9:10 作業(yè)4運(yùn)行結(jié)束，作業(yè)5因分不到打印機(jī)，只能在后備隊(duì)列繼續(xù)等待。9:15 作業(yè)2運(yùn)行結(jié)束，作業(yè)5投入運(yùn)行。作業(yè)1015K100K8:00作業(yè)1作業(yè)3015K75K100K8:20作業(yè)3作業(yè)4015K75K95K100K8:309:30 作業(yè)全部執(zhí)行結(jié)束。作業(yè)2作業(yè)4030K75K95K100K9:00作業(yè)2作業(yè)5030K40K100K9:10作業(yè)5030K40K100K9:15時(shí)間(分) 8:00 8:20 8:30 8:35 9:00 9:10 9:15 9:30作業(yè)1作業(yè)1、3作業(yè)3、4作業(yè)2、4作業(yè)2作業(yè)5作業(yè)1CPU作業(yè)1作業(yè)2作業(yè)5打印機(jī)作業(yè)1作業(yè)4作業(yè)5

21、磁帶機(jī)1作業(yè)3磁帶機(jī)2CPU作業(yè)11/2CPU等待作業(yè)21/2CPUCPU作業(yè)31/2CPU1/2CPU作業(yè)41/2CPU1/2CPU作業(yè)5等待CPU 北京大學(xué)1995年進(jìn)程調(diào)度題有一個(gè)具有兩道作業(yè)的批處理系統(tǒng)，作業(yè)調(diào)度采用短作業(yè)優(yōu)先的調(diào)度算法，進(jìn)程調(diào)度采用以?xún)?yōu)先數(shù)為基礎(chǔ)的搶占式調(diào)度算法，在下表所示的作業(yè)序列，作業(yè)優(yōu)先數(shù)即為進(jìn)程優(yōu)先數(shù)，優(yōu)先數(shù)越小優(yōu)先級(jí)越高。作業(yè)名 到達(dá)時(shí)間 估計(jì)運(yùn)行時(shí)間 優(yōu)先數(shù)A 10：00 40分 5B 10：20 30分 3C 10：30 50分 4D 10：50 20分 6 (1)列出所有作業(yè)進(jìn)入內(nèi)存時(shí)間及結(jié)束時(shí)間。 (2)計(jì)算平均周轉(zhuǎn)時(shí)間。分析：每個(gè)作業(yè)的運(yùn)行將經(jīng)歷兩

22、級(jí)調(diào)度：作業(yè)調(diào)度和進(jìn)程調(diào)度。作業(yè)調(diào)度采用短作業(yè)優(yōu)先調(diào)度算法，進(jìn)程調(diào)度采用基于優(yōu)先數(shù)的搶占式調(diào)度算法，高優(yōu)先級(jí)的進(jìn)程可以搶占系統(tǒng)處理機(jī)。只有當(dāng)作業(yè)調(diào)度程序?qū)⒆鳂I(yè)裝入內(nèi)存后，方能參與進(jìn)程調(diào)度。本題中的批處理系統(tǒng)是兩道作業(yè)系統(tǒng)，因此每次只能有兩道作業(yè)進(jìn)入系統(tǒng)內(nèi)存。本題中的作業(yè)和進(jìn)程推進(jìn)順序如下： 10：00時(shí)，A作業(yè)到達(dá)。因系統(tǒng)的后備作業(yè)隊(duì)列中沒(méi)有其他作業(yè)，進(jìn)程就緒隊(duì)列中也沒(méi)有進(jìn)程，故作業(yè)調(diào)度程序?qū)⒆鳂I(yè)A調(diào)入內(nèi)存并將它排在就緒隊(duì)列上，進(jìn)程調(diào)度程序調(diào)度它運(yùn)行。 10：20時(shí),B作業(yè)到達(dá)。因系統(tǒng)的后備作業(yè)隊(duì)列中沒(méi)有其他作業(yè)，故作業(yè)調(diào)度程序?qū)⒆鳂I(yè)B調(diào)入內(nèi)存并將它排在就緒隊(duì)列上。而作業(yè)B的優(yōu)先級(jí)高于作業(yè)A的

23、優(yōu)先級(jí)，進(jìn)程調(diào)度程序停止作業(yè)A的運(yùn)行，將作業(yè)B放入就緒隊(duì)列，調(diào)度作業(yè)運(yùn)行。此時(shí)，系統(tǒng)中已有兩道作業(yè)在內(nèi)存中運(yùn)行，作業(yè)A已運(yùn)行20分鐘，還需運(yùn)行20分鐘才能完成。 10：30時(shí)，C作業(yè)到達(dá)。因系統(tǒng)已有兩道作業(yè)在內(nèi)存中運(yùn)行，故作業(yè)C只能在后備作業(yè)隊(duì)列中等待作業(yè)調(diào)度。此時(shí)，作業(yè)B已運(yùn)行了10分鐘并將繼續(xù)運(yùn)行，還需運(yùn)行20分鐘才能完成；作業(yè)A已等待10分鐘并將繼續(xù)等待，還需運(yùn)行20分鐘才能完成。 10：50時(shí)，B作業(yè)運(yùn)行30分鐘結(jié)束運(yùn)行，D作業(yè)到達(dá)。因系統(tǒng)中只有作業(yè)A在內(nèi)存中運(yùn)行，作業(yè)后備隊(duì)列中有C、D兩作業(yè)，按短作業(yè)優(yōu)先的作業(yè)調(diào)度策略，作業(yè)D被作業(yè)調(diào)度程序選中，裝入內(nèi)存運(yùn)行，作業(yè)C仍在后備作業(yè)隊(duì)列中

24、等待作業(yè)調(diào)度。在內(nèi)存中，作業(yè)A的優(yōu)先級(jí)高于作業(yè)D，進(jìn)程調(diào)度程序調(diào)度作業(yè)A運(yùn)行，作業(yè)D在就緒隊(duì)列中等待進(jìn)程調(diào)度。此時(shí)，作業(yè)A已運(yùn)行了20分鐘，在就緒隊(duì)列中等待了30分鐘，還需運(yùn)行20分鐘才能完成；作業(yè)C已在后備隊(duì)列中等待了20分鐘并將繼續(xù)等待。 11：10時(shí)，A作業(yè)運(yùn)行40分鐘結(jié)束運(yùn)行。因系統(tǒng)中只有作業(yè)D在內(nèi)存中運(yùn)行，作業(yè)后備隊(duì)列中只有作業(yè)C在等待，作業(yè)調(diào)度程序?qū)⒆鳂I(yè)C內(nèi)存運(yùn)行。因作業(yè)C的優(yōu)先級(jí)高于作業(yè)D，進(jìn)程調(diào)度程序作業(yè)C運(yùn)行，作業(yè)D仍在就緒隊(duì)列中等待進(jìn)程調(diào)度。此時(shí)作業(yè)D已在就緒隊(duì)列中等待了20分鐘并將繼續(xù)等待。 12：00時(shí)，C作業(yè)運(yùn)行50分鐘結(jié)束運(yùn)行。因系統(tǒng)中只有作業(yè)D在內(nèi)存，進(jìn)程調(diào)度程序

25、調(diào)度作業(yè)D運(yùn)行。 12：20時(shí)，D作業(yè)運(yùn)行20分鐘結(jié)束運(yùn)行。 作業(yè) 時(shí)間10:00 10:20 10:30 10:50 11:10 12:00 12:20作業(yè)A作業(yè)B作業(yè)C作業(yè)DCPUCPUCPUCPUCPU就緒等待就緒等待后備等待 解：（1）由上述分析可得出所有作業(yè)的進(jìn)入內(nèi)存時(shí)間和結(jié)束時(shí)間：作業(yè)名 進(jìn)入內(nèi)存時(shí)間 結(jié)束時(shí)間A 10：00 11：10 B 10：20 10：50C 11：10 12：00D 10：50 12：20（2）各作業(yè)執(zhí)行時(shí)的周轉(zhuǎn)時(shí)間為： 作業(yè)A：70分鐘 作業(yè)B：30分鐘 作業(yè)C：90分鐘 作業(yè)D：90分鐘 作業(yè)的平均周轉(zhuǎn)時(shí)間為：（70309090）470分鐘。北京大學(xué)2

26、000年進(jìn)程調(diào)度題對(duì)某系統(tǒng)進(jìn)行監(jiān)測(cè)后表明平均每個(gè)進(jìn)程在I/O阻塞之前的運(yùn)行時(shí)間為T(mén)。一次進(jìn)程切換的系統(tǒng)開(kāi)銷(xiāo)時(shí)間為S。若采用時(shí)間片長(zhǎng)度為Q的時(shí)間片輪轉(zhuǎn)法，對(duì)下列各種情況算出CPU利用率。1）Q 2）QT 3）SQT 答：因?yàn)?， CPU利用率=進(jìn)程有效運(yùn)行時(shí)間/CPU總時(shí)間=有效運(yùn)行時(shí)間/(有效運(yùn)行時(shí)間+系統(tǒng)開(kāi)銷(xiāo))。由于Q 或QT，那么，時(shí)間片足夠大，進(jìn)程每次運(yùn)行總能結(jié)束，故1)和2)兩種情況下，在T+S時(shí)間中，有效運(yùn)行了T。得到CPU利用率=T/（T+S）。1）Q= CPU利用率=T/（T+S）2）Q>T CPU利用率=T/（T+S）下面一種情況，SQT ，也就是說(shuō)，進(jìn)程完成任務(wù)運(yùn)行過(guò)程

27、中共切換了T/Q次，浪費(fèi)時(shí)間為S×(T/Q)。故CPU利用率=T/(T+ S×(T/Q)，化簡(jiǎn)后得到：3）T>Q>S 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 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í)間序列、即開(kāi)始執(zhí)行時(shí)間

28、、作業(yè)完成時(shí)間、作業(yè)周轉(zhuǎn)時(shí)間。(2)計(jì)算平均作業(yè)周轉(zhuǎn)時(shí)間。解：作業(yè) 提交 需運(yùn)行 開(kāi)始運(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:35 5 8:45 8:50 15J6 8:40 10 8:50 9:00 20說(shuō)明:(1) 采用SJF,J2到達(dá)時(shí)搶占J1；J3到達(dá)時(shí)搶占J2。(2) 但J4到達(dá)時(shí)，因不滿(mǎn)足SJF，故J4不能被運(yùn)行，J3繼續(xù)執(zhí)行5分鐘。(

29、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:25 9:55 10:35J1J2J3J4J5J6就 緒 隊(duì) 列就 緒 隊(duì) 列就 緒 隊(duì) 列后備隊(duì)列后備隊(duì)列CPUCPUCPUCPUCPUCPUCPUCPU三、 同步和互斥類(lèi) 求解同步互斥問(wèn)題的一些規(guī)律：(1) 進(jìn)程同步問(wèn)題中

30、，管理共享資源常常設(shè)兩個(gè)信號(hào)量，而進(jìn)程互斥問(wèn)題中僅需設(shè)立一個(gè)信號(hào)量。(2) P、V操作要成對(duì)調(diào)用，在進(jìn)程互斥中是針對(duì)同一個(gè)信號(hào)量進(jìn)行。而在進(jìn)程同步問(wè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年同步與互斥題有一個(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ò)程。 分析及相關(guān)知識(shí)本題給出的第一個(gè)條件

31、是臨界資源的訪問(wèn)控制，可用一個(gè)互斥信號(hào)量解決該問(wèn)題。第二個(gè)條件可以分解為： NA產(chǎn)品數(shù)量B產(chǎn)品數(shù)量 A產(chǎn)品數(shù)量B產(chǎn)品數(shù)量M也就是說(shuō)，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產(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ù)中存放

32、入一個(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); P(mutex); 將B產(chǎn)品入庫(kù)； V(mutex); V(sa); 北京大學(xué)1994年同步與互斥題進(jìn)程A1，A2，An1通過(guò)m個(gè)緩沖區(qū)向進(jìn)程B1，B2，Bn2不斷地發(fā)送消息。發(fā)送和接收工作遵循如下規(guī)則：每個(gè)發(fā)送進(jìn)程一次發(fā)

33、送一個(gè)消息，寫(xiě)入一個(gè)緩沖區(qū)，緩沖區(qū)大小等于消息長(zhǎng)度；對(duì)每一個(gè)消息，B1，B2，Bn2 都須各接收一次，讀入各自的數(shù)據(jù)區(qū)內(nèi)；m個(gè)緩沖區(qū)都滿(mǎn)時(shí)，發(fā)送進(jìn)程等待；沒(méi)有可讀的消息時(shí)，接收進(jìn)程等待。試用P、V操作組織正確的發(fā)送和接收工作。 分析及相關(guān)知識(shí)本題是生產(chǎn)者消費(fèi)者問(wèn)題的一個(gè)變形，一組生產(chǎn)者A1，A2，An1和一組消費(fèi)者B1，B2，Bn2共用m個(gè)緩沖區(qū)，每個(gè)緩沖區(qū)只要寫(xiě)一次，但需要讀n2次。因此，可以把這一組緩沖區(qū)看成n2組緩沖區(qū)，每個(gè)發(fā)送者需要同時(shí)寫(xiě)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ū)的

34、互斥訪問(wèn)；兩個(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 () cobegin A1( ); A2( ); An1 () B1 (); B2 (); Bn2( );coend send ( ) /*發(fā)送消息*/ int i;for (i=0;i<=n2-1;i+) p(empt

35、yi); 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的程序類(lèi)似，這里只給出進(jìn)程Ai的描述*/while (1) send ( ); Bi ( ) /*因接收進(jìn)程B1,B2,Bn2的程序類(lèi)似，這里只給出進(jìn)程Bi描述*/while (1) receive(i); 北大1995年同步與互斥題有一個(gè)倉(cāng)庫(kù)可存放A、B兩種零件，最大庫(kù)容

36、量各為m個(gè)。生產(chǎn)車(chē)間不斷地取A和B進(jìn)行裝配，每次各取一個(gè)。為避免零件銹蝕，按先入庫(kù)者先出庫(kù)的原則。有兩組供應(yīng)商分別不斷地供應(yīng)A和B，每次一個(gè)。為保證配套和合理庫(kù)存，當(dāng)某種零件比另一種零件超過(guò)n(n<m)個(gè)時(shí)，暫停對(duì)數(shù)量大的零件的進(jìn)貨，集中補(bǔ)充數(shù)量少的零件。試用信號(hào)量與P、V操作正確地實(shí)現(xiàn)它們之間的同步關(guān)系。答：按照題意，應(yīng)滿(mǎn)足以下控制關(guān)系：A零件數(shù)量- B零件數(shù)量n；B零件數(shù)量- A零件數(shù)量n；A零件數(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ù)指針

37、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；cobeginprocess producerA repeat P(empty1)； P(sa)； P(mutex)； buffer1in1 ：=A零件； in1：=(in1+1) mod m

38、； 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(full2)；P(mutex)；Take from buffer1out1 and buffer2out2中的A、B零件；out1：=(out1+1) mod m；out2：=(out2+1)

39、mod m；V(mutex)；V(empty1)；V(empty2)；把A和B裝配成產(chǎn)品；until falsecoend.北大1997年同步與互斥題某高校開(kāi)設(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é)生同時(shí)離開(kāi)機(jī)房。試用信號(hào)量和P、V操作模擬上機(jī)實(shí)習(xí)過(guò)程。答1：var mutex,enter:semaphore; mutex:=1;enter:=0; finish,test,rc,comp

40、utercounter: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é)生，則在enter上等待 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é)

41、束 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,computer,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); /