摘要:論述了OS 中調度的概念、類型、調度隊列模型,并著重對VxWorks 實時內核進行了分析。
關鍵詞:嵌入式實時操作系統(RTOS) ;VxWorks ;調度

0 　引　言
　　VxWorks 是美國Wind River 公司推出的一種嵌入式強實時操作系統,自20 世紀80 年代問世以來,以其高性能、高可靠性、高實時性等特點成為實時操作系統中最具特色的系統。尤其以成功應用于火星探測車和愛國者導彈等高科技產品而聲名鵲起。自1996 年登陸中國,短短幾年就已成為國防、工業自動化、網絡通信、航空航天、醫療儀器、狀態監控以及消費電子產品等嵌入式實時領域的首選操作系統。嵌入式實時操作系統在內核方面具有自身的特點。本文著重對實時內核中任務調度進行了分析。


1 調度的概念
　　構成應用軟件系統的程序集合中,獨立的、相互作用的程序單元,在其執行時稱之為任務。單個CPU 中,多任務機制制造了一個多個任務同時執行的假象。其實系統只是根據一個多任務調度算法,將內核插入到這些任務中執行。任務由系統內核調度運行一段固定長度的時間,稱為時間片。
　　調度是指為任務分配資源和時間,使系統滿足特定的性能要求。調度算法的目的是在正常情況下,盡可能滿足所有任務的時限;在峰值負載條件下,保證強實時任務滿足時限。因為時限是區分實時系統和非實時系統的關鍵因素,因此調度算法是實時系統的基本問題。實時操作系統所具有的運行性能,如吞吐量的大小、周轉時間的長短、相應的及時性和可預測性等在很大程度上都取決于實時調度。


2 　調度的類型
　　雖然調度的主要目的都是為了分配處理機,但在不同的OS 中所采用的調度方式是完全不同的。在執行調度時所采用的調度算法也可能不同。因此,常按照調度的層次把調度分成高級、中級和低級調度。
　　高級調度又稱長程調度或作業調度,用于決定把外存上處于后備隊列中的哪些作業調入內存,并為它們創建進程、分配必要的資源,然后再將新創建的進程排在就緒隊列上,準備執行。然而在實時系統中,為了能及時響應,用戶通過鍵盤輸入的數據都是直接送入內存,因而實時系統通常不需要作業調度。中級調度又稱中程調度,引入它的主要目的是為了提高內存利用率和系統吞吐量。它使那些暫時不能運行的進程不再占用寶貴的內存空間,而將它們調到外存上去等待,此時的狀態稱為掛起狀態。當這些進程重新具備運行條件,且內存又有空閑,由中級調度決定,將外存上的那些重新具備運行條件的就緒進程重新調入內存,并使它為就緒狀態,掛在就緒隊列上等待進程調度。低級調度又稱進程調度。它決定就緒隊列中的哪個進程將獲得處理機,然后由分派程序執行把處理機分配給該進程的操作。進程調度是最基本的一種調度,各種OS 中都必須配置這級調度。

　　進程調度可采用下述兩種方式。
　　1) 非搶占方式。采用這種調度方式,一旦把處理機分配給某進程后,便讓該進程一直執行,直到該進程完成或發生某事件而被阻塞,才再把處理機分配給其他進程,決不允許某進程搶占已經分配出去的處理機。顯然它難于滿足緊急任務的要求,實時系統中不宜采用這種調度方式。
　　2) 搶占方式。允許調度程序根據某種原則,去停止某個正在執行的進程,將已分配給該進程的處理機,重新分配給另一進程。搶占的原則有:
①時間片原則。各進程按時間片運行,當一個時間片用完后,便停止該進程的執行而重新進行調度。
②優先權原則。當一個進程到來時,如果其優先級比正在執行的進程的優先級高,便停止正在執行的進程,將處理機分配給優先級高的進程,使之執行。實時系統中一般采用基于優先級的搶占式調度和輪轉調度的進程調度和中程調度相結合的調度策略。因此既可具有較大的靈活性,又能獲得極小的調度延遲。


