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

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

調度的實(shí)現可以分為2步來(lái)完成：
①何時(shí)啟動(dòng)調度，即解決調度啟動(dòng)時(shí)機的問(wèn)題；
②怎么調度，按優(yōu)先級調度就是要找到系統當前優(yōu)先級最高的進(jìn)程，然后進(jìn)行上下文切換。

在實(shí)時(shí)系統中，只有當就緒進(jìn)程集合發(fā)生變動(dòng)時(shí)才有調度的需要，而就緒進(jìn)程集合的變動(dòng)只可能發(fā)生在幾種情況下：
①運行中的進(jìn)程受阻或自動(dòng)放棄CPU；
②系統中新建了進(jìn)程；
③運行中的進(jìn)程“自殺”或“被殺”；
④運行中的進(jìn)程喚醒了某個(gè)線(xiàn)程；
⑤中斷服務(wù)子程序結束時(shí)喚醒了其他進(jìn)程。

理想情況下，實(shí)時(shí)系統在有高優(yōu)先級的進(jìn)程轉入就緒態(tài)時(shí)，就應該立即啟動(dòng)調度程序，響應高優(yōu)先級進(jìn)程。但實(shí)際上卻存在著(zhù)不可調度的時(shí)隙，稱(chēng)為不可調度窗口：
①正在進(jìn)行進(jìn)程切換，不能進(jìn)行調度；
②中斷響應期間，不能進(jìn)行調度；
③進(jìn)入臨界區，不能進(jìn)行調度；
④DMA期間CPU已被掛起，不可能進(jìn)行調度。

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

在調度啟動(dòng)的時(shí)機上，所有的實(shí)時(shí)操作系統基本一致。

那么接下來(lái)要做的就是尋找系統中當前最應該得到運行機會(huì )的進(jìn)程，下面分別看一個(gè)最簡(jiǎn)單的和比較復雜的實(shí)現。

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

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

通過(guò)上面的分析，不難理解下面這樣的語(yǔ)句了：

這個(gè)過(guò)程如此簡(jiǎn)潔，其根本原因是μC／OS-II嚴格按優(yōu)先級調度，并且每個(gè)優(yōu)先級只有一個(gè)進(jìn)程。如果優(yōu)先級的使用并非唯一，多個(gè)線(xiàn)程可以使用相同的優(yōu)先級，那就還有個(gè)相同優(yōu)先級的就緒進(jìn)程之間怎樣調度的問(wèn)題，這就使調度過(guò)程復雜化了。一些商品的實(shí)時(shí)操作系統，例如VxWorks，允許多個(gè)進(jìn)程具有相同的優(yōu)先級，因為不支持不同進(jìn)程可以有相同優(yōu)先級的系統，無(wú)法采用優(yōu)先級繼承算法來(lái)解決實(shí)時(shí)系統里令人討厭的優(yōu)先級反轉現象，但它不公開(kāi)源代碼。下面選擇一個(gè)公開(kāi)源代碼的實(shí)時(shí)操作系統Nut/OS進(jìn)行分析。它有256個(gè)優(yōu)先級且允許不同進(jìn)程具有相同的優(yōu)先級。在這樣的系統里，是不可能采用類(lèi)似于位圖這樣的機制來(lái)實(shí)現調度的。

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

在Nut／OS中，可以通過(guò)下面的函數創(chuàng )建一個(gè)線(xiàn)程：

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

如果創(chuàng )建成功，NutThreadCreate()將返回一個(gè)指向新創(chuàng )建的線(xiàn)程控制塊的指針，新創(chuàng )建的線(xiàn)程控制塊將放置在線(xiàn)程控制塊鏈表前面，nutThreadList指針總是指向這個(gè)鏈表的第一個(gè)控制快?，F在假設某一個(gè)應用中只有3個(gè)線(xiàn)程，1個(gè)隱藏線(xiàn)程、1個(gè)主線(xiàn)程和1個(gè)應用線(xiàn)程。其中隱藏線(xiàn)程(threads3)中創(chuàng )建了主線(xiàn)程(Threads2)，主線(xiàn)程中又創(chuàng )建了應用線(xiàn)程(Threadsl)。由于一開(kāi)始只有一個(gè)隱藏線(xiàn)程，因此nutThreadList鏈表指向了隱藏線(xiàn)程。當隱藏線(xiàn)程創(chuàng )建了主線(xiàn)程時(shí)，主線(xiàn)程控制塊添加在隱藏線(xiàn)程控制快鏈表的前面，因此nutThreadList鏈表指向主線(xiàn)程。當主線(xiàn)程創(chuàng )建了應用線(xiàn)程，應用線(xiàn)程控制塊添加在主線(xiàn)程控制塊的前面，因此nutThreadList鏈表改為指向應用線(xiàn)程。這就組成了一個(gè)如圖2所示的鏈表。

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

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

按優(yōu)先級調度是通過(guò)mnQuene鏈表來(lái)實(shí)現的。Nut/OS提供了2個(gè)API來(lái)操作這個(gè)鏈表，其中插入操作的代碼如下：

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

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

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

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