微型搶占式多任務(wù)實時內(nèi)核設(shè)計

1、微型搶占式多任務(wù)實時內(nèi)核設(shè)計摘要：介紹引入事件驅(qū)動觀念的搶占式多任務(wù)微型實時內(nèi)核MicroStar的設(shè)計與實現(xiàn)；提出基于事件的優(yōu)先級這一新概念。 事件驅(qū)動的觀點認為，任務(wù)應(yīng)該是被動地響應(yīng)外界發(fā)生的各種事件，而不是主動地去“查詢”，浪費處理器時間。采用事件驅(qū)動編程的方法，不僅提高了運行效率，而且降低了事件處理之間的耦合，使程序流程非常清晰，從而可大大提高開發(fā)效率。充分考慮中低端微控制器的硬件特點和嵌入式系統(tǒng)軟件的需求，引入“事件驅(qū)動”的觀念，筆者開發(fā)了一個微型的搶占式多任務(wù)RTOS內(nèi)核MicroStar。支持任務(wù)的動態(tài)創(chuàng)建、刪除、睡眠、掛起和恢復(fù)，提供消息（message）和信號（signal）

2、兩種任務(wù)間的通信方案、完善的定時器服務(wù)和功能齊全的任務(wù)同步函數(shù)庫。限于篇幅，著重論述幾個與眾不同的設(shè)計思路和實現(xiàn)難點。1 調(diào)度策略 1.1 基于事件的優(yōu)先級對內(nèi)核的實時性能來說，調(diào)度策略是關(guān)鍵。好的調(diào)度策略，既要體現(xiàn)各任務(wù)因所處理的事件對實時性的不同要求而帶來的優(yōu)先級差異，又要保證一定的公平性，避免出現(xiàn)低優(yōu)先級任務(wù)長時間得不到執(zhí)行的極端情形。常用的調(diào)度策略有兩種：一種是按時間片輪轉(zhuǎn)(round robin)調(diào)度，如RTX51；另一種是嚴格按優(yōu)先級的占先式調(diào)度，如C/OS。按時間片輪轉(zhuǎn)調(diào)度能很好地保證公平，但優(yōu)先級的差異是通過對處理器的占用時間的多少來體現(xiàn)的。如果各個任務(wù)都不主動放棄執(zhí)行，高優(yōu)先

3、級的任務(wù)能夠比低優(yōu)先級任務(wù)獲得更多的處理器時間；但在嵌入式系統(tǒng)中，某個事件要求實時處理，并不意味著該處理需要較長的時間，而往往是要求盡快響應(yīng)。因此，采用按時間片輪轉(zhuǎn)調(diào)度，實時性不會太好。如果嚴格按任務(wù)的優(yōu)先級來調(diào)度，可極大地提升系統(tǒng)的實時性，但卻欠缺公平。如果高優(yōu)先級任務(wù)是個無等待的死循環(huán)，低優(yōu)先級任務(wù)就無法獲得執(zhí)行機會。一個好的辦法是兩者的結(jié)合，即可由任務(wù)的優(yōu)先級產(chǎn)生調(diào)度，也可以由時間片到產(chǎn)生新的任務(wù)調(diào)度，如VxWorks；但是實現(xiàn)起來較為復(fù)雜，不一定適合中低檔MCU。為此，基于以下事實，提出“基于事件的優(yōu)先級(events based priority)”這一新觀念。 一個任務(wù)往往處理多個

4、事件，各個事件對實時性的要求不盡相同。一般的RTOS下，任務(wù)的優(yōu)先級是根據(jù)這些事件中對實時性要求最高的一個來確定的。因此，高優(yōu)先級任務(wù)在處理對實時性要求不高的事件時，完全可能會妨礙低優(yōu)先級任務(wù)處理具有一定實時性要求的事件。 有些情況下，對同一事件的處理可分為前臺處理和后臺處理：前臺處理所需時間短，對實時性有較高的要求；后臺處理花費時間長，對實時性則無多大要求。如果根據(jù)正在處理和等待處理的事件對實時性的不同要求，更細致地按事件處理的前后臺階段，動態(tài)地調(diào)整任務(wù)的優(yōu)先級，采用優(yōu)先級調(diào)度策略，既可發(fā)揮實時性好的優(yōu)點，又可在一定限度內(nèi)保證公平。這種情況下，任務(wù)的優(yōu)先級不再是一成不變的，而是動態(tài)地取決于所

