Operating Systems： Distributed Coordina

《Operating Systems： Distributed Coordina》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、JerryBreecherOPERATINGSYSTEMSDistributedCoordination118:DistributedCoordinationDISTRIBUTEDCOORDINATIONTopics:EventOrderingMutualExclusionAtomicityConcurrencyControlDeadlockHandlingElectionAlgorithmsReachingAgreement218:DistributedCoordinationDISTRIBUTEDCOORDINATIONDefin

2、itions:Tightlycoupledsystems:Sameclock,usuallysharedmemory.Communicationisviathissharedmemory.Multiprocessors.Looselycoupledsystems:Differentclock.Usecommunicationlinks.Distributedsystems.318:DistributedCoordinationDISTRIBUTEDCOORDINATION"Happeningbefore"vs.concurrent.H

3、ereA-->BmeansAoccurredbeforeBandthuscouldhavecausedB.Oftheeventsshownonthenextpage,whicharehappened-beforeandwhichareconcurrent?Orderingiseasyifthesystemsshareacommonclock(i.e.,it'sinacentralizedsystem.)Withnocommonclock,eachprocesskeepsalogicalclock.ThisLogicalClockcan

4、besimplyacounter-itmayhavenorelationtorealtime.Adjusttheclockifmessagesarereceivedwithtimehigherthancurrenttime.WerequirethatLC(A)=LC(B),thensetLC(B)=LC(A)+1.EventOrdering418:Di

5、stributedCoordinationDISTRIBUTEDCOORDINATIONEventOrderingP0P1P4P3P2PoooooQ0Q1Q4Q3Q2QoooooR0R1R4R3R2RoooooTime518:DistributedCoordinationDISTRIBUTEDCOORDINATIONHere’stheproblemwehavetosolve.Supposetwoprocesseswanttogaintwolocks.Forasinglesystemapproach,welearnedthatdeadl

6、ockcouldbeavoidedbyassuringthatthelocksarealwaysattainedinthesameorder:P1:P2:wait(Q);wait(Q);wait(S);wait(S);..........signal(S);signal(Q);signal(Q);signal(S);Tomakethiswork,weneedtomaintainstrictHappeningBeforerelationships.MutualExclusion/Synchronization618:Distribute

7、dCoordinationDISTRIBUTEDCOORDINATIONUSINGDISTRIBUTEDSEMAPHORESWithonlyasinglemachine,aprocessorcanprovidemutualexclusion.Butit'smuchhardertodowithadistributedsystem.Thenetworkmaynotbefullyconnectedsocommunicationmustbethroughanintermediarymachine.Concernscenteraround:1.

8、Efficiency/performance2.Howtore-coordinateifsomethingbreaks.MutualExclusion/SynchronizationTechniqueswewilldis