UC/OS-II內核調度分析 - 全文

　　一.內核概述：

　　多任務系統中，內核負責管理各個任務，或者說為每個任務分配CPU時間，并且負責任務之間的通訊。內核提供的基本服務是任務切換。之所以使用實時內核可以大大簡化應用系統的設計，是因為實時內核允許將應用分成若干個任務，由實時內核來管理它們。內核本身也增加了應用程序的額外負荷，代碼空間增加ROM的用量，內核本身的數據結構增加了RAM的用量。但更主要的是，每個任務要有自己的?？臻g，這一塊吃起內存來是相當厲害的。內核本身對CPU的占用時間一般在2到5個百分點之間。

　　UC/OS-II有一個精巧的內核調度算法,實時內核精小，執行效率高，算法巧妙,代碼空間很少。

　　二.UC/OS-II內核調度特點：

　　1.只支持基于優先級的搶占式調度算法，不支持時間片輪訓;

　　2.64個優先級,只能創建64個任務,用戶只能創建56個任務;

　　3.每個任務優先級都不相同。

　　4.不支持優先級逆轉;

　　5.READY隊列通過內存映射表實現快速查詢。效率非常高;

　　6.支持時鐘節拍;

　　7.支持信號量，消息隊列，事件控制塊，事件標志組，消息郵箱任務通訊機制;

　　8.支持中斷嵌套，中斷嵌套層數可達255層，中斷使用當前任務的堆棧保存上下文;

　　9.每個任務有自己的堆棧，堆棧大小用戶自己設定;

　　10.支持動態修改任務優先級;

　　11.任務TCB為靜態數組，建立任務只是從中獲得一個TCB，不用動態分配，釋放內存;

　　12.任務堆棧為用戶靜態或者動態創建，在任務創建外完成，任務創建本身不進行動態內存分配;

　　13.任務的總個數(OS_MAX_TASKS)由用戶決定;

　　14.0優先級最高，63優先級最低;

　　15.有一個優先級最低的空閑任務,在沒有用戶任務運行的時候運行.

　　三.任務控制塊OS_TCB描述：

　　UC/OS-II的TCB數據結構簡單，內容容易理解，保存最基本的任務信息，同時還支持裁減來減小內存消耗，TCB是事先根據用戶配置，靜態分配內存的結構數組，通過優先級序號進行添加，查找，刪除等功能。減少動態內存分配和釋放。因為依靠優先級進行TCB分配，每個任務必須有自己的優先級，不能和其他任務具有相同的優先級。

　　typedefstructos_tcb

　　{

　　OS_STK*OSTCBStkPtr;

　　#ifOS_TASK_CREATE_EXT_EN

　　void*OSTCBExtPtr;

　　OS_STK*OSTCBStkBottom;

　　INT32UOSTCBStkSize;

　　INT16UOSTCBOpt;

　　INT16UOSTCBId;

　　#endif

　　structos_tcb*OSTCBNext;

　　structos_tcb*OSTCBPrev;

　　#if(OS_Q_EN&&(OS_MAX_QS>=2))||OS_MBOX_EN||OS_SEM_EN

　　OS_EVENT*OSTCBEventPtr;

　　#endif

　　#if(OS_Q_EN&&(OS_MAX_QS>=2))||OS_MBOX_EN

　　void*OSTCBMsg;

　　#endif

　　INT16UOSTCBDly;

　　INT8UOSTCBStat;

　　INT8UOSTCBPrio;

　　INT8UOSTCBX;

　　INT8UOSTCBY;

　　INT8UOSTCBBitX;

　　INT8UOSTCBBitY;

　　#ifOS_TASK_DEL_EN

　　BOOLEANOSTCBDelReq;

　　#endif

　　}OS_TCB;

　　.OSTCBStkPtr是指向當前任務棧頂的指針。

　　.*OSTCBExtPtr;：任務擴展模塊使用;

　　.*OSTCBStkBottom;

　　.OSTCBStkSize;.

　　.OSTCBOpt;

　　.OSTCBId;

　　.OSTCBNext和.OSTCBPrev用于任務控制塊OS_TCBs的雙重鏈接，

　　.OSTCBEventPtr是指向事件控制塊的指針

　　.OSTCBMsg是指向傳給任務的消息的指針。

　　.OSTCBDly當需要把任務延時若干時鐘節拍時要用到這個變量，或者需要把任務掛起一段時間以等待某事件的發生，

