避免CAN總線饑餓報(bào)文的調(diào)度算法研究

摘要：CAN總線以非破壞性仲裁方式，保證了高優(yōu)先級(jí)信息的優(yōu)先傳輸，大量報(bào)文的傳輸，增加了總線負(fù)載率的同時(shí)也導(dǎo)致出現(xiàn)了饑餓報(bào)文，各節(jié)點(diǎn)的實(shí)時(shí)性需要無法得到滿足。CAN總線調(diào)度算法通過優(yōu)化調(diào)整報(bào)文優(yōu)先級(jí)，保證了數(shù)據(jù)傳輸?shù)膶?shí)時(shí)性。因此，本文首先介紹了CAN總線的基本結(jié)構(gòu)，其次分析了導(dǎo)致饑餓報(bào)文出現(xiàn)的原因，最后總結(jié)了近年CAN總線調(diào)度算法的研究現(xiàn)狀。

關(guān)鍵詞：CAN總線；調(diào)度算法；饑餓報(bào)文；仲裁

一、引言

控制局域網(wǎng)絡(luò)（Controller Area Net， CAN）總線通信協(xié)議是一種國(guó)際標(biāo)準(zhǔn)化串行通信協(xié)議，能夠?qū)﹄姎庠O(shè)備實(shí)現(xiàn)分布式實(shí)時(shí)控制，道路車輛行業(yè)應(yīng)用最廣泛。廠商為了提高車輛的舒適度以及駕駛安全性，在車身上增加了大量的電控元件、傳感器和執(zhí)行器，眾多元器件的加入增加了CAN總線的負(fù)載率，影響了CAN總線數(shù)據(jù)傳輸?shù)膶?shí)時(shí)性。因此，合理的算法調(diào)度對(duì)于提高CAN總線工作效率和實(shí)時(shí)性至關(guān)重要。近年來，對(duì)CAN總線調(diào)度的算法研究較多，本文主要介紹近年來國(guó)內(nèi)外CAN總線調(diào)度算法的研究。

二、CAN總線

（一）CAN總線介紹

國(guó)際化標(biāo)準(zhǔn)組織提出了開放式通信系統(tǒng)互聯(lián)參考的OSI模型定義了7層模型，包括：物理層、數(shù)據(jù)鏈路層、網(wǎng)絡(luò)層、傳輸層、會(huì)話層、表示層、應(yīng)用層。在OSI模型中，CAN總線位于第1層物理層以及第2層數(shù)據(jù)鏈路層。

（二）CAN節(jié)點(diǎn)結(jié)構(gòu)

CAN節(jié)點(diǎn)包括CAN收發(fā)器和CAN控制器，收發(fā)器之間通過CAN_H 和CAN_L端口連接， CAN_H和CAN_L之間的電壓差值稱為差分電壓，從而形成數(shù)據(jù)傳輸?shù)牟罘中盘?hào)。收發(fā)器和控制器之間通過TTL電平信號(hào)進(jìn)行數(shù)據(jù)傳輸。

（三）饑餓報(bào)文

CAN總線報(bào)文數(shù)據(jù)通過標(biāo)識(shí)符確定的優(yōu)先級(jí)參與總線競(jìng)爭(zhēng)，重要數(shù)據(jù)采用高優(yōu)先級(jí)進(jìn)行數(shù)據(jù)傳輸，非重要數(shù)據(jù)采用低優(yōu)先級(jí)進(jìn)行數(shù)據(jù)傳輸，當(dāng)總線中存在多個(gè)節(jié)點(diǎn)同時(shí)參與數(shù)據(jù)傳輸時(shí)，優(yōu)先級(jí)高的節(jié)點(diǎn)數(shù)據(jù)總是能夠順利傳輸，而優(yōu)先級(jí)低的節(jié)點(diǎn)數(shù)據(jù)在總線空閑的狀態(tài)下才能夠進(jìn)行傳輸。因此，導(dǎo)致低優(yōu)先級(jí)節(jié)點(diǎn)長(zhǎng)時(shí)間保持沉默，從而形成饑餓報(bào)文。饑餓報(bào)文會(huì)導(dǎo)致節(jié)點(diǎn)數(shù)據(jù)丟失，因此需要合適的算法進(jìn)行調(diào)度，保證高優(yōu)先級(jí)報(bào)文不喪失其優(yōu)先傳輸權(quán)限的情況下，同時(shí)滿足低優(yōu)先級(jí)數(shù)據(jù)的傳輸。

