0引言

嵌入式實時系統(tǒng)由于自身CPU計算能力較弱和內(nèi)存容量較低的原因，希望采用復雜度低、系統(tǒng)開銷小的調(diào)度算法。目前的實時系統(tǒng)通常采用單優(yōu)先級驅(qū)動的搶占式調(diào)度算法，根據(jù)任務的某一時間特性參數(shù)如任務周期或最后截止期等為各個任務分配系統(tǒng)資源[1][2]。這種搶占式調(diào)度策略具有靈活性和動態(tài)性等優(yōu)點。但在，實際應用系統(tǒng)中也有一些由不相交的周期任務子集組成，每個子集是系統(tǒng)的一個主要部分，稱之為子系統(tǒng)。例如，飛行管理系統(tǒng)包含飛行控制，電子設備和導航式三個子系統(tǒng)。這三個子系統(tǒng)的任務如果按照以前的靜態(tài)、動態(tài)算法實現(xiàn)需要系統(tǒng)開發(fā)人員設計很復雜的調(diào)度算法，實時控制也相對困難[3][4]。本文按照分層思想在實時操作系統(tǒng)層面上設計調(diào)度算法，減輕了解決此類問題系統(tǒng)開發(fā)人員的負擔，算法的主要思想是：修改內(nèi)核的任務控制塊，增加一個子模塊標識來控制分層調(diào)度，采用固

定時間輪轉(zhuǎn)算法調(diào)度各子系統(tǒng)模塊，子系統(tǒng)中的任務按照速率單調(diào)算法調(diào)度，從而實現(xiàn)兩層的調(diào)度策略。本文首先定義了分層調(diào)度系統(tǒng)的模型，并對分層調(diào)度算法的可調(diào)度性進行了理論分析；其次，以實時內(nèi)核μC/OS-Ⅱ為背景，實現(xiàn)了具有分層調(diào)度功能的調(diào)度器，最后通過實驗驗證分層調(diào)度算法的可行性和正確性。

1 分層調(diào)度系統(tǒng)模型的定義

定義1 在不考慮釋放抖動的情況下，一個任務集Τ={τ1,τ2,…, τn}中的任務τi 的屬性可以用一個五元組（Mi， ,Pi,Di, Ei）來表示。其中，Mi 表示任務屬于的模塊； 是相位；Pi 表示任務周期，對于非周期任務，取其最小時間間隔作為周期；Di 表示任務完成

的最后期限；Ei 表示任務的最大請求運行時間。

在定義任務屬性時，擴展以前任務描述的四元組到五元組[5]，增加了任務所屬模塊的屬性，這一點是為了給子模塊的索引表提供一個標志，以便實現(xiàn)任務集按子模塊分層調(diào)度管理。

定義2 對于任務τi，其各實例從到達時刻至執(zhí)行完成時刻之間的時間間隔稱為該實例的響應時間,各實例響應時間的最大值稱為任務τi的最大響應時間 Ri，若 Ri≤Di，則稱任務τi可調(diào)度。

2 分層調(diào)度算法模型的實現(xiàn)

2．1分層模型的可調(diào)度性分析

假定：系統(tǒng)中具有n個獨立的，可搶占的任務，并且任務的相對時限等于各自的周期。如果系統(tǒng)的總利用率U滿足下式：

