避免饑餓的CAN 總線高優(yōu)先級(jí)反轉(zhuǎn)算法

趙國(guó)承，張鳳登

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

0 引言

控制器局域網(wǎng)絡(luò)（Controller Area Network，CAN）總線是用于連接電子控制單元（Electronic Control Unit，ECU）的多主機(jī)廣播串行總線標(biāo)準(zhǔn)，CAN 總線上每個(gè)節(jié)點(diǎn)都能夠發(fā)送和接收?qǐng)?bào)文，但不能同時(shí)發(fā)送和接收?qǐng)?bào)文［1］。在CAN 總線中，任何具有高優(yōu)先級(jí)的報(bào)文要在短時(shí)間內(nèi)高頻率占用總線，都有可能造成低優(yōu)先級(jí)報(bào)文饑餓［2］。

解決CAN 總線中低優(yōu)先級(jí)報(bào)文饑餓問(wèn)題的研究較多。Murtaza 等［3］提出在CAN 總線上增加一個(gè)主節(jié)點(diǎn)，以防止其他低優(yōu)先級(jí)節(jié)點(diǎn)出現(xiàn)阻塞問(wèn)題。主節(jié)點(diǎn)必須嘗試檢測(cè)饑餓節(jié)點(diǎn)，并確保饑餓節(jié)點(diǎn)保持參與通信。主節(jié)點(diǎn)始終監(jiān)視CAN 網(wǎng)絡(luò)，并在收到來(lái)自所有節(jié)點(diǎn)的報(bào)文時(shí)保持沉默。如果主節(jié)點(diǎn)發(fā)現(xiàn)來(lái)自某些節(jié)點(diǎn)的報(bào)文沒(méi)有參與通信，則該主節(jié)點(diǎn)將變?yōu)榛顒?dòng)狀態(tài)，這確保了來(lái)自這些節(jié)點(diǎn)的報(bào)文可以在下一輪仲裁中訪問(wèn)以進(jìn)行廣播。雖然該方案可以防止啟動(dòng)問(wèn)題，但由于需要額外的節(jié)點(diǎn)支持，因此該方案需要更高的負(fù)擔(dān)。文獻(xiàn)［4］提出基于使用優(yōu)先級(jí)和先入先出FIFO（First Input First Output）隊(duì)列的CAN 總線報(bào)文調(diào)度方法，但其只關(guān)注了可行調(diào)度表的生成，卻因此忽略了CAN總線中存在的饑餓問(wèn)題。文獻(xiàn)［5］開(kāi)發(fā)了一種無(wú)饑餓模型，當(dāng)存在任務(wù)發(fā)送失敗的次數(shù)大于設(shè)置的閾值時(shí)，會(huì)使用優(yōu)先級(jí)反轉(zhuǎn)將該任務(wù)反轉(zhuǎn)為最高優(yōu)先級(jí)。文獻(xiàn)［6］提出了一種新的無(wú)饑餓CAN 總線仲裁模型，其特點(diǎn)是利用報(bào)文標(biāo)識(shí)符的最高兩位動(dòng)態(tài)反轉(zhuǎn)實(shí)現(xiàn)優(yōu)先級(jí)上升。Kimm 等［7］提出一種避免饑餓的CAN 總線調(diào)度方案，通過(guò)將每輪仲裁中發(fā)送失敗的報(bào)文優(yōu)先級(jí)反轉(zhuǎn)為更高的優(yōu)先級(jí)來(lái)避免饑餓問(wèn)題。

以上研究注重將優(yōu)先級(jí)低的任務(wù)在CAN 總線仲裁中動(dòng)態(tài)變?yōu)楦邇?yōu)先級(jí)任務(wù)，但這種方法存在弊端，當(dāng)CAN 總線存在非常緊急的報(bào)文需要立刻發(fā)送時(shí)，很有可能得不到及時(shí)發(fā)送。本文更多地考慮將優(yōu)先級(jí)高的任務(wù)在一定條件下進(jìn)行優(yōu)先級(jí)反轉(zhuǎn)，動(dòng)態(tài)降低其優(yōu)先級(jí)，因此不會(huì)出現(xiàn)CAN 總線不能立刻發(fā)送非常緊急的報(bào)文問(wèn)題，而且能有效避免CAN 總線固定優(yōu)先級(jí)調(diào)度造成的饑餓問(wèn)題。

