操作系统第7章

Chapter7:ProcessSynchronizationBackground背景TheCritical-SectionProblem临界区的问题SynchronizationHardware同步硬件Semaphores信号量ClassicalProblemsofSynchronization同步的经典问题CriticalRegions临界区Monitors管程Background不是一个人在战斗，关键区域只能一个人战斗Concurrentaccesstoshareddatamayresultindatainconsistency.对共享数据区的并发访问导致数据的不一致性Maintainingdataconsistencyrequiresmechanismstoensuretheorderlyexecutionofcooperatingprocesses.维持数据的一致性要求保证合作进程按一定的顺序执行的机制。Shared-memorysolutiontobounded-bufferproblem(Chapter4)allowsatmostn–1itemsinbufferatthesametime.Asolution,whereallNbuffersareusedisnotsimple.Supposethatwemodifytheproducer-consumercodebyaddingavariablecounter,initializedto0andincrementedeachtimeanewitemisaddedtothebufferBackground进程的同步隐含了系统中并发进程之间存在的两种相互制约关系：竞争（互斥）与协作（同步）互斥：两个并行的进程A、B，如果当A进行某个操作时，B不能做这一操作，进程间的这种限制条件称为进程互斥，这是引起资源不可共享的原因。同步：我们把进程间的这种必须互相合作的协同工作关系，称为进程同步。进程之间的互斥是由于共享系统资源而引起的一种间接制约关系进程之间的同步是并发进程由于要协作完成同一个任务而引起的一种直接制约关系如果无进程在使用共享资源时，可允许任何一个进程去使用共享资源（即使某个进程刚用过也允许再次使用），这是通过进程互斥的方式来管理共享资源如果某个进程通过共享资源得到指定消息时，在指定消息未到达之前，即使无进程在共享资源仍不允许该进程去使用共享资源，这是通过采用进程同步的方式来管理共享资源。Bounded-BufferShareddata#defineBUFFER_SIZE10typedefstruct{...}item;itembuffer[BUFFER_SIZE];intin=0;intout=0;intcounter=0;Bounded-BufferProducerprocessitemnextProduced;while(1){while(counter==BUFFER_SIZE);/*donothing*/buffer[in]=nextProduced;in=(in+1)%BUFFER_SIZE;counter++;}Bounded-BufferConsumerprocessitemnextConsumed;while(1){while(counter==0);/*donothing*/nextConsumed=buffer[out];out=(out+1)%BUFFER_SIZE;counter--;}BoundedBufferThestatementscounter++;counter--;mustbeperformedatomically.Atomicoperation（原子操作）meansanoperationthatcompletesinitsentiretywithoutinterruption.BoundedBufferThestatement“count++”maybeimplementedinmachinelanguageas:register1=counterregister1=register1+1counter=register1Thestatement“count--”maybeimplementedas:register2=counterregister2=register2–1counter=register2BoundedBufferIfboththeproducerandconsumerattempttoupdatethebufferconcurrently,theassemblylanguagestatementsmaygetinterleaved.Interleavingdependsuponhowtheproducerandconsumerprocessesarescheduled.BoundedBufferAssumecounterisinitially5.Oneinterleavingofstatementsis:producer:register1=counter(register1=5)producer:register1=register1+1(register1=6)consumer:register2=counter(register2=5)consumer:register2=register2–1(register2=4)producer:counter=register1(counter=6)consumer:counter=register2(counter=4)Thevalueofcountmaybeeither4or6,wherethecorrectresultshouldbe5.RaceCondition竞争条件Racecondition:Thesituationwhereseveralprocessesaccess–andmanipulateshareddataconcurrently.Thefinalvalueoftheshareddatadependsuponwhichprocessfinisheslast.竞争条件：几个进程并行地访问和操作共享数据的情形。最后的结果取决于最后那一个进程最后完成。Topreventraceconditions,concurrentprocessesmustbesynchronized.为了阻止出现竞争的条件，并行进程必须同步。TheCritical-SectionProblem临界区问题nprocessesallcompetingtousesomeshareddatan个进程都需要竞争使用某些共享的数据区。Eachprocesshasacodesegment,calledcriticalsection,inwhichtheshareddataisaccessed.每个进程有一个代码段，称为临界区，访问共享数据的代码都在临界区中。Problem–ensurethatwhenoneprocessisexecutinginitscriticalsection,nootherprocessisallowedtoexecuteinitscriticalsection.问题-确保当一个进程在临界区中时，没有其它进程在临界区中。你方唱罢我登场临界区问题进程结构进程的一般结构do{entrysectioncriticalsectionexitsectionremindersection}while(1);SolutiontoCritical-SectionProblem临界区问题的解决方案-满足三个条件MutualExclusion(互斥条件)：IfprocessPiisexecutinginitsCS,thennootherprocessescanbeexecutingintheirCSs.Progress(进入条件)：IfnoprocessisexecutinginitsCSandsomeprocesseswishtoentertheirCSs,thenonlythoseprocessesthatarenotexecutingintheirRSscanparticipateinthedecisiononwhichwillenteritsCSnext,andthisselectioncannotbepostponedindefinitely.BoundedWaiting(有限等待的条件)：Thereexistsabound,orlimit,onthenumberoftimesthatotherprocessesareallowedtoentertheirCSaafteraprocesshasmadearequesttoenteritsCSandbeforethatrequestisgranted.Assumethateachprocessexecutesatanonzerospeed.Noassumptionconcerningrelativespeedofthenprocesses.InitialAttemptstoSolveProblem解决临界区问题的初步方案-考虑两个进程Only2processes,P0andP1仅考虑两个进程的情形GeneralstructureofprocessPi(otherprocessPj,j=1-i)进程中的一般结构do{entrysectioncriticalsectionexitsectionremindersection}while(1);Processesmaysharesomecommonvariablestosynchronizetheiractions.进程通过共享一些变量来同步它们的行为。Algorithm1Sharedvariables:intturn;initiallyturn=0turn=iPicanenteritscriticalsectionProcessPido{while(turn!=i);criticalsectionturn=j;remindersection}while(1);Satisfiesmutualexclusion,butnotprogress两进程需严格按顺序交替执行，一个进程在RS就可能使另一个进程不能进其CSAlgorithm2Sharedvariablesbooleanflag[2];initiallyflag[0]=flag[1]=false.flag[i]=truePireadytoenteritscriticalsectionProcessPido{while(flag[j]);flag[i]=true;criticalsectionflag[i]=false;remaindersection}while(1);Satisfiesmutualexclusion,butnotprogressrequirement.两进程需严格按一定时序运行，否则可能在ES无限等待而没有进程能进入其CSAlgorithm3Combinedsharedvariablesofalgorithms1and2.ProcessPido{flag[i]=true;turn=j;while(flag[j]&&turn=j);criticalsectionflag[i]=false;remaindersection}while(1);Meetsallthreerequirements;solvesthecritical-sectionproblemfortwoprocesses.BakeryAlgorithm面包师算法Beforeenteringitscriticalsection,processreceivesanumber.Holderofthesmallestnumbere