嵌入式OSEK/VDX操作系統的優化與應用*

李 靜,邢國成,張家旭,2

(1.吉林大學，汽車仿真與控制國家重點實驗室，長春 130022; 2.中國第一汽車集團技術中心，長春 130011)

2016076

嵌入式OSEK/VDX操作系統的優化與應用*

李 靜1,邢國成1,張家旭1,2

(1.吉林大學，汽車仿真與控制國家重點實驗室，長春 130022; 2.中國第一汽車集團技術中心，長春 130011)

為了解決嵌入式OSEK/VDX操作系統在高負載、搶占模式下低優先級任務長時間得不到執行的問題，利用OSEK/VDX標準中的報警機制提出了一種優化的最小空閑時間優先調度算法來完善嵌入式OSEK/VDX操作系統的調度策略。給出了該算法的具體實現方案，在理論上分析了該算法的可行性，最后將該算法應用于汽車簡單和復雜的電控系統。測試結果表明：在高負載、搶占模式下，使用該算法能夠明顯改善低優先級任務的執行。

OSEK/VDX；最小空閑時間優先；調度算法；優化；應用

前言

針對復雜的汽車電子控制系統，歐洲汽車行業開發了OSEK/VDX標準[1]。文獻[2]中對OSEK/VDX標準進行了詳細解析。

基于OSEK/VDX標準的嵌入式實時操作系統在發動機管理系統(engine management system, EMS)、電子穩定性程序(electronic stability program，ESP)等汽車電子控制系統中有著廣泛的應用[3-4]。但是在實際應用中，當操作系統工作在搶占模式而且系統負載較大時，低優先級任務可能長時間得不到執行，任務的執行周期可能較大程度地偏離用戶的期望值[5-6]。

針對上述問題，文獻[5]中提出了一種基于時間片輪轉調度算法的補償調度策略。文獻[6]中用搶占式的最早截止期優先(earliest deadline first，EDF)調度算法對嵌入式OSEK/VDX操作系統進行了優化，實現了優先級的動態分配，使系統的實時性得到提高。EDF算法可以實現最優調度，但是在實際應用中搶占式EDF調度算法的搶占次數多，額外開銷大，一旦系統過載EDF算法的調度能力將急劇下降[7-8]。

最小空閑時間優先(least slack first，LSF)調度算法是一種典型的動態優先級實時調度算法，同樣能實現最優調度[9-10]。本文中在LSF算法的基礎上，利用嵌入式OSEK/VDX操作系統的報警機制實現了A-LSF(alarm-based least slack first，A-LSF)算法，在理論上分析了算法的合理性，并且給出了算法的應用方案，進行了實驗測試，結果表明：A-LSF算法能夠有效解決低優先級任務長時間得不到執行的問題，而且應用非常靈活。

1 LSF算法的優化

1.1 LSF算法簡介

LSF算法用空閑時間來描述任務的“緊急程度”，在每次任務調度之前都要重新分配所有任務的優先級，空閑時間越小的任務獲得的優先級越高。當兩個任務的空閑時間接近時，會出現任務“緊急程度”相互超越的情況，任務之間會頻繁相互搶占，每次搶占都會發生一次任務切換，這種頻繁切換的現象稱為顛簸現象[11]。

頻繁的任務切換會顯著增加任務的切換時間，而任務的切換時間是評價一個實時操作系統最重要的技術指標之一，因此顛簸現象大大降低了系統調度性能，也制約了LSF算法的應用[12]。現有的優化策略都是通過設置搶占閾值的方法來減輕顛簸現象，文獻[9]中提出了一種動態分配搶占閾值的方案，文獻[12]中提出了一種動態分配模糊閾值的方案，這些改進算法提高了LSF算法的性能，但是也明顯增加了系統的額外負載，降低了系統的實時性。

1.2 優化方案

本文中對LSF算法優化后得到A-LSF算法。A-LSF算法在本質上是對LSF算法的簡化，優化之后無須引入搶占閾值就能夠避免LSF算法的顛簸現象，同時可以解決搶占模式下系統負載較高時，低優先級任務長時間得不到執行的問題。

A-LSF算法是利用OSEK/VDX的報警機制來實現的。報警機制是嵌入式OSEK/VDX操作系統特有的一個概念，它可以在計數器的基礎上實現一系列的定時操作，當報警發生時可以激活任務、設置事件等。本文中通過設置報警和處理報警實現了A-LSF算法。

A-LSF算法是對OSEK/VDX調度算法的一個補充，只有當用戶需要時，為特定任務設置了相應報警，A-LSF算法才會起作用，而且只對指定的任務起作用。A-LSF算法主要分為報警設置和報警處理兩部分。報警處理中的優先級分配算法是整個算法的核心。圖1為A-LSF算法流程圖。