1 CAN 總線幀格式和仲裁方式

自從德國(guó)Bosch 公司在汽車工程師協(xié)會(huì)（Society of Automotive Engineers，SAE）大會(huì)上引入串行總線系統(tǒng)以來(lái)，CAN 總線已經(jīng)逐漸成為最成功的數(shù)據(jù)通信協(xié)議之一［8］。CAN 總線采用載波監(jiān)聽(tīng)多路訪問(wèn)/沖突避免（Carrier Sense Multiple Access with Collision Avoid，CSMA/CA）協(xié) 議［9-10］，所以CAN 總線的訪問(wèn)是無(wú)沖突、按位仲裁的［11］。無(wú)沖突意味著總是更高優(yōu)先級(jí)的報(bào)文在仲裁中獲勝并發(fā)送，且在發(fā)送過(guò)程中禁止其它報(bào)文發(fā)送。按位仲裁可以理解為，如果有兩個(gè)或多個(gè)節(jié)點(diǎn)同時(shí)進(jìn)行傳輸，且有顯性位和隱形位同時(shí)發(fā)送，這時(shí)規(guī)定顯性位的權(quán)重大于隱形位，故顯性位可以覆蓋隱形位。

在CAN 總線中有數(shù)據(jù)幀、遠(yuǎn)程幀、錯(cuò)誤幀和過(guò)載幀4 種不同的幀［12］，其中數(shù)據(jù)幀能夠?qū)?shù)據(jù)從發(fā)生端廣播至接收端，數(shù)據(jù)幀格式如圖1 所示，攜帶有標(biāo)識(shí)符的遠(yuǎn)程幀用來(lái)請(qǐng)求另一節(jié)點(diǎn)發(fā)送具有相同標(biāo)識(shí)符的數(shù)據(jù)幀；錯(cuò)誤幀發(fā)送總線中出現(xiàn)錯(cuò)誤的指示；當(dāng)數(shù)據(jù)幀與相鄰的一個(gè)數(shù)據(jù)幀或遠(yuǎn)程幀之間出現(xiàn)額外延遲時(shí)，過(guò)載幀將被發(fā)送。在CAN 總線空閑時(shí)，CAN 總線上任何一個(gè)節(jié)點(diǎn)都能在CAN 總線上發(fā)送報(bào)文，無(wú)需獲得總線上其他節(jié)點(diǎn)許可［13］。

Fig.1 Data frame format圖1 數(shù)據(jù)幀格式

數(shù)據(jù)幀分為標(biāo)準(zhǔn)格式和擴(kuò)展格式兩種。其中標(biāo)準(zhǔn)格式的標(biāo)識(shí)符長(zhǎng)度為11 位，擴(kuò)展格式標(biāo)識(shí)符有29 位［14］。本文對(duì)標(biāo)準(zhǔn)格式進(jìn)行論述，對(duì)數(shù)據(jù)幀中仲裁場(chǎng)的標(biāo)識(shí)符進(jìn)行分析。

當(dāng)CAN 總線上有多個(gè)節(jié)點(diǎn)同時(shí)發(fā)送時(shí)，通過(guò)對(duì)總線進(jìn)行監(jiān)控，可以確定每個(gè)節(jié)點(diǎn)當(dāng)前正在傳輸?shù)膱?bào)文優(yōu)先級(jí)高低。若在仲裁中某一節(jié)點(diǎn)勝出，那么該節(jié)點(diǎn)繼續(xù)傳輸其報(bào)文的剩余部分，此時(shí)仲裁失敗的節(jié)點(diǎn)均退出并繼續(xù)等待下一次仲裁開(kāi)始［15-17］。同時(shí)，因?yàn)镃AN 總線沒(méi)有全局時(shí)鐘，所以節(jié)點(diǎn)需要在每次報(bào)文傳輸時(shí)重新同步，并且每個(gè)節(jié)點(diǎn)必須與首先開(kāi)始傳輸?shù)墓?jié)點(diǎn)同步，以便總線仲裁能夠正常工作［18-19］。

