CAN總線中改進(jìn)的EDF調(diào)度算法可調(diào)度性分析

王 浩，張鳳登

(上海理工大學(xué) 光電信息與計算機(jī)工程學(xué)院，上海 200082)

0 引言

CAN總線采用面向消息的優(yōu)先級控制方式，用標(biāo)識符定義靜態(tài)消息優(yōu)先級，以及其短幀格式和CSMA/CA訪問控制，使得CAN具有極高的可靠性和獨特的設(shè)計，特別適合工業(yè)過程控制設(shè)備的互連[1]，因此CAN總線不僅僅局限適用于車體的控制系統(tǒng)中，在艦艇、航天、檢測等控制領(lǐng)域，CAN總線的身影也逐漸增多。從而，國內(nèi)外的學(xué)者均投入了大量精力，針對于CAN總線的調(diào)度做研究。最初，由Tindell等人將針對于單處理器的調(diào)度分析演化為求消息的最壞響應(yīng)時間來對CAN總線調(diào)度進(jìn)行分析[2]；K.M.Zuberi和K.G.Shin首次提出將EDF算法應(yīng)用于CAN總線[3]，但當(dāng)時他們提出的方法對CAN做出一些不切實際的假設(shè)并且由于時間范圍較短，調(diào)度能力的體現(xiàn)有一定的局限性，因而Livani對Zuberi等人的方法進(jìn)行改進(jìn)[4]；國內(nèi)對于這方面的研究起步較晚，主要集中于理論研究，例如，諶介人、彭軍等人提出了基于指數(shù)分區(qū)的EDF算法，一定程度上較平均分區(qū)的EDF算法保證了實時性[5]；袁暋、檀明等人針對搶占式和非搶占式的EDF調(diào)度算法，提出了任務(wù)集新的可調(diào)度性測試條件[6]。但是，在某些特殊情況下，現(xiàn)有的EDF算法經(jīng)常會導(dǎo)致CAN總線無法正常通訊調(diào)度，因此針對此現(xiàn)象，本文通過優(yōu)化算法改善總線仲裁機(jī)制完成對消息集的調(diào)度，提出了一種新的基于雙冪函數(shù)分區(qū)的EDF調(diào)度算法。

1 平均分區(qū)EDF算法

1.1 平均分區(qū)的EDF算法

EDF(Earliest deadline first)算法是按照絕對截止時間的遠(yuǎn)近來分配優(yōu)先級，即消息的絕對截止時間越近，任務(wù)的優(yōu)先級越高。在這種調(diào)度機(jī)制下，消息的優(yōu)先級并不是固定的，而是在每次仲裁前依據(jù)截止時間的變化，計算相應(yīng)的動態(tài)優(yōu)先級，最大程度的保證消息不錯過其截止時間。EDF算法的核心就是將消息的截止時間通過編碼方式轉(zhuǎn)換為標(biāo)識符的一部分，通過比較標(biāo)識符大小判定消息的優(yōu)先級。但是從實際情況可以看出，隨著時間的增大，消息的絕對截止時間也會無限增大，當(dāng)增大到一定程度時，由于標(biāo)識符位數(shù)的限制，從而無法對其編碼轉(zhuǎn)為標(biāo)識符的一部分。針對于此，文獻(xiàn)[4]中提出相對截止期的概念，因為消息的時間參考點是每一次仲裁開始時間，所以相對截止時間等于絕對截止時間減去仲裁開始時間，定義：

D=d-ts

(1)

式中，D為相對截止時間。隨著ts的增加，D會逐漸減小。根據(jù)EDF算法，相對截止時間D會逐漸減小，從而在前一次仲裁失敗的消息其D的減小意味著下次仲裁時優(yōu)先級的提升。當(dāng)然，即使通過這種優(yōu)化，相對截止時間表示的時間范圍仍會很大，因此Livani提出了平均分區(qū)的EDF調(diào)度算法。對于一組消息{m1,m2,…,mn}，其中，相對截止時間為{D1,D2,…,Dmax}，并且按照從小到大順序排列。平均分區(qū)就是將時間軸等分成k段，最后一段區(qū)間需要包含最大的相對截止時間Dmax，一般可以直接將時間軸的最大值設(shè)為最大相對截止時間，其中每段的時間長度稱為基本時間單元U。如圖1所示，在每一輪仲裁開始時，根據(jù)公式(1)計算出相對截止時間，再根據(jù)圖1所劃分的區(qū)域判斷相對截止時間在哪個時間段中，再根據(jù)當(dāng)前時間段的區(qū)間號來表示消息的優(yōu)先級。

