UCOS時間片輪轉(zhuǎn)調(diào)度算法詳解

1、UCOS 時間片輪轉(zhuǎn)調(diào)度算法詳解2009年8月4日 1. UCOS 一種只支持優(yōu)先級搶占型調(diào)度的操作系統(tǒng)。它不支持同一個優(yōu)先級有 2 個及以上的任務(wù)同時運作。 我修改的 UCOS 支持不同優(yōu)先級調(diào)度的同時，支持同一個優(yōu)先級有 2 個以上的任務(wù)以時間片輪轉(zhuǎn)方式進(jìn)行調(diào)度。 這個就是 UCOS 和我修改的 UCOS 的區(qū)別。 我修改后的 UCOS，在以后的文段中就稱為“FIFO-UCOS”。 FIFO 就是先進(jìn)先出的意思，和時間片輪轉(zhuǎn)調(diào)度差不多的意思。 一. FIFOUCOS核心思想   UCOS 在調(diào)度的時候，會按照優(yōu)先級選擇進(jìn)程進(jìn)行調(diào)度，我做的部分就僅僅是在他進(jìn)行優(yōu)先級檢查之

2、前，把和運行態(tài)同等級的進(jìn)程進(jìn)行了替換，替換成了時間片輪轉(zhuǎn)調(diào)度的下一個進(jìn)程！    二.TCB 的修改   FIFO-UCOS 和 UCOS 并不能完全兼容，最大的改變，就是對 TCB 的結(jié)構(gòu)做了改動，加入了我自己的段。 該部分代碼在 UCOS-II.H 文件中： typedef struct os_tcb OS_STK *OSTCBStkPtr; /* 當(dāng)前任務(wù)堆棧棧頂指針 */ #if OS_TASK_CREATE_EXT_EN > 0 void *OSTCBExtPtr; /* 指向用戶定義的任務(wù)控制塊擴(kuò)展*/ OS_STK *OSTCBStk

3、Bottom; /* 指向任務(wù)堆棧棧底指針 */ INT32U OSTCBStkSize; /*存有棧中可容納的指針元數(shù)目而不是用字節(jié)（Byte）表示的棧容量總數(shù)。*/ INT16U OSTCBOpt; /* Task options as passed by OSTaskCreateExt() */  INT16U OSTCBId; /* Task ID (0.65535) 存儲任務(wù)的識別碼ID，備用 */  #endif struct os_tcb *OSTCBNext; /*指向后一個任務(wù)控制塊的指針*/ struct os_tcb *OSTCBPrev; /*指向前

4、一個任務(wù)控制塊的指針*/ #if (OS_Q_EN > 0) && (OS_MAX_QS > 0) | (OS_MBOX_EN > 0) | (OS_SEM_EN > 0) | (OS_MUTEX_EN > 0) /* OS_EVENT_EN 定義為：能使隊列代碼產(chǎn)生&&申請隊列控制塊最大數(shù)不為零|能使郵箱代碼產(chǎn)生|    能使信號量代碼產(chǎn)生|能使互斥量代碼產(chǎn)生  */ OS_EVENT *OSTCBEventPtr; /*指向事件控制塊的指針*/ #endif #if (OS_Q_

5、EN > 0) && (OS_MAX_QS > 0) | (OS_MBOX_EN > 0) void *OSTCBMsg; /* Message received from OSMboxPost() or OSQPost() 指向傳遞給任務(wù)的消息的指針*/ #endif #if (OS_VERSION >= 251) && (OS_FLAG_EN > 0) && (OS_MAX_FLAGS > 0) #if OS_TASK_DEL_EN > 0 /* OS版本大于等于251&&能使事件標(biāo)志

