張永悅，孫 瑜，李 允，徐建華

(1.云南師范大學(xué)信息學(xué)院，昆明 650500；2.西南交通大學(xué)信息科學(xué)與技術(shù)學(xué)院，成都 610031；3.電子科技大學(xué)計算機(jī)科學(xué)與工程學(xué)院，成都 610054)

1 概述

隨著計算機(jī)技術(shù)的飛速發(fā)展，嵌入式系統(tǒng)已廣泛應(yīng)用于各科技領(lǐng)域及日常生活的每個角落。為了滿足航空航天等關(guān)鍵領(lǐng)域的嵌入式系統(tǒng)強(qiáng)實(shí)時性的要求、精確管理系統(tǒng)時間資源，在系統(tǒng)設(shè)計階段采取相應(yīng)的方法，對系統(tǒng)任務(wù)集進(jìn)行可調(diào)度性判定相當(dāng)必要。因而，自動化、精準(zhǔn)化、高效化判定工具的開發(fā)頗具意義。為此，本文提出一種基于仿真方法的任務(wù)集可調(diào)度性判定工具，用來判定任務(wù)集是否具備可調(diào)度性。

2 調(diào)度理論的相關(guān)研究

2.1 調(diào)度模型

在任務(wù)集可調(diào)度性判定的相關(guān)研究中，通常所提及的調(diào)度模型是一種理想的調(diào)度模型，其必備的要素有：調(diào)度策略，任務(wù)屬性參數(shù)(執(zhí)行時間、截止時間限、周期/非周期觸發(fā)方式)等[1-2]。

隨著航空電子應(yīng)用軟件標(biāo)準(zhǔn)接口的制定[3]，分區(qū)調(diào)度模型的相關(guān)研究逐漸成為調(diào)度理論研究的熱點(diǎn)。相比普通調(diào)度模型，分區(qū)調(diào)度模型增加了分區(qū)時間片的約束。分區(qū)系統(tǒng)中系統(tǒng)時間資源被劃分成多個分區(qū)，特定的分區(qū)下運(yùn)行指定的任務(wù)集，任務(wù)集只有在所在分區(qū)獲取時間片后才能調(diào)度執(zhí)行，時間片用完后等待下一次時間片的獲得。

2.2 可調(diào)度性判定方法

在當(dāng)前的階段，可調(diào)度性判定工具主要采用形式化(時間自動機(jī))方法和仿真方法實(shí)現(xiàn)。前者依據(jù)窮盡搜索的方法實(shí)現(xiàn)，存在狀態(tài)空間爆炸問題，調(diào)度能力有限；后者則采用仿真執(zhí)行過程的方法實(shí)現(xiàn)，判定效率較高，但只能分析擁有確定調(diào)度搶占過程任務(wù)集的可調(diào)度性，適用于純周期任務(wù)集可調(diào)度性判定工具的實(shí)現(xiàn)。

2.3 復(fù)雜實(shí)時系統(tǒng)的可調(diào)度性判定

2.3.1 復(fù)雜實(shí)時系統(tǒng)調(diào)度模型

