| 摘要 進程調(diào)度是計算機的靈魂。在實時系統(tǒng)里,要使重要緊急的進程一經(jīng)喚醒便被優(yōu)先調(diào)度運行,系統(tǒng)就必須有基于進程優(yōu)先級的實時調(diào)度策略。通過深入考察和對比μC/OS-II和Nut/OS對實時調(diào)度算法的實現(xiàn),可以深刻理解實時操作系統(tǒng)。 關(guān)鍵詞 μC/OS-II Nut/OS 實時調(diào)度算法 如果說CPU是計算機系統(tǒng)的心臟,那么進程調(diào)度就是計算機系統(tǒng)的靈魂,因為它決定了如何使用CPU。例如,Linux是一個多任務(wù)操作系統(tǒng),它的理想狀況是保持CPU有效運行。如果某個正在運行的進程轉(zhuǎn)入等待系統(tǒng)資源,操作系統(tǒng)就調(diào)度其他進程運行,從而保證CPU的最大利用率。如何使系統(tǒng)能夠保證較短的響應(yīng)時間和較高的吞吐量,使得多個進程競爭CPU時保持公平、高效,是通用操作系統(tǒng)所追求的目標(biāo)。但對于實時操作系統(tǒng)而言,它的調(diào)度算法是基于POSIX規(guī)定的基于事件驅(qū)動優(yōu)先級的調(diào)度算法,為了及時響應(yīng)高優(yōu)先級進程,它寧愿犧牲整體效率。 調(diào)度的實現(xiàn)可以分為2步來完成： ① 何時啟動調(diào)度,即解決調(diào)度啟動時機的問題;
�、� 怎么調(diào)度,按優(yōu)先級調(diào)度就是要找到系統(tǒng)當(dāng)前優(yōu)先級最高的進程,然后進行上下文切換。 在實時系統(tǒng)中,只有當(dāng)就緒進程集合發(fā)生變動時才有調(diào)度的需要,而就緒進程集合的變動只可能發(fā)生在幾種情況下： �、� 運行中的進程受阻或自動放棄CPU;
② 系統(tǒng)中新建了進程;
③ 運行中的進程“自殺”或“被殺”;
�、� 運行中的進程喚醒了某個線程;
�、� 中斷服務(wù)子程序結(jié)束時喚醒了其他進程。 理想情況下,實時系統(tǒng)在有高優(yōu)先級的進程轉(zhuǎn)入就緒態(tài)時,就應(yīng)該立即啟動調(diào)度程序,響應(yīng)高優(yōu)先級進程。但實際上卻存在著不可調(diào)度的時隙,稱為不可調(diào)度窗口： �、� 正在進行進程切換,不能進行調(diào)度;
② 中斷響應(yīng)期間,不能進行調(diào)度;
�、� 進入臨界區(qū),不能進行調(diào)度;
④ DMA期間CPU已被掛起,不可能進行調(diào)度。 在實時系統(tǒng)里,必須努力縮小不可調(diào)度窗口。 在調(diào)度啟動的時機上,所有的實時操作系統(tǒng)基本一致。那么接下來要做的就是尋找系統(tǒng)中當(dāng)前最應(yīng)該得到運行機會的進程,下面分別看一個最簡單的和比較復(fù)雜的實現(xiàn)。 1 μC/OS-II的實現(xiàn) 在μC/OS-II里,只允許有64個優(yōu)先級且不同進程優(yōu)先級互不相同。把64個優(yōu)先級分成8組,數(shù)據(jù)結(jié)構(gòu)位圖OSRdyGrp反映著哪一些進程組中有就緒進程。另外,各個進程組的標(biāo)志位在位圖中的位置也是有規(guī)律的,位置靠右邊的標(biāo)志位代表優(yōu)先級較高的進程組,只要從右到左掃描位圖OSRdyGrp,碰到第一個非0的標(biāo)志位就代表當(dāng)前優(yōu)先級最高的就緒進程所在的進程組。這樣,就可以預(yù)先編制一個對照表,即數(shù)組。此數(shù)組就是OSUnMapTbl[](該表的詳細描述可參閱參考文獻[1]的88～90頁),以位圖OSRdyGrp的數(shù)值為下標(biāo),就可以直接得到優(yōu)先級最高者所屬組號。 8個標(biāo)志位共有256種不同組合,所以這個數(shù)組大小是256。為了便于與μC/OS-II源代碼對照,把以O(shè)SRdyGrp的數(shù)值為下標(biāo),在OSUnMapTbl[]數(shù)組中查得的值稱為組號y。知道組號y以后,就可以以此為下標(biāo)在OSRdyTbl[]中得到相應(yīng)的組內(nèi)位圖。同理,以這個位圖的數(shù)值OSRdyTbl[y]為下標(biāo),又可以在OSUnMapTbl[]內(nèi)查得該組內(nèi)優(yōu)先級最高者進程號。將組號和組內(nèi)號拼合在一起,就得到了目標(biāo)進程完整的進程號,即優(yōu)先級。再以此為下標(biāo),就可以從OSTCBPrioTbl[]中得到指向目標(biāo)進程控制塊的OSTCBHighRdy。以下就是進程切換的工作了。 通過上面的分析,不難理解下面這樣的語句了： y=OSUnMapTbl[OSRdyGrp];
OSTCBHighRdy=(INT8U)((y<<3)+ OSUnMapTbl[OSRdyTbl[y]]);
If(OSTCBHighRdy!=OSPRIOCur){進程切換;}; 這個過程如此簡潔,其根本原因是μC/OS-II嚴格按優(yōu)先級調(diào)度,并且每個優(yōu)先級只有一個進程。如果優(yōu)先級的使用并非唯一,多個線程可以使用相同的優(yōu)先級,那就還有個相同優(yōu)先級的就緒進程之間怎樣調(diào)度的問題,這就使調(diào)度過程復(fù)雜化了。一些商品的實時操作系統(tǒng),例如VxWorks,允許多個進程具有相同的優(yōu)先級,因為不支持不同進程可以有相同優(yōu)先級的系統(tǒng),無法采用優(yōu)先級繼承算法來解決實時系統(tǒng)里令人討厭的優(yōu)先級反轉(zhuǎn)現(xiàn)象,但它不公開源代碼。下面選擇一個公開源代碼的實時操作系統(tǒng)Nut/OS進行分析。它有256個優(yōu)先級且允許不同進程具有相同的優(yōu)先級。在這樣的系統(tǒng)里,是不可能采用類似于位圖這樣的機制來實現(xiàn)調(diào)度的。 2 Nut/OS的實現(xiàn) 為了敘述方便,設(shè)計一個完整的進程運行的情景來說明。另外Nut/OS中采用了線程的概念,在不分系統(tǒng)空間和用戶空間的系統(tǒng)中,進程等價于線程。而進程和任務(wù)本來就是同一個概念的不同叫法。Nut/OS是一個嵌入式實時操作系統(tǒng),不分系統(tǒng)空間和用戶空間,所以以下的敘述中,線程、進程和任務(wù)混用,意思完全一樣。 在Nut/OS中,可以通過下面的函數(shù)創(chuàng)建一個線程： HANDLE NutThreadCreate(u_char *name,void(*fn)(void*),void *arg,size_t stacksize); 創(chuàng)建一個線程的過程,實際上就是從堆棧空間中申請一個放置線程控制塊的空間,在這個空間中建立線程控制塊并完成對控制塊的賦值的過程。為了更好地說明線程控制塊的作用,下面用一個圖表來說明,如圖1所示。 
圖1 線程控制塊圖解(對NUTTHREADINFO數(shù)據(jù)結(jié)構(gòu)有刪減)
如果創(chuàng)建成功,NutThreadCreate()將返回一個指向新創(chuàng)建的線程控制塊的指針,新創(chuàng)建的線程控制塊將放置在線程控制塊鏈表前面,nutThreadList指針總是指向這個鏈表的第一個控制快�，F(xiàn)在假設(shè)某一個應(yīng)用中只有3個線程,1個隱藏線程、1個主線程和1個應(yīng)用線程。其中隱藏線程（threads3）中創(chuàng)建了主線程（Threads2）,主線程中又創(chuàng)建了應(yīng)用線程（Threads1）。由于一開始只有一個隱藏線程,因此nutThreadList鏈表指向了隱藏線程。當(dāng)隱藏線程創(chuàng)建了主線程時,主線程控制塊添加在隱藏線程控制快鏈表的前面,因此nutThreadList鏈表指向主線程。當(dāng)主線程創(chuàng)建了應(yīng)用線程,應(yīng)用線程控制塊添加在主線程控制塊的前面,因此nutThreadList鏈表改為指向應(yīng)用線程。這就組成了一個如圖2所示的鏈表。 
注: ① nutthreadlist即全部創(chuàng)建的線程鏈表;② runQuene即全部就緒態(tài)并按優(yōu)先級排隊的線程鏈表;③ eventQuene即進入等待事件而掛起的全部線程鏈表;④ nutTimerList即進入延時而掛起的全部線程鏈表。
圖2 圖解線程鏈表
由圖2可知,Nut/OS采用4個鏈表來管理系統(tǒng)中的全部線程,其中runQuene總是指向全部就緒線程鏈表,這個鏈表由td_qnxt指針鏈成。td_qnxt鏈表與td_next鏈表形成機制不同。在td_next鏈表中,新創(chuàng)建的線程總是簡單地放在鏈表的前面,這個鏈表包括所有的線程控制塊;而td_qnxt鏈表是根據(jù)優(yōu)先級順序排序的,一個線程只有處于就緒態(tài)（TDS_READY）或者運行態(tài)(TDS_RUNNING)才能包括在這個鏈表中。 隱藏線程的優(yōu)先級為254,并且總是將該線程的td_next和td_qnxt設(shè)為空指針。線程的退出機制就是將要退出的線程的優(yōu)先級設(shè)為255。由于這個線程的優(yōu)先級比隱藏線程還低,而隱藏線程又沒有指向該線程的指針,因此這個退出線程永遠也不可能被運行。 按優(yōu)先級調(diào)度是通過runQuene鏈表來實現(xiàn)的。Nut/OS提供了2個API來操作這個鏈表,其中插入操作的代碼如下： void NutThreadAddPriQueue(NUTTHREADINFO * td, NUTTHREADINFO ** tqpp) {
NUTTHREADINFO *tqp;
td->td_queue = tqpp;
tqp = *tqpp;
while (tqp && (tqp->td_priority <= td->td_priority)) {
tqpp = &tqp->td_qnxt;
tqp = tqp->td_qnxt;
}
td->td_qnxt = tqp;
*tqpp = td;
} 該API函數(shù)表明,runQuene鏈表是一個按優(yōu)先級排序的鏈表,優(yōu)先級高的線程控制塊總是在最前面,當(dāng)發(fā)現(xiàn)有相同優(yōu)先級的線程控制快時,總是把后來的插到相同優(yōu)先級線程控制塊的最后面。這就自然實現(xiàn)了對相同優(yōu)先級線程按先來先服務(wù)的算法進行調(diào)度。 當(dāng)就緒進程集合發(fā)生變動時,則調(diào)用NutThreadRemoveQueue()、NutThreadAddPriQueue()完成鏈表的更新讓runQuene指向更新后的鏈表頭。接下來的事就是上下文切換了。 通過鏈表這個簡單的數(shù)據(jù)結(jié)構(gòu),Nut/OS也很簡潔地實現(xiàn)了實時調(diào)度算法。閱讀過Linux源代碼的人對鏈表的重要性可能更是感同身受,雖然Linux操作系統(tǒng)堪稱完美,但源代碼卻并不怎么規(guī)范,事實上造成了Linux源代碼復(fù)雜難懂;而同是開源的Nut/OS,代碼卻相當(dāng)規(guī)范,給我們提供了非常好的學(xué)習(xí)資料。筆者在這里感謝該系統(tǒng)的開發(fā)人員Harald Kipp和沈文先生等,以及那些熱愛開源并熱心奉獻的工程師。 結(jié)語 μC/OS-II的實時性已經(jīng)通過了非常嚴格的測試,事實上成了筆者比較其他系統(tǒng)實時性能的一個基準(zhǔn)。在這次畢業(yè)設(shè)計工作中,采用Nut/OS實現(xiàn)8位機接入以太網(wǎng),運行良好。不妨推測,在一些商品實時操作系統(tǒng)里,對優(yōu)先級調(diào)度算法的實現(xiàn)采用的機制和Nut/OS是類似的。 參考文獻 1 LabrosseJan J. 嵌入式實時操作系統(tǒng)μC/OSII. 邵貝貝,等譯. 第2版. 北京：北京航空航天大學(xué)出版社,2003
2 毛德操,胡希明. 嵌入式系統(tǒng)——采用公開源代碼和StrongARM/XScale處理器.杭州：浙江大學(xué)出版社,2003
3 www.ethernut.de
4 www.fjmcu.com許慶春:碩士研究生,主要研究方向為電子信息技術(shù)工程。 吳光敏 教授,主要研究方向為嵌入式系統(tǒng)和網(wǎng)絡(luò)集成。 |
66821730(技術(shù)支持)
