并行程序設(shè)計 中文課件 11 并行計算系統(tǒng)同步

ParallelProgrammingInstructor:ZhangWeizhe(張偉哲)ComputerNetworkandInformationSecurityTechniqueResearchCenter,SchoolofComputerScienceandTechnology,HarbinInstituteofTechnologyTimeandGlobalState31.Introduction介紹2.Clocks,eventsandprocessstates時鐘，事件和進(jìn)程狀態(tài)3.Synchronizingphysicalclocks同步物理時鐘4.Logicaltimeandlogicalclocks邏輯時間和邏輯時鐘5.SummaryOutline4Needtomeasureaccurately需要準(zhǔn)確測量E.g.auditingine-commerce電子商務(wù)審計Algorithmsdependingon算法取決于E.g.consistency,make，DistributedDebugging分布式調(diào)試TimeisanimportantissueinDS5Example:makeWheneachmachinehasitsownclock,aneventthatoccurredafteranothereventmayneverthelessbeassignedanearliertime.當(dāng)每臺機(jī)器都有自己的時鐘時，在另一個事件之后發(fā)生的事件可能會被分配較早的時間。6Physicist’sview物理學(xué)家的觀點Newton’snotation:absolutephysicaltime牛頓的符號：絕對的物理時間Einstein’sRelativityTheory愛因斯坦的相對論People’sapproachesdealingwithtime人們處理時間的方法Approximatelysynchronize大概同步Logicalclocks邏輯時鐘Thereisnouniversephysicalclock71.Introduction2.Clocks,eventsandprocessstates3.Synchronizingphysicalclocks4.Logicaltimeandlogicalclocks5.SummaryOutline8Adevicethatcountoscillationsoccurringinacrystalatadefinitefrequency以一定頻率計算晶體振蕩的裝置Hardwaretime:Hi(t)Thecountsofoscillationsinceanoriginalpoint原始點以來的振蕩計數(shù)Softwaretime:Ci(t)=

Hi(t)+

Timestampofanevent事件的時間戳Clockincomputer9Clockdrift時鐘漂移Crystaloscillateatdifferentrate晶體以不同的速率振蕩Clockdriftcannotbeavoided時鐘漂移是無法避免的Clockskew時鐘偏移Theinstantaneousdifferencebetweenthereadingsofanytwoclocks任何兩個時鐘的讀數(shù)之間的瞬時差異Clockskewandclockdrift10RotationofearthonitsaxisandabouttheSun自轉(zhuǎn)和公轉(zhuǎn)Days,Years,etcSecondis1/86400astronomical天文timeMeansolarsecond平均太陽秒TheperiodoftheEarth’srotationaboutitsaxisisgraduallygettinglonger地球圍繞其軸旋轉(zhuǎn)的時期逐漸變長Tidalfriction,atmosphericeffects,etc潮汐摩擦，大氣影響等AstronomicalTime(1)11AstronomicalTime(2)Computationofthemeansolarday.12Standardsecond標(biāo)準(zhǔn)秒Atomicoscillator原子振蕩器Driftrate:onepartin10-13Since1967:9,192,631,770periodsoftransitionbetweenthetwohyperfinelevelsofthegroundstateofCs133Shiftbetweenastronomicaltimeandatomictime天文時間與原子時間之間的轉(zhuǎn)換Leapsecond閏秒Atomictimewhichisinsertedaleapsecondoccasionallytokeepinstepwithastronomicaltime原子時間偶爾插入閏秒，與天文時間保持一致InternationalAtomicTime13LeapsecondTAIsecondsareofconstantlength,unlikesolarseconds.Leapsecondsareintroducedwhennecessarytokeepinphasewiththesun.

TAI秒的長度不變，不像太陽秒。必要時引入閏秒與太陽保持同步。14Greenwichmeantime格林威治標(biāo)準(zhǔn)時間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范圍內(nèi)Ci