6、代碼產(chǎn)生&&最大標(biāo)志數(shù)大于零*/ OS_FLAG_NODE *OSTCBFlagNode; /*指針指向事件標(biāo)志節(jié)點*/ #endif   OS_FLAGS OSTCBFlagsRdy; /* Event flags that made task ready to run事件標(biāo)志使任務(wù)準(zhǔn)備運行*/ #endif INT16U OSTCBDly; /* 任務(wù)等待的時限*/ INT8U OSTCBStat; /* 任務(wù)的當(dāng)前狀態(tài)標(biāo)志 */ INT8U OSTCBPrio; /* 任務(wù)優(yōu)先級 (0 = highest, 63 = lowest) */ /*以下四行

7、語句用于快速訪問就緒表的數(shù)據(jù)*/   INT8U OSTCBX; /* Bit position in group corresponding to task priority (0.7) */ INT8U OSTCBY; /* Index into ready table corresponding to task priority */ INT8U OSTCBBitX; /* Bit mask to access bit position in ready table */ INT8U OSTCBBitY; /* Bit mask to access bit posit

8、ion in ready group */ #if OS_TASK_DEL_EN > 0 BOOLEAN OSTCBDelReq; /* Indicates whether a task needs to delete itself */ #endif /* 以下代碼是我自己加的：*/#ifdef OS_TIME_SCHEDULE struct os_tcb *OSTSnext; struct os_tcb *OSTSprev;   INT8U OSTSLen; /*記錄了該進(jìn)程占用多少個時間片*/ INT8U OSTSCurLen; /*記錄的是該進(jìn)程現(xiàn)在還剩下多少

9、個時間片時間可以用*/#endif /*/ OS_TCB; 三.進(jìn)程創(chuàng)建   進(jìn)程創(chuàng)建的主要目的是跳過原代碼中的優(yōu)先級占用檢查，并在這里加入 FIFO 進(jìn)程創(chuàng)建。 文件在OS_TASK.C中： INT8U OSTaskCreate (void (*task)(void *pd), void *pdata, OS_STK *ptos,   INT8U prio,INT16U id, INT8U TSlen) #if OS_CRITICAL_METHOD = 3 /*  為CPU狀態(tài)寄存器分配存儲空間*/ OS_CPU_SR cpu_sr; /CP

10、U狀態(tài)字是十六位 cpu_sr為OS_CPU_SR型變量#endif OS_STK *psp; /創(chuàng)建一個指向數(shù)據(jù)類型為OS_STK的指針和一個8位的整型數(shù) INT8U err; #if OS_ARG_CHK_EN > 0 if (prio > OS_LOWEST_PRIO) /*保證優(yōu)先級在允許范圍內(nèi)  */ return (OS_PRIO_INVALID); #endif OS_ENTER_CRITICAL(); /* OS_ENTER_CRITICAL（）和OS_EXIT_CRITICAL（）為定義的宏，用來關(guān)閉、打開CPU 的中斷。*/ if (OSTC

