CAN总线调度算法研究

蔡一杰，杜 峰 ，胡乐媛，冯兵伟，吴 迪，史星彦

（1.天津职业技术师范大学机械工程学院，天津300222；2.天津职业技术师范大学汽车与交通学院，天津300222）

0 引言

CAN总线是当今世界中最为广泛使用的现场总线之一，每时每刻都有无数消息通过CAN总线进行传输，在CAN总线中传输的消息主要按其截止时间来分类，具体包括必须严格按照截止期进行传输的硬实时消息、在截止期附近可适当弹性传输的软实时消息以及没有严格时间要求的非实时消息[1]。硬实时消息一般为实时系统中的各种紧急消息（如错误信息、警告信息），对传输时间的要求极高；软实时消息一般是在系统内循环发送的消息，对传输时间的要求不太敏感，但不可长期大量超时，否则会引起系统报警，升级为硬实时消息；非实时消息一般为系统内部的检测信息、组态信息等，非实时消息的数据量较大，若即时发送会严重堵塞传输网络，因此对时间的要求较为宽松。CAN总线调度是指在系统的控制下，将需要传输的消息按照一定的次序及时间间隔有序的进行发送分配。在实时系统中，网络带宽资源是有限的，那么如何妥善使用有限的带宽资源，获得最大的使用效益，完成系统内部消息的有序传输成为了调度的主要目标[2]，以及接近截止期的消息如何按时发送、如何有序的安排周期性消息在无数非周期性消息中发送、如何保证实时性消息与非实时消息在发送时的公平性等[3]，也是目前CAN总线调度尚需解决的问题。

1 实时性

CAN总线本身采用的是非破坏性逐步仲裁技术，依靠标识符等确定优先级，当出现传输消息冲突时，可以有效地根据优先级解决问题。因此CAN总线本身就是基于优先级调度的协议进行的，若需最高的实时性，只需采用基于优先级的调度算法即可[4]。基于优先级调度的算法从分配方式上可分为静态调度和动态调度。

1.1 静态调度算法

静态调度是采用离线预先分配的方式，在未开始工作时，依据各消息的属性特点将网络资源划分出分配表，在接下来的工作过程中优先级不会发生改变，除非需要重新进行分配。所以静态调度的工作量很小，可以最大程度地保证实时性。但是相对地，静态调度在封闭系统中工作性能极佳，那么灵活性较差就成为了它的缺点，在变化的环境下或者是不可测算的工作环境下无法保证系统的工作性能甚至正常运作。静态调度的优缺点非常明显，它适合在封闭系统、确定性系统或时间特性不会变化的系统中进行工作。但是一旦网络中出现了时间特性会变化的节点或在无法预测的工作环境，静态调度的性能会变得很差甚至不得不全部重新分配。

1.1.1 速率单调算法

速率单调算法（RM算法）是一种典型的静态调度算法，它主要面对周期性的任务，在离线时预先划分出分配表，根据每个任务的周期制定好优先级[5]。由于周期任务具有较短的截止期，如无法在下一个周期到来之前将本周期的消息传输完，就会导致消息传输的冲突，遗漏或整体的堵塞，所以周期越短的任务优先级应越高，即通常情况下应当给予短周期的任务最高的优先级。在使用RM调度算法时，对不同任务的处理方法不同，对网络资源的利用率也不同[6]，因此可以完成的截止期长短也会有所不同，当截止期小于任务周期的时候就会出现不可调度的情况，所以采用RM算法的具体要求就在于能否调度。

判断RM算法能否调度的关键原理在于处理器的利用率。在RM算法模型中，针对周期性任务集，利用率U（c）被定义为：

其中：n为周期性任务的数量；Ci为任务i的执行时间；Ti为任务i的周期。

当n→∞时，

由式（2）可知，当无穷多个任务同时抢占时，处理器利用率极限为69%，即只要利用率小于69%，RM算法就可调度任何周期性任务。

1.1.2 截止期单调算法

截止期单调算法（DM算法）也是一种静态调度算法，主要面对对象同样是周期任务，它是在RM算法的基础上研究出来的。DM算法工作的方式更为直接，它的理念是截止期优先，必须优先处理截止期较短的任务，它通过检测任务的截止期来进行预先分配，给予截止期最短的任务最高的优先级。若将DM算法中的任务看作由周期、执行时间、截止期组成的三元组S=（T，C，D）。此时任务集S=（S1，S2，…，Sn），截止期为D1，D2，…，Dn，且满足D1≤D2≤…≤Dn，则此时任务的优先级P为P1≥P2≥…≥Pn。这样能最大程度上保证任务的可调度性，提高系统的实时性[7]。1.1.3 TT-CAN算法

在保证系统的实时性方面，TT-CAN也具备很大优势。它基于时间触发，能够最大程度的保证低优先级消息的实时性[8]。如图1所示为基于时间触发传送原理图。

图1 时间触发传送原理图