:pi’sclockI:anintervalofrealtime真實時間間隔External&Internalsynchronization(1)17Internalsynchronization內(nèi)部同步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協(xié)議Sender:sendM(t)Receiver:settimetot+TtransBoundsareknowinsynchronoussystem范圍在同步系統(tǒng)中是已知的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消息傳輸?shù)淖钚⊙舆tismin,thenaccuracy:(Tround/2–min)Cristian’smethodofsynchronizingclocks(2)tt+Tround-mint+Tround/2t+mint+Tround23Internalsynchronization內(nèi)部同步Themaster

pollstheslaves’clocks主輪詢從時鐘Themaster

estimatestheslaves’clocksbyround-triptime主人通過往返時間估計從時鐘SimilartoChristian’salgorithm類似于基督教的算法Themaster

averagestheslaves’clockvalues主人對從站的時鐘值進(jìn)行平均Cancelouttheindividualclock’stendenciestorunfastorslow取消個別時鐘的趨勢，以快速或慢速運行TheBerkeleyalgorithms24Themastersendsbacktotheslavestheamountthattheslaves’clocksshouldadjustby主機(jī)向從站發(fā)回從站的時鐘應(yīng)該調(diào)整的量Positiveornegativevalue正值或負(fù)值A(chǔ)voidfurtheruncertaintyduetothemessagetransmissiontime避免由于消息傳輸時間進(jìn)一步的不確定性Slaveajustitsclock從時鐘調(diào)整TheBerkeleyalgorithms(2)25TheBerkeleyAlgorithm(3)(a)Thetimedaemon時間守護(hù)進(jìn)程asksalltheothermachinesfortheirclockvalues.

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

frequentlytooffsettheratesofdriftfoundinmostcomputersSecurityProtectagainstinterferencewiththetimeserviceDesignaimsofNetworkTimeProtocol29外部同步使互聯(lián)網(wǎng)上的客戶端能夠準(zhǔn)確地同步到UTC可靠性可以長時間連接的損失冗余服務(wù)器和服務(wù)器之間的冗余路徑可擴(kuò)展性使客戶端能夠頻繁地重新同步，以抵消大多數(shù)計算機(jī)中發(fā)現(xiàn)的漂移速率安全防止干擾時間服務(wù)網(wǎng)絡(luò)時間協(xié)議的設(shè)計目標(biāo)30ReconfigurewhenserversbecomeunreachableNetworkTimeProtocolArchitecture123233Note:Arrowsdenotesynchronizationcontrol,numbersdenotestrata.31MulticastmodeIntendforuseonahighspeedLANAssumingasmalldelayLowaccuracybutefficientProcedure-callmodeSimilartoChristian’sHigheraccuracythanmulticastSymmetricmodeThehighestaccuracySynchronizationmeasures32組播模式適合在高速LAN上使用假設(shè)延遲很小精度低但效率高程序呼叫模式類似于基督徒精度高于多播對稱模式最高的準(zhǔn)確性同步措施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不適合處理不涉及消息傳輸?shù)膮f(xié)作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網(wǎng)絡(luò)時間協(xié)議Logicaltime邏輯時間Happen-beforerelation發(fā)生之前關(guān)系Lamporttimestampalgorithm拉姆波特時間戳算法Vectorclock矢量時鐘Summary46Globalstates全球狀態(tài)Consistentcut,consistentstate一致切割，一致狀態(tài)Snapshotalgorithm快照算法Constructreachabilityrelationshipbysnapshot通過快照構(gòu)建可達(dá)性關(guān)系Summary…continuedCoordinationandAgreement協(xié)調(diào)與協(xié)議481.Distributedmutualexclusion分布式互斥2.Elections選舉3.SummaryOutline49MutualExclusionToguaranteeconsistencyamongdistributedprocessesthatareaccessingsharedmemory,itisnecessarytoprovidemutualexclusion

whenaccessingacriticalsection.為了保證正在訪問共享內(nèi)存的分布式進(jìn)程之間的一致性，必須在訪問臨界區(qū)時提供互斥。Assume

