三取二平臺的時鐘同步算法

潘 雷

*卡斯柯信號有限公司 工程師，200071 上海

1 時鐘同步介紹

高安全性、高可靠性系統經常會使用三取二平臺作為系統處理器，尤其在鐵路信號領域中，有些設備可能需要持續工作幾年甚至幾十年，并且系統安全完善度等級需達到SIL4，這些需求對硬件的搭建提出了許多苛刻的要求。在搭建三取二平臺中，最重要的有2個功能:第1個是時鐘同步;第2個是數據同步，也稱為數據一致性比較。這里主要介紹時鐘同步算法。

三取二平臺中，3個通道獨立工作，但需要進行準確的時鐘同步，否則無法獲取相同的輸入值，也無法獲得一致的運算時序，最終就無法進行三取二的運算而獲取正確的結果，所以時鐘同步對三取二平臺而言是最為基本的功能需求。

在三取二平臺的時鐘網絡中，由于3個通道分別工作，時鐘是獨立的，故系統無法得知真正準確的絕對時間。時鐘同步的概念就是3個系通過某種算法協商出一個時間，同時需要證明這個協商出來的時間是一個最優的時間估值。

時鐘同步理論中，一般將時鐘同步分為2類:緊耦合時鐘同步和松散耦合時鐘同步 (又稱宏時鐘同步Macro-Synchronisation)。緊耦合時鐘同步是指在同一個時鐘控制下，所有CPU的執行時鐘完全同步。從IEC61508中得知，三取二系統如果需要達到更高的安全性，需要降低三系之間的耦合度，以降低共模系數。在國外的一些三取二系統中，人為地讓三通道錯開一個小的間隙 (tick)進行運算，就是為了降低共模系數;同時由于現在的CPU內部都有鎖相環，所以嚴格的物理時鐘同步已經不現實了，現在廣泛應用的三取二平臺一般采用松散耦合的方式進行時鐘同步。

這里主要討論松散時鐘同步方式。松散時鐘同步下還有2類實現方式:硬件實現和軟件實現。在本質上，這2種方式并沒有什么區別，只是時間同步精度的差別。由于軟件時鐘同步需要一定的運算開銷和數據傳遞開銷，所以在時鐘同步精度上無法和硬件時鐘同步相比，通過對2種時鐘同步方式進行驗證后發現，相同的同步算法精度在2種情況下會相差一個數量級。

2 時鐘同步基本概念

通過對相關參數進行數學量化，能夠比較時鐘同步算法的優劣。

2.1 時鐘周期

這里關注的是T，為邏輯時鐘，也就是需要同步的時鐘;t為物理實際時鐘，而C就是時鐘同步方程。

2.2 時鐘漂移

一個正確的物理時鐘應該有一個正常的漂移范圍，假設t2＞t1，則:

其中，ρ為最大物理時鐘偏差，一般由時鐘源的物理特性決定，從時鐘提供者的數據手冊可以查到，公式說明時鐘漂移為有界的，正確的物理時鐘與實際時間是線性關系。i代表通道號。

2.3 一致性

相同正確的物理時鐘之間有一個正常的擺動范圍:

其中，i和j代表通道號;δ為同一頻率的不同時鐘之間的最大擺動。δ有界，它也是問題所在。如果時鐘完全一致，那么也不存在同步問題。正是由于不同通道之間存在擺動，才有時鐘同步問題，因此這個參數就是我們重點關注的。

2.4 精確性

存在常數γ＞0，它和a、b常數一起使得如下公式成立:

也就是時鐘在有限時間內的誤差可以被2個線性函數包含，即絕對誤差有界。這也是同步時鐘追求的，也就是說，不但要同步而且要精確。

在設計時鐘同步器時，首先需要有這2個要求，然后才能提出合理的解決方案，選定不同參數去滿足這2個需求。

滿足一致性條件表明正確邏輯時鐘之間的最大偏差是有界的;而準確性條件表明正確的邏輯時鐘與實際時間是線性關系。

需要注意到γ是邏輯時鐘漂移率的一個邊界，同時它也是邏輯時鐘的準確性。我們只對那些γ值最小的時鐘同步算法感興趣。而精確性公式 (4)能夠證明γ≥ρ，所以只對滿足這個條件的算法有興趣。如果一個同步時鐘算法是最優的，那么必須滿足:任k≥1，t∈［endk，endk+1］ ，滿足如下

其中a，b與算法的初始化相關。

3 集中－非平均方式同步算法

