修改uCOS_II以实现“优先级+时间片”联合调度

2013年12月18日 18:12
转载(0) / 评论(0) / 浏览(1003)

本文在uCOS II上增加时间片任务调度的的原理:

对设置为同优先级的任务使用时间片调度,不同优先级任务仍然使用uCOS II的优先级调度策略。在同优先级任务的时间片调度中,所有任务暂时时间片长度固定,时间片的调度使用FIFO(先进先出)队列。


整体的描述参看下图。

\

上图中假设有3个优先级为5的任务,3个优先级为8的任务。纵向,第一列的OS_TCB形成OSTCBList双向链表(通过OSTCBNext和OSTCBPrev指针,这是原uCOS II系统已经有的部分)。横向,通过OSPSPrev和OSPSNext指针形成时间片链表(实际上是FIFO),这部分是我们在uCOS II上要增加的内容。第一列的任务每当有任务时间片用完后将挪到队列尾,从FIFO中选择下一个任务,这就是本文的时间片调度的过程。总体上看来,不同优先级使用了uCOS II原有的优先级调度策略,相同优先级之间增加了时间片调度策略,因此本文称为“优先级+时间片”联合调度。


下面我们列出实现时间片调度要修改的一些结构和函数,我们可以通过调试跟踪了解uCOS II的机理,从而理解为什么要这么做。

1 修改结构体OS_TCB(ucos_ii.h文件中)

增加4个成员变量用于时间片调度。

  1. struct os_tcb {  
  2.     ...  
  3.   
  4.     /* 增加下面4个成员 */  
  5.     struct os_tcb *OSPSNext;  /* 同一优先级下,每个任务的后向指针 */  
  6.     struct os_tcb *OSPSPrev;  /* 同一优先级下,每个任务的前向指针 */  
  7.     INT8U OSPSLen;            /* 该任务分配的时间片             */  
  8.     INT8U OSPSCurLen;         /* 该任务当前剩下的时间片          */  
  9. } OS_TCB;  


2 修改OS_TCBInit任务结构体初始化函数(os_core.c文件)

在OS_TCBInit中增加时间片长度的初始化,我们可以先在os_cfg_r.h中宏定义一个时间片长度用于不同情况下的配置,

  1. #define TIME_SLICE_LEN            10  

OS_TCBInit函数中增加结构体成员初始化

  1. ptcb->OSPSLen = TIME_SLICE_LEN;  
  2. ptcb->OSPSCurLen = TIME_SLICE_LEN;  
  3. ptcb->OSPSNext = (OS_TCB*)0;  
  4. ptcb->OSPSPrev = (OS_TCB*)0;  

当出现同优先级的情况时,任务控制块插入到时间片链表中而不是优先级链表中,OS_TCBInit函数中要增加将任务插入到时间片链表的过程,我写的一个示例如下:

  1. if (ptcb != (OS_TCB *)0) {  
  2.     ...  
  3.       
  4.     OSTCBPrioTbl[prio] = ptcb;  
  5.     if (OSTCBList != (OS_TCB *) 0) { /* 不存在同优先级任务, 按照uCOS ii方法链接到OSTCBList */  
  6.         ptcb->OSTCBNext    = OSTCBList; /* Link into TCB chain                      */  
  7.         ptcb->OSTCBPrev    = (OS_TCB *)0;  
  8.         if (OSTCBList != (OS_TCB *)0) {  
  9.             OSTCBList->OSTCBPrev = ptcb;  
  10.         }  
  11.         OSTCBList               = ptcb;  
  12.         OSRdyGrp               |= ptcb->OSTCBBitY; /* Make task ready to run */  
  13.         OSRdyTbl[ptcb->OSTCBY] |= ptcb->OSTCBBitX;  
  14.     } else {  /* 出现同优先级情况,链接到时间片链表 */  
  15.         while(ptcb1->OSPSNext!=(OS_TCB*) 0)  
  16.         {  
  17.            ptcb1=ptcb1->OSPSNext;   /* move to the rear of time slice list */  
  18.         }  
  19.         ptcb1->OSPSNext = ptcb;  
  20.         ptcb->OSPSPrev = ptcb1;   
  21.         ptcb->OSPSNext=(OS_TCB*) 0;  
  22.   
  23.         ptcb->OSTCBNext = (OS_TCB *)0;  
  24.         ptcb->OSTCBPrev = (OS_TCB *)0;  
  25.     }  
  26.   
  27.     OSTaskCtr++;  /* Increment the #tasks counter             */  
  28.     OS_EXIT_CRITICAL();  
  29.     return (OS_ERR_NONE);  
  30. }  


3 修改时钟中断函数OSTimeTick(os_core.c文件)

