并行程序设计 中文课件 11 并行计算系统同步

ParallelProgrammingInstructor:ZhangWeizhe(张伟哲)ComputerNetworkandInformationSecurityTechniqueResearchCenter,SchoolofComputerScienceandTechnology,HarbinInstituteofTechnologyTimeandGlobalState31.Introduction介绍2.Clocks,eventsandprocessstates时钟，事件和进程状态3.Synchronizingphysicalclocks同步物理时钟4.Logicaltimeandlogicalclocks逻辑时间和逻辑时钟5.SummaryOutline4Needtomeasureaccurately需要准确测量E.g.auditingine-commerce电子商务审计Algorithmsdependingon算法取决于E.g.consistency,make，DistributedDebugging分布式调试TimeisanimportantissueinDS5Example:makeWheneachmachinehasitsownclock,aneventthatoccurredafteranothereventmayneverthelessbeassignedanearliertime.当每台机器都有自己的时钟时，在另一个事件之后发生的事件可能会被分配较早的时间。6Physicist’sview物理学家的观点Newton’snotation:absolutephysicaltime牛顿的符号：绝对的物理时间Einstein’sRelativityTheory爱因斯坦的相对论People’sapproachesdealingwithtime人们处理时间的方法Approximatelysynchronize大概同步Logicalclocks逻辑时钟Thereisnouniversephysicalclock71.Introduction2.Clocks,eventsandprocessstates3.Synchronizingphysicalclocks4.Logicaltimeandlogicalclocks5.SummaryOutline8Adevicethatcountoscillationsoccurringinacrystalatadefinitefrequency以一定频率计算晶体振荡的装置Hardwaretime:Hi(t)Thecountsofoscillationsinceanoriginalpoint原始点以来的振荡计数Softwaretime:Ci(t)=

Hi(t)+

Timestampofanevent事件的时间戳Clockincomputer9Clockdrift时钟漂移Crystaloscillateatdifferentrate晶体以不同的速率振荡Clockdriftcannotbeavoided时钟漂移是无法避免的Clockskew时钟偏移Theinstantaneousdifferencebetweenthereadingsofanytwoclocks任何两个时钟的读数之间的瞬时差异Clockskewandclockdrift10RotationofearthonitsaxisandabouttheSun自转和公转Days,Years,etcSecondis1/86400astronomical天文timeMeansolarsecond平均太阳秒TheperiodoftheEarth’srotationaboutitsaxisisgraduallygettinglonger地球围绕其轴旋转的时期逐渐变长Tidalfriction,atmosphericeffects,etc潮汐摩擦，大气影响等AstronomicalTime(1)11AstronomicalTime(2)Computationofthemeansolarday.12Standardsecond标准秒Atomicoscillator原子振荡器Driftrate:onepartin10-13Since1967:9,192,631,770periodsoftransitionbetweenthetwohyperfinelevelsofthegroundstateofCs133Shiftbetweenastronomicaltimeandatomictime天文时间与原子时间之间的转换Leapsecond闰秒Atomictimewhichisinsertedaleapsecondoccasionallytokeepinstepwithastronomicaltime原子时间偶尔插入闰秒，与天文时间保持一致InternationalAtomicTime13LeapsecondTAIsecondsareofconstantlength,unlikesolarseconds.Leapsecondsareintroducedwhennecessarytokeepinphasewiththesun.

TAI秒的长度不变，不像太阳秒。必要时引入闰秒与太阳保持同步。14Greenwichmeantime格林威治标准时间Universalcoordinatedtime(UTC)BroadcastUTCtotheWorldE.g.,byGPSorWWVCoordinatedUniversalTime(UTC)151.Introduction2.Clocks,eventsandprocessstates3.Synchronizingphysicalclocks4.Logicaltimeandlogicalclocks5.SummaryOutline16Externalsynchronization外部同步ForasynchronizationboundD>0,andforasourceSofUTCtime,|S(t)-Ci(t)|<D,fori=1,2,…NandforallrealtimestinIClocksCiareaccurate

towithintheboundD时钟Ci精确到D范围内Ci

:pi’sclockI:anintervalofrealtime真实时间间隔External&Internalsynchronization(1)17Internalsynchronization内部同步ForasynchronizationboundD>0,|Ci(t)-Cj(t)|<D

fori,j=1,2,…N,andforallrealtimestinIClocksCi

agree

withintheboundDIf

accurate