圖1 A-LSF算法流程

1.2.1 報警的設置

設置報警是啟用A-LSF算法的前提。這需要為嵌入式OSEK/VDX操作系統添加“分配優先級”報警，即當報警發生時分配任務的優先級。

設置報警的API函數除了要設置“分配任務優先級”這種報警之外，還須檢測該任務是否有尚未發生的同類報警，如果有，則清除該報警。因為雖然在優化前，該任務長時間得不到執行，但仍然有可能憑借原來較低的靜態優先級被系統所調度，在這種情況下須將之前設置的“分配任務優先級”報警清除，否則該任務有可能會過于頻繁地執行而干擾其它任務的正常運行。在設置報警之后API函數還要恢復該任務的靜態優先級，以避免該任務憑借上一次報警發生后獲得的較高優先級而過多地執行。

1.2.2 報警的處理

報警的處理是A-LSF算法的核心內容。在每次報警發生時，都必須執行“優先級分配算法”來分配任務的優先級。如果此時該任務處于掛起狀態，必須馬上激活該任務；在完成上述操作的基礎上，對執行嵌入式OSEK/VDX操作系統的任務調度算法進行一次任務調度。

1.2.3 優先級分配算法

優先級分配算法是報警處理的核心內容，分為兩步，第一步完成優先級的初步分配，第二步在第一步的基礎上完成優先級分配的優化。

(1)“任務優先級的初步分配”應滿足“優先級限制條件”和“先報警先得到”的原則。前者能確保具有嚴格時限要求的任務不被干擾，后者能按照報警發生的先后順序合理分配任務的優先級。算法的參數定義如表1所示。

表1 優先級分配算法的參數定義

優先級限制條件：假設此時只有任務τj的“優先級分配”報警發生，則任務τj的新優先級pj=pm。在實際的系統中，某些高優先級任務可能有嚴格的時間要求，不允許被干擾，此時pm的值應該低于這類任務的優先級。

先報警先得到原則：先發生“分配優先級”報警的任務會獲得較高的優先級。假設任務τi的報警先發生，而且將優先級提高到了pi，緊接著任務τj的報警發生，則τj的新優先級pj取小于pi的最大值。

(2)“優先級分配的優化”目的在于使得所有使用A-LSF算法的任務盡量獲得較高的優先級。因此需要檢查是否有任務使用了A-LSF算法而且已經執行完畢，如果有，則該任務已經釋放了它的優先級，此時應該按照(1)中的條件盡量提升其它任務的優先級。

按照該算法來為任務分配優先級會出現整個系統中多個任務共享一個優先級的情況。在OSEK/VDX標準中，當操作系統的符合類為BCC2和ECC2時，系統允許多任務共享一個優先級，符合類為BCC1和ECC1時不允許這種情況發生。因此，只當符合類為BCC2或ECC2時才可以使用A-LSF算法。

2 A-LSF算法的理論分析

定義一個任務集：τi={Ti,ri,Di,di,t,ta1,i,tad,i,ts1,i,talarm,i}，i=0,1,2,3…。任務集中各參數定義如下：Ti為任務τi的周期(本文中的研究僅限于由周期性任務構成的實時系統)；ri為任務τi剩余的執行時間；Di為任務τi的空閑時間；di為任務τi的截止期限；ta1,i為任務τi第一次被激活的時刻；t為當前時刻；talarm,i為任務τi的報警時刻；tad,i為任務τi的剩余報警時間；ts1,i為任務τi第一次設置報警的時刻。

針對LSF算法中di的計算有多種研究，文獻[12]中以任務周期Ti的結束時刻作為LSF算法的截止期限，在此基礎上開發了針對多處理器調度的LSFR算法。實際中di的取值與Ti緊密相關，為了計算方便仍將任務在執行周期Ti結束的時刻作為di。

圖2為A-LSF算法的時序簡圖。由圖可知，在A-LSF算法中，當任務τi的第k次設置報警結束時，本次任務τi的截止期限為

di=ts1,i+k·Ti

(1)

圖2 A-LSF時序簡圖

根據嵌入式OSEK/VDX操作系統中的報警機制，計算在t時刻任務τi的剩余報警時間：

tad,i=di-t-ri

(2)

tad,i=ts1,i+k·Ti-t-ri

(3)

(4)

(5)

由于ts1,i可以視為常數，故在給定時刻t，任務的剩余報警時間tad,i是任務周期Ti和任務剩余時間ri的函數。

對LSF算法采用相同的思路計算可得：

di=ta1,i+k·Ti

(6)

Di=di-t-ri

