HRRF任務調(diào)度在汽車儀表中的改進與實現(xiàn)

韓琛 劉斌 謝斌 蔣崢

關(guān)鍵詞： 汽車儀表; 高響應比優(yōu)先; 任務調(diào)度; 任務優(yōu)先特性分類; 等待時間; 服務時間; 截止期錯失

中圖分類號： TN919?34; TP216+.2 ? ? ? ? ? ? ? ? ? ?文獻標識碼： A ? ? ? ? ? ? ? ? ?文章編號： 1004?373X（2019）05?0090?05

Improvement and implementation of task scheduling with high response

ratio first in automobile instrument

HAN Chen1， LIU Bin1， XIE Bin2， JIANG Zheng1

（1. MOE Engineering Research Center of Metallurgical Automation and Detecting Technology， College of Information Science and Engineering， Wuhan University of Science and Technology， Wuhan 430081， China; 2. Wuhan Baohua Display Technology Co.， Ltd.， Wuhan 430082， China）

Abstract： The foreground and background cycle mode is frequently used in the design of automotive instrument embedded system， by which the execution frequency of each system task is compulsive the same， the execution sequence can′t be changed， and each waiting time of the task fluctuates greatly， so it is difficult to guarantee the real?time performance of system task. In order to solve these problems， the task scheduling algorithm with highest response ratio first （HRRF） is optimized according to its advantages， and applied to the software design of automobile instrument. The periodic tasks are classified according to the priority characteristics. The waiting time and service time of each task are updated in real time. Considering the deadline missing of the task， the task with highest response ratio is selected in the same class for execution in every work period. The practical application result shows that the method has small scheduling overhead and high real?time performance， and is easy to maintenance and transplant.

Keywords： automobile instrument; highest response ratio first; task scheduling; task priority characteristics classification; waiting time; service time; deadline missing

0 ?引 ?言

隨著電子技術(shù)在汽車產(chǎn)品上的廣泛應用，功能越來越多樣化的嵌入式智能車載儀表受到了廣泛的關(guān)注和研究。目前，車載儀表軟件基本采用傳統(tǒng)的嵌入式前后臺循環(huán)設計開發(fā)模式。與之相比，多任務調(diào)度技術(shù)可以實現(xiàn)系統(tǒng)各任務的規(guī)律調(diào)度，提高了任務的實時性，具有調(diào)度開銷小、方便維護和移植等優(yōu)點。

