CAN總線調(diào)度算法研究

蔡一杰，杜 峰 ，胡樂媛，馮兵偉，吳 迪，史星彥

（1.天津職業(yè)技術(shù)師范大學(xué)機(jī)械工程學(xué)院，天津300222；2.天津職業(yè)技術(shù)師范大學(xué)汽車與交通學(xué)院，天津300222）

0 引言

CAN總線是當(dāng)今世界中最為廣泛使用的現(xiàn)場總線之一，每時(shí)每刻都有無數(shù)消息通過CAN總線進(jìn)行傳輸，在CAN總線中傳輸?shù)南⒅饕雌浣刂箷r(shí)間來分類，具體包括必須嚴(yán)格按照截止期進(jìn)行傳輸?shù)挠矊?shí)時(shí)消息、在截止期附近可適當(dāng)彈性傳輸?shù)能泴?shí)時(shí)消息以及沒有嚴(yán)格時(shí)間要求的非實(shí)時(shí)消息[1]。硬實(shí)時(shí)消息一般為實(shí)時(shí)系統(tǒng)中的各種緊急消息（如錯(cuò)誤信息、警告信息），對傳輸時(shí)間的要求極高；軟實(shí)時(shí)消息一般是在系統(tǒng)內(nèi)循環(huán)發(fā)送的消息，對傳輸時(shí)間的要求不太敏感，但不可長期大量超時(shí)，否則會(huì)引起系統(tǒng)報(bào)警，升級為硬實(shí)時(shí)消息；非實(shí)時(shí)消息一般為系統(tǒng)內(nèi)部的檢測信息、組態(tài)信息等，非實(shí)時(shí)消息的數(shù)據(jù)量較大，若即時(shí)發(fā)送會(huì)嚴(yán)重堵塞傳輸網(wǎng)絡(luò)，因此對時(shí)間的要求較為寬松。CAN總線調(diào)度是指在系統(tǒng)的控制下，將需要傳輸?shù)南凑找欢ǖ拇涡蚣皶r(shí)間間隔有序的進(jìn)行發(fā)送分配。在實(shí)時(shí)系統(tǒng)中，網(wǎng)絡(luò)帶寬資源是有限的，那么如何妥善使用有限的帶寬資源，獲得最大的使用效益，完成系統(tǒng)內(nèi)部消息的有序傳輸成為了調(diào)度的主要目標(biāo)[2]，以及接近截止期的消息如何按時(shí)發(fā)送、如何有序的安排周期性消息在無數(shù)非周期性消息中發(fā)送、如何保證實(shí)時(shí)性消息與非實(shí)時(shí)消息在發(fā)送時(shí)的公平性等[3]，也是目前CAN總線調(diào)度尚需解決的問題。

1 實(shí)時(shí)性

CAN總線本身采用的是非破壞性逐步仲裁技術(shù)，依靠標(biāo)識符等確定優(yōu)先級，當(dāng)出現(xiàn)傳輸消息沖突時(shí)，可以有效地根據(jù)優(yōu)先級解決問題。因此CAN總線本身就是基于優(yōu)先級調(diào)度的協(xié)議進(jìn)行的，若需最高的實(shí)時(shí)性，只需采用基于優(yōu)先級的調(diào)度算法即可[4]。基于優(yōu)先級調(diào)度的算法從分配方式上可分為靜態(tài)調(diào)度和動(dòng)態(tài)調(diào)度。

1.1 靜態(tài)調(diào)度算法

