Nut/OS和μC/OS—II的實(shí)時(shí)調(diào)度算法比較

　　如果說CPU是計(jì)算機(jī)系統(tǒng)的心臟，那么進(jìn)程調(diào)度就是計(jì)算機(jī)系統(tǒng)的靈魂，因?yàn)樗鼪Q定了如何使用CPU。例如，Linux是一個多任務(wù)操作系統(tǒng)，它的理想狀況是保持CPU有效運(yùn)行。如果某個正在運(yùn)行的進(jìn)程轉(zhuǎn)入等待系統(tǒng)資源，操作系統(tǒng)就調(diào)度其他進(jìn)程運(yùn)行，從而保證CPU的最大利用率。如何使系統(tǒng)能夠保證較短的響應(yīng)時(shí)間和較高的吞吐量，使得多個進(jìn)程競爭CPU時(shí)保持公平、高效，是通用操作系統(tǒng)所追求的目標(biāo)。但對于實(shí)時(shí)操作系統(tǒng)而言，它的調(diào)度算法是基于POSIX規(guī)定的基于事件驅(qū)動優(yōu)先級的調(diào)度算法，為了及時(shí)響應(yīng)高優(yōu)先級進(jìn)程，它寧愿犧牲整體效率。

　　調(diào)度的實(shí)現(xiàn)可以分為2步來完成：

　?、俸螘r(shí)啟動調(diào)度，即解決調(diào)度啟動時(shí)機(jī)的問題；

　　②怎么調(diào)度，按優(yōu)先級調(diào)度就是要找到系統(tǒng)當(dāng)前優(yōu)先級最高的進(jìn)程，然后進(jìn)行上下文切換。

　　在實(shí)時(shí)系統(tǒng)中，只有當(dāng)就緒進(jìn)程集合發(fā)生變動時(shí)才有調(diào)度的需要，而就緒進(jìn)程集合的變動只可能發(fā)生在幾種情況下：

　　①運(yùn)行中的進(jìn)程受阻或自動放棄CPU；

　　②系統(tǒng)中新建了進(jìn)程；

　　③運(yùn)行中的進(jìn)程“自殺”或“被殺”；

　?、苓\(yùn)行中的進(jìn)程喚醒了某個線程；

　?、葜袛喾?wù)子程序結(jié)束時(shí)喚醒了其他進(jìn)程。

　　理想情況下，實(shí)時(shí)系統(tǒng)在有高優(yōu)先級的進(jìn)程轉(zhuǎn)入就緒態(tài)時(shí)，就應(yīng)該立即啟動調(diào)度程序，響應(yīng)高優(yōu)先級進(jìn)程。但實(shí)際上卻存在著不可調(diào)度的時(shí)隙，稱為不可調(diào)度窗口：

　?、僬谶M(jìn)行進(jìn)程切換，不能進(jìn)行調(diào)度；

　?、谥袛囗憫?yīng)期間，不能進(jìn)行調(diào)度；

　　③進(jìn)入臨界區(qū)，不能進(jìn)行調(diào)度；

　?、蹹MA期間CPU已被掛起，不可能進(jìn)行調(diào)度。

　　在實(shí)時(shí)系統(tǒng)里，必須努力縮小不可調(diào)度窗口。

　　在調(diào)度啟動的時(shí)機(jī)上，所有的實(shí)時(shí)操作系統(tǒng)基本一致。

　　那么接下來要做的就是尋找系統(tǒng)中當(dāng)前最應(yīng)該得到運(yùn)行機(jī)會的進(jìn)程，下面分別看一個最簡單的和比較復(fù)雜的實(shí)現(xiàn)。

　　1 μC/OS-Il的實(shí)現(xiàn)

