UCOS时间片轮转调度算法详解

1、UCOS 时间片轮转调度算法详解2009年8月4日 1. UCOS 一种只支持优先级抢占型调度的操作系统。它不支持同一个优先级有 2 个及以上的任务同时运作。 我修改的 UCOS 支持不同优先级调度的同时，支持同一个优先级有 2 个以上的任务以时间片轮转方式进行调度。 这个就是 UCOS 和我修改的 UCOS 的区别。 我修改后的 UCOS，在以后的文段中就称为“FIFO-UCOS”。 FIFO 就是先进先出的意思，和时间片轮转调度差不多的意思。 一. FIFOUCOS核心思想 UCOS 在调度的时候，会按照优先级选择进程进行调度，我做的部分就仅仅是在他进行优先级检查之前，把和运行态同等级的进

2、程进行了替换，替换成了时间片轮转调度的下一个进程！ 二.TCB 的修改 FIFO-UCOS 和 UCOS 并不能完全兼容，最大的改变，就是对 TCB 的结构做了改动，加入了我自己的段。 该部分代码在 UCOS-II.H 文件中： typedef struct os_tcb OS_STK *OSTCBStkPtr; /* 当前任务堆栈栈顶指针 */ #if OS_TASK_CREATE_EXT_EN 0 void *OSTCBExtPtr; /* 指向用户定义的任务控制块扩展*/ OS_STK *OSTCBStkBottom; /* 指向任务堆栈栈底指针 */ INT32U OSTCBStkSi

3、ze; /*存有栈中可容纳的指针元数目而不是用字节（Byte）表示的栈容量总数。*/ INT16U OSTCBOpt; /* Task options as passed by OSTaskCreateExt() */ INT16U OSTCBId; /* Task ID (0.65535) 存储任务的识别码ID，备用 */ #endif struct os_tcb *OSTCBNext; /*指向后一个任务控制块的指针*/ struct os_tcb *OSTCBPrev; /*指向前一个任务控制块的指针*/ #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定义为：能使队列代码产生&申请队列控制块最大数不为零|能使邮箱代码产生| 能使信号量代码产生|能使互斥量代码产生 */ 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() 指向传递给任务的消息的指针*/ #endi

5、f #if (OS_VERSION = 251) & (OS_FLAG_EN 0) & (OS_MAX_FLAGS 0) #if OS_TASK_DEL_EN 0 /* OS版本大于等于251&能使事件标志代码产生&最大标志数大于零*/ OS_FLAG_NODE *OSTCBFlagNode; /*指针指向事件标志节点*/ #endif OS_FLAGS OSTCBFlagsRdy; /* Event flags that made task ready to run事件标志使任务准备运行*/ #endif INT16U OSTCBDly; /* 任务等待的时限*/ INT8U OSTCBSt

6、at; /* 任务的当前状态标志 */ INT8U OSTCBPrio; /* 任务优先级 (0 = highest, 63 = lowest) */ /*以下四行语句用于快速访问就绪表的数据*/ 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、/*记录了该进程占用多少个时间片*/ INT8U OSTSCurLen; /*记录的是该进程现在还剩下多少个时间片时间可以用*/#endif /*/ OS_TCB; 三.进程创建 进程创建的主要目的是跳过原代码中的优先级占用检查，并在这里加入 FIFO 进程创建。 文件在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状态寄存器分配存储空间*

9、/ OS_CPU_SR cpu_sr; /CPU状态字是十六位cpu_sr为OS_CPU_SR型变量#endif OS_STK *psp; /创建一个指向数据类型为OS_STK的指针和一个8位的整型数 INT8U err; #if OS_ARG_CHK_EN 0 if (prio OS_LOWEST_PRIO) /*保证优先级在允许范围内 */ return (OS_PRIO_INVALID); #endif OS_ENTER_CRITICAL(); /* OS_ENTER_CRITICAL（）和OS_EXIT_CRITICAL（）为定义的宏，用来关闭、打开CPU 的中断。*/ if (OST

10、CBPrioTblprio = (OS_TCB *)0) /*保证优先级没有被其它任务占用 */ /* * 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. */那就是说有一个任务存在了，不再是 Nul /*/ OS_EXIT_CRITICAL(); psp = (OS_STK *)OSTaskStkIn

11、it(task, pdata, ptos, 0); /* 初始化任务堆栈,即建立任务堆栈*/ err = OS_TCBInit(prio, psp, (OS_STK *)0, id, 0, (void *)0, 0, TSlen); /*初始化任务控制块，从空闲的OS_TCB缓冲池中获得并初始化一个任务控制块*/if (err = OS_NO_ERR) /如果初始化没有错 OS_ENTER_CRITICAL();/进入临界状态 OSTaskCtr+; /*任务数量加一*/ OS_EXIT_CRITICAL(); if (OSRunning = TRUE) /* 如果多任务开始，寻找最高优先级任

12、务 */ OS_Sched(); else /如果初始化任务控制块有错 OS_ENTER_CRITICAL(); OSTCBPrioTblprio = (OS_TCB *)0;/* Make this priority available to others 把这一优先级给其它任务*/ OS_EXIT_CRITICAL(); return (err); /返回错误信息/* */ else /这是FIFO的任务创建代码 OS_EXIT_CRITICAL(); psp = (OS_STK *)OSTaskStkInit(task, pdata, ptos, 0); /* Initialize th

13、etasks stack初始化任务堆栈,即建立任务堆栈*/ err = OS_TCBInit(prio, psp, (OS_STK *)0, id, 0, (void *)0, 0, TSlen); if (err = OS_NO_ERR) OS_ENTER_CRITICAL(); OSTaskCtr+; /*任务数量加一*/ 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); 其中加入的传递参数有两个，一个是 id，一个是 TSLen 因为会出现同优先级的任务，那么采用优先级做为任务 ID 的方式是不可取的了，我们必须加入任务 id 段 TSLen 段，是该进程的时间片为多长。 四.进程初始化 进程初始化基本保留以前的东西不动，要的就仅仅是把 TSLen 加入 TCB，把上面说到的那个链表链接起来。 代码在文件OS_CORE.C中初始化任务控制块1. 参数：prio：任务创建时的优先级2. ptos:假定CPU寄存器放置于堆栈中指向堆栈栈顶的指针。栈顶当OS_STK_GROWTH为1时是

