CAN網(wǎng)絡周期任務與偶發(fā)任務混合調(diào)度的研究*

張建軍，王躍飛，張本宏，張 利，李縣軍

(1.合肥工業(yè)大學計算機與信息學院，合肥 230009;2.合肥工業(yè)大學機械與汽車工程學院，合肥 230009;3.教育部安全關(guān)鍵工業(yè)測控技術(shù)工程研究中心，合肥 230009)

前言

CAN總線是一種具有高抗干擾性和非破壞性仲裁等特點的串行通信協(xié)議，在汽車電子領(lǐng)域得到廣泛應用。整車CAN網(wǎng)絡中，所傳輸?shù)南㈩愋陀兄芷谛?、偶發(fā)性和非周期性消息，有硬實時、軟實時和非實時消息。因此對于CAN網(wǎng)絡消息傳輸，須采用合適的調(diào)度算法來滿足各類消息傳輸?shù)男枨?，進而避免各種消息相互間的不良影響。從本質(zhì)上看，這種網(wǎng)絡消息調(diào)度與操作系統(tǒng)中任務調(diào)度類似，可將其看成實時任務調(diào)度。整車CAN系統(tǒng)是典型的混合任務系統(tǒng)，其調(diào)度目標是在保證硬實時周期任務時限的基礎(chǔ)上，縮短偶發(fā)任務和非周期任務的響應時間。

為實現(xiàn)該調(diào)度目標，時間挪用法［1］是一個較好的方法。其基本思想是在確保硬實時周期任務時限的同時，最大限度地使用周期任務集“挪出”的時間。周期任務集可挪用的時間由不同調(diào)度算法決定，一般情況下，動態(tài)優(yōu)先級算法能夠獲得很好的響應時間。最早截止期優(yōu)先(earliest deadline first，EDF)調(diào)度是典型的基于優(yōu)先級驅(qū)動動態(tài)調(diào)度方法，將其與 CAN 協(xié)議結(jié)合［2－4］，可實現(xiàn) CAN 網(wǎng)絡的EDF調(diào)度。但是該調(diào)度算法在一些特定的情況中，無法對偶發(fā)任務的信息傳輸進行有效調(diào)度。本文中應用了文獻［5］和文獻［6］中關(guān)于EDF調(diào)度算法、逆調(diào)度和空閑時間的研究結(jié)果，提出了基于最大可挪用時間的不可搶占EDF調(diào)度算法。

1 周期任務和偶發(fā)任務混合調(diào)度

1.1 系統(tǒng)模型

將實時任務分為硬實時周期任務和非周期偶發(fā)任務。其中硬實時周期任務集為Π={T1，…，Tn}，Ti=(Si，Ci，Di，Pi)(1≤i≤n)代表周期任務，其中任務首次到來時間為Si，任務的最大執(zhí)行時間為Ci，任務的最后期限為Di，任務的周期為Pi。周期任務Ti第 j次到來記為 τij=(sij，cij，dij，pij)，其中 sij=Si+(j－1)× Pi，cij=Ci，dij=Di，pij=Pi。偶發(fā)任務集記為 Γ，Γ ={J1，…，Jn}，Ji(1≤i≤n)代表偶發(fā)任務，Ji=(Si，Ci，Di)，其中任務的到來時間為 Si，任務的最大執(zhí)行時間為Ci，任務的最后期限為 Di［6］。

設(shè)UΠ=∑(Ci/Pi)≤1為周期任務集CPU的使用率，周期任務集的超周期H為各任務周期的最小公倍數(shù)。同時為方便研究，本文中只研究一個超周期中任務集的執(zhí)行情況針，并對CAN總線特點做如下假設(shè):(1)任務運行時不可被搶占;(2)高優(yōu)先級偶發(fā)任務優(yōu)先被調(diào)度;(3)對于周期任務Di=Pi，Si=0;(4)忽略進程調(diào)度與任務切換時間;(5)最大可挪用時間＞最壞執(zhí)行時間;(6)忽略進程調(diào)度與任務切換時間。

1.2 基本概念

為方便描述混合調(diào)度方法，引入文獻［1，6］中的相關(guān)術(shù)語，定義了如下概念。

定義1 任務執(zhí)行區(qū)間:設(shè)任務Ti獲得CPU開始執(zhí)行時刻為si，Ti執(zhí)行完讓出CPU時刻為ei，則區(qū)間［si，ei)為 Ti的任務執(zhí)行區(qū)間。

定義2 調(diào)度 ＆:設(shè) ＆={＆1，…，＆n}為超周期H內(nèi)周期性任務執(zhí)行過程。記任務Ti的執(zhí)行過程為 ＆i={＆i1，…，＆ik}，＆ij={［s1，e1)，…，［sp，ep)}，1≤i≤n，k=H/Pi，且 sq＜eq＜sq+1(1≤q≤p)。

