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).