　　.OSTCBStat是任務的狀態字。

　　.OSTCBPrio是任務優先級。

　　.OSTCBX,.OSTCBY,.OSTCBBitX和.OSTCBBitY用于加速任務進入就緒態的過程或進入等待事件發生狀態的過程

　　OSTCBY=priority>>3;

　　OSTCBBitY=OSMapTbl[priority>>3];

　　OSTCBX=priority&0x07;

　　OSTCBBitX=OSMapTbl[priority&0x07];

　　.OSTCBDelReq是一個布爾量，用于表示該任務是否需要刪除

　　四.就緒表(ReadyList)：

　　UC/OS-II采用內存映射的方式來實現READY隊列的加入，查找，刪除功能，效率非常高。但是也因此只能支持64個任務，每個任務都有自己的優先級，不能和其他任務優先級向同。

　　每個任務的就緒態標志都放入就緒表中的，就緒表中有兩個變量OSRdyGrp和OSRdyTbl[]。在OSRdyGrp中，任務按優先級分組，8個任務為一組。OSRdyGrp中的每一位表示8組任務中每一組中是否有進入就緒態的任務。任務進入就緒態時，就緒表OSRdyTbl[]中的相應元素的相應位也置位。就緒表OSRdyTbl[]數組的大小取決于OS_LOWEST_PRIO(見文件OS_CFG.H)。

　　為確定下次該哪個優先級的任務運行了，內核調度器總是將OS_LOWEST_PRIO在就緒表中相應字節的相應位置1。OSRdyGrp和OSRdyTbl[]的關系見圖3.3，是按以下規則給出的：

　　當OSRdyTbl[i]中的任何一位是1時，OSRdyGrp的第i位置1。i從0到7。

　　使任務進入就緒態

　　OSRdyGrp|=OSMapTbl[prio>>3];

　　OSRdyTbl[prio>>3]|=OSMapTbl[prio&0x07];

　　任務優先級的低三位用于確定任務在總就緒表OSRdyTbl[]中的所在位。接下去的三位用于確定是在OSRdyTbl[]數組的第幾個元素。OSMapTbl[]是在ROM中的(見文件OS_CORE.C)屏蔽字，用于限制OSRdyTbl[]數組的元素下標在0到7之間，如果一個任務被刪除了，則用程序清單3.6中的代碼做求反處理。

　　程序清單L3.6從就緒表中刪除一個任務

　　if((OSRdyTbl[prio>>3]&=~OSMapTbl[prio&0x07])==0)

　　OSRdyGrp&=~OSMapTbl[prio>>3];

　　以上代碼將就緒任務表數組OSRdyTbl[]中相應元素的相應位清零，而對于OSRdyGrp，只有當被刪除任務所在任務組中全組任務一個都沒有進入就緒態時，才將相應位清零。也就是說OSRdyTbl[prio>>3]所有的位都是零時，OSRdyGrp的相應位才清零。為了找到那個進入就緒態的優先級最高的任務，并不需要從OSRdyTbl[0]開始掃描整個就緒任務表，只需要查另外一張表，即優先級判定表OSUnMapTbl([256])(見文件OS_CORE.C)。OSRdyTbl[]中每個字節的8位代表這一組的8個任務哪些進入就緒態了，低位的優先級高于高位。利用這個字節為下標來查OSUnMapTbl這張表，返回的字節就是該組任務中就緒態任務中優先級最高的那個任務所在的位置。這個返回值在0到7之間。確定進入就緒態的優先級最高的任務是用以下代碼完成的。

　　找出進入就緒態的優先級最高的任務

　　y=OSUnMapTbl[OSRdyGrp];

　　x=OSUnMapTbl[OSRdyTbl[y]];

　　prio=(y<<3)+x;

　　例如，如果OSRdyGrp的值為二進制01101000，查OSUnMapTbl[OSRdyGrp]得到的值是3，它相應于OSRdyGrp中的第3位bit3，這里假設最右邊的一位是第0位bit0。類似地，如果OSRdyTbl[3]的值是二進制11100100,則OSUnMapTbl[OSRdyTbc[3]]的值是2，即第2位。于是任務的優先級Prio就等于26(3*8+2)。利用這個優先級的值。查任務控制塊優先級表OSTCBPrioTbl[]，得到指向相應任務的任務控制塊OS_TCB的工作就完成了。

　　五.任務狀態：

