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

Size: px

Start display at page:

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

栋巧邱
7 years ago
Views:

1 UCOS 时间片轮转调度算法详解引言.:UCOS 和我修改的 UCOS 的区别 UCOS 一种只支持优先级抢占型调度的操作系统它不支持同一个优先级有 2 个及以上的任务同时运作我修改的 UCOS 支持不同优先级调度的同时, 支持同一个优先级有 2 个以上的任务以时间片轮转方式进行调度这个就是 UCOS 和我修改的 UCOS 的区别我修改后的 UCOS, 在以后的文段中就称为 FIFO-UCOS FIFO 就是先进先出的意思, 和时间片轮转调度差不多的意思一. FIFO-UCOS 第一讲 -- 核心思想我不对 UCOS 做过多的解释, 我本人对 UCOS 的代码也没有看完事实上这个代码是我一年半以前做出来的了, 当时就是为了帮一个朋友完成论文, 并且为我卖的 S3C44B0 开发板增加一些东西吧 ( 不过我的板子最后没有卖出去多少, 题外话, 也许这个东西并没有多少人热心吧 ) 这一年半我再也没有从事过软件开发 ( 我一直都是硬件工程师 ), 对 UCOS 也有些遗忘了也许有的东西讲错了, 还请包函当时和那个做论文的朋友讨论的时候, 他也设计了一个调度方式, 但是事实证明没有我做的那个好毕竟它增加了另外一个 PCB 链 UCOS 写得很好, 把很多东西都做得很完善了我要说的核心思想, 就只有下面一小段话, 注意看了哦 : UCOS 在调度的时候, 会按照优先级选择进程进行调度, 我做的部分就仅仅是在他进行优先级检查之前, 把和运行态同等级的进程进行了替换, 替换成了时间片轮转调度的下一个进程!

进行调度这个就是 UCOS 和我修改的 UCOS 的区别我修改后的 UCOS, 在以后的文段中就称为 FIFO-UCOS FIFO 就是先进先出的意思, 和时间片轮转调度差不多的意思一.

2 呵呵, 核心思想讲完了下一节讲解具体代码了本人提供 UCOS 在 S3C44B0 上运行的完整代码注意, 是 UCOS 代码, 不是 FIFO-UCOS; 发邮件到我邮箱请不要在这个地方回复邮件地址问我要, 我不想复制地址那么麻烦, 就直接回复你的邮件是最简单的二.TCB 的修改 FIFO-UCOS 和 UCOS 并不能完全兼容, 最大的改变, 就是对 TCB 的结构做了改动, 加入了我自己的段该部分代码在 UCOS-II.H 文件中 : typedef struct os_tcb OS_STK *OSTCBStkPtr; /* Pointer to current top of stack */ #if OS_TASK_CREATE_EXT_EN > 0 void *OSTCBExtPtr; /* Pointer to user definable data for TCB extension */ OS_STK *OSTCBStkBottom; /* Pointer to bottom of stack */ INT32U OSTCBStkSize; /* Size of task stack (in number of stack elements) */ INT16U OSTCBOpt; /* Task options as passed by OSTaskCreateExt() */ INT16U OSTCBId; /* Task ID ( ) */ struct os_tcb *OSTCBNext; /* Pointer to next TCB in the TCB list */ struct os_tcb *OSTCBPrev; /* Pointer to previous TCB in the TCB list */

TCB 的修改 FIFO-UCOS 和 UCOS 并不能完全兼容, 最大的改变, 就是对 TCB 的结构做了改动, 加入了我自己的段该部分代码在 UCOS-II.