基于上述研究，結(jié)合現(xiàn)階段復(fù)雜嵌入式系統(tǒng)的特性，提出一種復(fù)雜實(shí)時系統(tǒng)混合調(diào)度模型的可調(diào)度性判定工具。該混合調(diào)度模型是一種多處理器的系統(tǒng)構(gòu)架，系統(tǒng)中可以含有多個處理器，各個處理器可掛載不同的任務(wù)結(jié)構(gòu)，如分區(qū)任務(wù)集合、普通任務(wù)集合?；旌险{(diào)度模型如圖1所示。

圖1 復(fù)雜調(diào)度模型圖示

2.3.2 可調(diào)度性判定依據(jù)

上述混合調(diào)度模型包含普通調(diào)度模型和分區(qū)調(diào)度模型，且約定每種調(diào)度模型下的任務(wù)都是周期任務(wù)。文獻(xiàn)[4]給出了純周期任務(wù)集的特性及相關(guān)證明：純周期任務(wù)集合中所有任務(wù)都是周期任務(wù)，每個任務(wù)的到達(dá)都成周期性，所有任務(wù)的到達(dá)在整體上也呈現(xiàn)周期性，周期值為所有任務(wù)周期值的最小公倍數(shù)。

現(xiàn)階段可調(diào)度性判定過程中，主要針對2類調(diào)度策略進(jìn)行研究：靜態(tài)優(yōu)先級調(diào)度策略和動態(tài)優(yōu)先級調(diào)度策略。并約定當(dāng)采用這2種調(diào)度策略計算任務(wù)優(yōu)先級過程中遇到多個任務(wù)優(yōu)先級相同時，設(shè)計者自定義二級調(diào)度策略區(qū)分任務(wù)的優(yōu)先級。本文約定當(dāng)出現(xiàn)優(yōu)先級相同時，任務(wù)列表中編號小的任務(wù)優(yōu)先級高，這樣便唯一確定了任務(wù)的搶占方式及搶占順序。

由上述結(jié)論可知，普通調(diào)度模型下任務(wù)集中所有任務(wù)在調(diào)度過程中的到達(dá)、搶占、執(zhí)行、完成是一個確定的路徑且整體上呈周期性，周期值為所有任務(wù)周期值的最小公倍數(shù)(mul)。同理，分區(qū)調(diào)度模型的周期值為所有任務(wù)周期值與任務(wù)集所屬分區(qū)獲取時間片的周期值的最小公倍數(shù)(mulpart)。此時，只需分析一個周期值時鐘區(qū)域內(nèi)任務(wù)集的調(diào)度情況，即可等價判定任務(wù)集整個調(diào)度過程的可調(diào)度性。因此，采用仿真方法判定含有純周期任務(wù)集的混合調(diào)度模型的可調(diào)度性是可行的、確定的。

2.3.3 仿真實(shí)現(xiàn)過程

定義變量X為系統(tǒng)時鐘，設(shè)置一個周期的仿真區(qū)域。當(dāng)待分析的處理器下掛載普通調(diào)度模型時，默認(rèn)任務(wù)集中所有任務(wù)都在0時刻到達(dá)，系統(tǒng)時鐘從0時刻開始計時，并以步長為一個時間單位增加系統(tǒng)時鐘值，模擬任務(wù)集的調(diào)度過程，系統(tǒng)時鐘的仿真區(qū)間為[0,mul]。當(dāng)待分析的處理器下掛載分區(qū)調(diào)度模型時，默認(rèn)當(dāng)前處理器中所有分區(qū)下的所有任務(wù)都在所屬分區(qū)第一次獲得系統(tǒng)時間片的時刻到達(dá)，系統(tǒng)時鐘區(qū)域長度為 mulpart。針對上述 2種調(diào)度模型，在模擬過程中系統(tǒng)時鐘每增加一個時間單位，根據(jù)任務(wù)到達(dá)、搶占的情況更新所有任務(wù)的執(zhí)行時鐘、響應(yīng)時鐘、狀態(tài)，依據(jù)任務(wù)超時條件判定任務(wù)的可調(diào)度性，從而判定任務(wù)集的可調(diào)度性。

3 核心實(shí)現(xiàn)及性能分析

3.1 工具整體框架

本文研究的復(fù)雜調(diào)度模型的可調(diào)度性判定工具包含3個主要功能模塊：調(diào)度模型編輯模塊，調(diào)度結(jié)果判定顯示模塊，調(diào)度過程的甘特圖顯示模塊。調(diào)度模型編輯模塊提供用戶自定義調(diào)度模型的建立。調(diào)度結(jié)果判定顯示模塊能自動提取用戶輸入的調(diào)度模型參數(shù)及調(diào)度策略，調(diào)用相應(yīng)的判定算法，自動、準(zhǔn)確、快速地給出任務(wù)的可調(diào)度性判定結(jié)果及所有任務(wù)的最壞響應(yīng)時間。調(diào)度過程顯示模塊實(shí)現(xiàn)了以甘特圖的方式單步或連續(xù)地模擬顯示任務(wù)集的調(diào)度過程，便于驗證工具判定結(jié)果的正確性。

該工具支持的調(diào)度策略有：單調(diào)速率調(diào)度策略(Rate Monotonic Scheduling, RMS)，短截止時間限優(yōu)先策略(Deadline Monotonic Scheduling, DMS)，固定優(yōu)先級調(diào)度策略(Fixed Priority Scheduling, FPS)，相對短截止時間限優(yōu)先策略(Earliest Deadline First,EDF)。其中，前3種為靜態(tài)優(yōu)先級搶占策略，最后一種為動態(tài)優(yōu)先級搶占策略。工具的整體結(jié)構(gòu)框圖如圖2所示。

圖2 可調(diào)度性判定工具的結(jié)構(gòu)框圖

3.2 任務(wù)模型

定義 T = {t1, t2,… ,tn}為一個含有n個周期任務(wù)的任務(wù)集，任務(wù)由 ti=(Ci, Ti, Di, Ei, Wi, Li, P)表示。其中，Ci為任務(wù)ti的執(zhí)行時間；Ti為任務(wù)的周期；Di為任務(wù)的截止時間；Ei為任務(wù)ti的執(zhí)行時鐘，只有當(dāng)任務(wù)處于運(yùn)行狀態(tài)時，執(zhí)行時鐘才開始計時；Wi為任務(wù)ti的響應(yīng)時鐘，當(dāng)任務(wù)請求到達(dá)時，響應(yīng)時鐘開始計時，直到任務(wù)執(zhí)行完成；Li為任務(wù)ti的當(dāng)前狀態(tài)，所有任務(wù)在調(diào)度過程中都有4個狀態(tài)：掛起(Suspend)，就緒(Ready)，執(zhí)行(Running)，超時(Error)。

當(dāng)任務(wù)所在系統(tǒng)為分區(qū)系統(tǒng)時，P為任務(wù)所在分區(qū)。 P =(P t, P c, o ffset )，其中，Pt為分區(qū)獲取系統(tǒng)時間片的周期；Pc為分區(qū)獲取時間片的長度；offset為分區(qū)第一次獲取時間片的系統(tǒng)時鐘偏移量。

任務(wù)ti在調(diào)度時的狀態(tài)遷移過程(默認(rèn)任務(wù)集中編號小的任務(wù)優(yōu)先級高)如圖3所示。

圖3 任務(wù)狀態(tài)轉(zhuǎn)換圖

圖3中任務(wù)搶占時的狀態(tài)遷移描述如下：

(1)Readyi->Runningi描述任務(wù)ti由就緒態(tài)遷移到運(yùn)行態(tài)。本文研究的復(fù)雜調(diào)度模型中包含普通調(diào)度模型和分區(qū)調(diào)度模型。針對分區(qū)調(diào)度模型，當(dāng)任務(wù)所在分區(qū)獲取系統(tǒng)時間片(即 PartObtainSystem Time為真)，并且所有比此任務(wù)優(yōu)先級高的任務(wù)都未到達(dá)時，該任務(wù)獲取 CPU資源，遷移到運(yùn)行狀態(tài)開始執(zhí)行。針對普通調(diào)度模型時，默認(rèn)任務(wù)集永遠(yuǎn)占有 CPU資源，遷移條件與分區(qū)調(diào)度模型相同，只需設(shè)定PartObtainSystemTime始終為真即可。

(2)Runningi->Readyi描述任務(wù)ti由運(yùn)行態(tài)遷移到就緒態(tài)。分區(qū)調(diào)度模型下任務(wù)ti執(zhí)行過程中，所在分區(qū)未獲得系統(tǒng)時間片用完時(即 PartObtain SystemTime為假時)，或者同分區(qū)下較高優(yōu)先級任務(wù)到達(dá)時，當(dāng)前任務(wù)轉(zhuǎn)向就緒狀態(tài)，釋放 CPU資源。普通調(diào)度模型的遷移條件與分區(qū)調(diào)度模型相同，只需設(shè)定PartObtainSystemTime始終為真即可。

3.3 可調(diào)度性判定算法

分區(qū)任務(wù)集可調(diào)度性判定算法如下：

輸入 任務(wù)集合列表 TaskList[n]，任務(wù)所在分區(qū)獲取時間片的相關(guān)屬性

輸出 任務(wù)集可調(diào)度性isScheduler(true, false)；任務(wù)最壞響應(yīng)時間列表TaskWT[n]

步驟 1 初始化任務(wù)集合列表中所有任務(wù)的參數(shù)(執(zhí)行時鐘、響應(yīng)時鐘、系統(tǒng)時鐘、任務(wù)狀態(tài))，計算分區(qū)任務(wù)集的仿真區(qū)間長度mulpart。

步驟 2 將任務(wù)集合列表中的任務(wù)按優(yōu)先級從高到低排序，sort(TaskList[n])。

步驟 3 判定當(dāng)前系統(tǒng)時鐘 X時刻，任務(wù)集可調(diào)度性：

(1)判定任務(wù)列表中當(dāng)前任務(wù)ti的可調(diào)度性

1)更新當(dāng)前任務(wù)ti的狀態(tài)Li、執(zhí)行時鐘Ei、響應(yīng)時鐘Wi：