三、CAN總線的調(diào)度算法

針對(duì)CAN總線優(yōu)先級(jí)調(diào)度的問題，學(xué)者們已經(jīng)進(jìn)行了大量的研究。目前的CAN總線優(yōu)先級(jí)調(diào)度算法分為靜態(tài)調(diào)度算法、動(dòng)態(tài)調(diào)度算法以及混合調(diào)度算法，其中靜態(tài)調(diào)度算法包括單調(diào)速率優(yōu)先級(jí)算法、截止期單調(diào)優(yōu)先級(jí)算法及分布式TTCAN算法等，動(dòng)態(tài)調(diào)度算法包括最早截止期優(yōu)先級(jí)算法、最小松弛優(yōu)先級(jí)算法等，混合調(diào)度算法將靜態(tài)調(diào)度算法和動(dòng)態(tài)調(diào)度算法進(jìn)行組合，不同的算法在調(diào)度邏輯上也存在不同。

（一）靜態(tài)調(diào)度算法

靜態(tài)調(diào)度算法的邏輯是在CAN總線節(jié)點(diǎn)未開始工作前，根據(jù)節(jié)點(diǎn)信息重要性先定義好每個(gè)節(jié)點(diǎn)的優(yōu)先級(jí)。在CAN總線工作時(shí)，按照預(yù)先定義好的節(jié)點(diǎn)優(yōu)先級(jí)發(fā)送報(bào)文，這種工作方式雖然預(yù)配置簡(jiǎn)單方便，但報(bào)文優(yōu)先級(jí)變動(dòng)時(shí)修改繁瑣。

1.RM算法

RM算法是Liu等人提出的一種搶占式、針對(duì)周期性任務(wù)的算法[1]，根據(jù)周期進(jìn)行優(yōu)先級(jí)分配，其截止期等于周期，周期越小，優(yōu)先級(jí)越高。對(duì)于周期性任務(wù)，在傳輸過程中有兩個(gè)參數(shù)：傳輸周期T和傳輸時(shí)間t。傳輸周期T即傳輸間隔，表示任務(wù)多久完成下一次傳輸，傳輸時(shí)間t表示傳輸一次任務(wù)需要的時(shí)間。

假設(shè)有兩組報(bào)文M1和M 2，M1的傳輸周期和傳輸時(shí)間分別為T1和t1，M 2的傳輸周期和傳輸時(shí)間分別為T2和t2，規(guī)定T1＜T2，且t1＜t2，同組報(bào)文傳輸時(shí)間小于傳輸周期，即報(bào)文必須在周期內(nèi)傳輸完成，執(zhí)行示意圖如圖1所示。

由于M1周期小，因此M1優(yōu)先級(jí)高于M 2，M1優(yōu)先傳輸，在t1時(shí)刻，M1的第一次報(bào)文M11傳輸完成，此時(shí)將M1在T1周期內(nèi)的剩余時(shí)間分配給M 2的第一次傳輸M 21，當(dāng)M1周期再次到來時(shí)，由于優(yōu)先級(jí)的仲裁，M12將會(huì)搶占正在傳輸?shù)腗 21進(jìn)行傳輸，直至M12傳輸完畢，系統(tǒng)將優(yōu)先級(jí)再次給到M 21進(jìn)行傳輸。

