四川大学操作系统课件Chapter05

1Chapter5MutualExclusion(互斥)andSynchronization(同步)OperatingSystems2Agenda5.1PrinciplesofConcurrency5.2MutualExclusion:HardwareSupport5.3Semaphores5.4Monitors5.5MessagePassing5.6Readers/WritersProblem5.7Summary3Concurrency•Concurrencyarisesinthreedifferentcontexts:–Multipleapplications(多应用程序)•Multiprogramming–Structuredapplication(结构化应用程序)•Someapplicationcanbedesignedasasetofconcurrentprocesses–Operating-systemstructure(操作系统结构)•Operatingsystemisasetofprocessesorthreads4Concurrency临界区死锁活锁互斥竞争条件饥饿55.1PrinciplesofConcurrency5.1.1ASimpleExample5.1.2RaceCondition5.1.3OperatingSystemConcerns5.1.4ProcessInteraction5.1.5RequirementsforMutualExclusion6DifficultiesofConcurrency•Sharingofglobalresources•Operatingsystemmanagingtheallocationofresourcesoptimally•Difficulttolocateprogrammingerrors7ASimpleExamplecharchin,chout;voidecho(){chin=getchar();chout=chin;putchar(chout);}8ASimpleExample(Uniprocessor)ProcessP1ProcessP2..chin=getchar();.chout=chin;.chin=getchar();chout=chin;putchar(chout);putchar(chout);...9ASimpleExample(Multiprocessor)ProcessP1ProcessP2..chin=getchar();..chin=getchar();chout=chin;chout=chin;putchar(chout);..putchar(chout);..105.1PrinciplesofConcurrency5.1.1ASimpleExample5.1.2RaceCondition5.1.3OperatingSystemConcerns5.1.4ProcessInteraction5.1.5RequirementsforMutualExclusion11RaceCondition(竞争条件)Araceconditionoccurswhenmultipleprocessesorthreadsreadandwritedataitemssothatthefinalresultdependsontheorderofexecutionofinstructionsinthemultipleprocessesorthread.(竞争条件发生在当多个进程或者线程在读写数据时，其最终结果依赖于多个进程或者线程的指令执行顺序)125.1PrinciplesofConcurrency5.1.1ASimpleExample5.1.2RaceCondition5.1.3OperatingSystemConcerns5.1.4ProcessInteraction5.1.5RequirementsforMutualExclusion13OperatingSystemConcerns•Keeptrackofvariousprocesses(throughPCB)•Allocateanddeallocateresources–Processortime–Memory–Files–I/Odevices•Protectdataandresources•Outputofprocessmustbeindependentofthespeedofexecutionofotherconcurrentprocesses145.1PrinciplesofConcurrency5.1.1ASimpleExample5.1.2RaceCondition5.1.3OperatingSystemConcerns5.1.4ProcessInteraction5.1.5RequirementsforMutualExclusion15ProcessInteraction(进程交互)•Processesunawareofeachother•Processesindirectlyawareofeachother•Processdirectlyawareofeachother1617CompetitionAmongProcessesforResources(进程间的资源争用)•MutualExclusion(互斥)–Criticalsections•Onlyoneprogramatatimeisallowedinitscriticalsection•Exampleonlyoneprocessatatimeisallowedtosendcommandtotheprinter•Deadlock(死锁)•Starvation(饥饿)18IllustrationofMutualExclusionbycriticalsection.entercritical：进入临界区.exitcritical：退出临界区195.1PrinciplesofConcurrency5.1.1ASimpleExample5.1.2RaceCondition5.1.3OperatingSystemConcerns5.1.4ProcessInteraction5.1.5RequirementsforMutualExclusion20RequirementsforMutualExclusion1.Onlyoneprocessatatimeisallowedinthecriticalsectionforaresource(一次只允许一个进程进入临界区，忙则等待)2.Aprocessthathaltsinitsnoncriticalsectionmustdosowithoutinterferingwithotherprocesses(阻塞于临界区外的进程不能干涉其它进程)3.Nodeadlockorstarvation(不会发生饥饿和死锁，有限等待)21RequirementsforMutualExclusion4.Aprocessmustnotbedelayedaccesstoacriticalsectionwhenthereisnootherprocessusingit(闲则让进)5.Noassumptionsaremadeaboutrelativeprocessspeedsornumberofprocesses(对相关进程的执行速度和处理器数目没有要求)6.Aprocessremainsinsideitscriticalsectionforafinitetimeonly(有限占用)22Agenda5.1PrinciplesofConcurrency5.2MutualExclusion:HardwareSupport5.3Semaphores5.4Monitors5.5MessagePassing5.6Readers/WritersProblem5.7Summary235.2MutualExclusion:HardwareSupport5.2.1InterruptDisabling(中断禁止)5.2.2SpecialMachineInstructions(特殊机器指令)24HardwareSupport:InterruptDisabling25•Aprocessrunsuntilitinvokesanoperatingsystemserviceoruntilitisinterrupted•Disablinginterruptsguaranteesmutualexclusiononuniprocessorsystem•Disadvantage:–Processorislimitedinitsabilitytointerleaveprograms–disablinginterruptsononeprocessorwillnotguaranteemutualexclusioninmulti-processorsenvironment.HardwareSupport:InterruptDisabling265.2MutualExclusion:HardwareSupport5.2.1InterruptDisabling5.2.2SpecialMachineInstructions27•Performedinasingleinstructioncycle–AccesstothememorylocationisblockedforanyotherinstructionsHardwareSupport:SpecialMachineInstructions28•TestandSetInstruction(textedition5)booleantestset(inti){if(i==0){i=1;returntrue;}else{returnfalse;}}HardwareSupport:SpecialMachineInstructions29•Compareandswapintcompare_and_swap(int*word,inttestval,intnewval){intoldval;oldval=*word;if(oldval==testval)*word=newval;returnoldval;}HardwareSupport:SpecialMachineInstructions30HardwareSupportforMutualExclusion31•ExchangeInstructionvoidexchange(intregister,intmemory){inttemp;temp=memory;memory=register;register=temp;}HardwareSupport:SpecialMachineInstructions32HardwareSupportforMutualExclusion注意：第5版教材错误33•Advantages–Bysharingmainmemory，itisapplicabletoanynumberofprocesses•singleprocessor•multipleprocessors–Itissimpleandthereforeeasytoverify–ItcanbeusedtosupportmultiplecriticalsectionsHardwareSupport:SpecialMachineInstructions34•Disadvantages–Busy-waiting(忙等待)consumesprocessortime–Starvation(饥饿)ispossiblewhenaprocessleavesacriticalsectionandmorethanonep