多任務調(diào)度技術(shù)已經(jīng)廣泛應用于社會生活的各個領(lǐng)域[1?2]。文獻[3]在時間觸發(fā)系統(tǒng)基礎(chǔ)上，把任務分為搶占式任務和周期性任務，增加了搶占式內(nèi)核的特性，明顯提高了搶占式任務處理的實時性，并將其成功應用于智能電表中。但在該系統(tǒng)中，周期性任務的實時性沒有得到明顯改善。文獻[4]提出基于分類和多優(yōu)先級隊列的調(diào)度方案，將非實時圖形任務和通用計算任務按照優(yōu)先級在各自隊列中排隊，實時圖形任務按照截止期（周期性任務各周期內(nèi)執(zhí)行的結(jié)束時刻）排隊。該調(diào)度方法專注于提升實時圖形任務的幀率，并未對其他兩種任務的實時性以及任務的調(diào)度開銷做優(yōu)化。文獻[5]實現(xiàn)了靜態(tài)優(yōu)先級和動態(tài)優(yōu)先級調(diào)度。其中，基于靜態(tài)優(yōu)先級調(diào)度的單調(diào)速率調(diào)度（Rate Monotonic Scheduling，RMS） 算法根據(jù)任務執(zhí)行周期的長短來決定調(diào)度優(yōu)先級，為短執(zhí)行周期的任務賦予較高的優(yōu)先級，為長執(zhí)行周期的任務設定較低的優(yōu)先級。動態(tài)優(yōu)先級調(diào)度的最早截止期優(yōu)先（Earliest Deadline First，EDF）算法，根據(jù)任務的截止期動態(tài)分配任務的優(yōu)先級。截止期越近，優(yōu)先級越高。但這兩種調(diào)度算法僅考慮單一因素對任務優(yōu)先級的影響，不利于處理器更加準確地分配任務優(yōu)先級。Rehana等人在RMS和EDF基礎(chǔ)上提出了PPA（Preference Priority Assignment）算法[6]和 POFP（Preference Oriented Fixed Priority）算法[7]。這兩種算法根據(jù)任務執(zhí)行優(yōu)先順序?qū)⒅芷谛詫崟r任務分類為ASAP（As Soon As Possible）類和ALAP（As Late As Possible）類。與RMS算法相比，PPA算法支持給ASAP類任務更高的優(yōu)先級。相反，給ALAP類任務更低的優(yōu)先級。POFP算法在RMS算法和PPA算法基礎(chǔ)上，將任務分為就緒隊列和延遲隊列兩個隊列。ASAP類任務由延遲隊列觸發(fā)后，立即進入就緒隊列，系統(tǒng)將盡快的調(diào)用;而ALAP類任務在延遲隊列中觸發(fā)后，會有一個觸發(fā)時間限制，只有當ALAP類任務在延遲隊列中觸發(fā)之后，等待時間大于該任務的觸發(fā)時間時，ALAP類任務才可以進入就緒隊列，等待系統(tǒng)調(diào)用。文獻[6?7]分別對周期性實時任務的優(yōu)先級劃分和任務執(zhí)行順序給出了具體的方法，但卻未對任務的截止期做過多考慮。文獻[8]提出SEED（ASAP?Ensured Earliest Deadline）算法和POED（Preference? Oriented Earliest Deadline）算法，以容錯系統(tǒng)為應用背景，考慮任務截止期錯失問題，給出了系統(tǒng)滿載（CPU利用率100%）下的SEED算法和非滿載下的POED算法。這兩種算法過于復雜，不適用也不必用于單處理器上的任務調(diào)度。文獻[9]中的先來先服務算法（First Come First Service，F(xiàn)CFS），任務按觸發(fā)時間先后順序執(zhí)行。采用這種算法，如果先觸發(fā)的任務執(zhí)行時間過長，則后觸發(fā)的任務實時性得不到保證。而短作業(yè)優(yōu)先算法（Shortest Job First，SJF）按執(zhí)行時間長短給任務分配優(yōu)先級，執(zhí)行時間越短，優(yōu)先級越高。此算法中，如果短作業(yè)過多，則長作業(yè)等待時間可能會過長，影響調(diào)度性能。文獻[10]將高響應比優(yōu)先（Highest Response Ratio First，HRRF）調(diào)度應用于網(wǎng)絡地理信息系統(tǒng)中，縮短所有用戶并發(fā)請求的平均響應時間，解決并發(fā)訪問產(chǎn)生的響應滯后問題。該文提升了全局的負載均衡效果，但對于響應比優(yōu)先算法本身沒有明顯改進。文獻[11]針對傳感器網(wǎng)絡操作系統(tǒng)Tiny OS采用非剝奪的先來先服務調(diào)度策略，針對系統(tǒng)緊急任務不能得到及時響應及節(jié)點吞吐量下降的情況，提出一種可搶占的HRRF任務調(diào)度策略。該策略在不影響Tiny OS原有性能的基礎(chǔ)上極大改善了傳感器網(wǎng)絡承擔實時性任務的運行效率，但其也沒有考慮實時性任務截止期錯失問題。

為了提高任務的響應速度，減小平均等待時間，本文同時兼顧任務的等待時間和服務時間，結(jié)合ASAP和ALAP性質(zhì)以及截止期錯失問題，對HRRF進行改進，并將改進后的HRRF算法應用于汽車儀表軟件設計中。結(jié)果表明，相比于嵌入式前后臺循環(huán)軟件設計模式，本設計有效降低了任務的平均等待時間，各任務都能在更快的時間內(nèi)得到響應，且調(diào)度開銷小，方便維護和移植，提升了調(diào)度性能。

1 ?汽車儀表開發(fā)研究現(xiàn)狀