靜態(tài)調(diào)度是采用離線預(yù)先分配的方式，在未開始工作時(shí)，依據(jù)各消息的屬性特點(diǎn)將網(wǎng)絡(luò)資源劃分出分配表，在接下來的工作過程中優(yōu)先級不會(huì)發(fā)生改變，除非需要重新進(jìn)行分配。所以靜態(tài)調(diào)度的工作量很小，可以最大程度地保證實(shí)時(shí)性。但是相對地，靜態(tài)調(diào)度在封閉系統(tǒng)中工作性能極佳，那么靈活性較差就成為了它的缺點(diǎn)，在變化的環(huán)境下或者是不可測算的工作環(huán)境下無法保證系統(tǒng)的工作性能甚至正常運(yùn)作。靜態(tài)調(diào)度的優(yōu)缺點(diǎn)非常明顯，它適合在封閉系統(tǒng)、確定性系統(tǒng)或時(shí)間特性不會(huì)變化的系統(tǒng)中進(jìn)行工作。但是一旦網(wǎng)絡(luò)中出現(xiàn)了時(shí)間特性會(huì)變化的節(jié)點(diǎn)或在無法預(yù)測的工作環(huán)境，靜態(tài)調(diào)度的性能會(huì)變得很差甚至不得不全部重新分配。

1.1.1 速率單調(diào)算法

速率單調(diào)算法（RM算法）是一種典型的靜態(tài)調(diào)度算法，它主要面對周期性的任務(wù)，在離線時(shí)預(yù)先劃分出分配表，根據(jù)每個(gè)任務(wù)的周期制定好優(yōu)先級[5]。由于周期任務(wù)具有較短的截止期，如無法在下一個(gè)周期到來之前將本周期的消息傳輸完，就會(huì)導(dǎo)致消息傳輸?shù)臎_突，遺漏或整體的堵塞，所以周期越短的任務(wù)優(yōu)先級應(yīng)越高，即通常情況下應(yīng)當(dāng)給予短周期的任務(wù)最高的優(yōu)先級。在使用RM調(diào)度算法時(shí)，對不同任務(wù)的處理方法不同，對網(wǎng)絡(luò)資源的利用率也不同[6]，因此可以完成的截止期長短也會(huì)有所不同，當(dāng)截止期小于任務(wù)周期的時(shí)候就會(huì)出現(xiàn)不可調(diào)度的情況，所以采用RM算法的具體要求就在于能否調(diào)度。

判斷RM算法能否調(diào)度的關(guān)鍵原理在于處理器的利用率。在RM算法模型中，針對周期性任務(wù)集，利用率U（c）被定義為：

其中：n為周期性任務(wù)的數(shù)量；Ci為任務(wù)i的執(zhí)行時(shí)間；Ti為任務(wù)i的周期。

當(dāng)n→∞時(shí)，

由式（2）可知，當(dāng)無窮多個(gè)任務(wù)同時(shí)搶占時(shí)，處理器利用率極限為69%，即只要利用率小于69%，RM算法就可調(diào)度任何周期性任務(wù)。

1.1.2 截止期單調(diào)算法

截止期單調(diào)算法（DM算法）也是一種靜態(tài)調(diào)度算法，主要面對對象同樣是周期任務(wù)，它是在RM算法的基礎(chǔ)上研究出來的。DM算法工作的方式更為直接，它的理念是截止期優(yōu)先，必須優(yōu)先處理截止期較短的任務(wù)，它通過檢測任務(wù)的截止期來進(jìn)行預(yù)先分配，給予截止期最短的任務(wù)最高的優(yōu)先級。若將DM算法中的任務(wù)看作由周期、執(zhí)行時(shí)間、截止期組成的三元組S=（T，C，D）。此時(shí)任務(wù)集S=（S1，S2，…，Sn），截止期為D1，D2，…，Dn，且滿足D1≤D2≤…≤Dn，則此時(shí)任務(wù)的優(yōu)先級P為P1≥P2≥…≥Pn。這樣能最大程度上保證任務(wù)的可調(diào)度性，提高系統(tǒng)的實(shí)時(shí)性[7]。1.1.3 TT-CAN算法

在保證系統(tǒng)的實(shí)時(shí)性方面，TT-CAN也具備很大優(yōu)勢。它基于時(shí)間觸發(fā)，能夠最大程度的保證低優(yōu)先級消息的實(shí)時(shí)性[8]。如圖1所示為基于時(shí)間觸發(fā)傳送原理圖。

圖1 時(shí)間觸發(fā)傳送原理圖