2 反轉(zhuǎn)算法設(shè)計(jì)

2.1 算法思路

本算法中11 位報(bào)文標(biāo)識(shí)符設(shè)計(jì)為1 位動(dòng)態(tài)反轉(zhuǎn)標(biāo)識(shí)位、1 位級(jí)別位和9 位靜態(tài)位3 部分，如圖2 報(bào)文標(biāo)識(shí)符ID劃分所示。當(dāng)然這僅僅是在標(biāo)準(zhǔn)格式中的劃分，除此之外還可根據(jù)需要應(yīng)用在擴(kuò)展格式中。靜態(tài)標(biāo)識(shí)位（ID0-ID8）從優(yōu)先級(jí)最低的111111111 開(kāi)始，以最高優(yōu)先級(jí)的0 位000000000 結(jié)束。級(jí)別標(biāo)識(shí)位ID9用來(lái)區(qū)分高優(yōu)先級(jí)組和低優(yōu)先級(jí)組，其中高優(yōu)先級(jí)組的級(jí)別標(biāo)識(shí)位為0，低優(yōu)先級(jí)組的級(jí)別標(biāo)識(shí)位為1，動(dòng)態(tài)反轉(zhuǎn)標(biāo)識(shí)位ID10默認(rèn)為0 未反轉(zhuǎn)，當(dāng)高優(yōu)先級(jí)組存在報(bào)文滿足反轉(zhuǎn)條件時(shí)會(huì)動(dòng)態(tài)反轉(zhuǎn)為1。

Fig.2 Message identifier ID partition圖2 報(bào)文標(biāo)識(shí)符ID 劃分

CAN 總線上發(fā)送的報(bào)文由節(jié)點(diǎn)生成，為不同的報(bào)文分配優(yōu)先級(jí)時(shí)，這些報(bào)文的優(yōu)先級(jí)將伴隨著報(bào)文同樣保存在節(jié)點(diǎn)中。由于報(bào)文發(fā)送基于固定優(yōu)先級(jí)的CAN 總線調(diào)度，因此，當(dāng)CAN 總線上的節(jié)點(diǎn)發(fā)送報(bào)文時(shí)，該報(bào)文所獲得的優(yōu)先級(jí)會(huì)一直固定不變，而且每一個(gè)報(bào)文的優(yōu)先級(jí)都是獨(dú)一無(wú)二的，不能出現(xiàn)重復(fù)的優(yōu)先級(jí)，否則很有可能造成死鎖。

本文選擇非搶占式的單調(diào)速率（Rate Monotonic，RM）算法進(jìn)行報(bào)文優(yōu)先級(jí)分配。選擇非搶占式的RM 算法調(diào)度原因如下：①如圖3 所示，非搶占式調(diào)度方法可以確保一旦發(fā)送某一報(bào)文就能夠一直發(fā)送直到發(fā)送完畢，在此期間不能被其它高優(yōu)先級(jí)報(bào)文打斷，發(fā)送過(guò)程中上下文切換開(kāi)銷忽略不計(jì)；②RM 算法是根據(jù)報(bào)文的周期來(lái)分配優(yōu)先級(jí)，其特點(diǎn)是報(bào)文發(fā)送的周期越短優(yōu)先級(jí)越高［20］，反之報(bào)文的發(fā)送周期越長(zhǎng)優(yōu)先級(jí)越低，要求在報(bào)文開(kāi)始發(fā)送之前便分配完畢且運(yùn)行過(guò)程中始終固定。

Fig.3 Non-preemptive scheduling圖3 非搶占式調(diào)度

