陳平等

摘 要： 實時調(diào)度算法是嵌入式系統(tǒng)的核心組成部分，高效的調(diào)度算法能增強系統(tǒng)的實時性和可靠性，ARINC653標準已經(jīng)廣泛地應(yīng)用于綜合航空電子系統(tǒng)中。首先介紹了幾種實時調(diào)度算法，從滿足ARINC653標準的角度出發(fā)，選取近幾年的雙層調(diào)度算法進行綜述，討論了現(xiàn)有的雙層調(diào)度模型和雙層調(diào)度算法，不同的分區(qū)間與分區(qū)內(nèi)的調(diào)度算法組合會產(chǎn)生不同的效果。通過對各種雙層模型和算法的比較與分析給出了各自的優(yōu)缺點，對常用調(diào)度分析工具進行了敘述，以供設(shè)計和分析人員選擇。最后，分析了雙層調(diào)度算法有待深入研究的難點，并對其發(fā)展趨勢進行展望。

關(guān)鍵詞： 實時算法； 雙層調(diào)度； ARINC653； 嵌入式系統(tǒng)

中圖分類號： TN911?34 文獻標識碼： A 文章編號： 1004?373X（2015）12?0029?04

0 引 言

嵌入式系統(tǒng)被廣泛地使用在諸多對安全要求的行業(yè)。嵌入式系統(tǒng)在規(guī)模上已發(fā)生重大改變，在航空領(lǐng)域，嵌入式系統(tǒng)由聯(lián)合式發(fā)展到目前的高度綜合化、模塊化的航空電子系統(tǒng)（Integrated Modular Avionics， IMA）。也就是說，軟件的規(guī)模變大，復雜度增加。因此，為了確保軟件的可靠性，模型驅(qū)動結(jié)構(gòu)方法（MDA）應(yīng)運而生，MDA的核心思想用模型抽象現(xiàn)實將模型與現(xiàn)實分離，通過模型來對系統(tǒng)進行開發(fā)和維護。在軟件設(shè)計階段就可以通過對模型的驗證發(fā)現(xiàn)潛在錯誤，以此來提高系統(tǒng)的可靠性。

針對嵌入式軟件存在的問題，美國SAE組織給出了一種建立在MDA思想上的建模語言。它就是體系結(jié)構(gòu)分析設(shè)計語言（Architecture Analysis and Design Language，AADL），其支持對嵌入式系統(tǒng)軟硬件結(jié)構(gòu)及功能、非功能需求建模，并提供多種模型分析工具，可支持對系統(tǒng)模型的分析、驗證、測試和自動代碼生成等，并且可以針對特定領(lǐng)域進行擴展。AADL的語法相對簡單，具有很多的功能，并且具有很好的可擴展性。使基于AADL的MDA過程具有很好的應(yīng)用前景。ARINC653作為接口標準，已經(jīng)應(yīng)用于航空系統(tǒng)的設(shè)計中。在對航空系統(tǒng)的模型建立時要參照該標準的要求。文獻[1]將其定義了為航空電子計算機的操作系統(tǒng)和應(yīng)用程序軟件之間的通用的應(yīng)用/執(zhí)行（APEX）軟件接口。

近幾年來有不少學者都對實時調(diào)度算法進行了研究，已提出了多種算法和模型。本文重點關(guān)注嵌入式實時系統(tǒng)的調(diào)度性算法，首先介紹一些近年來較為新穎實用的實時調(diào)度算法，然后介紹滿足ARINC653標準的雙層調(diào)度算法，最后介紹幾種調(diào)度性工具，為使用者提供一個參考。

1 實時調(diào)度算法

因為實時調(diào)度算法是雙層調(diào)度算法的基礎(chǔ)，因此研究一些較為新穎的實時調(diào)度算法以備研究雙層調(diào)度算法時使用。在實時調(diào)度算法中，對于靜態(tài)調(diào)度來說，大都在RMS算法之上進行改進，而動態(tài)調(diào)度則是以最早截止時間優(yōu)先算法或最低松弛度優(yōu)先算法為主。在這些經(jīng)典的調(diào)度算法之上，業(yè)界提出以下若干新的實時調(diào)度算法。

