一種分區(qū)操作系統(tǒng)實時任務調(diào)度方法

周霆　胡寧　任曉瑞

摘 要：本文以提高在綜合化航空電子系統(tǒng)混合任務場景中的實時任務響應性能和解決遺產(chǎn)代碼重用問題為目標，提出一種具備虛擬化支持能力的分區(qū)操作系統(tǒng)實時任務調(diào)度方法。該方法通過建立全局調(diào)度隊列，并對任務狀態(tài)進行合理控制，相比已有分區(qū)操作系統(tǒng)兩級調(diào)度模型更為靈活，并且保證了虛擬化分區(qū)中客戶操作系統(tǒng)自身的調(diào)度策略不被破壞，能夠滿足分區(qū)操作系統(tǒng)對任務調(diào)度實時性和虛擬化支持能力的需求。

關鍵詞：分區(qū)操作系統(tǒng)；任務調(diào)度；全局調(diào)度隊列；虛擬化支持

中圖分類號：TP316.2

隨著航空電子技術的發(fā)展，機載電子系統(tǒng)綜合化模塊化（Integrated Modular Avionics，簡稱IMA）成為必然發(fā)展趨勢，一個物理平臺可能承擔來自多個系統(tǒng)的不同類型的任務，這些任務對基礎平臺的處理特性有著極為不同的需求。例如，機電應用可能需要快速處理多個外部事件，飛控應用可能需要根據(jù)當前傳感器數(shù)據(jù)及時進行舵面控制，而航電應用可能需要進行復雜計算以完成某種功能，這些應用綜合在一起，提出了強實時任務與一般任務共存的需求。如圖1所示的操作系統(tǒng)（簡稱OS）架構所示[1]，目前為了解決綜合化帶來的故障隔離和信息安全問題，現(xiàn)有的高安全機載操作系統(tǒng)都采用了分區(qū)機制，提供分區(qū)間隔離與分區(qū)間通信能力?，F(xiàn)有的典型分區(qū)操作系統(tǒng)，如VxWorks653等采用兩級任務調(diào)度策略，分區(qū)調(diào)度凌駕于分區(qū)內(nèi)的任務調(diào)度之上，任務響應難以逾越分區(qū)時間窗口的限制，雖然能夠確保任務的確定性實時響應，但是無法對任務從全局層面提供以任務為單位的統(tǒng)一調(diào)度，需要進行大量的前期任務規(guī)劃，缺乏靈活性。

另一方面，機載軟件的開發(fā)和驗證成本相對較高，業(yè)界一直在探索降低機載軟件成本的途徑。系統(tǒng)綜合中重用遺產(chǎn)代碼可以有效降低成本，提高系統(tǒng)的安全性。虛擬化能夠為代碼重用提供有效支持[2]，支持虛擬化也成為機載操作系統(tǒng)發(fā)展的一個新的方向。如何在不破壞虛擬化分區(qū)中客戶OS自身調(diào)度策略的前提下進行全局統(tǒng)一調(diào)度，也是綜合化調(diào)度算法亟待解決的問題。

面對上述問題，需要通過在軟件架構層面優(yōu)化，提出新的綜合化任務調(diào)度方法[3]，使含有虛擬化分區(qū)的混合任務環(huán)境下的強實時任務調(diào)度成為可能。

1 強實時全局統(tǒng)一調(diào)度算法

如圖2所示，為了從根本上提高系統(tǒng)混合任務場景中實時任務的響應性能，必須減少調(diào)度層次，給分區(qū)操作系統(tǒng)所有分區(qū)內(nèi)的每個任務賦予全局統(tǒng)一優(yōu)先級，在分區(qū)管理程序中維護一個全局優(yōu)先級調(diào)度隊列，進行全局統(tǒng)一調(diào)度。具體來說就是將所有任務的當前優(yōu)先級都映射為全局的統(tǒng)一優(yōu)先級，然后在時間片耗盡和實時事件觸發(fā)時，由分區(qū)管理程序的調(diào)度器進行統(tǒng)一調(diào)度。