3 #if ((OS_Q_EN > 0) && (OS_MAX_QS > 0)) (OS_MBOX_EN > 0) (OS_SEM_EN > 0) (OS_MUTEX_EN > 0) OS_EVENT *OSTCBEventPtr; /* Pointer to event control block */ #if ((OS_Q_EN > 0) && (OS_MAX_QS > 0)) (OS_MBOX_EN > 0) void *OSTCBMsg; /* Message received from OSMboxPost() or OSQPost() */ #if (OS_VERSION >= 251) && (OS_FLAG_EN > 0) && (OS_MAX_FLAGS > 0) #if OS_TASK_DEL_EN > 0 OS_FLAG_NODE *OSTCBFlagNode; /* Pointer to event flag node */ OS_FLAGS OSTCBFlagsRdy; /* Event flags that made task ready to run */ INT16U OSTCBDly; /* Nbr ticks to delay task or, timeout waiting for event */ INT8U OSTCBStat; /* Task status */ INT8U OSTCBPrio; /* Task priority (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 position 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 */ //////////////////////////////////////////////////////////////////////////

*OSTCBFlagNode; /* Pointer to event flag node */ OS_FLAGS OSTCBFlagsRdy; /* Event flags that made task ready to run */ INT16U OSTCBDly; /* Nbr ticks to delay task or, timeout waiting for event */

4 //this is my FIFO shedule code #ifdef OS_TIME_SCHEDULE struct os_tcb *OSTSnext; struct os_tcb *OSTSprev; INT8U OSTSLen; INT8U OSTSCurLen; ////////////////////////////////////////////////////////////////////////// OS_TCB; 以下代码是我自己加的 : struct os_tcb *OSTSnext; struct os_tcb *OSTSprev; INT8U OSTSLen; INT8U OSTSCurLen; 当进程为同一个优先级的时候,*OSTSnext 和 *OSTSprev 就形成一个链表, 该链表是双向的, 前后形成一个环链表 OSTLen 记录了该进程占用多少个时间片 ; OSTSCurLen 记录的是该进程现在还剩下多少个时间片时间可以用 ; 三. 进程创建我的语言习惯很差, 毕竟做软件不是我的专业我再次说明, 我是硬件工程师把代码给一个朋友看的时候, 他直皱眉头他说 : 你改过的地方, 为什么不用 #ifdef FIFO_Schedule 来进行选择? 呵呵, 以后的代码可能要让行家郁闷了, 很难看, 见笑! 进程创建的主要目的是跳过原代码中的优先级占用检查, 并在这里加入 FIFO

INT8U OSTSLen; INT8U OSTSCurLen; 当进程为同一个优先级的时候,*OSTSnext 和 *OSTSprev 就形成一个链表, 该链表是双向的, 前后形成一个环链表 OSTLen 记录了该进程占用多少个时间片 ; OSTSCurLen 记录的是该进程现在还剩

5 进程创建文件在 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 /* Allocate storage for CPU status register */ OS_CPU_SR cpu_sr; OS_STK *psp; INT8U err; #if OS_ARG_CHK_EN > 0 if (prio > OS_LOWEST_PRIO) /* Make sure priority is within allowable range */ return (OS_PRIO_INVALID); OS_ENTER_CRITICAL(); if (OSTCBPrioTbl[prio] == (OS_TCB *)0) /* Make sure task doesn't already exist at this priority */ /////////////////////////////////////////////////////////////////////////////// //////// // if you want run the fifo mask this code //OSTCBPrioTbl[prio] = (OS_TCB *)1; /* Reserve the priority to prevent others from doing... */ /*... the same thing until task is created. */ //////////////////////////////////////////////////////////////////////

cpu_sr; OS_STK *psp; INT8U err; #if OS_ARG_CHK_EN > 0 if (prio > OS_LOWEST_PRIO) /* Make sure priority is within allowable range */ return (OS_PRIO_INVALID); OS_ENTER_CRITICAL(); if

6 psp = (OS_STK *)OSTaskStkInit(task, pdata, ptos, 0); /* Initialize the task's stack */ err = OS_TCBInit(prio, psp, (OS_STK *)0, id, 0, (void *)0, 0, TSlen); if (err == OS_NO_ERR) OS_ENTER_CRITICAL(); OSTaskCtr++; /* Increment the #tasks counter */ if (OSRunning == TRUE) /* Find highest priority task if multitasking has started */ OS_Sched(); else OS_ENTER_CRITICAL(); OSTCBPrioTbl[prio] = (OS_TCB *)0;/* Make this priority available to others */ return (err); //////////////////////////////////////////////////////////////////// else //this is FIFO task create code psp = (OS_STK *)OSTaskStkInit(task, pdata, ptos, 0); /* Initialize the task's stack */ err = OS_TCBInit(prio, psp, (OS_STK *)0, id, 0, (void *)0, 0, TSlen); if (err == OS_NO_ERR) OS_ENTER_CRITICAL(); OSTaskCtr++; /* Increment the #tasks counter */