文獻[2]提出基于RM和EDF的一種新的實時調(diào)度算法 SBRD（Schedule Based on Rate and Dead line） 。在SBRD中引入了重要性因子來描述任務(wù)的重要程度，引入緊急因子用來描述任務(wù)的緊急程度。在SBRD中對于調(diào)度優(yōu)先級由一對數(shù)值對決定。數(shù)值對包括2個元素priority和urgency，其中前者表示重要性因子，它不表示時間屬性，而是由用戶決定的，反應(yīng)用戶的要求。后者表示緊急性因子，它是一種動態(tài)因子，它會隨當前截止期限不同而不同。SBRD相比于與RM和 EDF算法，能更好地利用CUP資源，因為它能保證緊急任務(wù)優(yōu)先執(zhí)行、保證重要任務(wù)順利執(zhí)，因此它能更大程度上的滿足更多任務(wù)在截止期限之前被執(zhí)行。

文獻[3]給出了名為MLLF（Modified Least Laxity）調(diào)度算法。MLLF調(diào)度算法相對于最早截止時間優(yōu)先算法或最低松弛度優(yōu)先算法來說，它的適應(yīng)性更廣，其優(yōu)先級計算公式為di（t）-t-f[×]ei（t），f在0～1之間。若f為0，則MLLF調(diào)度算法退化為最早截止時間優(yōu)先算法，f=1，MLLF算法退化為最低松弛度優(yōu)先算法。MLLF只考慮周期任務(wù)，沒有對突發(fā)任務(wù)的實時調(diào)度進行考慮。另外要求周期任務(wù)不能有關(guān)聯(lián)并且獨自占用系統(tǒng)資源。

文獻[4]針對實時調(diào)度，針對在多任務(wù)的情況下優(yōu)先級較低的任務(wù)延遲問題，給出一種因優(yōu)先級較低而出現(xiàn)延遲任務(wù)的優(yōu)先級，周期性地與較高任務(wù)的優(yōu)先級互換的算法。該算法中，周期是固定的，選擇2個相互獨立的、優(yōu)先級不同的任務(wù)周期性地交換其優(yōu)先級，這樣在不同的周期內(nèi)原優(yōu)先級較低的任務(wù)的優(yōu)先級級別是不一樣的，這樣就能使優(yōu)先級較低的任務(wù)盡快的被執(zhí)行同時不影響較高優(yōu)先級任務(wù)的執(zhí)行。這樣做的好處是縮短優(yōu)先級較低任務(wù)的延遲時間，能夠使優(yōu)先級較低任務(wù)的實時性得到保障，因此能夠改善實時系統(tǒng)在執(zhí)行多任務(wù)時的整體性能。該算法以時間片輪轉(zhuǎn)算法為基礎(chǔ)，同時考慮了系統(tǒng)開銷和算法的靈活性。其不足之處在于固定時間片的長度，預先定義好任務(wù)的優(yōu)先級別并且不能同時進行多組任務(wù)的同時互換優(yōu)先級。

2 雙層調(diào)度

2.1 雙層調(diào)度算法概述

在IMA的架構(gòu)下，軟件被封裝于分區(qū)中。就分區(qū)這一概念而言它由2部分組成，一部分是空間分區(qū)，另一部分是時間分區(qū)。分區(qū)是進行調(diào)度、資源分配、隔離保護的單位。空間分區(qū)指各個分區(qū)的地址空間是不同的，使用存儲管理器（Memory Manage Unit）將虛擬地址映射到物理地址，使分區(qū)的物理存儲空間相互隔離，不被其他分區(qū)所使用，從而對其進行保護。時間分區(qū)指不同分區(qū)在同一周期內(nèi)被調(diào)度并且不同分區(qū)的優(yōu)先級別相同，由系統(tǒng)建立一個時長確定的主時間框架并且周期性的重復，它可以被分成若干時間窗口，要求時間窗口個數(shù)要不小于分區(qū)數(shù)目，這樣才能保證每個分區(qū)占有至少一個時間窗口，并且只能在它占有的時間窗口內(nèi)才能被調(diào)度。因此在ARINC653系統(tǒng)中當某一分區(qū)故障時，其他分區(qū)不會受到影響，仍然能正常執(zhí)行。時間隔離表示每個分區(qū)都具有固定的、相互獨立的時間框架來執(zhí)行。操作系統(tǒng)內(nèi)的主時間框的長度是全部分區(qū)周期總和的倍數(shù)。操作系統(tǒng)由各分區(qū)的不同需求為其劃分時間窗口，每個分區(qū)將獲得一個或多個時間窗口，可將其稱之為時間片。這樣就在時間上和空間上將分區(qū)隔離開來。

