CAN网络周期任务与偶发任务混合调度的研究*

张建军，王跃飞，张本宏，张 利，李县军

(1.合肥工业大学计算机与信息学院，合肥 230009;2.合肥工业大学机械与汽车工程学院，合肥 230009;3.教育部安全关键工业测控技术工程研究中心，合肥 230009)

前言

CAN总线是一种具有高抗干扰性和非破坏性仲裁等特点的串行通信协议，在汽车电子领域得到广泛应用。整车CAN网络中，所传输的消息类型有周期性、偶发性和非周期性消息，有硬实时、软实时和非实时消息。因此对于CAN网络消息传输，须采用合适的调度算法来满足各类消息传输的需求，进而避免各种消息相互间的不良影响。从本质上看，这种网络消息调度与操作系统中任务调度类似，可将其看成实时任务调度。整车CAN系统是典型的混合任务系统，其调度目标是在保证硬实时周期任务时限的基础上，缩短偶发任务和非周期任务的响应时间。

为实现该调度目标，时间挪用法［1］是一个较好的方法。其基本思想是在确保硬实时周期任务时限的同时，最大限度地使用周期任务集“挪出”的时间。周期任务集可挪用的时间由不同调度算法决定，一般情况下，动态优先级算法能够获得很好的响应时间。最早截止期优先(earliest deadline first，EDF)调度是典型的基于优先级驱动动态调度方法，将其与 CAN 协议结合［2－4］，可实现 CAN 网络的EDF调度。但是该调度算法在一些特定的情况中，无法对偶发任务的信息传输进行有效调度。本文中应用了文献［5］和文献［6］中关于EDF调度算法、逆调度和空闲时间的研究结果，提出了基于最大可挪用时间的不可抢占EDF调度算法。

1 周期任务和偶发任务混合调度

1.1 系统模型

将实时任务分为硬实时周期任务和非周期偶发任务。其中硬实时周期任务集为Π={T1，…，Tn}，Ti=(Si，Ci，Di，Pi)(1≤i≤n)代表周期任务，其中任务首次到来时间为Si，任务的最大执行时间为Ci，任务的最后期限为Di，任务的周期为Pi。周期任务Ti第 j次到来记为 τij=(sij，cij，dij，pij)，其中 sij=Si+(j－1)× Pi，cij=Ci，dij=Di，pij=Pi。偶发任务集记为 Γ，Γ ={J1，…，Jn}，Ji(1≤i≤n)代表偶发任务，Ji=(Si，Ci，Di)，其中任务的到来时间为 Si，任务的最大执行时间为Ci，任务的最后期限为 Di［6］。

设UΠ=∑(Ci/Pi)≤1为周期任务集CPU的使用率，周期任务集的超周期H为各任务周期的最小公倍数。同时为方便研究，本文中只研究一个超周期中任务集的执行情况针，并对CAN总线特点做如下假设:(1)任务运行时不可被抢占;(2)高优先级偶发任务优先被调度;(3)对于周期任务Di=Pi，Si=0;(4)忽略进程调度与任务切换时间;(5)最大可挪用时间＞最坏执行时间;(6)忽略进程调度与任务切换时间。

1.2 基本概念

为方便描述混合调度方法，引入文献［1，6］中的相关术语，定义了如下概念。

定义1 任务执行区间:设任务Ti获得CPU开始执行时刻为si，Ti执行完让出CPU时刻为ei，则区间［si，ei)为 Ti的任务执行区间。

定义2 调度 ＆:设 ＆={＆1，…，＆n}为超周期H内周期性任务执行过程。记任务Ti的执行过程为 ＆i={＆i1，…，＆ik}，＆ij={［s1，e1)，…，［sp，ep)}，1≤i≤n，k=H/Pi，且 sq＜eq＜sq+1(1≤q≤p)。

定义3 调度执行区间:如果周期任务集的任务在时刻 S获得 CPU，在时刻 E让出 CPU，且在［S，E)时间段中从未让出过CPU，则称Π的调度执行区间为［S，E)。