nprocesses.50AssumptionAsynchronous,noprocessfail,reliablechannel異步，沒有進(jìn)程失敗，可靠的通道Applicationlevelprotocolenter()resourceAccesses()exit()Algorithmsformutualexclusion51EssentialrequirementsformutualexlcusionSafetyAtmostoneprocessmayexecuteinthecriticalsectionatatimeLivenessRequeststoenterandexitthecriticalsection(CS)eventuallysucceedFreefromdeadlockandstarvationOrderingIfonerequesttoentertheCShappened-beforeanother,thenentrytotheCSisgrantedinthatorderAlgorithmsformutualexclusion52互斥的基本要求安全一次最多可以在關(guān)鍵部分執(zhí)行一個進(jìn)程活躍進(jìn)入和退出關(guān)鍵部分（CS）的請求最終成功沒有死鎖和饑餓順序如果進(jìn)入CS的一個請求發(fā)生在另一個之前，則按照該順序授予對CS的輸入互斥算法53EvaluatetheperformanceofthealgorithmsBandwidthconsumedThenumberofmessagessentineachentryandexitoperationClientDelayIncurredbyaprocessateachentryandexitoperationsAlgorithmsformutualexclusion…continued54評估算法的性能帶寬消耗在每個進(jìn)入和退出操作中發(fā)送的消息數(shù)客戶延遲在進(jìn)入和退出操作過程中發(fā)生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互斥的集中算法假設(shè)一個協(xié)調(diào)者已經(jīng)當(dāng)選了。1.進(jìn)程向協(xié)調(diào)者發(fā)送消息，請求進(jìn)入關(guān)鍵部分的許可。如果關(guān)鍵部分中沒有其他進(jìn)程，則授予權(quán)限。2.如果另一個進(jìn)程要求進(jìn)入相同關(guān)鍵區(qū)域的權(quán)限，則協(xié)調(diào)器不會回復(fù)（或者它發(fā)送“被拒絕的權(quán)限”）并對請求進(jìn)行排隊。3.當(dāng)一個進(jìn)程退出臨界區(qū)時，它向協(xié)調(diào)器發(fā)送一個消息。4.協(xié)調(diào)者從隊列中選擇第一個，并向該進(jìn)程發(fā)送一個消息，授予進(jìn)入關(guān)鍵部分的權(quán)限。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協(xié)調(diào)者崩潰Performancebottleneck性能瓶頸ACentralizedAlgorithm(4)61ADistributedAlgorithm(1)Threedifferentcases:Ifthereceiverisnotaccessingtheresourceanddoesnotwanttoaccessit,itsendsbackanOKmessagetothesender.Ifthereceiveralreadyhasaccesstotheresource,itsimplydoesnotreply.Instead,itqueuestherequest.Ifthereceiverwantstoaccesstheresourceaswellbuthasnotyetdoneso,itcomparesthetimestampoftheincomingmessagewiththeonecontainedinthemessagethatithassenteveryone.Thelowestonewins.62分布式算法(1)三種不同的情況：如果接收方?jīng)]有訪問資源，并且不想訪問該資源，則它向發(fā)送方發(fā)回一條OK消息。如果接收者已經(jīng)可以訪問資源，它根本就不會回復(fù)。相反，它會排隊請求。如果接收方想要訪問資源，但還沒有這樣做，它將傳入消息的時間戳與發(fā)送給每個人的消息中包含的時間戳進(jìn)行比較。最低的一個勝利。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任何進(jìn)程崩潰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等待操作根據(jù)總順序執(zhí)行Maekawa’svotingalgorithm711.Distributedmutualexclusion2.Elections3.SummaryOutline72ElectionAlgorithmsManydistributedalgorithmssuchasmutualexclusionanddeadlockdetectionrequirea

coordinatorprocess.Whenthecoordinatorprocessfails,thedistributedgroupofprocessesmustexecuteanelectionalgorithmtodetermineanewcoordinatorprocess.Thesealgorithmswillassumethateachactiveprocesshasauniquepriorityid.

73選擇算法Manydistributedalgorithmssuchasmutualexclusionanddeadlockdetectionrequirea