(7)

(8)

式(5)和式(8)只有常數項ts1,i與ta1,i不同，A-LSF算法中tad,i的概念等同于LSF算法中Di的概念。在A-LSF算法中，報警發生時意味著任務剩余報警時間tad,i=0，即Di=0，此時才會提升該任務的優先級，否則任務只能擁有原來相對較低的靜態優先級，這正是LSF算法中“最小空閑時間優先”的思想。

A-LSF算法中報警發生之前，每個任務的空閑時間都是嚴格遞減的，報警發生之后將不再變化，因此不會出現LSF算法中任務的緊急程度交替超越的情況。這實際上是LSF算法運行過程中的一種特殊情況，A-LSF算法只有在這種情況下才會為任務分配優先級，而且優先級分配算法遵循“先報警先得到”的原則，避免了“顛簸現象”。

LSF算法在每次調度之前都要更新所有任務的空閑時間和優先級，以此來實現最優調度。但是本文中的目的在于解決低優先級任務得不到執行的問題，低優先級任務的執行周期本身就較長，沒有必要在每次任務調度之前都重新分配任務的優先級，如果不對LSF算法進行簡化，系統分配優先級的頻率會大大增加，而且必須添加其它算法來避免“顛簸現象”，這會額外增加系統負荷。所以，A-LSF算法相當于簡化了LSF算法，滿足了當前的需求。

3 優化后操作系統的應用

A-LSF調度策略是可選項，用戶可以根據具體情況決定是否使用A-LSF算法。如果在測試過程中發現某些低優先級任務需要使用A-LSF算法，只須針對這些任務進行簡單的配置即可；如果不使用該算法，不會對操作系統的運行產生任何影響，這大大增強了操作系統的靈活性。一般來說，只有當汽車電控系統較為復雜時才有必要在系統中配置該調度策略。本節分別介紹優化后的嵌入式OSEK/VDX操作系統在復雜系統和簡單系統中的應用。

3.1 復雜的汽車電控系統

在實時性要求較高的復雜汽車電控系統中，傳感器和執行器數量較多，控制算法也很復雜。因此，系統的任務數量多，負載較大。假設現有控制系統中，包含任務τ0,τ1，…,τ9，任務優先級由1到10逐次升高，均配置為搶占模式。此時用戶需要根據具體的測試數據來配置系統的調度策略。假設測得任務τ0,τ1較長時間得不到執行，運行周期嚴重偏離用戶預期，此時需要使用A-LSF算法，按照表2來配置系統的調度策略。

表2 調度策略配置方案

按照表2的配置方案，各個任務的調度策略如圖3所示。

圖3 任務調度策略配置結果

任務1和任務2配置為A-LSF，即使用A-LSF算法，任務3-任務10配置為Default，即不使用A-LSF算法。pm值設置為4，意味著在A-LSF算法運行時，任務1和任務2的優先級最多升高至4。在決定了系統的調度策略之后，最重要的是完成報警的設置和處理。

(1)任務τ1和任務τ2中在應用層代碼結束的位置設置基于系統計數器的“分配優先級”報警，因為設置報警的API函數具有恢復任務靜態優先級的功能，所以放到用戶代碼之后算法才有意義。由圖2可知，設置報警的時長由任務的周期和執行時間決定，但是圖2僅僅是理想的情況，實際中當報警發生之后，任務仍然可能被更高優先級任務搶占，不會連續執行至結束。因此報警發生的時刻應該比圖2中的時刻提前一些，具體的提前量須由用戶實際測試后確定。

(2)在系統時鐘的中斷服務程序中調用處理報警的API函數。

3.2 簡單的汽車電控系統

在相對簡單的汽車電控系統中，任務數量一般較少，系統負載較小。任務的實時性比較容易滿足要求。因此，在這類系統中無須為任何任務配置A-LSF算法，調度策略配置結果如圖4所示，操作系統與優化前相比沒有任何區別,這也體現了A-LSF算法的靈活性。

圖4 任務調度策略配置結果

4 實驗測試與結果分析

以飛思卡爾公司的微控制器MC9S12XS128和Dspace公司的MicroAutoBox搭建實驗平臺。合理安排τ0-τ9共10個搶占式周期性任務，優先級從1到10逐次升高。每個任務的執行時間是固定的，分別在優化前和優化后的嵌入式OSEK/VDX操作系統上運行，其中高優先級任務的代碼執行時間和執行周期都較短，低優先級任務的代碼執行時間和執行周期都較長。