RM算法只能對(duì)周期性任務(wù)進(jìn)行調(diào)度，但在實(shí)際工況中，非周期性任務(wù)也大量存在，馮紅艷等人對(duì)RM算法進(jìn)行優(yōu)化[2]，將系統(tǒng)中的非周期任務(wù)臨時(shí)轉(zhuǎn)化為周期性任務(wù)，通過預(yù)先約定的優(yōu)先級(jí)規(guī)則將其插入到就緒列隊(duì)相應(yīng)的位置，并且完成調(diào)度。

2.DM算法

DM算法是RM算法的進(jìn)一步優(yōu)化，與RM不同的是，DM對(duì)于調(diào)度的任務(wù)均設(shè)置了確定的截止期D和周期T，且截止期D小于周期T，截止期越短，其調(diào)度任務(wù)優(yōu)先級(jí)越高，截止期越長(zhǎng)，其調(diào)度任務(wù)優(yōu)先級(jí)越低，DM算法的任務(wù)在其截止期內(nèi)完成，能夠保證系統(tǒng)的實(shí)時(shí)性。

3.TTCAN算法

TTCAN是一種以系統(tǒng)矩陣為核心、基于時(shí)間觸發(fā)的CAN總線協(xié)議的高層協(xié)議。TTCAN的系統(tǒng)矩陣在任務(wù)調(diào)度開始前預(yù)定義完成，每個(gè)系統(tǒng)矩陣由多個(gè)周期組成，每個(gè)周期由多個(gè)時(shí)間窗口組成，時(shí)間窗口分為獨(dú)占時(shí)間窗口、自由時(shí)間窗口以及仲裁時(shí)間窗口。

由于TTCAN基于時(shí)間觸發(fā)，因此對(duì)于周期性任務(wù)傳輸具有極大優(yōu)勢(shì)，同時(shí)也能夠?qū)⒎侵芷谛匀蝿?wù)進(jìn)行轉(zhuǎn)化傳輸，其任務(wù)調(diào)度是在系統(tǒng)矩陣內(nèi)進(jìn)行預(yù)定義的，因此傳輸實(shí)時(shí)性高，但對(duì)于有變化節(jié)點(diǎn)的傳輸環(huán)境中，TTCAN的調(diào)度性能將變得極差，甚至需要重新進(jìn)行任務(wù)調(diào)度定義。

（二）動(dòng)態(tài)調(diào)度算法

動(dòng)態(tài)調(diào)度算法的邏輯是在CAN總線節(jié)點(diǎn)工作時(shí)，根據(jù)預(yù)先定義好的任務(wù)調(diào)度邏輯，實(shí)時(shí)調(diào)整節(jié)點(diǎn)任務(wù)的優(yōu)先級(jí)，以此來避免CAN總線饑餓報(bào)文的出現(xiàn)，同時(shí)可以充分利用處理器的處理性能。

1.EDF算法

EDF算法是根據(jù)任務(wù)的截止期進(jìn)行優(yōu)先級(jí)，其邏輯為截止期越早的任務(wù)，優(yōu)先級(jí)越高。在非搶占式任務(wù)調(diào)度中，只考慮任務(wù)截止期，對(duì)于在某一截止期內(nèi)到來的任務(wù)，直接按照截止期進(jìn)行優(yōu)先級(jí)分配，截止期越小，任務(wù)優(yōu)先級(jí)越高。 在搶占式任務(wù)調(diào)度中，EDF算法雖然也是通過截止期判定優(yōu)先級(jí)，但EDF算法在周期性任務(wù)中需要根據(jù)截止期以及任務(wù)到達(dá)時(shí)間進(jìn)行優(yōu)先級(jí)動(dòng)態(tài)調(diào)整。如圖2所示，假設(shè)有兩組報(bào)文M1和M 2，傳輸時(shí)間分別為t1和t2，截止期分別為D1和D2，規(guī)定D1lt;D2，t1lt;t2，且同組報(bào)文傳輸時(shí)間小于截止期。當(dāng)M1和M 2同時(shí)進(jìn)行傳輸時(shí)，由于M1截止期早，因此M1的初始優(yōu)先級(jí)高，當(dāng)M1的第一次任務(wù)M11傳輸完成后，M 2的第一次任務(wù)M 21開始傳輸。在M 21傳輸過程中，M1的第一次截止期結(jié)束，進(jìn)入第二次截止期，但由于此時(shí)M 2的第一次截止期末結(jié)束，所以M 2的截止期早于M1的第二次截止期，因此此時(shí)M 2的優(yōu)先級(jí)高于M1的優(yōu)先級(jí)，M 2的傳輸任務(wù)不會(huì)被M1搶占，可以傳輸完成。