*)0;/* Make this priority available to others */ return (err); //////////////////////////////////////////////////////////////////// else //this is FIFO task create code OSTaskCtr++; /* Increment the

7 if (OSRunning == TRUE) /* Find highest priority task if multitasking has started */ OS_Sched(); return(err); //////////////////////////////////////////////////////////////////// return (OS_PRIO_EXIST); 其中加入的传递参数有两个, 一个是 id, 一个是 TSLen 因为会出现同优先级的任务, 那么采用优先级做为任务 ID 的方式是不可取的了, 我们必须加入任务 id 段 TSLen 段, 是该进程的时间片为多长 /////////////////////////////////////////// 符号中的都是我加的代码, 注意看注释很容易看懂的四. 进程初始化进程初始化基本保留以前的东西不动, 要的就仅仅是把 TSLen 加入 TCB, 把上面说到的那个链表链接起来代码在文件 Os_task.c 中 INT8U OS_TCBInit (INT8U prio, OS_STK *ptos, OS_STK *pbos, INT16U id, INT32U stk_size, void *pext, INT16U opt, INT8U TSlen)

级做为任务 ID 的方式是不可取的了, 我们必须加入任务 id 段 TSLen 段, 是该进程的时间片为多长 /////////////////////////////////////////// 符号中的都是我加的代码, 注意看注释很容易看懂的四.

8 #if OS_CRITICAL_METHOD == 3 /* Allocate storage for CPU status register */ OS_CPU_SR cpu_sr; OS_TCB *ptcb; OS_ENTER_CRITICAL(); ptcb = OSTCBFreeList; /* Get a free TCB from the free TCB list */ if (ptcb!= (OS_TCB *)0) OSTCBFreeList = ptcb->ostcbnext; /* Update pointer to free TCB list */ ptcb->ostcbstkptr = ptos; /* Load Stack pointer in TCB */ ptcb->ostcbprio = (INT8U)prio; /* Load task priority into TCB */ ptcb->ostcbstat = OS_STAT_RDY; /* Task is ready to run */ ptcb->ostcbdly = 0; /* Task is not delayed */ #if OS_TASK_CREATE_EXT_EN > 0 ptcb->ostcbextptr = pext; /* Store pointer to TCB extension */ ptcb->ostcbstksize = stk_size; /* Store stack size */ ptcb->ostcbstkbottom = pbos; /* Store pointer to bottom of stack */ ptcb->ostcbopt = opt; /* Store task options */ #else pext = pext; /* Prevent compiler warning if not used */ stk_size = stk_size; pbos = pbos; opt = opt; ptcb->ostcbid = id; /* Store task ID */ #if OS_TASK_DEL_EN > 0 ptcb->ostcbdelreq = OS_NO_ERR;

= (OS_TCB *)0) OSTCBFreeList = ptcb->ostcbnext; /* Update pointer to free TCB list */ ptcb->ostcbstkptr = ptos; /* Load Stack pointer in TCB */ ptcb->ostcbprio = (INT8U)prio; /* Load task priority

9 ptcb->ostcby = prio >> 3; /* Pre-compute X, Y, BitX and BitY */ ptcb->ostcbbity = OSMapTbl[ptcb->OSTCBY]; ptcb->ostcbx = prio & 0x07; ptcb->ostcbbitx = OSMapTbl[ptcb->OSTCBX]; #if OS_EVENT_EN > 0 ptcb->ostcbeventptr = (OS_EVENT *)0; /* Task is not pending on an event */ #if (OS_VERSION >= 251) && (OS_FLAG_EN > 0) && (OS_MAX_FLAGS > 0) && (OS_TASK_DEL_EN > 0) ptcb->ostcbflagnode = (OS_FLAG_NODE *)0; /* Task is not pending on an event flag */ #if (OS_MBOX_EN > 0) ((OS_Q_EN > 0) && (OS_MAX_QS > 0)) ptcb->ostcbmsg = (void *)0; /* No message received */ ///////////////////////////////////////////////////////////////////////////// ptcb->ostslen=tslen; ptcb->ostscurlen=tslen; ///////////////////////////////////////////////////////////////////////////// #if OS_VERSION >= 204 OSTCBInitHook(ptcb); OSTaskCreateHook(ptcb); /* Call user defined hook */