圖1中，KL.30是汽車電子控制單元（Electronic Control Unit，ECU）的電源供電信號;KL.15是發(fā)動機點火信號，也表示車鑰匙扭動，啟動汽車的信號。在KL.30給汽車儀表供電后，汽車儀表會根據(jù)觸發(fā)條件判斷接下來的儀表工作狀態(tài)，儀表工作狀態(tài)包括點火（Ignition，IGN）、充電（CHARGE）和STANDBY。點火和充電狀態(tài)不難理解，STANDBY表示汽車儀表處于車鑰匙關(guān)閉但仍然有CAN報文傳輸?shù)墓ぷ鳡顟B(tài)。汽車儀表進入到某工作狀態(tài)后，先進行該工作狀態(tài)的初始化，然后開始在該工作狀態(tài)下按照固定的順序重復遍歷執(zhí)行任務，直到儀表工作狀態(tài)改變。圖1中相關(guān)術(shù)語及含義見表1。

圖1中給出的儀表軟件結(jié)構(gòu)，優(yōu)點是處理起來比較簡單方便，不需考慮各任務的周期性和截止期丟失，將各任務按一定的邏輯依次放在循環(huán)中即可。但其缺點也很明顯，隨著用戶對汽車儀表要求的功能種類不斷增加，需要處理的任務量不斷上升時，該開發(fā)模式下，處理器處理相同儀表工作狀態(tài)下各任務的頻率相同，需要反復處理較多不必要的任務，導致處理器利用率較低。因此，在汽車儀表軟件設計中，使用多任務調(diào)度技術(shù)來解決上述問題是必然的發(fā)展趨勢。

2 ?任務管理

2.1 ?任務狀態(tài)

在本文設計系統(tǒng)中，儀表中的每個功能任務均具有如下四個任務狀態(tài)：

就緒（Ready）：任務周期時間開始，準備就緒，相關(guān)數(shù)據(jù)結(jié)構(gòu)已經(jīng)建立，可以隨時調(diào)度運行時的狀態(tài)。

運行 （Running）：任務處于占用CPU運行時的狀態(tài)。

掛起 （Suspend）：任務由一次運行結(jié)束到下一次就緒中間這段時間所處的狀態(tài)。

未激活 （Unactive）：任一儀表工作狀態(tài)下，如果某任務在此種儀表工作狀態(tài)下不需執(zhí)行，則該任務為此種儀表工作狀態(tài)下的未激活態(tài)。例如儀表處于充電下，不需要顯示汽車速度，此時速度顯示任務處于未激活。未激活之外的任務處于相對應儀表工作狀態(tài)下的激活（Active）。

儀表功能任務的各狀態(tài)之間切換關(guān)系如圖2所示。

其中，條件1：任務被調(diào)度;條件2：該次任務執(zhí)行結(jié)束;條件3：任務新周期到來;條件4：儀表工作狀態(tài)改變。

2.2 ?任務結(jié)構(gòu)

為方便任務管理，需要創(chuàng)建一個用于描述單個任務的數(shù)據(jù)結(jié)構(gòu)，本系統(tǒng)中，單個任務描述結(jié)構(gòu)如下：

typedef ?struct

{

uint8_t ? Type; ? ? ? //類型：根據(jù)性質(zhì)把任務分為ASAP類和ALAP類

uint16_t ?Period; ? ?//周期：任務的調(diào)度周期，即任務由一次Suspend開始到下一次Suspend開始中間的這段時間

float ? Start_Time; ? //開始時刻：任務在一個調(diào)度周期內(nèi)開始執(zhí)行的時刻，下文公式中用[Tstart]表示

float End_Time; ? ?//結(jié)束時刻：任務在一個調(diào)度周期內(nèi)結(jié)束執(zhí)行的時刻，下文公式中用[Tend]表示

float Wait_Time; ? //等待時間：任務從觸發(fā)到開始執(zhí)行的時間，下文公式中用[Twait]表示

float Service_Time; ? //服務時間：任務從開始執(zhí)行到結(jié)束執(zhí)行的時間，下文公式中用[Tservice]表示

float Response_Rate; ? //響應比：任務優(yōu)先級的衡量標準，下文公式中用RR表示

uint8_t ?State; ? //狀態(tài)：任務狀態(tài)

uint8_t ?Period_Count; ?//周期計時：任務每一個周期的計時

uint8_t ?Wait_Time_Flag; ?//等待時間標識：任務是否開始計算等待時間的標識

float WCET; ? //最差執(zhí)行時間，任務單次執(zhí)行所需最長時間

}Task_Control_Block;