ARINC653系統(tǒng)包含兩級調(diào)度即分區(qū)間調(diào)度和分區(qū)內(nèi)調(diào)度。在下圖所示的調(diào)度模型中在系統(tǒng)層依據(jù)ARINC653標準使用一定的調(diào)度策略去進行分區(qū)調(diào)度，在區(qū)間層根據(jù)分區(qū)內(nèi)定義的調(diào)度策略進行任務(wù)調(diào)度。 每一個分區(qū)內(nèi)部的任務(wù)只能在當前分區(qū)處于激活狀態(tài)才有可能被執(zhí)行， 從而使得模塊中各分區(qū)相互獨立。

2.2 雙層調(diào)度算法

為了滿足ARINC653的兩級調(diào)度要求，目前已經(jīng)有不少學者提出了雙層調(diào)度的模型和算法，主要包括模型的建立和改進[5?7]、分區(qū)參數(shù)的設(shè)計[8，6]和解析以及對時間片算法的改進[9?11]等方面。

文獻[8]中較早地提出了雙層調(diào)度的概念，給出了部分相關(guān)分區(qū)的參數(shù)，并針對分區(qū)的調(diào)度考慮任務(wù)最大響應(yīng)時間，在單處理器情況下借用Tindell提出的一種精確的分析算法。該算法引入“關(guān)鍵時刻”這一概念，在對分區(qū)進行調(diào)度性分析時可以得到“關(guān)鍵時刻”的“關(guān)鍵條件”。最后通過分析給出了分區(qū)成功調(diào)度的一些要求。但是文中僅考慮單處理器情況下的算法，雙層模型有待進一步的擴充和完善，并且不考慮釋放抖動等復雜情形下的調(diào)度。文獻[5]中建立的雙層調(diào)度模型，上層使用輪轉(zhuǎn)調(diào)度策略，下層使用EDF調(diào)度策略，對于分區(qū)調(diào)度的關(guān)鍵參數(shù)，在文中給出了它的解析表達式和解析模型。對于其他算法設(shè)計者有很好的參考價值。文中給出的算法上層使用傳統(tǒng)時間片輪轉(zhuǎn)，分區(qū)之間優(yōu)先級相同，雖然算法簡單卻不夠靈活，并且時間片長度確定，為了滿足分區(qū)對時間片的最大要求，時間片就應(yīng)該設(shè)置為分區(qū)要求最大時間，因此存在不必要的時間開銷。

文獻[6]中對于ARINC653分區(qū)管理模型進行了擴展。提出上層調(diào)度使用動態(tài)優(yōu)先級的調(diào)度策略的分區(qū)設(shè)計方法。相比較于上層為靜態(tài)優(yōu)先級的調(diào)度算法，這種調(diào)度策略有很好的靈活性，但同時也增加其復雜性。上層考慮最大響應(yīng)時間，使用改造的針對動態(tài)優(yōu)先級任務(wù)的算法。文中還探討了下層采用固定優(yōu)先級和動態(tài)優(yōu)先級調(diào)度策略下的分區(qū)設(shè)計方法，并且通過價值函數(shù)給出了一些分區(qū)設(shè)計的參數(shù)。

文獻[7]提出了一種靜態(tài)雙層調(diào)度模型。在該模型中使用固定周期分區(qū)和優(yōu)先級位圖算法。為了確保分區(qū)內(nèi)的任務(wù)在規(guī)定時間內(nèi)正確執(zhí)行， 在分區(qū)內(nèi)使用兩種調(diào)度方式，一種是靜態(tài)優(yōu)先級，另一種是EDF動態(tài)優(yōu)先級。文中對任務(wù)調(diào)度時的條件約束及任務(wù)的可調(diào)度性做了相關(guān)的研究。這種調(diào)度策略存在的不足是在確定分區(qū)優(yōu)先級時是采用RM調(diào)度算法，忽略了分區(qū)執(zhí)行周期不確定的情況。