在時鐘同步算法中，有如下幾種方式:集中方式、一致性方式和概率方式。這里不做詳細介紹，比較常用的方式是集中方式，其下面又有集中－平均方式和集中－非平均方式。為了避免一個通道的失效影響到其他通道 (稱為拜占庭式失效)，集中－平均方式需要至少4個及以上通道，才能做到避免拜占庭失效，它的理念基本上是取平均數，由于不適合三取二模型，這里也不做介紹，這里只介紹集中－非平均方法，適用于三取二的方式。集中－非平均方式同步方程涉及以下內容。

m為最大容忍錯誤通道數，n為通道數，需要滿足如下條件n≥2m+1，在三取二中，n=3，m=1;每一個通道都周期性的尋求時鐘同步 (分布式時鐘同步)，每一個通道到達自己時鐘周期時發布同步信息，同時在給定時間窗內接收到達的時鐘同步消息，如果接收到m+1即2(如果是三取二的話，m=1)條信息，立刻啟動同步，同時將接收到的信息向其他所有通道轉發。見圖1。

圖1 通道時鐘同步圖

從圖1中可以看出，假設通道3最快，通道1其次，通道2最慢。通道3最快而最先到達周期節點，那么它廣播自己到達的消息給所有通道，然后等待。通道1第二快，它在自己的一個給定窗口內接收到來自通道3的同步信息，然后過一段時間它又接收到自己到達的消息，這個時候它相當于接收到了2個通道的同步消息了，可以重新啟動同步計數器，并認定已經同步，同時將自己的同步消息廣播出去，并傳遞所有接收到的消息給其他所有通道。

這個時候通道3接收到了通道1廣播的消息和傳遞的消息，通過消息認定已經有2個通道到達同步了，也可以啟動自己下一個同步周期。同樣通道2接收到通道3廣播過來的同步消息和通道1廣播和傳遞的消息，通過消息確認也發現有2個通道已經到達了，所以不用等待自己的時鐘周期是否真的結束，立刻重新啟動新的時鐘周期來保證同步。

本時鐘同步方式并不是以最快的時鐘為準，而是以中間的時鐘為準，這里給出這個方程的一致性結果，如 (5)式，表1為 (5)式變量。

表1 變量參數表

d為信息傳播延時 (通信延時加上消息驗證延時)，上式近似為δ≈d+2ρR，在給定δ下，可以反推其他參數，這樣就能設計出符合要求的定時器。

在試驗中使用硬件和軟件2種方式進行驗證，R=1ms，即同步時鐘周期為1ms，軟件采用高速串口傳輸;硬件采用TTL電平互聯，由于串口傳輸和驗證d=50 μs，所以，軟件方式的δ≈50 μs，而硬件傳輸延時可忽略，δ≈d+2ρR ≈2ρR ＜ 1 μs，試驗結果與上述數據相當，可見使用此方法進行時鐘同步可以取得比較好的同步效果。

4 初始化、升級操作

初始化操作:這個算法本身就帶有明顯的修正能力，在初始化過程中使用上述方式就能夠完成初始化，只是初始化時對一致性沒有要求，但是正常操作時，如果通道之間的一致性差別大于某個閾值的話，需要切斷該錯誤通道。

升級操作:如果三取二降級為二取二后，經過維護，再次升級到三取二模式，當一個通道p想加入一個系統時，它發送 (加入)消息給系統中當前的所有通道，然后從這些通道接收到消息，被告知當前系統是出于哪個時鐘同步階段k，由于p可能是在同步周期的中期階段開始它的算法，因此它要等到系統進行下一次時鐘同步時方可加入。當通道p接收到k+1次時鐘同步消息時，它將開始其邏輯時鐘

5 結論

可以證明這種時鐘同步方式可以達到最優同步時鐘的要求，同時這樣的時鐘同步器也比較適合三取二系統中使用。

這種時鐘同步器可以由軟件方式實現，本項目組通過使用串行通信在1 MHz時鐘下，完成1 ms的時鐘同步，誤差在10 μs左右，同時也在硬件中完成相同的實現，精度在1 μs左右。

［1］ Srikanth＆ Toueg．Optimal clock synchronization．Journal of the ACM ．1987:624－645．

［2］ David Powell．Generic fault-Tolerant architecture for real－ Time dependable systems．Kluwer Academic Publishers．2001:27 －34．

［3］ Lundelius-Welch ＆ Lynch．A New Fault-Tolerant Algorithm for Clock synchronization．Information and Computation ．1988:1－16．