3 ?任務調(diào)度算法改進及應用

3.1 ?HRRF任務調(diào)度算法

HRRF任務調(diào)度算法是將CPU分配給就緒任務中響應比最高任務的一種算法。HRRF基于先來先服務算法與短作業(yè)優(yōu)先算法，既考慮任務等待時間又考慮任務服務時間，既照顧短作業(yè)又不使長作業(yè)等待時間過長，從而改進了調(diào)度性能。

任務等待時間的定義如下：

[Twait=Tstart-Tperiod] （1）

式中：[Twait]為任務等待時間，單位為ms;[Tstart]為任務在一個周期內(nèi)開始執(zhí)行的時刻，單位為ms;[Tperiod]為該周期的起始時刻，單位為ms。

任務服務時間定義如下：

[Tservice=Tend-Tstart] （2）

式中：[Tservice]為任務服務時間，單位為ms;[Tend]為任務在一個周期內(nèi)結(jié)束執(zhí)行的時刻，單位為ms;[Tstart]為任務在該周期內(nèi)開始執(zhí)行的時刻，單位為ms。

任務響應比定義為任務等待時間和任務服務時間的和與任務服務時間的比值，即：

[RR=Twait+TserviceTservice=1+TwaitTservice] （3）

式中：[RR]為任務響應比;[Twait]為任務等待時間，單位為ms;[Tservice]為任務服務時間，單位為ms。HRRF任務調(diào)度算法按式（3）定義任務的響應比大小來確定任務的執(zhí)行順序。

3.2 ?改進HRRF及在汽車儀表中的應用

3.2.1 ?HRRF的改進

結(jié)合電動汽車儀表的實際需求，對HRRF任務調(diào)度算法做如下改進：

1） 根據(jù)任務實時性要求的程度，將任務根據(jù)實際情況分為ASAP類和ALAP類。目前的HRRF任務調(diào)度算法在CPU選擇任務分配時，對所有的任務沒有性質(zhì)上的優(yōu)先，都要重新計算響應比，然后選擇響應比最高的任務執(zhí)行。本文改進的HRRF算法，在實際情況中根據(jù)任務的周期大小將任務分為ASAP類和ALAP類。當有ASAP類任務就緒時，只計算ASAP類就緒任務的響應比，選擇最高響應比的任務。沒有ASAP類任務就緒時，再計算ALAP類就緒任務的響應比，選擇最高響應比的任務。

2） 在1）的基礎(chǔ)上選出最高響應比的任務后，判斷在該任務執(zhí)行期間是否有其他任務截止期錯失。若有，則強制選擇截止期丟失的任務中響應比最高的任務執(zhí)行;若沒有，則執(zhí)行1）中最高響應比的任務。

3.2.2 ?改進后的HRRF在汽車儀表軟件設計中的應用

以電動汽車儀表處于IGN工作狀態(tài)為例，改進后的HRRF在汽車儀表軟件設計中的流程如圖3所示。

1） 各任務的初始化與更新

系統(tǒng)在IGN初始化之后，將IGN下激活任務按一定邏輯順序執(zhí)行一次，這樣測得每個任務的第一次服務時間。在各個任務之后每次執(zhí)行時，均測量其服務時間，并實時記錄服務時間最長的一次WCET（Worst Case Execution Time）。每次調(diào)用HRRF算法時，任務的服務時間用上一次測得的任務服務時間近似代替。在激活任務全部執(zhí)行一次完畢之后，任務均處于Suspend狀態(tài)，開始給任務按各自周期計時。任務周期到了，該任務狀態(tài)由Suspend變?yōu)镽eady狀態(tài)，開始等待時間計時。

2） 改進HRRF算法的執(zhí)行

調(diào)用HRRF算法時，先判斷是否有ASAP類任務處于Ready等待執(zhí)行。若有，則在處于Ready的ASAP類任務中選擇響應比最高的任務為接下來執(zhí)行的任務;若沒有，則在處于Ready的ALAP類任務中選擇響應比最高的任務接下來執(zhí)行。同時，系統(tǒng)會判斷是否有任務截止期錯失，若有多個任務截止期丟失，則任務的優(yōu)先級會發(fā)生轉(zhuǎn)換，接下來強制執(zhí)行截止期丟失任務中響應比最高的任務;否則，執(zhí)行ASAP類或ALAP類響應比最高的任務。若系統(tǒng)某時刻執(zhí)行調(diào)度時，所有任務響應比均為0，則接下來執(zhí)行空操作，即此次調(diào)度系統(tǒng)不執(zhí)行任務。任務執(zhí)行時，其狀態(tài)變?yōu)镽unning。執(zhí)行結(jié)束后，任務狀態(tài)變?yōu)镾uspend。

