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

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


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


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

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


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

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

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

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


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


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