圖1 平均分區(qū)示意圖

1.2 量化誤差的分析和影響

由C.L.Liu[7]等人提出的EDF調(diào)度算法判定定理：假定存在一個由n個周期性消息構(gòu)成的任務(wù)集{M1,M2,…，Mn}，如果消息i滿足如下判定式(2)，則該消息可調(diào)度。

(2)

若任務(wù)集中所有消息均滿足上式，則該任務(wù)集可調(diào)度。

其中：Ci為消息i的傳輸時間，Di為消息i的截止時間，Bi為消息i的最大阻塞時間。

我們通過計算可以得到相對截止時間，盡管這些值可能在數(shù)值上的確有些差異，但是在將相對截止時間進(jìn)行分區(qū)時，分割所得到的每個區(qū)間是有長度的，無法保障不同的截止時間落到不同的區(qū)間中，從而導(dǎo)致不同相對截止時間的消息得到相同的優(yōu)先級。這是“分區(qū)”方案所帶來的誤差，且無法避免，將這種誤差稱之為“量化誤差”。由圖(1)可得，最糟糕的情況下，即兩個相對截止時間分別無限接近于某個區(qū)間的上下限，此時量化誤差最大可近似等于基本時間單元U。因此，在量化誤差的影響下，判定式可更新為下式：

(3)

(4)

取max{xi}=x，則：

(5)

對比式(2)、(5)可以看出，量化誤差對CAN總線的消息傳輸帶來影響，且使得任務(wù)可被調(diào)度的條件更為嚴(yán)苛。

若存在消息mi和mj的標(biāo)識符分別為Ii和Ij且Ii>Ij，即mj的優(yōu)先級高于mi。參考圖1，當(dāng)兩個消息的相對截止時間十分接近時，且Di

2 雙冪函數(shù)分區(qū)EDF算法

2.1 雙冪函數(shù)分區(qū)的EDF算法

由于平均分區(qū)的缺陷，使得優(yōu)先級反轉(zhuǎn)現(xiàn)象頻出，也正是基于此，本論文提出新的冪函數(shù)分區(qū)方法。

具體過程如下：采用以a為冪指數(shù)的方式對相對截止時間Dmax進(jìn)行分區(qū)，a的值取決于實際的系統(tǒng)情況。為簡化計算，以及考慮到CAN總線通訊時各節(jié)點處理器的工作情況，第二次使用冪函數(shù)分區(qū)時，冪指數(shù)取1。冪函數(shù)分區(qū)使得不同截止期的消息更容易分到不同的母區(qū)間內(nèi)，更好地保證了消息的實時性。分區(qū)方法如圖2所示。

圖2 雙冪函數(shù)分區(qū)示意圖

Ui,j=

(6)

2.2 可調(diào)度性分析

令右式記為函數(shù)f(x)，利用數(shù)學(xué)方式求極限[8]：

所以如果已有：

則必有：

(7)

(8)

顯然，滿足判定式(8)時，任務(wù)集是可被調(diào)度的，各參數(shù)的取值取決于實際環(huán)境中消息截止期的分布范圍，選取合適的參數(shù)值可以獲得合適的分區(qū)范圍，從而使得調(diào)度性能得到優(yōu)化。通過對比圖1和圖2可以發(fā)現(xiàn)，采用雙冪函數(shù)分區(qū)時，可以將接近起始時間的區(qū)域分區(qū)更小，提高精度，從而使得不同截止期的消息可以分配到不同的母區(qū)間，有效減少了截止期相近的的消息被分配到同一個母區(qū)間內(nèi)的概率。與平均分區(qū)相比，調(diào)度的條件也變得更加苛刻，這是保證消息實時性所必須要達(dá)到的前提條件。

