避免饥饿的CAN 总线高优先级反转算法

赵国承，张凤登

（上海理工大学光电信息与计算机工程学院，上海 200093）

0 引言

控制器局域网络（Controller Area Network，CAN）总线是用于连接电子控制单元（Electronic Control Unit，ECU）的多主机广播串行总线标准，CAN 总线上每个节点都能够发送和接收报文，但不能同时发送和接收报文［1］。在CAN 总线中，任何具有高优先级的报文要在短时间内高频率占用总线，都有可能造成低优先级报文饥饿［2］。

解决CAN 总线中低优先级报文饥饿问题的研究较多。Murtaza 等［3］提出在CAN 总线上增加一个主节点，以防止其他低优先级节点出现阻塞问题。主节点必须尝试检测饥饿节点，并确保饥饿节点保持参与通信。主节点始终监视CAN 网络，并在收到来自所有节点的报文时保持沉默。如果主节点发现来自某些节点的报文没有参与通信，则该主节点将变为活动状态，这确保了来自这些节点的报文可以在下一轮仲裁中访问以进行广播。虽然该方案可以防止启动问题，但由于需要额外的节点支持，因此该方案需要更高的负担。文献［4］提出基于使用优先级和先入先出FIFO（First Input First Output）队列的CAN 总线报文调度方法，但其只关注了可行调度表的生成，却因此忽略了CAN总线中存在的饥饿问题。文献［5］开发了一种无饥饿模型，当存在任务发送失败的次数大于设置的阈值时，会使用优先级反转将该任务反转为最高优先级。文献［6］提出了一种新的无饥饿CAN 总线仲裁模型，其特点是利用报文标识符的最高两位动态反转实现优先级上升。Kimm 等［7］提出一种避免饥饿的CAN 总线调度方案，通过将每轮仲裁中发送失败的报文优先级反转为更高的优先级来避免饥饿问题。

以上研究注重将优先级低的任务在CAN 总线仲裁中动态变为高优先级任务，但这种方法存在弊端，当CAN 总线存在非常紧急的报文需要立刻发送时，很有可能得不到及时发送。本文更多地考虑将优先级高的任务在一定条件下进行优先级反转，动态降低其优先级，因此不会出现CAN 总线不能立刻发送非常紧急的报文问题，而且能有效避免CAN 总线固定优先级调度造成的饥饿问题。

1 CAN 总线帧格式和仲裁方式

自从德国Bosch 公司在汽车工程师协会（Society of Automotive Engineers，SAE）大会上引入串行总线系统以来，CAN 总线已经逐渐成为最成功的数据通信协议之一［8］。CAN 总线采用载波监听多路访问/冲突避免（Carrier Sense Multiple Access with Collision Avoid，CSMA/CA）协 议［9-10］，所以CAN 总线的访问是无冲突、按位仲裁的［11］。无冲突意味着总是更高优先级的报文在仲裁中获胜并发送，且在发送过程中禁止其它报文发送。按位仲裁可以理解为，如果有两个或多个节点同时进行传输，且有显性位和隐形位同时发送，这时规定显性位的权重大于隐形位，故显性位可以覆盖隐形位。

在CAN 总线中有数据帧、远程帧、错误帧和过载帧4 种不同的帧［12］，其中数据帧能够将数据从发生端广播至接收端，数据帧格式如图1 所示，携带有标识符的远程帧用来请求另一节点发送具有相同标识符的数据帧；错误帧发送总线中出现错误的指示；当数据帧与相邻的一个数据帧或远程帧之间出现额外延迟时，过载帧将被发送。在CAN 总线空闲时，CAN 总线上任何一个节点都能在CAN 总线上发送报文，无需获得总线上其他节点许可［13］。

Fig.1 Data frame format图1 数据帧格式

数据帧分为标准格式和扩展格式两种。其中标准格式的标识符长度为11 位，扩展格式标识符有29 位［14］。本文对标准格式进行论述，对数据帧中仲裁场的标识符进行分析。

当CAN 总线上有多个节点同时发送时，通过对总线进行监控，可以确定每个节点当前正在传输的报文优先级高低。若在仲裁中某一节点胜出，那么该节点继续传输其报文的剩余部分，此时仲裁失败的节点均退出并继续等待下一次仲裁开始［15-17］。同时，因为CAN 总线没有全局时钟，所以节点需要在每次报文传输时重新同步，并且每个节点必须与首先开始传输的节点同步，以便总线仲裁能够正常工作［18-19］。

2 反转算法设计

2.1 算法思路

本算法中11 位报文标识符设计为1 位动态反转标识位、1 位级别位和9 位静态位3 部分，如图2 报文标识符ID划分所示。当然这仅仅是在标准格式中的划分，除此之外还可根据需要应用在扩展格式中。静态标识位（ID0-ID8）从优先级最低的111111111 开始，以最高优先级的0 位000000000 结束。级别标识位ID9用来区分高优先级组和低优先级组，其中高优先级组的级别标识位为0，低优先级组的级别标识位为1，动态反转标识位ID10默认为0 未反转，当高优先级组存在报文满足反转条件时会动态反转为1。

