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：beginy:=1;y:=y+2;V(S1);z:=y+1;P(S2);y:=z+yend.P2：beginx:=1;x:=x+1;P(S1);x:=x+y;V(S2);z:=z+xend.答：現(xiàn)對(duì)進(jìn)程語句進(jìn)行編號(hào)，以方便描述。P1：P2：beginy:=1;y:=y

2、+2;V(S1);z:=y+1;P(S2);y:=z+yend.beginx:=1;x:=x+1;P(S1);x:=x+y;V(S2);z:=z+x;end.、和是不相交語句，可以任何次序交錯(cuò)執(zhí)行，而結(jié)果是唯一的。接著無論系統(tǒng)如何調(diào)度進(jìn)程并發(fā)執(zhí)行，當(dāng)執(zhí)行到語句時(shí)，可以得到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、國(guó)防科大1999與時(shí)間有關(guān)錯(cuò)題進(jìn)程P0，P1共享變量flag和turn。若flag和tu

3、rn單元內(nèi)容的修改和訪問是互斥的，它們?nèi)缦逻M(jìn)入臨界區(qū)：varflag:array01ofBoolean;turn:0T;flag0:=flag1:=false;turn:=0;processi(i=0or1)whiletruedobeginflagi:=true;(Dwhileturn?i:dobeginwhileflagj=falsedoskip;turn:=i:end;臨界區(qū);flagi:=false;出臨界區(qū);end:該算法能正確實(shí)現(xiàn)互斥嗎應(yīng)如何修改解：不能。若P0執(zhí)行到，flag0:=true;這時(shí)P0被打斷，P1開始執(zhí)行，首先執(zhí)行:,使得flag1的值為true。接著執(zhí)行，由于tur

4、n的初值為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ū)。修改算法如下：varflag:array01ofBoolean;turn:0T;flag0:=flag1:=false;turn:=0or1;process0whiletruedobeginflag0:=true;turn:=1;whileflag1andturn=1doskip;臨界區(qū);flag0:=false;出臨界區(qū);end;process1whiletruedobeginflag1:=true;turn:=0

5、;whileflag0andturn=0doskip;臨界區(qū);flag1:=false;出臨界區(qū);end;此算法能保證互斥，討論：1沒有進(jìn)程在臨界區(qū)，顯然，任一進(jìn)程能進(jìn)入。2 有一個(gè)進(jìn)程己在臨界區(qū)，另一個(gè)必將在whileflagkandturn=k(k=0or1)上做空操作等待進(jìn)入。3 進(jìn)程交叉執(zhí)行時(shí)，有一個(gè)也必將在whileflagkandturn=k(k=0or1)上做空操作等待進(jìn)入。復(fù)旦大學(xué)1999、浙江大學(xué)1997與時(shí)間有關(guān)錯(cuò)題下述流程是解決兩進(jìn)程互斥訪問臨界區(qū)問題的一種方法。試從“互斥”(mutualexclusion)、“空閑讓進(jìn)”(progress、)“有限等待”(bounded

6、waiting)等三方面討論它的正確性。如果它是正確的，則證明之；如果它不正確，請(qǐng)說明理由。programattemp;varc1,c2:integer;procedurep1;(/*對(duì)第一個(gè)進(jìn)程p1*/)beginrepeatRemainSection1;repeatc1:=1-c2untilc2<>0;CriticalSection;（/*臨界區(qū)*/）c1:=1untilfalseend;procedurep2;（/*對(duì)另一個(gè)進(jìn)程p2*/）beginrepeatRemainSection2;repeatc2:=1-c1untilc1<>0;CriticalSecti

7、on;（/*臨界區(qū)*/）c2:=1untilfalseend;begin（/*主程序*/）c1:=1;c2:=1;cobeginp1;p2（/*兩進(jìn)程p1,p2開始執(zhí)行*/）coendend.答：(1)互斥己知cl和c2的初值為1,若進(jìn)程P1執(zhí)行到c1:=1-c方寸，進(jìn)程P池同時(shí)執(zhí)行c2:=1-c1。這樣一來，cl和c2的值都變?yōu)?。于是，P1和P2會(huì)同時(shí)進(jìn)入臨界區(qū)，不滿足互斥條件。(2) 有空讓進(jìn)設(shè)開始無進(jìn)程在臨界區(qū)中，進(jìn)程P1執(zhí)行了c1:=1-c2,由于c2的初值為1,這使得cl的值變?yōu)?但c2仍為1,從而保證了P1進(jìn)入臨界區(qū)。當(dāng)P1退出臨界區(qū)時(shí)，執(zhí)行了c1：=1,使得P2M可進(jìn)入臨界區(qū)。

