1-7章典型例題-v1講解1

.(5points)ThereexisttwoprocessesP1andP2inamultiprogrammingbatchsystem.P2entersintothesystem10mslaterthanP1,andtheirexecutingtraces,i.e.alternatingsequencesofCPUburstsandI/Obursts,areasfollows:P1:computing,80ms口I/Ooperation,100ms口computing,40msP2:computing,130ms口I/Ooperation,50ms口computing,50msItisassumedthattimecostsofCPUschedulingandprocessswitchareomitted,whatisthemaximalthroughputforcompletingthesetwoprocesses,andwhy?Answers：□□□□□=2/(80+130+50+50)=2/310=1/155個(gè)/ms(3points)2.當(dāng)斗P2.當(dāng)斗P2的CPU計(jì)算和I/O操作最大程度并行執(zhí)行時(shí)，2個(gè)進(jìn)程總的執(zhí)行時(shí)間最短，系統(tǒng)吞吐量達(dá)到最大，如下圖所示；(2points)40msCInacomputersystem,theuserssubmittothesystemtheircomputationaltasksasjobs,andallthesejobsarethenstoredasthestandbyjobsonthedisk.Thejobscheduler(alsoknownaslong-termscheduler)selectsthestandbyjobsonthedisk,createsnewprocessesinmemoryforthem,andthenstartsexecutingoftheseprocesses.Eachjob’sIDisthesameasthatoftheprocesscreatedforit,forexample,JiandPi.Whenthenumberofconcurrentprocessesinmemoryislowerthanthree,thejobschedulertakestheFCFSalgorithmtoselectastandbyjobonthedisktocreateanewprocess.Otherwise,thejobsshouldwaitonthedisk.,Fortheprocessesinmemory,theprocessscheduler(alsoknownasshort-termscheduler)takesthenon-preemptivepriority-basedalgorithmtoselectaprocessandallocatestheCPUtoit.Itisassumedthesystemcostsresultingfromjobandprocessschedulingareomitted.ConsiderthefollowingsetofJobsJ1,J2,J3,J4andJ5.For1<i<5,thearrivaltimeofeachJi,thelengthoftheCPUbursttimeofeachprocessPi,andtheprioritynumberforeachJi/Piaregivenasbelow,andasmallerprioritynumberimpliesahigherpriority.JobArrivalTimeBurstTime(minute)PriorityNumberJ114:00404J214:2030.012J314:3050.013J414:5020.015J515:0510.015Illustratetheexecutionofeachjob/processbycharts.Whatistheturnaroundtimeofeachjob?Whatisthewaitingtimeofeachjob?Note:Thewaitingtimeofajobincludesthetimeitwaitsonthediskandthatit(asaprocess)waitsinmemory.Answer:（1）J/P:J,P11111-14:0014:40J/P:1P/J1P122122|2||.14:0014:2014:4015:10.01J3/P/1P3/J31P31?14:0014:3015:10.0116:00.02J4/P4：1P4/J41P41.14:0014:5016:00.0216:20.03注：圖中Ji部分表示作業(yè)被調(diào)入內(nèi)存，Pi表示進(jìn)程被調(diào)度執(zhí)行。J1到達(dá)時(shí)，內(nèi)存中并發(fā)進(jìn)程數(shù)=0<3,，作業(yè)被直接調(diào)入內(nèi)存，創(chuàng)建進(jìn)程P1;P1被調(diào)度程序選中，開始執(zhí)行。在P1執(zhí)行過程中，J2到達(dá)，內(nèi)存中并發(fā)進(jìn)程數(shù)=1<3,作業(yè)被直接調(diào)入內(nèi)存，創(chuàng)建進(jìn)程P2；此時(shí)P1在執(zhí)行，由于采用非搶占式進(jìn)程調(diào)度，P2處于就緒等待狀態(tài)。在P1執(zhí)行過程中，J3到達(dá)，內(nèi)存中并發(fā)進(jìn)程數(shù)=2<3,作業(yè)被直接調(diào)入內(nèi)存，創(chuàng)建進(jìn)程P3,等待P2執(zhí)行完畢。P1結(jié)束后，作業(yè)J1隨之結(jié)束，系統(tǒng)內(nèi)有作業(yè)J2、J3對(duì)對(duì)應(yīng)的進(jìn)程P2、P3。進(jìn)程調(diào)度選擇高優(yōu)先級(jí)的P2開始執(zhí)行。P2執(zhí)行過程中，J4到達(dá)時(shí)，內(nèi)存中并發(fā)進(jìn)程數(shù)=2<3,作業(yè)被直接調(diào)入內(nèi)存，創(chuàng)建進(jìn)程P4,等待P2執(zhí)行完畢。P2執(zhí)行過程中，J5到達(dá)時(shí)，內(nèi)存中并發(fā)進(jìn)程數(shù)=3,必須等到P2結(jié)束后，系統(tǒng)內(nèi)并發(fā)進(jìn)程數(shù)<3,方能創(chuàng)建進(jìn)程P5。P2執(zhí)行完畢后，系統(tǒng)內(nèi)有2個(gè)作業(yè)J3、J4對(duì)應(yīng)的進(jìn)程P3、P4,內(nèi)存中并發(fā)進(jìn)程數(shù)=2<3。此時(shí)，長(zhǎng)期調(diào)度程序首先為作業(yè)J5創(chuàng)建進(jìn)程P5。然后，進(jìn)程調(diào)度程序從P3、P4、P5中，選擇高優(yōu)先級(jí)的P3開始執(zhí)行。P3執(zhí)行完畢后，系統(tǒng)內(nèi)有2個(gè)作業(yè)J4、J5對(duì)應(yīng)的進(jìn)程P4、P5,2者的優(yōu)先級(jí)相同，按照FCFS原則，P4先執(zhí)行。P4執(zhí)行完畢后，剩余的唯一進(jìn)程P5開始執(zhí)行。（2）J1：T1=40（min）J2：T2=20+30.01=50.01（min）J3：T3=40.01+50.01=90.02（min）J4：T4=70.02+20.01=90.03（min）J5：T5=5.01+70.02+10.01=85.04（min）（3）J1：W1=0（min）J2：W2=20（min）J3：W3=40.01（min）J4：W4=70.02（min）J5：W5=75.03（min）3.某多道程序設(shè)計(jì)系統(tǒng)供用戶使用的主存為100K，磁帶機(jī)2臺(tái)，打印機(jī)1臺(tái)。采用可變分區(qū)內(nèi)存管理，采用靜態(tài)方式分配外圍設(shè)備（以先申請(qǐng)先滿足、非搶占方式分配磁帶機(jī)、打印機(jī)），忽略作業(yè)I/O時(shí)間?，F(xiàn)有作業(yè)序列如下:作業(yè)號(hào)進(jìn)入輸入井時(shí)間運(yùn)行時(shí)間主存需求量磁帶機(jī)需求量打印機(jī)需求量18:0025分鐘15K1128:2010分鐘30K0138:2020分鐘60K1048:3020分鐘20K1058:3515分鐘10K11作業(yè)調(diào)度采用FCFS策略，優(yōu)先分配主存低地址區(qū)，且不準(zhǔn)移動(dòng)已在主存的作業(yè)，在主存中的各作業(yè)平分CPU時(shí)間（時(shí)間片輪轉(zhuǎn)法）?，F(xiàn)求：作業(yè)被調(diào)度的先后順序全部作業(yè)運(yùn)行結(jié)束的時(shí)間作業(yè)平均周轉(zhuǎn)時(shí)間最大作業(yè)周轉(zhuǎn)時(shí)間答案：本題綜合了作業(yè)調(diào)度、進(jìn)程調(diào)度、對(duì)外設(shè)競(jìng)爭(zhēng)、對(duì)主存競(jìng)爭(zhēng)。作業(yè)調(diào)度選擇的作業(yè)順序?yàn)椋鹤鳂I(yè)1、作業(yè)3、作業(yè)4、作業(yè)2、作業(yè)5全部作業(yè)運(yùn)行結(jié)束的時(shí)間為9:30周轉(zhuǎn)時(shí)間：作業(yè)1為30分鐘，作業(yè)2為55分鐘，作業(yè)3為40分鐘，作業(yè)4為40分鐘，作業(yè)5為55分鐘平均作業(yè)周轉(zhuǎn)時(shí)間為44分鐘最大作業(yè)周轉(zhuǎn)時(shí)間為55分鐘調(diào)度過程描述：8:00作業(yè)1到達(dá)，占有資源(內(nèi)存、磁帶機(jī)、打印機(jī))，并調(diào)入內(nèi)存運(yùn)行；8:20作業(yè)2、3同時(shí)到達(dá)，但作業(yè)2因?yàn)榉植坏酱蛴C(jī)，只能在后備隊(duì)列中等待。作業(yè)3所需資源（內(nèi)存，磁帶機(jī)）滿足，調(diào)入內(nèi)存運(yùn)行；此時(shí)，作業(yè)1還需5分鐘CPU時(shí)間，但由于采用時(shí)間片分時(shí)調(diào)度，作業(yè)2與作業(yè)1平分CPU時(shí)間，作業(yè)1還需運(yùn)行10分鐘。8:30作業(yè)1在8:30結(jié)束，釋放磁帶機(jī)與打印機(jī)。但作業(yè)2仍不能執(zhí)行，因?yàn)榉峙浣o作業(yè)3的內(nèi)存無法壓縮、移動(dòng)，當(dāng)前主存內(nèi)沒有30K的空閑區(qū)域，無法滿足作業(yè)2的內(nèi)存要求。8:30作業(yè)4到達(dá)，并進(jìn)入內(nèi)存執(zhí)行，與作業(yè)3分享CPU。8:35作業(yè)5到達(dá)，因?yàn)榉植坏酱蛴C(jī)、磁帶機(jī)，只能在后備隊(duì)列等待。9:00作業(yè)3運(yùn)行結(jié)束，釋放磁帶機(jī)。此時(shí)，作業(yè)2的主存、打印機(jī)需求均可滿足，作業(yè)2投入運(yùn)行；作業(yè)5到達(dá)時(shí)間晚，只能等待。9:10作業(yè)4運(yùn)行結(jié)束，作業(yè)5因?yàn)槿匀环植坏酱蛴C(jī)，只能在后備隊(duì)列中等待。9:15作業(yè)2運(yùn)行結(jié)束，作業(yè)5投入運(yùn)行9:30全部作業(yè)執(zhí)行結(jié)束。Consideringareal-timesystem,inwhichthereare4real-timeprocessesP1,P2,P3andP4thatareaimedtoreactto4criticalenvironmentaleventse1,e2,e3ande4intimerespectively.Thearrivaltimeofeacheventei,1口i口4,(thatis,thearrivaltimeoftheprocessPi),thelengthofthebursttimeofeachprocessPi,andthedeadlineforeacheventeiaregivenbelow.Here,thedeadlineforeiisdefinedastheabsolutetimepointbeforewhichtheprocessPimustbecompleted.Thepriorityforeacheventei(alsoforPi)isalsogiven,andasmallerprioritynumberimpliesahigherpriority.EventsProcessArrivalTimeBurstTimePrioritiesDeadlinee1P10.004.0037.00e2P23.002.0015.50e3P34.002.00412.01e4P46.004.00211.00Supposethatpriority-basedpreemptiveschedulingisemployed,DrawaGanttchartillustratingtheexecutionoftheseprocessesWhataretheaveragewaitingtimeandtheaverageturnaroundtimeWhicheventwillbetreatedwithintime?SupposethatFCFSschedulingisemployed,DrawaGanttchartillustratingtheexecutionoftheseprocessesWhataretheaveragewaitingtimeandtheaverageturnaroundtimeWhicheventwillbetreatedwithintime,thatis,theprocessreactingtothiseventwillbecompletedbeforeitsdeadline?Answers:(1)甘特圖如下平均等待時(shí)間=[(5-3)+(3-3)+(10-4)+(6-6)]/4=2平均周轉(zhuǎn)時(shí)間=[(6-0)+(5-3)+(12-4)+(10-6)]/4=5根據(jù)各進(jìn)程的完成時(shí)間點(diǎn)和所對(duì)應(yīng)的事件的deadline可知，全部4個(gè)事件均可得到及時(shí)響應(yīng)．(2)甘特圖如下PlP2P3P4046812平均等待時(shí)間=[(0—0)+(4-3)+(6T)+(8-6)]/4=1.25平均周轉(zhuǎn)時(shí)間=[(4-0)+(6-3)+(8-4)+(12-6)]/4=4.25根據(jù)各進(jìn)程的完成時(shí)間點(diǎn)和所對(duì)應(yīng)的事件的deadline可知，事件e1和e3可得到及時(shí)響應(yīng)．Asillustratedinthefigure,onthetwosidesofaone-plankbridge(獨(dú)木橋),therearetwogroupsofsoldiersthatarecomposedofmandnpeoplerespectivelyandneedtocrossthebridge,butthenarrowbridgeallowsonlyonegroupofthesoldiersinthesamedirectiontocrossatthesametime.Onegroupofthesoldiersispermittedtocrossaslongastherearenopeopleonthebridge.Onceonegroupofthesoldiersbeginswalkingonthebridge,theothergroupshouldbewaitingtostartcrossinguntilallmembersofthefirstgrouphavepassedthebridge.Pleasedesigntwosemaphore-basedprocessestodescribethecrossingactionsofthesoldiersinthetwogroups.Itisrequiredtodefinethesemaphoresandvariablesneeded,explaintheirroles?,andgivetheirinitialvalues;andtoillustratethestructuresofprocessesforthesoldiersineachgroup.Answers:該問題可歸結(jié)為讀寫者問題，但2隊(duì)士兵均為讀者。(1)定義2個(gè)整型變量countl、count2,分別用于計(jì)數(shù)每組士兵過橋人數(shù)。定義2個(gè)二元信號(hào)量mutexl、mutex2，用于控制對(duì)countl、count2的互斥訪問。定義二元信號(hào)量bridge，用于2隊(duì)士兵間的互斥。初始化：count1=0，count2=0；mutex1=1、mutex2=1；bridge=1；(2)P1(){wait(mutex1);count1++;ifcount1==1wait(bridge);//該組第1個(gè)士兵過橋時(shí)，阻塞另一組過橋signal(mutex1);crossingthebridge;wait(mutex1);count1--;ifcount1==0signal(bridge);//該組最后1個(gè)士兵過橋后，允許另一組過橋signal(mutex1);}.P2(){wait(mutex2);count2++;ifcount2==1wait(bridge);//該組第1個(gè)士兵過橋時(shí)，阻塞另一組過橋signal(mutex2);crossingthebridge;wait(mutex2);count2--;ifcount2==0signal(bridge);//該組最后1個(gè)士兵過橋后，允許另一組過橋signal(mutex2);}.6.Considerthebounded-buffer(alsoknownasproducer-consumerproblem).Thereareseveralproducerprocessesandconsumerprocesses,andtheseprocessesshareapoolofbuffer.Thepoolofbufferconsistsofnbuffers,andeachbuffercanholdonlyoneitem.Theproducerprocessproducesoneitemandputsitintoanemptybufferinthepool.Theconsumerprocesstakesoneitemfromafullbufferinthepoolandconsumesthisitem.Ateachmoment,atmostoneproducerprocessandatmostoneconsumerprocessarepermittedtosimultaneouslyoperateonthebufferpool,i.e.,oneproducerprocessispermittedtoaccessthebufferlonelyoneconsumerprocessispermittedtoaccessthebufferlonelyiftwoormoreprocesseswanttoaccessthebuffersimultaneously,twoormoreproducerprocessesarenotpermittedtosimultaneouslyoperateonthebuffer,theyshouldaccessthebuffermutualexclusivelytwoormoreconsumerprocessesarealsonotpermittedtosimultaneouslyoperateonthebuffer,theyshouldaccessthebuffermutualexclusivelyonlyoneproducerprocessandoneconsumerprocessareallowedtosimultaneouslyoperateondifferentitemsinthebufferWriteanalgorithmtosynchronizeproducerprocessesandconsumerprocessesbyusingsemaphores.Answer1:Principles:definethesemaphoresemptyandfulltocountthenumberofemptybuffersandfullbuffersinthepool,respectively;definebinarysemaphoremutex1tocontrolallproducerstoaccesstheemptybuffersinthepoolmutualexclusively;definebinarysemaphoremutex2tocontrolallconsumerstoaccessthefullbuffersinthepoolmutualexclusively;AlgorithmSemaphoresempty,fullBinarysemaphoresmutex1,mutex2Initially,empty:=n;full:=0;mutex1:=1;mutex2:=2;Thestructureoftheproducerprocessisasfollows:do{…produceaniteminnextp…wait(empty);wait(mutex1);searchforanemptybuffer…addnextptotheemptybuffer…signal(mutex1);signal(full);}while(1);Thestructureoftheconsumerprocessisasfollows:do{…wait(full);wait(mutex2);searchforanfullbuffer…removeiteminbuffer[j]tonext;….signal(mutex2);signal(empty);…consumetheiteminnextc…}while(1);Answer2:Semaphoresempty,full;Binarysemaphoresmutex1,mutex2,mutex;ArrayFlag[n];/*Flag[i]=0indicatesthatbuffer[i]isempty,Flag[i]=1indicatesthatbuffer[i]isfull,0<iWn-1;*/Initially,empty:=n;full:=0;mutex1:=1;mutex2:=1;mutex=1;Flag[i]=0,0WiWn-1;Thestructureoftheproducerprocessisasfollows:do{…produceaniteminnextp…wait(empty);wait(mutex1);wait(mutex);searchonarrayFlagforanemptybuffer[i],whereFlag[i]=0;signal(mutex);…addnextptotheemptybuffer[i];wait(mutex);Flag[i]:=1;signal(mutex);signal(mutex1);signal(full);…}while(1);Thestructureoftheconsumerprocessisasfollows:do{…wait(full);wait(mutex2);wait(mutex);searchonarrayFlagforanfullbuffer[j],whereFlag[j]=1;signal(mutex);removeiteminbuffer[j]tonext;wait(mutex);Flag[j]:=0;signal(mutex);signal(mutex2);signal(empty);…consumetheiteminnextc…}while(1);7.有1個(gè)倉庫，可以存放X、丫兩種產(chǎn)品，倉庫容量足夠大，但要求:1）每次只能存入一種產(chǎn)品X或Y,2）滿足一N<X產(chǎn)品數(shù)量一Y產(chǎn)品數(shù)量<M，M、N為正整數(shù)。用信號(hào)量實(shí)現(xiàn)產(chǎn)品X、Y的入庫過程。Answers：產(chǎn)品數(shù)量制約條件：X產(chǎn)品數(shù)量一Y產(chǎn)品數(shù)量＜MX產(chǎn)品數(shù)量一Y產(chǎn)品數(shù)量＞—N設(shè)置2個(gè)信號(hào)量控制X、Y的數(shù)量：1)sx表示當(dāng)前允許X產(chǎn)品比Y產(chǎn)品多入庫的數(shù)量，即在當(dāng)前庫存量和Y產(chǎn)品不入庫的情況下，還可以允許sx個(gè)X產(chǎn)品入庫；初始時(shí)，若不放Y而僅放X產(chǎn)品，則sx最多為M—1個(gè)。2)sy表示當(dāng)前允許Y產(chǎn)品比X產(chǎn)品多入庫的數(shù)量，即在當(dāng)前庫存量和X產(chǎn)品不入庫的情況下，還可以允許sy個(gè)Y產(chǎn)品入庫；初始時(shí)，若不放X而僅放Y產(chǎn)品，則sy最多為N—1個(gè)。當(dāng)往庫中放入一個(gè)X產(chǎn)品時(shí)，則允許存入Y產(chǎn)品的數(shù)量加1,故信號(hào)量sy應(yīng)加1；當(dāng)往庫中放入一個(gè)Y產(chǎn)品時(shí)，則允許存入X產(chǎn)品的數(shù)量加1,故信號(hào)量sx應(yīng)加1；Mutex：semaphore=1互斥信號(hào)量sx,sy:semaphoresx=M-1,sy=N-1ProcessXRepeatWait(sx)Wait(mutex)將X入庫Signal(mutex)Signal(sy)UntilfalseProcessYRepeatWait(sy)Wait(mutex)將Y入庫Signal(mutex)Signal(sx)UntilfalseHerearethreeworkersW1,W2andW3.W1andW2areresponsibleforproducingthepart(零件)P1andpartP2respectively,andW3takeschargeofassembling(裝配)thepartP3.W1producesoneP1andthenputsitintothecargotank(貨箱)T1;W2manufacturesoneP2andthenputsitintothecargotankT2.W3takesP1fromT1andP2fromT2,andthenassemblesP1andP2intoP3.Itisassumedthat(1)T1canhold8partsofP1,andT2canhold10partsofP2,andtheyareallinitiallyempty;(2)eachtimeW3cantakesonlyonepartofP1fromT1andonepartofP2fromT2,andthenassemblesonepartofP3;(3)T1andT2arepermittedonlytobetakenorputinthemutuallyexclusivemode,thatis,atanytimeonlyoneworkerareallowedtooperateonT1orT2.PleasedesignthreesemaDhore-basedprogramsforW1,W2andW3,todescribetheirproductionactivities.Itisrequiredtodefinethesemaphoresforsynchronizingthethreeprocesses,explaintheroleofeachsemaphore,andgivetheirinitialvalues;andtoillustratethestructuresofprocessesforW1,W2andW3.Answers:(1)信號(hào)量定義：Binarysemaphoremutex1,mutex2Semaphoreempty1,full1,empty2,full2信號(hào)量含義：mutexl用于控制W1和W2對(duì)T1的互斥訪問，mutex2用于控制W1和W3對(duì)T2的互斥訪問；emptyl和empty2分別表示T1和T2中的空閑容量，fulll和full2分別表示T1和T2中已經(jīng)被占用的容量。信號(hào)量初值：mutex1=1;mutex2=1;empty1=8;empty2=10;full1=0;full2=0;W1：ProduceoneP1;Wait(empty1);Wait(mutex1);PutsitintoT1,Signal(mutex1);Signal(full1);W2：ProduceoneP2;Wait(empty2);Wait(mutex2);PutsitintoT2,Signal(mutex2);Signal(full2);W3：Wait(full1);Wait(mutex1);takesoneP1fromT1;Signal(mutex1);Signal(empty1);Wait(full2);Wait(mutex2);takesoneP2fromT2;Signal(mutex2);Signal(empty2);AssemblesP1andP2intoP3.Inadatacollectionsystem,thereareadatacollectionprocess,adatamanipulationprocess,andadataoutputprocess.TheDatacollectionprocessputsoneunitofdatacollectedintoBuffer1,thedatamanipulationprocessgetsoneunitofdatafromBuffer1tomanipulateandputstheresultsintoBuffer2,andthenthedataoutputprocessgetsoneunitofdatafromBuffer2,andoutputsthem.ItisassumedthatBuffer1cankeepthreeunitsofdataandBuffer2cankeeptwounitsofdataatmost.Definethesemaphoresusedtosynchronizethethreeprocesses,andsettheirinitialvalues.Pleasedesignthreeprocessesforthedatacollectionprocess,thedatamanipulationprocess,andthedataoutputprocessrespectivelybyusingsemaphoresdefinedin1).Answers:(4points)binarysemaphoremutex1,mutex2semaphorefull1,full2,empty1,empty2mutex1=1;mutex2=1;empty1=3;full1=0;empty2=2;full2=0;(4x3=12points)thecollectionprocess:collectoneunitofdata;wait(empty1);wait(mutex1);putthedataintobuffer1;signal(mutex1);signal(full1);themanipulatingprocess:wait(full1);wait(mutex1);removeoneunitofdatafrombuffer1;signal(mutex1);signal(empty1);manipulatethedata;wait(empty2