11、BPrioTblprio = (OS_TCB *)0) /*保證優(yōu)先級沒有被其它任務(wù)占用  */    /* * if you want run the FIFO mask this code OSTCBPrioTblprio = (OS_TCB *)1; /* Reserve the priority to prevent others from doing . */ /* . the same thing until task is created. */那就是說有一個任務(wù)存在了，不再是 Nul /*/ OS_EXIT_CRITICAL(); psp

12、 = (OS_STK *)OSTaskStkInit(task, pdata, ptos, 0); /* 初始化任務(wù)堆棧,即建立任務(wù)堆棧*/ err = OS_TCBInit(prio, psp, (OS_STK *)0, id, 0, (void *)0, 0, TSlen); /*初始化任務(wù)控制塊，從空閑的OS_TCB緩沖池中獲得并初始化一個任務(wù)控制塊*/if (err = OS_NO_ERR)  /如果初始化沒有錯 OS_ENTER_CRITICAL();/進(jìn)入臨界狀態(tài) OSTaskCtr+; /*任務(wù)數(shù)量加一*/ OS_EXIT_CRITICAL(); if (OSRunni

13、ng = TRUE) /* 如果多任務(wù)開始，尋找最高優(yōu)先級任務(wù)  */ OS_Sched(); else /如果初始化任務(wù)控制塊有錯 OS_ENTER_CRITICAL(); OSTCBPrioTblprio = (OS_TCB *)0;/* Make this priority available to   others 把這一優(yōu)先級給其它任務(wù)*/ OS_EXIT_CRITICAL(); return (err); /返回錯誤信息/*   */ else /這是FIFO的任務(wù)創(chuàng)建代碼 OS_EXIT_CRITICAL(); psp = (OS

14、_STK *)OSTaskStkInit(task, pdata, ptos, 0); /* Initialize the task's stack初始化任務(wù)堆棧,即建立任務(wù)堆棧*/ err = OS_TCBInit(prio, psp, (OS_STK *)0, id, 0, (void *)0, 0, TSlen); if (err = OS_NO_ERR) OS_ENTER_CRITICAL(); OSTaskCtr+; /*任務(wù)數(shù)量加一*/ OS_EXIT_CRITICAL(); if (OSRunning = TRUE) /* Find highest priori

15、ty task if multitasking has started */ OS_Sched(); return(err); /*/ OS_EXIT_CRITICAL(); return (OS_PRIO_EXIST); 其中加入的傳遞參數(shù)有兩個，一個是 id，一個是 TSLen 因為會出現(xiàn)同優(yōu)先級的任務(wù)，那么采用優(yōu)先級做為任務(wù) ID 的方式是不可取的了，我們必須加入任務(wù) id 段 TSLen 段，是該進(jìn)程的時間片為多長。 四.進(jìn)程初始化   進(jìn)程初始化基本保留以前的東西不動，要的就僅僅是把 TSLen 加入 TCB，把上面說到的那個鏈表鏈接起來。 代碼在文件O

16、S_CORE.C 中初始化任務(wù)控制塊1. 參數(shù)：prio：任務(wù)創(chuàng)建時的優(yōu)先級  2.      ptos:假定CPU寄存器放置于堆棧中指向堆棧棧頂?shù)闹羔槨ｍ敭?dāng)OS_STK_GROWTH為1時是寄存器的 高位、當(dāng)OS_STK_GROWTH為0時是寄存器的低位，堆棧增長是CPU的特權(quán)。  3.       pbos：棧底指針。由OSTaskCreate()調(diào)用時傳入空指針。  4.   &

17、#160;   id： 任務(wù)的ID  5.       stk_size:堆棧大小。 當(dāng)堆棧單位是int8us時，堆棧大小包含堆棧數(shù)量個字節(jié)，當(dāng)堆棧單位是int32us時，堆棧大小包含“4*stk_size”個字節(jié)。堆棧單位由“#define constant OS_STK”建立，它是CPU特有。如果被OSTaskCreate()調(diào)用stk_size為0。  6.      &

18、#160;pext：用戶提供存儲器空間的指針，用于任務(wù)控制塊。允許存儲浮點寄存器常量，MMU寄存器或者其它在內(nèi)容轉(zhuǎn)換時有用的東西。甚至在TCB擴(kuò)展中為每個任務(wù)指定一個名字存到這個名 字里面。 OSTaskCreate()調(diào)用的時候為空指針。  7 opt ：傳到OSTaskCreateExt()時可以選擇，被OSTaskCreate()調(diào)用的時候為0。  INT8U OS_TCBInit (INT8U prio, OS_STK *ptos, OS_STK *pbos, INT16U id, INT32U stk_size, void

19、*pext, INT16U opt, INT8U TSlen) #if OS_CRITICAL_METHOD = 3 /*為CPU狀態(tài)寄存器分配存儲空間  */ OS_CPU_SR cpu_sr; #endif   OS_TCB *ptcb; OS_ENTER_CRITICAL(); ptcb = OSTCBFreeList; /*從空TCB列表中得到一塊空TCB */ if (ptcb != (OS_TCB *)0) /分配空TCB成功 OSTCBFreeList = ptcb->OSTCBNext; /*更新空閑TCB鏈表頭指針 */ OS_EXIT_C

