操作系统并发性互斥和同步

1Concurrency:MutualExclusionandSynchronizationChapter52ConcurrencyOverviewThecentralthemesofoperatingsystemdesignareallconcernedwiththemanagementofprocessesandthreads:MultiprogrammingMultiprocessingDistributedprocessingFundamentaltooperatingsystemdesignisconcurrency(并发)TheBasicrequirementforsupportofconcurrencyistheabilitytoenforcemutualexclusion(互斥)3ConcurrencyContexts(并发上下文)Concurrencyarisesinthreedifferentcontexts:MultipleapplicationsMultiprogrammingStructuredapplicationApplicationcanbeasetofconcurrentprocessesorthreadsOperating-systemstructureOperatingsystemisasetofprocessesorthreads4DesignIssuesofConcurrencyCommunicationamongprocessesSharingandcompeting(竞争)ofresourcesSynchronizationoftheactivitiesofmultipleprocessesAllocationofprocessortimetoprocesses5PrinciplesofConcurrencyInterleavingOverlappingBasiccharacteristicofmultiprogrammingsystems:relativespeedofexecutionofprocessescannotbepredicted6DifficultiesofConcurrencySharingofglobalresourcesForexample:GlobalvariableOperatingsystemmanagingtheallocationofresourcesoptimallyForexample:I/OchannelDifficulttolocateprogrammingerrorsProgramresultsarenotdeterministicandreproducible(再现)7ASimpleExamplevoidecho(){chin=getchar();chout=chin;putchar(chout);}ProcessP1ProcessP2..chin=getchar();..chin=getchar();chout=chin;chout=chin;putchar(chout);..putchar(chout);..8RaceCondition(竞争条件)WhenmultipleprocessesorthreadsaccesssharedresourcesothatthefinalresultdependsontheorderofexecutionofinstructionsinthemultipleprocessesMurphyLawIfSomethingcangowrong,itwill.SolutiontoRaceCondition:ControlaccesstothesharedresourceMutualExclusion(互斥)9ProcessInteractionThreepossibledegreesofawarenessamongprocesses:ProcessesunawareofeachotherCompetitionProcessesindirectlyawareofeachotherCooperationProcessdirectlyawareofeachotherCooperation10CompetitionAmongProcessesforResourcesCriticalsections(临界区)PortionoftheprogramthataccesssharedresourceOnlyoneprogramatatimeisallowedinitscriticalsectionExampleonlyoneprocessatatimeisallowedtosendcommandtotheprinterEnforcementofmutualexclusionincurstwoadditionalproblems:Deadlock(死锁)Starvation(饥饿)11MutualExclusion/*programmutualexclusion*/constintn=/*numberofprocesses*/;voidP(inti){while(true){entercritical(i);/*criticalsection*/;exitcritical(i);/*remainder*/}}voidmain(){parbegin(P(1),P(2)…,P(n));}12RequirementsforMutualExclusionOnlyoneprocessatatimeisallowedinthecriticalsectionforaresourceAprocessthathaltsinitsnoncriticalsection(非临界区)mustdosowithoutinterferingwithotherprocessesNodeadlockorstarvation13RequirementsforMutualExclusion(Cont.)AprocessmustnotbedelayedaccesstoacriticalsectionwhenthereisnootherprocessusingitNoassumptionsaremadeaboutrelativeprocessspeedsornumberofprocessesAprocessremainsinsideitscriticalsectionforafinitetimeonly14LockVariables(锁变量)ThesimplestapproachwecanimagineHowdoesitwork?15MutualExclusion:HardwareSupportInterruptDisabling(关中断)AprocessrunsuntilitinvokesanoperatingsystemserviceoruntilitisinterruptedDisablinginterruptsguaranteesmutualexclusionProcessorislimitedinitsabilitytointerleaveprogramsMultiprocessingdisablinginterruptsononeprocessorwillnotguaranteemutualexclusion16MutualExclusion:HardwareSupportSpecialMachineInstructionsPerformedinasingleinstructioncycleAccesstothememorylocationisblockedforanyotherinstructionsTestandSetInstructionExchangeInstruction17TestandSetInstructionbooleantestset(inti){if(i==0){i=1;returntrue;}else{returnfalse;}}18voidexchange(intregister,intmemory){inttemp;temp=memory;memory=register;register=temp;}ExchangeInstruction19TestandSetforMutualExclusionvoidmain(){bolt=0;parbegin(P(1),P(2),...,P(n));}/*programmutualexclusion*/constintn=/*numberofprocesses*/;intbolt;voidP(inti){while(true){while(!testset(bolt))/*donothing*/;/*criticalsection*/;bolt=0;/*remainder*/}}20ExchangeforMutualExclusionvoidmain(){bolt=0;parbegin(P(1),P(2),...,P(n));}/*programmutualexclusion*/constintn=/*numberofprocesses*/;intbolt;voidP(inti){intkeyi=1;while(true){doexchange(keyi,bolt)while(keyi!=0);/*criticalsection*/;exchange(keyi,bolt);/*remainder*/}}21ExchangeforMutualExclusionvoidmain(){bolt=0;parbegin(P(1),P(2),...,P(n));}/*programmutualexclusion*/constintn=/*numberofprocesses*/;intbolt;voidP(inti){intkeyi=1;while(true){while(keyi!=0)exchange(keyi,bolt);/*criticalsection*/;exchange(keyi,bolt);/*remainder*/}}22AdvantagesofMachine-instructionApproachApplicabletoanynumberofprocessesoneitherasingleprocessorormultipleprocessorssharingmainmemoryItissimpleandthereforeeasytoverifyItcanbeusedtosupportmultiplecriticalsections23DisadvantagesofMachine-instructionApproachBusy-waiting(忙等待)consumesprocessortimeStarvationispossiblewhenaprocessleavesacriticalsectionandmorethanoneprocessiswaiting.DeadlockIfalowpriorityprocesshasthecriticalregionandahigherpriorityprocessneeds,thehigherpriorityprocesswillobtaintheprocessortowaitforthecriticalregionPriorityInversionProblem(优先级翻转问题)24Semaphores(信号量)1965,DijkstraSpecialvariablecalledasemaphoreisusedforsignalingTwoprimitives(原语)ared