文獻[9]給出了一種改進的時間片輪轉(zhuǎn)算法。文中將最后一次時間片的分配進行優(yōu)化，改進算法對原算法做了下述改變：當前進程即將執(zhí)行完畢，但是仍有剩余工作，這時通過增加一定的時間片將當前任務(wù)執(zhí)行完成而不必等待下一次系統(tǒng)調(diào)用。增加時間片的時機是可以調(diào)整的，正在執(zhí)行進程需要繼續(xù)執(zhí)行的時間不足系統(tǒng)原來分配的時間片值得若干分之一時，通過調(diào)度算法為其增加一定的時間片值， 使當前進程能在該時間片內(nèi)完成。該算法在一定程度上減少了進程的切換也就是說減少了調(diào)度的次數(shù)，從這一點上來說增強了實時性。但是文中沒有給出如何確定增加時間片長度的一般方法，也沒有給出具體參數(shù)確定方法。

文獻[10]提出了一種加權(quán)輪轉(zhuǎn)調(diào)度算法。分區(qū)通過核心調(diào)度器以加權(quán)輪轉(zhuǎn)（Weighted Round Robin）調(diào)度的方式逐一被激活，當分區(qū)激活后擁有對CPU內(nèi)存等資源的使用權(quán)。分區(qū)內(nèi)部采用可搶占式FP調(diào)度算法，即在分區(qū)被激活時，在時間片結(jié)束前優(yōu)先級高的任務(wù)優(yōu)先被調(diào)度，高優(yōu)先級任務(wù)可以搶占低優(yōu)先級任務(wù)，從而減少高優(yōu)先級任務(wù)的響應(yīng)時間。文中將該調(diào)度策略命名為WRP?FP，以加權(quán)輪轉(zhuǎn)調(diào)度策略來激活分區(qū)，同時將時間窗口固定，提高了系統(tǒng)的可預測性。該調(diào)度算法允許進行混合任務(wù)集的調(diào)度。對強實時的周期任務(wù)建立具有任意時限的任務(wù)模型，使模型具有更強的通用性，文中通過對響應(yīng)時間上限的計算，給出了可調(diào)度條件；文中將“期望可調(diào)度”概念引入弱實時的非周期任務(wù)，以此來確保在統(tǒng)計條件下任務(wù)是可調(diào)度的。

上述算法在起始時時間片都是人為確定好的，在文獻[11]中提出了基于ARINC653航空電子設(shè)備實時操作系統(tǒng)，將其模擬為2層分級制度。使用具有非零偏移值的處理過程技術(shù)，擴展了現(xiàn)有的基于資源模型。提出了一種分區(qū)搶占策略，使用這些技術(shù)和策略來自動的生成分區(qū)時間表，文中所提出的技術(shù)作為分區(qū)級調(diào)度原則可用來設(shè)計的平臺。此外還提供了正確性分析和驗證，從而確保在系統(tǒng)認證中可以使用。文獻[12]提出了一個資源模型能夠描述分區(qū)占用資源的周期性行為，并提供精確的調(diào)度條件。對于分級調(diào)度框架，提出了橋接兩個獨立開發(fā)的調(diào)度模型的接口模型，這種調(diào)度接口模型、可以使用任何獨立的調(diào)度算法對其進行調(diào)度性分析，與另一個調(diào)度模型是沒有任何交互的。在圖1中詳細給出了幾種雙層模型和調(diào)度算法的優(yōu)缺點。

3 調(diào)度分析工具

3.1 OSATE