3 實驗驗證與分析

在上一章節(jié)，借助量化誤差的概念理論上給出了消息集可調(diào)度的判定準(zhǔn)則，接下來我們通過系統(tǒng)模擬方式來驗證是否滿足可調(diào)度性。采用系統(tǒng)模擬方式簡單易行，雖然結(jié)果不能完全反應(yīng)系統(tǒng)的真實情況，但能夠作為一種輔助手段去驗證我們提出的雙冪函數(shù)分區(qū)調(diào)度算法。

參考本文所提出的改進(jìn)的EDF調(diào)度算法，采用CANoe平臺進(jìn)行仿真實驗。CANoe的主要組成部分：模擬界面編輯、CANdb++編輯器、CAPL瀏覽器、面板設(shè)計等。目前市面上流行的幾種總線，如CAN、LIN、FlexRay、以太網(wǎng)等，均可在CANoe上實現(xiàn)仿真測試。通過CANoe可以將所有節(jié)點虛擬化，對于各個節(jié)點相應(yīng)的通信數(shù)據(jù)可以使用CANdb++編輯器建立所需要的數(shù)據(jù)庫，并通過CAPL語言編寫各CAN節(jié)點程序?qū)崿F(xiàn)節(jié)點間的通訊、錯誤處理等。

此外，汽車工程師協(xié)會(SAE)提供了一個“基準(zhǔn)”應(yīng)用[9]，其描述了在原型電動汽車上的7個不同子系統(tǒng)之間發(fā)送的一組信號。盡管這個汽車控制系統(tǒng)是使用點對點鏈路設(shè)計的，但是這組信號為說明CAN總線在復(fù)雜分布式實時控制系統(tǒng)中的應(yīng)用提供了一個很好的例子，因此，針對于本次實驗，我們將通過CANoe搭建出此網(wǎng)絡(luò)通信模型。其中7個子系統(tǒng)分別是：電池(Battery)，車輛控制器(V/C)，逆變器/電機(jī)控制器(I/M C)，儀表盤顯示(Ins)，驅(qū)動器輸入(Driver)，制動器(Brakes)，變速器控制(Trans)，如圖3所示。

圖3 節(jié)點示意圖

連接這些子系統(tǒng)的網(wǎng)絡(luò)需要處理總共53個信號，按照信號的接收方、發(fā)送方、信號周期以及信號長度等要求將信號打包成10個消息，如表1所示。根據(jù)表中信息，通過操作CANdb++,將所有信號打包封裝，并且對該網(wǎng)絡(luò)的相關(guān)參數(shù)進(jìn)行配置，如波特率、采樣點等。根據(jù)表1消息矩陣中消息的周期分布情況，同時在滿足判定式(8)的前提下，可將分區(qū)中各參數(shù)選取為：a=2，k=16，q=8。

表1 消息矩陣

CAN網(wǎng)絡(luò)中的節(jié)點在收發(fā)消息時，依據(jù)本文所提出的雙冪函數(shù)分區(qū)EDF調(diào)度算法，利用CAPL編程對消息以及通訊進(jìn)程進(jìn)行動態(tài)處理，以實現(xiàn)合理的調(diào)度。具體實現(xiàn)過程如下：在本文的調(diào)度機(jī)制下，CAN節(jié)點在發(fā)送消息前，計算該消息的相對截止時間，然后依據(jù)所得相對截止時間算出對應(yīng)的母區(qū)間和子區(qū)間號，將對應(yīng)的區(qū)間號轉(zhuǎn)換為消息的優(yōu)先級并進(jìn)行進(jìn)制轉(zhuǎn)換得到消息的標(biāo)識符，再根據(jù)當(dāng)前的標(biāo)識符進(jìn)行仲裁。部分程序設(shè)計如下所示：

if(msg4.DIR!=TX)