5、處理的事件和處理階段，這就是所謂的“基于事件的優(yōu)先級”。 1.2 在MicroStar中的實現(xiàn)MicroStar中任務(wù)的優(yōu)先級是由靜態(tài)優(yōu)先級和動態(tài)優(yōu)先級共同決定的。靜態(tài)優(yōu)先級等同于其它RTOS中的優(yōu)先級；動態(tài)優(yōu)先級為基于事件的優(yōu)先級由內(nèi)核根據(jù)任務(wù)正在處理和等待處理的事件動態(tài)調(diào)整。靜態(tài)優(yōu)先等級限定為015級，不允許創(chuàng)建靜態(tài)優(yōu)先級相同的任務(wù)。動態(tài)優(yōu)先等級目前只有0(亦稱緊急級)、1(亦稱普通級)兩級。任務(wù)的實際優(yōu)先等級可由下式來計算：優(yōu)先等級動態(tài)優(yōu)先等級16 + 靜態(tài)優(yōu)先等級。優(yōu)先等級值越大，優(yōu)先級越低?？梢钥闯?，動態(tài)優(yōu)先級起決定作用。怎樣實現(xiàn)優(yōu)先級動態(tài)可調(diào)呢?首先簡要介紹MacroStar中任務(wù)

6、的四個狀態(tài)：休眠(dormant)任務(wù)因調(diào)用睡眠函數(shù)、掛起函數(shù)或者等待內(nèi)核同步對象而進入休眠態(tài)；等待(waiting)任務(wù)因等待消息或者信號(勿與“信標”、“信號量”相混淆)而進入等待態(tài)；就緒(ready)任務(wù)運行的條件都已俱備，只等被調(diào)度，稱為就緒態(tài)，亦稱可調(diào)度態(tài)；運行(running)任務(wù)正在使用處理器的資源，稱為運行態(tài)。這些狀態(tài)都是用標志位來實現(xiàn)的。16個靜態(tài)優(yōu)先級對應(yīng)的任務(wù)的某一狀態(tài)剛好可用一個16位的二進制數(shù)來標識。休眠態(tài)用os_slpState來表示，從高位算起，第N位為0表示靜態(tài)優(yōu)先級為N的任務(wù)處于休眠態(tài)。等待態(tài)是依據(jù)“事件驅(qū)動”觀念而專為消息和信號而設(shè)計的，用os_rdyhSt

7、ate和os_rdyState兩個16位的變量來記錄。只有當(dāng)os_rdyhState和os_rdyState的第N位均為0時，才表示靜態(tài)優(yōu)先級為N的任務(wù)處于等待態(tài)。如果任務(wù)處于非等待狀態(tài)，意味著任務(wù)已在處理事件或者有事件要處理(可以認為任務(wù)一開始就處理“啟動”這個“虛擬事件”)，這時，才有動態(tài)優(yōu)先級的概念。如果os_rdyhState中的第N位為1，表示靜態(tài)優(yōu)先級為N的任務(wù)的動態(tài)優(yōu)先級為緊急級；如果os_rdyhState第N位為0，則表示靜態(tài)優(yōu)先級為N的任務(wù)的動態(tài)優(yōu)先級為普通級。要求實時處理的事件發(fā)生后，內(nèi)核簡單將os_rdyhState相應(yīng)位置1，提升任務(wù)的動態(tài)優(yōu)先級；當(dāng)前事件處理完畢后，

8、如果已無實時性要求較高的事件等待處理，簡單地將os_rdyhState相應(yīng)位清0，降低任務(wù)的動態(tài)優(yōu)先級。由此，即可實現(xiàn)優(yōu)先級的動態(tài)可調(diào)。只有當(dāng)任務(wù)既不處在休眠態(tài)也不處在等待態(tài)時，任務(wù)才是可以調(diào)度的。 2.1 任務(wù)控制塊多任務(wù)系統(tǒng)中用任務(wù)控制塊（TCB）來記錄任務(wù)的各種屬性。在這些屬性中，最重要的是任務(wù)堆棧棧頂?shù)刂?。進行上下文切換（context switch）時，被停止執(zhí)行的任務(wù)的所有寄存器狀態(tài)、下一條代碼的地址都要入棧保護，因而這個屬性是必需的。如果允許修改任務(wù)的優(yōu)先級，優(yōu)先級屬性也是必需的。所以，將任務(wù)控制塊簡化如下：typedef structuint_16 msg2; /*消息接收區(qū)*

9、/int * sp; /*堆棧棧頂指針*/uchar priority; /*靜態(tài)優(yōu)先級*/uchar reserved; /*保留 */TCB,*PTCB;TCB os_tcbs USER_TASK_NUM +1 ;/*用戶任務(wù)數(shù)最多為15個*/msg用來存儲發(fā)送給任務(wù)的消息，兩個16位的二進制可按位存放32個消息。sp指向任務(wù)堆棧棧頂。priority記錄任務(wù)的靜態(tài)優(yōu)先級。數(shù)組os_tcbs用來記錄系統(tǒng)所有任務(wù)的信息，其下標與任務(wù)的ID號相對應(yīng)，即ID號為N的任務(wù)的控制塊為os_tcbsN。2.2 任務(wù)的創(chuàng)建os_CreateTask函數(shù)用來創(chuàng)建一個任務(wù)：void os_CreateTas

