CAN调度理论与实践分析

2012-04-23 19:51:45来源: 互联网

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比高优先级消息早了一点;二是本算法得到的是确切的而非保守的结果。

关键字:CAN  调度理论  实践分析

编辑:神话 引用地址:http://www.eeworld.com.cn/mndz/2012/0423/article_15805.html
本网站转载的所有的文章、图片、音频视频文件等资料的版权归版权所有人所有,本站采用的非本站原创文章及图片等内容无法一一联系确认版权者。如果本网所选内容的文章作者及编辑认为其作品不宜公开自由传播,或不应无偿使用,请及时通过电子邮件或电话通知我们,以迅速采取适当措施,避免给双方造成不必要的经济损失。
论坛活动 E手掌握
微信扫一扫加关注
论坛活动 E手掌握
芯片资讯 锐利解读
微信扫一扫加关注
芯片资讯 锐利解读
推荐阅读
全部
CAN
调度理论
实践分析

小广播

独家专题更多

富士通铁电随机存储器FRAM主题展馆
富士通铁电随机存储器FRAM主题展馆
馆内包含了 纵览FRAM、独立FRAM存储器专区、FRAM内置LSI专区三大部分内容。 
走,跟Molex一起去看《中国电子消费品趋势》!
走,跟Molex一起去看《中国电子消费品趋势》!
 
带你走进LED王国——Microchip LED应用专题
带你走进LED王国——Microchip LED应用专题
 
电子工程世界版权所有 京ICP证060456号 京ICP备10001474号 电信业务审批[2006]字第258号函 京公海网安备110108001534 Copyright © 2005-2016 EEWORLD.com.cn, Inc. All rights reserved