(該子系統(tǒng)模塊1中的任務在最壞的情況下，完成任務的時間分別為：
R11=RL-1+E1=2+0.5=2.5
R12=2*RL-1-(1-E1)+E2=5-0.5+1.2=5.7
R13=3*RL-1-(2-E1-E2)+E3+E1=9-1-0.3+0.8-0.5=9

而按照分層模型可調(diào)度性公式(2.2a)迭代計算可知Rij最大響應時間分別如下：

R11(max):初始預設值為t(1)=0.5（即任務的執(zhí)行時間）,用該值替代t，發(fā)現(xiàn)公式(2.2a)左邊等于0.5，但右邊為0，不滿足公式(2.2a),第二次迭代中，t(2)＝ =3,經(jīng)計算發(fā)現(xiàn)針對該t值，公式(2.2a)成立，因此T11的最大響應時間為3，依次可計算第一個子模塊中其它兩個任務的最大響應時間分別為 R12(max)＝6，R13(max)＝9。

由此可知系統(tǒng)在分層調(diào)度情況下，子模塊M1中的任務最壞情況下的調(diào)度能在最大響應時間內(nèi)運行完畢。同理，對其它2個模塊中的任務逐個檢驗它的可調(diào)度條件，可判別出子系統(tǒng)模塊中的任務在最壞情況下的調(diào)度能滿足最大響應時間的要求，從而保證分層情況下任務的可調(diào)度性。

2．2 實現(xiàn)分層調(diào)度的μC/OS-Ⅱ內(nèi)核結(jié)構(gòu)修改和擴展

為了實現(xiàn)分層調(diào)度，需要修改和擴展μC/OS-Ⅱ內(nèi)核結(jié)構(gòu)。創(chuàng)建一個模塊控制塊MCB，以此作為模塊標識，將屬于同一模塊的任務TCB掛在同一模塊任務鏈上，在調(diào)度過程中，子模塊按固定時間輪轉(zhuǎn)調(diào)度，子模塊中任務的調(diào)度仍然保持μC/OS-Ⅱ按優(yōu)先級的搶占式調(diào)度策略按RM調(diào)度算法進行。為實現(xiàn)分層任務的級聯(lián)查找，需要創(chuàng)建兩級索引表，一級指向子模塊，另一級索引子模塊中的任務，原內(nèi)核結(jié)構(gòu)如圖2所示，改進后的內(nèi)核結(jié)構(gòu)如圖3所示。

具體的調(diào)度算法如下 ：
OS_Layered_Sched(){
OSMCBRdy = "Get a ready submode";/* 控制塊就緒指針指向一個子模塊*/
if ( OSMCBGetCycle_Piece = =ture ) {/*子模塊得到固定時間分配。*/
if (MCBTb[].TaskTcb[].Rdy==ture) /*查看其中是否有就緒的任務，如果有，則調(diào)度*/
{OS_ENTER_CRITICAL();
OS_PRIOCYCLE_RDY =(INT8U)(z+(y<<3+)+OS_UnMapTb1[OSRdyTb1[y]];
 /* z是用來確定模塊的地址*/     OS_sched(); 
OS_EXIT_CRITICAL()}
else {
   if( MCBTb!= MCBTb[n]) /*判斷是否到了最后一個子模塊*/
{ MCBTb= MCBTb->next;  }/*是，指向下一個子模塊，否，指針回到第一個子模塊*/
Else
{ MCBTb = MCBTb[1] }
}
}

3、實驗仿真及結(jié)果分析

移植μC/OS- Ⅱ?qū)崟r操作系統(tǒng)到PC機上，以BC++4.5為開發(fā)平臺，完成分層調(diào)度算法下任務的調(diào)度執(zhí)行，結(jié)果如圖4所示。

實驗結(jié)果顯示，改進后的算法可以實現(xiàn)分層子模塊中任務的調(diào)度，調(diào)度器運轉(zhuǎn)正常，證明了分層調(diào)度算法的可行性。在執(zhí)行多次后，如有任務完成，它就脫離原來的鏈，重新調(diào)整兩級索引表，并按調(diào)整后的兩級索引表引起新的調(diào)度。

本算法存在的問題是任務切換的頻繁次數(shù)增加，增大了調(diào)度的時間開銷，表1是對圖1的任務集在分層前后的調(diào)度運行時任務切換次數(shù)的比較。

表1 分層調(diào)度前、后的任務切換次數(shù)對比分析表

4、結(jié)束語

本文作者創(chuàng)新點：通過重構(gòu)μC/OS-Ⅱ內(nèi)核結(jié)構(gòu)和改進其調(diào)度器，達到了μC/OS-Ⅱ支持分層調(diào)度的設計目標，其調(diào)度功能得到了擴展和加強。改進的μC/OS-Ⅱ內(nèi)核支持兩級的分層調(diào)度，在不改變原μC/OS-Ⅱ內(nèi)核搶占式內(nèi)核特征下實現(xiàn)了子系統(tǒng)模塊的固定時間分配方案的調(diào)度策略，使得μC /OS-Ⅱ內(nèi)核有能力支撐更為復雜的實時應用。理論分析和實驗認證證明了擴展μC/OS-Ⅱ內(nèi)核功能方法的正確性和有效性。

參考文獻：
[1]WilliamL.Preemption-threshold. White Paper[Z].Express Logic Inc. 1992.
[2] Wang Y, Saksena M. Scheduling Fixed Priority Tasks with PreemptionThreshold[C]. Proceeding of 6th IEEE Real-time Computing Systemsand Applications Symposium, Hong Kong, 1999: 328-335.
[3]楊博，陳志剛. 一種基于雙層進化結(jié)構(gòu)的網(wǎng)格任務調(diào)度算[J].計算機工程與應用, 2006(15):4-7.
[4]劉衛(wèi)，程明霄王曉榮. 實時系統(tǒng)優(yōu)先級位圖調(diào)度算法的改進[J].微計算機信息程,2007,23(2):155-157.
[5] Mok,A.K.-L.,and D.Chen,“A multiframe model for real-time,”Proceedings of IEEE Real-time Systems Symposium,December, 1996.