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

潘 雷

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

1 時鐘同步介紹

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

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

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

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

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

2 時鐘同步基本概念

通過對相關(guān)參數(shù)進行數(shù)學(xué)量化，能夠比較時鐘同步算法的優(yōu)劣。

2.1 時鐘周期

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

2.2 時鐘漂移

一個正確的物理時鐘應(yīng)該有一個正常的漂移范圍，假設(shè)t2＞t1，則:

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

2.3 一致性

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

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

2.4 精確性

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

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

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

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

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

其中a，b與算法的初始化相關(guān)。

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

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

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

圖1 通道時鐘同步圖

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

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

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

表1 變量參數(shù)表

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

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

4 初始化、升級操作

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

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

5 結(jié)論

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

這種時鐘同步器可以由軟件方式實現(xiàn)，本項目組通過使用串行通信在1 MHz時鐘下，完成1 ms的時鐘同步，誤差在10 μs左右，同時也在硬件中完成相同的實現(xiàn)，精度在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．