CAN调度理论与实践分析

　　式(7)代表最坏等待时间已超时限，消息m不可调度。

　　按优先级降低的次序逐条校验消息是否可调度，就可验证整个通信系统是否可调度。

　　在2006年实时网络会议上，Bril、Davis等人发表了有关Tindell算法有漏洞的文章，后来他们又提出了完整的改进算法[4]。作为反例，表1中消息C用Tindell算法是可调度的，最坏响应时间为3 ms；但第2次消息C的传送已超时限，如图2所示。Tindell算法仅考虑了消息C的第1次传送。

表1 Tindell算法的反例

图2 消息C的最坏响应时间为3.5 ms

　　另外，如将消息B和C的周期缩短为3.25 ms，按照Tindell算法，系统由于未求得最大的最坏响应时间，故仍是可调度的，但实际上总线的利用率已超过100%。Davis的方法核心是引入忙周期的概念，再对忙周期内各次传送的响应时间求最坏值，详见附录1。（见本刊网站www.mesnet.com.cn——编者注。）

　　Tindell的开创性工作对后续的研究与应用有巨大的影响，Volcano通信技术公司(现在的Mentor Graphics)以此理论为基础开发了商用的CAN调度分析软件。由于漏洞的发现，用户应检验软件是否有了新的补丁以及用它完成的应用是否受影响。

2 笔者对Davis算法的简化

　　Davis算法要先算出忙周期，再在忙周期中消息m多次传送中寻找最坏等待最大的那次。基于以下考虑，计算可以简化：

　　在忙周期中，消息m传送时有高优先级消息进入队列，使m的后续消息发送前可能插入更多的高优先级消息，代表仍有一个对总线需求的高峰，从而有可能使后面的消息m有更大的最坏响应时间。

　　最坏的情形是消息m刚发送，所有高优先级消息就进入队列，即领先于发完消息m后的第一个发送空隙的相位达到最大。

　　因此求消息m的最坏响应时间就有两种可能： 用Bm产生阻塞，像Tindell那样求消息m的最坏响应时间；由Cm产生阻塞，求下一个消息m的最坏响应时间，下一个消息m的排队时间为Tm-Jm。

　　简化方法的优点是减少了计算的次数，从而减少工作量。

　　这种算法与Davis算法中的保守算法有两点不同：一是用Cm来产生阻塞是真实可能发生的，例如从休眠到上电时消息m比高优先级消息早了一点；二是本算法得到的是确切的而非保守的结果。