　　UC/OS-II主要有五種任務狀態，睡眠態就是掛起態，阻塞態和延時態這里統一為等待狀態。增加了一個被中斷狀態。UC/OS-Ⅱ總是建立一個空閑任務，這個任務在沒有其它任務進入就緒態時投入運行。這個空閑任務[OSTaskIdle()]永遠設為最低優先級空閑任務OSTaskIdle()什么也不做，只是在不停地給一個32位的名叫OSIdleCtr的計數器加1，統計任務使用這個計數器以確定現行應用軟件實際消耗的CPU時間?？臻e任務不可能被應用軟件刪除。

　　睡眠態(DORMANT)指任務駐留在程序空間之中，還沒有交給μC/OS-Ⅱ管理，把任務交給μC/OS-Ⅱ是通過調用下述兩個函數之一：OSTaskCreate()或OSTaskCreateExt()。當任務一旦建立，這個任務就進入就緒態準備運行。任務的建立可以是在多任務運行開始之前，也可以是動態地被一個運行著的任務建立。如果一個任務是被另一個任務建立的，而這個任務的優先級高于建立它的那個任務，則這個剛剛建立的任務將立即得到CPU的控制權。一個任務可以通過調用OSTaskDel()返回到睡眠態，或通過調用該函數讓另一個任務進入睡眠態。

　　調用OSStart()可以啟動多任務。OSStart()函數運行進入就緒態的優先級最高的任務。就緒的任務只有當所有優先級高于這個任務的任務轉為等待狀態，或者是被刪除了，才能進入運行態。

　　正在運行的任務可以通過調用兩個函數之一將自身延遲一段時間，這兩個函數是OSTimeDly()或OSTimeDlyHMSM()。這個任務于是進入等待狀態，等待這段時間過去，下一個優先級最高的、并進入了就緒態的任務立刻被賦予了CPU的控制權。等待的時間過去以后，系統服務函數OSTimeTick()使延遲了的任務進入就緒態(見3.10節，時鐘節拍)。

　　正在運行的任務期待某一事件的發生時也要等待，手段是調用以下3個函數之一：OSSemPend()，OSMboxPend()，或OSQPend()。調用后任務進入了等待狀態(WAI TING)。當任務因等待事件被掛起(Pend)，下一個優先級最高的任務立即得到了CPU的控制權。當事件發生了，被掛起的任務進入就緒態。事件發生的報告可能來自另一個任務，也可能來自中斷服務子程序。

　　正在運行的任務是可以被中斷的，除非該任務將中斷關了，或者μC/OS-Ⅱ將中斷關了。被中斷了的任務就進入了中斷服務態(ISR)。響應中斷時，正在執行的任務被掛起，中斷服務子程序控制了CPU的使用權。中斷服務子程序可能會報告一個或多個事件的發生，而使一個或多個任務進入就緒態。在這種情況下，從中斷服務子程序返回之前，μC/OS-Ⅱ要判定，被中斷的任務是否還是就緒態任務中優先級最高的。如果中斷服務子程序使一個優先級更高的任務進入了就緒態，則新進入就緒態的這個優先級更高的任務將得以運行，否則原來被中斷了的任務才能繼續運行。

　　當所有的任務都在等待事件發生或等待延遲時間結束，μC/OS-Ⅱ執行空閑任務(idletask)，執行OSTaskIdle()函數。

　　六.任務切換：

　　ContextSwitch在有的書中翻譯成上下文切換，實際含義是任務切換，或CPU寄存器內容切換。當多任務內核決定運行另外的任務時，它保存正在運行任務的當前狀態(Context)，即CPU寄存器中的全部內容。這些內容保存在任務的當前狀況保存區(Task’sContextStoragearea)，也就是任務自己的棧區之中。(見圖2.2)。入棧工作完成以后，就是把下一個將要運行的任務的當前狀況從該任務的棧中重新裝入CPU的寄存器，并開始下一個任務的運行。這個過程叫做任務切換。任務切換過程增加了應用程序的額外負荷。CPU的內部寄存器越多，額外負荷就越重。做任務切換所需要的時間取決于CPU有多少寄存器要入棧。實時內核的性能不應該以每秒鐘能做多少次任務切換來評價。

　　七.任務調度分析：

　　μC/OS-Ⅱ提供最簡單的實時內核任務調度，算法簡單，因此也只支持優先級搶占任務調度，不支持時間片輪訓調度算法,不支持優先級逆轉。