在EDF算法中，弱化了周期對(duì)任務(wù)調(diào)度的影響，同時(shí)由于動(dòng)態(tài)優(yōu)先級(jí)的分配，理想狀態(tài)下任務(wù)調(diào)度率可以達(dá)到100%。因此，Livani對(duì)EDF的限定條件以及截止期進(jìn)行了優(yōu)化[3]，諶教授等人針對(duì)任務(wù)實(shí)時(shí)性提出了基于指數(shù)分區(qū)的EDF算法[4]，王浩等人基于平均分區(qū)的EDF算法[5]，提出了基于雙冪函數(shù)分區(qū)的EDF算法，將任務(wù)分區(qū)為母區(qū)間和子區(qū)間，克服了平均分區(qū)算法下優(yōu)先級(jí)反轉(zhuǎn)現(xiàn)象頻出的問題，提高了系統(tǒng)的實(shí)時(shí)性。

2.LLF算法

LLF算法根據(jù)任務(wù)的重要性進(jìn)行優(yōu)先級(jí)定義，以松弛度表示任務(wù)的重要性，松弛度越小的任務(wù)越重要，其優(yōu)先級(jí)越高，計(jì)算公式為：

松弛度S=傳輸周期T-傳輸時(shí)間ｔ-當(dāng)前時(shí)間τ（1）

假如有兩組報(bào)文M1和M 2，傳輸周期分別為T1=20和T2=50，傳輸時(shí)間分別為t1=10和t2=25，根據(jù)公式（1），M1和M 2 的調(diào)度如圖3所示.

在τ=0時(shí)刻，報(bào)文傳輸任務(wù)開始，此時(shí)M1的松弛度S11=10，M 2的松弛度S21=25，由于初始M1的松弛度因此M1首先開始傳輸M11，在τ=10時(shí)刻，M11傳輸完成，此時(shí)M1的松弛度S12=20，M 2的第一次周期尚未結(jié)束，所以M 2的松弛度S21=15，S12gt;S21，開始執(zhí)行M 2的第一次任務(wù)M 21的傳輸，以此邏輯進(jìn)行調(diào)度。

LLF算法通過優(yōu)先級(jí)搶占保證了傳輸?shù)膶?shí)時(shí)性，能夠在截止期前檢驗(yàn)優(yōu)先級(jí)的時(shí)間沖突，但調(diào)度增大了系統(tǒng)開銷，同時(shí)在某些特殊情況下會(huì)產(chǎn)生抖動(dòng)。

Hildebrandt J等人采用一種調(diào)度協(xié)處理器增強(qiáng)LLF算法[6]，消除了LLF算法在復(fù)雜調(diào)度時(shí)的抖動(dòng)問題。Sabeghi M等人通過模糊調(diào)度[7]，將截止期作為模糊參數(shù)優(yōu)化了LLF算法，提高了CPU的利用率和搶占性能。

（三）混合調(diào)度算法