20、RITICAL(); ptcb->OSTCBStkPtr = ptos; /*保存棧頂指針到TCB  */ ptcb->OSTCBPrio = (INT8U)prio; /*保存任務(wù)優(yōu)先級到TCB */ ptcb->OSTCBStat = OS_STAT_RDY; /*任務(wù)狀態(tài)設(shè)為就緒*/ ptcb->OSTCBDly = 0; /*任務(wù)不延時*/ #if OS_TASK_CREATE_EXT_EN > 0 ptcb->OSTCBExtPtr = pext; /*存儲TCB擴(kuò)展指針*/ ptcb->OSTCBStkSize = stk_siz

21、e; /*存儲堆棧大小  */ ptcb->OSTCBStkBottom = pbos; /*存儲棧底指針*/ ptcb->OSTCBOpt = opt; /*存儲任務(wù)選項  */ #else /以下四條語句用于防止編譯器警告，不要刪除  pext = pext; /* Prevent compiler warning if not used */ stk_size = stk_size; pbos = pbos; opt = opt; #endif ptcb->OSTCBId = id; /* 存儲任務(wù)ID */ #if OS_TASK_DEL

22、_EN > 0 /允許包含任務(wù)刪除代碼 ptcb->OSTCBDelReq = OS_NO_ERR; /是否允許自動刪除 #endif ptcb->OSTCBY = prio >> 3; /*提前計算X,Y,位X，位Y*/ ptcb->OSTCBBitY = OSMapTblptcb->OSTCBY; ptcb->OSTCBX = prio & 0x07; /* 存儲就緒優(yōu)先級組中的 8 個優(yōu)先級情況 */ ptcb->OSTCBBitX = OSMapTblptcb->OSTCBX; /*為什么要這樣算？不知道&#

23、160;*/ #if OS_EVENT_EN > 0 ptcb->OSTCBEventPtr = (OS_EVENT *)0; /* 任務(wù)不等待任何事件發(fā)生 */ #endif #if (OS_VERSION >= 251) && (OS_FLAG_EN > 0) && (OS_MAX_FLAGS > 0) && (OS_TASK_DEL_EN > 0) /*OS版本大于等于251&&能使事件標(biāo)志代碼產(chǎn)生&&最大標(biāo)志數(shù)大于零&& 允許包含任務(wù)刪

24、除函數(shù)*/ ptcb->OSTCBFlagNode = (OS_FLAG_NODE *)0; /*  任務(wù)不等待事件標(biāo)志*/ #endif #if (OS_MBOX_EN > 0) | (OS_Q_EN > 0) && (OS_MAX_QS > 0) /允許郵箱代碼產(chǎn)生|允許隊列代碼產(chǎn)生&&最大隊列控制塊大于零  ptcb->OSTCBMsg = (void *)0; /*沒有接收到任務(wù)消息*/ #endif ptcb->OSTSLen=TSlen; ptcb->OSTSCurLen=TSlen; #

25、if OS_VERSION >= 204 /ucos版本大于等于204 OSTCBInitHook(ptcb); #endif OSTaskCreateHook(ptcb); /* Call user defined hook */    OS_ENTER_CRITICAL(); if(OSTCBPrioTblprio = 0) OSTCBPrioTblprio = ptcb; /*任務(wù)控制塊存入到已創(chuàng)建任務(wù)控制塊列表當(dāng)中*/  ptcb->OSTSnext = ptcb; ptcb->OSTSprev = ptcb; else ptcb->