　　在μC／OS-II里。只允許有64個優(yōu)先級且不同進(jìn)程優(yōu)先級互不相同。把64個優(yōu)先級分成8組，數(shù)據(jù)結(jié)構(gòu)位圖OSRdyGrp反映著哪一些進(jìn)程組中有就緒進(jìn)程。另外，各個進(jìn)程組的標(biāo)志位在位圖中的位置也是有規(guī)律的，位置靠右邊的標(biāo)志位代表優(yōu)先級較高的進(jìn)程組，只要從右到左掃描位圖OSRdyGrp，碰到第一個非0的標(biāo)志位就代表當(dāng)前優(yōu)先級最高的就緒進(jìn)程所在的進(jìn)程組。這樣，就可以預(yù)先編制一個對照表，即數(shù)組。此數(shù)組就是OStJnMapTbl[](該表的詳細(xì)描述可參閱參考文獻(xiàn)的88～90頁)，以位圖OSRdyGrp的數(shù)值為下標(biāo)，就可以直接得到優(yōu)先級最高者所屬組號。

　　8個標(biāo)志位共有256種不同組合，所以這個數(shù)組大小是256。為了便于與μC／OS-II源代碼對照，把以O(shè)SRdyGrp的數(shù)值為下標(biāo)，在OSTJnMapTbl[]數(shù)組中查得的值稱為組號y。知道組號y以后，就可以以此為下標(biāo)在OSRdyTbl[]中得到相應(yīng)的組內(nèi)位圖。同理，以這個位圖的數(shù)值OSRdyThl[y]為下標(biāo)，又可以在OSUnMapTbl[]內(nèi)查得該組內(nèi)優(yōu)先級最高者進(jìn)程號。將組號和組內(nèi)號拼合在一起，就得到了目標(biāo)進(jìn)程完整的進(jìn)程號，即優(yōu)先級。再以此為下標(biāo)，就可以從OSTcBPrioTbl[]中得到指向目標(biāo)進(jìn)程控制塊的OSTCBHighRdy。以下就是進(jìn)程切換的工作了。

　　通過上面的分析，不難理解下面這樣的語句了：這個過程如此簡潔，其根本原因是μC／OS-II嚴(yán)格按優(yōu)先級調(diào)度，并且每個優(yōu)先級只有一個進(jìn)程。如果優(yōu)先級的使用并非唯一，多個線程可以使用相同的優(yōu)先級，那就還有個相同優(yōu)先級的就緒進(jìn)程之間怎樣調(diào)度的問題，這就使調(diào)度過程復(fù)雜化了。一些商品的實(shí)時(shí)操作系統(tǒng)，例如VxWorks，允許多個進(jìn)程具有相同的優(yōu)先級，因?yàn)椴恢С植煌M(jìn)程可以有相同優(yōu)先級的系統(tǒng)，無法采用優(yōu)先級繼承算法來解決實(shí)時(shí)系統(tǒng)里令人討厭的優(yōu)先級反轉(zhuǎn)現(xiàn)象，但它不公開源代碼。下面選擇一個公開源代碼的實(shí)時(shí)操作系統(tǒng)Nut/OS進(jìn)行分析。它有256個優(yōu)先級且允許不同進(jìn)程具有相同的優(yōu)先級。在這樣的系統(tǒng)里，是不可能采用類似于位圖這樣的機(jī)制來實(shí)現(xiàn)調(diào)度的。

　　2Nut／OS的實(shí)現(xiàn)

為了敘述方便，設(shè)計(jì)一個完整的進(jìn)程運(yùn)行的情景來說明。另外Nut／0S中采用了線程的概念，在不分系統(tǒng)空間和用戶空間的系統(tǒng)中，進(jìn)程等價(jià)于線程。而進(jìn)程和任務(wù)本來就是同一個概念的不同叫法。Nut／Os是一個嵌入式實(shí)時(shí)操作系統(tǒng)，不分系統(tǒng)空間和用戶空間，所以以下的敘述中，線程、進(jìn)程和任務(wù)混用，意思完全一樣。

　　在Nut／OS中，可以通過下面的函數(shù)創(chuàng)建一個線程：

　　創(chuàng)建一個線程的過程，實(shí)際上就是從堆棧空間中申請一個放置線程控制塊的空間，在這個空間中建立線程控制塊并完成對控制塊的賦值的過程。為了更好地說明線程控制塊的作用，下面用一個圖表來說明，如圖1所示。