根據(jù)實(shí)時(shí)性，CAN總線消息可以劃分為三類：硬實(shí)時(shí)信息、軟實(shí)時(shí)信息和非實(shí)時(shí)信息。混合調(diào)度算法對(duì)于硬實(shí)時(shí)消息給予高優(yōu)先級(jí)，并設(shè)置為固定優(yōu)先級(jí)進(jìn)行優(yōu)先調(diào)度，對(duì)于軟實(shí)時(shí)信息和非實(shí)時(shí)信息給予低優(yōu)先級(jí)，并設(shè)置為動(dòng)態(tài)優(yōu)先級(jí)進(jìn)行調(diào)度。

尹安東等人采用EDF和DM算法混合的調(diào)度策略[8]，設(shè)計(jì)了基于截止期公差遞增區(qū)分策略的混合調(diào)度算法，消除調(diào)度時(shí)的不確定性缺陷和低優(yōu)先級(jí)信號(hào)易鎖死現(xiàn)象。江杰等人提出一種結(jié)合TTCAN和動(dòng)態(tài)晉升機(jī)制的調(diào)度算法[9]，解決了調(diào)度任務(wù)實(shí)時(shí)性和數(shù)據(jù)發(fā)送沖突的問題。

四、存在的問題與展望

隨著研究的不斷深入，CAN總線調(diào)度算法已經(jīng)在工業(yè)領(lǐng)域應(yīng)用。然而，調(diào)度算法解決饑餓報(bào)文的同時(shí)，也帶來了調(diào)度時(shí)時(shí)間開銷的問題。此外，隨著設(shè)備的智能化發(fā)展，需要面對(duì)的網(wǎng)絡(luò)安全問題也越來越多。目前，急需解決CAN總線調(diào)度算法存在的問題，在未來的研究中，需要考慮CAN總線調(diào)度算法的執(zhí)行效率、傳輸安全等問題的權(quán)重，使算法更加合理。

作者單位：李英松 劉劍奇 馮浩然 孫晶 李慧美

中機(jī)生產(chǎn)力促進(jìn)中心有限公司

參考文獻(xiàn)

[1]Liu C L . Scheduling Algorithms for Multiprogramming in a Hard Real-Time Environment[J]. Journal of the ACM， 1973， 20.

[2]馮艷紅，張玉明，徐美華.實(shí)時(shí)調(diào)度算法分類研究[J].微型電腦應(yīng)用，2005，（07）：12-14+1.

[3]Livani M A， Kaiser J. EDF consensus on CAN bus access for dynamic real-time applications[C]//Parallel and Distributed Processing： 10 IPPS/SPDP'98 Workshops Held in Conjunction with the 12th International Parallel Processing Symposium and 9th Symposium on Parallel and Distributed Processing Orlando， Florida， USA， March 30–April 3， 1998 Proceedings 12. Springer Berlin Heidelberg， 1998： 1088-1097.

[4]諶介人，彭軍，吳敏，等.CAN總線中EDF調(diào)度算法的研究與改進(jìn)[J].計(jì)算機(jī)測(cè)量與控制，2008，16（11）：4.

[5]王浩，張鳳登.CAN總線中改進(jìn)的EDF調(diào)度算法可調(diào)度性分析[J].計(jì)算機(jī)測(cè)量與控制，2020.

[6]Hildebrandt J ，" Golatowski F ，" Timmermann D . Scheduling coprocessor for enhanced least-laxity-first scheduling in hard real-time systems[C]// Euromicro Conference on Real-time Systems. IEEE， 1999.

[7]Sabeghi M ，" Bertels K ，" Naghibzadeh M . Deadline vs. Laxity as a Decision Parameter in Fuzzy Real-Time Scheduling." 2006.

[8]尹安東，朱云驍，江昊，等.CAN總線混合調(diào)度算法在HEV控制系統(tǒng)中的應(yīng)用[J].電子測(cè)量與儀器學(xué)報(bào)，2012，26（01）：31-36.

[9]江杰，胡文江，范宇.一種“動(dòng)靜結(jié)合”的CAN總線調(diào)度算法在汽車電子控制網(wǎng)絡(luò)中的研究與應(yīng)用[J].電子技術(shù)應(yīng)用，2007，（06）：127-128.