時鐘同步

時鐘同步(Clock synchronization)計算機科學工程學中的一個概念,旨在協調多個獨立的時鐘。現實中的多個時鐘,即使時間已調至一致,但在一段時間後依然會因為時鐘漂移英語clock drift而顯示不同的時間,因為它們計時的速率會略有差異。時鐘計時速率的差異會造成多種問題,但已有多種解決方案,最佳的解決方案須由實際情況決定。[1]

術語

串行通信中,時鐘同步可以指代時鐘恢復英語clock recovery,即頻率同步,與相位同步英語phase synchronization相對。這種時鐘同步被用在電信通信中的同步電信通信中的同步英語synchronization in telecommunications與波特率自動檢測波特率自動檢測英語automatic baud rate detection[2]

准同步英語plesiochronous system等時英語isochronous操作指一個系統具有頻率同步,但並沒有嚴格要求相位同步。同步操作對時間(可能包括頻率)具有更高的同步要求。

問題

如果無法在更小的尺度管理時間,在具有較高時間同步要求的分佈式計算中,會產生許多因時間偏移引發的問題。

例如,在 Unix 系統中,make 命令可用於增量編譯代碼,並避免編譯已經編譯過且未發生改變的代碼。make 命令使用主機的時鐘來確定哪些原始碼需要編譯,如果原始碼處於另一台單獨的文件伺服器上,而兩者時鐘不一致,make 就可能導致錯誤的結果。[3]

解決方案

在一個具有中心伺服器的系統中,同步方案較為簡單:由這個中心伺服器指示時間。在這種環境中,Cristian 算法英語Cristian's algorithmBerkeley 算法英語Berkeley algorithm可能是最佳的解決方案。

分佈式系統中,問題變得更為複雜,因為並沒有全局通用的時間。在互聯網上最常用的時鐘同步協議是 NTP,採用 UDP 通信,並形成層級的客戶端 - 服務端架構。分佈式系統的邏輯時鐘英語logical clock涉及到的概念包括 Lamport 時間戳英語Lamport timestamps向量時鐘英語vector clock

在無線網絡中,因為其不穩定性,包括同步數據包的碰撞等,這一問題變得更為艱難。[4][5]

Berkeley 算法

Berkeley 算法英語Berkeley algorithm 適用於無線電時鐘(radio clock)不可用的分佈式系統,此類系統無法得知真實時間,只能通過維護一個全局的平均時間作為標準時間。一台時間伺服器會周期性地獲取各個客戶端上的時間,將其平均處理後,回傳每個客戶端的時間與平均時間的偏移,以達到統一使用此平均時間的目的。此算法適用於不僅時間可能不一致,時鐘速率也可能不一致的系統。

如果一個客戶端的時間偏移過大,超出了容忍值,則通常不會參與平均時間的計算。如此可以防止系統的時間被單個異常的時鐘過度影響。

時鐘採樣網絡互同步

Cristian 算法

GPS 時鐘

靶場儀器組時間碼

網絡時間協議

精確時間協議

基礎設施參考點廣播同步

同步以太網

Ad-hoc 無線網絡中的時間同步

參考文獻

  1. ^ Tanenbaum, Andrew S.; van Steen, Maarten, Distributed Systems : Principles and Paradigms, Prentice Hall, 2002, ISBN 0-13-088893-1 
  2. ^ Norman Matloff, Transmission on a Serial Line (PDF), September 3, 2001 [2018-04-17], (原始內容存檔 (PDF)於2020-09-22) 
  3. ^ Marco Platania. Clock Synchronization (PDF): 11. 2018-06-03 [2018-08-25]. (原始內容存檔 (PDF)於2020-09-22). 
  4. ^ Maróti, Miklós; Kusy, Branislav; Simon, Gyula; Lédeczi, Ákos. The Flooding Time Synchronization Protocol. Proceedings of the 2nd International Conference on Embedded Networked Sensor Systems. SenSys '04 (New York, NY, USA: ACM). 2004: 39–49. ISBN 1581138792. doi:10.1145/1031495.1031501. 
  5. ^ Koo, Jinkyu; Panta, Rajesh K.; Bagchi, Saurabh; Montestruque, Luis. A Tale of Two Synchronizing Clocks. Proceedings of the 7th ACM Conference on Embedded Networked Sensor Systems. SenSys '09 (New York, NY, USA: ACM). 2009: 239–252. ISBN 9781605585192. doi:10.1145/1644038.1644062.