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

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

2016076

嵌入式OSEK/VDX操作系統(tǒng)的優(yōu)化與應(yīng)用*

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

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

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

OSEK/VDX；最小空閑時間優(yōu)先；調(diào)度算法；優(yōu)化；應(yīng)用

前言

針對復(fù)雜的汽車電子控制系統(tǒng)，歐洲汽車行業(yè)開發(fā)了OSEK/VDX標(biāo)準(zhǔn)[1]。文獻[2]中對OSEK/VDX標(biāo)準(zhǔn)進行了詳細(xì)解析。

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

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

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

1 LSF算法的優(yōu)化

1.1 LSF算法簡介

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

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

1.2 優(yōu)化方案

本文中對LSF算法優(yōu)化后得到A-LSF算法。A-LSF算法在本質(zhì)上是對LSF算法的簡化，優(yōu)化之后無須引入搶占閾值就能夠避免LSF算法的顛簸現(xiàn)象，同時可以解決搶占模式下系統(tǒng)負(fù)載較高時，低優(yōu)先級任務(wù)長時間得不到執(zhí)行的問題。

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

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

圖1 A-LSF算法流程

1.2.1 報警的設(shè)置

設(shè)置報警是啟用A-LSF算法的前提。這需要為嵌入式OSEK/VDX操作系統(tǒng)添加“分配優(yōu)先級”報警，即當(dāng)報警發(fā)生時分配任務(wù)的優(yōu)先級。

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

1.2.2 報警的處理

報警的處理是A-LSF算法的核心內(nèi)容。在每次報警發(fā)生時，都必須執(zhí)行“優(yōu)先級分配算法”來分配任務(wù)的優(yōu)先級。如果此時該任務(wù)處于掛起狀態(tài)，必須馬上激活該任務(wù)；在完成上述操作的基礎(chǔ)上，對執(zhí)行嵌入式OSEK/VDX操作系統(tǒng)的任務(wù)調(diào)度算法進行一次任務(wù)調(diào)度。

1.2.3 優(yōu)先級分配算法

優(yōu)先級分配算法是報警處理的核心內(nèi)容，分為兩步，第一步完成優(yōu)先級的初步分配，第二步在第一步的基礎(chǔ)上完成優(yōu)先級分配的優(yōu)化。

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

表1 優(yōu)先級分配算法的參數(shù)定義

優(yōu)先級限制條件：假設(shè)此時只有任務(wù)τj的“優(yōu)先級分配”報警發(fā)生，則任務(wù)τj的新優(yōu)先級pj=pm。在實際的系統(tǒng)中，某些高優(yōu)先級任務(wù)可能有嚴(yán)格的時間要求，不允許被干擾，此時pm的值應(yīng)該低于這類任務(wù)的優(yōu)先級。

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

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

按照該算法來為任務(wù)分配優(yōu)先級會出現(xiàn)整個系統(tǒng)中多個任務(wù)共享一個優(yōu)先級的情況。在OSEK/VDX標(biāo)準(zhǔn)中，當(dāng)操作系統(tǒng)的符合類為BCC2和ECC2時，系統(tǒng)允許多任務(wù)共享一個優(yōu)先級，符合類為BCC1和ECC1時不允許這種情況發(fā)生。因此，只當(dāng)符合類為BCC2或ECC2時才可以使用A-LSF算法。

2 A-LSF算法的理論分析

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

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

圖2為A-LSF算法的時序簡圖。由圖可知，在A-LSF算法中，當(dāng)任務(wù)τi的第k次設(shè)置報警結(jié)束時，本次任務(wù)τi的截止期限為

di=ts1,i+k·Ti

(1)

圖2 A-LSF時序簡圖

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

tad,i=di-t-ri

(2)

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

(3)

(4)

(5)

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

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

di=ta1,i+k·Ti

(6)

Di=di-t-ri

(7)

(8)

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

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

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

3 優(yōu)化后操作系統(tǒng)的應(yīng)用

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

3.1 復(fù)雜的汽車電控系統(tǒng)

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

表2 調(diào)度策略配置方案

按照表2的配置方案，各個任務(wù)的調(diào)度策略如圖3所示。

圖3 任務(wù)調(diào)度策略配置結(jié)果

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

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

(2)在系統(tǒng)時鐘的中斷服務(wù)程序中調(diào)用處理報警的API函數(shù)。

3.2 簡單的汽車電控系統(tǒng)

在相對簡單的汽車電控系統(tǒng)中，任務(wù)數(shù)量一般較少，系統(tǒng)負(fù)載較小。任務(wù)的實時性比較容易滿足要求。因此，在這類系統(tǒng)中無須為任何任務(wù)配置A-LSF算法，調(diào)度策略配置結(jié)果如圖4所示，操作系統(tǒng)與優(yōu)化前相比沒有任何區(qū)別,這也體現(xiàn)了A-LSF算法的靈活性。

圖4 任務(wù)調(diào)度策略配置結(jié)果

4 實驗測試與結(jié)果分析

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

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

圖5 優(yōu)化前的任務(wù)運行狀態(tài)

圖6 優(yōu)化后的任務(wù)運行狀態(tài)

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

5 結(jié)論

(1)A-LSF算法可以實現(xiàn)對嵌入式OSEK/VDX操作系統(tǒng)的優(yōu)化，能夠解決系統(tǒng)在高負(fù)載搶占模式下低優(yōu)先級任務(wù)得不到及時執(zhí)行的問題。

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

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

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

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

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

[5] 蔣建春，張慧.基于OSEK標(biāo)準(zhǔn)的任務(wù)調(diào)度算法的改進[J]. 計算機工程,2009,35(20)：228-230.

[6] 馬明禮,等.OSEK實時操作系統(tǒng)任務(wù)調(diào)度的優(yōu)化[J]. 單片機與嵌入式系統(tǒng), 2007,10:17-53.

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

[8] 王濟勇,林濤,王金東,等.EDF調(diào)度算法搶占行為的研究及其改進[J].電子學(xué)報，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] 金宏, 王宏安, 王強, 等. 改進的最小空閑時間優(yōu)先調(diào)度算法[J]. 軟件學(xué)報, 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

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

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