算法實(shí)現(xiàn)如下：在CAN 總線中，當(dāng)高優(yōu)先級(jí)組在一定時(shí)間內(nèi)出現(xiàn)某一報(bào)文發(fā)送的次數(shù)大于設(shè)置的固定值時(shí)，則在下一次繼續(xù)參與CAN 總線仲裁之前將其動(dòng)態(tài)反轉(zhuǎn)到標(biāo)識(shí)位ID10，進(jìn)行反轉(zhuǎn)由0 變?yōu)?，從而使其比低優(yōu)先級(jí)組里的報(bào)文優(yōu)先級(jí)還低，此時(shí)處于饑餓中的報(bào)文得到機(jī)會(huì)發(fā)送，實(shí)現(xiàn)避免饑餓目的；當(dāng)其動(dòng)態(tài)反轉(zhuǎn)標(biāo)識(shí)位變?yōu)? 時(shí)，并不意味其喪失繼續(xù)參與本次CAN 總線仲裁的資格，而是進(jìn)一步判斷當(dāng)前CAN 總線是否處于空閑狀態(tài)。如果總線空閑，則該反轉(zhuǎn)后的報(bào)文正常發(fā)送，否則不會(huì)發(fā)送，這樣可以避免當(dāng)總線擁擠時(shí)，反轉(zhuǎn)后發(fā)送的高優(yōu)先級(jí)報(bào)文經(jīng)過(guò)多次仲裁都不能占用總線的問(wèn)題，避免報(bào)文發(fā)送的順序錯(cuò)亂；最后，不管本次是否發(fā)送成功，都會(huì)在下一次參與CAN 總線仲裁之前將其動(dòng)態(tài)反轉(zhuǎn)標(biāo)識(shí)位變?yōu)?，重新恢復(fù)其高優(yōu)先級(jí)。有了1 位動(dòng)態(tài)反轉(zhuǎn)標(biāo)識(shí)位，任何具有高優(yōu)先級(jí)的報(bào)文在短時(shí)間內(nèi)高頻率占用總線一定次數(shù)后都會(huì)被中斷。本文使用的11 位ID 動(dòng)態(tài)反轉(zhuǎn)標(biāo)識(shí)位開(kāi)始均為0，級(jí)別標(biāo)識(shí)位可在0與1之間進(jìn)行劃分，靜態(tài)標(biāo)識(shí)位內(nèi)數(shù)字可任意選取。

2.2 任務(wù)模型

模型如圖4 所示。在本模型中，設(shè)被調(diào)度的報(bào)文組為｛M1，M2，…，Mn｝，Mi是其中的一個(gè)報(bào)文，i=1，2，…n。避免饑餓的高優(yōu)先級(jí)反轉(zhuǎn)模型主要由2 個(gè)參數(shù)Ttc和TMax決定，其中Ttc代表檢測(cè)報(bào)文發(fā)送次數(shù)的時(shí)間，TMax代表在Ttc時(shí)間內(nèi)發(fā)送報(bào)文的次數(shù)。同時(shí)進(jìn)行如下定義：

Fig.4 High priority inversion model to avoid starvation圖4 避免饑餓的高優(yōu)先級(jí)反轉(zhuǎn)模型

定義1報(bào)文Mi的傳輸周期等于其截止時(shí)間

其中，Pi為報(bào)文Mi傳輸周期，Di為報(bào)文Mi截止時(shí)間。

定義2CAN 總線利用率U定義為：

其中，K為報(bào)文Mi執(zhí)行時(shí)間，P為報(bào)文Mi傳輸周期，i=1，2，…n。

定義3報(bào)文Mi的響應(yīng)時(shí)間T定義為：

其中，t1為報(bào)文Mi的激活時(shí)間，t2為報(bào)文Mi的發(fā)送完成時(shí)間。

其中，n為報(bào)文數(shù)量，i=1，2，…n。

定義4到達(dá)率S定義為：

其中，R指單位時(shí)間內(nèi)實(shí)際發(fā)送報(bào)文的數(shù)量，C為預(yù)計(jì)發(fā)送報(bào)文的數(shù)量。

