CAN總線調度算法研究

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

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

0 引言

CAN總線是當今世界中最為廣泛使用的現場總線之一，每時每刻都有無數消息通過CAN總線進行傳輸，在CAN總線中傳輸的消息主要按其截止時間來分類，具體包括必須嚴格按照截止期進行傳輸的硬實時消息、在截止期附近可適當彈性傳輸的軟實時消息以及沒有嚴格時間要求的非實時消息[1]。硬實時消息一般為實時系統中的各種緊急消息（如錯誤信息、警告信息），對傳輸時間的要求極高；軟實時消息一般是在系統內循環發送的消息，對傳輸時間的要求不太敏感，但不可長期大量超時，否則會引起系統報警，升級為硬實時消息；非實時消息一般為系統內部的檢測信息、組態信息等，非實時消息的數據量較大，若即時發送會嚴重堵塞傳輸網絡，因此對時間的要求較為寬松。CAN總線調度是指在系統的控制下，將需要傳輸的消息按照一定的次序及時間間隔有序的進行發送分配。在實時系統中，網絡帶寬資源是有限的，那么如何妥善使用有限的帶寬資源，獲得最大的使用效益，完成系統內部消息的有序傳輸成為了調度的主要目標[2]，以及接近截止期的消息如何按時發送、如何有序的安排周期性消息在無數非周期性消息中發送、如何保證實時性消息與非實時消息在發送時的公平性等[3]，也是目前CAN總線調度尚需解決的問題。

1 實時性

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

1.1 靜態調度算法

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

1.1.1 速率單調算法

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

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

其中：n為周期性任務的數量；Ci為任務i的執行時間；Ti為任務i的周期。

當n→∞時，

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

1.1.2 截止期單調算法

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

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

圖1 時間觸發傳送原理圖

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

圖2 TTCAN協議工作周期

TT-CAN最適合傳輸的消息為周期性消息，同時對于某些非周期性消息，可以依靠基于表的特性將其轉換為周期性的傳輸模式[9]。TT-CAN算法擁有著一定的可預測性但具有靜態調度算法的通病，一旦消息本身的時間特性出現某些改動，那么整個分配表都需要重新調整。

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

1.2 動態調度算法

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

1.2.1 EDF算法

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

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

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

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

1.2.2 MTS算法

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

圖3 MTS算法控制策略

采用這種方式，可以有效地防止EDF算法工作時的高開銷，同時面對復雜環境時也可以避免DM算法可能造成的沖突等問題。呂偉杰等[12]同樣希望同時利用二者的優點，提出利用EDF調度硬實時消息，利用RM調度軟實時和非實時消息，實驗表明，可以有效提高網絡利用率，減少消息傳輸的延時。

2 基于公平性

2.1 PE與DS算法

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

2.2 SS類算法

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

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

圖4 SS算法流程圖

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

2.3 TBS類算法

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

3 算法性能分析

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

表1 各算法性能分析

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

4 總結與討論

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