TT-CAN與RM等算法不同，它是在標(biāo)準(zhǔn)CAN協(xié)議基礎(chǔ)之上的一種高層協(xié)議，不會(huì)對CAN協(xié)議造成變動(dòng)，是一種基于表的、基于時(shí)間觸發(fā)的靜態(tài)調(diào)度協(xié)議。TT-CAN每隔固定的時(shí)間會(huì)向整個(gè)系統(tǒng)發(fā)送基準(zhǔn)消息，各個(gè)節(jié)點(diǎn)會(huì)將該基準(zhǔn)消息作為基準(zhǔn)的“表”，從而達(dá)到確立基準(zhǔn)時(shí)鐘的目的。由于TT-CAN通過確立時(shí)鐘來使各節(jié)點(diǎn)自行管理，所以在協(xié)議中沒有設(shè)置主管理節(jié)點(diǎn)。各個(gè)節(jié)點(diǎn)自身擁有已分配好的調(diào)度表，包含發(fā)送時(shí)間、接受時(shí)間、任務(wù)傳輸周期等信息，系統(tǒng)可以根據(jù)這些信息推算出可能存在的延遲時(shí)間。如圖2所示為TT-CAN工作的基本周期圖。

圖2 TTCAN協(xié)議工作周期

TT-CAN最適合傳輸?shù)南橹芷谛韵?，同時(shí)對于某些非周期性消息，可以依靠基于表的特性將其轉(zhuǎn)換為周期性的傳輸模式[9]。TT-CAN算法擁有著一定的可預(yù)測性但具有靜態(tài)調(diào)度算法的通病，一旦消息本身的時(shí)間特性出現(xiàn)某些改動(dòng)，那么整個(gè)分配表都需要重新調(diào)整。

RM、DM、TT-CAN等算法均為基于固定優(yōu)先級的靜態(tài)調(diào)度算法，他們的高實(shí)時(shí)性都是建立在面對周期性任務(wù)的基礎(chǔ)上的，面對復(fù)雜多變的開放工作環(huán)境時(shí)，可能會(huì)占用大量的網(wǎng)絡(luò)資源，導(dǎo)致消息傳輸?shù)难訒r(shí)甚至丟幀，而且對網(wǎng)絡(luò)資源的低利用率也是一種浪費(fèi)。針對這種情況，研究人員開始嘗試將動(dòng)態(tài)優(yōu)先級的調(diào)度算法應(yīng)用于CAN總線中。

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

在實(shí)時(shí)系統(tǒng)工作時(shí)，可以動(dòng)態(tài)地改變各個(gè)節(jié)點(diǎn)消息的發(fā)送次序，根據(jù)需要實(shí)時(shí)調(diào)整系統(tǒng)中任務(wù)優(yōu)先級的調(diào)度方法被稱為動(dòng)態(tài)調(diào)度算法[10]。在動(dòng)態(tài)調(diào)度過程中，系統(tǒng)根據(jù)實(shí)時(shí)地需求調(diào)整消息的優(yōu)先級，這樣可以充分的利用網(wǎng)絡(luò)資源，較好的適應(yīng)環(huán)境的變化，在復(fù)雜多變的開放工作環(huán)境中也可以穩(wěn)定的進(jìn)行消息傳輸，保證了實(shí)時(shí)系統(tǒng)的魯棒性。當(dāng)然實(shí)時(shí)計(jì)算消息的優(yōu)先級勢必會(huì)占用一部分系統(tǒng)資源，在一定程度上影響了傳輸?shù)男?，因此該類算法通常來說在網(wǎng)絡(luò)負(fù)載較輕的工況下會(huì)擁有較好的調(diào)度效果。

1.2.1 EDF算法

最早在CAN總線中被應(yīng)用的是EDF動(dòng)態(tài)優(yōu)先級調(diào)度算法，即最早截止期優(yōu)先算法。EDF算法可以被稱為最經(jīng)典的動(dòng)態(tài)調(diào)度算法，在實(shí)際工作中，它會(huì)根據(jù)每個(gè)任務(wù)的相對截止期實(shí)時(shí)地進(jìn)行計(jì)算并分配優(yōu)先級，給予相對截止期最短的任務(wù)以最高的優(yōu)先級。