(OS_FLAG_NODE *)0; /* Task is not pending on an event flag */ #if (OS_MBOX_EN > 0) ((OS_Q_EN > 0) && (OS_MAX_QS > 0)) ptcb->ostcbmsg = (void *)0; /* No message received */

10 OS_ENTER_CRITICAL(); //////////////////////////////////////////////////////////////////////// if(ostcbpriotbl[prio] == 0) OSTCBPrioTbl[prio] = ptcb; ptcb->ostsnext = ptcb; ptcb->ostsprev = ptcb; else ptcb->ostsnext = OSTCBPrioTbl[prio]->OSTSnext; OSTCBPrioTbl[prio]->OSTSnext = ptcb; ptcb->ostsprev = OSTCBPrioTbl[prio]; (ptcb->ostsnext )->OSTSprev=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 */ OSRdyTbl[ptcb->OSTCBY] = ptcb->ostcbbitx; return (OS_NO_ERR); return (OS_NO_MORE_TCB);

/////////////////////////////////////////////////////////////////////////// ptcb->ostcbnext = OSTCBList; /* Link into TCB chain */ ptcb->ostcbprev = (OS_TCB *)0; if (OSTCBList!

11 if(ostcbpriotbl[prio] == 0) OSTCBPrioTbl[prio] = ptcb; ptcb->ostsnext = ptcb; ptcb->ostsprev = ptcb; else ptcb->ostsnext = OSTCBPrioTbl[prio]->OSTSnext; OSTCBPrioTbl[prio]->OSTSnext = ptcb; ptcb->ostsprev = OSTCBPrioTbl[prio]; (ptcb->ostsnext )->OSTSprev=ptcb; 这一段解释一下链表必须进行链接, 在优先级没有被占用的时候, 这个链表的前后都链向自己, 这样在调度的时候,FIFO 调度就算指向下个任务, 也指向的是自己, 不影响优先级调度当在这个优先级已经有进程的时候, 那么我们需要的就是把这个进程加入到这个优先级的链表中, 链表操作相信大家都能看懂, 不多做解释五. 进程调度进程调度基本还是依靠 UCOS 自己的调度算法, 修改的, 就仅仅是在调度之间, 把运行态优先级的任务进行运算, 时间片使用完, 就指向下一个进程 Os_core.c void OSTimeTick (void)

用的时候, 这个链表的前后都链向自己, 这样在调度的时候,FIFO 调度就算指向下个任务, 也指向的是自己, 不影响优先级调度当在这个优先级已经有进程的时候, 那么我们需要的就是把这个进程加入到这个优先级的链

12 #if OS_CRITICAL_METHOD == 3 /* Allocate storage for CPU status register */ OS_CPU_SR cpu_sr; 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++; if((ostcbcur->ostscurlen)>0)// 如果时间片没有用完 if(--ostcbcur->ostscurlen==0)// 时间片在这次调度中用完了 if(ostcbcur->ostsnext!= OSTCBCur)// 如果优先级里面至少有两个进程 ( 看上一篇文章来理解这个地方 ) OSTCBCur->OSTSCurLen = OSTCBCur->OSTSLen;// 把现在时间片用完的进程的时间补回来, 以便下次调度 OSTCBPrioTbl[OSTCBCur->OSTCBPrio] = OSTCBCur->OSTSnext;// 把该优先级的任务替换成下一个任务 ; OSPrioCur=0;// 把当前的运行优先级改成 0, 不然调度认为该优先级的任务没有结束, 不执行任务调度, 结果回到的地方, 还是上一个时间片的任务, 就死翘翘了!

