桑 磊，陸 陽，3，俞 磊

（1．合肥工業(yè)大學計算機與信息學院，合肥230009；2．安徽中醫(yī)藥大學醫(yī)藥信息工程學院，合肥230012；3．安徽省礦山物聯(lián)網(wǎng)與安全監(jiān)控技術重點實驗室，合肥230088）

1 概述

物聯(lián)網(wǎng)技術的快速發(fā)展使得嵌入式系統(tǒng)被廣泛地應用于物流、智能家居、安防等領域，這些嵌入式系統(tǒng)很多都是實時系統(tǒng)。實時操作系統(tǒng)與一般的操作系統(tǒng)相比，最大的特色就是其具有實時性，即：如果有一個任務需要執(zhí)行，實時操作系統(tǒng)會馬上執(zhí)行該任務，不會有較長的延時，并在其截止期內完成。實時任務的這種執(zhí)行時間和截止期限屬性保證了各個任務的及時執(zhí)行［1－2］，可見實時任務的正確性不僅取決于程序邏輯的正確性，也取決于截止期能否得到滿足。

嵌入式實時系統(tǒng)的實時性能很大程度上取決于實時任務的調度策略。在眾多實時調度策略中，基于優(yōu)先級驅動（Priority Driven，PD）的算法是一類重要的調度算法，典型代表有速率單調（Rate Monotonic，RM）算法、最早截止期優(yōu)先（Earliest Deadline First，EDF）調度算法等［2］。其中，EDF算法被證明是較優(yōu)的動態(tài)優(yōu)先級調度策略。實時系統(tǒng)中任務的優(yōu)先級各不相同，且存在動態(tài)變化的過載狀態(tài)。EDF算法在這種過載情況下會產(chǎn)生“多米諾效應”，一個任務錯失截止期會導致后續(xù)很多任務也錯失截止期，從而使得大部分任務的實時性無法保證［3］。在這種動態(tài)過載狀態(tài)下，如何盡最大努力降低任務的截止期錯失率（Deadline Missing Ratio，DMR）成為一個重要問題。文獻［4］研究采用BACK－SLASH和SLAD算法來降低EDF調度算法在過載情況下的截止期錯誤率，但其以系統(tǒng)的復雜性顯著提高為代價。

傳統(tǒng)的實時調度算法存在的問題在于采用簡單和片面的特征參數(shù)來確定優(yōu)先級，如截止期、到達時間和關鍵性等，然而基于某個單一的特征參數(shù)不能體現(xiàn)任務在其他重要性方面的要求，同時也不能考慮用戶對任務優(yōu)先級確定的喜好［5］。為此，本文在EDF算法的基礎上增加全局優(yōu)先級特征參數(shù)來標識任務價值，通過引入貪心策略對過載時的任務進行最優(yōu)化選擇，在保證高優(yōu)先級任務執(zhí)行性能的前提下，盡可能地執(zhí)行更多的任務，充分利用系統(tǒng)資源。

2 任務調度模型

2．1 算法可調度性判斷

在一個單核處理器系統(tǒng)中，定義S＝｛t1，t2，…，tN｝為調度任務集，該任務集包含N個周期性任務，Ti表示任務ti的周期，Ci表示任務ti的最壞執(zhí)行時間。

定義1（超周期） 所有任務周期值的最小公倍數(shù)，記為H。對于周期性任務，每個周期內任務的運行情況是相同的，所以，只需要分析在第一個超周期［0，H］內系統(tǒng)的調度情況，就可以知道在其他時段內的執(zhí)行情況。在每個超周期內執(zhí)行的最大任務實例數(shù)為：

定義2（周期任務的負載） 一個周期任務對處理器的平均占用率，記為Ui，Ui＝Ci／Ti，這里假設每個任務在任何時刻都是可被搶占的，且這一搶占過程不會增加其他的輔助開銷。

定義3（周期任務集的負載） 系統(tǒng)周期任務集中所有周期任務的負載之和［6－7］，記為：

系統(tǒng)周期任務集的負載體現(xiàn)了所有任務對CPU資源的需求情況與系統(tǒng)能提供的最大服務之間的關系。

定理 使用EDF算法調度周期性任務集，可調度的充要條件是周期任務集的負載U≤1。

對實時系統(tǒng)任務集S采用EDF調度算法，當且僅當U≤1，此時系統(tǒng)處于低負載狀態(tài)，就稱任務集S是可調度的。在單處理器的情況下，在一個超周期H內，處理器忙運行的總共時間為H×U，處理器空閑的時間共為H×（1－U）。顯然只有當U≤1時，才可能有一種調度算法能把所有的周期任務都執(zhí)行完。但當CPU資源利用率U＞1時，會發(fā)生系統(tǒng)過載，任務集的處理需求大于系統(tǒng)的處理能力，則該任務集是不可調度的。