增加时间片调度的内容,这是时间片调度的主要部分。给出一个示例:

  1. OSTimeTick (void)  
  2. {  
  3.     ...  
  4.     OS_TCB *ptcb1;  
  5.     
  6.     if (OSRunning == TRUE)  
  7.     {  
  8.         ptcb = OSTCBList;       /* Point at first TCB in TCB list           */  
  9.         while (ptcb->OSTCBPrio != OS_IDLE_PRIO)  
  10.         {           /* Go through all TCBs in TCB list          */  
  11.             OS_ENTER_CRITICAL ();  
  12.   
  13.             /* delay time out */  
  14.             ...  
  15.   
  16.             /* time slice count down */  
  17.             if (ptcb->OSPSCurLen != 0) {  
  18.                 --ptcb->OSPSCurLen;  
  19.             } else {  /* time slice out */  
  20.                 /* reload time slice */  
  21.                 ptcb->OSPSCurLen = ptcb->OSPSLen;  
  22.   
  23.                 ptcb1 = ptcb->OSPSNext;  
  24.                 if (ptcb1 != (OS_TCB*) 0) {  /* there are some tasks with the same priority */  
  25.                     /* (1) link new to priority-level list */  
  26.                     ptcb1->OSTCBNext = ptcb->OSTCBNext;  
  27.                     ptcb1->OSTCBPrev = ptcb->OSTCBPrev;  
  28.                     if (ptcb->OSTCBNext != (OS_TCB *)0) {  
  29.                         ptcb->OSTCBNext->OSTCBPrev = ptcb1;      
  30.                     }  
  31.                     if (ptcb->OSTCBPrev != (OS_TCB *)0) {  
  32.                         ptcb->OSTCBPrev->OSTCBNext = ptcb1;  
  33.                     }  
  34.                     ptcb->OSTCBPrev = (OS_TCB *)0;  
  35.                     ptcb->OSTCBNext = (OS_TCB *)0;  
  36.   
  37.                     /* (2) update OSTCBList if TCBcur is OSTCBList*/  
  38.                     if (ptcb == OSTCBList) {  
  39.                         OSTCBList = ptcb1;     
  40.                     }             
  41.   
  42.                     /* (3) Compute X, Y, BitX and BitY */  
  43.                     ptcb1->OSTCBY = ptcb1->OSTCBPrio >> 3;     
  44.                     ptcb1->OSTCBBitY = OSMapTbl[ptcb1->OSTCBY];   
  45.                     ptcb1->OSTCBX = ptcb1->OSTCBPrio & 0x07;                          
  46.                     ptcb1->OSTCBBitX = OSMapTbl[ptcb1->OSTCBX];     
  47.                       
  48.                     /* (4) set task to be ready */  
  49.                     if (ptcb1->OSTCBDly == 0) {  
  50.                         OSRdyGrp |= OSMapTbl[ptcb1->OSTCBY];  
  51.                         OSRdyTbl[ptcb1->OSTCBY] |= OSMapTbl[ptcb1->OSTCBX];  
  52.                     }                             
  53.   
  54.                     /* (5) move ptcb to the rear of queue */                          
  55.                     while(ptcb1->OSPSNext!=(OS_TCB*) 0)  
  56.                     {  
  57.                         ptcb1=ptcb1->OSPSNext;  
  58.                     }  
  59.                     ptcb1->OSPSNext = ptcb;       
  60.                     ptcb->OSPSPrev = ptcb1;   
  61.                     ptcb->OSPSNext=(OS_TCB*) 0;  
  62.   
  63.                     /* (6) set OSTCBPrioTbl for Context switch */  
  64.                     OSTCBPrioTbl[ptcb1->OSTCBPrio]=ptcb1;    
  65.                 } else {  
  66.                     // do nothing  
  67.                 }     
  68.             }  
  69.   
  70.             /*  
  71.              * (7) don't forgot that after time slice  
  72.              * schedule, ptcb->OSTCBNext==NULL  
  73.              */  
  74.             if (ptcb->OSTCBNext != (OS_TCB*)0) {  
  75.                 ptcb = ptcb->OSTCBNext;  
  76.             } else if (ptcb1->OSTCBNext != (OS_TCB*)0) {  
  77.                 ptcb = ptcb1->OSTCBNext;  
  78.             } else {  
  79.                 break;  
  80.             }  
  81.               
  82.             OS_EXIT_CRITICAL ();  
  83.         }  
  84.     }  
  85. }  

OK,修改好上面的内容就大致实现了在uCOS II上增加时间片调度的过程,通过修改时间片长度TIME_SLICE_LEN可以验证时间片长度对任务调度的影响。本文最后在硬件平台STM32F103RB上测试通过,但因为时间片的引入而且未对程序做相关优化,因此时间片调度的实时性提高上还有待完善。

评论(0)

发表评论
登录
我可以
  • 评论
关联标签
关联热门电子辑
类似的技文