操作系统原理6 [兼容模式]

Chapter6:ProcessSynchronization沈卓炜h@[e-mail]九龙湖校区计算机楼347房间52090919Chapter6:ProcessShitiSynchronization„Backgrond„Background„TheCritical-SectionProblem„SynchronizationHardwareSh„Semaphores„ClassicalProblemsofSynchronizationy„MonitorsS„SynchronizationExamplesSoutheastUniversity6.2OperatingSystemConceptsBackground„Concurrentaccesstoshareddatamayresultindatainconsistency.y„Maintainingdataconsistencyrequiresmechanismstoensuretheorderlyexecutionofmechanismstoensuretheorderlyexecutionofcooperatingprocesses.„Shared-memorysolutiontobounded-bufferproblem(Chapter3)allowsatmostn–1itemsproblem(Chapter3)allowsatmostn1itemsinbufferatthesametime.Asolution,whereallNbuffersareusedisnotsimpleNbuffersareusedisnotsimple.‹Supposethatwemodifytheproducer-consumerdbddiiblSoutheastUniversity6.3OperatingSystemConceptscodebyaddingavariablecounterBounded-Buffer„Shareddata#defineBUFFER_SIZE10typedefstruct{...}item;itembuffer[BUFFER_SIZE];intin=0;intout=0;intcounter=0;SoutheastUniversity6.4OperatingSystemConceptsBounded-Bufferoudedue„ProducerprocessitemnextProduced;itemnextProduced;while(1){while(counter==BUFFERSIZE)while(counter==BUFFER_SIZE);/*donothing*/buffer[in]=nextProduced;in=(in+1)%BUFFERSIZE;in=(in+1)%BUFFER_SIZE;counter++;SoutheastUniversity6.5OperatingSystemConcepts}Bounded-Bufferoudedue„ConsumerprocessitemnextConsumed;while(1){while(counter==0)while(counter==0);/*donothing*/tCdbff[t]nextConsumed=buffer[out];out=(out+1)%BUFFER_SIZE;counter--;}SoutheastUniversity6.6OperatingSystemConcepts}BoundedBufferoudedue„Thestatementscounter++;counter--;mustbeperformedatomically.„Atomicoperationmeansanoperationthatcompletesinitsentiretywithoutinterruption.SoutheastUniversity6.7OperatingSystemConceptsBoundedBufferThttt“t”biltd„Thestatement“count++”maybeimplementedinmachinelanguageas:register1=counterregister1counterregister1=register1+1tit1counter=register1„Thestatement“count--”maybeimplementedypas:register2=counterregister2=counterregister2=register2–1counter=register2SoutheastUniversity6.8OperatingSystemConceptscounter=register2BoundedBufferoudedue„Ifboththeprodcerandconsmerattempt„Ifboththeproducerandconsumerattempttoupdatethebufferconcurrently,theassemblylanguagestatementsmaygetinterleaved.Itliddhthd„Interleavingdependsuponhowtheproducerandconsumerprocessesarescheduled.SoutheastUniversity6.9OperatingSystemConceptsBoundedBufferAtiiitill5Oitli„Assumecounterisinitially5.Oneinterleavingofstatementsis:producer:register1=counter(register1=5)producer:register1=register1+1(register1=producer:register1register11(register16)consumer:register2=counter(register2=5)consumer:register2=counter(register2=5)consumer:register2=register2–1(register24)=4)producer:counter=register1(counter=6)consumer:counter=register2(counter=4)„Thevalueofcountmaybeeither4or6whereSoutheastUniversity6.10OperatingSystemConcepts„Thevalueofcountmaybeeither4or6,wherethecorrectresultshouldbe5.ProducerConsumerregister1=counterregister2=counterregister1=counterregister1=register1+1register2=counterregister2=register2–1egsteegstecounter=register1register2=register2–1counter=register2counterregister2SoutheastUniversity6.11OperatingSystemConceptsRaceConditionaceCodto„Raceconditionoccrsif„Raceconditionoccurs,if:‹twoormoreprocesses/threadsaccessandmanipulatethesamedataconcurrently,and‹theoutcomeoftheexecutiondependsonptheparticularorderinwhichtheaccesstakesplace.pTtditit„Topreventraceconditions,concurrentprocessesmustbesynchronized.SoutheastUniversity6.12OperatingSystemConceptsChapter6:ProcessShitiSynchronization„Backgrond„Background„TheCritical-SectionProblem„SynchronizationHardwareSh„Semaphores„ClassicalProblemsofSynchronizationy„MonitorsS„SynchronizationExamplesSoutheastUniversity6.13OperatingSystemConceptsTheCritical-SectionProblemeCtcaSectoobe„nprocessesallcompetingtousesome„nprocessesallcompetingtousesomeshareddata„Eachprocesshasacodesegment,calledcriticalsection,inwhichtheshareddatais,accessed.„Problemensurethatwhenoneprocessis„Problem–ensurethatwhenoneprocessisexecutinginitscriticalsection,nootherilldttiititilprocessisallowedtoexecuteinitscriticalsection.SoutheastUniversity6.14OperatingSystemConceptsCriticalSectionandMutualExclusion„Thstheeectionofcriticalsectionsmst„Thus,theexecutionofcriticalsectionsmustbemutuallyexclusive(e.g.,atmostoneprocesscanbeinitscriticalsectionatanytime).)„Thecritical-sectionproblemistodesignaprotocolthatprocessescanusetoprotocolthatprocessescanusetocooperate.SoutheastUniversity6.15OperatingSystemConceptsTheCriticalSectionProtocoleCtcaSectootoco„Acriticalsection„Acriticalsectionprotocolconsistsoftwoparts:anentrytwoparts:anentrysectionandanexitsectionsection.„Betweenthemisthecriticalsectionthatmustruninamutuallyexclusiveway.SoutheastUniversity6.16OperatingSystemConceptsSolutiontoCritical-SectionPblProblem„Anysolutiontothecriticalsectionproblemmustsatisfythefollowingthreeconditions:‹MutualExclusion‹MutualExclusion‹Progress‹BoundedWaiting‹BoundedWaiting„Moreover,thesolutioncannotdependonrelativespeedofprocessesandschedulingpolicy.policy.Southeas