CAN調(diào)度理論與實(shí)踐分析

CAN總線中消息能否按時送達(dá)是事關(guān)系統(tǒng)安全等問題的重要指標(biāo)，它要通過調(diào)度分析加以驗(yàn)證。本文介紹CAN調(diào)度理論的新研究成果，以及對工程應(yīng)用的指導(dǎo)意義及其實(shí)施難點(diǎn)。具體分為4個部分：Tindell的分析方法和Davis的改進(jìn)；筆者對Davis算法的簡化；最壞響應(yīng)時間分析在應(yīng)用上的一些結(jié)果；調(diào)度分析在應(yīng)用上的難處。

關(guān)鍵詞? CAN? 調(diào)度理論? 響應(yīng)時間? Davis算法? Tindell算法

　　分布式嵌入式系統(tǒng)是當(dāng)前嵌入式系統(tǒng)的重要發(fā)展方向，因?yàn)樗芴峁└鼜?qiáng)的性能，節(jié)約系統(tǒng)的總體成本。但是由于各單個節(jié)點(diǎn)必須有通信網(wǎng)絡(luò)相連才能協(xié)調(diào)地工作，網(wǎng)絡(luò)就成了關(guān)鍵部分，沒有網(wǎng)絡(luò)提供及時正確的數(shù)據(jù)和命令，就談不上所設(shè)計(jì)的系統(tǒng)服務(wù)了。在汽車的分布式嵌入式系統(tǒng)中，目前主流的通信網(wǎng)絡(luò)是CAN總線。CAN是事件觸發(fā)的通信協(xié)議，它根據(jù)消息的優(yōu)先等級和節(jié)點(diǎn)的狀態(tài)自動地調(diào)度消息的傳送。低優(yōu)先級的消息會因同時發(fā)生的高優(yōu)先級消息太多而不能及時發(fā)送，高優(yōu)先級消息也有可能由于節(jié)點(diǎn)狀態(tài)等的影響而丟失。關(guān)于CAN的局限問題可見參考文獻(xiàn)[1]。本文主要從調(diào)度理論方面討論CAN系統(tǒng)的問題，這些問題與工程應(yīng)用有非常大的關(guān)系，實(shí)踐意義很強(qiáng)。

1? Tindell的分析方法和Davis的改進(jìn)

　　1994年，Tindell [23]首先將分析單處理器任務(wù)調(diào)度方法改造成適用于CAN總線的調(diào)度方法，求取消息的最壞響應(yīng)時間。對于與安全相關(guān)的應(yīng)用，只有對最壞響應(yīng)時間有確切的掌握，才是合理的。CAN通信在網(wǎng)絡(luò)上的實(shí)現(xiàn)經(jīng)過2個階段：通信任務(wù)將消息發(fā)到發(fā)送的通信控制器(CC)，發(fā)送的通信控制器將消息發(fā)到接收的通信控制器。廣義地講，響應(yīng)時間是從需產(chǎn)生通信的事件發(fā)生到消息到達(dá)目標(biāo)節(jié)點(diǎn)的時間，包括發(fā)送節(jié)點(diǎn)host內(nèi)的處理時間，host到CC的時間，總線上消息仲裁傳送時間，接收CC到host的處理時間。仲裁獲勝的消息開始傳送后，便不能被中止，所以CAN調(diào)度是固定優(yōu)先級非搶先式任務(wù)調(diào)度。消息m用到的參數(shù)定義如下:

　　Tm ——啟動通信的事件間隔，即周期；
　　Jm——由事件發(fā)生到消息開始送CC的時間之最大變化，即抖動；
　　Cm—— 在總線上傳送消息m所需時間（要考慮位填充形成的最大值）；
　　Dm——由應(yīng)用決定的傳送消息m允許的時限；
　　Rm——實(shí)際的最壞傳送時間；
　　Wm——傳送消息m時最壞等待時間。

　　它們之間的關(guān)系如圖1所示。

圖1? 用于調(diào)度分析的時間參數(shù)

　　Wm由2部分構(gòu)成：由低于優(yōu)先級m的消息（其集合寫為lp(m)）正在總線上傳送而造成的阻塞Bm，和由高于優(yōu)先級m的消息（其集合寫為hp(m)）在總線上搶先傳送而造成的干擾Im。它們?nèi)∽畲笾禃r就使Wm成為最壞等待時間。

　　為了印刷的方便和易于理解，這里用了不同的寫法，其中頂函數(shù)Ceiling返回的是最接近（大于等于）變量的上限整數(shù), τ是1位時間。Ceiling( (Wm+Jk+τ)/Tk)表示在Wm時段內(nèi)高優(yōu)先級消息k會出現(xiàn)的最多次數(shù)。于是有：

　　Wm取離散值且出現(xiàn)在非線性方程(4)的兩邊，所幸的是其求解并不難。在式(5)中，用W0m=Bm作為初值循環(huán)求解即可。

　　式(7)代表最壞等待時間已超時限，消息m不可調(diào)度。