本算法實(shí)現(xiàn)檢測(cè)報(bào)文發(fā)送次數(shù)并防止遺漏、到達(dá)規(guī)定次數(shù)以后進(jìn)行反轉(zhuǎn)，以及未反轉(zhuǎn)報(bào)文的發(fā)送功能。算法部分代碼如下：

3 實(shí)驗(yàn)仿真

本文使用Vector CANoe 平臺(tái)實(shí)現(xiàn)避免饑餓的高優(yōu)先級(jí)反轉(zhuǎn)算法。CANoe 是一種軟件開(kāi)發(fā)和測(cè)試工具，主要用于通信網(wǎng)絡(luò)和ECU的開(kāi)發(fā)、分析、仿真、測(cè)試、診斷和啟動(dòng)，編程語(yǔ)言CAPL 用于編寫(xiě)測(cè)試腳本和仿真模型［21］。實(shí)驗(yàn)開(kāi)始所有報(bào)文均在0 時(shí)刻釋放，本文設(shè)置兩組周期報(bào)文隊(duì)列，分別為高優(yōu)先級(jí)組和低優(yōu)先級(jí)組，兩組報(bào)文的截止日期均等于報(bào)文的發(fā)送周期，實(shí)驗(yàn)將每組設(shè)置為2 個(gè)報(bào)文。

其中高優(yōu)先級(jí)組的兩個(gè)報(bào)文為M1和M2，低優(yōu)先級(jí)組的兩個(gè)報(bào)文為M3和M4，高優(yōu)先級(jí)組得到報(bào)文優(yōu)先級(jí)遠(yuǎn)遠(yuǎn)大于低優(yōu)先級(jí)組。為了進(jìn)一步驗(yàn)證避免饑餓的高優(yōu)先級(jí)反轉(zhuǎn)模型與正常固定優(yōu)先級(jí)的優(yōu)勢(shì)，實(shí)驗(yàn)分別進(jìn)行CAN 總線正常工作、CAN 總線滿利用率工作、CAN 總線產(chǎn)生饑餓以及將報(bào)文數(shù)量擴(kuò)大仿真。

3.1 CAN 總線正常工作

設(shè)報(bào)文M1的發(fā)送周期為2ms，優(yōu)先級(jí)設(shè)置為0x01，報(bào)文M2的發(fā)送周期為4ms，優(yōu)先級(jí)設(shè)置為0x02，報(bào)文M3的發(fā)送周期為8ms，優(yōu)先級(jí)設(shè)置為0x201，報(bào)文M4的發(fā)送周期為12ms，優(yōu)先級(jí)設(shè)置為0x202。規(guī)定兩組報(bào)文的執(zhí)行時(shí)間K均設(shè)置為1ms，檢測(cè)時(shí)間Ttc設(shè)置為8ms，檢測(cè)報(bào)文發(fā)送次數(shù)TMax設(shè)置為3。如圖5 所示，通過(guò)對(duì)比未進(jìn)行反轉(zhuǎn)的固定優(yōu)先級(jí)調(diào)度和有反轉(zhuǎn)的非搶占式RM 算法調(diào)度在CAN 總線的發(fā)送隊(duì)列可知，未進(jìn)行反轉(zhuǎn)的固定優(yōu)先級(jí)調(diào)度和有反轉(zhuǎn)的非搶占式RM 算法調(diào)度雖然均能將報(bào)文正常發(fā)送，但是使用了反轉(zhuǎn)的非搶占式RM 算法調(diào)度能夠較好地降低低優(yōu)先級(jí)組報(bào)文的響應(yīng)時(shí)間T，例如報(bào)文M4。其中反轉(zhuǎn)報(bào)文----M1是報(bào)文M1的反轉(zhuǎn)，根據(jù)避免饑餓的高優(yōu)先級(jí)反轉(zhuǎn)模型可知，其優(yōu)先級(jí)反轉(zhuǎn)為0×401，遠(yuǎn)遠(yuǎn)小于低優(yōu)先級(jí)組的兩個(gè)報(bào)文的優(yōu)先級(jí)，因此反轉(zhuǎn)后報(bào)文M4可以在反轉(zhuǎn)報(bào)文----M1的前面執(zhí)行。此時(shí)CAN 總線上的報(bào)文均得到機(jī)會(huì)發(fā)送，故低優(yōu)先級(jí)組的到達(dá)率S 始終為1。