TT-CAN与RM等算法不同，它是在标准CAN协议基础之上的一种高层协议，不会对CAN协议造成变动，是一种基于表的、基于时间触发的静态调度协议。TT-CAN每隔固定的时间会向整个系统发送基准消息，各个节点会将该基准消息作为基准的“表”，从而达到确立基准时钟的目的。由于TT-CAN通过确立时钟来使各节点自行管理，所以在协议中没有设置主管理节点。各个节点自身拥有已分配好的调度表，包含发送时间、接受时间、任务传输周期等信息，系统可以根据这些信息推算出可能存在的延迟时间。如图2所示为TT-CAN工作的基本周期图。

图2 TTCAN协议工作周期

TT-CAN最适合传输的消息为周期性消息，同时对于某些非周期性消息，可以依靠基于表的特性将其转换为周期性的传输模式[9]。TT-CAN算法拥有着一定的可预测性但具有静态调度算法的通病，一旦消息本身的时间特性出现某些改动，那么整个分配表都需要重新调整。

RM、DM、TT-CAN等算法均为基于固定优先级的静态调度算法，他们的高实时性都是建立在面对周期性任务的基础上的，面对复杂多变的开放工作环境时，可能会占用大量的网络资源，导致消息传输的延时甚至丢帧，而且对网络资源的低利用率也是一种浪费。针对这种情况，研究人员开始尝试将动态优先级的调度算法应用于CAN总线中。

1.2 动态调度算法

在实时系统工作时，可以动态地改变各个节点消息的发送次序，根据需要实时调整系统中任务优先级的调度方法被称为动态调度算法[10]。在动态调度过程中，系统根据实时地需求调整消息的优先级，这样可以充分的利用网络资源，较好的适应环境的变化，在复杂多变的开放工作环境中也可以稳定的进行消息传输，保证了实时系统的鲁棒性。当然实时计算消息的优先级势必会占用一部分系统资源，在一定程度上影响了传输的效率，因此该类算法通常来说在网络负载较轻的工况下会拥有较好的调度效果。

1.2.1 EDF算法

最早在CAN总线中被应用的是EDF动态优先级调度算法，即最早截止期优先算法。EDF算法可以被称为最经典的动态调度算法，在实际工作中，它会根据每个任务的相对截止期实时地进行计算并分配优先级，给予相对截止期最短的任务以最高的优先级。

对于EDF算法来说，针对周期性任务集，可被调度的充分必要条件为：

式（3）中，U（n）为处理器利用率。即当处理器利用率小于100%时，EDF算法可调度任何任务集。由式（1）、（2）可知，RM算法只能在利用率小于69%的情况下进行工作，这也进一步证明了动态调度算法的优越性。

由于该算法需要每时每刻都进行任务相对截止期的计算以进行优先级的分配，尤其是当有多个任务的截止期相对接近时，每隔较短的时间都会出现优先级更替的情况，所以会占用较多的网络资源，在网络负载较大时，系统的控制性能势必会发生断崖式下跌，这也是动态调度算法的通病。

1.2.2 MTS算法

固定优先级调度面对周期性消息时拥有的高实时性的优点与复杂环境下低效率的缺点，动态优先级调度有稳定、效率高的优点，而负载过大时传输效率低下的缺点，为了更好地扬长避短，充分利用二者的特点，研究人员不断地尝试混合调度算法的可能性。Zuberi等人[11]研究出了 MTS（Mixed Traffic Scheduler）分级调度机制，并在CAN总线中予以实践，其基于动态调度算法EDF的灵活性来对实时性数据进行调度，以保持消息传输的实时性；基于静态调度算法DM的截止期单调性对非实时性数据进行调度，以保证这些数据的传输均在截止期之前完成。如图3所示是一种MTS算法的控制策略。

图3 MTS算法控制策略

采用这种方式，可以有效地防止EDF算法工作时的高开销，同时面对复杂环境时也可以避免DM算法可能造成的冲突等问题。吕伟杰等[12]同样希望同时利用二者的优点，提出利用EDF调度硬实时消息，利用RM调度软实时和非实时消息，实验表明，可以有效提高网络利用率，减少消息传输的延时。

2 基于公平性

2.1 PE与DS算法

FTT-CAN、EDF等算法的优越性在于极高的实时性，可以极大程度上减少消息的抖动，但由于对周期性消息过于重视，难免会对非周期消息的公平性造成影响。为了解决此问题，Lehoczky等人[13]提出了DS（deferrable server，可延期服务器）算法和 PE（priority exchange，优先权交换）算法，这两个算法的核心思想比较相似，都是设置一个专用的优先级较高的周期性任务，这一任务专门用来供非周期性任务使用，若执行到设置的这一周期性任务时刚好不存在排队等待的非周期性任务，系统就会按照设定好的方法为非周期性任务保留一定的带宽资源，随时应对可能存在的待处理任务[14]。系统所需要操作的这些设定好的方法就是PE算法与DS算法的区别。

2.2 SS类算法

