四川大學(xué)操作系統(tǒng)課件Chapter05

1Chapter5MutualExclusion(互斥)andSynchronization(同步)

OperatingSystems2Agenda5.1PrinciplesofConcurrency5.2MutualExclusion:HardwareSupport5.3Semaphores5.4Monitors5.5MessagePassing5.6Readers/WritersProblem5.7Summary3ConcurrencyConcurrencyarisesinthreedifferentcontexts:Multipleapplications(多應(yīng)用程序)MultiprogrammingStructuredapplication(結(jié)構(gòu)化應(yīng)用程序)SomeapplicationcanbedesignedasasetofconcurrentprocessesOperating-systemstructure(操作系統(tǒng)結(jié)構(gòu))Operatingsystemisasetofprocessesorthreads4Concurrency臨界區(qū)死鎖活鎖互斥競爭條件饑餓55.1PrinciplesofConcurrency5.1.1ASimpleExample5.1.2RaceCondition5.1.3OperatingSystemConcerns5.1.4ProcessInteraction5.1.5RequirementsforMutualExclusion6DifficultiesofConcurrencySharingofglobalresourcesOperatingsystemmanagingtheallocationofresourcesoptimallyDifficulttolocateprogrammingerrors7ASimpleExamplecharchin,chout;voidecho(){ chin=getchar(); chout=chin; putchar(chout);}8ASimpleExample(Uniprocessor)

ProcessP1 ProcessP2. . chin=getchar(); .chout=chin; . chin=getchar(); chout=chin;putchar(chout);putchar(chout); .. .9ASimpleExample(Multiprocessor)