3.2 CAN 總線滿利用率工作

除了將報(bào)文M3的發(fā)送周期設(shè)置為6ms 以外，其它所有實(shí)驗(yàn)參數(shù)均與CAN 總線正常工作時(shí)一樣。通過(guò)觀察圖6 可知，未進(jìn)行反轉(zhuǎn)的固定優(yōu)先級(jí)調(diào)度恰好能夠?qū)⑺袌?bào)文在其周期內(nèi)發(fā)送，而此時(shí)有反轉(zhuǎn)的非搶占式RM 算法調(diào)度則很明顯地降低了低優(yōu)先級(jí)組報(bào)文的響應(yīng)時(shí)間T，此時(shí)CAN總線上的報(bào)文恰好均能發(fā)送，故低優(yōu)先級(jí)組的到達(dá)率S 始終為1。

3.3 CAN 總線產(chǎn)生饑餓

將高優(yōu)先級(jí)組報(bào)文M2的發(fā)送周期改為3ms，低優(yōu)先級(jí)組報(bào)文M3的發(fā)送周期為改6ms，其它所有實(shí)驗(yàn)參數(shù)均與CAN 總線正常工作時(shí)一樣。如圖7 所示，未進(jìn)行反轉(zhuǎn)的固定優(yōu)先級(jí)調(diào)度在實(shí)驗(yàn)中產(chǎn)生饑餓，導(dǎo)致低優(yōu)先級(jí)組報(bào)文M4一直沒(méi)有占用總線的機(jī)會(huì)，一直處于饑餓當(dāng)中，故低優(yōu)先級(jí)組報(bào)文的到達(dá)率S 小于1。而此時(shí)有反轉(zhuǎn)的非搶占式RM算法調(diào)度能夠避免CAN 總線中低優(yōu)先級(jí)報(bào)文產(chǎn)生饑餓問(wèn)題，使得兩組報(bào)文在其周期內(nèi)均能得到占用總線的機(jī)會(huì)。此時(shí)低優(yōu)先級(jí)組報(bào)文的響應(yīng)時(shí)間T 得到明顯降低，低優(yōu)先級(jí)組的到達(dá)率S 仍保持為1。

Fig.5 Reverse transmission queue situation when CAN bus works normally圖5 CAN 總線正常工作時(shí)有無(wú)反轉(zhuǎn)發(fā)送隊(duì)列情況

Fig.6 Reverse transmission queue situation when CAN bus works at full utilization圖6 CAN 總線滿利用率工作時(shí)有無(wú)反轉(zhuǎn)發(fā)送隊(duì)列情況

Fig.7 Reverse transmission queue situation when CAN is in starvation圖7 CAN 產(chǎn)生饑餓時(shí)有無(wú)反轉(zhuǎn)發(fā)送隊(duì)列情況

3.4 擴(kuò)大仿真

為進(jìn)一步驗(yàn)證避免饑餓的高優(yōu)先級(jí)反轉(zhuǎn)模型與正常固定優(yōu)先級(jí)的優(yōu)勢(shì)，將實(shí)驗(yàn)中的報(bào)文數(shù)量擴(kuò)大，設(shè)置報(bào)文數(shù)量n 為20，每組報(bào)文數(shù)量設(shè)置為10，仿真時(shí)間為1s，對(duì)比低優(yōu)先級(jí)組在未進(jìn)行反轉(zhuǎn)的固定優(yōu)先級(jí)調(diào)度和有反轉(zhuǎn)的非搶占式RM 算法調(diào)度下的到達(dá)率和平均響應(yīng)時(shí)間。