towithinD,then

agree

within2D如果精确到D，允许范围是2DExternal&Internalsynchronization(2)18Clockfailures时钟故障Crashfailure:stopticking崩溃故障：停止滴答Arbitrary任意failure,e.g.Y2KbugGeneralsynchronizationissues19Protocol协议Sender:sendM(t)Receiver:settimetot+TtransBoundsareknowinsynchronoussystem范围在同步系统中是已知的min<Ttrans<max(constant)So,setTtrans=(min+max)/2Receiver’sclock=t+(min+max)/2Synchronizationinasynchronoussystem20Clockskewbetweensenderandreceiver(max–min)/2Synchronizationinasynchronoussystem(2)tt+maxt+Ttranst+min21Externalsynchronization外部同步Applyingcircumstance适用情况C/SRound-triptimeisshortcomparedwiththerequiredaccuracyC/S与所需精度相比，往返时间短Protocolmr,mt(t),TroundEstimatedtime:tinmt+Tround/2Cristian’smethodofsynchronizingclocksmrmtpTimeserver,S22Accuracyanalysis精度分析Iftheminimumdelayofamessagetransmission消息传输的最小延迟ismin,thenaccuracy:(Tround/2–min)Cristian’smethodofsynchronizingclocks(2)tt+Tround-mint+Tround/2t+mint+Tround23Internalsynchronization内部同步Themaster

pollstheslaves’clocks主轮询从时钟Themaster

estimatestheslaves’clocksbyround-triptime主人通过往返时间估计从时钟SimilartoChristian’salgorithm类似于基督教的算法Themaster

averagestheslaves’clockvalues主人对从站的时钟值进行平均Cancelouttheindividualclock’stendenciestorunfastorslow取消个别时钟的趋势，以快速或慢速运行TheBerkeleyalgorithms24Themastersendsbacktotheslavestheamountthattheslaves’clocksshouldadjustby主机向从站发回从站的时钟应该调整的量Positiveornegativevalue正值或负值Avoidfurtheruncertaintyduetothemessagetransmissiontime避免由于消息传输时间进一步的不确定性Slaveajustitsclock从时钟调整TheBerkeleyalgorithms(2)25TheBerkeleyAlgorithm(3)(a)Thetimedaemon时间守护进程asksalltheothermachinesfortheirclockvalues.

26TheBerkeleyAlgorithm(4)(b)Themachinesanswer.27TheBerkeleyAlgorithm(5)(c)Thetimedaemontellseveryonehowtoadjusttheirclock.28ExternalsynchronizationEnableclientsacrosstheInternettobesynchronizedaccuratelytoUTCReliabilityCansurvivelengthylossesofconnectivityRedundantserver&redundantpathbetweenserversScalabilityEnableclientstoresynchronizesufficiently

frequentlytooffsettheratesofdriftfoundinmostcomputersSecurityProtectagainstinterferencewiththetimeserviceDesignaimsofNetworkTimeProtocol29外部同步使互联网上的客户端能够准确地同步到UTC可靠性可以长时间连接的损失冗余服务器和服务器之间的冗余路径可扩展性使客户端能够频繁地重新同步，以抵消大多数计算机中发现的漂移速率安全防止干扰时间服务网络时间协议的设计目标30ReconfigurewhenserversbecomeunreachableNetworkTimeProtocolArchitecture123233Note:Arrowsdenotesynchronizationcontrol,numbersdenotestrata.31MulticastmodeIntendforuseonahighspeedLANAssumingasmalldelayLowaccuracybutefficientProcedure-callmodeSimilartoChristian’sHigheraccuracythanmulticastSymmetricmodeThehighestaccuracySynchronizationmeasures32组播模式适合在高速LAN上使用假设延迟很小精度低但效率高程序呼叫模式类似于基督徒精度高于多播对称模式最高的准确性同步措施331.Introduction2.Clocks,eventsandprocessstates3.Synchronizingphysicalclocks4.Logicaltimeandlogicalclocks5.SummaryOutline34

