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

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

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

表1 Tindell算法的反例

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

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

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

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

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

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

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

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

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

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