定义4 ＆(t):＆(t)是在时刻t以前调度＆已经完成的任务执行区间的集合。

定义5 逆调度＆－1:＆－1是相对于＆的过程，即={［H －ep，H －sp)，…，［H －e1，H －s1)}(1≤j≤k)，如果 ＆i(k－j+1)={［s1，e1)，…，［sp，ep)}，＆i(k－j+1)属于＆，则称＆i(k－j+1)为对应的任务执行区间集。

定义6 ＆－1(t):＆－1中在时刻t以前已经完成的任务执行区间记为＆－1(t)。

假设τij是在＆(t)中未执行而＆－1(t)中已执行的任务是＆－1－＆(t)中 t+ε时刻后当前任务第一个执行区间。

其中，1≤i≤n，j=H/Pi，T 是系统在 t+ ε 时刻后的空闲时间，w是后移执行区间的截止期。

(2)＆－1(t)－＆(t)≤0

v是＆－1－＆(t)中t+ε时刻后当前任务第一执行区间截止时刻。T'是＆－1－＆(t)中t+ε时刻后，第一执行区间后的空闲时间。

定义7 ＆－1－＆(t):＆－1－＆(t)是逆调度 ＆－1减去＆(t)后剩余的任务执行区间。设n是周期任务数，＆－1－＆(t)={［sq+1，eq+1)，…，［sj，ej)}。当len(＆i(t))={(e1－s1)+… +(eq－sq)}时，＆－1－＆(t)={(＆1－1－＆1(t))+… +(＆n－1－ ＆n(t))}。

2 不可抢占EDF混合调度

2.1 基本思想

针对CAN网络硬实时周期任务与非周期偶发任务混合调度无法保证非周期偶发任务实时性的问题，在EDF调度与逆调度起止时刻表(见表1)的基础上，提出基于最大可挪用时间的不可抢占EDF调度算法。即在网络运行时，网络中调度节点根据其他节点提供的信息建立或者更新自身的EDF调度与逆调度起止时刻表，当偶发任务发生时，根据此表计算调度与逆调度可挪用时间，实现偶发任务的及时响应。

表1 EDF调度与逆调度起止时刻表

表1中:MS_NM为消息名称，SC_S_TIME为EDF调度消息报文传输起始时刻，SC_E_TIME为EDF调度消息报文传输终止时刻，NSC_S_TIME为与调度相对应的消息报文逆调度起始时刻，NSC_E_TIME为与调度相对应的消息报文逆调度终止时刻。

2.2 最大可挪用时间计算

定理:S是＆－1－＆(t)中第一个调度执行区间的开始时刻，则周期任务在时刻t+ε的最大可挪用时间 TKN=S －(t+ε)［1］。

证明:因为不能后移＆－1(t)的所有调度执行区间，故不能后移＆－1(t)－＆(t)中的任何调度执行区间，＆－1－＆(t)中第一个调度执行区间的开始时刻是S，即S的值在时刻t+ε后是不能再增大的，故任务在时刻t+ε的最大可挪用时间TKN=S－(t+ε)，证毕。

根据定理的结论，可以设计求解最大可挪用时间相应的算法。用向量 α ={s1，s2，…，si，si+1，…，sN}表示一个超周期中所有任务到来的时间，设si＜si+1，s1=0，sN=H。在一个超周期中，周期任务到来次数之和为N。每个si对应的＆－1(si)由定义7计算得到。t+ε前周期任务的完成量len(＆－1(t))和len(＆(t))组成向量 β ={len(＆－1(t))，len(＆(t))}。得到α和β之后，根据下面的公式，可以计算任意时刻t与＆－1－＆(t)对应的S:

其中t+ε =(j－1)Pi+cij，j是第 i个任务的第j次执行，cij=Ci，TKN=S － ((j－1)Pi+cij)。

2.3 不可抢占EDF混合调度算法