HB1:Ifprocesspi:eie`,thenee`HB2:Foranymessagem,send(m)receive(m)HB3:IFe,e`ande``areeventssuchthatee`ande`e``,thenee``CausalorderingHappen-beforerelation35Examplea||eShortcomings缺点Notsuitabletoprocessescollaborationthatdoesnotinvolvemessagestransmission不适合处理不涉及消息传输的协作Capturepotentialcausalordering捕获潜在的因果秩序Happen-beforerelation36Example37LC1Liisincrementedbeforeeacheventisissuedatprocesspi:Li:=Li+1LC2:(a)Whenaprocesspisendsamessagem,itpiggybacksonmthevaluet=Li(b)Onreceiving(m,t),aprocessPjcomputesLj:=max(Lj,t)andthenappliesLC1beforetimestampingtheeventreceive(m)Lamporttimestampsalgorithm38ee`L(e)<L(e`)L(e)<L(e`)ee`ore||e`Lamporttimestampsalgorithm(2)39Example:Lamport’sClocks(1)(a)Threeprocesses,eachwithitsownclock.

Theclocksrunatdifferentrates.

40Example:Lamport’sClocks(2)(b)Lamport’salgorithmcorrectstheclocks.41EachprocesspikeepsavectorclockViVC1:Initially,Vi[j]=0,fori,j=1,2…,NVC2:Justbeforepitimestampsanevent,itsetsVi[i]:=Vi[i]+1VC3:piincludesthevaluet=ViineverymessageitsendsVC4:Whenpireceivesatimestamptinamessage,itsetsVi[j]:=max(Vi[j],t[j]),forj=1,2…,NVectorClocks-algorithm42VectorClocks-example43Comparevectortimestamps

V=V’iffV[j]=V’[j]forj=1,2…,NV<=V’iffV[j]<=V’[j]forj=1,2…,N

