四川大学操作系统课件Chapter05

1Chapter5MutualExclusion(互斥)andSynchronization(同步)

OperatingSystems2Agenda5.1PrinciplesofConcurrency5.2MutualExclusion:HardwareSupport5.3Semaphores5.4Monitors5.5MessagePassing5.6Readers/WritersProblem5.7Summary3ConcurrencyConcurrencyarisesinthreedifferentcontexts:Multipleapplications(多应用程序)MultiprogrammingStructuredapplication(结构化应用程序)SomeapplicationcanbedesignedasasetofconcurrentprocessesOperating-systemstructure(操作系统结构)Operatingsystemisasetofprocessesorthreads4Concurrency临界区死锁活锁互斥竞争条件饥饿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.(竞争条件发生在当多个进程或者线程在读写数据时，其最终结果依赖于多个进程或者线程的指令执行顺序)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(进程交互)ProcessesunawareofeachotherProcessesindirectlyawareofeachotherProcessdirectlyawareofeachother1617CompetitionAmongProcessesforResources(进程间的资源争用)MutualExclusion(互斥)CriticalsectionsOnlyoneprogramatatimeisallowedinitscriticalsectionExampleonlyoneprocessatatimeisallowedtosendcommandtotheprinterDeadlock(死锁)Starvation(饥饿)18IllustrationofMutualExclusionbycriticalsection.entercritical：进入临界区.exitcritical：退出临界区195.1PrinciplesofConcurrency5.1.1ASimpleExample5.1.2RaceCondition5.1.3OperatingSystemConcerns5.1.4ProcessInteraction5.1.5RequirementsforMutualExclusion20RequirementsforMutualExclusionOnlyoneprocessatatimeisallowedinthecriticalsectionforaresource(一次只允许一个进程进入临界区，忙则等待)Aprocessthathaltsinitsnoncriticalsectionmustdosowithoutinterferingwithotherprocesses(阻塞于临界区外的进程不能干涉其它进程)Nodeadlockorstarvation(不会发生饥饿和死锁，有限等待)21RequirementsforMutualExclusionAprocessmustnotbedelayedaccesstoacriticalsectionwhenthereisnootherprocessusingit(闲则让进)Noassumptionsaremadeaboutrelativeprocessspeedsornumberofprocesses(对相关进程的执行速度和处理器数目没有要求)Aprocessremainsinsideitscriticalsectionforafinitetimeonly(有限占用)22Agenda5.1PrinciplesofConcurrency5.2MutualExclusion:HardwareSupport5.3Semaphores5.4Monitors5.5MessagePassing5.6Readers/WritersProblem5.7Summary235.2MutualExclusion:HardwareSupport5.2.1InterruptDisabling(中断禁止)5.2.2SpecialMachineInstructions(特殊机器指令)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.(两个或者多个进程可以通过简单的信号进行合作，一个进程可以被迫在一个位置停止，直到它收到一个信号)Forsignaling,specialvariablescalledsemaphoresareused(一种称为信号量的特殊变量用来传递信号)Ifaprocessiswaitingforasignal,itissuspendeduntilthatsignalissent(如果一个进程在等待一个信号，它会被挂起，直到它等待的信号被发出）38SemaphoresSemaphoreisavariablethathasanintegervalue(整数值)Initialize：Maybeinitializedtoanonnegativenumber(非负数)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(信号量术语)BinarySemaphore(二元信号量)Mutex(互斥信号量)CountingSemaphore(计数信号量)GeneralSemaphore(一般信号量)WeakSemaphore(弱信号量)StrongSemaphore(强信号量)435.3Semaphores5.3.1Overview5.3.2MutualExclusion5.3.3TheProducer/ConsumerProblem5.3.4ImplementofSemaphores44MutualExclusionUsingSemaphores45-1-2-146Morethanoneprocessinitscriticalsectionatatime(多个进程同时在临界区内)Initializethesemaphoretothespecifiedvalues.count>=0:s.countisthenumberofprocessesthatcanexecutesemWait(s)withoutsuspensions.count<0:Themagnitudeofs.countisthenumberofprocessessuspendedins.queue.475.3Semaphores5.3.1Overview5.3.2MutualExclusion5.3.3TheProducer/ConsumerProblem5.3.4ImplementofSemaphores48Producer/ConsumerProblem(生产者/消费者问题)OneormoreproducersaregeneratingdataandplacingtheseinabufferAsingleconsumeristakingitemsoutofthebufferoneattimeOnlyoneproducerorconsumermayaccessthebufferatanyonetime49Producer/ConsumerProblemwithInfiniteBuffer(无限缓冲区)50ProducerwithInfiniteBufferproducer:while(true){ /*produceitemv*/ b[in]=v; in++;}51ConsumerwithInfiniteBufferconsumer:while(true){ while(in<=out) /*donothing*/; w=b[out]; out++; /*consumeitemw*/}52控制进入临界区避免“超前”消费缓冲区中的项数535455控制进入临界区控制“超前消费”56Producer/ConsumerProblemwithFiniteBuffer(有限缓冲区)57Producer/ConsumerProblemwithFiniteBuffer(有限缓冲区)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控制进入临界区控制“超前”消费控制生产“过剩”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(管程由一个或者多个例程、一段初始化代码和局部数据组成).Andthechiefcharacteristicsarethefollowing:LocaldatavariablesareaccessibleonlybythemonitorProcessentersmonitorbyinvokingoneofitsproceduresOnlyoneprocessmaybeexecutinginthemonitoratatime66MonitorsOperations(管程操作)Amonitorsupportssynchronizationbytheuseofconditionvariables(管程通过条件变量实现同步)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