潘 雷

*卡斯柯信號(hào)有限公司 工程師，200071 上海

1 時(shí)鐘同步介紹

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

三取二平臺(tái)中，3個(gè)通道獨(dú)立工作，但需要進(jìn)行準(zhǔn)確的時(shí)鐘同步，否則無(wú)法獲取相同的輸入值，也無(wú)法獲得一致的運(yùn)算時(shí)序，最終就無(wú)法進(jìn)行三取二的運(yùn)算而獲取正確的結(jié)果，所以時(shí)鐘同步對(duì)三取二平臺(tái)而言是最為基本的功能需求。

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

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

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

2 時(shí)鐘同步基本概念

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

2.1 時(shí)鐘周期

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

2.2 時(shí)鐘漂移

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

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

2.3 一致性

相同正確的物理時(shí)鐘之間有一個(gè)正常的擺動(dòng)范圍:

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

2.4 精確性

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

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

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

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

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

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

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

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

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

圖1 通道時(shí)鐘同步圖

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

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

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

表1 變量參數(shù)表

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

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

4 初始化、升級(jí)操作

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

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

5 結(jié)論

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

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