Fig.2 Message identifier ID partition图2 报文标识符ID 划分

CAN 总线上发送的报文由节点生成，为不同的报文分配优先级时，这些报文的优先级将伴随着报文同样保存在节点中。由于报文发送基于固定优先级的CAN 总线调度，因此，当CAN 总线上的节点发送报文时，该报文所获得的优先级会一直固定不变，而且每一个报文的优先级都是独一无二的，不能出现重复的优先级，否则很有可能造成死锁。

本文选择非抢占式的单调速率（Rate Monotonic，RM）算法进行报文优先级分配。选择非抢占式的RM 算法调度原因如下：①如图3 所示，非抢占式调度方法可以确保一旦发送某一报文就能够一直发送直到发送完毕，在此期间不能被其它高优先级报文打断，发送过程中上下文切换开销忽略不计；②RM 算法是根据报文的周期来分配优先级，其特点是报文发送的周期越短优先级越高［20］，反之报文的发送周期越长优先级越低，要求在报文开始发送之前便分配完毕且运行过程中始终固定。

Fig.3 Non-preemptive scheduling图3 非抢占式调度

算法实现如下：在CAN 总线中，当高优先级组在一定时间内出现某一报文发送的次数大于设置的固定值时，则在下一次继续参与CAN 总线仲裁之前将其动态反转到标识位ID10，进行反转由0 变为1，从而使其比低优先级组里的报文优先级还低，此时处于饥饿中的报文得到机会发送，实现避免饥饿目的；当其动态反转标识位变为1 时，并不意味其丧失继续参与本次CAN 总线仲裁的资格，而是进一步判断当前CAN 总线是否处于空闲状态。如果总线空闲，则该反转后的报文正常发送，否则不会发送，这样可以避免当总线拥挤时，反转后发送的高优先级报文经过多次仲裁都不能占用总线的问题，避免报文发送的顺序错乱；最后，不管本次是否发送成功，都会在下一次参与CAN 总线仲裁之前将其动态反转标识位变为0，重新恢复其高优先级。有了1 位动态反转标识位，任何具有高优先级的报文在短时间内高频率占用总线一定次数后都会被中断。本文使用的11 位ID 动态反转标识位开始均为0，级别标识位可在0与1之间进行划分，静态标识位内数字可任意选取。

2.2 任务模型

模型如图4 所示。在本模型中，设被调度的报文组为｛M1，M2，…，Mn｝，Mi是其中的一个报文，i=1，2，…n。避免饥饿的高优先级反转模型主要由2 个参数Ttc和TMax决定，其中Ttc代表检测报文发送次数的时间，TMax代表在Ttc时间内发送报文的次数。同时进行如下定义：

Fig.4 High priority inversion model to avoid starvation图4 避免饥饿的高优先级反转模型

定义1报文Mi的传输周期等于其截止时间

其中，Pi为报文Mi传输周期，Di为报文Mi截止时间。

定义2CAN 总线利用率U定义为：

其中，K为报文Mi执行时间，P为报文Mi传输周期，i=1，2，…n。

定义3报文Mi的响应时间T定义为：

其中，t1为报文Mi的激活时间，t2为报文Mi的发送完成时间。

其中，n为报文数量，i=1，2，…n。

定义4到达率S定义为：

其中，R指单位时间内实际发送报文的数量，C为预计发送报文的数量。

本算法实现检测报文发送次数并防止遗漏、到达规定次数以后进行反转，以及未反转报文的发送功能。算法部分代码如下：

3 实验仿真

本文使用Vector CANoe 平台实现避免饥饿的高优先级反转算法。CANoe 是一种软件开发和测试工具，主要用于通信网络和ECU的开发、分析、仿真、测试、诊断和启动，编程语言CAPL 用于编写测试脚本和仿真模型［21］。实验开始所有报文均在0 时刻释放，本文设置两组周期报文队列，分别为高优先级组和低优先级组，两组报文的截止日期均等于报文的发送周期，实验将每组设置为2 个报文。

其中高优先级组的两个报文为M1和M2，低优先级组的两个报文为M3和M4，高优先级组得到报文优先级远远大于低优先级组。为了进一步验证避免饥饿的高优先级反转模型与正常固定优先级的优势，实验分别进行CAN 总线正常工作、CAN 总线满利用率工作、CAN 总线产生饥饿以及将报文数量扩大仿真。

3.1 CAN 总线正常工作