13 ptcb = OSTCBList; /* Point at first TCB in TCB list */ while (ptcb->ostcbprio!= OS_IDLE_PRIO) /* Go through all TCBs in TCB list */ OS_ENTER_CRITICAL(); if (ptcb->ostcbdly!= 0) /* Delayed or waiting for event with TO */ if (--ptcb->ostcbdly == 0) /* Decrement nbr of ticks to end of delay */ if ((ptcb->ostcbstat & OS_STAT_SUSPEND) == 0x00) /* Is task suspended? */ if(ostcbpriotbl[ptcb->ostcbprio]==0)// 如果该优先级只剩下一个进程了 OSRdyGrp = ptcb->ostcbbity; /* No, Make task Rdy to Run (timed out)*/ OSRdyTbl[ptcb->OSTCBY] = ptcb->ostcbbitx; OSTCBPrioTbl[ptcb->OSTCBPrio]=ptcb; ptcb->ostsnext=ptcb;// 指向自己 ptcb->ostsprev=ptcb;// 指向自己 else// 增加了链表操作而已, 自己看吧, 把任务脱出链表而已 ptcb->ostsnext=ostcbpriotbl[ptcb->ostcbprio]->ostsnext; OSTCBPrioTbl[ptcb->OSTCBPrio]->OSTSnext=ptcb; ptcb->ostsprev=ostcbpriotbl[ptcb->ostcbprio]; (ptcb->ostsnext)->ostsprev=ptcb; else /* Yes, Leave 1 tick to prevent... */ ptcb->ostcbdly = 1; /*... loosing the task when the... */ /*... suspension is removed. */ ptcb = ptcb->ostcbnext; /* Point at next TCB in TCB list */

*/ if(ostcbpriotbl[ptcb->ostcbprio]==0)// 如果该优先级只剩下一个进程了 OSRdyGrp = ptcb->ostcbbity; /* No, Make task Rdy to Run (timed out)*/ OSRdyTbl[ptcb->OSTCBY] = ptcb->ostcbbitx;

14 该函数是 UCOS 调度的关键函数, 也是 FIFO 最核心的东西我知道有些东西多余了, 比如完全没有必要判断是否这个优先级只有一个任务但是, 这个是任务调度处理中, 消耗的 OS 时间, 也就是调度效率, 我个人认为, 调度占用时间越短越好呵呵 UCOS 调度的文章就写到这里, 信号量等其他地方修改还请大家自己动手了! 10 楼 : 张 SIR 真是好样的我也是做硬件的, 有一段时间没玩过 UCOS 了最近也写了一个调度程序 ( 不敢说是操作系统 ), 实现多个任务的伪并行运行

好呵呵 UCOS 调度的文章就写到这里, 信号量等其他地方修改还请大家自己动手了!

<433A5C446F63756D656E747320616E642053657474696E67735C41646D696E6973747261746F725CD7C0C3E65CC2DBCEC4CFB5CDB3CAB9D3C3D6B8C4CFA3A8BCF2BBAFA3A95CCAB9D3C3D6B8C4CF31302D31392E646F63>

<433A5C446F63756D656E747320616E642053657474696E67735C41646D696E6973747261746F725CD7C0C3E65CC2DBCEC4CFB5CDB3CAB9D3C3D6B8C4CFA3A8BCF2BBAFA3A95CCAB9D3C3D6B8C4CF31302D31392E646F63> ( 一 ) 系统整体操作流程简述 3 ( 二 ) 系统中各角色操作功能说明 5 1. 学院管理员 5 2. 教学院长 8 3. 指导教师 10 4. 答辩组组长 12 5. 学生 12 6. 系统管理员 15 ( 一 ) 论文系统常见问题 16 ( 二 ) 论文查重常见问题 22 1 2 主