分布式系統(tǒng)時鐘同步

1、同 步寇迦南1.時鐘同步 時鐘同步例子：UNIX中make程序的調(diào)用問題。 時鐘同步例子：UNIX中make程序的調(diào)用問題Make程序的作用是什么？ 可以自動完成對源文件的編譯。 時鐘同步UNIX系統(tǒng)會把較大的程序分成多個源程序，當一個源文件發(fā)生變化時（比如被修改后），只需編譯一個文件即可，不需要對所有的文件進行編譯。 時鐘同步這個過程如何進行？ 時鐘同步這個過程如何進行？當調(diào)用make程序時， make程序根據(jù)所有源文件和對應目標文件的修改時間來決定是否對某個源文件重新編譯。 時鐘同步例如：如果源文件input.c.c的修改時間為5155且對應目標文件input.o.o的修改時間為5151，

2、那么，make程序知道input.c.c已被修改。input.c必須被重新編譯。input.oinput.oinput.cinput.c51515155t 時鐘同步例如：如果源文件output.c.c的修改時間為5144且對應目標文件output.o.o的修改時間為5145，那么，不需要對output.c.c進行重新編譯。output.coutput.coutput.ooutput.o51445145t 時鐘同步make程序在考察完所有源文件和其對應目標文件的修改時間后決定哪些文件需要重新編譯并調(diào)用編譯器對其進行編譯。時鐘同步在分布式環(huán)境中，由于時間不同步會造成的程序不能正常運行。時鐘同步在分

3、布式環(huán)境中，由于時間不同步會造成的程序不能正常運行。時鐘同步假定output.o的修改時間為5144，output.c被修改并賦予的時間為5143，原因是output.c所在機器上的時鐘要比output.o所在機器上的時鐘慢。創(chuàng)建創(chuàng)建 output.ooutput.o51445145t進行編譯的進行編譯的計算機計算機51465147根據(jù)本地時根據(jù)本地時鐘的時間鐘的時間創(chuàng)建創(chuàng)建 output.coutput.c51425143t進行編譯的進行編譯的計算機計算機51445145根據(jù)本地時根據(jù)本地時鐘的時間鐘的時間時鐘同步因此，make程序不調(diào)用編譯器進行編譯。結(jié)果，最終的可執(zhí)行的二進制程序?qū)?/p>

4、舊的源文件和新的源文件所產(chǎn)生的混合目標文件，導致該可執(zhí)行程序無法運行而程序員卻不知道原因而一直尋找代碼的錯誤。時鐘同步結(jié)論：在分布式系統(tǒng)中，時鐘同步是非常重要的，也是必不可少的。p 物理時間概念 UTC（統(tǒng)一協(xié)調(diào)時間），它是所有現(xiàn)代人使用的時間。時鐘同步算法如果一臺機器上有一個WWV接收器接收標準時間，那么，時間同步算法的就是讓所有機器的時鐘與該機器的時鐘進行同步。如果沒有一臺機器具有WWV接收器且每一臺機器都有自己的時鐘，那么時鐘同步算法的就是使得所有機器的時鐘盡可能地一致。系統(tǒng)基礎模型系統(tǒng)基礎模型1. 2. 3. 時鐘同步算法：p 基本思想一臺機器設為時間服務器（帶有衛(wèi)星接收器）其他的每一

5、臺機器周期性地向時間服務器發(fā)送請求消息已獲得當前標準時間。時間服務器在短時間內(nèi)將包含當前時間的消息發(fā)送給請求時間機器。發(fā)送機器收到此消息后，將機器時鐘調(diào)到與時間服務器一致的標準狀態(tài)。時鐘同步算法：時鐘同步算法：p 存在問題 發(fā)送者如何根據(jù)時間服務器的返回值調(diào)整時間？ 由于時間不能倒退，因此一種方法是根據(jù)時鐘快慢，中斷服務程序調(diào)整（增大或減?。┟看沃袛嗨拥臅r間。時鐘同步算法：p 存在問題 如何處理從時間服務器發(fā)送的應答到發(fā)送者存在的延遲？ 精確記錄從向時間服務器發(fā)送請求的起始時間T0和接受到的應答的結(jié)束時間T1 。 當前服務器時間估計值 = CUTC+(T0- T1)/2 如果考慮服務器中斷處

6、理的時間I，那么傳輸?shù)臅r間間隔為TI- T0=I ,單向傳輸時間為它的一半。時鐘同步算法：p 基本思想 主動式服務-與中的被動式時間服務器相反 適合于沒有WWV接收器的系統(tǒng) 時鐘同步算法：p 過程 服務器主動定期詢問每臺機器的時間 服務器基于客戶的回答，告知它們撥快或者撥慢時間時鐘同步算法：p 實現(xiàn)方法a)a)時間守衛(wèi)程序向所有時間守衛(wèi)程序向所有其他機器詢問時鐘值其他機器詢問時鐘值b)b)其他其他機器做出應答機器做出應答c)c)時間守衛(wèi)時間守衛(wèi)程序通知每程序通知每臺機器如何調(diào)整他們臺機器如何調(diào)整他們的時鐘的時鐘時間守衛(wèi)程序時間守衛(wèi)程序a)b)c)時鐘同步算法：p 實現(xiàn)方法a) a) 在在3:0