對于EDF算法來說，針對周期性任務(wù)集，可被調(diào)度的充分必要條件為：

式（3）中，U（n）為處理器利用率。即當(dāng)處理器利用率小于100%時(shí)，EDF算法可調(diào)度任何任務(wù)集。由式（1）、（2）可知，RM算法只能在利用率小于69%的情況下進(jìn)行工作，這也進(jìn)一步證明了動(dòng)態(tài)調(diào)度算法的優(yōu)越性。

由于該算法需要每時(shí)每刻都進(jìn)行任務(wù)相對截止期的計(jì)算以進(jìn)行優(yōu)先級的分配，尤其是當(dāng)有多個(gè)任務(wù)的截止期相對接近時(shí)，每隔較短的時(shí)間都會(huì)出現(xiàn)優(yōu)先級更替的情況，所以會(huì)占用較多的網(wǎng)絡(luò)資源，在網(wǎng)絡(luò)負(fù)載較大時(shí)，系統(tǒng)的控制性能勢必會(huì)發(fā)生斷崖式下跌，這也是動(dòng)態(tài)調(diào)度算法的通病。

1.2.2 MTS算法

固定優(yōu)先級調(diào)度面對周期性消息時(shí)擁有的高實(shí)時(shí)性的優(yōu)點(diǎn)與復(fù)雜環(huán)境下低效率的缺點(diǎn)，動(dòng)態(tài)優(yōu)先級調(diào)度有穩(wěn)定、效率高的優(yōu)點(diǎn)，而負(fù)載過大時(shí)傳輸效率低下的缺點(diǎn)，為了更好地?fù)P長避短，充分利用二者的特點(diǎn)，研究人員不斷地嘗試混合調(diào)度算法的可能性。Zuberi等人[11]研究出了 MTS（Mixed Traffic Scheduler）分級調(diào)度機(jī)制，并在CAN總線中予以實(shí)踐，其基于動(dòng)態(tài)調(diào)度算法EDF的靈活性來對實(shí)時(shí)性數(shù)據(jù)進(jìn)行調(diào)度，以保持消息傳輸?shù)膶?shí)時(shí)性；基于靜態(tài)調(diào)度算法DM的截止期單調(diào)性對非實(shí)時(shí)性數(shù)據(jù)進(jìn)行調(diào)度，以保證這些數(shù)據(jù)的傳輸均在截止期之前完成。如圖3所示是一種MTS算法的控制策略。

圖3 MTS算法控制策略

采用這種方式，可以有效地防止EDF算法工作時(shí)的高開銷，同時(shí)面對復(fù)雜環(huán)境時(shí)也可以避免DM算法可能造成的沖突等問題。呂偉杰等[12]同樣希望同時(shí)利用二者的優(yōu)點(diǎn)，提出利用EDF調(diào)度硬實(shí)時(shí)消息，利用RM調(diào)度軟實(shí)時(shí)和非實(shí)時(shí)消息，實(shí)驗(yàn)表明，可以有效提高網(wǎng)絡(luò)利用率，減少消息傳輸?shù)难訒r(shí)。

2 基于公平性

2.1 PE與DS算法

FTT-CAN、EDF等算法的優(yōu)越性在于極高的實(shí)時(shí)性，可以極大程度上減少消息的抖動(dòng)，但由于對周期性消息過于重視，難免會(huì)對非周期消息的公平性造成影響。為了解決此問題，Lehoczky等人[13]提出了DS（deferrable server，可延期服務(wù)器）算法和 PE（priority exchange，優(yōu)先權(quán)交換）算法，這兩個(gè)算法的核心思想比較相似，都是設(shè)置一個(gè)專用的優(yōu)先級較高的周期性任務(wù)，這一任務(wù)專門用來供非周期性任務(wù)使用，若執(zhí)行到設(shè)置的這一周期性任務(wù)時(shí)剛好不存在排隊(duì)等待的非周期性任務(wù)，系統(tǒng)就會(huì)按照設(shè)定好的方法為非周期性任務(wù)保留一定的帶寬資源，隨時(shí)應(yīng)對可能存在的待處理任務(wù)[14]。系統(tǒng)所需要操作的這些設(shè)定好的方法就是PE算法與DS算法的區(qū)別。