8、進(jìn)程P冼執(zhí)行的情況相似，能保證有空讓進(jìn)的原則。(3) 有限等待不一定能實(shí)現(xiàn)。假定進(jìn)程P1離開臨界區(qū)，進(jìn)程P2申請(qǐng)進(jìn)入臨界區(qū)，但還未來得及執(zhí)行c2:=1-c1時(shí)，進(jìn)程P1又再次執(zhí)行c1:=1-c2,搶先進(jìn)入臨界區(qū)。因而，造成饑餓現(xiàn)象。北京大學(xué)1993、國(guó)防科大2001與時(shí)間有關(guān)錯(cuò)舉例說明P，V操作為什么要用原語實(shí)現(xiàn)操作系統(tǒng)如何實(shí)現(xiàn)這種原語操作解：信號(hào)量S是P,V均要操作的共享變量，每次它們有對(duì)S的加或減1操作。若不把P,V設(shè)計(jì)成原語，則它們交替在同一信號(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操

9、作執(zhí)行ifS<0then之前，有另一個(gè)進(jìn)程的P操作搶先執(zhí)行S:=S-1這時(shí)S=-1,而第一個(gè)執(zhí)行P操作的進(jìn)程被阻塞了。這是不符合P,V原定義的含義的。附：typesemaphore=recordvalue:integer;queue:listofprocess;endprocedureP(vars:semaphore);begin:=-1;/*把信號(hào)量減去1*/if<0thenW;/*若信號(hào)量小于0，則執(zhí)行P(s)的進(jìn)程調(diào)用W進(jìn)行自我封鎖，被置成等待信號(hào)量s的狀態(tài)，進(jìn)入信號(hào)量隊(duì)列queue*/end;procedureV(vars:semaphore);begin:=+1;/*把信

10、號(hào)量加1*/if<0thenR;/*若信號(hào)量小于等于0,則調(diào)用R從信號(hào)量s隊(duì)列queueend;釋放一個(gè)等待信號(hào)量s的進(jìn)程并置成就緒態(tài)*/二、 進(jìn)程管理與調(diào)度類中山大學(xué) 1996 進(jìn)程管理題在 UNIX 系統(tǒng)中運(yùn)行以下程序，最多可產(chǎn)生出多少進(jìn)程畫出進(jìn)程家屬樹。main( )fork( ); /* -pc(程序計(jì)數(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( )fork( );fork( ); /* - pc(程序計(jì)數(shù)器

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

12、,且所有進(jìn)程的PC均指向程序結(jié)束處。這時(shí)進(jìn)程A共派生出7個(gè)子進(jìn)程。電子科技大學(xué)2001進(jìn)程管理及調(diào)度題如圖，系統(tǒng)進(jìn)程分4類排入隊(duì)列，各類之間采用優(yōu)先級(jí)調(diào)度，各類內(nèi)部采用時(shí)間片輪轉(zhuǎn)調(diào)度。簡(jiǎn)述進(jìn)程P1-P8的調(diào)度過程。答：系統(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í)間片到來。若P1、P2和P3均運(yùn)行結(jié)束，或均進(jìn)入了等待態(tài)，系統(tǒng)會(huì)調(diào)度優(yōu)先級(jí)3隊(duì)列中的P4、P5執(zhí)行，執(zhí)行過程同上。若有處等待態(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)入等待

13、態(tài)時(shí)，才調(diào)度優(yōu)先級(jí)2隊(duì)列中的進(jìn)程P6、P7和P8執(zhí)行，過程如上不贅。復(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)o請(qǐng)分別討論在狀態(tài)轉(zhuǎn)換i和狀態(tài)轉(zhuǎn)換j之間是否存在因果關(guān)系：若存在，請(qǐng)指出這種關(guān)系是必然的，或是有條件的，條件是什么解：1-2存在因果關(guān)系。時(shí)間片到。1-3不存在。1-4不存在。2-1不存在。2-3不存在。2-4不存在。3-1不存在。3-2存在。僅當(dāng)發(fā)生在優(yōu)先權(quán)剝奪式調(diào)度算法中3-4不存在。4-1不存在。4-2存在。運(yùn)行進(jìn)程等待必引起另一進(jìn)程被調(diào)度4-3不存在。南京大學(xué)1999進(jìn)程調(diào)度題在單CPU和兩臺(tái)1/

14、0(11,12)設(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)如果CPUI1和I2都能并行工作，優(yōu)先級(jí)從高到低為Job1、Job2和Job3,優(yōu)先級(jí)高的作業(yè)可以搶占優(yōu)先級(jí)低的作業(yè)的CPU,但不搶占I1和12。試求：(1)每個(gè)作業(yè)從投入到完成分別所需的時(shí)間。(2)從投入到完成CPU的利用率。(3)1/0設(shè)備利用率。答：畫出三個(gè)作業(yè)并行工作圖如下(圖中著色部分為作業(yè)等待時(shí)間):CPUJob3

15、|Job2Job1|Job2Job3|Job1|11Job2|Job1Job3|I2Job1|Job2|Job1I2CPUI1CPU(ms)0102030405060708090(1)Job1從投入到運(yùn)行完成需80ms,Job2從投入到運(yùn)行完成需90ms,Job3從投入到運(yùn)行完成需90ms。CPU使用時(shí)間為10+10+10+10+20+10=70所以CPU利用率為70/90=%。設(shè)備I1空閑時(shí)間段為：20ms至40ms,故I1的禾I用率為70/90=%。設(shè)備I2空閑時(shí)間段為：30ms至50ms,故I2的利用率為70/90=%。東南大學(xué)1996進(jìn)程調(diào)度題某多道程序設(shè)計(jì)系統(tǒng)供用戶使用的主存為100

16、K,磁帶機(jī)2臺(tái)，打印機(jī)1臺(tái)。采用可變分區(qū)內(nèi)存管理，采用靜態(tài)方式分配外圍設(shè)備，忽略用戶作業(yè)I/O時(shí)間。現(xiàn)有作業(yè)序列如下：作業(yè)甘進(jìn)入輸入開燈問廷仃燈問土仔前不重才印機(jī)言不18:0025分鐘15K1128:2010分鐘30K0138:2020分鐘60K1048:3020分鐘20K1058:3515分鐘10K11作業(yè)調(diào)度采用FCF磔略，優(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。

17、（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）最大作業(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資源滿足，可進(jìn)主存運(yùn)行，并與作業(yè)1平分CPU時(shí)間。8:30作業(yè)1在8:30結(jié)束，釋放磁帶與打印機(jī)。但作業(yè)2仍不能執(zhí)行,因不能移動(dòng)而沒有30KB的空閑區(qū)，繼續(xù)等待。作業(yè)4在8:30到達(dá),并進(jìn)入主存執(zhí)行

18、，與作業(yè)3分享CPU8:35作業(yè)5到達(dá)，因分不到磁帶機(jī)/打印機(jī)，只能在后備隊(duì)列等待。9:00作業(yè)3運(yùn)行結(jié)束，釋放磁帶機(jī)。此時(shí)作業(yè)2的主存及打印機(jī)均可滿足，投入運(yùn)行。作業(yè)5到達(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)行8:008:208:309:30作業(yè)全部執(zhí)行結(jié)束015K75K100K015K75K95K100K作業(yè)3作業(yè)4030K75K95K100K9:00030K40K100K9:10100K9:15時(shí)間（分）CPU打印機(jī)磁帶機(jī)1磁帶機(jī)2作業(yè)1作業(yè)2作業(yè)3作業(yè)4作業(yè)5;作業(yè)111作業(yè)1、3作業(yè)3、4作業(yè)2、

19、4作業(yè)2作業(yè)5:作業(yè)111作業(yè)2作業(yè)58:008:208:308:359:009:109:15作業(yè)1作業(yè)4作業(yè)5L作業(yè)3,CPU11/2CPUr1/2CPU1等待1/2CPU1/2CPU1/2CPUcpu:1G1i111/2CPU11119；1等待，1111111CPU9:30北京大學(xué)1995年進(jìn)程調(diào)度題有一個(gè)具有兩道作業(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)先級(jí)越高。到達(dá)時(shí)間A10:0040分5B10:2030分3C10:3050分4D10:5020分6(1)列出所有作業(yè)進(jìn)入內(nèi)存

20、時(shí)間及結(jié)束時(shí)間。(2)計(jì)算平均周轉(zhuǎn)時(shí)間。分析：每個(gè)作業(yè)的運(yùn)行將經(jīng)歷兩級(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ì)列中沒有其他作業(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時(shí),B作業(yè)到達(dá)。因系統(tǒng)的后備作業(yè)隊(duì)列中沒有其他作業(yè)，故作業(yè)調(diào)度程

21、序?qū)⒆鳂I(yè)麗入內(nèi)存并將它排在就緒隊(duì)列上。而作業(yè)B的優(yōu)先級(jí)高于作業(yè)A的優(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ì)列中有CD兩作業(yè)，按短作業(yè)優(yōu)先的作業(yè)調(diào)度策略，

22、作業(yè)D作業(yè)調(diào)度程序選中，裝入內(nèi)存運(yùn)行，作業(yè)C仍在后備作業(yè)隊(duì)列中等待作業(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)彳f了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è)CS等待，作業(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

23、作業(yè)運(yùn)行50分鐘結(jié)束運(yùn)行。因系統(tǒng)中只有作業(yè)D在內(nèi)存，進(jìn)程調(diào)度程序調(diào)度作業(yè)D運(yùn)行。?12:20時(shí)，D作業(yè)運(yùn)行20分鐘結(jié)束運(yùn)行。12:00J 作業(yè)A作業(yè)Bi作業(yè)CiCPU作業(yè)D作業(yè)時(shí)間-10:0012:201!就緒等待CPU ia：i: :J1CPUi后備等待J1iiii10:2010:3010:50!二i- iCPUi就緒等待11:10CPU解：（1）由上述分析可得出所有作業(yè)的進(jìn)入內(nèi)存時(shí)間和結(jié)束時(shí)間:進(jìn)入內(nèi)存時(shí)間結(jié)束時(shí)間A10:0011:10B10:2010:50C11:1012:00D10:5012:20(2)各作業(yè)執(zhí)行時(shí)的周轉(zhuǎn)時(shí)間為：作業(yè)A:70分鐘作業(yè)B:30分鐘作業(yè)C:90分鐘作業(yè)D:9

24、0分鐘作業(yè)的平均周轉(zhuǎn)時(shí)間為：(70+30+90+90)/4=70分鐘。北京大學(xué)2000年進(jìn)程調(diào)度題對(duì)某系統(tǒng)進(jìn)行監(jiān)測(cè)后表明平均每個(gè)進(jìn)程在I/O阻塞之前的運(yùn)行時(shí)間為T。一次進(jìn)程切換的系統(tǒng)開銷時(shí)間為$若采用時(shí)間片長(zhǎng)度為Q的時(shí)間片輪轉(zhuǎn)法，對(duì)下列各種情況算出CPU利用率。1)Q=s2)Q>T3)S<Q<T答：因?yàn)椋珻PU利用率=進(jìn)程有效運(yùn)行時(shí)間/CPU總時(shí)間=有效運(yùn)行時(shí)間/(有效運(yùn)行時(shí)間+系統(tǒng)開銷)。由于Q=s或Q>T,那么，時(shí)間片足夠大，進(jìn)程每次運(yùn)行總能結(jié)束，故1)和2)兩種情況下，在T+S時(shí)間中，有效運(yùn)行了T。得到CPU禾I用率=T/(T+a。1) Q*CPU利用率=T/(T

25、+S)2) Q>TCPU利用率=T/(T+S)下面一種情況，S<Q<T,也就是說，進(jìn)程完成任務(wù)運(yùn)行過程中共切換了T/Q次，浪費(fèi)時(shí)間為SX(T/Q)。故CPU利用率=T/(T+SX(T/Q),化簡(jiǎn)后得到：3) T>Q>SCPU利用率=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)彳T時(shí)間(分鐘)18:006028:203538:252048:302558:355系統(tǒng)采用SJF調(diào)度算法，作業(yè)被調(diào)度進(jìn)入系統(tǒng)后中途不會(huì)退出，但作業(yè)運(yùn)行時(shí)可被更短作業(yè)搶占。(1)分

26、別給出6個(gè)作業(yè)的執(zhí)行時(shí)間序列、即開始執(zhí)行時(shí)間、均作業(yè)周轉(zhuǎn)時(shí)間。作業(yè)完成時(shí)間、作業(yè)周轉(zhuǎn)時(shí)間。(2)計(jì)算平周轉(zhuǎn)時(shí)間解：需運(yùn)行時(shí)間作業(yè)號(hào)提交時(shí)間開始運(yùn)行時(shí)間被搶占還需運(yùn)行時(shí)間完成時(shí)間J18:00608:004010:35155J28:20358:20309:5595J38:25208:258:4520J48:30259:00259:2555J58:3558:458:5015J68:40108:509:0020說明：(1)采用SJF,J型達(dá)時(shí)搶占J1;J3到達(dá)時(shí)搶占J2。但J4到達(dá)時(shí)，因不滿足SJF故J4不能被運(yùn)行，J3繼續(xù)執(zhí)行5分鐘。(3)注意，是4道的作業(yè)系統(tǒng)，故后面作業(yè)不能進(jìn)入主存而在后備隊(duì)歹!

27、J等待。(4)根據(jù)進(jìn)程調(diào)度可搶占原則，J3第一個(gè)做完。而這時(shí)J5可進(jìn)入主存。因J5最短，故它第二個(gè)完成。這時(shí)J6可進(jìn)入主存。(6)因J6最短，故它第三個(gè)完成。(7)然后是:J4J2和J1T=608:008:208:258:308:358:408:458:509:009:259:5510:35J1J2CPU -| 就緒隊(duì)列I: CPUJ3CPUJ4就緒隊(duì)列 T cpuiJ5后備隊(duì)列CPUJ6后備隊(duì)列；CPU三、同步和互斥類求解同步互斥問題的一些規(guī)律：(1)進(jìn)程同步問題中，管理共享資源常常 設(shè)兩個(gè)信號(hào)量，而進(jìn)程互斥問題中僅需 設(shè)立一個(gè)信號(hào)量。(2) P、V操作要成對(duì)調(diào)用，在進(jìn)程互斥中 是針對(duì)同一個(gè)

28、信號(hào)量進(jìn)行。而在進(jìn)程同 步問題中，進(jìn)入臨界區(qū)前后P、V操作是針對(duì)不同的信號(hào)量的(3)至少有一個(gè)信號(hào)量初值大于等于1(-cpul;i就緒隊(duì)列i：:cpu般指管理共享資源的信號(hào)量），否則進(jìn)程無法被啟動(dòng)運(yùn)行。（4）若有多個(gè)（k）共享資源，則某信號(hào)量初值可設(shè)為k。北京大學(xué)1991年同步與互斥題有一個(gè)倉庫，可以存放A和B兩種產(chǎn)品，但要求： 1） 1）每次只能存入一種產(chǎn)品（A或B）； 2） N<A產(chǎn)品數(shù)量-B產(chǎn)品數(shù)量VM。其中，N和M是正整數(shù)。試用P、V操作描述產(chǎn)品A與產(chǎn)品B的入庫過程。分析及相關(guān)知識(shí)本題給出的第一個(gè)條件是臨界資源的訪問控制，可用一個(gè)互斥信號(hào)量解決該問題。第二個(gè)條件可以分解為：N&l

29、t;A產(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)量來控制A、B產(chǎn)品的存放數(shù)量，sa表示當(dāng)前允許A產(chǎn)品比B產(chǎn)品多入庫的數(shù)量，即在當(dāng)前庫存量和B產(chǎn)品不入庫的情況下，還可以允許sa個(gè)A產(chǎn)品入庫；sb表示當(dāng)前允許B產(chǎn)品比A產(chǎn)品多入庫的數(shù)量，即在當(dāng)前庫存量和A產(chǎn)品不入庫的情況下，還可以允許sb個(gè)B產(chǎn)品入庫。初始時(shí)，sa為M1,sb為N1。當(dāng)往庫中存放入一個(gè)A產(chǎn)品時(shí)，則允許存入B產(chǎn)品的數(shù)量也增加1;當(dāng)往庫中存放入一個(gè)B產(chǎn)品時(shí),則允許存入A產(chǎn)品的數(shù)量也增加1。varmutex：s

30、emaphore=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)品入庫；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個(gè)緩沖區(qū)向進(jìn)程B1,B2,BnZ不斷地發(fā)送消息。發(fā)送和接收工作遵循如下規(guī)則：每個(gè)發(fā)送進(jìn)程一次發(fā)送一個(gè)消息，寫入一個(gè)緩沖區(qū)，緩沖區(qū)大小等于消息長(zhǎng)度；對(duì)每一個(gè)消息，B1,B2,，Bn2都須各接收一次，讀入各自

31、的數(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,-Anl和一組消費(fèi)者B1,B2,-6門2共用m個(gè)緩沖區(qū)，每個(gè)緩沖區(qū)只要寫一次，但需要讀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;em

32、pty中的元素初值為m;數(shù)組full中的元素初值為0。其同步關(guān)系描述如下：varmutex,emptyn2,fulln2：semaphore;inti;mutex=1;for(i=0;i<=n2-1;i+)emptyi=m;fulli=0;main()cobeginA1();A2();IIIIAn1()B1();B2();IIIIBn2();coendsend()/*發(fā)送消息*/inti;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)/

