1、同 步寇迦南1.時鐘同步 時鐘同步例子：UNIX中make程序的調用問題。 時鐘同步例子：UNIX中make程序的調用問題Make程序的作用是什么？ 可以自動完成對源文件的編譯。 時鐘同步UNIX系統會把較大的程序分成多個源程序，當一個源文件發生變化時（比如被修改后），只需編譯一個文件即可，不需要對所有的文件進行編譯。 時鐘同步這個過程如何進行？ 時鐘同步這個過程如何進行？當調用make程序時， make程序根據所有源文件和對應目標文件的修改時間來決定是否對某個源文件重新編譯。 時鐘同步例如：如果源文件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程序在考察完所有源文件和其對應目標文件的修改時間后決定哪些文件需要重新編譯并調用編譯器對其進行編譯。時鐘同步在分布式環境中，由于時間不同步會造成的程序不能正常運行。時鐘同步在分

3、布式環境中，由于時間不同步會造成的程序不能正常運行。時鐘同步假定output.o的修改時間為5144，output.c被修改并賦予的時間為5143，原因是output.c所在機器上的時鐘要比output.o所在機器上的時鐘慢。創建創建 output.ooutput.o51445145t進行編譯的進行編譯的計算機計算機51465147根據本地時根據本地時鐘的時間鐘的時間創建創建 output.coutput.c51425143t進行編譯的進行編譯的計算機計算機51445145根據本地時根據本地時鐘的時間鐘的時間時鐘同步因此，make程序不調用編譯器進行編譯。結果，最終的可執行的二進制程序將包含由

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

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

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

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

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

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

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

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