本文設計的算法既要保證優(yōu)先級高的任務先執(zhí)行，又要保證完成盡可能多的任務實例，即使任務的錯失率降到最低。

2．2 貪心策略分析

在系統(tǒng)過載的情況下，并不是所有的任務都能執(zhí)行，所以，就需要對任務有選擇的進行調度，使得CPU利用率U盡可能接近于1，且被調度任務具有較高的優(yōu)先級。最優(yōu)調度任務集的選擇過程可以抽象為一個典型的0－1背包問題。0－1背包問題可描述為：給定一個背包和n個物品，物品i的重量是wi，價值是vi。背包至多只能裝下總重量為W的物品，要從這n件物品中選出若干件放入背包中，放入物品的總重量不多于W，并且背包中的物品總價值達到最大［8］。在本文最優(yōu)調度集的選擇問題上，就是要選擇出若干任務組成最優(yōu)調度集，調度集中各任務的CPU利用率U之和不超過1，且所有任務的總優(yōu)先級達到最大。在過載狀態(tài)下只對最優(yōu)調度集中的任務進行調度，既可保證系統(tǒng)資源被充分利用，又可確保高優(yōu)先級的任務優(yōu)先被調度，這樣在某個時間段內就可以提高系統(tǒng)性能，獲得最大任務價值。

0－1背包問題是一個NP難題，而貪心算法是對0－1背包類型問題的一種常用解決方法。貪心算法是使每次所做的選擇在當前看來都是最佳的，也就是期望通過所做出的局部最優(yōu)選擇來產(chǎn)生一個全局的最優(yōu)解。這種啟發(fā)式的求解策略并不總能獲得最優(yōu)解，然而在許多情況下仍能達到預期的目的。在0－1背包問題的解決上使用價值密度（價值重量比vi／wi）的貪心策略，該策略為從剩余的物品中選擇價值密度最大的那個物品，使用該策略求解0－1背包問題的具體過程如下［9］：

對于每個物品，分別求出其價值密度，ri＝vi／wi，i＝1，2，…，n。

（1）按照價值密度，對所有物品按非升序排列：（v（1）／w（1））≥（v（2）／w（2））≥…≥（v（n）／w（n））。

（2）重復以下步驟，直到條件不滿足為止：對當前的物品，如果重量不大于包中剩余的重量，則放入，并置物品標志為1（表明被選中），否則就停止。

算法主要耗時在于把所有物品按價值密度排序，本文是基于快速排序實現(xiàn)的，因此，該算法的時間復雜度為O（nlogn）。

2．3 基于貪心策略選擇最優(yōu)任務集選擇

2．3．1 任務優(yōu)先級的定義

EDF調度算法中的任務優(yōu)先級是根據(jù)截止期來確定的，但是在實際的應用中，截止期短的任務并不一定是用戶認為最重要的任務，而截止期長的任務也不一定是最不重要的任務，為此，在每個任務中引入一個重要程度參數(shù)Ei，來表示任務在實際應用中的重要度。已知任務Ti的運行時間是Ci，任務Ti的優(yōu)先級計算如下：

其中，We和Wc分別表示重要度和運行時間的權重，且有We＞W(wǎng)c。Pi越大，則優(yōu)先級越大，體現(xiàn)出任務的價值也就越高。

2．3．2 調度算法

本文介紹了一種基于貪心策略的調度算法（EDF scheduling algorithm Based on Greedy Policy，EDFGP）。EDFGP是通過改進EDF算法而來的，EDFGP同時參考截止期和優(yōu)先級2個特征參數(shù)。這里的全局優(yōu)先級Pi是通過綜合考慮任務的運行時間和重要度而得到的結果。這樣就使得每個任務不但有截止期參數(shù)而且還擁有體現(xiàn)任務價值的全局優(yōu)先級。

當U≤1時，系統(tǒng)采用EDF算法的對任務集S進行調度，系統(tǒng)可正常運行；當U＞1時，并不是任務集S中的所有任務都能得到調度。此時，根據(jù)任務的優(yōu)先級CPU利用率比Pi／Ui，即任務的價值密度，把所有任務按照非升序排列。利用貪心策略，就能快速地從已排序的任務集中選擇出一個最優(yōu)任務集。系統(tǒng)優(yōu)先對最優(yōu)調度集中的任務進行調度，而只有在處理器空閑時才會對非最優(yōu)調度集中的任務進行調度。

2．3．3 算法實現(xiàn)

EDFGP算法主要分3步實現(xiàn)：