3 　調度隊列模型
3. 1 　僅有進程調度的調度隊列模型就緒態的進程排在就緒隊列中,按時間片輪轉調度運行,每個進程執行時,都可能出現以下3種情況。
　　1) 任務在時間片內完成,則該任務釋放處理機,該進程完成。
　　2) 任務在時間片內未完成,則OS 將該進程放在就緒隊列的末尾,等待下一輪調度。
　　3) 任務在執行期間,進程被阻塞后,OS 將該進程放入阻塞隊列。如圖1 所示。
圖1 　僅具有進程調度的調度隊列模型
3. 2 　引入中級調度的調度隊列模型較完善的OS 中,除設置了進程調度外,還引入中級調度來改善內存的利用率。當在OS 引入中級調度后,可把進程的就緒狀態分為內存就緒態(進程在內存中就緒) 、外存就緒態(進程在外存中就緒) ;把阻塞狀態分為內存阻塞和外存阻塞。在調出操作的作用下,可使內存就緒轉變為外存就緒、內存阻塞轉變為外存阻塞;在中級調度的作用下,可使外存就緒轉變為內存就緒。如圖2 所示。 圖2 　引入中級調度的進程調度的調度隊列模型

4 　VxWorks 實時內核Wind 調度分析Wind 內核缺省調度機制為基于優先級的搶占式調度。采用這種機制時,系統把處理機分配給優先級最高的進程,使之執行。一旦出現了另一個優先級更高的進程時,進程調度程序剝奪當前任務的執行,將處理機分配給高優先級任務。而在相同優先級的多個任務之間,采用時間片輪轉調度機制。采用這種機制時,當一個任務到達時,它被排在輪轉隊列的后面,等待分配給自己的間片的到來,如果在時間片內沒有結束,則再等待屬于自己的時間片的到來,直到任務完成。

4. 1 　基于優先級的搶占式調度
　　采用基于優先級的搶占式調度,系統中每個任務都有一個介于最高0 到最低255 之間的優先級。任一時刻,系統內核一旦發現一個優先級更高的任務轉變為就緒態,內核就保存當前任務的上下文并把當前任務狀態轉換為阻塞態,同時切換到這個高優先級任務的上下文執行。如圖3 ,低優先級的task1 被中優先級的task2 搶占,task2又被高優先級的task3 搶占。
圖3 　基于優先級的搶占式調度
4. 2 　輪轉調度算法
　　采用輪轉調度算法,系統讓處于就緒態的優先級相同的一組任務依次輪流執行預先確定長度的時間片。這是一種處理機平均分配的方法。如果不使用輪轉調度算法,優先級相同的一組任務中第一個獲得處理機的任務將不會被阻塞而獨占處理機,如果沒有阻塞或其他情況發生,它不會放棄處理機的使用權。如圖4 , 相同優先級的task1 、task2 和task3 平均分配預先確定的處理機時間片。 圖4 　優先級相同輪轉調度

4. 3 　基于優先級的搶占式調度與輪轉調度相結合有時,基于優先級的搶占式調度可與輪轉調度相結合。當優先級相同的一組任務依次輪流平均分配處理機時,若有高優先級的任務轉變為就緒態則可搶占該組任務。直到再一次符合執行條件時,該組任務才可再次共享處理機。如圖5 ,相同優先級的task1 、task2 和task3 輪流占有處理機時,高于該組優先級的task4 搶占處理機,等task4執行結束,該組任務再次共享處理機。
圖5 　基于優先級的搶占式調度與輪轉調度相結合調度
　　為了任務控制的靈活性,Wind 內核還提供了動態優先級機制,任務的優先級在運行期間可動態地變化。同時,為了防止優先級反轉,還具有優先級繼承機制,通過使用互斥信號量可以防止高優先級的任務被迫等待一段不確定時間,直到一個低優先級任務完成。


5 　結論
　　內核調度是一個實時系統的核心,它的好壞直接影響整個系統的好壞,通過對這種內核調度分析,可以更深入的理解實時操作系統設計的獨到之處。


參考文獻：
[1 ] 　孔祥營. 嵌入式實時操作系統VxWorks 及其開發環境Tornado[M] . 北京:中國電力出版社,2001.
[2 ] 　拉伯羅斯.μC/ OS 2 Ⅱ- 源代碼公開的實時嵌入式操作系統[M] . 北京:中國電力出版社,2001.
[3 ] 　郭鳳儀,王其平,孫鶴旭. 開關電弧材料侵蝕研究[J ] . 遼寧工程技術大學學報,1997 ,16 (3) : 374 -379.
[4 ] 　張吉軍. 模糊層次分析法[J ] . 模糊系統與數學,2000 ,14 (2) :15 - 18.
[5 ] 　王　琦. 實用模糊數學[M] . 北京:科學技術文獻出版社,1991.