ARINC653調度算法研究

陳平等

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

關鍵詞： 實時算法； 雙層調度； ARINC653； 嵌入式系統

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

0 引 言

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

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

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

1 實時調度算法

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

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

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

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

2 雙層調度

2.1 雙層調度算法概述

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

ARINC653系統包含兩級調度即分區間調度和分區內調度。在下圖所示的調度模型中在系統層依據ARINC653標準使用一定的調度策略去進行分區調度，在區間層根據分區內定義的調度策略進行任務調度。 每一個分區內部的任務只能在當前分區處于激活狀態才有可能被執行， 從而使得模塊中各分區相互獨立。

2.2 雙層調度算法

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

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

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

文獻[7]提出了一種靜態雙層調度模型。在該模型中使用固定周期分區和優先級位圖算法。為了確保分區內的任務在規定時間內正確執行， 在分區內使用兩種調度方式，一種是靜態優先級，另一種是EDF動態優先級。文中對任務調度時的條件約束及任務的可調度性做了相關的研究。這種調度策略存在的不足是在確定分區優先級時是采用RM調度算法，忽略了分區執行周期不確定的情況。

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

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

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

3 調度分析工具

3.1 OSATE

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

3.2 Cheddar

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

3.3 Marzhin

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

4 結 語

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

參考文獻

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

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

[3] 翟鴻鳴.單處理器系統的實時調度算法研究[J].微機發展，2003，13（10）：99?101.

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

[5] 何鋒，宋麗茹，熊華鋼.航空電子雙層任務分區調度設計[J].北京航空航天大學學報，2008，34（11）：1365?1368.

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

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

[8] 何鋒，熊華鋼，宋麗茹.航空電子分區調度研究[J].系統仿真學報，2008（z1）：522?525.

[9] 肖建明，張向利.一種改進的時間片輪轉調度算法[J].計算機應用，2005（z1）：447?448

[10] 周天然，熊華鋼.航空電子系統混合實時任務的雙層調度[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.