步驟1用式（2）對當前系統(tǒng)進行可調度判斷，確定系統(tǒng)處于過載狀態(tài)，如果沒有發(fā)生過載，就直接使用EDF算法調度；否則到步驟2，使用EDFGP算法進行調度。

步驟2對任務進行分類，使用貪心策略選擇高價值密度的任務組成一個集合，稱之為最優(yōu)調度集合；而剩余的其他任務組成一個集合，稱之為非最優(yōu)調度集合；每當有新的任務加入時，都要重新確定最優(yōu)調度集合。

圖1是最優(yōu)調度集的選擇流程。在實際的應用中，使用鏈表Q用來存儲最優(yōu)調度集中的任務，鏈表P用來存儲非最優(yōu)調度集。選擇出的最優(yōu)調度集合Q必須滿足式（2）中的可調度條件U≤1；而若對所有任務集S有U≤1，即系統(tǒng)處于非過載狀態(tài)時，任務集S可以認為就是最優(yōu)調度集，此時非最優(yōu)調度集P為空。

圖1 最優(yōu)調度集選擇流程

步驟3任務調度，當前任務完成后，必須刷新所有任務的截止期，然后判斷是否有新的任務加入，如果有新的任務加入，就重新使用貪心策略確定最優(yōu)調度集。

EDFGP調度算法的偽代碼如下：

3 性能分析與實驗結果

如果一個任務不能在其截止期限內完成，則稱該任務錯失了截止期。在實時系統(tǒng)中，截止期錯失率是一個評價系統(tǒng)性能的重要指標。DMR定義為在運行的一段時間內錯過截止期的任務數(shù)與所有任務數(shù)的比值［10－11］。假設錯過截止期的任務數(shù)n，而沒有錯過截止期的任務為m，則有：

下面通過HVF，EDF與EDFGP算法的實驗比較來考察各算法的執(zhí)行性能。

3．1 性能分析

通過2個實驗對比HVF，EDF和EDFGP算法在不同負載的情況下的性能表現(xiàn)。

3．1．1 低負載情況下的調度分析

設在一個實時系統(tǒng)中有2個任務，其周期、最壞執(zhí)行時間、優(yōu)先級等參數(shù)如表1所示。其中，優(yōu)先級只對HVF調度算法起作用，因為在低負載時EDF和EDFGP的優(yōu)先級由其任務的截止期來確定。

表1 實驗任務集1

此時系統(tǒng)總負載U＝30／50＋10／40＋10／70≤1，系統(tǒng)未過載。分別使用HVF，EDF和EDFGP算法對這3個任務進行調度，運行結果如圖2所示。其中，縱坐標執(zhí)行性能表示不同任務的截止期被滿足的比例。

圖2 系統(tǒng)低負載時的執(zhí)行性能比較

在使用固定優(yōu)先級的HVF調度算法時，任務A和任務B的DMR為0，任務得到充分執(zhí)行，但任務C存在錯失截止期的情況。而采用EDF和EDFGP算法3個任務都能得到有效執(zhí)行，CPU資源利用率達到了100%，總的DMR為0。實驗表明，在低負載情況下，EDFGP算法可以達到和EDF算法相同的執(zhí)行性能。

3．1．2 過載情況下的調度分析

假設在過載情況下有3個任務，其周期、執(zhí)行時間、全局優(yōu)先級等屬性如表2所示。

表2 實驗任務集2

表2中的優(yōu)先級是表示任務重要性的全局優(yōu)先級，數(shù)字越小優(yōu)先級越高，則此時任務價值應表示為Pi×Ui。由可調度性判斷式（2）計算出CPU資源利用率為1．275＞1，即此任務集不可調度（系統(tǒng)過載），并不是所有的任務都能在截止期前保證完成。3個任務分別使用HVF，EDF和EDFGP算法進行調度，執(zhí)行結果如圖3所示。

圖3 系統(tǒng)過載時的執(zhí)行性能比較

在系統(tǒng)過載的情況下，使用EDF算法雖然可以使每個任務都得到調度的機會，但是總體的執(zhí)行性能不好，3個任務總的DMR達到了42．1%。在HVF調度算法下，只有優(yōu)先級高的任務A和任務B的截止期得到了保證，優(yōu)先級最低的任務C則完全錯失。而在使用EDFGP算法時，既保證了關鍵任務A和任務B的執(zhí)行，又使系統(tǒng)整體的DMR降低到了21．1%，調度性能比HVF和EDF算法都好。

3．2 實驗結果分析

使用μC／OS－II實時操作系統(tǒng)對 HVF，EDF和優(yōu)化后的EDFGP算法進行仿真實驗，并通過實驗來對比各算法的截止期錯誤率DMR。