10、k(TASKPROC task, /任務(wù)函數(shù)的指針uchar taskId, /任務(wù)的ID號uchar priority, /優(yōu)先級int * pStack, /任務(wù)堆棧棧底地址void * param /任務(wù)函數(shù)的入口參數(shù));typedef void (*TASKPROC)( void * param);創(chuàng)建任務(wù)時，內(nèi)核要做以下幾方面的工作： 初始化任務(wù)控制塊； 初始化任務(wù)堆棧，使其如同被其它任務(wù)搶斷時的情形； 將任務(wù)狀態(tài)置為就緒態(tài)。該函數(shù)是依賴于處理器的，圖1是較為通用的描述。中斷程序中，在高優(yōu)先級任務(wù)剝奪低優(yōu)先級任務(wù)之前，內(nèi)核將斷點時的各寄存器狀態(tài)入棧保護，這部分區(qū)域即為寄存器映像區(qū)。將

11、任務(wù)退出函數(shù)os_Exit的地址先于任務(wù)函數(shù)MyTask入棧，以使MyTask函數(shù)退出后返回到os_Exit中去，由此來實現(xiàn)任務(wù)的自動刪除。 2.3 任務(wù)切換與任務(wù)創(chuàng)建一樣，任務(wù)切換代碼與硬件相關(guān)。在PC機上，代碼和步驟如下：void interrupt os_Schedule( )（1）if( os_nLayers )return;os_nLayers+; （2）_DX = (int)os_pCurTCB;/*os_pCurTCB指向當(dāng)前任務(wù)的控制塊*/*(int*)(_DX+4) = _SP;*(int*)(_DX+6) = _SS; （3）os_GetReadyTask( ); （4）_

12、DX = (int)os_pCurTCB;_SP = *(int*)(_DX+4);_DX = *(int*)(_DX+6);_SS = _DX; （5）os_nLayers-;? （6）UNLOCK_INT( ); （7） (1)利用C語言interrupt關(guān)鍵字使各寄存器入棧保護。（2）鎖定調(diào)度器，不允許重調(diào)度。（3）將當(dāng)前任務(wù)的棧頂?shù)刂罚ㄓ啥褩６渭拇嫫鱏S和棧指針寄存器SP組成）保存在os_pCurTCB-sp中（PC機下，TCB中的sp定義為遠指針類型）。（4）選出優(yōu)先級最高的就緒任務(wù)(方法類似于C/OS)，并將os_pCurTCB指向新任務(wù)的控制塊。（5）棧寄存器指向新任務(wù)的棧頂?shù)刂?/p>

13、。（6）解鎖調(diào)度器。（7）各寄存器出棧，恢復(fù)到上次被中斷時的情形。3 消息與信號為很好地支持事件驅(qū)動編程，MicroStar借鑒了Windows的“基于消息，事件驅(qū)動”觀念，并加以擴展。在MicroStar中，事件不僅可以觸發(fā)消息、信號，而且由事件觸發(fā)的消息或信號是有優(yōu)先級的，這是因為不同事件對處理的實時性要求是不同的。內(nèi)核正是根據(jù)消息、信號的優(yōu)先級來動態(tài)調(diào)整任務(wù)的動態(tài)優(yōu)先級的。 3.1 消 息消息是一種很友好的通信方式?？紤]中低檔單片機的內(nèi)存容量和需求，將消息簡化為一個031的值。采用固定位圖存儲格式，將這32個值映射到任務(wù)控制塊的msg域，這大大減小了存儲空間?？蓪sg域看作一個32位的

