操作系统第7章

Chapter7:ProcessSynchronization,Background背景TheCritical-SectionProblem临界区的问题SynchronizationHardware同步硬件Semaphores信号量ClassicalProblemsofSynchronization同步的经典问题CriticalRegions临界区Monitors管程,Background,不是一个人在战斗，关键区域只能一个人战斗Concurrentaccesstoshareddatamayresultindatainconsistency.对共享数据区的并发访问导致数据的不一致性Maintainingdataconsistencyrequiresmechanismstoensuretheorderlyexecutionofcooperatingprocesses.维持数据的一致性要求保证合作进程按一定的顺序执行的机制。Shared-memorysolutiontobounded-bufferproblem(Chapter4)allowsatmostn1itemsinbufferatthesametime.Asolution,whereallNbuffersareusedisnotsimple.Supposethatwemodifytheproducer-consumercodebyaddingavariablecounter,initializedto0andincrementedeachtimeanewitemisaddedtothebuffer,Background,进程的同步隐含了系统中并发进程之间存在的两种相互制约关系：竞争（互斥）与协作（同步）互斥：两个并行的进程A、B，如果当A进行某个操作时，B不能做这一操作，进程间的这种限制条件称为进程互斥，这是引起资源不可共享的原因。同步：我们把进程间的这种必须互相合作的协同工作关系，称为进程同步。进程之间的互斥是由于共享系统资源而引起的一种间接制约关系进程之间的同步是并发进程由于要协作完成同一个任务而引起的一种直接制约关系如果无进程在使用共享资源时，可允许任何一个进程去使用共享资源（即使某个进程刚用过也允许再次使用），这是通过进程互斥的方式来管理共享资源如果某个进程通过共享资源得到指定消息时，在指定消息未到达之前，即使无进程在共享资源仍不允许该进程去使用共享资源，这是通过采用进程同步的方式来管理共享资源。,Bounded-Buffer,Shareddata#defineBUFFER_SIZE10typedefstruct.item;itembufferBUFFER_SIZE;intin=0;intout=0;intcounter=0;,Bounded-Buffer,ProducerprocessitemnextProduced;while(1)while(counter=BUFFER_SIZE);/*donothing*/bufferin=nextProduced;in=(in+1)%BUFFER_SIZE;counter+;,Bounded-Buffer,ConsumerprocessitemnextConsumed;while(1)while(counter=0);/*donothing*/nextConsumed=bufferout;out=(out+1)%BUFFER_SIZE;counter-;,BoundedBuffer,Thestatementscounter+;counter-;mustbeperformedatomically.Atomicoperation（原子操作）meansanoperationthatcompletesinitsentiretywithoutinterruption.,BoundedBuffer,Thestatement“count+”maybeimplementedinmachinelanguageas:register1=counterregister1=register1+1counter=register1Thestatement“count-”maybeimplementedas:register2=counterregister2=register21counter=register2,BoundedBuffer,Ifboththeproducerandconsumerattempttoupdatethebufferconcurrently,theassemblylanguagestatementsmaygetinterleaved.Interleavingdependsuponhowtheproducerandconsumerprocessesarescheduled.,BoundedBuffer,Assumecounterisinitially5.Oneinterleavingofstatementsis:producer:register1=counter(register1=5)producer:register1=register1+1(register1=6)consumer:register2=counter(register2=5)consumer:register2=register21(register2=4)producer:counter=register1(counter=6)consumer:counter=register2(counter=4)Thevalueofcountmaybeeither4or6,wherethecorrectresultshouldbe5.,RaceCondition竞争条件,Racecondition:Thesituationwhereseveralprocessesaccessandmanipulateshareddataconcurrently.Thefinalvalueoftheshareddatadependsuponwhichprocessfinisheslast.竞争条件：几个进程并行地访问和操作共享数据的情形。最后的结果取决于最后那一个进程最后完成。Topreventraceconditions,concurrentprocessesmustbesynchronized.为了阻止出现竞争的条件，并行进程必须同步。,TheCritical-SectionProblem临界区问题,nprocessesallcompetingtousesomeshareddatan个进程都需要竞争使用某些共享的数据区。Eachprocesshasacodesegment,calledcriticalsection,inwhichtheshareddataisaccessed.每个进程有一个代码段，称为临界区，访问共享数据的代码都在临界区中。Problemensurethatwhenoneprocessisexecutinginitscriticalsection,nootherprocessisallowedtoexecuteinitscriticalsection.问题-确保当一个进程在临界区中时，没有其它进程在临界区中。,你方唱罢我登场,临界区问题进程结构,进程的一般结构doentrysectioncriticalsectionexitsectionremindersectionwhile(1);,SolutiontoCritical-SectionProblem临界区问题的解决方案-满足三个条件,MutualExclusion(互斥条件)：IfprocessPiisexecutinginitsCS,thennootherprocessescanbeexecutingintheirCSs.Progress(进入条件)：IfnoprocessisexecutinginitsCSandsomeprocesseswishtoentertheirCSs,thenonlythoseprocessesthatarenotexecutingintheirRSscanparticipateinthedecisiononwhichwillenteritsCSnext,andthisselectioncannotbepostponedindefinitely.BoundedWaiting(有限等待的条件)：Thereexistsabound,orlimit,onthenumberoftimesthatotherprocessesareallowedtoentertheirCSaafteraprocesshasmadearequesttoenteritsCSandbeforethatrequestisgranted.,Assumethateachprocessexecutesatanonzerospeed.Noassumptionconcerningrelativespeedofthenprocesses.,InitialAttemptstoSolveProblem解决临界区问题的初步方案-考虑两个进程,Only2processes,P0andP1仅考虑两个进程的情形GeneralstructureofprocessPi(otherprocessPj,j=1-i)进程中的一般结构doentrysectioncriticalsectionexitsectionremindersectionwhile(1);Processesmaysharesomecommonvariablestosynchronizetheiractions.进程通过共享一些变量来同步它们的行为。,Algorithm1,Sharedvariables:intturn;initiallyturn=0turn=iPicanenteritscriticalsectionProcessPidowhile(turn!=i);criticalsectionturn=j;remindersectionwhile(1);Satisfiesmutualexclusion,butnotprogress,两进程需严格按顺序交替执行，一个进程在RS就可能使另一个进程不能进其CS,Algorithm2,Sharedvariablesbooleanflag2;initiallyflag0=flag1=false.flagi=truePireadytoenteritscriticalsectionProcessPidowhile(flagj);flagi=true;criticalsectionflagi=false;remaindersectionwhile(1);Satisfiesmutualexclusion,butnotprogressrequirement.,两进程需严格按一定时序运行，否则可能在ES无限等待而没有进程能进入其CS,Algorithm3,Combinedsharedvariablesofalgorithms1and2.ProcessPidoflagi=true;turn=j;while(flagjsolvesthecritical-sectionproblemfortwoprocesses.,BakeryAlgorithm面包师算法,Beforeenteringitscriticalsection,processreceivesanumber.Holderofthesmallestnumberentersthecriticalsection.进入临界区前，进程得到一个数字，持有最小数字的进程获准进入临界区。IfprocessesPiandPjreceivethesamenumber,ifij,thenPiisservedfirst;elsePjisservedfirst.如果两个进程得到相同的数字，进程号较小者获准进入临界区Thenumberingschemealwaysgeneratesnumbersinincreasingorderofenumeration;i.e.,1,2,3,3,3,3,4,5.永远以增序的形式产生数字。,Criticalsectionfornprocessesn个进程的临界区算法,BakeryAlgorithm面包师算法,Notationlexicographicalorder(ticket#,processid#)(a,b)(c,d)ifacorifa=candbdmax(a0,an-1)isanumber,k,suchthatkaifori：0,n1Shareddatabooleanchoosingn;intnumbern;Datastructuresareinitializedtofalseand0respectively,BakeryAlgorithm,dochoosingi=true;numberi=max(number0,number1,numbern1)+1;choosingi=false;for(j=0;jn;j+)while(choosingj);while(numberj!=0),SynchronizationHardware,Testandmodifythecontentofawordatomically.booleanTestAndSet(boolean,MutualExclusionwithTest-and-Set,Shareddata:booleanlock=false;ProcessPidowhile(TestAndSet(lock);criticalsectionlock=false;remaindersection,SynchronizationHardware,Atomicallyswaptwovariables.voidSwap(boolean,MutualExclusionwithSwap,Shareddata(initializedtofalse):booleanlock;booleanwaitingn;ProcessPidokey=true;while(key=true)Swap(lock,key);criticalsectionlock=false;remaindersection,Semaphores,Synchronizationtoolthatdoesnotrequirebusywaiting.SemaphoreSintegervariablecanonlybeaccessedviatwoindivisible(atomic)operationswait(S):whileS0dono-op;S-;signal(S):S+;,CriticalSectionofnProcesses,Shareddata:semaphoremutex;/initiallymutex=1ProcessPi:dowait(mutex);criticalsectionsignal(mutex);remaindersectionwhile(1);,SemaphoreImplementation,能不能聪明一点？Defineasemaphoreasarecordtypedefstructintvalue;structprocess*L;semaphore;Assumetwosimpleoperations:blocksuspendstheprocessthatinvokesit.wakeup(P)resumestheexecutionofablockedprocessP.,Implementation,Semaphoreoperationsnowdefinedaswait(S):S.value-;if(S.value0)addthisprocesstoS.L;block;signal(S):S.value+;if(S.value=0)removeaprocessPfromS.L;wakeup(P);,SemaphoreasaGeneralSynchronizationTool,ExecuteBinPjonlyafterAexecutedinPiUsesemaphoreflaginitializedto0Code:PiPjAwait(flag)signal(flag)B,DeadlockandStarvation,Deadlock（死锁）twoormoreprocessesarewaitingindefinitelyforaneventthatcanbecausedbyonlyoneofthewaitingprocesses.LetSandQbetwosemaphoresinitializedto1P0P1wait(S);wait(Q);wait(Q);wait(S);signal(S);signal(Q);signal(Q)signal(S);Starvation（饿死）indefiniteblocking.Aprocessmayneverberemovedfromthesemaphorequeueinwhichitissuspended.,TwoTypesofSemaphores,Countingsemaphore（计数信号量）integervaluecanrangeoveranunrestricteddomain.Binarysemaphore（二元信号量）integervaluecanrangeonlybetween0and1;canbesimplertoimplement.CanimplementacountingsemaphoreSasabinarysemaphore.,ClassicalProblemsofSynchronization,Bounded-BufferProblem（有界缓存）ReadersandWritersProblem（读者-写者）Dining-PhilosophersProblem（哲学家就餐）,Bounded-BufferProblem,Shareddatasemaphorefull,empty,mutex;Initially:full=0,empty=n,mutex=1,Bounded-BufferProblemProducerProcess,doproduceaniteminnextpwait(empty);wait(mutex);addnextptobuffersignal(mutex);signal(full);while(1);,Bounded-BufferProblemConsumerProcess,dowait(full)wait(mutex);removeanitemfrombuffertonextcsignal(mutex);signal(empty);consumetheiteminnextcwhile(1);,Readers-WritersProblem,Shareddatasemaphoremutex,wrt;Initiallymutex=1,wrt=1,readcount=0,Readers-WritersProblemWriterProcess,wait(rd);wait(wrt);writingisperformedsignal(wrt);signal(rd);,Readers-WritersProblemReaderProcess,wait(rd);wait(mutex);readcount+;if(readcount=1)wait(wrt);signal(mutex);signal(rd);readingisperformedwait(mutex);readcount-;if(readcount=0)signal(wrt);signal(mutex):,Readers-WritersProblem,Writer正在写时，第一个reader等待writer，其他readers等待第一个reader只要有readers，writer必须等Writers必须等writer（有writer正在writing）和readers（有readers正在reading）思考：能让写者优先吗？能让两者公平吗？,Dining-PhilosophersProblem,Shareddatasemaphorechopstick5;Initiallyallvaluesare1,Dining-PhilosophersProblem（1）,Philosopheri:dowait(chopsticki)wait(chopstick(i+1)%5)eatsignal(chopsticki);signal(chopstick(i+1)%5);thinkwhile(1);,Dining-PhilosophersProblem（2）,Starvation？Howtodealwith？,Aboutsynchronization,RaceconditionMustkeepcorrecttimingsequencesUserUsuallytimingerrorsNeedplaytrickbadOsSemaphoreBetterBut，wronguseofsemaphoresresultingintimingerrors,Aboutsynchronization(1),Howtodealwitherrorslistedabove？Highlevelsynchronizationconstructmonitor,Signal(mutex)CSWait(mutex)Nomutualexclusion,wait(mutex)Wait(mutex)Deadlock,Monitors,Amonitorischaracterizedbyasetofprogrammer-definedoperators.Monitor确保一次只有一个进程在monitor内活跃。monitormonitor-name/sharedvariabledeclarationsprocedurebodyP1().procedurebodyP2().procedurebodyPn().initializationcode(),Monitors,如何保证？条件变量Toallowaprocesstowaitwithinthemonitor,aconditionvariablemustbedeclared,asconditionx,y;Conditionvariablecanonlybeusedwiththeoperationswaitandsignal.Theoperationx.wait();meansthattheprocessinvokingthisoperationissuspendeduntilanotherprocessinvokesx.signal();Thex.signaloperationresumesexactlyonesuspendedprocess.Ifnoprocessissuspended,thenthesignaloperationhasnoeffect.,SchematicViewofaMonitor,MonitorWithConditionVariables,DiningPhilosophersExample只有同时拿到左右两根筷子才能吃,monitordpenumthinking,hungry,eatingstate5;conditionself5;voidpickup(inti)/followingslidesvoidputdown(inti)/followingslidesvoidtest(inti)/followingslidesvoidinit()for(inti=0;i5;i+)statei=thinking;,DiningPhilosophers,voidpickup(inti)statei=hungry;test(i);if(statei!=eating)selfi.wait();voidputdown(inti)statei=thinking;/testleftandrightneighborstest(i+4)%5);test(i+1)%5);,DiningPhilosophers,voidtest(inti)if(state(i+4)%5!=eating),DiningPhilosophers,philosopheridp.pickup(i);eatdp.putdown(i);,Synchronizationexamples,Solaris2:adaptivemutex,conditionvariable,semaphore,reader-writerlock,turnstile(十字转门)WindowsXP:Inkernel-maskinterrupt(uniprocessor),spinlock(multiprocessor)Outsidekernel-dispatcherobjectsMutex,semaphore,event,timerLinux2.6:enable/disablepreemption(uniprocessor),spinlock(multiprocessor)PthreadsAPI:mutexlock,conditionvariable,read-writelock,AtomicTransactions原子交易,CS-你方唱罢我登场MutualexclusionofcriticalsectionsAT-油盐坛子，公不离婆秤不离砣HowtomakesureacriticalsectionformsasinglelogicunitofworkEitherperformedinitsentiretyOrnotperformedatallTransaction交易Acollectionofinstructions(oroperations)thatperformsasinglelogicalfunctionAmajorissueinprocessingtransactionsisthepreservationofatomicitydespitethepossibilityoffailureswithinthecomputersystemAsequenceofreadandwriteoperations,terminatedbyacommitorabortoperation,AtomicTransactions(1),Commit提交TheeffectofacommittedtransactioncannotbeundonebyabortionofthetransactionAbort终止AnabortedtransactionmusthavenoeffectonthestateofthedataithasalreadymodifiedThestateofthedataaccessedbyanabortedtransactionmustberestoredtowhatitwasjustbeforethetransactionstartedexecuting.如何恢复？存储信息。怎么存储？Torecordonstablestorage,informationdescribingallthemodificationsmadebythetransactiontothevariousdataitaccessed,Howtorecord,Log-basedrecoveryTransactionnameDataitemnameOldvalueNewvalueCheckpointsToreducethesearchingoverheadConcurrentatomictransactionsSerializabilityLockingprotocolTimestamp-basedprotocols,Summary,进程的同步隐含了系统中并发进程之间存在的两种相互制约关系：竞争（互斥）与协作（同步）互斥：两个并行的进程A、B，如果当A进行某个操作时，B不能做这一操作，进程间的这种限制条件称为进程互斥，这是引起资源不可共享的原因。同步：我们把进程间的这种必须互相合作的协同工作关系，称为进程同步。进程之间的互斥是由于共享系统资源而引起的一种间接制约关系进程之间的同步是并发进程由于要协作完成同一个任务而引起的一种直接制约关系如果无进程在使用共享资源时，可允许任何一个进程去使用共享资源（即使某个进程刚用过也允许再次使用），这是通过进程互斥的方式来管理共享资源如果某个进程通过共享资源得到指定消息时，在指定消息未到达之前，即使无进程在共享资源仍不允许该进程去使用共享资源，这是通过采用进程同步的方式来管理共享资源。临界资源：一些被共享的资源，具有一次仅允许一个进程使用的特点临界区：并发进程访问临界资源的那段必须互斥执行的程序实现临界区互斥一个遵循的准则有空让进，临界区空闲时，允许一个进程进入执行无空等待，有进程在临界区执行时，要进入的进程必须等待让权等待，有进程在临界区执行时，要求进入的进程必须立即释放CPU而等待有限等待，不应该使进入临界区的进程无限期地等待在临界区之外信号量及p、v操作经典同步问题原子交易,作业,1.Thefirstknowncorrectsoftwaresolutiontothecritical-sectionproblemfortwothreadswasdevelopedbyDekker.Thetwothreads,T0andT1,sharethefollowingvariables:Booleanflag2;/*initiallyfalse*/intturn;ThestructureofthreadTi(i=0or1),withTj(j=1or0)beingtheotherthread,isshownas:doflagi=true;while(flagj)if(turn=j)flagi=false;while(turn=j);flagi=true;criticalsectionturn=j;flagi=false;remaindersectionwhile(1);Provethatthealgorithmsatisfiesallthreerequirementsforthecritical-sectionproblem.,7-cont.,2.Thefirstknowncorrectsoftwaresolutiontothecritical-sectionproblemfornprocesseswithalowerboundonwaitingofn-1turnswaspresentedbyEisenbergandMcGuire.Theproces