Nut/OS和μC/OS—II的實時調度算法比較

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

　　調度的實現可以分為2步來完成：

　　①何時啟動調度，即解決調度啟動時機的問題；

　　②怎么調度，按優先級調度就是要找到系統當前優先級最高的進程，然后進行上下文切換。

　　在實時系統中，只有當就緒進程集合發生變動時才有調度的需要，而就緒進程集合的變動只可能發生在幾種情況下：

　　①運行中的進程受阻或自動放棄CPU；

　　②系統中新建了進程；

　　③運行中的進程“自殺”或“被殺”；

　　④運行中的進程喚醒了某個線程；

　　⑤中斷服務子程序結束時喚醒了其他進程。

　　理想情況下，實時系統在有高優先級的進程轉入就緒態時，就應該立即啟動調度程序，響應高優先級進程。但實際上卻存在著不可調度的時隙，稱為不可調度窗口：

　　①正在進行進程切換，不能進行調度；

　　②中斷響應期間，不能進行調度；

　　③進入臨界區，不能進行調度；

　　④DMA期間CPU已被掛起，不可能進行調度。

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

　　在調度啟動的時機上，所有的實時操作系統基本一致。

　　那么接下來要做的就是尋找系統中當前最應該得到運行機會的進程，下面分別看一個最簡單的和比較復雜的實現。

　　1 μC/OS-Il的實現

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

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

　　通過上面的分析，不難理解下面這樣的語句了：這個過程如此簡潔，其根本原因是μC／OS-II嚴格按優先級調度，并且每個優先級只有一個進程。如果優先級的使用并非唯一，多個線程可以使用相同的優先級，那就還有個相同優先級的就緒進程之間怎樣調度的問題，這就使調度過程復雜化了。一些商品的實時操作系統，例如VxWorks，允許多個進程具有相同的優先級，因為不支持不同進程可以有相同優先級的系統，無法采用優先級繼承算法來解決實時系統里令人討厭的優先級反轉現象，但它不公開源代碼。下面選擇一個公開源代碼的實時操作系統Nut/OS進行分析。它有256個優先級且允許不同進程具有相同的優先級。在這樣的系統里，是不可能采用類似于位圖這樣的機制來實現調度的。

　　2Nut／OS的實現

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

　　在Nut／OS中，可以通過下面的函數創建一個線程：

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

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

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

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

　　按優先級調度是通過mnQuene鏈表來實現的。Nut/OS提供了2個API來操作這個鏈表，其中插入操作的代碼如下：

　　該API函數表明，runQuene鏈表是一個按優先級排序的鏈表，優先級高的線程控制塊總是在最前面，當發現有相同優先級的線程控制快時，總是把后來的插到相同優先級線程控制塊的最后面。這就自然實現了對相同優先級線程按先來先服務的算法進行調度。

　　當就緒進程集合發生變動時，則調用NutThreadRemoveQueue()、NutThreadAddPriQueue()完成鏈表的更新讓runQuene指向更新后的鏈表頭。接下來的事就是上下文切換了。

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

　　結語

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