在圖2中，以分區(qū)中分別運行包含大量非實時應用的普通OS（例如Linux）和實時OS（簡稱RTOS，例如μC/OS）為例，雖然運行在RTOS上的實時任務通常具有最高的調(diào)度優(yōu)先級，然而每個RTOS中也有低優(yōu)先級的后臺活動，它們不應該搶占運行在普通OS之下的用戶前臺任務。同樣的，普通OS也會運行一些軟實時活動（比如媒體播放器），而這些軟實時活動可能會搶占RTOS中別的實時活動。很明顯，使用現(xiàn)有分區(qū)操作系統(tǒng)那種分散的、層次性的調(diào)用模型，需要進行大量的前期任務規(guī)劃來應對這種復雜的混合任務場景。

本文中分區(qū)管理程序中的調(diào)度器提供的綜合化調(diào)度算法是一種搶占式、嚴格優(yōu)先級、在最高優(yōu)先級任務之間進行時間片輪轉的調(diào)度算法。如圖2所示，調(diào)度器維護一個包含255個優(yōu)先級的全局就緒任務隊列，調(diào)度器總是選擇隊列中具有最高優(yōu)先級的任務獲得處理器，如果處于最高優(yōu)先級的有多個任務，則進行時間片輪轉（RR，Round-Robin）調(diào)度。

本調(diào)度方法也提供了足夠的用戶可控支持[4]。用戶可以通過系統(tǒng)服務動態(tài)的改變?nèi)魏我粋€任務的以下3個基本調(diào)度參數(shù)：（1）優(yōu)先級，0-255；（2）時間片長度；（3）處理器的編號。從而，任務的時間片通過在調(diào)度前對優(yōu)先級的進行計算由系統(tǒng)缺省配置，也可以由用戶通過系統(tǒng)服務進行修改。

出于調(diào)度開銷和效率的考慮，本方法通過分析各種調(diào)度時機，可以在確認不會有更高優(yōu)先級任務就緒的情況下不觸發(fā)調(diào)度器而直接進行切換。

其中觸發(fā)調(diào)度器調(diào)度的時機如下：（1）當前線程的時間片耗盡；（2）當前線程主動放棄時間片；（3）分區(qū)間通信（IPC，Inter-Partition Communication）操作阻塞當前線程或激活另一個線程。

不激活調(diào)度器，直接觸發(fā)任務切換將減少系統(tǒng)開銷，增加執(zhí)行效率[5]。任務直接切換的時機如下：（1）中斷發(fā)生時，通過全局優(yōu)先級決定獲取執(zhí)行權的是當前線程或用戶級中斷服務線程；（2）IPC機制觸發(fā)多個接受線程就緒，則在發(fā)送方和多個接受方之間選擇一個優(yōu)先級高的任務直接切換，此時可以不考慮優(yōu)先級，而選用其他策略。

相比現(xiàn)有的兩級調(diào)度算法，依據(jù)上述調(diào)度策略，借助合理的優(yōu)先級部署，可以有效提高關鍵任務的實時響應性能，但是單級的綜合化調(diào)度如何保證在虛擬化條件下分區(qū)中客戶OS原有的調(diào)度策略不被破壞，是一個必須要解決的問題。

2 維護客戶OS的自有調(diào)度策略

對于圖2所示的全局調(diào)度策略，對于同一類型的任務全部給定相同的全局優(yōu)先級，相同優(yōu)先級的任務在全局實時調(diào)度中是以輪轉Round-Robin方式進行調(diào)度。這種優(yōu)先級配置策略在系統(tǒng)存在虛擬化分區(qū)的情況下將破壞客戶OS原本的調(diào)度策略（比如Linux的普通用戶級任務使用CFS調(diào)度策略），違反虛擬化的原則[6]。因此，分區(qū)管理程序和客戶OS必須采取必要的措施，在無其它分區(qū)更高優(yōu)先級任務搶占時采取合理的配合機制，保留客戶OS自身的調(diào)度策略。

