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

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

0 引言

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

1 實時性

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

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

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

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

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

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

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

當n→∞時，

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

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

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

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

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

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

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

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

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

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

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

1.2.1 EDF算法

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

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

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

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

1.2.2 MTS算法

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

圖3 MTS算法控制策略

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

2 基于公平性

2.1 PE與DS算法

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

2.2 SS類算法

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

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

圖4 SS算法流程圖

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

2.3 TBS類算法

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

3 算法性能分析

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

表1 各算法性能分析

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

4 總結(jié)與討論

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