為了能直觀地觀察任務的運行狀態，安排τ0-τ9各個任務分別控制一個IO口。當任務運行時相應IO口為高電平，任務退出或者被搶占后IO為低電平。利用ControlDesk的plotter工具，分別顯示兩個最高優先級和兩個最低優先級任務的運行狀態，優化前、后任務的運行狀態分別如圖5和圖6所示。4個波形由上到下分別代表任務τ0，τ1，τ8和τ9，優化后任務τ0和τ1使用了ALSF算法。

圖5 優化前的任務運行狀態

圖6 優化后的任務運行狀態

對比圖5和圖6可知：優化前后高優先級任務的運行周期和執行時間基本穩定，沒有明顯變化；優化前低優先級任務的運行周期和執行時間很不穩定，可能很長時間才執行一次，優化后低優先級任務的運行狀態雖然沒有高優先級任務穩定，但是得到了非常明顯的改善，能夠滿足用戶的需求。

5 結論

(1)A-LSF算法可以實現對嵌入式OSEK/VDX操作系統的優化，能夠解決系統在高負載搶占模式下低優先級任務得不到及時執行的問題。

(2)A-LSF算法克服了LSF算法原有的顛簸現象，而且與EDF或LSF算法相比，結構更加簡單，容易實現。A-LSF算法作為可選項也增加了整個操作系統的靈活性。

[1]KIENCKEU,THIERERC.TheOSEK/VDXStandardforAutomotiveApplications-CurrentStatus[C].SAETransactions,March, 2000: 140-146.

[2] 羅克露，等.OSEK/VDX汽車電子嵌入式軟件編程技術[M]. 北京：北京航空航天大學出版社，2004.

[3]MirceaPopa,AncaSoranaPopa,TitusSlavici,etal.OntheImplementationoftheOSEK/VDXOperatingSystemonAdvancedMicrocontrollers[C].TheInternationalConferenceonComputerasaTool,IEEE, 2007:419-426.

[4] 郜文,李繼來,梁華為.OSEK/VDX嵌入式實時操作系統在汽車穩定性控制器中的應用[J]. 計算機系統應用, 2010, 19(4):148-151.

[5] 蔣建春，張慧.基于OSEK標準的任務調度算法的改進[J]. 計算機工程,2009,35(20)：228-230.

[6] 馬明禮,等.OSEK實時操作系統任務調度的優化[J]. 單片機與嵌入式系統, 2007,10:17-53.

[7]LIUCL，JamesWLaykand.SchedulingAlgorithmsforMultiprogramminginaHard-Real-TimeEnvironment[J].JournaloftheAssociationforComputingMachinery，1973,20(1)：46-61.

[8] 王濟勇,林濤,王金東,等.EDF調度算法搶占行為的研究及其改進[J].電子學報，2004,32(1):64-68.

[9]BAWei,ZHANGDabo.ANovelLeastSlackFirstSchedulingAlgorithmOptimizedbyThreshold[C].Proceedingsofthe26thChineseControlConference，Zhangjiajie,July26-31, 2007.Beijing:BeihangUniversityPress, 2007.

[10]HWANGMyunggwon,CHOIDongjin,KIMPankoo.LeastSlackTimeRatefirst:NewSchedulingAlgorithmforMulti-ProcessorEnvironment[C].IEEEComputerSociety,Feb,2010:806-811.

[11]PARKS,KIMJai-Hoon,FOXG.Effectivereal-timeSchedulingAlgorithmforCyberPhysicalSystemsSociety[J].FutureGenerationComputerSystems, 2014,32:253-259.

[12] 金宏, 王宏安, 王強, 等. 改進的最小空閑時間優先調度算法[J]. 軟件學報, 2004,15(8):1116-1123.

Optimizationand Application of Embedded OSEK/VDX Operating System

Li Jing1, Xing Guocheng1& Zhang Jiaxu1,2

1.JilinUniversity,StateKeyLaboratoryofAutomotiveSimulationandControl,Changchun130022；2.ResearchandDevelopmentCenter,ChinaFAWGroupCorporation,Changchun130011

For solving the problem that the low-priority tasks are hard to be executed under high load and preemption mode with embedded OSEK/VDX operating system, an optimized least slack first algorithm is proposed by utilizing the alarm mechanism of OSEK/VDX standard to improve the scheduling strategy of embedded OSEK/VDX operating system. The specific implementation scheme of the algorithm is presented, its feasibility is theoretically analyzed, and finally the algorithm is applied to both simple and complex electric control systems of vehicle. The results of test show that the algorithm proposed can significantly improve the excitation of low-priority tasks under the condition of high load and preemption mode.

OSEK/VDX； LSF; scheduling algorithm; optimization; application

*國家自然科學基金(51275206)資助。

原稿收到日期為2015年3月16日，修改稿收到日期為2015年5月28日。