參考μC／OS－II的內核結構，修改系統(tǒng)任務控制塊模型并產(chǎn)生多個隨機的周期性任務［12－14］，其中系統(tǒng)優(yōu)先級設置為1～64，產(chǎn)生的任務數(shù)為1～64。任務的周期和執(zhí)行時間同樣分別在［100，700］，［1，50］區(qū)間上隨機產(chǎn)生。分別使用HVF，EDF和EDFGP算法對這些隨機生成的任務進行調度。使用μC／OS－II中的狀態(tài)檢查函數(shù)OSTaskStat（）可以統(tǒng)計出每個任務實際的完成時間，通過與該任務的截止期進行對比就可以判斷是否錯失了截止期，然后計算出整組任務的DMR。反復進行多組實驗后，3種調度算法的DMR對比如圖4所示。

圖4 3種算法的截止期錯失率對比

從實驗結果可以看出，3種算法在負載較低時都保持著較好的一致性，但是在任務數(shù)增加到一定程度后，3種算法都會存在任務截止期錯誤率急劇上升的問題。其中，HVF算法在系統(tǒng)過載后DMR上升最為明顯，而從增加的速度上來看，EDFGP算法DMR增速較EDF算法略低；在同樣的系統(tǒng)負載下，經(jīng)過優(yōu)化后的EDFGP算法的DMR要比優(yōu)化前的EDF算法低。同之前的仿真性能分析比較，在未過載的情況下實驗結果與前面的性能分析一致，在系統(tǒng)過載的情況下，EDFGP算法較HVF算法有著明顯的性能提升，雖然相對于EDF算法的提高并不明顯，但也達到了優(yōu)化的目的。

4 結束語

本文在EDF算法的基礎上，分析其在過載情況下所存在的問題，提出一種基于貪心策略的動態(tài)搶占調度算法。該算法使用貪心策略從任務集中高效地選擇出最優(yōu)調度集，使CPU資源得到充分利用，并實現(xiàn)高優(yōu)先級任務的及時調度，從而降低系統(tǒng)的截止期錯誤率，提高算法的執(zhí)行性能。實驗結果表明，本文算法較EDF算法具有更低的截止期錯失率。下一步將研究如何優(yōu)化最優(yōu)調度集的選擇過程，使調度性能提高更為明顯。

［1］夏家莉，陳 輝，楊 兵．一種動態(tài)優(yōu)先級實時任務調度算法［J］．計算機學報，2012，35（12）：2685－2695．

［2］Liu C L，Layland J W．Scheduling Algorithms for Multi－programming in a Hard－real－time Environment［J］．Journal of the ACM，1973，20（1）：46－61．

［3］羅 鈞，吳 志．嵌入式系統(tǒng)動態(tài)策略任務調度算法［J］．重慶大學學報：自然科學報，2008，31（7）：792－796．

［4］余祖峰，蔡啟先，劉 明．EDF調度算法的實時性改進［J］．廣西工學院學報，2010，21（1）：82－85．

［5］夏家莉，陳 輝，楊 兵．一種動態(tài)優(yōu)先級實時任務調度算法［J］．計算機學報，2012，35（12）：2685－2695．

［6］程 禹，趙宏偉，龍曼麗，等．最早截止期優(yōu)先調度算法的改進［J］．吉林大學學報：工學版，2013，43（5）：1338－1342．

［7］于國龍，張明富．基于桶排序的 EDF調度算法優(yōu)化［J］．蘭州理工大學學報，2013，39（4）：110－113．

［8］史 嵐，張義宏，呂建輝，等．基于絕對貪心和預期效率的0－1背包問題優(yōu)化［J］．計算機應用研究，2014，31（3）：684－687．

［9］田烽楠，王 于．求解0－1背包問題算法綜述［J］．軟件導刊，2009，8（1）：59－61．

［10］吳 訊，馬 媛，董勤鵬．實時操作系統(tǒng)實時性能測試技術研究［J］．系統(tǒng)仿真學報，2013，9（2）：12－15．

［11］宋 杰，檀林欣，曹竹冬，等．一種新型的實時調度算法［J］．計算機技術與發(fā)展，2010，20（12）：73－76．

［12］龍昭華，漆動波，蔣貴全．一種嵌入式系統(tǒng)自適應調度算法研究［J］．重慶郵電大學學報：自然科學版，2009，21（5）：653－657．

［13］尹嘉鵬，徐志祥．針對少實時任務應用的嵌入式Linux改進［J］．計算機工程，2013，39（10）：49－52．

［14］周本海，王溪波，喬建忠，等．基于多參數(shù)的μC／OS－Ⅱ任務優(yōu)先級和調度方法［J］．計算機工程，2007，33（21）：28－30．