33、*進(jìn)程Bi接收消息*/p(fulli);p(mutex);將消息從緩沖區(qū)取出；V(mutex);V(emtpyi);Ai()/*因發(fā)送進(jìn)程A1,A2,人門的程序類似，這里只給出進(jìn)程Ai的描述*/while(的)IIIIsend();IIIIBi()/*因接收進(jìn)程B1,B2,Bri2程序類似，這里只給出進(jìn)程Bi描述*/while(的)receive(i);IIII北大1995年同步與互斥題有一個(gè)倉庫可存放A、B兩種零件，最大庫容量各為m個(gè)。生產(chǎn)車間不斷地取A和B進(jìn)行裝配，每次各取一個(gè)。為避免零件銹蝕，按先入庫者先出庫的原則。有兩組供應(yīng)商分別不斷地供應(yīng)A和B，每次一個(gè)。為保證配套和合理庫存，當(dāng)某種

34、零件比另一種零件超過n(n<m)個(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ù)量wn;B零件數(shù)量-A零件數(shù)量wn;A零件數(shù)量wm;B零件數(shù)量wm。四個(gè)控制關(guān)系分別用信號(hào)量sa、sb、empty1和empty2實(shí)施。為遵循先入庫者先出庫的原則，A、B零件可以組織成兩個(gè)循形隊(duì)列，并增加入庫指針in1、in2和出庫指針out1、out2來控制順序。并發(fā)程序編制如下：varempty1，empty2，full1，full2：semaphore；mutex，sa，sb：semaphor