经过深入研究，Sprunt[15]在这两种算法的基础上提出了SS（sporadic server不定时服务器）方法，这是一种更完善的服务方式。SS可以称作PE算法和DS算法的升级版，主要体现在两点上：PE算法的缺陷在于，需要维护每一个优先级的工作时长，这样就造成了大量的工作负载；DS算法的缺陷在于，其工作时长的补充与实际工作时长无关，因此难免出现额外的时长补充，这样会造成处理器利用率的浪费，且造成网络资源的浪费与信息传输的延时[16]。

SS算法补偿非周期性消息的工作时长的方法的流程图如图4所示：将实时工作的任务的优先级设为Ps，将系统中的各个优先级设为Pi（i=1，2，…），且Pi＞Pj，当且仅当i＞j；将是否补充工作时长的状态定义为ON与OFF，将PS与Pi的优先级层次进行比较，若PS≥Pi，则Pi的状态为ON，否则为OFF。在服务器中，若存在空余的工作时长，则将在优先级Pi的状态为ON时开始计算补充的工作时长并添加；若不存在空余的工作时长，则需等待至服务器有空余时长时，且Pi的状态为ON时，才可以开始计算补充时长[17]。

图4 SS算法流程图

上述方法都是在RM算法等固定优先级算法的基础上研究的，都可以被归为固定优先级服务器算法。固定优先级算法对网络资源利用率较低这一缺陷比较明显，为了解决这一问题，Ghazalie与Baker[18]开始研究在EDF算法基础上的更好地针对公平性的方法，并提出了SS算法的动态调度版本，并将其命名为（deadline sporadic server，截止期不定时服务器，DSS算法）。这一算法的核心思想与SS算法相同，不同之处在于DSS算法可以通过计算截止期及时为服务器调整优先级，但显而易见，及时更新优先级需要系统保持极高的计算量，实现较为复杂且易造成较大负载。

2.3 TBS类算法

可以看出，不论是DS、PE算法还是SS类算法，若服务器本身的周期就较久，则非周期性任务被延迟的可能还是很大。除了为非周期性消息分配较短的周期外，有学者提出了TBS算法，这种算法的核心思想是缩短非周期性消息的截止期，并为其限定一个较合适的处理器利用率，规定截止期的分配不会使处理器利用率超标[19]。由于系统始终保持在合理的负载，因此开销极小甚至可忽略。除此之外，Lipari等利用TBS+EDF混合调度算法来完成混合任务的工作；Caccamo等提出了可调的TB*算法，进一步提高了算法的性能与稳定性。

3 算法性能分析

由表1可知，RM算法的优点是在截止期与任务的周期相同时可以获得最高的实时性与工作效率。但它可能会造成无法调度的情况，影响了适用情况与控制性能。DM算法具有比RM算法更优越的工作条件，不论任务周期与相对截止期关系如何，都可以达到最优的调度效果，在同类的静态调度算法中，DM算法的优势明显。值得一提的是，DM与RM算法虽简单且易实现，但由于只依靠一种因素分配优先级，所以无法综合比较整个控制系统的性能。TTCAN最适合传输的消息为周期性消息，同时对于某些非周期性消息，可以依靠基于表的特性将其转换为周期性的传输模式。但缺点是难以适应复杂环境。EDF算法在处理器利用率小于100%时可调度任何任务，但负载过大时性能会出现暴跌。MTS算法可以有效地防止EDF算法工作时的高开销，同时面对复杂环境时也可以避免DM算法可能造成的冲突等问题，是未来研究发展的趋势。基于服务器的算法可以更好地保证非周期性消息的公平性，主要以DS与PE算法为基础，但他们都存在很明显的缺陷，SS算法及建立在动态调度基础上的DSS算法是一种更完善的服务方式。相对于SS算法，DSS算法的优势在于可以及时的更新优先级，但难免造成负载过大的问题。TBS算法可以在保持处理器利用率不超标的前提下为非周期性任务争取最多的工作时长，也可以与EDF算法等进行混合使用，进一步提高算法的性能与稳定性，相较于SS类算法来说优势较大。

表1 各算法性能分析

就基于CAN总线的调度算法而言，本文主要对同类的算法或改进后与改进前的算法进行了性能对比分析，且由于存在RM、DM算法等只依靠单一变量分配优先级的算法，因此难以对这些算法的综合性能进行比较，进一步的研究目标应对不同类别算法进行性能比较。算法的好坏不能仅依靠某一种情况下的性能，还受到实时负载、工作中的抖动、定期任务的截止期与周期的关系等因素的影响，如何减少这些因素造成的影响，得到较为客观的结果，也应是新的研究内容。

4 总结与讨论

本文综述了在基于不同目的时可采用的调度算法及其性能特点，分析了不同算法的优缺点及适用情况，为复杂工况下的实时系统设计者提供了选择的思路。CAN总线作为世界上应用最为广泛的总线之一，应用情况数不胜数，除实时性及公平性要求之外，设计者还可能存在调度性能要求、网络资源利用率要求等等。对于如何利用CAN总线调度算法完善的解决各种实际问题，兼顾各方面要求，还有待进一步研究。