①如果 Li== "Suspend"&& X %Ti== 0，任務(wù)到達(dá)，狀態(tài)遷移時鐘計時( Li= "Ready",Wi++)。

②如果ti處于就緒狀態(tài)( Li= "Ready")，任務(wù)獲取時間片(PartObtainSystemTime==true)，并且所有較ti優(yōu) 先 級 高 的 任 務(wù) 都 未 到 達(dá) 時( ?j = 1,2 … ,i ?1,Lj== "Suspend")，ti開始運(yùn)行，狀態(tài)遷移時鐘計時( Li= "Running",Ei++,Wi++)。

③如果 Li== "Running"，任意一個較ti優(yōu)先級高的任務(wù)到達(dá)時( ?j = 1,2,… ,i ? 1,Lj=="Ready")，或者Part ObtainSystemTime==false時，任務(wù)ti由運(yùn)行態(tài)轉(zhuǎn)向就緒態(tài)( Li= "Ready",Wi++)。

④如果 Li== "Error"，當(dāng)前任務(wù)不可調(diào)度，任務(wù)集不可調(diào)度(isScheduler=false)，跳轉(zhuǎn)到步驟5。

2)如果ti執(zhí)行完成( Ei== Ci&&Wi＜= Di)，時鐘清零，計算任務(wù)響應(yīng)時間，比較以往所有次響應(yīng)時間，將最大值存入TaskWT[i]中。