　　按優(yōu)先級降低的次序逐條校驗(yàn)消息是否可調(diào)度，就可驗(yàn)證整個通信系統(tǒng)是否可調(diào)度。

　　在2006年實(shí)時網(wǎng)絡(luò)會議上，Bril、Davis等人發(fā)表了有關(guān)Tindell算法有漏洞的文章，后來他們又提出了完整的改進(jìn)算法[4]。作為反例，表1中消息C用Tindell算法是可調(diào)度的，最壞響應(yīng)時間為3 ms；但第2次消息C的傳送已超時限，如圖2所示。Tindell算法僅考慮了消息C的第1次傳送。

表1? Tindell算法的反例

圖2? 消息C的最壞響應(yīng)時間為3.5 ms

　　另外，如將消息B和C的周期縮短為3.25 ms，按照Tindell算法，系統(tǒng)由于未求得最大的最壞響應(yīng)時間，故仍是可調(diào)度的，但實(shí)際上總線的利用率已超過100%。Davis的方法核心是引入忙周期的概念，再對忙周期內(nèi)各次傳送的響應(yīng)時間求最壞值，詳見附錄1。（見本刊網(wǎng)站www.mesnet.com.cn——編者注。）

　　Tindell的開創(chuàng)性工作對后續(xù)的研究與應(yīng)用有巨大的影響，Volcano通信技術(shù)公司(現(xiàn)在的Mentor Graphics)以此理論為基礎(chǔ)開發(fā)了商用的CAN調(diào)度分析軟件。由于漏洞的發(fā)現(xiàn)，用戶應(yīng)檢驗(yàn)軟件是否有了新的補(bǔ)丁以及用它完成的應(yīng)用是否受影響。

2? 筆者對Davis算法的簡化

　　Davis算法要先算出忙周期，再在忙周期中消息m多次傳送中尋找最壞等待最大的那次。基于以下考慮，計(jì)算可以簡化：

　　在忙周期中，消息m傳送時有高優(yōu)先級消息進(jìn)入隊(duì)列，使m的后續(xù)消息發(fā)送前可能插入更多的高優(yōu)先級消息，代表仍有一個對總線需求的高峰，從而有可能使后面的消息m有更大的最壞響應(yīng)時間。

　　最壞的情形是消息m剛發(fā)送，所有高優(yōu)先級消息就進(jìn)入隊(duì)列，即領(lǐng)先于發(fā)完消息m后的第一個發(fā)送空隙的相位達(dá)到最大。

　　因此求消息m的最壞響應(yīng)時間就有兩種可能： 用Bm產(chǎn)生阻塞，像Tindell那樣求消息m的最壞響應(yīng)時間；由Cm產(chǎn)生阻塞，求下一個消息m的最壞響應(yīng)時間，下一個消息m的排隊(duì)時間為Tm-Jm。

　　簡化方法的優(yōu)點(diǎn)是減少了計(jì)算的次數(shù)，從而減少工作量。

　　這種算法與Davis算法中的保守算法有兩點(diǎn)不同：一是用Cm來產(chǎn)生阻塞是真實(shí)可能發(fā)生的，例如從休眠到上電時消息m比高優(yōu)先級消息早了一點(diǎn)；二是本算法得到的是確切的而非保守的結(jié)果。

　　計(jì)算方法：

　　第1次，用公式（5）～（7）計(jì)算Wm，得到Wm(0)；

　　第2次，用公式

　　對表1所列的例子，按本節(jié)方法有: W0m(1)= Tm-Jm=3.5,W1m(1)=5,W2m(1)=6，W3m(1)=6。所以有Wm(1)=6-3.5=2.5, Wm=2.5,最壞響應(yīng)時間為3.5 ms，與Davis的結(jié)果相同；而按Davis的保守算法，Wm=6。至于系統(tǒng)是否可調(diào)度，仍然要求每個消息都可調(diào)度。

3? 最壞響應(yīng)時間分析在應(yīng)用上的一些結(jié)果

3.1? 總線利用率低不能保證可調(diào)度性

　　有人憑經(jīng)驗(yàn)認(rèn)為，總線利用率＜30%時，性能便有了保證。其實(shí)不然，為了證明這一點(diǎn)，Davis等構(gòu)造了一個例子，如表2所列。

表2? 總線利用率低與可調(diào)度性無直接關(guān)系舉例

圖3? n=1時表2消息X的傳送過程

　　當(dāng)I和L的周期增加到任意大時，其占用的總線時間可以忽略不計(jì)。此時總線利用率為：

　　就本例而言，在Ch=Cx=55位（0字節(jié)數(shù)據(jù)）、Ci=135位（8字節(jié)數(shù)據(jù)）、Cl=0時，總線利用率與可調(diào)度性的關(guān)系如表3所列。

表3? 總線利用率與可調(diào)度性的關(guān)系

