CAN调度理论与实践分析
CAN总线中消息能否按时送达是事关系统安全等问题的重要指标，它要通过调度分析加以验证。本文介绍CAN调度理论的新研究成果，以及对工程应用的指导意义及其实施难点。具体分为4个部分：Tindell的分析方法和Davis的改进；笔者对Davis算法的简化；最坏响应时间分析在应用上的一些结果；调度分析在应用上的难处。
关键词 CAN 调度理论 响应时间 Davis算法 Tindell算法
分布式嵌入式系统是当前嵌入式系统的重要发展方向，因为它能提供更强的性能，节约系统的总体成本。但是由于各单个节点必须有通信网络相连才能协调地工作，网络就成了关键部分，没有网络提供及时正确的数据和命令，就谈不上所设计的系统服务了。在汽车的分布式嵌入式系统中，目前主流的通信网络是CAN总线。CAN是事件触发的通信协议，它根据消息的优先等级和节点的状态自动地调度消息的传送。低优先级的消息会因同时发生的高优先级消息太多而不能及时发送，高优先级消息也有可能由于节点状态等的影响而丢失。关于CAN的局限问题可见参考文献[1]。本文主要从调度理论方面讨论CAN系统的问题，这些问题与工程应用有非常大的关系，实践意义很强。
1 Tindell的分析方法和Davis的改进
1994年，Tindell [23]首先将分析单处理器任务调度方法改造成适用于CAN总线的调度方法，求取消息的最坏响应时间。对于与安全相关的应用，只有对最坏响应时间有确切的掌握，才是合理的。CAN通信在网络上的实现经过2个阶段：通信任务将消息发到发送的通信控制器(CC)，发送的通信控制器将消息发到接收的通信控制器。广义地讲，响应时间是从需产生通信的事件发生到消息到达目标节点的时间，包括发送节点host内的处理时间，host到CC的时间，总线上消息仲裁传送时间，接收CC到host的处理时间。仲裁获胜的消息开始传送后，便不能被中止，所以CAN调度是固定优先级非抢先式任务调度。消息m用到的参数定义如下:
Tm ——启动通信的事件间隔，即周期；
Jm——由事件发生到消息开始送CC的时间之最大变化，即抖动；
Cm—— 在总线上传送消息m所需时间（要考虑位填充形成的最大值）；
Dm——由应用决定的传送消息m允许的时限；
Rm——实际的最坏传送时间；
Wm——传送消息m时最坏等待时间。
它们之间的关系如图1所示。
图1 用于调度分析的时间参数
Wm由2部分构成：由低于优先级m的消息（其集合写为lp(m)）正在总线上传送而造成的阻塞Bm，和由高于优先级m的消息（其集合写为hp(m)）在总线上抢先传送而造成的干扰Im。它们取最大值时就使Wm成为最坏等待时间。
为了印刷的方便和易于理解，这里用了不同的写法，其中顶函数Ceiling返回的是最接近（大于等于）变量的上限整数, τ是1位时间。Ceiling( (Wm+Jk+τ)/Tk)表示在Wm时段内高优先级消息k会出现的最多次数。于是有：
Wm取离散值且出现在非线性方程(4)的两边，所幸的是其求解并不难。在式(5)中，用W0m=Bm作为初值循环求解即可。
式(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比高优先级消息早了一点；二是本算法得到的是确切的而非保守的结果。
计算方法：
第1次，用公式（5）～（7）计算Wm，得到Wm(0)；
第2次，用公式
对表1所列的例子，按本节方法有: 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,最坏响应时间为3.5 ms，与Davis的结果相同；而按Davis的保守算法，Wm=6。至于系统是否可调度，仍然要求每个消息都可调度。
3 最坏响应时间分析在应用上的一些结果
3.1 总线利用率低不能保证可调度性
有人凭经验认为，总线利用率＜30%时，性能便有了保证。其实不然，为了证明这一点，Davis等构造了一个例子，如表2所列。
表2 总线利用率低与可调度性无直接关系举例
图3 n=1时表2消息X的传送过程
当I和L的周期增加到任意大时，其占用的总线时间可以忽略不计。此时总线利用率为：
就本例而言，在Ch=Cx=55位（0字节数据）、Ci=135位（8字节数据）、Cl=0时，总线利用率与可调度性的关系如表3所列。
表3 总线利用率与可调度性的关系
例如在总线利用率为9.2%时，对10条消息也不能进行调度。本例中优先级消息的抖动较大，似有点异常。但对偶发的事件消息，其周期可取较长，如考虑限定相邻消息间的时间时，就相当于本例对T－J的设定，所以也非完全没有理由。
3.2 优先级设计策略的讨论
一般的说，消息优先级的设置采用时限或（时限－抖动）单调递变的策略，即时限越短的消息设置的优先级越高，但须用可调度性分析加以验证，并非这样做最好[4]。例如，表4优先级的设置为A-B-C，是不能调度的，如图4所示。此例用11位ID，125 kbps的传送速率。但将优先级改为A—C—B，按计算结果是可调度的，如图5所示。
表4 优先级设置的例子
3.3 硬件选用对可调度性的影响
Tindell [2]比较了两种通信控制器，认为像82C200一类的通信控制器只有一个发送缓冲器，从而会引起很大的滞后或抖动。例如一个节点有3个消息要传送，它们的优先级分别为H、 M、 L1，其他节点的消息优先级为L2、 L3、L4。对82C200来说，当要发送H而M已在发送缓冲器里时，就要中止M的发送，而将H写入，H发完后再将M写入，由于这些动作都需占用一定时间，而在这些时间里总线可能为其他节点的消息所占用。一次H的抢先，会造成M多次延迟而引起问题（详见附录2）。SJA1000与82C200是兼容的通信控制器，国内很多用户都用它。如果只用于发一种消息，则没有什么问题；如多个消息共用一个通信控制器，就必须考虑这个问题了。
4 调度分析在应用上的难处
上述分析方法是十分简化的，对出错重发情形已有的扩展处理方法，以错误的概率模型为基础，并未考虑节点的状态。处于bus-off状态的节点是无法调度的了。因而这种分析总是不完整的，还有待完善。
更为困难的是，如果系统不能通过可调度性，那么提供的补救措施极为有限。因为T、C均为实现应用功能所必需的，并可能是产品的现成的特性。此时可能要尝试修改优先级的分配，包括利用软件工具自动分配ID，但这与优先级（消息ID）的标准化又背道而驰。同一部件在不同系统应用中要装入不同的ID，容易混淆，对诊断与维修来说也比较困难。
图4 优先级为A—B—C时不可调度
图5 优先级为A—C—B时可调度
即使进行可调度性分析，必须有所有消息的T、C、J三个参数。其中T、C是供应商会提供的，但J不一定会或不一定能提供。由OEM指定T、C、J，然后由供应商去满足订货要求。虽然有时可行，但随着专业分工的细化，供应商对控制对象的研究更深刻，所以主动权不全在OEM手里。
为了在干扰严重的环境下可靠地工作，host一般会起用Watchdog功能来防止程序因走飞而失效。J与Watchdog的正常周期有关，也与Reset后的处理时间有关。如果程序抗干扰设计对数据没有足够的保护，则启动消息发送的本地时钟和某些与传送相关的状态标志会失控，使J也失控。一般的说，设计者现在还无法遍历所有的走飞状态从而提供有干扰下的J。如果通过测试确定，与软件有关的J测试集也是没保证的。不考虑走飞的J，对CAN调度分析结果可信度有所降低。
从上述分析可知，像CAN这种事件触发的通信协议，为保证消息不错过时限，必须进行可调度分析；分析后要使不可调度的系统变为可调度，在实践上比较困难。如果要解决host走飞形成的抖动造成通信失常的后果，只能在控制算法上花力气了，这在时间触发协议中也是一样的。