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

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

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

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

4、X_EN 0) | (OS_SEM_EN 0) | (OS_MUTEX_EN 0) /* OS_EVENT_EN定義為：能使隊(duì)列代碼產(chǎn)生&申請(qǐng)隊(duì)列控制塊最大數(shù)不為零|能使郵箱代碼產(chǎn)生| 能使信號(hào)量代碼產(chǎn)生|能使互斥量代碼產(chǎn)生 */ OS_EVENT *OSTCBEventPtr; /*指向事件控制塊的指針*/ #endif #if (OS_Q_EN 0) & (OS_MAX_QS 0) | (OS_MBOX_EN 0) void *OSTCBMsg; /* Message received from OSMboxPost() or OSQPost() 指向傳遞給任務(wù)的消息的指針*/ #endi

5、f #if (OS_VERSION = 251) & (OS_FLAG_EN 0) & (OS_MAX_FLAGS 0) #if OS_TASK_DEL_EN 0 /* OS版本大于等于251&能使事件標(biāo)志代碼產(chǎn)生&最大標(biāo)志數(shù)大于零*/ OS_FLAG_NODE *OSTCBFlagNode; /*指針指向事件標(biāo)志節(jié)點(diǎn)*/ #endif OS_FLAGS OSTCBFlagsRdy; /* Event flags that made task ready to run事件標(biāo)志使任務(wù)準(zhǔn)備運(yùn)行*/ #endif INT16U OSTCBDly; /* 任務(wù)等待的時(shí)限*/ INT8U OSTCBSt

6、at; /* 任務(wù)的當(dāng)前狀態(tài)標(biāo)志 */ INT8U OSTCBPrio; /* 任務(wù)優(yōu)先級(jí) (0 = highest, 63 = lowest) */ /*以下四行語(yǔ)句用于快速訪(fǎng)問(wèn)就緒表的數(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 posit

7、ion in ready table */ INT8U OSTCBBitY; /* Bit mask to access bit position 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;

8、/*記錄了該進(jìn)程占用多少個(gè)時(shí)間片*/ INT8U OSTSCurLen; /*記錄的是該進(jìn)程現(xiàn)在還剩下多少個(gè)時(shí)間片時(shí)間可以用*/#endif /*/ OS_TCB; 三.進(jìn)程創(chuàng)建 進(jìn)程創(chuàng)建的主要目的是跳過(guò)原代碼中的優(yōu)先級(jí)占用檢查，并在這里加入 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)寄存器分配存儲(chǔ)空間*

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