coordinatorprocess.許多分布式算法，如互斥和死鎖檢測需要協(xié)調(diào)程序。Whenthecoordinatorprocessfails,thedistributedgroupofprocessesmustexecuteanelectionalgorithmtodetermineanewcoordinatorprocess.當(dāng)協(xié)調(diào)程序進(jìn)程失敗時，分布式進(jìn)程組必須執(zhí)行選擇算法來確定新的協(xié)調(diào)程序進(jìn)程。Thesealgorithmswillassumethateachactiveprocesshasauniquepriorityid.這些算法將假設(shè)每個活動進(jìn)程具有唯一的優(yōu)先級id。74ElectionChooseauniqueprocesstoplayaparticularroleDefinetheelection:choosethelargestidentifierE.g.forelectingtheprocesswithlowestload,thenid=1/loadEvaluatetheperformanceofelectionalgorithmTotalbandwidthutilizationTurnaroundtimeThenumberofserializedmessagetransmissiontimesbetweentheinitiationandterminationofasinglerunSomeconceptsaboutElectionalgorithm75選舉選擇一個獨特的過程來發(fā)揮特定的作用確定被選者：選擇最大的標(biāo)識符例如，用于選擇最低負(fù)載的過程，則id=1/負(fù)載評估選舉算法的性能總帶寬利用率周轉(zhuǎn)時間在單次運行的啟動和終止之間的序列化消息傳輸時間的數(shù)量選擇算法一些概念76AssumptionSynchronoussystemUsetimeouttodetectaprocessfailureReliablefailuredetectorProcesscancommunicatewithprocesseswhichhavehigheridentifiershigherprocesses&lowerprocessesThebullyalgorithm77假設(shè)同步系統(tǒng)使用超時來檢測進(jìn)程故障可靠的故障檢測器進(jìn)程可以與具有更高標(biāo)識符的進(jìn)程通信更高的流程和更低的流程Thebullyalgorithm78ThebullyalgorithmTheBullyAlgorithm1.PsendsanELECTIONmessagetoallprocesseswithhighernumbers.2.Ifnooneresponds,Pwinstheelectionandbecomescoordinator.3.Ifoneofthehigher-upsanswers,ittakesover.P’sjobisdone.79Thebullyalgorithm欺負(fù)算法1.P發(fā)送一個ELECTION消息給所有具有較高數(shù)字的進(jìn)程。2.如果沒有人回應(yīng)，P贏得選舉，成為協(xié)調(diào)員。3.如果其中一個高層回答，它將接管。P的工作完成了。80TheBullyAlgorithm(1)(a)Process4holdsanelection.(b)Processes5and6respond,telling4tostop.(c)Now5and6eachholdanelection.81TheBullyAlgorithm(2)(d)Process6tells5tostop.(e)Process6winsandtellseveryone.82Evaluatetheperformance評估性能bandwidthbest

=N-2Thesecondhighestprocessinitiatetheelection第二高的進(jìn)程開始選舉SendN-2coordinatormessagetolowerprocessesTurnaroundtime=1messagebandwidthworst

:O(N2)Thelowestprocessinitiatetheelection

Thebullyalgorithm…continued83ARingAlgorithmAssumetheprocessesarelogicallyorderedinaring{impliesasuccessorpointerandanactiveprocesslist}

thatisunidirectional.Whenanyprocess,P,noticesthatthecoordinatorisnolongerrespondingitinitiatesanelection:1.PsendsmessagecontainingP’sprocessidtothenextavailablesuccessor.84ARingAlgorithm假設(shè)這些進(jìn)程在一個環(huán)中被邏輯地排序（這意味著一個獨立的后繼指針和一個活動的進(jìn)程列表）。當(dāng)任何進(jìn)程P發(fā)現(xiàn)協(xié)調(diào)員不再響應(yīng)時，會啟動一個選舉：P將包含P進(jìn)程標(biāo)識的消息發(fā)送到下一個可用的后繼。85ARingAlgorithm2.

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

86ARingA