本算法的思路是让周期任务集先运行一个超周期的时间，得出＆、＆－1、α和β的值，在运行过程中计算＆－1(t)的值，调度算法的流程见图1，具体步骤如下。

Step1:在第1个超周期中，使用EDF调度运行各周期消息，各节点记录消息报文发送时刻α。当接收节点正确接收消息报文时，会在应答间隙期间向发送节点发出ACK应答信号，发送节点记录此时刻，获得消息报文的执行时间。若偶发消息到来，让其在后台运行，使偶发消息在空闲时间执行。

Step2:记录EDF调度(＆)起止时刻，同时计算逆调度＆－1的执行起止时刻。

Step3:通过周期性消息报文的发送，调度节点获得一张各节点消息调度与逆调度起止时刻表，记录了各周期性消息报文EDF调度与逆调度执行的起止时间。

Step4:若t时刻偶发消息到来，调度节点根据EDF调度与逆调度起止时刻表计算β，由此可以得到＆－1－＆(t)对应的任务执行起始时刻S。

Step5:计算 S－(t+ε)，若 S－(t+ε)＞0，则挪用S－(t+ε)长度的时间段，若 S－(t+ε)≤0，则等到对应的调度执行区间结束后转Step4，重新计算S－(t+ε)的值。

Step6:挪用S－(t+ε)时间段后，继续使用EDF调度，记录周期任务的起止时刻到EDF调度与逆调度的起止时刻表中。

Step7:新的超周期到来，转Step3。

3 仿真实验

在Vector CANoe平台中建立仿真系统，该系统由7个汽车控制节点和1个调度节点组成，如图2所示。其中，调度节点负责＆、＆－1和＆－1－＆(t)的运算。设周期任务选取满足假设(6)，周期性任务的参数如表2所示，经计算可知负载率(即CPU使用率)分别为24%、49%和98%。

偶发任务随机产生，为了方便计算，根据周期任务集，取偶发任务为 J1=(3，1，12)、J2=(7，1，12)、J3=(10，1，12)3种情况进行分析，图3～图5分别是负载等于98%、49%和24%情况下的比较结果，可以看出:在后台运行法、带宽保留法和本文的时间挪用法等3种方法下，随着系统负载的增加，偶发任务的响应时间随着增加，本文的时间挪用法在网络负载较低时，获得了很好的响应时间，在网络负载高时也获得了较为理想的响应时间。结果表明本文中所提出的方法可在不影响周期任务集调度的情况下满足偶发任务的实时调度。

表2 周期任务集

4 结论

针对CAN网络中应用的EDF算法，引入了调度与逆调度等相关概念。运用这些概念，以硬周期任务时限为约束条件，提出了周期任务集最大可挪用时间求解方法，并建立了相关仿真系统对偶发任务的响应时间进行了仿真测试。结果表明，该算法在保证硬实时周期任务满足截止期限的同时，缩短了偶发任务的响应时间，具有一定的实用性。

［1］张杰，阳富民，卢炎生，等.EDF统一调度硬实时周期任务和偶发任务的可调度性判定算法［J］.小型微型计算机系统，2009(12):2383－2388.

［2］沈卓炜.不可抢占式EDF调度算法的可调度性分析［J］.计算机工程与应用，2006(9):10－12.

［3］Davis R I，Burns A，Bril R J，et al.Controller Area Network(CAN)Schedulability Analysis:Refuted，Revisited and Revised［J］.Real-Time Systems，2007，35(3):239 －272.

［4］张利，王跃飞，严刚，等.混合动力汽车CAN网络优先级的动态分配方法［J］.农业机械学报，2011，42(5):22 －26.

［5］王永炎，王强，王宏安，等.基于优先级表的实时调度算法及其实现［J］.软件学报，2004，15(3):361 －369.

［6］涂刚，阳富民，卢炎生.基于动态优先级策略的最优软非周期任务调度算法［J］.计算机研究与发展，2004，41(11).