35、e；in1，in2，out1，out2：integer；buffer1，buffer2：array0.m-1ofitem；empty1：=empty2：=m；sa：=sb：=n；in1：=in2：=out1：=out2：=0；cobeginprocessproducerArepeatP(empty1)；P(sa)；P(mutex)；buffer1in1：=A零件；in1：=(in1+1)modm；V(mutex)；V(sb)；V(full1)；untilefalse；processproducerBrepeatP(empty2)；P(sb)；P(mutex)；Buffer2in2：=B零件；i

36、n2：=(in2+1)modm；V(mutex)；V(sa)；V(full2)；untilefalse；processtakerepeatP(full1)；P(full2)；P(mutex)；Takefrombuffer1out1andbuffer2out2中的A、B零件；out1：=(out1+1)modm；out2：=(out2+1)modm；V(mutex)；V(empty1)；V(empty2)；把A和B裝配成產(chǎn)品；untilfalsecoend.北大1997年同步與互斥題某高校開設(shè)網(wǎng)絡(luò)課程并安排上機(jī)實(shí)習(xí)，如果機(jī)房共有2m臺(tái)機(jī)器，有2n個(gè)學(xué)生選課，規(guī)定：(1)每?jī)蓚€(gè)學(xué)生分成一組，并占用

37、一臺(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í)離開機(jī)房。試用信號(hào)量和P、V操作模擬上機(jī)實(shí)習(xí)過程。答1：varmutex,enter:semaphore;mutex:=1;enter:=0;finish,test,rc,computercounter:integer;finish:=test:=rc:=0;computercounter:=2m;cobeginprocessstudenti(i=1,2,)beginP(computercounter);/*申請(qǐng)計(jì)算機(jī)P(mutex);rc:=r

38、c+1;/*學(xué)生互斥計(jì)數(shù)ifrc=1thenV(mutex);P(enter);/*若只來一個(gè)學(xué)生，則在enter上等待elserc:=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ī)endprocessteacherbeginP(finish);/*等第一個(gè)學(xué)生實(shí)習(xí)結(jié)束P(finish);/*等第二個(gè)學(xué)生實(shí)習(xí)結(jié)束檢查實(shí)習(xí)結(jié)果;V(test);/*第一個(gè)學(xué)生檢查完成V(test);/*第二個(gè)學(xué)生檢

39、查完成endcoend.答2：varstudent,computer,enter,finish,check:semaphore;student:=enter:=finish:=check:=0;computer:=2m;cobeginprocessstudentbeginV(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;processteacherbeginrepeatP(finish);/*等學(xué)生完成P(f

40、inish);/*等學(xué)生伙伴完成檢查實(shí)習(xí)結(jié)果;V(check);V(ckeck);Untilfalse;end;processmonitorbeginrepeatP(student);/*等學(xué)生到達(dá)P(student);/*等學(xué)生伙伴到達(dá)檢查實(shí)習(xí)結(jié)果;V(enter);/*允許學(xué)生進(jìn)入V(enter);/*允許學(xué)生進(jìn)入U(xiǎn)ntilfalse;end;coend.2000年同步與互斥題桌上有一只盤子，最多可以容納兩個(gè)水果，每次僅能放入或取出一個(gè)水果。爸爸向盤子中放蘋果(apple),媽媽向盤子中放桔子(orange),兩個(gè)兒子專等吃盤子中的桔子，兩個(gè)女兒專等吃盤子中的蘋果。試用PV操作或管程來實(shí)現(xiàn)

41、爸爸、媽媽、兒子、女兒間的同步與互斥關(guān)系。TYPEFMSD=MONITORvarplateARRAY0,1of(apple,orange);count:integer;flag0,flag1:boolean;SP,SS,SD:condition;defineput,get;usewait,signal,check,release；procedureput(varfruit:(apple,orange);begincheck(IM);if(count=2)thenwait(SP,IM)；elseif(flag0=false)thenplate0:=fruit;flag0:=true;elsepl

42、ate1:=fruit;flag1:=true;count:=count+1;if(fruit=orange)thensignal(SS,IM)；elsesignal(SD,IM);release(IM);end;procedureget(varfruit:(apple,orange),x:plate);begincheck(IM);if(count=0)orplate<>fruitthenbeginif(fruit=orange)thenwait(SS,IM)；elsewait(SD,IM)；end;count:=count-1;if(flag0&plate0=fruit

43、)thenx:=plate0;flag0:=false;elsex:=plate1;flag1:=false;signal(SP,IM);release(IM);end;begincount:=0;flag0:=false;flag1:=false;SP:=0;SS:=0;SD:=0；plate0:=plate1:=null;end;main()cobeginprocessfatherbeginwhile(1)準(zhǔn)備好蘋果;call(apple);end;processmotherbeginwhile(1)準(zhǔn)備好桔子;call(orange);end;processsonbeginwhile(1

44、)call(orange,x);吃取到的桔子end;processdaughterbeginwhile(1)call(apple,x);吃取到的蘋果;end;coend南京大學(xué)2000年同步與互斥題某工廠有兩個(gè)生產(chǎn)車間和一個(gè)裝配車間，兩個(gè)生產(chǎn)車間分別生產(chǎn)A、B兩種零件，裝配車間的任務(wù)是把A、B兩種零件組裝成產(chǎn)品。兩個(gè)生產(chǎn)車間每生產(chǎn)一個(gè)零件后都要分別把它們送到裝配車間的貨架F1、F2上，F(xiàn)1存放零件A,F2存放零件B,F1和F2的容量均為可以存放10個(gè)零件。裝配工人每次從貨架上取一個(gè)A零件和一個(gè)B零件，然后組裝成產(chǎn)品。請(qǐng)用：(1)信號(hào)量和P、V操作進(jìn)行正確管理，(2)管程進(jìn)行正確管理。答：(1)

45、 信號(hào)量和P、V操作進(jìn)行正確管理。varF1,F2:ARRAY0.9ofitem;SP1,SP2,SI1,SI2:semaphore;in1,in2,out1,out2:integer;in1:=0;in2:=0;out1:=0;out2:=0;SP1:=10;SP2:=10;SI1:=0;SI2:=0;main()cobeginproducer1();producer2();installer()coendprocessproducer1()beginwhile(true)produceA零件;P(SP1);F1in1:=A;in1:=(in1+1)MOD10V(SI1);endproces

46、sproducer2()beginwhile(true)produceB零件;P(SP2);F2in2:=B;in2:=(in2+1)MOD10V(SI2);endprocessinstaller()varproduct:item;beginwhile(true)P(SI1);product1:=F1out1;out1:=(out1+1)MOD10;V(SP1);P(SI2);product2:=F2out2;out2:=(out2+1)MOD10;V(SP2);組裝產(chǎn)品;end(2) 管程進(jìn)行正確管理。TYPEproduceprodut=monitorVARF1,F2:ARRAY0.9ofi

47、tem;SP1,SP2,SG1,SG2:semaphore;SP1_count,SP2_count,SG1_count,SG2_count:integer;in1,in2,out1,out2:integer;inc1,inc2:integer;DEFINEput1,put2,get;USEwait,signal;procedureput1(A);beginifinc1=10thenwait(SP1,SP1_count,IM);inc1:=inc1+1;F1in1:=A;in1:=(in1+1)MOD10signal(SG1,SG1_count,IM);end;procedureput2(B);

48、beginifinc2=10thenwait(SP2,SP2_count,IM);inc2:=inc2+1;F2in2:=B;in2:=(in2+1)MOD10signal(SG2,SG2_count,IM)end;procedureget(A,B);beginifinc1=0thenwait(SG1,SG1_count,IM);ifinc2=0thenwait(SG2,SG2_count,IM);inc1:=inc1-1;inc2:=inc2-1;A:=F1out1;out1:=(out1+1)MOD10B:=F2out2;Out2:=(out2+1)MOD10signal(SP1,SP1_

49、count,IM);signal(SP2,SP2_count,IM);end;beginin1:=0;in2:=0;out1:=0;out2:=0;inc1:=0;inc2:=0;end.cobeginprocessProduce1beginwhile(true)produceA零件;P;call(A);if_count>0thenV;elseV;end;processProduce2beginwhile(true)produceB零件;P;call(B);if_count>0thenV;elseV;end;processconsumebeginwhile(true)P;call(

50、A,B);if_count>0thenV;elseV;組裝產(chǎn)品;end;coend.在pipeline通信機(jī)制中，試用PV操作描述讀寫進(jìn)程訪問管道文件的過程。假設(shè)管道文件的大小為10KB。解：原理略。varpipe:array09ofkilobytes;ts,length,in,out:integer;empty,full,mutex1,mutex2:semaphore;ts:=10;in:=out;=0;empty:=10;full:=0;mutex1:=mutex2:=1;cobeginprocesspipe-writerbeginL1;proceduredata;P(empty);Length尸datalength;/*以KB計(jì)算數(shù)據(jù)塊數(shù)while(length>0andts>0)beginpipein:=dataof1KB/*寫1KB長(zhǎng)數(shù)據(jù)in:=(in+1)mod10;ts:=ts-1;length:=length-1;endV(full);end;GotoL1;endprocesspipe-readerbeginL2:P(full);takeadatafrompipeout;out:=(out+1)mod10ts:=ts+1;V(empty);GotoL2;endcoend.華中科技大2002同步互斥題（理發(fā)師問題）復(fù)印室有一個(gè)操作員為顧客復(fù)印資