设报文M1的发送周期为2ms，优先级设置为0x01，报文M2的发送周期为4ms，优先级设置为0x02，报文M3的发送周期为8ms，优先级设置为0x201，报文M4的发送周期为12ms，优先级设置为0x202。规定两组报文的执行时间K均设置为1ms，检测时间Ttc设置为8ms，检测报文发送次数TMax设置为3。如图5 所示，通过对比未进行反转的固定优先级调度和有反转的非抢占式RM 算法调度在CAN 总线的发送队列可知，未进行反转的固定优先级调度和有反转的非抢占式RM 算法调度虽然均能将报文正常发送，但是使用了反转的非抢占式RM 算法调度能够较好地降低低优先级组报文的响应时间T，例如报文M4。其中反转报文----M1是报文M1的反转，根据避免饥饿的高优先级反转模型可知，其优先级反转为0×401，远远小于低优先级组的两个报文的优先级，因此反转后报文M4可以在反转报文----M1的前面执行。此时CAN 总线上的报文均得到机会发送，故低优先级组的到达率S 始终为1。

3.2 CAN 总线满利用率工作

除了将报文M3的发送周期设置为6ms 以外，其它所有实验参数均与CAN 总线正常工作时一样。通过观察图6 可知，未进行反转的固定优先级调度恰好能够将所有报文在其周期内发送，而此时有反转的非抢占式RM 算法调度则很明显地降低了低优先级组报文的响应时间T，此时CAN总线上的报文恰好均能发送，故低优先级组的到达率S 始终为1。

3.3 CAN 总线产生饥饿

将高优先级组报文M2的发送周期改为3ms，低优先级组报文M3的发送周期为改6ms，其它所有实验参数均与CAN 总线正常工作时一样。如图7 所示，未进行反转的固定优先级调度在实验中产生饥饿，导致低优先级组报文M4一直没有占用总线的机会，一直处于饥饿当中，故低优先级组报文的到达率S 小于1。而此时有反转的非抢占式RM算法调度能够避免CAN 总线中低优先级报文产生饥饿问题，使得两组报文在其周期内均能得到占用总线的机会。此时低优先级组报文的响应时间T 得到明显降低，低优先级组的到达率S 仍保持为1。

Fig.5 Reverse transmission queue situation when CAN bus works normally图5 CAN 总线正常工作时有无反转发送队列情况

Fig.6 Reverse transmission queue situation when CAN bus works at full utilization图6 CAN 总线满利用率工作时有无反转发送队列情况

Fig.7 Reverse transmission queue situation when CAN is in starvation图7 CAN 产生饥饿时有无反转发送队列情况

3.4 扩大仿真

为进一步验证避免饥饿的高优先级反转模型与正常固定优先级的优势，将实验中的报文数量扩大，设置报文数量n 为20，每组报文数量设置为10，仿真时间为1s，对比低优先级组在未进行反转的固定优先级调度和有反转的非抢占式RM 算法调度下的到达率和平均响应时间。

平均响应时间如图8 所示，分别验证在不同CAN 总线利用率下有反转的非抢占式RM 算法调度和无反转的CAN总线固定优先级调度对低优先级组平均响应时间的影响。当CAN 总线利用率逐渐增加时，不管低优先级组处于未进行反转的固定优先级调度，还是有反转的非抢占式RM 算法调度，其平均响应时间都在不断增加，但是有反转的非抢占式RM 算法调度的平均响应时间总是小于未反转的CAN 总线正常调度的平均响应时间。

到达率实验如图9 所示，对CAN 总线由正常到产生饥饿、有反转的非抢占式RM 算法调度和无反转的CAN 总线固定优先级调度对低优先级组到达率的影响进行分析。若CAN 总线利用率小于等于100 时，有无反转对低优先级组的到达率无显著影响；当CAN 总线利用率大于100 时，CAN 总线存在处于饥饿状态报文。当CAN 总线利用率逐渐增加时，无反转的CAN 总线固定优先级调度下的低优先级组到达率持续减少，直到为0，此时低优先级组中没有一个报文能够再占用CAN 总线。与之相反，在有反转的非抢占式RM 算法调度下的低优先级组到达率则基本维持不变。

Fig.8 Average response time of low priority group with or without inversion图8 低优先级组有无反转的平均响应时间

Fig.9 Arrival rate of low priority group with or without inversion图9 低优先级组有无反转的到达率情况

4 结语

针对CAN 总线存在的饥饿问题，本文提出一个避免饥饿的高优先级反转算法并建立模型。在满足优先级反转条件下使高优先级反转为低优先级。仿真实验结果表明，在不同的CAN 总线利用率下，该模型能够通过改善CAN 总线中周期任务的平均响应时间来减少饥饿。当CAN 总线利用率超过100 时，有反转的低优先级组到达率能够保持正常，表明避免饥饿的高优先级反转算法工作良好。

避免饥饿的高优先级反转算法虽然有效，但高优先级组在一定时间内的发送次数是固定值，大于该固定值后才能进行动态反转，在此期间没有考虑低优先级组的饥饿程度。后续可围绕该固定值与低优先级组饥饿程度的关系进行研究。