计算机操作系统第三版答案完整版(汤晓丹 梁红兵 哲凤屏 汤子瀛)

121OS12342OS1OS2OS3OS3OSOSI/OOS412345I/OI/OI/O3I/O6CPU78OSOS910816CP/MMS-DOS.411WindowsOS1MicrosoftWindows1.02Windows9516/32323Windows9816/32Windows4WindowsXPWindows2000Luna5WindowsVistaWindowsAeroWindowsIndexingService1211002313OS514______________1215?3/4807G093/4816::I/OI/OCPUI/OI/OI/O.617/18191OSOS“”220OS/C/S⑴⑵⑶⑷21OS12/3422OSOS72324123451.(PrecedenceGraph)DAG(DirectedAcyclicGraph)2.:S1=a=x+y;S2=b=z+1;S3=c=a–bS4=w=c+1;3.845?:6?(1)(2)OS(3)7PCBPCBPCBOSPCB81→CPU2→93→I/O4→I/O9:5/4807G095/481012341112I/O131OSCreat()2PCB10345.141PCBPCB2345PCB15a.b.c.d..161ABABABA2ABABABA1117“”“”18.19.waitsignalwait(S)S.value0waitS.value:=S.value-1S.value0blockS.Lsignal(S)signalS.value:=S.value+11S.value≤0wakeupS.L20“”21mutex121CSwait(mutex)signal(mutex)mutexwaitwaitmutexwaitmutexsignalVarmutex:semaphore:=1beginparbeginprocess1:beginrepeatwait(mutex)criticalsectionsignal(mutex)remaindersectionuntilfalseendprocess2:beginrepeatwait(mutex)criticalsectionsignal(mutex)remaindersectionuntilfalseendparend13222-17aVara,b,c,d,e,f,g,h;semaphore:=0,0,0,0,0,0,0,0;beginparbeginbeginS1;signal(a);signal(b);end;beginwait(a);S2;signal(c);signal(d);end;beginwait(b);S3;signal(e);end;beginwait(c);S4;signal(f);end;beginwait(d);S5;signal(g);end;beginwait(e);S6;signal(h);end;beginwait(f);wait(g);wait(h);S7;end;parendendbVara,b,c,d,e,f,g,h,i,j;semaphore:=0,0,0,0,0,0,0,0,0,0;beginparbeginbeginS1;signal(a);signal(b);end;beginwait(a);S2;signal(c);signal(d);end;beginwait(b);S3;signal(e);signal(f);end;beginwait(c);S4;signal(g);end;beginwait(d);S5;signal(h);end;beginwait(e);S6;signal(i);end;beginwait(f);S7;signal(j);end;beginwait(g);wait(h);wait(i);wait(j);S8;end;parendend23signal(full)signal(empty),signal(full)full14full0wait(full)signal(empty)nempty=0full=nemptyempty0n24waitwait(full)wait(mutex)signal(mutex)signalfullwait(full)wait(mutex)wait(mutex)wait(empty)signal(empty)signal(mutex)wait(mutex)signal(mutex)signal(full)25WW=1W=0lock(W):whileW=1dono-opW:=1;unlock(W):W:=0;lock(W):W:=W+1;if(W1)thenblock(W,L)unlock(W):W:=W-1;if(W0)thenwakeup(W,L)VarW:semaphore:=0begin15repeatlock(W);criticalsectionunlock(W);remaindersectionuntilfalse;end26:producer:beginrepeat…produceraniteminnextp;wait(mutex);wait(full);/*wait(empty),wait(mutex)*/buffer(in):=nextp;/*:in:=(in+1)modn;*/signal(mutex);/*signal(full);*/untilfalse;endconsumer:beginrepeatwait(mutex);wait(empty);/*wait(full),wait(mutex)*/nextc:=buffer(out);out:=out+1;/*:out:=(out+1)modn;*/signal(mutex);/*signal(empty);*/consumeriteminnextc;untilfalse;end27.Varchopstick:array[0,…,4]ofsemaphore;1i16RepeatWait(chopstick[i]);Wait(.chopstick[(i+1)mod5]);…Ea.t;…Signal(chopstick[i]);Signal(chopstick[(i+1)mod5])Ea.t;…Think;Untilfalse;28.a.Varmutex,empty,full:semaphore:=1,1,0;gather:beginrepeat……gatherdatainnextp;wait(empty);wait(mutex);buffer:=nextp;signal(mutex);signal(full);untilfalse;endcompute:beginrepeat……wait(full);wait(mutex);nextc:=buffer;signal(mutex);signal(empty);computedatainnextc;untilfalse;endb.Varempty,full:semaphore:=1,0;gather:17beginrepeat……gatherdatainnextp;wait(empty);buffer:=nextp;signal(full);untilfalse;endcompute:beginrepeat……wait(full);nextc:=buffer;signal(empty);computedatainnextc;untilfalse;end29condition3018ProclucerConsumer1Putitemcountcount≥n2getitemcount≤0PCtypeproducer-consumer=monitorVarin,out,count:integer;buffer:array[0,…,n-1]ofitem;notfullnotempty:condition;procedureentrydot(item)beginifcount=nthennotfull.wait;buffer(in):=nextp;in:=(in+1)modn;count:=count+1;ifnotempty.queuethennotempty.signal;endprocedureentryget(item)beginifcount=0thennotfull.wait;nextc:=buffer(out);out:=(out+1)modn;count:=count-1;ifnotfull.quenethennotfull.signal;endbeginin:=out:=0;count:=0endproducer:beginpepeatproduceanineminnestpPC.put(item);untilfalse;endconsumer:begin19repeatPC.get(item);consumetheiteminenxtc;untilfalse;end31ANDANDwaitAND:varmutex,empty,full:semaphore:=1,n,0;buffer:array[0,...,n-1]ofitem;in,out:integer:=0,0;beginparbeginproducer:beginrepeat…produceaniteminnextp;…wait(empty);wait(s1,s2,s3,...,sn);//s1,s2,...,snemptywait(mutex);buffer(in):=nextp;in:=(in+1)modn;signal(mutex);signal(full);signal(s1,s2,s3,...,sn);untilfalse;endconsumer:beginrepeatwait(full);wait(k1,k2,k3,...,kn);//k1,k2,...,knfullwait(mutex);nextc:=buffer(out);out:=(out+1)modn;signal(mutex);20signal(empty);signal(k1,k2,k3,...,kn);consumetheiteminnextc;untilfalse;endparendend32ANDVarRNinteger;L,mx:semaphore:=RN,1;beginparbeginreader:beginrepeatSwait(L,1,1);Swait(mx,1,1);…performreadoperation;…Ssignal(L,1);untilfalseendwriter:beginrepeatSwait(mx,1,1;L,RN,0);performwriteoperation;Ssignal(mx,1);untilfalseendparendend33342135123436OSOSCPU,371)23438.1OS23439.OS401222OS411242“”“”LWPLWP43PTDATCBTCBTCBPTDATCBTCBTCB12323JCBJCBJCB1)2)3)4)CPUI/O5)6)7)8)9)10)11)12)4:51236247128EDFLLF910FCFSSPFFCFS//SPF//112512/1312312…n14CPU15163-91123321263423423-9EDF17()200ms100ms100ms()100ms400ms150ms250ms1819201“”272“”3“”21P0Request(0,2,0)Request(0,1,0)()11057T02Requst0(0,1,0)=Need0(7,4,3);Requst0(0,1,0)=Available(2,3,0);P0Available0Allocation0Need03P0P0R