7、03:00中時，中時，時間守衛(wèi)程序時間守衛(wèi)程序把它的時間告訴其他機器把它的時間告訴其他機器，并并詢問他們各自的時間詢問他們各自的時間。b)b) 各臺機器將它們各臺機器將它們各自的時間各自的時間與與時間守護程序時間的差值時間守護程序時間的差值告訴告訴時間守護進程時間守護進程。c) c) 有了這些值，有了這些值，時間守護程序時間守護程序計算出它們的平均值計算出它們的平均值，并通，并通知知各臺機器如何調(diào)整各自的各臺機器如何調(diào)整各自的時鐘時鐘。時間守衛(wèi)程序時間守衛(wèi)程序a)b)c)時鐘同步算法：和時鐘同步算法：p 基本思想 將時間分成固定長度的再同步間隔R 第i次同步開始于T0+iR，結(jié)束于T0+(i+

8、1)R 每次同步間隔開始，每臺機器廣播自己的時間 對于某一具體的機器，當所有的同步廣播都到達后，它根據(jù)所有的時間執(zhí)行某一平均算法得到一新值，再根據(jù)新值調(diào)整時鐘2.邏輯時鐘p 基本概念 許多應用中，并不嚴格要求所有的機器都與UTC時間保持一致，而只需要所有機器時間相同就夠了，即系統(tǒng)保持一個內(nèi)部一致的時鐘。這種時鐘稱為邏輯時鐘。更進一步，很多問題中根本就不需要時間嚴格一致，而只是需要多個事件的發(fā)生順序一致就可以。如果兩個進程不進行交互，那么它們的時鐘也無須同步。這是因為即使沒有同步也察覺不出來，并且也不會產(chǎn)生問題。通常重要的不是所有的進程在時間上完全一致，而是它們在事件的發(fā)生順序上要達成一致。p

9、Lamport 時間戳 為了同步邏輯時鐘，Lamport定義了一個稱作“先發(fā)生”的關(guān)系。事件a先發(fā)生，然后b才發(fā)生 如果a和b是同一個進程的兩個事件，如果a在b之前發(fā)生，則ab為真 如果a是一個進程發(fā)生消息的事件， b是另一個進程的接收消息事件，則ab也為真先發(fā)生關(guān)系是一個傳遞關(guān)系，若ab且bc ，則ac 。先發(fā)生關(guān)系 ab 如果x和y事件發(fā)生在兩個互不交換消息的進程中， xy不真， yx也不真。 這兩個事件稱為并發(fā)的，意味著無法說這兩個事件什么時候發(fā)生，哪個事件先發(fā)生。并發(fā)事件p Lamport 時間戳 我們需要一種，使得對于每個時間a，我們都能為它分配一個所有進程都認可的時間值C(a)。

10、這些時間值必須具有如下性質(zhì)：如果ab，那么C(a) C(b)。 若在同一進程中a在b之前發(fā)生，則C(a) C(b) 。 若a和b分別表示發(fā)送一個消息和接收該消息的事件，則C(a) C(b) 。p Lamport 時間戳 時間值C是一直向前走的（即增加），不會向后退（即減少）。 校正時間的操作總是給時間加上一個正值，而不能是減掉一個正值，時間的修改只能增加而不能減少。在a)中有三個進程。每一個進程都運行 在不同的機器上。每一個機器都有一個自己的時鐘。并且以各自的速度向前走。Step 1當進程0中的時鐘滴答6次時；進程1滴答了8次；進程3滴答10次。Step 2在時間為6時，進程0發(fā)送了一個消息A

11、給進程1，進程1在時間為16時收到了消息。如果消息中含有消息開始發(fā)送的時間值6，則進程1認為該消息的傳輸花費了10次滴答。Step 316-6=10同理，消息B從進程1傳輸?shù)竭M程2花費了16次滴答Step 440-24=16但是，由進程2發(fā)送給進程1的消息C在發(fā)送時的時間值為60而在接收時時間值為56。這樣，消息C的傳輸時間為負值。Step 5Lamport解決這個問題的算法：每一個消息都含有一個發(fā)送者時鐘的發(fā)送時間，當消息到達時，接受者將自己時鐘的接收時間與發(fā)送時間相比較。如果接收時間小于等于發(fā)送時間，則接收者的時鐘被修改成發(fā)送時間加1。如果接收時間大于發(fā)送時間，則不改變接受者的時鐘。因此消息C到達進程1的時間改為61消息D到達進程0的時間改為70。Step 6p Lamport算法還需滿足一個要求：任意兩個事件的時間之