OSATE（Open Source AADL Tool Environment）是一款開源的AADL工具，它是Eclipse平臺下的AADL模型開發(fā)工具。它由SEI開發(fā)，集建模，分析，驗證，轉(zhuǎn)換為一體，功能全面且集成度高。OSATE適用于終端用戶和工具開發(fā)人員，OSATE向終端用戶提供文本、圖形編輯器以及一些分析驗證工具。OSATE中已經(jīng)集成了幾種調(diào)度分析的插件，包括VERSA插件和Scheduling插件，支持EDF、RMS等調(diào)度算法。只需要在模型建立好之后通過點擊相應(yīng)的調(diào)度算法，就可以得到調(diào)度結(jié)果。而且越來越多的調(diào)度策略和算法將被作為插件集成進入OSATE中。

3.2 Cheddar

Cheddar由布雷斯特大學開發(fā)，是一種開源的實時調(diào)度框架。它的框架使用Ada編寫，能夠?qū)崟r應(yīng)用的時間要求進行驗證。Cheddar將一個應(yīng)用定義為處理器、任務(wù)、緩存、共享資源和消息的集合。Cheddar不僅支持單處理器的時間可行性分析，它還支持多處理器和分布式系統(tǒng)，同時還提供了仿真機制。文獻[13] 介紹了正在為了增加實時調(diào)度理論的可用性研究的Cheddar項目3個可能的方向。提出了一套開源的工具，幫助設(shè)計人員自動將理論應(yīng)用于具體案例。這個工具可以讓不同層次的人員使用，并能執(zhí)行寫入標準化設(shè)計語言模型的分析。該Cheddar項目一直集中在AADL上。還提出了一個領(lǐng)域特定語言，它可以被用來研究結(jié)構(gòu)的性能，因為現(xiàn)有的實時調(diào)度理論沒有提出合適的分析方法。

3.3 Marzhin

在文獻[14]中介紹了使用Marzhin模擬器，相比于Cheddar，Marzhin基于多Agent技術(shù)，提供實時系統(tǒng)的調(diào)度分析結(jié)果，該模擬器集成在AADL中，同時提供了逼真的3D動畫效果增強了可視性。通常，實時仿真器的實現(xiàn)是基于實時操作系統(tǒng)（RTOS）的仿真。這些仿真器必須因此提供相同的應(yīng)用程序編程接口（API），并且具有相同的動態(tài)行為作為真正的軟件。Marzhin是基于現(xiàn)有的多代理仿真內(nèi)核VAgent的重用。相對于實施確定性調(diào)度算法傳統(tǒng)模擬器，該內(nèi)核隨機刺激的一組自主互連的基本實體（Agent），以顯示出所得的宏觀行為。Cheddar不能給任何種類的AADL架構(gòu)提供一個顯著結(jié)果。但是，Marzhin的作用是專門為具有不能在確定的方式進行處理的情況下對Cheddar的一個補充。

4 結(jié) 語

本文首先介紹了3種較新穎的實時調(diào)度算法，然后對滿足ARINC653要求的雙層調(diào)度算法做了詳細的介紹，實時調(diào)度算法對于實時系統(tǒng)起著至關(guān)重要的作用。在ARINC653標準下，雙層調(diào)度算法出現(xiàn)并使用在航電系統(tǒng)模型中，上層調(diào)度和下層調(diào)度的不同組合和不斷地優(yōu)化勢必會產(chǎn)生更好的調(diào)度模型，因此在未來一段時間內(nèi)雙層調(diào)度算法將成為研究熱點。對于分區(qū)間的調(diào)度，時間片輪轉(zhuǎn)算法是其基礎(chǔ)算法，對于如何進行時間片大小的確定、輪轉(zhuǎn)方式以及空閑時間的利用將有待進一步的研究。分區(qū)內(nèi)的調(diào)度算法需要考慮如何確保實時任務(wù)在結(jié)束時間到來之前被調(diào)度，同如何調(diào)度非周期的弱實時任務(wù)，分區(qū)調(diào)度的參數(shù)的解析和優(yōu)化以及如何提高效率。最后，介紹了3種用于調(diào)度性分析的工具，以供設(shè)計人員選擇使用。

參考文獻

[1] Anon. ARINC specification 653?2， part I： engineering standards for avionics and cabin systems [M]. [S.l.]： AEEC， 2006.

[2] 洪雪玉，張凌，袁華.Linux下的實時調(diào)度算法木[J].華南理工大學學報：自然科學版，2008，36（4）：104?109.