ProcessP1 ProcessP2. . chin=getchar(); .. chin=getchar();chout=chin; chout=chin;putchar(chout); .. putchar(chout);. .105.1PrinciplesofConcurrency5.1.1ASimpleExample5.1.2RaceCondition5.1.3OperatingSystemConcerns5.1.4ProcessInteraction5.1.5RequirementsforMutualExclusion11RaceCondition(競爭條件)Araceconditionoccurswhenmultipleprocessesorthreadsreadandwritedataitemssothatthefinalresultdependsontheorderofexecutionofinstructionsinthemultipleprocessesorthread.(競爭條件發(fā)生在當(dāng)多個進(jìn)程或者線程在讀寫數(shù)據(jù)時，其最終結(jié)果依賴于多個進(jìn)程或者線程的指令執(zhí)行順序)125.1PrinciplesofConcurrency5.1.1ASimpleExample5.1.2RaceCondition5.1.3OperatingSystemConcerns5.1.4ProcessInteraction5.1.5RequirementsforMutualExclusion13OperatingSystemConcernsKeeptrackofvariousprocesses(throughPCB)AllocateanddeallocateresourcesProcessortimeMemoryFilesI/OdevicesProtectdataandresourcesOutputofprocessmustbeindependentofthespeedofexecutionofotherconcurrentprocesses145.1PrinciplesofConcurrency5.1.1ASimpleExample5.1.2RaceCondition5.1.3OperatingSystemConcerns5.1.4ProcessInteraction5.1.5RequirementsforMutualExclusion15ProcessInteraction(進(jìn)程交互)ProcessesunawareofeachotherProcessesindirectlyawareofeachotherProcessdirectlyawareofeachother1617CompetitionAmongProcessesforResources(進(jìn)程間的資源爭用)MutualExclusion(互斥)CriticalsectionsOnlyoneprogramatatimeisallowedinitscriticalsectionExampleonlyoneprocessatatimeisallowedtosendcommandtotheprinterDeadlock(死鎖)Starvation(饑餓)18IllustrationofMutualExclusionbycriticalsection.entercritical：進(jìn)入臨界區(qū).exitcritical：退出臨界區(qū)195.1PrinciplesofConcurrency5.1.1ASimpleExample5.1.2RaceCondition5.1.3OperatingSystemConcerns5.1.4ProcessInteraction5.1.5RequirementsforMutualExclusion20RequirementsforMutualExclusionOnlyoneprocessatatimeisallowedinthecriticalsectionforaresource(一次只允許一個進(jìn)程進(jìn)入臨界區(qū)，忙則等待)Aprocessthathaltsinitsnoncriticalsectionmustdosowithoutinterferingwithotherprocesses(阻塞于臨界區(qū)外的進(jìn)程不能干涉其它進(jìn)程)Nodeadlockorstarvation(不會發(fā)生饑餓和死鎖，有限等待)21RequirementsforMutualExclusionAprocessmustnotbedelayedaccesstoacriticalsectionwhenthereisnootherprocessusingit(閑則讓進(jìn))Noassumptionsaremadeaboutrelativeprocessspeedsornumberofprocesses(對相關(guān)進(jìn)程的執(zhí)行速度和處理器數(shù)目沒有要求)Aprocessremainsinsideitscriticalsectionforafinitetimeonly(有限占用)22Agenda5.1PrinciplesofConcurrency5.2MutualExclusion:HardwareSupport5.3Semaphores5.4Monitors5.5MessagePassing5.6Readers/WritersProblem5.7Summary235.2MutualExclusion:HardwareSupport5.2.1InterruptDisabling(中斷禁止)5.2.2SpecialMachineInstructions(特殊機(jī)器指令)24HardwareSupport:InterruptDisabling25AprocessrunsuntilitinvokesanoperatingsystemserviceoruntilitisinterruptedDisablinginterruptsguaranteesmutualexclusiononuniprocessorsystemDisadvantage:Processorislimitedinitsabilitytointerleaveprogramsdisablinginterruptsononeprocessorwillnotguaranteemutualexclusioninmulti-processorsenvironment.HardwareSupport:InterruptDisabling265.2MutualExclusion:HardwareSupport5.2.1InterruptDisabling5.2.2SpecialMachineInstructions27PerformedinasingleinstructioncycleAccesstothememorylocationisblockedforanyotherinstructionsHardwareSupport:SpecialMachineInstructions28TestandSetInstruction(textedition5) booleantestset(inti){ if(i==0){ i=1; returntrue; } else{ returnfalse; } }HardwareSupport:SpecialMachineInstructions29Compareandswapintcompare_and_swap(int*word,inttestval,intnewval){ intoldval; oldval=*word; if(oldval==testval)*word=newval; returnoldval;}HardwareSupport:SpecialMachineInstructions30HardwareSupportforMutualExclusion31ExchangeInstruction voidexchange(intregister, intmemory){ inttemp; temp=memory; memory=register; register=temp; }HardwareSupport:SpecialMachineInstructions32HardwareSupportforMutualExclusion注意：第5版教材錯誤33AdvantagesBysharingmainmemory，itisapplicabletoanynumberofprocessessingleprocessormultipleprocessorsItissimpleandthereforeeasytoverifyItcanbeusedtosupportmultiplecriticalsectionsHardwareSupport:SpecialMachineInstructions34DisadvantagesBusy-waiting(忙等待)consumesprocessortimeStarvation(饑餓)ispossiblewhenaprocessleavesacriticalsectionandmorethanoneprocessiswaiting.Deadlock(死鎖)ispossibleIfalowpriorityprocesshasthecriticalregionandahigherpriorityprocessneeds,thehigherpriorityprocesswillobtaintheprocessortowaitforthecriticalregionHardwareSupport:SpecialMachineInstructions35Agenda5.1PrinciplesofConcurrency5.2MutualExclusion:HardwareSupport5.3Semaphores5.4Monitors5.5MessagePassing5.6Readers/WritersProblem5.7Summary365.3Semaphores5.3.1Overview5.3.2MutualExclusion5.3.3TheProducer/ConsumerProblem5.3.4ImplementofSemaphores37Semaphores(信號量)Fundamentalprinciple(基本原理):Twoormoreprocessescancooperatebymeansofsimplesignals,suchthataprocesscanbeforcedtostopataspecifiedplaceuntilithasreceivedaspecificsignal.(兩個或者多個進(jìn)程可以通過簡單的信號進(jìn)行合作，一個進(jìn)程可以被迫在一個位置停止，直到它收到一個信號)Forsignaling,specialvariablescalledsemaphoresareused(一種稱為信號量的特殊變量用來傳遞信號)Ifaprocessiswaitingforasignal,itissuspendeduntilthatsignalissent(如果一個進(jìn)程在等待一個信號，它會被掛起，直到它等待的信號被發(fā)出）38SemaphoresSemaphoreisavariablethathasanintegervalue(整數(shù)值)Initialize：Maybeinitializedtoanonnegativenumber(非負(fù)數(shù))semWait(P)：Waitoperationdecrementsthesemaphorevalue，Ifthevaluebecomesnegative,thentheprocessexecutingthesemWaitisblocked.semSignal(V)：Signaloperationincrementssemaphorevalue，Iftheresultingvalueislessthanorequaltozero,thenaprocessblockedbyasemWaitoperation,ifany,isunblocked.39SemaphorePrimitives(原語，原子操作)40BinarySemaphore(二元信號量)BinarySemaphoreisavariablethathasanintegervalueMaybeinitializedto0or1.semWaitB：checksthesemaphorevalue.Ifthevalueiszero,thentheprocessexecutingthesemWaitBisblocked.Ifthevalueisone,thenthevalueischangedtozeroandtheprocesscontinuesexecution.semSignalB：checkstoseeifanyprocessesareblockedonthis

semaphore.Ifso,thenaprocessblockedbya

semWaitBoperationisunblocked.Ifnoprocessesareblocked,thenthevalue

ofthesemaphoreissettoone.41BinarySemaphore(二元信號量)Primitives(原語)42Semaphoreterms(信號量術(shù)語)BinarySemaphore(二元信號量)Mutex(互斥信號量)CountingSemaphore(計數(shù)信號量)GeneralSemaphore(一般信號量)WeakSemaphore(弱信號量)StrongSemaphore(強(qiáng)信號量)435.3Semaphores5.3.1Overview5.3.2MutualExclusion5.3.3TheProducer/ConsumerProblem5.3.4ImplementofSemaphores44MutualExclusionUsingSemaphores45-1-2-146Morethanoneprocessinitscriticalsectionatatime(多個進(jìn)程同時在臨界區(qū)內(nèi))Initializethesemaphoretothespecifiedvalues.count>=0:s.countisthenumberofprocessesthatcanexecutesemWait(s)withoutsuspensions.count<0:Themagnitudeofs.countisthenumberofprocessessuspendedins.queue.475.3Semaphores5.3.1Overview5.3.2MutualExclusion5.3.3TheProducer/ConsumerProblem5.3.4ImplementofSemaphores48Producer/ConsumerProblem(生產(chǎn)者/消費(fèi)者問題)OneormoreproducersaregeneratingdataandplacingtheseinabufferAsingleconsumeristakingitemsoutofthebufferoneattimeOnlyoneproducerorconsumermayaccessthebufferatanyonetime49Producer/ConsumerProblemwithInfiniteBuffer(無限緩沖區(qū))50ProducerwithInfiniteBufferproducer:while(true){ /*produceitemv*/ b[in]=v; in++;}51ConsumerwithInfiniteBufferconsumer:while(true){ while(in<=out) /*donothing*/; w=b[out]; out++; /*consumeitemw*/}52控制進(jìn)入臨界區(qū)避免“超前”消費(fèi)緩沖區(qū)中的項數(shù)535455控制進(jìn)入臨界區(qū)控制“超前消費(fèi)”56Producer/ConsumerProblemwithFiniteBuffer(有限緩沖區(qū))57Producer/ConsumerProblemwithFiniteBuffer(有限緩沖區(qū))Thebufferistreatedasacircularstorage,andpointervaluesmustbeexpressedmodulothesizeofthebuffer.Thefollowingrelationshipshold:58ProducerwithCircularBufferproducer:while(true){ /*produceitemv*/ while((in+1)%n==out) /*donothing*/; b[in]=v; in=(in+1)%n}59ConsumerwithCircularBufferconsumer:while(true){ while(in==out) /*donothing*/; w=b[out]; out=(out+1)%n; /*consumeitemw*/}60控制進(jìn)入臨界區(qū)控制“超前”消費(fèi)控制生產(chǎn)“過剩”615.3Semaphores5.3.1Overview5.3.2MutualExclusion5.3.3TheProducer/ConsumerProblem5.3.4ImplementofSemaphores625.3.4ImplementofSemaphoresImplementinhardwareorfirmware(固件)Implementinsoftware,e.g.DekkerorPetersonImplementbyinhibitinterrupts(中斷禁止)forasingle-processorsystem635.3.4ImplementofSemaphores64Agenda5.1PrinciplesofConcurrency5.2MutualExclusion:HardwareSupport5.3Semaphores5.4Monitors5.5MessagePassing5.6Readers/WritersProblem5.7Summary65Monitors(管程)Monitorisasoftwaremoduleconsistingofoneoremoreprocedures,aninitializationsequence,andlocaldata(管程由一個或者多個例程、一段初始化代碼和局部數(shù)據(jù)組成).Andthechiefcharacteristicsarethefollowing:LocaldatavariablesareaccessibleonlybythemonitorProcessentersmonitorbyinvokingoneofitsproceduresOnlyoneprocessmaybeexecutinginthemonitoratatime66MonitorsOperations(管程操作)Amonitorsupportssynchronizationbytheuseofconditionvariables(管程通過條件變量實(shí)現(xiàn)同步)cwait(c):Suspendexecutionofthecallingprocessonconditionc.Themonitorisnowavailableforusebyanotherprocess.csignal(c):Resumeexecutionofsomeprocessblockedafteracwaitonthesamecondition.Ifthereareseveralsuchprocesses,chooseoneofthem;ifthereisnosuchprocess,donothing.Notethatmonitorwaitandsignaloperationsaredifferentfromthoseforthesemaphore.Ifaprocessinamonitorsignalsandnotaskiswaitingontheconditionvariable,thesignalislost.67686970Agenda5.1PrinciplesofConcurrency5.2MutualExclusion:HardwareSupport5.3Semaphores5.4Monitors5.5MessagePassing5.6Readers/WritersProblem5.7Summary71MessagePassingEnforcemutualexclusionExchangeinformation

send(destination,message) receive(source,message)72SynchronizationSenderandreceivermayormaynotbeblockingBlockingsend,blockingreceiveBothsenderandreceiverareblockeduntilmessageisdelivered73SynchronizationNonblockingsend,blockingreceiveSendercontinuesonReceiverisblockeduntiltherequestedmessagearrivesNonblockingsend,nonblockingreceiveNeitherpa