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

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

　　按優(yōu)先級降低的次序逐條校驗消息是否可調度，就可驗證整個(gè)通信系統是否可調度。

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

表1 Tindell算法的反例

圖2 消息C的最壞響應時(shí)間為3.5 ms

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

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

2 筆者對Davis算法的簡(jiǎn)化

　　Davis算法要先算出忙周期，再在忙周期中消息m多次傳送中尋找最壞等待最大的那次?；谝韵驴紤]，計算可以簡(jiǎn)化：

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

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

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

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

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