2.2 SS類算法

經(jīng)過深入研究，Sprunt[15]在這兩種算法的基礎(chǔ)上提出了SS（sporadic server不定時(shí)服務(wù)器）方法，這是一種更完善的服務(wù)方式。SS可以稱作PE算法和DS算法的升級版，主要體現(xiàn)在兩點(diǎn)上：PE算法的缺陷在于，需要維護(hù)每一個(gè)優(yōu)先級的工作時(shí)長，這樣就造成了大量的工作負(fù)載；DS算法的缺陷在于，其工作時(shí)長的補(bǔ)充與實(shí)際工作時(shí)長無關(guān)，因此難免出現(xiàn)額外的時(shí)長補(bǔ)充，這樣會(huì)造成處理器利用率的浪費(fèi)，且造成網(wǎng)絡(luò)資源的浪費(fèi)與信息傳輸?shù)难訒r(shí)[16]。

SS算法補(bǔ)償非周期性消息的工作時(shí)長的方法的流程圖如圖4所示：將實(shí)時(shí)工作的任務(wù)的優(yōu)先級設(shè)為Ps，將系統(tǒng)中的各個(gè)優(yōu)先級設(shè)為Pi（i=1，2，…），且Pi＞Pj，當(dāng)且僅當(dāng)i＞j；將是否補(bǔ)充工作時(shí)長的狀態(tài)定義為ON與OFF，將PS與Pi的優(yōu)先級層次進(jìn)行比較，若PS≥Pi，則Pi的狀態(tài)為ON，否則為OFF。在服務(wù)器中，若存在空余的工作時(shí)長，則將在優(yōu)先級Pi的狀態(tài)為ON時(shí)開始計(jì)算補(bǔ)充的工作時(shí)長并添加；若不存在空余的工作時(shí)長，則需等待至服務(wù)器有空余時(shí)長時(shí)，且Pi的狀態(tài)為ON時(shí)，才可以開始計(jì)算補(bǔ)充時(shí)長[17]。

圖4 SS算法流程圖

上述方法都是在RM算法等固定優(yōu)先級算法的基礎(chǔ)上研究的，都可以被歸為固定優(yōu)先級服務(wù)器算法。固定優(yōu)先級算法對網(wǎng)絡(luò)資源利用率較低這一缺陷比較明顯，為了解決這一問題，Ghazalie與Baker[18]開始研究在EDF算法基礎(chǔ)上的更好地針對公平性的方法，并提出了SS算法的動(dòng)態(tài)調(diào)度版本，并將其命名為（deadline sporadic server，截止期不定時(shí)服務(wù)器，DSS算法）。這一算法的核心思想與SS算法相同，不同之處在于DSS算法可以通過計(jì)算截止期及時(shí)為服務(wù)器調(diào)整優(yōu)先級，但顯而易見，及時(shí)更新優(yōu)先級需要系統(tǒng)保持極高的計(jì)算量，實(shí)現(xiàn)較為復(fù)雜且易造成較大負(fù)載。

2.3 TBS類算法

可以看出，不論是DS、PE算法還是SS類算法，若服務(wù)器本身的周期就較久，則非周期性任務(wù)被延遲的可能還是很大。除了為非周期性消息分配較短的周期外，有學(xué)者提出了TBS算法，這種算法的核心思想是縮短非周期性消息的截止期，并為其限定一個(gè)較合適的處理器利用率，規(guī)定截止期的分配不會(huì)使處理器利用率超標(biāo)[19]。由于系統(tǒng)始終保持在合理的負(fù)載，因此開銷極小甚至可忽略。除此之外，Lipari等利用TBS+EDF混合調(diào)度算法來完成混合任務(wù)的工作；Caccamo等提出了可調(diào)的TB*算法，進(jìn)一步提高了算法的性能與穩(wěn)定性。