3)如果ti超時( Ei＜ Ci&&Wi== Di)，ti不可調(diào)度，任務(wù)集合不可調(diào)度，設(shè)置isScheduler=false，跳轉(zhuǎn)到步驟5，否則跳轉(zhuǎn)到(2)。

(2)i++，如果 i>n，跳轉(zhuǎn)到步驟 4，否則，跳轉(zhuǎn)到(1)。

步驟 4 如果任務(wù)集采用動態(tài)優(yōu)先級調(diào)度策略(EDF)，重新排序任務(wù)集合 sort(TaskList[n])；X++，如果X>mulpart，跳轉(zhuǎn)到步驟5，否則，繼續(xù)步驟3。

步驟5 如果isScheduler==true，輸出任務(wù)集可調(diào)度、輸出任務(wù)集最壞響應(yīng)時間列表TaskWT[n]；否則，輸出任務(wù)集不可調(diào)度，判定過程結(jié)束。

上述判定算法的時間復(fù)雜度為 O(taskNum×mulpart)，將上述算法中系統(tǒng)時鐘仿真上限更改為mul，設(shè)定PartObtainSystemTime參數(shù)始終為真值時，即變更為普通模型可調(diào)度性判定算法。

3.4 工具性能分析

該工具的判定效率數(shù)據(jù)在簡單調(diào)度模型判定工具文獻(xiàn)中詳細(xì)列舉。文獻(xiàn)[5-8]也分別對RMS及EDF調(diào)度策略下任務(wù)集可調(diào)度性判定算法進(jìn)行研究，但均未涉及分區(qū)約束。文獻(xiàn)[9-10]對分區(qū)調(diào)度算法進(jìn)行了相關(guān)研究，提出了合理利用空閑時間片的方法，但并未過多涉及分區(qū)調(diào)度模型的可調(diào)度性判定問題。

相比上述文獻(xiàn)的相關(guān)研究，本文的可調(diào)度性判定工具提供更友好的用戶操作界面；更強(qiáng)的復(fù)雜模型判定仿真能力，能判定單處理器、多處理器、多分區(qū)之間任意組合的調(diào)度模型，適用于復(fù)雜嵌入式系統(tǒng)的需要。

4 實(shí)例分析

假定待判定系統(tǒng)含有2個處理器CPU1和CPU2。CPU1下掛載分區(qū)調(diào)度模型，模型中包含3個分區(qū)，每個分區(qū)下掛載各自的任務(wù)集合；CPU2下掛載普通調(diào)度模型。

CPU1下3個分區(qū)獲取時間片情況如表1所示。各分區(qū)下掛載的任務(wù)集合、調(diào)度策略、任務(wù)屬性參數(shù)如表2所示。CPU2下掛載普通調(diào)度模型，調(diào)度模型中任務(wù)的屬性參數(shù)、調(diào)度策略如表3所示。

表1 CPU1下分區(qū)時間片分派情況

表2 CPU1下各分區(qū)掛載任務(wù)的屬性參數(shù)

表3 CPU2下任務(wù)集中任務(wù)屬性參數(shù)

圖4描述了上述系統(tǒng)中2個處理器下所有調(diào)度單元的調(diào)度結(jié)果及甘特圖仿真結(jié)果。結(jié)果顯示，CPU1中分區(qū) PART1下的任務(wù)集可調(diào)度，各任務(wù)的最壞響應(yīng)時間分別為6、7、6；分區(qū)PART2下任務(wù)集可調(diào)度，各任務(wù)的最壞響應(yīng)時間分別為 3、34；分區(qū) PART3下的任務(wù)集合不可調(diào)度，任務(wù)執(zhí)行過程超時。CPU2下任務(wù)集可調(diào)度，任務(wù)集中3個任務(wù)的最壞響應(yīng)時間分別是 3、4、8。

