周霆　胡寧　任曉瑞

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

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

中圖分類號(hào)：TP316.2

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 結(jié)論

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

參考文獻(xiàn)：

[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.