定義3 調(diào)度執(zhí)行區(qū)間:如果周期任務集的任務在時刻 S獲得 CPU，在時刻 E讓出 CPU，且在［S，E)時間段中從未讓出過CPU，則稱Π的調(diào)度執(zhí)行區(qū)間為［S，E)。

定義4 ＆(t):＆(t)是在時刻t以前調(diào)度＆已經(jīng)完成的任務執(zhí)行區(qū)間的集合。

定義5 逆調(diào)度＆－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)為對應的任務執(zhí)行區(qū)間集。

定義6 ＆－1(t):＆－1中在時刻t以前已經(jīng)完成的任務執(zhí)行區(qū)間記為＆－1(t)。

假設(shè)τij是在＆(t)中未執(zhí)行而＆－1(t)中已執(zhí)行的任務是＆－1－＆(t)中 t+ε時刻后當前任務第一個執(zhí)行區(qū)間。

其中，1≤i≤n，j=H/Pi，T 是系統(tǒng)在 t+ ε 時刻后的空閑時間，w是后移執(zhí)行區(qū)間的截止期。

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

v是＆－1－＆(t)中t+ε時刻后當前任務第一執(zhí)行區(qū)間截止時刻。T'是＆－1－＆(t)中t+ε時刻后，第一執(zhí)行區(qū)間后的空閑時間。

定義7 ＆－1－＆(t):＆－1－＆(t)是逆調(diào)度 ＆－1減去＆(t)后剩余的任務執(zhí)行區(qū)間。設(shè)n是周期任務數(shù)，＆－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混合調(diào)度

2.1 基本思想

針對CAN網(wǎng)絡硬實時周期任務與非周期偶發(fā)任務混合調(diào)度無法保證非周期偶發(fā)任務實時性的問題，在EDF調(diào)度與逆調(diào)度起止時刻表(見表1)的基礎(chǔ)上，提出基于最大可挪用時間的不可搶占EDF調(diào)度算法。即在網(wǎng)絡運行時，網(wǎng)絡中調(diào)度節(jié)點根據(jù)其他節(jié)點提供的信息建立或者更新自身的EDF調(diào)度與逆調(diào)度起止時刻表，當偶發(fā)任務發(fā)生時，根據(jù)此表計算調(diào)度與逆調(diào)度可挪用時間，實現(xiàn)偶發(fā)任務的及時響應。

表1 EDF調(diào)度與逆調(diào)度起止時刻表

表1中:MS_NM為消息名稱，SC_S_TIME為EDF調(diào)度消息報文傳輸起始時刻，SC_E_TIME為EDF調(diào)度消息報文傳輸終止時刻，NSC_S_TIME為與調(diào)度相對應的消息報文逆調(diào)度起始時刻，NSC_E_TIME為與調(diào)度相對應的消息報文逆調(diào)度終止時刻。

2.2 最大可挪用時間計算

定理:S是＆－1－＆(t)中第一個調(diào)度執(zhí)行區(qū)間的開始時刻，則周期任務在時刻t+ε的最大可挪用時間 TKN=S －(t+ε)［1］。

證明:因為不能后移＆－1(t)的所有調(diào)度執(zhí)行區(qū)間，故不能后移＆－1(t)－＆(t)中的任何調(diào)度執(zhí)行區(qū)間，＆－1－＆(t)中第一個調(diào)度執(zhí)行區(qū)間的開始時刻是S，即S的值在時刻t+ε后是不能再增大的，故任務在時刻t+ε的最大可挪用時間TKN=S－(t+ε)，證畢。

根據(jù)定理的結(jié)論，可以設(shè)計求解最大可挪用時間相應的算法。用向量 α ={s1，s2，…，si，si+1，…，sN}表示一個超周期中所有任務到來的時間，設(shè)si＜si+1，s1=0，sN=H。在一個超周期中，周期任務到來次數(shù)之和為N。每個si對應的＆－1(si)由定義7計算得到。t+ε前周期任務的完成量len(＆－1(t))和len(＆(t))組成向量 β ={len(＆－1(t))，len(＆(t))}。得到α和β之后，根據(jù)下面的公式，可以計算任意時刻t與＆－1－＆(t)對應的S:

其中t+ε =(j－1)Pi+cij，j是第 i個任務的第j次執(zhí)行，cij=Ci，TKN=S － ((j－1)Pi+cij)。

2.3 不可搶占EDF混合調(diào)度算法