平均響應(yīng)時(shí)間如圖8 所示，分別驗(yàn)證在不同CAN 總線利用率下有反轉(zhuǎn)的非搶占式RM 算法調(diào)度和無(wú)反轉(zhuǎn)的CAN總線固定優(yōu)先級(jí)調(diào)度對(duì)低優(yōu)先級(jí)組平均響應(yīng)時(shí)間的影響。當(dāng)CAN 總線利用率逐漸增加時(shí)，不管低優(yōu)先級(jí)組處于未進(jìn)行反轉(zhuǎn)的固定優(yōu)先級(jí)調(diào)度，還是有反轉(zhuǎn)的非搶占式RM 算法調(diào)度，其平均響應(yīng)時(shí)間都在不斷增加，但是有反轉(zhuǎn)的非搶占式RM 算法調(diào)度的平均響應(yīng)時(shí)間總是小于未反轉(zhuǎn)的CAN 總線正常調(diào)度的平均響應(yīng)時(shí)間。

到達(dá)率實(shí)驗(yàn)如圖9 所示，對(duì)CAN 總線由正常到產(chǎn)生饑餓、有反轉(zhuǎn)的非搶占式RM 算法調(diào)度和無(wú)反轉(zhuǎn)的CAN 總線固定優(yōu)先級(jí)調(diào)度對(duì)低優(yōu)先級(jí)組到達(dá)率的影響進(jìn)行分析。若CAN 總線利用率小于等于100 時(shí)，有無(wú)反轉(zhuǎn)對(duì)低優(yōu)先級(jí)組的到達(dá)率無(wú)顯著影響；當(dāng)CAN 總線利用率大于100 時(shí)，CAN 總線存在處于饑餓狀態(tài)報(bào)文。當(dāng)CAN 總線利用率逐漸增加時(shí)，無(wú)反轉(zhuǎn)的CAN 總線固定優(yōu)先級(jí)調(diào)度下的低優(yōu)先級(jí)組到達(dá)率持續(xù)減少，直到為0，此時(shí)低優(yōu)先級(jí)組中沒(méi)有一個(gè)報(bào)文能夠再占用CAN 總線。與之相反，在有反轉(zhuǎn)的非搶占式RM 算法調(diào)度下的低優(yōu)先級(jí)組到達(dá)率則基本維持不變。

Fig.8 Average response time of low priority group with or without inversion圖8 低優(yōu)先級(jí)組有無(wú)反轉(zhuǎn)的平均響應(yīng)時(shí)間

Fig.9 Arrival rate of low priority group with or without inversion圖9 低優(yōu)先級(jí)組有無(wú)反轉(zhuǎn)的到達(dá)率情況

4 結(jié)語(yǔ)

針對(duì)CAN 總線存在的饑餓問(wèn)題，本文提出一個(gè)避免饑餓的高優(yōu)先級(jí)反轉(zhuǎn)算法并建立模型。在滿足優(yōu)先級(jí)反轉(zhuǎn)條件下使高優(yōu)先級(jí)反轉(zhuǎn)為低優(yōu)先級(jí)。仿真實(shí)驗(yàn)結(jié)果表明，在不同的CAN 總線利用率下，該模型能夠通過(guò)改善CAN 總線中周期任務(wù)的平均響應(yīng)時(shí)間來(lái)減少饑餓。當(dāng)CAN 總線利用率超過(guò)100 時(shí)，有反轉(zhuǎn)的低優(yōu)先級(jí)組到達(dá)率能夠保持正常，表明避免饑餓的高優(yōu)先級(jí)反轉(zhuǎn)算法工作良好。

避免饑餓的高優(yōu)先級(jí)反轉(zhuǎn)算法雖然有效，但高優(yōu)先級(jí)組在一定時(shí)間內(nèi)的發(fā)送次數(shù)是固定值，大于該固定值后才能進(jìn)行動(dòng)態(tài)反轉(zhuǎn)，在此期間沒(méi)有考慮低優(yōu)先級(jí)組的饑餓程度。后續(xù)可圍繞該固定值與低優(yōu)先級(jí)組饑餓程度的關(guān)系進(jìn)行研究。