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

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


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


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

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


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

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

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

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


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


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