本算法的思路是讓周期任務集先運行一個超周期的時間，得出＆、＆－1、α和β的值，在運行過程中計算＆－1(t)的值，調(diào)度算法的流程見圖1，具體步驟如下。

Step1:在第1個超周期中，使用EDF調(diào)度運行各周期消息，各節(jié)點記錄消息報文發(fā)送時刻α。當接收節(jié)點正確接收消息報文時，會在應答間隙期間向發(fā)送節(jié)點發(fā)出ACK應答信號，發(fā)送節(jié)點記錄此時刻，獲得消息報文的執(zhí)行時間。若偶發(fā)消息到來，讓其在后臺運行，使偶發(fā)消息在空閑時間執(zhí)行。

Step2:記錄EDF調(diào)度(＆)起止時刻，同時計算逆調(diào)度＆－1的執(zhí)行起止時刻。

Step3:通過周期性消息報文的發(fā)送，調(diào)度節(jié)點獲得一張各節(jié)點消息調(diào)度與逆調(diào)度起止時刻表，記錄了各周期性消息報文EDF調(diào)度與逆調(diào)度執(zhí)行的起止時間。

Step4:若t時刻偶發(fā)消息到來，調(diào)度節(jié)點根據(jù)EDF調(diào)度與逆調(diào)度起止時刻表計算β，由此可以得到＆－1－＆(t)對應的任務執(zhí)行起始時刻S。

Step5:計算 S－(t+ε)，若 S－(t+ε)＞0，則挪用S－(t+ε)長度的時間段，若 S－(t+ε)≤0，則等到對應的調(diào)度執(zhí)行區(qū)間結(jié)束后轉(zhuǎn)Step4，重新計算S－(t+ε)的值。

Step6:挪用S－(t+ε)時間段后，繼續(xù)使用EDF調(diào)度，記錄周期任務的起止時刻到EDF調(diào)度與逆調(diào)度的起止時刻表中。

Step7:新的超周期到來，轉(zhuǎn)Step3。

3 仿真實驗

在Vector CANoe平臺中建立仿真系統(tǒng)，該系統(tǒng)由7個汽車控制節(jié)點和1個調(diào)度節(jié)點組成，如圖2所示。其中，調(diào)度節(jié)點負責＆、＆－1和＆－1－＆(t)的運算。設(shè)周期任務選取滿足假設(shè)(6)，周期性任務的參數(shù)如表2所示，經(jīng)計算可知負載率(即CPU使用率)分別為24%、49%和98%。

偶發(fā)任務隨機產(chǎn)生，為了方便計算，根據(jù)周期任務集，取偶發(fā)任務為 J1=(3，1，12)、J2=(7，1，12)、J3=(10，1，12)3種情況進行分析，圖3～圖5分別是負載等于98%、49%和24%情況下的比較結(jié)果，可以看出:在后臺運行法、帶寬保留法和本文的時間挪用法等3種方法下，隨著系統(tǒng)負載的增加，偶發(fā)任務的響應時間隨著增加，本文的時間挪用法在網(wǎng)絡負載較低時，獲得了很好的響應時間，在網(wǎng)絡負載高時也獲得了較為理想的響應時間。結(jié)果表明本文中所提出的方法可在不影響周期任務集調(diào)度的情況下滿足偶發(fā)任務的實時調(diào)度。

表2 周期任務集

4 結(jié)論

針對CAN網(wǎng)絡中應用的EDF算法，引入了調(diào)度與逆調(diào)度等相關(guān)概念。運用這些概念，以硬周期任務時限為約束條件，提出了周期任務集最大可挪用時間求解方法，并建立了相關(guān)仿真系統(tǒng)對偶發(fā)任務的響應時間進行了仿真測試。結(jié)果表明，該算法在保證硬實時周期任務滿足截止期限的同時，縮短了偶發(fā)任務的響應時間，具有一定的實用性。

［1］張杰，陽富民，盧炎生，等.EDF統(tǒng)一調(diào)度硬實時周期任務和偶發(fā)任務的可調(diào)度性判定算法［J］.小型微型計算機系統(tǒng)，2009(12):2383－2388.

［2］沈卓煒.不可搶占式EDF調(diào)度算法的可調(diào)度性分析［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網(wǎng)絡優(yōu)先級的動態(tài)分配方法［J］.農(nóng)業(yè)機械學報，2011，42(5):22 －26.

［5］王永炎，王強，王宏安，等.基于優(yōu)先級表的實時調(diào)度算法及其實現(xiàn)［J］.軟件學報，2004，15(3):361 －369.

［6］涂剛，陽富民，盧炎生.基于動態(tài)優(yōu)先級策略的最優(yōu)軟非周期任務調(diào)度算法［J］.計算機研究與發(fā)展，2004，41(11).