　　μC/OS-Ⅱ總是運行進入就緒態任務中優先級最高的那一個。確定哪個任務優先級最高，下面該哪個任務運行了的工作是由調度器(Scheduler)完成的。任務級的調度是由函數OSSched()完成的。中斷級的調度是由另一個函數OSIntExt()完成的，這個函數將在以后描述。

　　μC/OS-Ⅱ任務調度所花的時間是常數，與應用程序中建立的任務數無關。

　　在μC/OS中曾經是先得到OSTCBHighRdy然后和OSTCBCur做比較。因為這個比較是兩個指針型變量的比較，在8位和一些16位微處理器中這種比較相對較慢。而在μC/OS-Ⅱ中是兩個整數的比較。并且，除非用戶實際需要做任務切換，在查任務控制塊優先級表OSTCBPrioTbl[]時，不需要用指針變量來查OSTCBHighRdy。綜合這兩項改進，即用整數比較代替指針的比較和當需要任務切換時再查表，使得μC/OS-Ⅱ比μC/OS在8位和一些16位微處理器上要更快一些。

　　為實現任務切換，OSTCBHighRdy必須指向優先級最高的那個任務控制塊OS_TCB，這是通過將以OSPrioHighRdy為下標的OSTCBPrioTbl[]數組中的那個元素賦給OSTCBHighRdy來實現的[L3.8(4)]。最后宏調用OS_TASK_SW()來完成實際上的任務切換[L3.8(6)]。

　　任務切換很簡單，由以下兩步完成，將被掛起任務的微處理器寄存器推入堆棧，然后將較高優先級的任務的寄存器值從棧中恢復到寄存器中。在μC/OS-Ⅱ中，就緒任務的棧結構總是看起來跟剛剛發生過中斷一樣，所有微處理器的寄存器都保存在棧中。換句話說，μC/OS-Ⅱ運行就緒態的任務所要做的一切，只是恢復所有的CPU寄存器并運行中斷返回指令。為了做任務切換，運行OS_TASK_SW(),人為模仿了一次中斷。多數微處理器有軟中斷指令或者陷阱指令TRAP來實現上述操作。中斷服務子程序或陷阱處理(Traphardler)，也稱作事故處理(exceptionhandler)，必須提供中斷向量給匯編語言函數OSCtxSw()。OSCtxSw()除了需要OS_TCBHighRdy指向即將被掛起的任務，還需要讓當前任務控制塊OSTCBCur指向即將被掛起的任務。

　　OSSched()的所有代碼都屬臨界段代碼。在尋找進入就緒態的優先級最高的任務過程中，為防止中斷服務子程序把一個或幾個任務的就緒位置位，中斷是被關掉的。為縮短切換時間，OSSched()全部代碼都可以用匯編語言寫。為增加可讀性，可移植性和將匯編語言代碼最少化，OSSched()是用C寫的。

　　任務切換的相關函數:與CPU體系相關，匯編完成。

　　1.OSStartHighRdy()執行優先級最高的任務

　　2.OSCtxSw()完成任務的上下文切換

　　3.OSIntCtxSw()中斷后的上下文切換

　　4.OSTickISR()中斷服務程序啟動

　　八.UC/OS-II的初始化：

　　OSInit()建立空閑任務idletask，這個任務總是處于就緒態的。空閑任務OSTaskIdle()的優先級總是設成最低。

　　這兩個任務的任務控制塊(OS_TCBs)是用雙向鏈表鏈接在一起的。OSTCBList指向這個鏈表的起始處。當建立一個任務時，這個任務總是被放在這個鏈表的起始處。換句話說，OSTCBList總是指向最后建立的那個任務。鏈的終點指向空字符NULL(也就是零)。

　　因為這兩個任務都處在就緒態，在就緒任務表OSRdyTbl[]中的相應位是設為1的。還有，因為這兩個任務的相應位是在OSRdyTbl[]的同一行上，即屬同一組，故OSRdyGrp中只有1位是設為1的。

　　μC/OS-Ⅱ還初始化了4個空數據結構緩沖區，如圖F3.8所示。每個緩沖區都是單向鏈表，允許μC/OS-Ⅱ從緩沖區中迅速得到或釋放一個緩沖區中的元素。控制塊OS_TCB的數目也就自動確定了。當然，包括足夠的任務控制塊分配給統計任務和空閑任務。

　　UC/OS-II內核調度分析vxWorks內核調度分析