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

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


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


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

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


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

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

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

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


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


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