摘要 多任务的调度算法多种多样，各种调度算法也各有千秋。在某些应用场合，时间片调度法就比纯粹的优先级调度法更具优势。本文提出了基于µC/OS-II的时间片调度法的设计原理，给出了实现该调度法的关键部分源代码，并且通过一个简单的应用实例将该时间片调度法与优先级调度法进行比较。
关键词 多任务、时间片调度法、优先级调度法、µC/OS-II
引言
µC/OS-II嵌入式实时操作系统采用的是基于优先级的可剥夺调度法[1]。基于优先级的可剥夺调度法是指，CPU总是让处于就绪态的、优先级最高的任务运行；最高优先级的任务一旦就绪，总能得到CPU的使用权，当一个运行着的任务使一个比它优先级高的任务进入了就绪态时，当前任务的CPU使用权就被剥夺了，更高优先级的任务立刻得到了CPU的使用权。除非最高优先级的任务主动放弃CPU的使用权（通过调用OSTimeDly()、OSSemPend()等函数），否则低优先级的任务是没机会获得CPU使用权的。对于一个实际应用系统中耗时比较长的任务，为了让其他任务能够得到实时调度，我们可以用两种方法来处理，第一种方法是把该任务的优先级设为最低（当然还是比空闲任务要高）；第二种方法就是让该耗时任务运行一段时间后延时一下再继续运行，即把整个任务划分为若干步骤来执行，如以下的示例代码：
void Task_Timeconsuming(void *pdata)
{
……
While(1)
{
ExecuteStep1();
OSTimeDly(n); /*延时若干时间以让其他低优先级任务获得CPU的使用权*/
ExecuteStep2();
OSTimeDly(n);
……
}
}
很多情况下耗时长的任务并不能设置为最低优先级任务，而划分步骤来执行的方法不但繁琐而且每一步执行的时间也是不确定的（其他低优先级任务获得CPU使用权的时间也会是不确定的）。笔者在用µC/OS-II开发一款车载信息娱乐系统的时候就碰到了这样的问题，因此设计了一种优先级和时间片相结合的调度法（也就是基于µC/OS-II的时间片调度法）。
1．调度原理
这种调度法给处于就绪态的每一个任务都分配一个时间片（优先级越高分配的时间片越长，空闲任务得不到时间片的分配），内核按照任务的优先级依次调度处于就绪态的任务，即当就绪态中最高优先级的任务用完自己的时间片后，CPU控制权转让给就绪态中优先级第二高的任务，该任务用完自己的时间片后，CPU控制权又转让给下一优先级的就绪态任务……当就绪态的每一个任务都被调度一次之后将重新为它们分配时间片，然后又开始新一轮的调度……[2]
其中要注意的是，在调度过程中如果有一个比当前任务优先级更高的任务由其他态变成了就绪态（被创建或获取了一个信号量等等），当前任务的CPU控制权将被剥夺；空闲任务仍然是等到其他任务都退出就绪态才获得CPU使用权。
图1解释了该调度法的调度过程（其中任务1优先级最高，任务2次之，任务3最低）。
（1） 任务2和任务3都处于就绪态，任务1在等待一个信号量，优先级中的任务2获得CPU使用权。
（2） 任务2的时间片用完，优先级低的任务3获得CPU使用权。
（3） 任务3的时间片用完，任务2重新获得CPU使用权。
（4） 任务2的时间片还没用完时中断来临，中断服务程序获得CPU使用权。
（5） 中断服务程序发送了一个任务1等待的信号量，中断服务完成后优先级高的任务1获得CPU使用权。
（6） 任务1的时间片用完，任务2继续运行。
（7） 任务2的时间片用完，任务3获得CPU使用权。
（8） 任务3的时间片用完，重新分配时间片，新一轮调度开始。
2．实现方法
在调度算法的实现过程中，笔者力求做到3点：
（1） 尽可能少地改动µC/OS-II原有的代码。
（2） 增加的代码在风格上保持与原有的相一致。
（3） 兼容原有的优先级调度法（可以很方便地选择优先级调度法或是时间片调度法）。
注：对于该小节中出现的代码，如果是笔者增加的部分都用粗体表示。
2．1 数据结构中增加的变量
在进程控制块中增加两项：
Typedef struct os_tcb{
……
#if OS_TASK_TIME_SLICE_EN > 0 /*条件编译，OS_TASK_TIME_SLICE_EN在os_cfg.h中定义，凡是涉及到与时间片调度相关的代码都用条件编译，这样一来我们可以通过更改配置文件很方便地选择任务调度法*/
INT16U OSTCBTimeSlice; /*任务的时间片大小，在任务创建时被初始化，运行过程中保持不变*/
INT16U OSTCBCounter; /*任务运行剩余时间计数器，每一轮调度开始时该变量被赋值（等于OSTCBTimeSlice），运行过程中不断递减，当其等于0时任务被剥夺CPU使用权*/
#endif
}
由于当前任务的时间片使用完时，该任务将被从就绪表OSRdyGrp以及OSRdyTbl[OS_RDY_TBL_SIZE]中清除；新一轮调度开始时它又必须被恢复，因此笔者在uCOS_II.h文件中增加以下变量（我们不妨把它们称为时间片调度表）分别用于保存OSRdyGrp 和OSRdyTbl[OS_RDY_TBL_SIZE]。
OS_EXT INT8U OSTSSGrp;
OS_EXT INT8U OSTSSTbl[OS_RDY_TBL_SIZE];
另外在uCOS_II.h文件中增加宏定义用于表示任务时间片被用完这种状态：
#define OS_STAT_TS_USEUP 0x40
2．2 相关函数的修改
对OS_TCBInit()、OSTimeTick()、OSTimeDly()、OS_EventTaskWait()、OS_EventTaskRdy()这五个函数的修改是在µC/OS-II基础上实现时间片调度法的关键，下面将一一对这几个函数的修改部分进行说明。
在初始化任务控制块的函数OS_TCBInit()中，笔者添加以下代码让新创建的任务处于时间片就绪表中，并根据任务优先级对任务的时间片大小进行初始化。
if(prio < OS_STAT_PRIO) /*统计任务和空闲任务不加入时间片调度表*/
{
OSTSSGrp |= ptcb->OSTCBBitY;
OSTSSTbl[ptcb->OSTCBY] |= ptcb->OSTCBBitX;
ptcb->OSTCBTimeSlice = 64-prio; /*这里可以根据实际需要来计算时间片的大小*/
ptcb->OSTCBCounter = 64-prio;
}
else
{
ptcb->OSTCBTimeSlice = 0;
ptcb->OSTCBCounter = 0;
}
OSTimeTick()函数在每个时钟滴答被调用，在时间片调度过程中起到了递减时间片计数器的作用，当计数器为0时进行任务切换或是重新给各个任务分配时间片并开始新一轮调度。具体代码如下：
void OSTimeTick (void)
{
……
if (OSRunning == TRUE) {
ptcb = OSTCBList;
while (ptcb->OSTCBPrio != OS_IDLE_PRIO) {
OS_ENTER_CRITICAL();
if (ptcb->OSTCBDly != 0) {
if (--ptcb->OSTCBDly == 0) { /*任务延时的时间到*/
……
#if OS_TASK_TIME_SLICE_EN > 0
/*把该任务加入时间片调度表中*/
OSTSSGrp |= ptcb->OSTCBBitY;
OSTSSTbl[ptcb->OSTCBY] |= ptcb->OSTCBBitX;
#endif
}
……
}
}
……
}
#if OS_TASK_TIME_SLICE_EN > 0
if(OSTCBCur->OSTCBCounter != 0)
{
if(--OSTCBCur->OSTCBCounter == 0) /*任务时间片用完*/
{
OSTCBCur->OSTCBStat |= OS_STAT_TS_USEUP; /*把任务状态置为时间片用完态*/
/*把当前任务从任务就绪表中清除*/
if((OSRdyTbl[OSTCBCur->OSTCBY] &= (~OSTCBCur->OSTCBBitX)) == 0x00)
{
OSRdyGrp &= (~OSTCBCur->OSTCBBitY);
}
/*找出此时处于就绪态的最高优先级任务*/
y = OSUnMapTbl[OSRdyGrp];
x = OSUnMapTbl[OSRdyTbl[y]];
prio = (y<<3)+x;
/*如果就绪任务只剩下统计任务和空闲任务，说明这一轮调度结束，准备下一轮调度*/
if(prio >= OS_STAT_PRIO)
{
/*把就绪任务从时间片调度表恢复到任务就绪表*/
OSRdyGrp |= OSTSSGrp;
for(i=0; i<OS_RDY_TBL_SIZE; i++)
{
OSRdyTbl[i] |= OSTSSTbl[i];
}
/*遍历任务链表，重新为任务分配时间片*/
ptcb = OSTCBList;
while(ptcb->OSTCBPrio != OS_IDLE_PRIO)
{
if((ptcb->OSTCBStat & OS_STAT_TS_USEUP) == OS_STAT_TS_USEUP)
{
ptcb->OSTCBStat &= (~OS_STAT_TS_USEUP);
ptcb->OSTCBCounter = ptcb->OSTCBTimeSlice;
}
ptcb = ptcb->OSTCBNext;
}
}
}
}
#endif
}
}
OSTimeDly()函数的作用是将任务延时一定的时间，这种情况下应该把该任务从时间片调度表中清除，相关代码如下：
void OSTimeDly (INT16U ticks)
{
……
if (ticks > 0) {
OS_ENTER_CRITICAL();
if ((OSRdyTbl[OSTCBCur->OSTCBY] &= ~OSTCBCur->OSTCBBitX) == 0) {
OSRdyGrp &= ~OSTCBCur->OSTCBBitY;
}
OSTCBCur->OSTCBDly = ticks;
#if OS_TASK_TIME_SLICE_EN > 0
/*将当前任务从时间片调度表中清除*/
if ((OSTSSTbl[OSTCBCur->OSTCBY] &= ~OSTCBCur->OSTCBBitX) == 0) {
OSTSSGrp &= ~OSTCBCur->OSTCBBitY;
}
/*根据任务延时的时间来调整任务剩余计数值*/
if((ticks+OSTCBCur->OSTCBCounter) >= (OSTCBCur->OSTCBTimeSlice))
{
OSTCBCur->OSTCBCounter = OSTCBCur->OSTCBTimeSlice;
}
else
{
OSTCBCur->OSTCBCounter = OSTCBCur->OSTCBCounter + ticks;
}
y = OSUnMapTbl[OSRdyGrp];
x = OSUnMapTbl[OSRdyTbl[y]];
prio = (y<<3)+x;
if(prio >= OS_STAT_PRIO) /*除了统计任务和空闲任务，就绪表中再没其他任务了*/
{
/*根据时间片调度表OSTSSGrp 和OSTSSTbl来恢复任务就绪表OSRdyGrp 及OSRdyTbl */
OSRdyGrp |= OSTSSGrp;
for(i=0; i<OS_RDY_TBL_SIZE; i++)
{
OSRdyTbl[i] |= OSTSSTbl[i];
}
ptcb = OSTCBList;
while(ptcb->OSTCBPrio != OS_IDLE_PRIO)
{
/*给处于时间片用完态的任务重新分配时间片，并把时间片用完标志清除*/
if((ptcb->OSTCBStat & OS_STAT_TS_USEUP) == OS_STAT_TS_USEUP)
{
ptcb->OSTCBStat &= (~OS_STAT_TS_USEUP);
ptcb->OSTCBCounter = ptcb->OSTCBTimeSlice; /*重新分配时间片*/
}
ptcb = ptcb->OSTCBNext;
}
}
#endif
OS_EXIT_CRITICAL();
OS_Sched();
}
}
当某个任务须等待一个事件的发生时，信号量、互斥型信号量、邮箱及消息队列会通过相应的PEND函数调用函数OS_EventTaskWait()，使当前任务从就绪任务表中脱离就绪态，此时还需把当前任务从时间片调度表中清除，笔者在OS_EventTaskWait()函数中添加以下代码：
if((OSTSSTbl[OSTCBCur->OSTCBY] &= (~OSTCBCur->OSTCBBitX)) == 0x00)
{
OSTSSGrp &= (~OSTCBCur->OSTCBBitY);
}
OSTCBCur->OSTCBCounter = OSTCBCur->OSTCBTimeSlice; /*重新给该任务分配时间片*/
相应地，当某个事件发生了，信号量、互斥型信号量、邮箱及消息队列会通过相应的POST函数调用OS_EventTaskRdy()，从等待任务队列中使最高优先级任务脱离等待状态，此时还需要把该任务添加到时间片调度表中，笔者在OS_EventTaskRdy()函数中添加以下代码：
OSTSSGrp |= bity;
OSTSSTbl[y] |= bitx;
3．应用实例
笔者首先把µC/OS-II移植到开发板上（MCU是意法半导体生产的基于ARM7TDMI核的STR730[3]），然后如2小节所述对相关部分的源代码进行修改，接下来将优先级调度法和基于µC/OS-II的时间片调度法进行比较。为此我们分别建立了2个任务Task_TimeConsuming()、Task_Audio()，任务的优先级分别是5、6。
void Task_TimeConsuming(void *pdata)
{
……
while(1)
{
__asm {nop};
}
}
void Task_Audio(void *pdata)
{
……
while(1)
{
AudioProcess();
}
}
由于模拟的耗时任务Task_TimeConsuming()是个死循环且没有调用OSTimeDly()函数，其优先级又比Task_Audio()高，如果完全按照优先级调度，系统不会有声音输出，因为负责声音控制的任务Task_Audio一直得不到运行。而如果按照时间片调度（在os_cfg.h中增加#define OS_TASK_TIME_SLICE_EN 1），则声音输出正常，通过仿真器在Task_Audio()中设置断点，程序会很快停止在断点处。进一步地，我们依次在Task_TimeConsuming()和Task_Audio()函数体中设置断点，分别记录两次PC指针停止在断点处时看门狗计数器的值WDG_Counter1和WDG_Counter2，我们可以利用WDG_Counter1和WDG_Counter2的差值估算出任务Task_Audio前后两次被调度的时间间隔（忽略任务在切换过程中的耗时），经过多次计算，这个时间间隔值的范围在58～59ms之间，而任务Task_TimeConsuming的时间片理论值＝64－Prio=64－5=59ms，实验值与理论值是非常吻合的。
当然，这只是简单的验证实验。严格的测试还需要兼顾信号量、互斥型信号量、邮箱及消息队列相应的PEND、POST函数以及OSTimeDly()函数调用，鉴于篇幅关系，在这里就不再赘述了。
结语
笔者已经成功地把这种基于µC/OS-II的时间片调度法运用到车载信息娱乐系统的开发中，实践证明对于含有耗时任务的系统，尤其是在需要严格控制耗时任务运行时间长度的场合，该调度算法会给实际的开发工作带来一定的便捷性，同时也保证了系统的实时响应。而且整个算法只改动了µC/OS-II中的少量代码，我们还可以根据实际需要调整各个任务的时间片大小，体现出了算法的实用性与灵活性。