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

1、操作系統(tǒng)碩士研究生入學(xué)考試全真試題分類解析一、 與時間有關(guān)錯誤類二、 進(jìn)程管理及調(diào)度類三、 同步和互斥類四、 死鎖問題類五、 存儲管理類六、 文件管理類七、 設(shè)備管理類一、 與時間有關(guān)錯誤類北航2001與時間有關(guān)錯題有兩個優(yōu)先級相同的進(jìn)程P1和P2，各自執(zhí)行的操作如下，信號量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)對進(jìn)程語句進(jìn)行編

2、號，以方便描述。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.、和是不相交語句，可以任何次序交錯執(zhí)行，而結(jié)果是唯一的。接著無論系統(tǒng)如何調(diào)度進(jìn)程并發(fā)執(zhí)行，當(dāng)執(zhí)行到語句時，可以得到x=5，y=3。按Bernstein條件，語句的執(zhí)行結(jié)果不受語句的影響，故語句執(zhí)行后得到z=4。最后，語句和并發(fā)執(zhí)行，最后結(jié)果為：語句先執(zhí)行，再執(zhí)行：x=5，y=7，z=9。語句先執(zhí)行，再執(zhí)行：x=5 ，y=12，z=9。華中科技大2000

3、、國防科大1999與時間有關(guān)錯題進(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;這時P0被打斷，P1開始執(zhí)行，首先執(zhí)行.，使得flag1的值為true。接著執(zhí)行，由于turn的初值為0，故進(jìn)入內(nèi)循環(huán)時turn置為1。這時調(diào)度轉(zhuǎn)向P0，P0也進(jìn)入內(nèi)循環(huán)，由于flag1的值己為true，故P0再次把turn值置為0。重復(fù)上述兩個操作，沒有進(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 有一個進(jìn)程己在臨界區(qū)，另一個必將在while flagk and turn=k (k=0 or 1)上做空操作等待進(jìn)入。 3 進(jìn)程交叉執(zhí)行時，有一個也必將在while flagk and turn

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

7、0;Critical Section; (/* 臨界區(qū) */)c1:=1 until false end;procedure p2; (/* 對另一個進(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開始執(zhí)行 */)coend end.答：(1)互斥己知c1和c2的初值為1，若進(jìn)程P1執(zhí)行到

8、c1:=1-c2時，進(jìn)程P2也同時執(zhí)行c2:=1-c1。這樣一來，c1和c2的值都變?yōu)?。于是，P1和P2會同時進(jìn)入臨界區(qū)，不滿足互斥條件。(2) 有空讓進(jìn)設(shè)開始無進(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ū)時，執(zhí)行了c1:=1，使得P2就可進(jìn)入臨界區(qū)。進(jìn)程P2先執(zhí)行的情況相似，能保證有空讓進(jìn)的原則。(3) 有限等待不一定能實(shí)現(xiàn)。假定進(jìn)程P1離開臨界區(qū)，進(jìn)程P2申請進(jìn)入臨界區(qū)，但還未來得及執(zhí)行c2:=1-c1時，進(jìn)程P1又再次執(zhí)行c1:=1-c2，搶先進(jìn)入臨界區(qū)。因而，造成饑餓現(xiàn)象。北京大學(xué)19

9、93、國防科大2001與時間有關(guān)錯舉例說明P，V操作為什么要用原語實(shí)現(xiàn)？操作系統(tǒng)如何實(shí)現(xiàn)這種原語操作？解：信號量S是P,V均要操作的共享變量，每次它們有對S的加或減1操作。若不把P,V設(shè)計成原語，則它們交替在同一信號量上操作時會造成S值不惟一，更為嚴(yán)重的會造成某些進(jìn)程處于永遠(yuǎn)等待狀態(tài)。例如，若S當(dāng)前值為1，第一個P操執(zhí)行后，進(jìn)程是不會阻塞的。但若在第一個P操作執(zhí)行 if S<0 then之前，有另一個進(jìn)程的P操作搶先執(zhí)行S:=S-1，這時S=-1，而第一個執(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;/* 把信號量減去1 */ if s.value< 0 then W(s.queue);/* 若信號量小于0，則執(zhí)行P(s)的進(jìn)程調(diào)用 W(s.queue) 進(jìn)行自我封鎖，被置成等待信號量s的狀態(tài)，進(jìn)入信 號量隊(duì)列queue*/ end; procedure V(var s:semaphore); begin s.value:= s.value + 1; /* 把信號量加1 */if s.value 0 then R(s

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

12、( ); /*pc(程序計數(shù)器)，進(jìn)程A fork( ); /*pc(程序計數(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(程序計數(shù)器)，進(jìn)程A fork( ); /*pc(程序計數(shù)器)，進(jìn)程B main( ) main( ) fork( ); fork( ); fork( ); fork( ); fork( ); /*pc(程序計數(shù)器)，進(jìn)程C fork( ); /*pc(程序計數(shù)器)，進(jìn)程D 當(dāng)進(jìn)程

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

14、。若有處等待態(tài)的P1或P2或P3有個變成就緒態(tài)，則當(dāng)前時間片耗盡后又回到優(yōu)先級4執(zhí)行。只有當(dāng)優(yōu)先級4或優(yōu)先級3隊(duì)列中進(jìn)程空或全進(jìn)入等待態(tài)時，才調(diào)度優(yōu)先級2隊(duì)列中的進(jìn)程P6、P7和P8執(zhí)行，過程如上不贅。復(fù)旦大學(xué)大學(xué)2002進(jìn)程管理及調(diào)度題對基本的進(jìn)程狀態(tài)轉(zhuǎn)換圖中的狀態(tài)轉(zhuǎn)換編號1，2，3和4。令i和j取值1，2，3和4（ji）。請分別討論在狀態(tài)轉(zhuǎn)換i和狀態(tài)轉(zhuǎn)換j之間是否存在因果關(guān)系：若存在，請指出這種關(guān)系是必然的，或是有條件的，條件是什么？ 運(yùn)行就緒阻塞1423解：12 存在因果關(guān)系。時間片到。 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和兩臺I/O(I1,I2)設(shè)備的多道程序設(shè)計環(huán)境下，同時投入三個作業(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)先級從高到低為Job1、Job2和Job3，優(yōu)先級高的作業(yè)可以搶占優(yōu)先級低的作業(yè)的CPU，但不搶占I1

16、和I2。試求：(1)每個作業(yè)從投入到完成分別所需的時間。(2) 從投入到完成CPU的利用率。(3)I/O設(shè)備利用率。答：畫出三個作業(yè)并行工作圖如下(圖中著色部分為作業(yè)等待時間)：CPUI1I2Job1Job2Job3時間(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使用時間為10+10

17、+10+10+20+10=70。所以CPU利用率為70/90=77.8%。(3) 設(shè)備I1空閑時間段為：20ms至40ms，故I1的利用率為70/90=77.8%。設(shè)備I2空閑時間段為：30ms至50ms，故I2的利用率為70/90=77.8%。東南大學(xué)1996進(jìn)程調(diào)度題某多道程序設(shè)計系統(tǒng)供用戶使用的主存為100K，磁帶機(jī)2臺，打印機(jī)1臺。采用可變分區(qū)內(nèi)存管理，采用靜態(tài)方式分配外圍設(shè)備，忽略用戶作業(yè)I/O時間?，F(xiàn)有作業(yè)序列如下：作業(yè)號 進(jìn)入輸入井時間 運(yùn)行時間 主存需求量 磁帶需求 打印機(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)移動已在主存的作業(yè)，在主存中的各作業(yè)平分CPU時間?，F(xiàn)求：(1)作業(yè)被調(diào)度的先后次序?(2)全部作業(yè)運(yùn)行結(jié)束的時間?(3)作業(yè)平均周轉(zhuǎn)時間為多少?(4)最大作業(yè)周轉(zhuǎn)時間為多少?答：(1)作業(yè)調(diào)度選擇的作業(yè)次序?yàn)椋鹤鳂I(yè)1、作業(yè)3、作業(yè)4、作業(yè)2和作業(yè)5。 (2)全部作業(yè)運(yùn)行結(jié)束的時間9:30。 (3)周轉(zhuǎn)時間：作業(yè)1為30分鐘、作業(yè)2為55分鐘、作業(yè)3為40分鐘、作業(yè)4為40分鐘和作業(yè)5為55分鐘。 (4)平均作業(yè)周轉(zhuǎn)時間=44分鐘。 (5) )

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

20、達(dá)時間晚，只能等待。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時間(分) 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)度題有一個具有兩道作業(yè)的批處理系統(tǒng)，作業(yè)調(diào)度采用短作業(yè)優(yōu)先的調(diào)度算法，進(jìn)程調(diào)度采用以優(yōu)先數(shù)為基礎(chǔ)的搶占式調(diào)度算法，在下表所示的作業(yè)序列，作業(yè)優(yōu)先數(shù)即為進(jìn)程優(yōu)先數(shù)，優(yōu)先數(shù)越小優(yōu)先級越高。作業(yè)名 到達(dá)時間 估計運(yùn)行時間 優(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)存時間及結(jié)束時間。 (2)計算平均周轉(zhuǎn)時間。分析：每個作業(yè)的運(yùn)行將經(jīng)歷兩

22、級調(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ì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時，A作業(yè)到達(dá)。因系統(tǒng)的后備作業(yè)隊(duì)列中沒有其他作業(yè)，進(jìn)程就緒隊(duì)列中也沒有進(jìn)程，故作業(yè)調(diào)度程序?qū)⒆鳂I(yè)A調(diào)入內(nèi)存并將它排在就緒隊(duì)列上，進(jìn)程調(diào)度程序調(diào)度它運(yùn)行。 10：20時,B作業(yè)到達(dá)。因系統(tǒng)的后備作業(yè)隊(duì)列中沒有其他作業(yè)，故作業(yè)調(diào)度程序?qū)⒆鳂I(yè)B調(diào)入內(nèi)存并將它排在就緒隊(duì)列上。而作業(yè)B的優(yōu)先級高于作業(yè)A的

23、優(yōu)先級，進(jìn)程調(diào)度程序停止作業(yè)A的運(yùn)行，將作業(yè)B放入就緒隊(duì)列，調(diào)度作業(yè)運(yùn)行。此時，系統(tǒng)中已有兩道作業(yè)在內(nèi)存中運(yùn)行，作業(yè)A已運(yùn)行20分鐘，還需運(yùn)行20分鐘才能完成。 10：30時，C作業(yè)到達(dá)。因系統(tǒng)已有兩道作業(yè)在內(nèi)存中運(yùn)行，故作業(yè)C只能在后備作業(yè)隊(duì)列中等待作業(yè)調(diào)度。此時，作業(yè)B已運(yùn)行了10分鐘并將繼續(xù)運(yùn)行，還需運(yùn)行20分鐘才能完成；作業(yè)A已等待10分鐘并將繼續(xù)等待，還需運(yùn)行20分鐘才能完成。 10：50時，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)先級高于作業(yè)D，進(jìn)程調(diào)度程序調(diào)度作業(yè)A運(yùn)行，作業(yè)D在就緒隊(duì)列中等待進(jìn)程調(diào)度。此時，作業(yè)A已運(yùn)行了20分鐘，在就緒隊(duì)列中等待了30分鐘，還需運(yùn)行20分鐘才能完成；作業(yè)C已在后備隊(duì)列中等待了20分鐘并將繼續(xù)等待。 11：10時，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)先級高于作業(yè)D，進(jìn)程調(diào)度程序作業(yè)C運(yùn)行，作業(yè)D仍在就緒隊(duì)列中等待進(jìn)程調(diào)度。此時作業(yè)D已在就緒隊(duì)列中等待了20分鐘并將繼續(xù)等待。 12：00時，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時，D作業(yè)運(yùn)行20分鐘結(jié)束運(yùn)行。 作業(yè) 時間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)存時間和結(jié)束時間：作業(yè)名 進(jìn)入內(nèi)存時間 結(jié)束時間A 10：00 11：10 B 10：20 10：50C 11：10 12：00D 10：50 12：20（2）各作業(yè)執(zhí)行時的周轉(zhuǎn)時間為： 作業(yè)A：70分鐘 作業(yè)B：30分鐘 作業(yè)C：90分鐘 作業(yè)D：90分鐘 作業(yè)的平均周轉(zhuǎn)時間為：（70309090）470分鐘。北京大學(xué)2

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

27、中共切換了T/Q次，浪費(fèi)時間為S×(T/Q)。故CPU利用率=T/(T+ S×(T/Q)，化簡后得到：3）T>Q>S CPU利用率=Q/（Q+S）南京大學(xué)本課生進(jìn)程管理及調(diào)度習(xí)題有一個四道作業(yè)的操作系統(tǒng)，若在一段時間內(nèi)先后到達(dá)6個作業(yè)，它們的提交和估計運(yùn)行時間由下表給出：作業(yè) 提交時間 估計運(yùn)行時間(分鐘) 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)后中途不會退出，但作業(yè)運(yùn)行時可被更短作業(yè)搶占。(1)分別給出6個作業(yè)的執(zhí)行時間序列、即開始執(zhí)行時間

28、、作業(yè)完成時間、作業(yè)周轉(zhuǎn)時間。(2)計算平均作業(yè)周轉(zhuǎn)時間。解：作業(yè) 提交 需運(yùn)行 開始運(yùn)行 被搶占還 完成 周轉(zhuǎn)號 時間 時間 時間 需運(yùn)行時間 時間 時間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說明:(1) 采用SJF,J2到達(dá)時搶占J1；J3到達(dá)時搶占J2。(2) 但J4到達(dá)時，因不滿足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第一個做完。而這時J5可進(jìn)入主存。(5) 因J5最短，故它第二個完成。這時J6可進(jìn)入主存。(6) 因J6最短，故它第三個完成。(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三、 同步和互斥類 求解同步互斥問題的一些規(guī)律：(1) 進(jìn)程同步問題中

30、，管理共享資源常常設(shè)兩個信號量，而進(jìn)程互斥問題中僅需設(shè)立一個信號量。(2) P、V操作要成對調(diào)用，在進(jìn)程互斥中是針對同一個信號量進(jìn)行。而在進(jìn)程同步問題中，進(jìn)入臨界區(qū)前后P、V操作是針對不同的信號量的(3) 至少有一個信號量初值大于等于1(一般指管理共享資源的信號量)，否則進(jìn)程無法被啟動運(yùn)行。(4) 若有多個(k)共享資源，則某信號量初值可設(shè)為k。北京大學(xué)1991年同步與互斥題有一個倉庫，可以存放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的入庫過程。 分析及相關(guān)知識本題給出的第一個條件

31、是臨界資源的訪問控制，可用一個互斥信號量解決該問題。第二個條件可以分解為： 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個以上，A產(chǎn)品的數(shù)量不能比B產(chǎn)品的數(shù)量多M個以上。解：在本題中，可以設(shè)置兩個信號量來控制A、B產(chǎn)品的存放數(shù)量，sa表示當(dāng)前允許A產(chǎn)品比B產(chǎn)品多入庫的數(shù)量，即在當(dāng)前庫存量和B產(chǎn)品不入庫的情況下，還可以允許sa個A產(chǎn)品入庫；sb表示當(dāng)前允許B產(chǎn)品比A產(chǎn)品多入庫的數(shù)量，即在當(dāng)前庫存量和A產(chǎn)品不入庫的情況下，還可以允許sb個B產(chǎn)品入庫。初始時，sa為M1，sb為N1。當(dāng)往庫中存放入一個A產(chǎn)品時，則允許存入B產(chǎn)品的數(shù)量也增加1；當(dāng)往庫中存放

32、入一個B產(chǎn)品時，則允許存入A產(chǎn)品的數(shù)量也增加1。var mutex：semaphore=1;/*互斥信號量*/ sa，sb：semaphore； sa=M-1; sb=N-1;mian( ) while (1) 取一個產(chǎn)品； if(取的是A產(chǎn)品) P(sa); P(mutex); 將A產(chǎn)品入庫； V(mutex); V(sb); else /*取的產(chǎn)品是B*/ P(sb); P(mutex); 將B產(chǎn)品入庫； V(mutex); V(sa); 北京大學(xué)1994年同步與互斥題進(jìn)程A1，A2，An1通過m個緩沖區(qū)向進(jìn)程B1，B2，Bn2不斷地發(fā)送消息。發(fā)送和接收工作遵循如下規(guī)則：每個發(fā)送進(jìn)程一次發(fā)

33、送一個消息，寫入一個緩沖區(qū)，緩沖區(qū)大小等于消息長度；對每一個消息，B1，B2，Bn2 都須各接收一次，讀入各自的數(shù)據(jù)區(qū)內(nèi)；m個緩沖區(qū)都滿時，發(fā)送進(jìn)程等待；沒有可讀的消息時，接收進(jìn)程等待。試用P、V操作組織正確的發(fā)送和接收工作。 分析及相關(guān)知識本題是生產(chǎn)者消費(fèi)者問題的一個變形，一組生產(chǎn)者A1，A2，An1和一組消費(fèi)者B1，B2，Bn2共用m個緩沖區(qū)，每個緩沖區(qū)只要寫一次，但需要讀n2次。因此，可以把這一組緩沖區(qū)看成n2組緩沖區(qū)，每個發(fā)送者需要同時寫n2組緩沖區(qū)中相應(yīng)的n2個緩沖區(qū)，而每一個接收者只需讀它自己對應(yīng)的那組緩沖區(qū)中的對應(yīng)單元。解：在本題中，應(yīng)設(shè)置一個信號量mutex實(shí)現(xiàn)諸進(jìn)程對緩沖區(qū)的

34、互斥訪問；兩個信號量數(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的程序類似，這里只給出進(jìn)程Ai的描述*/while (1) send ( ); Bi ( ) /*因接收進(jìn)程B1,B2,Bn2的程序類似，這里只給出進(jìn)程Bi描述*/while (1) receive(i); 北大1995年同步與互斥題有一個倉庫可存放A、B兩種零件，最大庫容

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

37、out1、out2來控制順序。并發(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年同步與互斥題某高校開設(shè)網(wǎng)絡(luò)課程并安排上機(jī)實(shí)習(xí)，如果機(jī)房共有2m臺機(jī)器，有2n個學(xué)生選課，規(guī)定：(1)每兩個學(xué)生分成一組，并占用一臺機(jī)器，協(xié)同完成上機(jī)實(shí)習(xí)；(2)僅當(dāng)一組兩個學(xué)生到齊，并且機(jī)房機(jī)器有空閑時，該組學(xué)生才能進(jìn)機(jī)房；(3)上機(jī)實(shí)習(xí)由一名教師檢查，檢查完畢，一組學(xué)生同時離開機(jī)房。試用信號量和P、V操作模擬上機(jī)實(shí)習(xí)過程。答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); /*申請計算機(jī) P(mutex); rc:=rc+1; /*學(xué)生互斥計數(shù) if rc=1 then V(mutex);P(enter); /*若只來一個學(xué)生，則在enter上等待 else rc:=0; V(mutex);V(enter); /*到達(dá)一組中第二個學(xué)生，rc清0是為下一組計數(shù)用 學(xué)生進(jìn)入機(jī)房,上機(jī)實(shí)習(xí); V(finish); /*告訴老師，實(shí)習(xí)結(jié)

41、束 P(test); /*等待老師檢查實(shí)習(xí)結(jié)果 V(computercounter); /*歸還計算機(jī)end process teacherbegin P(finish); /*等第一個學(xué)生實(shí)習(xí)結(jié)束 P(finish); /*等第二個學(xué)生實(shí)習(xí)結(jié)束 檢查實(shí)習(xí)結(jié)果; V(test); /*第一個學(xué)生檢查完成 V(test); /*第二個學(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); /*申請一臺計算機(jī) P(enter); /*等待允許進(jìn)入 與同伴上機(jī)實(shí)習(xí); V(finish); /*完成實(shí)習(xí) P(check); /