4 ?性能驗證及說明

將所提出的改進HRRF任務調(diào)度算法應用于某公司自主研發(fā)的某車型儀表，對系統(tǒng)各項指標進行實際測量，并進行了分析。

以汽車儀表處于IGN工作狀態(tài)為例，將汽車儀表IGN工作狀態(tài)下任務分為10個，分別為段碼屏顯示速度控制、信號燈控制、CAN數(shù)據(jù)接收處理、按鍵狀態(tài)檢測、電機指針控制、蜂鳴器控制、界面顯示、數(shù)據(jù)丟失處理、故障報警彈窗邏輯控制和蓄電池電壓檢測。

4.1 ?調(diào)度開銷

調(diào)度開銷指在任務切換之間的時間間隔，即調(diào)用HRRF進行任務調(diào)度所花費的時間，其計算公式如下：

[TOverhead=TNext_start-TLast_end] （4）

式中：[TOverhead]表示調(diào)度開銷;[TNext_start]表示下一任務開始執(zhí)行時刻;[TLast_end]表示上一任務結(jié)束時刻。分別設定ASAP類任務占全部任務的比例為0%，20%，40%，60%，80%，相應的進行多次調(diào)度開銷測量，測算結(jié)果見表2。

由表2可知，基于本文提出的調(diào)度算法，汽車儀表系統(tǒng)根據(jù)ASAP類任務占比不同，每次任務調(diào)度開銷約為10～50 μs不等。當ASAP類任務占比為0%，即任務沒有設定上的優(yōu)先屬性時，系統(tǒng)進行任務調(diào)度，實質(zhì)上就是傳統(tǒng)HRRF任務調(diào)度算法。此時，調(diào)度開銷明顯大于任務有設定優(yōu)先屬性時。當ASAP類任務占比不為0%時，ASAP類任務占比越多，調(diào)度開銷越大。在汽車儀表系統(tǒng)中，與各任務的周期相比較，這種調(diào)度開銷完全可以忽略。在實際設計中，可以根據(jù)任務的實際性質(zhì)，配置各任務的優(yōu)先屬性和周期，盡可能優(yōu)化系統(tǒng)。

4.2 ?任務平均等待時間

任務平均等待時間定義為各任務多次等待時間的平均值。設前5個為ASAP類任務，后5個為ALAP類任務，多次測量各任務的等待時間，得到其平均等待時間見表3。

由表3分析可得，ASAP類任務的平均等待時間明顯小于ALAP類任務。原嵌入式前后臺循環(huán)軟件設計模式下，任務無論何時觸發(fā)，都將在系統(tǒng)下次循環(huán)到該任務時才可以執(zhí)行，因此平均等待時間可以近似為整個循環(huán)時間的[12]，而在嵌入式前后臺循環(huán)軟件設計模式中，為了控制系統(tǒng)運行的速度，整個系統(tǒng)循環(huán)控制在100 ms，這就是說，各任務的平均等待時間近似可以認為是50 ms。顯然，系統(tǒng)采用改進后的HRRF任務調(diào)度，無論任務是ASAP類還是ALAP類，均減小了其平均等待時間，任務響應時間變短，提高了實時性。相比于ALAP類任務，ASAP類任務實時性提高的更多。

4.3 ?其他優(yōu)點

相比于嵌入式前后臺循環(huán)軟件設計模式，系統(tǒng)采用HRRF任務調(diào)度，各任務的執(zhí)行頻率不再強行一致，而是根據(jù)各自優(yōu)先屬性決定各自的執(zhí)行頻率。當系統(tǒng)需要增加任務或者減少任務時，只需將相對應的任務添加到任務隊列中或者從任務隊列中刪除，方便了系統(tǒng)的維護和移植。并且考慮任務的截止期錯失，周期性任務調(diào)度的時限會更加規(guī)律。隨著汽車的不斷發(fā)展，汽車儀表要執(zhí)行的任務會更多，采用多任務調(diào)度的優(yōu)勢會更加明顯。