15、寄存器的高位、当OS_STK_GROWTH为0时是寄存器的低位，堆栈增长是CPU的特权。3. pbos：栈底指针。由OSTaskCreate()调用时传入空指针。4. id：任务的ID5. stk_size:堆栈大小。当堆栈单位是int8us时，堆栈大小包含堆栈数量个字节，当堆栈单位是int32us时，堆栈大小包含“4*stk_size”个字节。堆栈单位由“#defineconstantOS_STK”建立，它是CPU特有。如果被OSTaskCreate()调用stk_size为0。6. pext：用户提供存储器空间的指针，用于任务控制块。允许存储浮点寄存器常量，MMU寄存器或者其它在内容转换时

16、有用的东西。甚至在TCB扩展中为每个任务指定一个名字存到这个名字里面。OSTaskCreate()调用的时候为空指针。7 opt：传到OSTaskCreateExt()时可以选择，被OSTaskCreate()调用的时候为0。 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状态寄存器分配存储空间 */ 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; /*保存任务优先级到TCB */ ptcb-OSTCBStat = O

18、S_STAT_RDY; /*任务状态设为就绪*/ ptcb-OSTCBDly = 0; /*任务不延时*/ #if OS_TASK_CREATE_EXT_EN 0 ptcb-OSTCBExtPtr = pext; /*存储TCB扩展指针*/ ptcb-OSTCBStkSize = stk_size; /*存储堆栈大小 */ ptcb-OSTCBStkBottom = pbos; /*存储栈底指针*/ ptcb-OSTCBOpt = opt; /*存储任务选项 */ #else /以下四条语句用于防止编译器警告，不要删除 pext = pext; /* Prevent compiler warn

19、ing if not used */ stk_size = stk_size; pbos = pbos; opt = opt; #endif ptcb-OSTCBId = id; /* 存储任务ID */ #if OS_TASK_DEL_EN 0 /允许包含任务删除代码 ptcb-OSTCBDelReq = OS_NO_ERR; /是否允许自动删除#endif ptcb-OSTCBY = prio 3; /*提前计算X,Y,位X，位Y*/ ptcb-OSTCBBitY = OSMapTblptcb-OSTCBY; ptcb-OSTCBX = prio & 0x07; /* 存储就绪优先级组中的

20、 8 个优先级情况 */ ptcb-OSTCBBitX = OSMapTblptcb-OSTCBX; /*为什么要这样算？不知道*/ #if OS_EVENT_EN 0 ptcb-OSTCBEventPtr = (OS_EVENT *)0; /* 任务不等待任何事件发生*/ #endif #if (OS_VERSION = 251) & (OS_FLAG_EN 0) & (OS_MAX_FLAGS 0) & (OS_TASK_DEL_EN 0) /*OS版本大于等于251&能使事件标志代码产生&最大标志数大于零&允许包含任务删除函数*/ ptcb-OSTCBFlagNode = (OS_FLA

21、G_NODE *)0; /* 任务不等待事件标志*/ #endif #if (OS_MBOX_EN 0) | (OS_Q_EN 0) & (OS_MAX_QS 0) /允许邮箱代码产生|允许队列代码产生&最大队列控制块大于零 ptcb-OSTCBMsg = (void *)0; /*没有接收到任务消息*/ #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; /*任务控制块存入到已创建任务控制块列表当中*/ 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、链表必须进行链接，在优先级没有被占用的时候，这个链表的前后都链向自己，这样在调度的时候，FIFO 调度就算指向下个任务，也指向的是自己，不影响优先级调度。 当在这个优先级已经有进程的时候，那么我们需要的就是把这个进程加入到这个优先级的链表中，链表操作相信大家都能看懂，不多做解释。 五.进程调度 进程调度基本还是依靠 UCOS 自己的调度算法，修改的，就仅仅是在调度之间，把运行态优先级的任务进行运算，时间片使用完，就指向下一个进程。 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+; /*系统节拍现阶段值，计算自系统上电以来的时钟节拍数*/ OS_EXIT_CRITICAL(); #endif if(OSTCBCur-OSTSCurLen)0)/如果时间片没有用完 if(

27、-OSTCBCur-OSTSCurLen=0)/时间片在这次调度中用完了 if(OSTCBCur-OSTSnext != OSTCBCur)/*如果优先级里面至少有两个进程（看上一篇文章来理解这个地方）*/ OSTCBCur-OSTSCurLen = OSTCBCur-OSTSLen;/*把现在时间片用完的进程的时间补回来，以便下次调度*/ OSTCBPrioTblOSTCBCur-OSTCBPrio = OSTCBCur-OSTSnext;/*把该优先级的任务替换成下一个任务*/ OSPrioCur=0;/把当前的运行优先级改成 0，不然调度认为该优先级的任务没有结束，不执行任务调度，结果回到的地方，还是上一个时间片的任务，就死翘翘了！ ptcb = OSTCBList; /* Point at first TCB in TCB list */ while (ptcb-OSTCBPrio != OS_IDLE_PRIO) /*空闲任务处于控制块双向链表的最后一个