圖4 復(fù)雜調(diào)度模型的可調(diào)度性判定及甘特圖仿真結(jié)果

對比各調(diào)度模塊下的甘特圖仿真結(jié)果可知，可調(diào)度性判定工具的分析結(jié)果準(zhǔn)確無誤。該甘特圖仿真結(jié)果驗證了純周期任務(wù)集的特性、動態(tài)優(yōu)先級搶占策略EDF的特性、分區(qū)調(diào)度模型的特性。如：CPU2下任務(wù)集調(diào)度的甘特圖仿真結(jié)果顯示，在區(qū)間[0,60]與區(qū)間[60,120]中任務(wù)集的調(diào)度過程完全一致，滿足純周期任務(wù)集的特性；CPU1中分區(qū) PART1下任務(wù)集及CPU2下任務(wù)集調(diào)度的甘特圖仿真結(jié)果，準(zhǔn)確無誤地顯示了不同時刻下各個任務(wù)的優(yōu)先級動態(tài)變化情況；CPU1中分區(qū)PART1、PART2、PART3中任務(wù)集調(diào)度的甘特圖仿真結(jié)果同樣顯示了分區(qū)調(diào)度模型的特性，分區(qū)下的任務(wù)只有在所屬分區(qū)獲取時間片的時鐘區(qū)域內(nèi)調(diào)度執(zhí)行，在調(diào)度過程中當(dāng)所在分區(qū)時間片用完時，只有等待分區(qū)下一次獲取時間片時才能繼續(xù)任務(wù)執(zhí)行過程。

5 結(jié)束語

本文基于仿真方法實(shí)現(xiàn)了含有多處理器、多分區(qū)復(fù)雜實(shí)時系統(tǒng)的可調(diào)度性判定工具，闡述了工具核心模塊構(gòu)成及核心算法的實(shí)現(xiàn)過程，并通過實(shí)例驗證了工具的可調(diào)度性判定結(jié)果和仿真過程的正確性。涉及分區(qū)間任務(wù)搶占、多處理器之間存在觸發(fā)關(guān)系的模型調(diào)度問題是下一步的工作重點(diǎn)。

[1]Liu C L, Layland J W.Scheduling Algorithms for Multiprogramming in a Hard Real Time Environment[J].Journal of the ACM, 1973, 20(1): 46-61.

[2]王永吉, 陳秋萍.單調(diào)速率及其擴(kuò)展算法的可調(diào)度性判定[J].軟件學(xué)報, 2004, 15(6): 799-814.

[3]Airlines Electronic Engineering Committee.ARINC 653P1-3-2010 Avionics Application Software Standard Interface Part1——Required Services[S].2006.

[4]Leung J Y T, Merrill M L.A Note on Preemptive Scheduling of Periodic, Real-time Tasks[J].Information Processing Letters, 1980, 11(3): 115-118.

[5]劉軍祥, 王永吉, Cartmell M.一種改進(jìn)的RM可調(diào)度性判斷算法[J].軟件學(xué)報, 2005, 16(1): 89-100.

[6]刁 承, 虞慧群.改進(jìn)的單調(diào)速率調(diào)度算法[J].計算機(jī)科學(xué)與探索, 2011, 5(6): 562-568.

[7]李 琦, 巴 巍.兩種改進(jìn)的 EDF軟實(shí)時動態(tài)調(diào)度算法[J].計算機(jī)學(xué)報, 2011, 34(5): 943-950.

[8]張 杰, 陽富民, 盧炎生, 等.EDF統(tǒng)一調(diào)度硬實(shí)時周期任務(wù)和偶發(fā)任務(wù)的可調(diào)度性判定算法[J].小型微型計算機(jī)系統(tǒng), 2009, 30(12): 2383-2388.

[9]何 峰, 宋麗茹, 熊華鋼.航空電子雙層任務(wù)分區(qū)調(diào)度設(shè)計[J].北京航空航天大學(xué)學(xué)報, 2008, 34(11): 1364-1368.

[10]李昕穎, 顧 健, 何 峰, 等.硬實(shí)時系統(tǒng)在強(qiáng)分區(qū)約束下的雙層分區(qū)調(diào)度[J].計算機(jī)學(xué)報, 2010, 33(6):1032-1039.