5 ?結(jié) ?語

本文分析了傳統(tǒng)的嵌入式前后臺循環(huán)軟件設計模式的缺點，以汽車儀表為載體，提出將改進后的HRRF任務調(diào)度算法應用于汽車儀表的軟件設計中，解決了目前汽車儀表系統(tǒng)實時性不強，響應時間較慢的問題，并通過實際開發(fā)，對設計算法的實時性及實用性進行了驗證。結(jié)果表明，本文設計的調(diào)度開銷可以忽略，實時性優(yōu)于原設計模式，且方便維護和移植。

參考文獻

[1] 周鵬.管道流量泄漏在線監(jiān)測中的模糊調(diào)度設計[J].計算機工程與應用，2009，45（27）：231?236.

ZHOU Peng. Fuzzy scheduling design in computer on?line mo?nitoring system based on pipeline flux leak [J]. Computer engineering and applications， 2009， 45（27）： 231?236.

[2] 鄭英治，焦哲勇.基于OSEK標準的嵌入式實時操作系統(tǒng)在汽車電子中的應用[J].現(xiàn)代電子技術(shù)，2011，34（3）：148?150.

ZHENG Yingzhi， JIAO Zheyong. Application of embedded RTOS in automotive electronics based on OSEK [J]. Modern electronics technique， 2011， 34（3）： 148?150.

[3] 朱德良，吳國強，陳新春.一種單片機多任務操作系統(tǒng)的設計與應用[J].自動化與儀表，2014，29（1）：50?52.

ZHU Deliang， WU Guoqiang， CHEN Xinchun. Design and application of microcontroller based on multi?tasking operating system [J]. Automation & instrumentation， 2014， 29（1）： 50?52.

[4] 丑文龍，梅魁志，高增輝，等.ARM GPU的多任務調(diào)度設計與實現(xiàn)[J].西安交通大學學報，2014，48（12）：87?92.

CHOU Wenlong， MEI Kuizhi， GAO Zenghui， et al. Design and implementation of multitask scheduling for embedded ARM GPU [J]. Journal of Xian Jiaotong University， 2014， 48（12）： 87?92.

[5] 邢群科，郝紅衛(wèi)，溫天江.兩種經(jīng)典實時調(diào)度算法的研究與實現(xiàn)[J].計算機工程與設計，2006，27（1）：117?119.

XING Qunke， HAO Hongwei， WEN Tianjiang. Research and implementation of two classical real?time scheduling algorithms [J]. Computer engineering and design， 2006， 27（1）： 117?119.

[6] BEGAM R， XIA Qin， ZHU Dakai， et al. Preference?oriented fixed?priority scheduling for periodic real?time tasks [J]. Journal of systems architecture， 2016， 69（C）： 1?14.

[7] BEGAM R， ZHU Dakai， AYDIN H. Preference?oriented fixed?priority scheduling for real?time systems [C]// 2014 IEEE International Conference on Dependable， Autonomic and Secure Computing. Dalian： IEEE， 2014： 159?165.

[8] GUO Yifeng， SU Hang， ZHU Dakai， et al. Preference?oriented real?time scheduling and its application in fault?tolerant systems [J]. Journal of systems architecture， 2015， 61（2）： 127?139.

[9] ALHUSAINY M A F. Best?job?first CPU scheduling algorithm [J]. Information technology journal， 2010， 6（2）： 288?293.

[10] 郭明強，黃穎，謝忠.基于響應比優(yōu)先調(diào)度的WebGIS動態(tài)負載均衡算法[J].地理與地理信息科學，2013，29（2）：36?39.

GUO Mingqiang， HUANG Ying， XIE Zhong. A WebGIS dynamic load balancing algorithm based on response ratio priority scheduling [J]. Geography and geo?information science， 2013， 29（2）： 36?39.

[11] 李海成.基于TinyOS的HRRF調(diào)度策略[J].計算機科學，2010，37（4）：80?81.

LI Haicheng. Research on HRRF scheduling strategy based on TinyOS [J]. Computer science， 2010， 37（4）： 80?81.