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

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

前言

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

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

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

1.1 系統(tǒng)模型

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

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

1.2 基本概念

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

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

定義2 調(diào)度 ＆:設(shè) ＆={＆1，…，＆n}為超周期H內(nèi)周期性任務(wù)執(zhí)行過程。記任務(wù)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ū)間:如果周期任務(wù)集的任務(wù)在時(shí)刻 S獲得 CPU，在時(shí)刻 E讓出 CPU，且在［S，E)時(shí)間段中從未讓出過CPU，則稱Π的調(diào)度執(zhí)行區(qū)間為［S，E)。

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

定義5 逆調(diào)度＆－1:＆－1是相對(duì)于＆的過程，即={［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)為對(duì)應(yīng)的任務(wù)執(zhí)行區(qū)間集。

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

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

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

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

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

定義7 ＆－1－＆(t):＆－1－＆(t)是逆調(diào)度 ＆－1減去＆(t)后剩余的任務(wù)執(zhí)行區(qū)間。設(shè)n是周期任務(wù)數(shù)，＆－1－＆(t)={［sq+1，eq+1)，…，［sj，ej)}。當(dāng)len(＆i(t))={(e1－s1)+… +(eq－sq)}時(shí)，＆－1－＆(t)={(＆1－1－＆1(t))+… +(＆n－1－ ＆n(t))}。

2 不可搶占EDF混合調(diào)度

2.1 基本思想

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

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

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

2.2 最大可挪用時(shí)間計(jì)算

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

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

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

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

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

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

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

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

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

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

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

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

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

3 仿真實(shí)驗(yàn)

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

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

表2 周期任務(wù)集

4 結(jié)論

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

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

［2］沈卓煒.不可搶占式EDF調(diào)度算法的可調(diào)度性分析［J］.計(jì)算機(jī)工程與應(yīng)用，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］張利，王躍飛，嚴(yán)剛，等.混合動(dòng)力汽車CAN網(wǎng)絡(luò)優(yōu)先級(jí)的動(dòng)態(tài)分配方法［J］.農(nóng)業(yè)機(jī)械學(xué)報(bào)，2011，42(5):22 －26.

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

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