　　如果創(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)用線程(Threadsl)。由于一開始只有一個隱藏線程，因此nutThreadList鏈表指向了隱藏線程。當(dāng)隱藏線程創(chuàng)建了主線程時(shí)，主線程控制塊添加在隱藏線程控制快鏈表的前面，因此nutThreadList鏈表指向主線程。當(dāng)主線程創(chuàng)建了應(yīng)用線程，應(yīng)用線程控制塊添加在主線程控制塊的前面，因此nutThreadList鏈表改為指向應(yīng)用線程。這就組成了一個如圖2所示的鏈表。

　　由圖2可知，Nut/OS采用4個鏈表來管理系統(tǒng)中的全部線程，其中runQuene總是指向全部就緒線程鏈表，這個鏈表由td_qnxt指針鏈成。td_qnxt鏈表與td_next鏈表形成機(jī)制不同。在td_next鏈表中，新創(chuàng)建的線程總是簡單地放在鏈表的前面，這個鏈表包括所有的線程控制塊；而td_q
nxt鏈表是根據(jù)優(yōu)先級順序排序的，一個線程只有處于就緒態(tài)(TDs_READY)或者運(yùn)態(tài)(TDS_RUNNING)才能包括在這個鏈表中。

　　隱藏線程的優(yōu)先級為254，并且總是將該線程的td_next和td_qnxt設(shè)為空指針。線程的退出機(jī)制就是將要退出的線程的優(yōu)先級設(shè)為255。由于這個線程的優(yōu)先級比隱藏線程還低，而隱藏線程又沒有指向該線程的指針，因此這個退出線程永遠(yuǎn)也不可能被運(yùn)行。

　　按優(yōu)先級調(diào)度是通過mnQuene鏈表來實(shí)現(xiàn)的。Nut/OS提供了2個API來操作這個鏈表，其中插入操作的代碼如下：

　　該API函數(shù)表明，runQuene鏈表是一個按優(yōu)先級排序的鏈表，優(yōu)先級高的線程控制塊總是在最前面，當(dāng)發(fā)現(xiàn)有相同優(yōu)先級的線程控制快時(shí)，總是把后來的插到相同優(yōu)先級線程控制塊的最后面。這就自然實(shí)現(xiàn)了對相同優(yōu)先級線程按先來先服務(wù)的算法進(jìn)行調(diào)度。

　　當(dāng)就緒進(jìn)程集合發(fā)生變動時(shí)，則調(diào)用NutThreadRemoveQueue()、NutThreadAddPriQueue()完成鏈表的更新讓runQuene指向更新后的鏈表頭。接下來的事就是上下文切換了。

　　通過鏈表這個簡單的數(shù)據(jù)結(jié)構(gòu)，Nut/OS也很簡潔地實(shí)現(xiàn)了實(shí)時(shí)調(diào)度算法。閱讀過Linux源代碼的人對鏈表的重要性可能更是感同身受，雖然Linux操作系統(tǒng)堪稱完美，但源代碼卻并不怎么規(guī)范，事實(shí)上造成了Linux源代碼復(fù)雜難懂；而同是開源的Nut/OS，代碼卻相當(dāng)規(guī)范，給我們提供了非常好的學(xué)習(xí)資料。筆者在這里感謝該系統(tǒng)的開發(fā)人員Harald Kipp和沈文先生等，以及那些熱愛開源并熱心奉獻(xiàn)的工程師。

　　結(jié)語

　　μC/OS-II的實(shí)時(shí)性已經(jīng)通過了非常嚴(yán)格的測試，事實(shí)上成了筆者比較其他系統(tǒng)實(shí)時(shí)性能的一個基準(zhǔn)。在這次畢業(yè)設(shè)計(jì)工作中，采用Nut/OS實(shí)現(xiàn)8位機(jī)接入以太網(wǎng)，運(yùn)行良好。不妨推測，在一些商品實(shí)時(shí)操作系統(tǒng)里，對優(yōu)先級調(diào)度算法的實(shí)現(xiàn)采用的機(jī)制和Nut／OS是類似的。