　　例如在總線利用率為9.2%時，對10條消息也不能進(jìn)行調(diào)度。本例中優(yōu)先級消息的抖動較大，似有點(diǎn)異常。但對偶發(fā)的事件消息，其周期可取較長，如考慮限定相鄰消息間的時間時，就相當(dāng)于本例對T－J的設(shè)定，所以也非完全沒有理由。

3.2? 優(yōu)先級設(shè)計(jì)策略的討論

　　一般的說，消息優(yōu)先級的設(shè)置采用時限或（時限－抖動）單調(diào)遞變的策略，即時限越短的消息設(shè)置的優(yōu)先級越高，但須用可調(diào)度性分析加以驗(yàn)證，并非這樣做最好[4]。例如，表4優(yōu)先級的設(shè)置為A-B-C，是不能調(diào)度的，如圖4所示。此例用11位ID，125 kbps的傳送速率。但將優(yōu)先級改為A—C—B，按計(jì)算結(jié)果是可調(diào)度的，如圖5所示。

表4? 優(yōu)先級設(shè)置的例子

3.3? 硬件選用對可調(diào)度性的影響

　　Tindell [2]比較了兩種通信控制器，認(rèn)為像82C200一類的通信控制器只有一個發(fā)送緩沖器，從而會引起很大的滯后或抖動。例如一個節(jié)點(diǎn)有3個消息要傳送，它們的優(yōu)先級分別為H、 M、 L1，其他節(jié)點(diǎn)的消息優(yōu)先級為L2、 L3、L4。對82C200來說，當(dāng)要發(fā)送H而M已在發(fā)送緩沖器里時，就要中止M的發(fā)送，而將H寫入，H發(fā)完后再將M寫入，由于這些動作都需占用一定時間，而在這些時間里總線可能為其他節(jié)點(diǎn)的消息所占用。一次H的搶先，會造成M多次延遲而引起問題（詳見附錄2）。SJA1000與82C200是兼容的通信控制器，國內(nèi)很多用戶都用它。如果只用于發(fā)一種消息，則沒有什么問題；如多個消息共用一個通信控制器，就必須考慮這個問題了。

4? 調(diào)度分析在應(yīng)用上的難處

　　上述分析方法是十分簡化的，對出錯重發(fā)情形已有的擴(kuò)展處理方法，以錯誤的概率模型為基礎(chǔ)，并未考慮節(jié)點(diǎn)的狀態(tài)。處于bus-off狀態(tài)的節(jié)點(diǎn)是無法調(diào)度的了。因而這種分析總是不完整的，還有待完善。

　　更為困難的是，如果系統(tǒng)不能通過可調(diào)度性，那么提供的補(bǔ)救措施極為有限。因?yàn)門、C均為實(shí)現(xiàn)應(yīng)用功能所必需的，并可能是產(chǎn)品的現(xiàn)成的特性。此時可能要嘗試修改優(yōu)先級的分配，包括利用軟件工具自動分配ID，但這與優(yōu)先級（消息ID）的標(biāo)準(zhǔn)化又背道而馳。同一部件在不同系統(tǒng)應(yīng)用中要裝入不同的ID，容易混淆，對診斷與維修來說也比較困難。

圖4? 優(yōu)先級為A—B—C時不可調(diào)度

圖5? 優(yōu)先級為A—C—B時可調(diào)度

　　即使進(jìn)行可調(diào)度性分析，必須有所有消息的T、C、J三個參數(shù)。其中T、C是供應(yīng)商會提供的，但J不一定會或不一定能提供。由OEM指定T、C、J，然后由供應(yīng)商去滿足訂貨要求。雖然有時可行，但隨著專業(yè)分工的細(xì)化，供應(yīng)商對控制對象的研究更深刻，所以主動權(quán)不全在OEM手里。

　　為了在干擾嚴(yán)重的環(huán)境下可靠地工作，host一般會起用Watchdog功能來防止程序因走飛而失效。J與Watchdog的正常周期有關(guān)，也與Reset后的處理時間有關(guān)。如果程序抗干擾設(shè)計(jì)對數(shù)據(jù)沒有足夠的保護(hù)，則啟動消息發(fā)送的本地時鐘和某些與傳送相關(guān)的狀態(tài)標(biāo)志會失控，使J也失控。一般的說，設(shè)計(jì)者現(xiàn)在還無法遍歷所有的走飛狀態(tài)從而提供有干擾下的J。如果通過測試確定，與軟件有關(guān)的J測試集也是沒保證的。不考慮走飛的J，對CAN調(diào)度分析結(jié)果可信度有所降低。

　　從上述分析可知，像CAN這種事件觸發(fā)的通信協(xié)議，為保證消息不錯過時限，必須進(jìn)行可調(diào)度分析；分析后要使不可調(diào)度的系統(tǒng)變?yōu)榭烧{(diào)度，在實(shí)踐上比較困難。如果要解決host走飛形成的抖動造成通信失常的后果，只能在控制算法上花力氣了，這在時間觸發(fā)協(xié)議中也是一樣的。