V<V’iffV[j]<V’[j]forj=1,2…,NOtherwiseV<>V’V(e)<V(e`)ee`,V(e)<>V(e`)e||e`VectorClocks-significance441.Introduction2.Clocks,eventsandprocessstates3.Synchronizingphysicalclocks4.Logicaltimeandlogicalclocks5.SummaryOutline45Clockskew,clockdrift时钟偏移，时钟漂移Synchronizephysicalclocks物理时钟同步Christian’salgorithm基督教的算法Berkeleyalgorithm伯克利算法NetworkTimeProtocol网络时间协议Logicaltime逻辑时间Happen-beforerelation发生之前关系Lamporttimestampalgorithm拉姆波特时间戳算法Vectorclock矢量时钟Summary46Globalstates全球状态Consistentcut,consistentstate一致切割，一致状态Snapshotalgorithm快照算法Constructreachabilityrelationshipbysnapshot通过快照构建可达性关系Summary…continuedCoordinationandAgreement协调与协议481.Distributedmutualexclusion分布式互斥2.Elections选举3.SummaryOutline49MutualExclusionToguaranteeconsistencyamongdistributedprocessesthatareaccessingsharedmemory,itisnecessarytoprovidemutualexclusion

whenaccessingacriticalsection.为了保证正在访问共享内存的分布式进程之间的一致性，必须在访问临界区时提供互斥。Assume

nprocesses.50AssumptionAsynchronous,noprocessfail,reliablechannel异步，没有进程失败，可靠的通道Applicationlevelprotocolenter()resourceAccesses()exit()Algorithmsformutualexclusion51EssentialrequirementsformutualexlcusionSafetyAtmostoneprocessmayexecuteinthecriticalsectionatatimeLivenessRequeststoenterandexitthecriticalsection(CS)eventuallysucceedFreefromdeadlockandstarvationOrderingIfonerequesttoentertheCShappened-beforeanother,thenentrytotheCSisgrantedinthatorderAlgorithmsformutualexclusion52互斥的基本要求安全一次最多可以在关键部分执行一个进程活跃进入和退出关键部分（CS）的请求最终成功没有死锁和饥饿顺序如果进入CS的一个请求发生在另一个之前，则按照该顺序授予对CS的输入互斥算法53EvaluatetheperformanceofthealgorithmsBandwidthconsumedThenumberofmessagessentineachentryandexitoperationClientDelayIncurredbyaprocessateachentryandexitoperationsAlgorithmsformutualexclusion…continued54评估算法的性能带宽消耗在每个进入和退出操作中发送的消息数客户延迟在进入和退出操作过程中发生Algorithmsformutualexclusion…continued55ACentralizedAlgorithm

forMutualExclusionAssumeacoordinatorhasbeenelected. 1.Aprocesssendsamessagetothecoordinatorrequesting permissiontoenteracriticalsection.Ifnootherprocess isinthecriticalsection,permissionisgranted. 2.Ifanotherprocessthenaskspermissiontoenterthesame criticalregion,thecoordinatordoesnotreply(Or,it sends“permissiondenied”)andqueuestherequest. 3.Whenaprocessexitsthecriticalsection,itsendsa messagetothecoordinator. 4.Thecoordinatortakesfirstentryoffthequeueandsends thatprocessamessagegrantingpermissiontoenterthe criticalsection.56互斥的集中算法假设一个协调者已经当选了。1.进程向协调者发送消息，请求进入关键部分的许可。如果关键部分中没有其他进程，则授予权限。2.如果另一个进程要求进入相同关键区域的权限，则协调器不会回复（或者它发送“被拒绝的权限”）并对请求进行排队。3.当一个进程退出临界区时，它向协调器发送一个消息。4.协调者从队列中选择第一个，并向该进程发送一个消息，授予进入关键部分的权限。57ACentralizedAlgorithm(1)(a)Process1asksthecoordinatorforpermissiontoaccessaharedresource.Permissionisgranted.

58ACentralizedAlgorithm(2)(b)Process2thenaskspermissiontoaccessthesameresource.Thecoordinatordoesnotreply.59ACentralizedAlgorithm(3)(c)Whenprocess1releasestheresource,ittellsthecoordinator,whichthenrepliesto2.60PerformanceBandwidthconsumption=3Enter():Arequestmessage,agrantmessageExit():areleasemessageClientDelay(nowaitingprocesses)=2Requestmessage+grantmessageProblems:Coordinatorcrash协调者崩溃Performancebottleneck性能瓶颈ACentralizedAlgorithm(4)61ADistributedAlgorithm(1)Threedifferentcases:Ifthereceiverisnotaccessingtheresourceanddoesnotwanttoaccessit,itsendsbackanOKmessagetothesender.Ifthereceiveralreadyhasaccesstotheresource,itsimplydoesnotreply.Instead,itqueuestherequest.Ifthereceiverwantstoaccesstheresourceaswellbuthasnotyetdoneso,itcomparesthetimestampoftheincomingmessagewiththeonecontainedinthemessagethatithassenteveryone.Thelowestonewins.62分布式算法(1)三种不同的情况：如果接收方没有访问资源，并且不想访问该资源，则它向发送方发回一条OK消息。如果接收者已经可以访问资源，它根本就不会回复。相反，它会排队请求。如果接收方想要访问资源，但还没有这样做，它将传入消息的时间戳与发送给每个人的消息中包含的时间戳进行比较。最低的一个胜利。63ADistributedAlgorithm(2)(a)Twoprocesseswanttoaccessasharedresourceatthesamemoment.64ADistributedAlgorithm(3)(b)Process0hasthelowesttimestamp,soitwins.65ADistributedAlgorithm(4)(c)

Whenprocess0isdone,itsendsanOKalso,so2cannowgoahead.66IdeaAprocessentersCSifallotherprocessespromiseMulticast+replyPerformanceBandwidth=2(n-1)Enter():N-1multicastmessage,N-1replyClientdelay:round-triptime=2(n-1)Problems:Crashofanyprocess任何进程崩溃ADistributedAlgorithm(4)67ATokenRingAlgorithm(1)(a)Anunorderedgroupofprocessesonanetwork.

(b)Alogicalringconstructedinsoftware.68PerformanceBandwidthconsumed=1~infiniteContinuouslyconsumenetworkbandwidthClientDelay=0~n-1Min:0message,whenithasjustreceivedthetokenMax:Nmessages,whenithasjustpassedonthetokenATokenRingAlgorithm(2)69AComparisonoftheThreeAlgorithmsAlgorithmMessagesperentry/exitDelaybeforeentry(inmessagetimes)ProblemsCentralized32CoordinatorcrashDistributed2(n–1)2(n–1)ProcesscrashTokenring1to

0ton–1Losttoken,processcrashCentralizedisthemostefficient.Tokenringefficientwhenmanywanttousecriticalregion.70IdeaAprocessenterCSwhenpartofotherprocessespromisePerformanceBandwidthutilization带宽利用率Noreleasemessages:Havereleasemessages:Betterthan2(N-1)ifN>4Clientdelay:aroundtriptime客户延迟：往返时间Sameasmulticastalgorithm与多播算法相同TheimprovedalgorithmAtotalorderofeachrequest每个请求的总顺序Thewait-foroperationexecutesinaccordancewiththetotalorder等待操作根据总顺序执行Maekawa’svotingalgorithm711.Distributedmutualexclusion2.Elections3.SummaryOutline72ElectionAlgorithmsManydistributedalgorithmssuchasmutualexclusionanddeadlockdetectionrequirea

coordinatorprocess.Whenthecoordinatorprocessfails,thedistributedgroupofprocessesmustexecuteanelectionalgorithmtodetermineanewcoordinatorprocess.Thesealgorithmswillassumethateachactiveprocesshasauniquepriorityid.

73选择算法Manydistributedalgorithmssuchasmutualexclusionanddeadlockdetectionrequirea

coordinatorprocess.许多分布式算法，如互斥和死锁检测需要协调程序。Whenthecoordinatorprocessfails,thedistributedgroupofprocessesmustexecuteanelectionalgorithmtodetermineanewcoordinatorprocess.当协调程序进程失败时，分布式进程组必须执行选择算法来确定新的协调程序进程。Thesealgorithmswillassumethateachactiveprocesshasauniquepriorityid.这些算法将假设每个活动进程具有唯一的优先级id。74ElectionChooseauniqueprocesstoplayaparticularroleDefinetheelection:choosethelargestidentifierE.g.forelectingtheprocesswithlowestload,thenid=1/loadEvaluatetheperformanceofelectionalgorithmTotalbandwidthutilizationTurnaroundtimeThenumberofserializedmessagetransmissiontimesbetweentheinitiationandterminationofasinglerunSomeconceptsaboutElectionalgorithm75选举选择一个独特的过程来发挥特定的作用确定被选者：选择最大的标识符例如，用于选择最低负载的过程，则id=1/负载评估选举算法的性能总带宽利用率周转时间在单次运行的启动和终止之间的序列化消息传输时间的数量选择算法一些概念76AssumptionSynchronoussystemUsetimeouttodetectaprocessfailureReliablefailuredetectorProcesscancommunicatewithprocesseswhichhavehigheridentifiershigherprocesses&lowerprocessesThebullyalgorithm77假设同步系统使用超时来检测进程故障可靠的故障检测器进程可以与具有更高标识符的进程通信更高的流程和更低的流程Thebullyalgorithm78ThebullyalgorithmTheBullyAlgorithm1.PsendsanELECTIONmessagetoallprocesseswithhighernumbers.2.Ifnooneresponds,Pwinstheelectionandbecomescoordinator.3.Ifoneofthehigher-upsanswers,ittakesover.P’sjobisdone.79Thebullyalgorithm欺负算法1.P发送一个ELECTION消息给所有具有较高数字的进程。2.如果没有人回应，P赢得选举，成为协调员。3.如果其中一个高层回答，它将接管。P的工作完成了。80TheBullyAlgorithm(1)(a)Process4holdsanelection.(b)Processes5and6respond,telling4tostop.(c)Now5and6eachholdanelection.81TheBullyAlgorithm(2)(d)Process6tells5tostop.(e)Process6winsandtellseveryone.82Evaluatetheperformance评估性能bandwidthbest

=N-2Thesecondhighestprocessinitiatetheelection第二高的进程开始选举SendN-2coordinatormessagetolowerprocessesTurnaroundtime=1messagebandwidthworst

:O(N2)Thelowestprocessinitiatetheelection

Thebullyalgorithm…continued83ARingAlgorithmAssumetheprocessesarelogicallyorderedinaring{impliesasuccessorpointerandanactiveprocesslist}

thatisunidirectional.Whenanyprocess,P,noticesthatthecoordinatorisnolongerrespondingitinitiatesanelection:1.PsendsmessagecontainingP’sprocessidtothenextavailablesuccessor.84ARingAlgorithm假设这些进程在一个环中被逻辑地排序（这意味着一个独立的后继指针和一个活动的进程列表）。当任何进程P发现协调员不再响应时，会启动一个选举：P将包含P进程标识的消息发送到下一个可用的后继。85ARingAlgorithm2.

Ateachactiveprocess,thereceivingprocessaddsitsprocessnumbertothelistofprocessesinthemessageandforwardsittoitssuccessor.3.Eventually,themessagegetsbacktothesender.4.Theinitialsendersendsoutasecondmessagelettingeveryoneknowwhothecoordinatoris{theprocesswiththehighestnumber}andindicatingthecurrentmembersoftheactivelistofprocesses.

86ARingA