10、CBPrioTblprio = (OS_TCB *)0) /*保證優(yōu)先級(jí)沒(méi)有被其它任務(wù)占用 */ /* * if you want run the FIFO mask this code OSTCBPrioTblprio = (OS_TCB *)1; /* Reserve the priority to preventothers from doing . */ /* . the same thing until task is created. */那就是說(shuō)有一個(gè)任務(wù)存在了，不再是 Nul /*/ OS_EXIT_CRITICAL(); psp = (OS_STK *)OSTaskStkIn

11、it(task, pdata, ptos, 0); /* 初始化任務(wù)堆棧,即建立任務(wù)堆棧*/ err = OS_TCBInit(prio, psp, (OS_STK *)0, id, 0, (void *)0, 0, TSlen); /*初始化任務(wù)控制塊，從空閑的OS_TCB緩沖池中獲得并初始化一個(gè)任務(wù)控制塊*/if (err = OS_NO_ERR) /如果初始化沒(méi)有錯(cuò) OS_ENTER_CRITICAL();/進(jìn)入臨界狀態(tài) OSTaskCtr+; /*任務(wù)數(shù)量加一*/ OS_EXIT_CRITICAL(); if (OSRunning = TRUE) /* 如果多任務(wù)開(kāi)始，尋找最高優(yōu)先級(jí)任

12、務(wù) */ OS_Sched(); else /如果初始化任務(wù)控制塊有錯(cuò) OS_ENTER_CRITICAL(); OSTCBPrioTblprio = (OS_TCB *)0;/* Make this priority available to others 把這一優(yōu)先級(jí)給其它任務(wù)*/ OS_EXIT_CRITICAL(); return (err); /返回錯(cuò)誤信息/* */ else /這是FIFO的任務(wù)創(chuàng)建代碼 OS_EXIT_CRITICAL(); psp = (OS_STK *)OSTaskStkInit(task, pdata, ptos, 0); /* Initialize th

13、etasks 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 priority task if multitaskinghas started */ OS_Sched(); return(err); /*/ OS_E

14、XIT_CRITICAL(); return (OS_PRIO_EXIST); 其中加入的傳遞參數(shù)有兩個(gè)，一個(gè)是 id，一個(gè)是 TSLen 因?yàn)闀?huì)出現(xiàn)同優(yōu)先級(jí)的任務(wù)，那么采用優(yōu)先級(jí)做為任務(wù) ID 的方式是不可取的了，我們必須加入任務(wù) id 段 TSLen 段，是該進(jìn)程的時(shí)間片為多長(zhǎng)。 四.進(jìn)程初始化 進(jìn)程初始化基本保留以前的東西不動(dòng)，要的就僅僅是把 TSLen 加入 TCB，把上面說(shuō)到的那個(gè)鏈表鏈接起來(lái)。 代碼在文件OS_CORE.C中初始化任務(wù)控制塊1. 參數(shù)：prio：任務(wù)創(chuàng)建時(shí)的優(yōu)先級(jí)2. ptos:假定CPU寄存器放置于堆棧中指向堆棧棧頂?shù)闹羔槨ｍ敭?dāng)OS_STK_GROWTH為1時(shí)是

15、寄存器的高位、當(dāng)OS_STK_GROWTH為0時(shí)是寄存器的低位，堆棧增長(zhǎng)是CPU的特權(quán)。3. pbos：棧底指針。由OSTaskCreate()調(diào)用時(shí)傳入空指針。4. id：任務(wù)的ID5. stk_size:堆棧大小。當(dāng)堆棧單位是int8us時(shí)，堆棧大小包含堆棧數(shù)量個(gè)字節(jié)，當(dāng)堆棧單位是int32us時(shí)，堆棧大小包含“4*stk_size”個(gè)字節(jié)。堆棧單位由“#defineconstantOS_STK”建立，它是CPU特有。如果被OSTaskCreate()調(diào)用stk_size為0。6. pext：用戶(hù)提供存儲(chǔ)器空間的指針，用于任務(wù)控制塊。允許存儲(chǔ)浮點(diǎn)寄存器常量，MMU寄存器或者其它在內(nèi)容轉(zhuǎn)換時(shí)

16、有用的東西。甚至在TCB擴(kuò)展中為每個(gè)任務(wù)指定一個(gè)名字存到這個(gè)名字里面。OSTaskCreate()調(diào)用的時(shí)候?yàn)榭罩羔槨? opt：傳到OSTaskCreateExt()時(shí)可以選擇，被OSTaskCreate()調(diào)用的時(shí)候?yàn)?。 INT8U OS_TCBInit (INT8U prio, OS_STK *ptos, OS_STK *pbos, INT16U id, INT32U stk_size, void *pext, INT16U opt, INT8U TSlen) #if OS_CRITICAL_METHOD = 3 /*為CPU狀態(tài)寄存器分配存儲(chǔ)空間 */ OS_CPU_SR cpu_s

17、r; #endif OS_TCB *ptcb; OS_ENTER_CRITICAL(); ptcb = OSTCBFreeList; /*從空TCB列表中得到一塊空TCB */ if (ptcb != (OS_TCB *)0) /分配空TCB成功 OSTCBFreeList = ptcb-OSTCBNext; /*更新空閑TCB鏈表頭指針 */ OS_EXIT_CRITICAL(); ptcb-OSTCBStkPtr = ptos; /*保存棧頂指針到TCB */ ptcb-OSTCBPrio = (INT8U)prio; /*保存任務(wù)優(yōu)先級(jí)到TCB */ ptcb-OSTCBStat = O

18、S_STAT_RDY; /*任務(wù)狀態(tài)設(shè)為就緒*/ ptcb-OSTCBDly = 0; /*任務(wù)不延時(shí)*/ #if OS_TASK_CREATE_EXT_EN 0 ptcb-OSTCBExtPtr = pext; /*存儲(chǔ)TCB擴(kuò)展指針*/ ptcb-OSTCBStkSize = stk_size; /*存儲(chǔ)堆棧大小 */ ptcb-OSTCBStkBottom = pbos; /*存儲(chǔ)棧底指針*/ ptcb-OSTCBOpt = opt; /*存儲(chǔ)任務(wù)選項(xiàng) */ #else /以下四條語(yǔ)句用于防止編譯器警告，不要?jiǎng)h除 pext = pext; /* Prevent compiler warn