3 算法性能分析

由表1可知，RM算法的優(yōu)點(diǎn)是在截止期與任務(wù)的周期相同時(shí)可以獲得最高的實(shí)時(shí)性與工作效率。但它可能會(huì)造成無法調(diào)度的情況，影響了適用情況與控制性能。DM算法具有比RM算法更優(yōu)越的工作條件，不論任務(wù)周期與相對截止期關(guān)系如何，都可以達(dá)到最優(yōu)的調(diào)度效果，在同類的靜態(tài)調(diào)度算法中，DM算法的優(yōu)勢明顯。值得一提的是，DM與RM算法雖簡單且易實(shí)現(xiàn)，但由于只依靠一種因素分配優(yōu)先級，所以無法綜合比較整個(gè)控制系統(tǒng)的性能。TTCAN最適合傳輸?shù)南橹芷谛韵?，同時(shí)對于某些非周期性消息，可以依靠基于表的特性將其轉(zhuǎn)換為周期性的傳輸模式。但缺點(diǎn)是難以適應(yīng)復(fù)雜環(huán)境。EDF算法在處理器利用率小于100%時(shí)可調(diào)度任何任務(wù)，但負(fù)載過大時(shí)性能會(huì)出現(xiàn)暴跌。MTS算法可以有效地防止EDF算法工作時(shí)的高開銷，同時(shí)面對復(fù)雜環(huán)境時(shí)也可以避免DM算法可能造成的沖突等問題，是未來研究發(fā)展的趨勢?；诜?wù)器的算法可以更好地保證非周期性消息的公平性，主要以DS與PE算法為基礎(chǔ)，但他們都存在很明顯的缺陷，SS算法及建立在動(dòng)態(tài)調(diào)度基礎(chǔ)上的DSS算法是一種更完善的服務(wù)方式。相對于SS算法，DSS算法的優(yōu)勢在于可以及時(shí)的更新優(yōu)先級，但難免造成負(fù)載過大的問題。TBS算法可以在保持處理器利用率不超標(biāo)的前提下為非周期性任務(wù)爭取最多的工作時(shí)長，也可以與EDF算法等進(jìn)行混合使用，進(jìn)一步提高算法的性能與穩(wěn)定性，相較于SS類算法來說優(yōu)勢較大。

表1 各算法性能分析

就基于CAN總線的調(diào)度算法而言，本文主要對同類的算法或改進(jìn)后與改進(jìn)前的算法進(jìn)行了性能對比分析，且由于存在RM、DM算法等只依靠單一變量分配優(yōu)先級的算法，因此難以對這些算法的綜合性能進(jìn)行比較，進(jìn)一步的研究目標(biāo)應(yīng)對不同類別算法進(jìn)行性能比較。算法的好壞不能僅依靠某一種情況下的性能，還受到實(shí)時(shí)負(fù)載、工作中的抖動(dòng)、定期任務(wù)的截止期與周期的關(guān)系等因素的影響，如何減少這些因素造成的影響，得到較為客觀的結(jié)果，也應(yīng)是新的研究內(nèi)容。

4 總結(jié)與討論

本文綜述了在基于不同目的時(shí)可采用的調(diào)度算法及其性能特點(diǎn)，分析了不同算法的優(yōu)缺點(diǎn)及適用情況，為復(fù)雜工況下的實(shí)時(shí)系統(tǒng)設(shè)計(jì)者提供了選擇的思路。CAN總線作為世界上應(yīng)用最為廣泛的總線之一，應(yīng)用情況數(shù)不勝數(shù)，除實(shí)時(shí)性及公平性要求之外，設(shè)計(jì)者還可能存在調(diào)度性能要求、網(wǎng)絡(luò)資源利用率要求等等。對于如何利用CAN總線調(diào)度算法完善的解決各種實(shí)際問題，兼顧各方面要求，還有待進(jìn)一步研究。