{

t_new=timeNow()/100000.0+0.16;

write("t_new=%f",t_new);

D=d-t_new-init;

count++;

if(D>0.001&&D<62.5)

{

g=1;

h=_floor(7-(1000.0/(16*D)));

}

else if(D>62.5)

{

g=_floor(5-exp(1000/D));

h=_floor((exp(6-g)*6*D-7000)/(exp(6-g)*D-1000));

}

p=h+(g-1)*5;

write("p4=%d",p);

p=0x14-p;

p=p<<18;

對于雙冪函數(shù)分區(qū)調(diào)度算法的網(wǎng)絡(luò)性能分析，我們主要將關(guān)注點放在最壞響應(yīng)時間上，最壞響應(yīng)時間是消息的最大時延，即消息在隊列中的最長排隊時間和傳輸時間的總和，因此實時性的強(qiáng)弱在數(shù)據(jù)上最直觀的體現(xiàn)就是最壞響應(yīng)時間的大小。其中，挑選出5組周期差別較大的消息通過對比平均分區(qū)方法來驗證雙冪函數(shù)分區(qū)的優(yōu)越性。每組實驗3次后計算“消息最壞響應(yīng)時間”的平均值，實驗結(jié)果如圖4所示。

圖4 消息最壞響應(yīng)時間

結(jié)合實驗結(jié)果，對比傳統(tǒng)的基于平均分區(qū)EDF調(diào)度算法，我們可以發(fā)現(xiàn)本文提出的基于雙冪函數(shù)分區(qū)方法所具有的優(yōu)點：

1)針對于消息集的截止期，采用傳統(tǒng)的平均分區(qū)EDF調(diào)度算法(分區(qū)大小為2 ms)，在對標(biāo)識符進(jìn)行編碼時至少需要7位才能夠滿足編碼要求，而采用本文的方法，只需要6位就可以滿足需求。

2)通過計算可以得知，在本文的試驗參數(shù)下，最小的子區(qū)間大小約為0.05 ms，相較于平均分區(qū)的2 ms，明顯提高了分區(qū)精度，換言之，在經(jīng)歷一段時間后，消息的截止期在不斷地減小，那么仍然會導(dǎo)致多個消息的截止期落在同一個分區(qū)內(nèi)，從而獲得同樣的優(yōu)先級，而本文的雙冪函數(shù)分區(qū)方法可以將截止期劃分至微秒級，從而保證了較高的辨識度。

3)采用雙冪函數(shù)分區(qū)的EDF調(diào)度算法，可以降低消息集的最壞響應(yīng)時間，從圖5中可以觀察到20 ms以內(nèi)的消息，即高優(yōu)先級消息，最壞響應(yīng)時間的減少尤為明顯，這也驗證了第二點，雙冪函數(shù)分區(qū)現(xiàn)在對較小的截止期上依然保證了很強(qiáng)的辨識度。

顯然，通過雙冪函數(shù)分區(qū)的方法進(jìn)行調(diào)度，分區(qū)誤差進(jìn)一步減小，對于截止期最終落在哪個分區(qū)更為精確，降低了因優(yōu)先級反轉(zhuǎn)而無法調(diào)度的情況，使得消息的最壞響應(yīng)時間得到了有效的縮減，從而提高了網(wǎng)絡(luò)傳輸?shù)膶崟r性。

4 結(jié)束語

本文對比平均分區(qū)EDF調(diào)度算法，對于量化誤差引起的消息不可被調(diào)度問題，引入一種雙冪函數(shù)分區(qū)的方法。理論分析量化誤差對該方法的影響，并論證了該方法使用時消息可調(diào)度的判定條件。實驗證明了本文的雙冪函數(shù)分區(qū)調(diào)度算法對消息的截止周期進(jìn)行合理的分配，從而克服了傳統(tǒng)EDF算法在調(diào)度方面的不足，優(yōu)化了消息的最壞響應(yīng)時間，提高系統(tǒng)實時性，對于EDF調(diào)度算法在實際中更好的應(yīng)用于CAN總線通信優(yōu)化中起著指導(dǎo)作用。