19、ing if not used */ stk_size = stk_size; pbos = pbos; opt = opt; #endif ptcb-OSTCBId = id; /* 存儲(chǔ)任務(wù)ID */ #if OS_TASK_DEL_EN 0 /允許包含任務(wù)刪除代碼 ptcb-OSTCBDelReq = OS_NO_ERR; /是否允許自動(dòng)刪除#endif ptcb-OSTCBY = prio 3; /*提前計(jì)算X,Y,位X，位Y*/ ptcb-OSTCBBitY = OSMapTblptcb-OSTCBY; ptcb-OSTCBX = prio & 0x07; /* 存儲(chǔ)就緒優(yōu)先級(jí)組中的

20、 8 個(gè)優(yōu)先級(jí)情況 */ ptcb-OSTCBBitX = OSMapTblptcb-OSTCBX; /*為什么要這樣算？不知道*/ #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ù)刪除函數(shù)*/ ptcb-OSTCBFlagNode = (OS_FLA

21、G_NODE *)0; /* 任務(wù)不等待事件標(biāo)志*/ #endif #if (OS_MBOX_EN 0) | (OS_Q_EN 0) & (OS_MAX_QS 0) /允許郵箱代碼產(chǎn)生|允許隊(duì)列代碼產(chǎn)生&最大隊(duì)列控制塊大于零 ptcb-OSTCBMsg = (void *)0; /*沒(méi)有接收到任務(wù)消息*/ #endif ptcb-OSTSLen=TSlen; ptcb-OSTSCurLen=TSlen; #if OS_VERSION = 204 /ucos版本大于等于204 OSTCBInitHook(ptcb); #endif OSTaskCreateHook(ptcb); /* Call

22、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-OSTSnext = OSTCBPrioTblprio-OSTSnext; OSTCBPrioTblprio-OSTSnext = ptcb; ptcb-OSTSprev = OSTCBPrioTblprio; (ptcb-OSTSnext )-OSTSpr

23、ev=ptcb; ptcb-OSTCBNext = OSTCBList; /* Link into TCB chain */ ptcb-OSTCBPrev = (OS_TCB *)0; if (OSTCBList != (OS_TCB *)0) OSTCBList-OSTCBPrev = ptcb; OSTCBList = ptcb; OSRdyGrp |= ptcb-OSTCBBitY; /* Make task ready to run */ OSRdyTblptcb-OSTCBY |= ptcb-OSTCBBitX; OS_EXIT_CRITICAL(); return (OS_NO_E

24、RR); OS_EXIT_CRITICAL(); return (OS_NO_MORE_TCB); if(OSTCBPrioTblprio = 0) OSTCBPrioTblprio = ptcb; ptcb-OSTSnext = ptcb; ptcb-OSTSprev = ptcb; else ptcb-OSTSnext = OSTCBPrioTblprio-OSTSnext; OSTCBPrioTblprio-OSTSnext = ptcb; ptcb-OSTSprev = OSTCBPrioTblprio; (ptcb-OSTSnext )-OSTSprev=ptcb; 這一段解釋一下

25、鏈表必須進(jìn)行鏈接，在優(yōu)先級(jí)沒(méi)有被占用的時(shí)候，這個(gè)鏈表的前后都鏈向自己，這樣在調(diào)度的時(shí)候，F(xiàn)IFO 調(diào)度就算指向下個(gè)任務(wù)，也指向的是自己，不影響優(yōu)先級(jí)調(diào)度。 當(dāng)在這個(gè)優(yōu)先級(jí)已經(jīng)有進(jìn)程的時(shí)候，那么我們需要的就是把這個(gè)進(jìn)程加入到這個(gè)優(yōu)先級(jí)的鏈表中，鏈表操作相信大家都能看懂，不多做解釋。 五.進(jìn)程調(diào)度 進(jìn)程調(diào)度基本還是依靠 UCOS 自己的調(diào)度算法，修改的，就僅僅是在調(diào)度之間，把運(yùn)行態(tài)優(yōu)先級(jí)的任務(wù)進(jìn)行運(yùn)算，時(shí)間片使用完，就指向下一個(gè)進(jìn)程。 OS_CORE.C void OSTimeTick (void) #if OS_CRITICAL_METHOD = 3 /* Allocate storage fo

26、r CPU status register */ OS_CPU_SR cpu_sr; #endif OS_TCB *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)階段值，計(jì)算自系統(tǒng)上電以來(lái)的時(shí)鐘節(jié)拍數(shù)*/ OS_EXIT_CRITICAL(); #endif if(OSTCBCur-OSTSCurLen)0)/如果時(shí)間片沒(méi)有用完 if(

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