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

如果說(shuō)CPU是計(jì)算機(jī)系統(tǒng)的心臟，那么進(jìn)程調(diào)度就是計(jì)算機(jī)系統(tǒng)的靈魂，因?yàn)樗鼪Q定了如何使用CPU。例如，Linux是一個(gè)多任務(wù)操作系統(tǒng)，它的理想狀況是保持CPU有效運(yùn)行。如果某個(gè)正在運(yùn)行的進(jìn)程轉(zhuǎn)入等待系統(tǒng)資源，操作系統(tǒng)就調(diào)度其他進(jìn)程運(yùn)行，從而保證CPU的最大利用率。如何使系統(tǒng)能夠保證較短的響應(yīng)時(shí)間和較高的吞吐量，使得多個(gè)進(jìn)程競(jìng)爭(zhēng)CPU時(shí)保持公平、高效，是通用操作系統(tǒng)所追求的目標(biāo)。但對(duì)于實(shí)時(shí)操作系統(tǒng)而言，它的調(diào)度算法是基于POSIX規(guī)定的基于事件驅(qū)動(dòng)優(yōu)先級(jí)的調(diào)度算法，為了及時(shí)響應(yīng)高優(yōu)先級(jí)進(jìn)程，它寧愿犧牲整體效率。
　　調(diào)度的實(shí)現(xiàn)可以分為2步來(lái)完成：
　?、俸螘r(shí)啟動(dòng)調(diào)度，即解決調(diào)度啟動(dòng)時(shí)機(jī)的問(wèn)題；
　　②怎么調(diào)度，按優(yōu)先級(jí)調(diào)度就是要找到系統(tǒng)當(dāng)前優(yōu)先級(jí)最高的進(jìn)程，然后進(jìn)行上下文切換。
　　在實(shí)時(shí)系統(tǒng)中，只有當(dāng)就緒進(jìn)程集合發(fā)生變動(dòng)時(shí)才有調(diào)度的需要，而就緒進(jìn)程集合的變動(dòng)只可能發(fā)生在幾種情況下：
　?、龠\(yùn)行中的進(jìn)程受阻或自動(dòng)放棄CPU；
　?、谙到y(tǒng)中新建了進(jìn)程；
　?、圻\(yùn)行中的進(jìn)程“自殺”或“被殺”；
　?、苓\(yùn)行中的進(jìn)程喚醒了某個(gè)線程；
　?、葜袛喾?wù)子程序結(jié)束時(shí)喚醒了其他進(jìn)程。
　　理想情況下，實(shí)時(shí)系統(tǒng)在有高優(yōu)先級(jí)的進(jìn)程轉(zhuǎn)入就緒態(tài)時(shí)，就應(yīng)該立即啟動(dòng)調(diào)度程序，響應(yīng)高優(yōu)先級(jí)進(jìn)程。但實(shí)際上卻存在著不可調(diào)度的時(shí)隙，稱(chēng)為不可調(diào)度窗口：
　　①正在進(jìn)行進(jìn)程切換，不能進(jìn)行調(diào)度；
　?、谥袛囗憫?yīng)期間，不能進(jìn)行調(diào)度；
　　③進(jìn)入臨界區(qū)，不能進(jìn)行調(diào)度；
　　④DMA期間CPU已被掛起，不可能進(jìn)行調(diào)度。
　　在實(shí)時(shí)系統(tǒng)里，必須努力縮小不可調(diào)度窗口。
　　在調(diào)度啟動(dòng)的時(shí)機(jī)上，所有的實(shí)時(shí)操作系統(tǒng)基本一致。
　　那么接下來(lái)要做的就是尋找系統(tǒng)中當(dāng)前最應(yīng)該得到運(yùn)行機(jī)會(huì)的進(jìn)程，下面分別看一個(gè)最簡(jiǎn)單的和比較復(fù)雜的實(shí)現(xiàn)。
　　1 μC/OS-Il的實(shí)現(xiàn)
　　在μC／OS-II里。只允許有64個(gè)優(yōu)先級(jí)且不同進(jìn)程優(yōu)先級(jí)互不相同。把64個(gè)優(yōu)先級(jí)分成8組，數(shù)據(jù)結(jié)構(gòu)位圖OSRdyGrp反映著哪一些進(jìn)程組中有就緒進(jìn)程。另外，各個(gè)進(jìn)程組的標(biāo)志位在位圖中的位置也是有規(guī)律的，位置靠右邊的標(biāo)志位代表優(yōu)先級(jí)較高的進(jìn)程組，只要從右到左掃描位圖OSRdyGrp，碰到第一個(gè)非0的標(biāo)志位就代表當(dāng)前優(yōu)先級(jí)最高的就緒進(jìn)程所在的進(jìn)程組。這樣，就可以預(yù)先編制一個(gè)對(duì)照表，即數(shù)組。此數(shù)組就是OStJnMapTbl［］（該表的詳細(xì)描述可參閱參考文獻(xiàn)的88～90頁(yè)），以位圖OSRdyGrp的數(shù)值為下標(biāo)，就可以直接得到優(yōu)先級(jí)最高者所屬組號(hào)。
　　8個(gè)標(biāo)志位共有256種不同組合，所以這個(gè)數(shù)組大小是256。為了便于與μC／OS-II源代碼對(duì)照，把以O(shè)SRdyGrp的數(shù)值為下標(biāo)，在OSTJnMapTbl［］數(shù)組中查得的值稱(chēng)為組號(hào)y。知道組號(hào)y以后，就可以以此為下標(biāo)在OSRdyTbl［］中得到相應(yīng)的組內(nèi)位圖。同理，以這個(gè)位圖的數(shù)值OSRdyThl［y］為下標(biāo)，又可以在OSUnMapTbl［］內(nèi)查得該組內(nèi)優(yōu)先級(jí)最高者進(jìn)程號(hào)。將組號(hào)和組內(nèi)號(hào)拼合在一起，就得到了目標(biāo)進(jìn)程完整的進(jìn)程號(hào)，即優(yōu)先級(jí)。再以此為下標(biāo)，就可以從OSTcBPrioTbl［］中得到指向目標(biāo)進(jìn)程控制塊的OSTCBHighRdy。以下就是進(jìn)程切換的工作了。
　　通過(guò)上面的分析，不難理解下面這樣的語(yǔ)句了：這個(gè)過(guò)程如此簡(jiǎn)潔，其根本原因是μC／OS-II嚴(yán)格按優(yōu)先級(jí)調(diào)度，并且每個(gè)優(yōu)先級(jí)只有一個(gè)進(jìn)程。如果優(yōu)先級(jí)的使用并非唯一，多個(gè)線程可以使用相同的優(yōu)先級(jí)，那就還有個(gè)相同優(yōu)先級(jí)的就緒進(jìn)程之間怎樣調(diào)度的問(wèn)題，這就使調(diào)度過(guò)程復(fù)雜化了。一些商品的實(shí)時(shí)操作系統(tǒng)，例如VxWorks，允許多個(gè)進(jìn)程具有相同的優(yōu)先級(jí)，因?yàn)椴恢С植煌M(jìn)程可以有相同優(yōu)先級(jí)的系統(tǒng)，無(wú)法采用優(yōu)先級(jí)繼承算法來(lái)解決實(shí)時(shí)系統(tǒng)里令人討厭的優(yōu)先級(jí)反轉(zhuǎn)現(xiàn)象，但它不公開(kāi)源代碼。下面選擇一個(gè)公開(kāi)源代碼的實(shí)時(shí)操作系統(tǒng)Nut/OS進(jìn)行分析。它有256個(gè)優(yōu)先級(jí)且允許不同進(jìn)程具有相同的優(yōu)先級(jí)。在這樣的系統(tǒng)里，是不可能采用類(lèi)似于位圖這樣的機(jī)制來(lái)實(shí)現(xiàn)調(diào)度的。
　　2Nut／OS的實(shí)現(xiàn)
　　為了敘述方便，設(shè)計(jì)一個(gè)完整的進(jìn)程運(yùn)行的情景來(lái)說(shuō)明。另外Nut／0S中采用了線程的概念，在不分系統(tǒng)空間和用戶空間的系統(tǒng)中，進(jìn)程等價(jià)于線程。而進(jìn)程和任務(wù)本來(lái)就是同一個(gè)概念的不同叫法。Nut／Os是一個(gè)嵌入式實(shí)時(shí)操作系統(tǒng)，不分系統(tǒng)空間和用戶空間，所以以下的敘述中，線程、進(jìn)程和任務(wù)混用，意思完全一樣。
　　在Nut／OS中，可以通過(guò)下面的函數(shù)創(chuàng)建一個(gè)線程：
　　
　　創(chuàng)建一個(gè)線程的過(guò)程，實(shí)際上就是從堆棧空間中申請(qǐng)一個(gè)放置線程控制塊的空間，在這個(gè)空間中建立線程控制塊并完成對(duì)控制塊的賦值的過(guò)程。為了更好地說(shuō)明線程控制塊的作用，下面用一個(gè)圖表來(lái)說(shuō)明，如圖1所示。