新聞中心

EEPW首頁(yè) > 嵌入式系統(tǒng) > 設(shè)計(jì)應(yīng)用 > Nut/OS和μC/OS―II的實(shí)時(shí)調(diào)度算法比較

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

作者: 時(shí)間:2007-04-19 來(lái)源:網(wǎng)絡(luò) 收藏
摘要 進(jìn)程是計(jì)算機(jī)的靈魂。在系統(tǒng)里,要使重要緊急的進(jìn)程一經(jīng)喚醒使被優(yōu)先運(yùn)行,系統(tǒng)就必須有基于進(jìn)程優(yōu)先級(jí)的策略。通過(guò)深入考察和對(duì)比μC/OS-和Nut/OS對(duì)調(diào)度的實(shí)現(xiàn),可以深刻理解實(shí)時(shí)操作系統(tǒng)。
關(guān)鍵詞 μC/0S- 實(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)完成:
①何時(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;
②系統(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í)隙,稱為不可調(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 μ-Il的實(shí)現(xiàn)
在μC/OS-里。只允許有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ù)組中查得的值稱為組號(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)進(jìn)行分析。它有256個(gè)優(yōu)先級(jí)且允許不同進(jìn)程具有相同的優(yōu)先級(jí)。在這樣的系統(tǒng)里,是不可能采用類(lèi)似于位圖這樣的機(jī)制來(lái)實(shí)現(xiàn)調(diào)度的。

2 Nut/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所示。

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

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

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

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


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

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

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

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



評(píng)論


相關(guān)推薦

技術(shù)專區(qū)

關(guān)閉