26、;OSTSnext = OSTCBPrioTblprio->OSTSnext; OSTCBPrioTblprio->OSTSnext = ptcb; ptcb->OSTSprev = OSTCBPrioTblprio; (ptcb->OSTSnext )->OSTSprev=ptcb; ptcb->OSTCBNext = OSTCBList; /* Link into TCB chain */ ptcb->OSTCBPrev = (OS_TCB *)0; if (OSTCBList != (OS_TCB *)0) OSTCBList->OSTCB

27、Prev = ptcb; OSTCBList = ptcb; OSRdyGrp |= ptcb->OSTCBBitY; /* Make task ready to run */ OSRdyTblptcb->OSTCBY |= ptcb->OSTCBBitX; OS_EXIT_CRITICAL(); return (OS_NO_ERR); OS_EXIT_CRITICAL(); return (OS_NO_MORE_TCB); if(OSTCBPrioTblprio = 0) OSTCBPrioTblprio = ptcb; ptcb->OSTSnext = ptcb;

28、ptcb->OSTSprev = ptcb; else ptcb->OSTSnext = OSTCBPrioTblprio->OSTSnext; OSTCBPrioTblprio->OSTSnext = ptcb; ptcb->OSTSprev = OSTCBPrioTblprio; (ptcb->OSTSnext )->OSTSprev=ptcb; 這一段解釋一下 鏈表必須進(jìn)行鏈接，在優(yōu)先級沒有被占用的時候，這個鏈表的前后都鏈向自己，這樣在調(diào)度的時候，F(xiàn)IFO 調(diào)度就算指向下個任務(wù)，也指向的是自己，不影響優(yōu)先級調(diào)度。 當(dāng)在這個優(yōu)先級已經(jīng)有進(jìn)程的時候，

29、那么我們需要的就是把這個進(jìn)程加入到這個優(yōu)先級的鏈表中，鏈表操作相信大家都能看懂，不多做解釋。 五.進(jìn)程調(diào)度   進(jìn)程調(diào)度基本還是依靠 UCOS 自己的調(diào)度算法，修改的，就僅僅是在調(diào)度之間，把運行態(tài)優(yōu)先級的任務(wù)進(jìn)行運算，時間片使用完，就指向下一個進(jìn)程。  OS_CORE.C  void OSTimeTick (void) #if OS_CRITICAL_METHOD = 3 /* Allocate storage for CPU status register */ OS_CPU_SR cpu_sr; #endif   OS_TCB *

30、ptcb; OSTimeTickHook(); /* Call user definable hook */ #if OS_TIME_GET_SET_EN > 0   OS_ENTER_CRITICAL(); /* Update the 32-bit tick counter */ OSTime+; /*系統(tǒng)節(jié)拍現(xiàn)階段值，計算自系統(tǒng)上電以來的時鐘節(jié)拍數(shù)*/ OS_EXIT_CRITICAL(); #endif   if(OSTCBCur->OSTSCurLen)>0)/如果時間片沒有用完 if(-OSTCBCur->OSTSCur

31、Len=0)/時間片在這次調(diào)度中用完了 if(OSTCBCur->OSTSnext != OSTCBCur)/*如果優(yōu)先級里面至少有兩個進(jìn)程（看上一篇文章來理解這個地方）*/ OSTCBCur->OSTSCurLen = OSTCBCur->OSTSLen;/*把現(xiàn)在時間片用完的進(jìn)程的時間補(bǔ)回來，以便下次調(diào)度*/ OSTCBPrioTblOSTCBCur->OSTCBPrio = OSTCBCur->OSTSnext;/*把該優(yōu)先級的任務(wù)替換成下一個任務(wù)*/ OSPrioCur=0;/把當(dāng)前的運行優(yōu)先級改成 0，不然調(diào)度認(rèn)為該優(yōu)先級的任務(wù)沒有結(jié)束，不執(zhí)行任務(wù)調(diào)度，結(jié)果回到的地方，還是上一個時間片的任務(wù)，就死翹翹了！ ptcb = OSTCBList; /* Point at first TCB in TCB list */ while (ptcb->OSTCBPrio !