14、二進制變量，第i位為1，表示有值為i的消息，因此消息的存取只需通過簡單的“與”、“或”運算。消息的優(yōu)先級依值而定，值越大，優(yōu)先級越低。在系統(tǒng)范圍內(nèi)，消息優(yōu)先級又分為兩級：緊急級（值015）與普通級（值1631）。當(dāng)有緊急消息發(fā)送給任務(wù)時，內(nèi)核會提升任務(wù)的動態(tài)優(yōu)先級，從而提高消息處理的實時性。當(dāng)任務(wù)無緊急消息要處理時，內(nèi)核就降低它的動態(tài)優(yōu)先級。發(fā)送消息的核心代碼如下：/*const uint_16 os_maskTable16 = 0x8000,0x4000, .,0x0008,0x0004,0x0002,0x0001 */if( msg&0xF0 ) /*普通級消息*/pTCB-msg1 |=

15、 os_maskTablemsg&0x0F;/*普通級消息存在msg1中*/os_rdyState |= os_maskTablepTCB-priority;else /*緊急級消息*/pTCB-msg0 |= os_maskTablemsg; ;/*緊急級消息存在msg0中*/os_rdyhState |= os_maskTablepTCB-priority;/*提升動態(tài)優(yōu)先級*/與先進先出(FIFO)方式的消息隊列不同，內(nèi)核總是取出優(yōu)先級最高的消息來交給任務(wù)處理。消息接收函數(shù)os_GetMessage設(shè)計思路如下：如果消息接收區(qū)中無緊急消息，則降低任務(wù)的動態(tài)優(yōu)先級；如果消息接收區(qū)中有消息，

16、則取出優(yōu)先級最高的消息；如果沒有消息，則將任務(wù)轉(zhuǎn)為等待態(tài)?？紤]有時候不希望任務(wù)進入等待態(tài)，MicroStar還提供了非阻塞的os_PeekMessage消息接收函數(shù)。 3.2 信 號在嵌入式系統(tǒng)編程中，常利用標志位來實現(xiàn)前后臺程序或不同的任務(wù)間的通信。MicroStar也提供了類似的任務(wù)間的通信方式信號（signal）。它避免了用戶程序因不斷查詢標志位而帶來的時間浪費，而且支持信號間的“與”、“或”運算。通俗來說，信號就是標志位，用來標識某個事件的發(fā)生。同消息一樣，信號也有緊急級與普通級之分。與消息不同的是，信號完全由用戶程序創(chuàng)建和維護，內(nèi)核只是幫助用戶程序等待信號，以避免低效率的標志位查詢。

17、使用起來不如消息直觀，但執(zhí)行效率較高。實現(xiàn)起來非常簡單，請參見源碼。定時器在嵌入式系統(tǒng)有著大量的用途，如LED的定時刷新、串口通信中的超時檢查。對定時器的需求分為兩類，一種是周期性重復(fù)定時，比如每隔10ms去刷新LED；另一種是僅需定時一次的一次性定時。定時時長以系統(tǒng)時鐘節(jié)拍（tick,又譯作滴達）作為單位。兩次系統(tǒng)定時中斷之間的時間間隔為一個節(jié)拍。定時器結(jié)構(gòu)體如下：typedef structuint_16 elapse; /*定時時長的余值*/uint_16 backTime; /*定時時長的備份值*/MSG timerId; /*定時器ID號*/uchar taskId; /*擁有該定時

18、器的任務(wù)的ID*/TIMERPROC lpTimerFunc; /*定時調(diào)用的函數(shù)指針*/TIMER,*PTIMER;TIMERos_timersUSER_TIMER_NUM; /*最多為16個*/周期性定時和一次性定時是通過timerId來區(qū)分的。如果timeId為64，為一次性定時；如果timerId不大于32，則為周期性定時。用os_timers數(shù)組記錄定時器信息，用16位的os_timerState表示定時器的狀態(tài)。如果os_timerState的二進制數(shù)的第N位為1，則表示os_timersN空閑可用。對周期性定時器，每隔定時時長的時間，內(nèi)核就調(diào)用的lpTimerFunc指向的函數(shù)，

19、并且將timerId以消息的方式發(fā)送給任務(wù)，對任務(wù)的動態(tài)優(yōu)先級的影響與普通消息一樣。因此，要想取得實時性較好的定時器，只需將timerId設(shè)在015之間。與一次性定時相關(guān)的是睡眠函數(shù)和限時等待同步對象的函數(shù)。任務(wù)使用這兩個函數(shù)而進入休眠態(tài)后，在定時時間到時，內(nèi)核將其恢復(fù)為就緒態(tài)，并自動釋放定時器資源。系統(tǒng)定時處理的核心代碼如下：if( !(-pTimer-elapse) ) /*elapse減為零表示時間到*/if( pTimer-lpTimerFunc)(*pTimer-lpTimerFunc)(pTimer-taskId,pTimer-timerId);switch( pTimer-tim

20、erId&0xF0 )case SLEEP_ID: /*一次性定時*/os_slpState |= taskMask; /*結(jié)束休眠態(tài)*/os_timerState |= timerMask; /*釋放定時器*/break;case 0x00: /*發(fā)送緊急級定時器消息*/pTCB-msg0 |= os_maskTablepTimer-timerId;os_rdyhState |= os_maskTablepTCB-priority ;break;case 0x10: : /*發(fā)送普通級定時器消息*/pTCB-msg1 |= os_maskTablepTimer-timerId&0x0f;os