[3] 翟鴻鳴.單處理器系統(tǒng)的實時調(diào)度算法研究[J].微機發(fā)展，2003，13（10）：99?101.

[4] 王彬，王聰，薛潔，等.優(yōu)先級周期性互換的實時調(diào)度算法[J].計算機應(yīng)用，2014，34（3）：668?672.

[5] 何鋒，宋麗茹，熊華鋼.航空電子雙層任務(wù)分區(qū)調(diào)度設(shè)計[J].北京航空航天大學學報，2008，34（11）：1365?1368.

[6] 何鋒，顧健，熊華鋼.基于動態(tài)優(yōu)先級的核心處理安全分區(qū)優(yōu)化設(shè)計[J].北京航空航天大學學報，2011，37（10）：1282?1287.

[7] 楊霞，桑楠，雷劍，等.嵌入式高可信架構(gòu)中基于靜態(tài)模型的調(diào)度研究[J].航空學報，2009（12）：2387?2394.

[8] 何鋒，熊華鋼，宋麗茹.航空電子分區(qū)調(diào)度研究[J].系統(tǒng)仿真學報，2008（z1）：522?525.

[9] 肖建明，張向利.一種改進的時間片輪轉(zhuǎn)調(diào)度算法[J].計算機應(yīng)用，2005（z1）：447?448

[10] 周天然，熊華鋼.航空電子系統(tǒng)混合實時任務(wù)的雙層調(diào)度[J].航空學報，2011（6）：1067?1074.

[11] EASWARAN A， LEE I， SOKOLSKY O， et al. A compositional scheduling framework for digital avionics systems [C]// 2009 15th IEEE International Conference on Embedded and Real?Time Computing Systems and Applications. [S.l.]： IEEE， 2009： 371?380.

[12] SHIN I， LEE I. Periodic resource model for compositional real?time guarantees[C]// 2003 24th IEEE Real?Time Systems Symposium. [S.l.]： IEEE， 2003： 2?13.

[13] SINGHOFF F， PLANTEC A， DISSAUX P， et al. Investigating the usability of real?time scheduling theory with the Cheddar project [J/OL]. [ 2014?08?13]. http：// www.9512.net/read/f6ae...990.htm.

[14] DISSAUX Pierre， MARC Olivier， RUBINI Stephane， et al. The SMART Project： multi?agent scheduling simulation of real?time architectures [J/OL]. [2014?12?26]. http：//www.researchgate.net.

[15] FEILER P H， GLUCH D P， HUDAK J J. The architecture analysis & design language （AADL）： An introduction [R]. USA： Pittsburgh PA Software Engineering Inst， Carnegie?Mellon University， 2006.

[16] DELANGE J， PAUTET L， PLANTEC A， et al. Validate， simulate， and implement ARINC653 systems using the AADL[J]. ACM SIGAda Ada Letters， 2009， 29（3）： 31?44.

[17] DAVIS R I， BURNS A. Improved priority assignment for global fixed priority pre?emptive scheduling in multiprocessor real?time systems [J]. Real?Time Systems， 2011， 47（1）： 1?40.

[18] MOHANTY R， BEHERA H S， PATWARI K， et al. Priority based dynamic round robin （PBDRR） algorithm with intelligent time slice for soft real time systems [J]. International Journal of Advanced Computer Science and Application， 2011， 2（2）： 46?50.

[19] LIANG B， YONGHENG J， DEXIAN H. A novel two?level optimization framework based on constrained ordinal optimization and evolutionary algorithms for scheduling of multipipeline crude oil blending [J]. Industrial & Engineering Chemistry Research， 2012， 51（26）： 9078?9093.

[20] SINGHOFF F， PLANTEC A， DISSAUX P， et al. Investigating the usability of real?time scheduling theory with the Cheddar project [J/OL]. [2014?12?18]. http：//www.researchgate.net.

[21] LEE Y H， KIM D， YOUNIS M， et al. Resource scheduling in dependable integrated modular avionics [C]// Proceedings of 2000. Proceedings International Conference on Dependable Systems and Networks. [S.l.]： IEEE， 2000： 14?23.