復雜實時系統可調度性判定工具的研究與實現

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

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

1 概述

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

2 調度理論的相關研究

2.1 調度模型

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

隨著航空電子應用軟件標準接口的制定[3]，分區調度模型的相關研究逐漸成為調度理論研究的熱點。相比普通調度模型，分區調度模型增加了分區時間片的約束。分區系統中系統時間資源被劃分成多個分區，特定的分區下運行指定的任務集，任務集只有在所在分區獲取時間片后才能調度執行，時間片用完后等待下一次時間片的獲得。

2.2 可調度性判定方法

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

2.3 復雜實時系統的可調度性判定

2.3.1 復雜實時系統調度模型

基于上述研究，結合現階段復雜嵌入式系統的特性，提出一種復雜實時系統混合調度模型的可調度性判定工具。該混合調度模型是一種多處理器的系統構架，系統中可以含有多個處理器，各個處理器可掛載不同的任務結構，如分區任務集合、普通任務集合?；旌险{度模型如圖1所示。

圖1 復雜調度模型圖示

2.3.2 可調度性判定依據

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

現階段可調度性判定過程中，主要針對2類調度策略進行研究：靜態優先級調度策略和動態優先級調度策略。并約定當采用這2種調度策略計算任務優先級過程中遇到多個任務優先級相同時，設計者自定義二級調度策略區分任務的優先級。本文約定當出現優先級相同時，任務列表中編號小的任務優先級高，這樣便唯一確定了任務的搶占方式及搶占順序。

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

2.3.3 仿真實現過程

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

3 核心實現及性能分析

3.1 工具整體框架

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

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

圖2 可調度性判定工具的結構框圖

3.2 任務模型

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

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

任務ti在調度時的狀態遷移過程(默認任務集中編號小的任務優先級高)如圖3所示。

圖3 任務狀態轉換圖

圖3中任務搶占時的狀態遷移描述如下：

(1)Readyi->Runningi描述任務ti由就緒態遷移到運行態。本文研究的復雜調度模型中包含普通調度模型和分區調度模型。針對分區調度模型，當任務所在分區獲取系統時間片(即 PartObtainSystem Time為真)，并且所有比此任務優先級高的任務都未到達時，該任務獲取 CPU資源，遷移到運行狀態開始執行。針對普通調度模型時，默認任務集永遠占有 CPU資源，遷移條件與分區調度模型相同，只需設定PartObtainSystemTime始終為真即可。

(2)Runningi->Readyi描述任務ti由運行態遷移到就緒態。分區調度模型下任務ti執行過程中，所在分區未獲得系統時間片用完時(即 PartObtain SystemTime為假時)，或者同分區下較高優先級任務到達時，當前任務轉向就緒狀態，釋放 CPU資源。普通調度模型的遷移條件與分區調度模型相同，只需設定PartObtainSystemTime始終為真即可。

3.3 可調度性判定算法

分區任務集可調度性判定算法如下：

輸入 任務集合列表 TaskList[n]，任務所在分區獲取時間片的相關屬性

輸出 任務集可調度性isScheduler(true, false)；任務最壞響應時間列表TaskWT[n]

步驟 1 初始化任務集合列表中所有任務的參數(執行時鐘、響應時鐘、系統時鐘、任務狀態)，計算分區任務集的仿真區間長度mulpart。

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

步驟 3 判定當前系統時鐘 X時刻，任務集可調度性：

(1)判定任務列表中當前任務ti的可調度性

1)更新當前任務ti的狀態Li、執行時鐘Ei、響應時鐘Wi：

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

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

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

④如果 Li== "Error"，當前任務不可調度，任務集不可調度(isScheduler=false)，跳轉到步驟5。

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

3)如果ti超時( Ei＜ Ci&&Wi== Di)，ti不可調度，任務集合不可調度，設置isScheduler=false，跳轉到步驟5，否則跳轉到(2)。

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

步驟 4 如果任務集采用動態優先級調度策略(EDF)，重新排序任務集合 sort(TaskList[n])；X++，如果X>mulpart，跳轉到步驟5，否則，繼續步驟3。

步驟5 如果isScheduler==true，輸出任務集可調度、輸出任務集最壞響應時間列表TaskWT[n]；否則，輸出任務集不可調度，判定過程結束。

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

3.4 工具性能分析

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

相比上述文獻的相關研究，本文的可調度性判定工具提供更友好的用戶操作界面；更強的復雜模型判定仿真能力，能判定單處理器、多處理器、多分區之間任意組合的調度模型，適用于復雜嵌入式系統的需要。

4 實例分析

假定待判定系統含有2個處理器CPU1和CPU2。CPU1下掛載分區調度模型，模型中包含3個分區，每個分區下掛載各自的任務集合；CPU2下掛載普通調度模型。

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

表1 CPU1下分區時間片分派情況

表2 CPU1下各分區掛載任務的屬性參數

表3 CPU2下任務集中任務屬性參數

圖4描述了上述系統中2個處理器下所有調度單元的調度結果及甘特圖仿真結果。結果顯示，CPU1中分區 PART1下的任務集可調度，各任務的最壞響應時間分別為6、7、6；分區PART2下任務集可調度，各任務的最壞響應時間分別為 3、34；分區 PART3下的任務集合不可調度，任務執行過程超時。CPU2下任務集可調度，任務集中3個任務的最壞響應時間分別是 3、4、8。

圖4 復雜調度模型的可調度性判定及甘特圖仿真結果

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

5 結束語

本文基于仿真方法實現了含有多處理器、多分區復雜實時系統的可調度性判定工具，闡述了工具核心模塊構成及核心算法的實現過程，并通過實例驗證了工具的可調度性判定結果和仿真過程的正確性。涉及分區間任務搶占、多處理器之間存在觸發關系的模型調度問題是下一步的工作重點。

[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]王永吉, 陳秋萍.單調速率及其擴展算法的可調度性判定[J].軟件學報, 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.一種改進的RM可調度性判斷算法[J].軟件學報, 2005, 16(1): 89-100.

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

[7]李 琦, 巴 巍.兩種改進的 EDF軟實時動態調度算法[J].計算機學報, 2011, 34(5): 943-950.

[8]張 杰, 陽富民, 盧炎生, 等.EDF統一調度硬實時周期任務和偶發任務的可調度性判定算法[J].小型微型計算機系統, 2009, 30(12): 2383-2388.

[9]何 峰, 宋麗茹, 熊華鋼.航空電子雙層任務分區調度設計[J].北京航空航天大學學報, 2008, 34(11): 1364-1368.

[10]李昕穎, 顧 健, 何 峰, 等.硬實時系統在強分區約束下的雙層分區調度[J].計算機學報, 2010, 33(6):1032-1039.