21、_rdyState |= os_maskTablepTCB-priority ;5 同 步搶占式多任務(wù)下，低優(yōu)先級的任務(wù)可以被高優(yōu)先級任務(wù)打斷執(zhí)行。以常規(guī)方式訪問共享變量或資源時，會出現(xiàn)奇怪的結(jié)果。比如，一個任務(wù)調(diào)用printf(“12345”)試圖在輸出設(shè)備上輸出“12345”，但執(zhí)行中被高優(yōu)先級任務(wù)打斷；而高優(yōu)先級任務(wù)也調(diào)用printf(“67890”)試圖輸出“67890”，最終的輸出結(jié)果可能是“1267890345”之類。這就是多任務(wù)環(huán)境下的任務(wù)同步問題。同步方式有兩種，一種為用戶同步方式，不需要與內(nèi)核打交道，具有速度快的優(yōu)點，但只適合保護執(zhí)行時間短的代碼；另一種是內(nèi)核同步方式，需要通

22、過內(nèi)核來實現(xiàn)，速度相對較慢，但可保護執(zhí)行時間長的代碼。 5.1 用戶同步方式用戶方式下的同步是通過關(guān)鍵代碼段（critical section）保護來實現(xiàn)。關(guān)鍵代碼段是指這樣一小段代碼，它執(zhí)行時必須獨占對某些共享資源的訪問權(quán)，不允行被其它試圖訪問該資源的代碼打斷。最簡單的是得用關(guān)/開中斷來實現(xiàn)，優(yōu)點是速度極快，缺點是帶來中斷延遲，只適合執(zhí)行時間極短的代碼段。另一簡單的方案是通過加鎖/解鎖調(diào)度器來實現(xiàn)，即在關(guān)鍵代碼段執(zhí)行期間禁止內(nèi)核進行任務(wù)切換。采用這種方法，不會帶來中斷延遲，但帶來了調(diào)度延遲。在MicroStar中，對os_nLayers加1即可鎖定調(diào)度器，減1即可解鎖。但直接利用解鎖調(diào)度器來

23、離開關(guān)鍵代碼段并不合適。如果在關(guān)鍵代碼段執(zhí)行中，發(fā)生了中斷，使更高優(yōu)先級任務(wù)就緒。但由于調(diào)度器被鎖定，中斷程序退出時不能進行任務(wù)切換以使高優(yōu)先級任務(wù)執(zhí)行。因此我們希望，最好一旦調(diào)度器解鎖，馬上就切換到高優(yōu)先級任務(wù)。為此，專門用變量os_flag的最低位作為標志位，中斷程序中調(diào)用任何可以使任務(wù)就緒的系統(tǒng)函數(shù)都會影響到該標志位，如os_PostMessage、os_SetEvent，os_Notity。退出關(guān)鍵代碼段時以此來判斷是否需要進行任務(wù)調(diào)度。離開臨界代碼段時的代碼如下：if( (os_flag&0x01) & (!(-s_nLayers ) ) ) -os_Schedule( ); 5.2

24、 內(nèi)核同步對象如果要保護執(zhí)行時間較長的代碼，就要使用內(nèi)核同步對象來同步。常用的內(nèi)核同步對象有事件(event)、信標(semaphore，亦稱信號量)和互斥量(mutex)。 事件對象用來通知事件或者操作已經(jīng)完成，它用一個布爾值來表示該事件處于通知還是未通知狀態(tài)。信標對象用于對資源進行計數(shù)。它記錄了當(dāng)前可用的資源數(shù)目。當(dāng)用1來初始化信標對象的可用資源數(shù)目時，信標對象實際上成為了互斥對象。MicroStar提供事件和信標兩種同步對象，支持查詢、限時等待或無限時等待操作。內(nèi)核同步對象的結(jié)構(gòu)如下：typedef structuint_16 waiter; /*等待列表*/uchar num; /*可用資源數(shù)目或者事件狀態(tài)*/uch