本文提出的調(diào)度方法解決此問題的基本原理是：首先，限制單個客戶OS上應用級任務在全局調(diào)度隊列中同時出現(xiàn)，從而使全局調(diào)度策略無法影響到客戶OS內(nèi)部的任務調(diào)度；其次，在觸發(fā)調(diào)度的時機，全局調(diào)度器優(yōu)先調(diào)度，如果沒有當前運行客戶OS之外的更高優(yōu)先級的任務就緒，則將調(diào)度控制權交給當前客戶OS的客戶級調(diào)度器，此時激活客戶級調(diào)度策略。

如圖3所示，如果能夠保證在每一時刻所有的客戶OS應用級任務只有一個處于全局就緒隊列中，就可以避免多個同等全局優(yōu)先級的用戶級線程按照全局調(diào)度策略進行輪轉調(diào)度。在創(chuàng)建客戶OS的任務時通過分區(qū)管理器系統(tǒng)服務修改任務在分區(qū)管理器中的系統(tǒng)狀態(tài)，使其一經(jīng)創(chuàng)建就處于未激活狀態(tài)，不進入全局調(diào)度隊列。在客戶OS分區(qū)中創(chuàng)建一個高優(yōu)先級的定時器處理線程timer_thread[7]，這個線程處理所有的客戶級時間中斷（真實時間中斷在分區(qū)管理器的預處理中已經(jīng)判斷了在全局隊列中是否有其他更高優(yōu)先級線程就緒的情況，有則調(diào)用分區(qū)管理器的全局調(diào)度器進行調(diào)度），否則喚醒客戶OS的調(diào)度器，依據(jù)客戶OS的調(diào)度策略進行調(diào)度，啟動獲取CPU的新任務，將其加入全局隊列，更改被剝奪CPU的上一個任務的狀態(tài)（將其屏蔽出全局隊列），從而保證了同一時刻所有的客戶OS用戶級線程只有一個處于就緒狀態(tài)。

通過上述機制，可以在確保實時性和堅持虛擬化原則的基礎上，完成分區(qū)管理器和客戶OS的調(diào)度配合，達到在虛擬化分區(qū)內(nèi)維護客戶OS自有調(diào)度策略的目標。

3 結論

本文針對航空電子系統(tǒng)綜合化產(chǎn)生的實時任務和非實時任務共存的混合調(diào)度需求，以及遺產(chǎn)代碼繼承產(chǎn)生的虛擬化需求，能夠在不破壞虛擬化原則的前提下，對實時任務和非實時任務進行全局統(tǒng)一的單級調(diào)度，改進實時任務的響應性能，解決全局調(diào)度策略破壞客戶OS自有調(diào)度策略的問題，突破現(xiàn)有兩級調(diào)度策略的瓶頸。

參考文獻：

[1]Alves-Foss J，Oman P W，Taylor C，et al.The MILS Architecture for High-assurance Embedded System.International Journal of Embedded Systems，2006，2（3/4）：239-247.

[2]Gernot Heiser，PhD.Virtualization for Embedded Systems.

[3]Sergio Ruocco，Real-Time Programming and L4 Microkernels.

[4]J. Kamada， M.Yuhara， and E.Ono.User-level real-time scheduler exploiting kernel-level fixed priority scheduler.In Multimedia Japan，Mar，1996.

[5]M. Hohmuth and H.H¨artig.Pragmatic nonblocking synchronization for real-time systems.In 2001 USENIX Techn.Conf.，Boston，MA，USA，2001.

[6]U.A.Steinberg.Quality assuring scheduling.Diploma thesis，Dresden University of Technology，Mar，2004.

[7]National ICT Australia.NICTA L4-embedded Kernel Reference Manual Version N1，Oct 2005.http：//ertos.nicta.com.