如何设计一种优先级和时间片相结合的调度法？

　　引言
　　μC/OS-II嵌入式实时操作系统采用的是基于优先级的可剥夺调度法［1］。基于优先级的可剥夺调度法是指，CPU总是让处于就绪态的、优先级最高的任务运行；最高优先级的任务一旦就绪，总能得到CPU的使用权，当一个运行着的任务使一个比它优先级高的任务进入了就绪态时，当前任务的CPU使用权就被剥夺了，更高优先级的任务立刻得到了CPU的使用权。除非最高优先级的任务主动放弃CPU的使用权（通过调用OSTimeDly（）、 OSSemPend（）等函数），否则低优先级的任务是没机会获得CPU使用权的。对于一个实际应用系统中耗时比较长的任务，为了让其他任务能够得到实时调度，可以用两种方法来处理。第一种方法是把该任务的优先级设为最低（当然还是比空闲任务要高）；第二种方法就是让该耗时任务运行一段时间后延时一下再继续运行，即把整个任务划分为若干步骤来执行，如以下的示例代码：
　　
　　很多情况下，耗时长的任务并不能设置为最低优先级任务，而划分步骤来执行的方法不但繁琐而且每一步执行的时间也是不确定的（其他低优先级任务获得CPU使用权的时间也会是不确定的）。笔者在用μC/OSII开发一款车载信息娱乐系统的时候就碰到了这样的问题，因此设计了一种优先级和时间片相结合的调度法（也就是基于μC/OSII的时间片调度法）。
　　1 调度原理
　　这种调度法给处于就绪态的每一个任务都分配一个时间片（优先级越高分配的时间片越长，空闲任务得不到时间片的分配），内核按照任务的优先级依次调度处于就绪态的任务，即当就绪态中最高优先级的任务用完自己的时间片后，CPU控制权转让给就绪态中优先级第二高的任务。该任务用完自己的时间片后，CPU控制权又转让给下一优先级的就绪态任务……当就绪态的每一个任务都被调度一次之后将重新为它们分配时间片，然后又开始新一轮的调度……［2］
　　其中要注意的是，在调度过程中如果有一个比当前任务优先级更高的任务由其他态变成了就绪态（被创建或获取了一个信号量等），当前任务的CPU控制权将被剥夺；空闲任务仍然是等到其他任务都退出就绪态才获得CPU的使用权。
　　图1解释了该调度法的调度过程（其中任务1优先级最高，任务2次之，任务3最低）。
　　2.gif
　　图1 基于μC/OSII时间片调度过程
　　① 任务2和任务3都处于就绪态，任务1在等待一个信号量，优先级中的任务2获得CPU使用权。
　　② 任务2的时间片用完，优先级低的任务3获得CPU使用权。
　　③ 任务3的时间片用完，任务2重新获得CPU的使用权。
　　④ 任务2的时间片还没用完时中断来临，中断服务程序获得CPU使用权。
　　⑤ 中断服务程序发送了一个任务1等待的信号量，中断服务完成后优先级高的任务1获得CPU使用权。
　　⑥ 任务1的时间片用完，任务2继续运行。
　　⑦ 任务2的时间片用完，任务3获得CPU使用权。
　　⑧ 任务3的时间片用完，重新分配时间片，新一轮调度开始。
　　2 实现方法
　　在调度算法的实现过程中，力求做到3点：
　　① 尽可能少地改动μC/OSII原有的代码；
　　② 增加的代码在风格上保持与原有的相一致；
　　③ 兼容原有的优先级调度法（可以很方便地选择优先级调度法或是时间片调度法）。
　　注：对于该小节中出现的代码，如果是笔者增加的部分都用黑体表示。
　　2.1 数据结构中增加的变量
　　在进程控制块中增加两项：
　　Typedef struct os_tcb{
　　……
　　#if OS_TASK_TIME_SLICE_EN》0
　　/*条件编译，OS_TASK_TIME_SLICE_EN在os_cfg.h中定义，凡是涉及与时间片调度相关的代码都用条件编译。这样，可以通过更改配置文件很方便地选择任务调度法
　　*/INT16UOSTCBTimeSlice;
　　/*任务的时间片大小，在任务创建时被初始化，运行过程中保持不变*/
　　INT16UOSTCBCounter;
　　/*任务运行剩余时间计数器，每一轮调度开始时该变量被赋值（等于OSTCBTimeSlice），运行过程中不断递减。当其等于0时任务被剥夺CPU使用权*/
　　#endif
　　}
　　由于当前任务的时间片使用完时，该任务将被从就绪表OSRdyGrp以及OSRdyTbl［OS_RDY_TBL_SIZE］中清除；新一轮调度开始时它又必须被恢复，因此笔者在uCOS_II.h文件中增加以下变量（不妨把它们称为“时间片调度表”）分别用于保存OSRdyGrp和 OSRdyTbl［OS_RDY_TBL_SIZE］。
　　OS_EXT INT8UOSTSSGrp;
　　OS_EXT INT8UOSTSSTbl［OS_RDY_TBL_SIZE］;
　　另外，在uCOS_II.h文件中增加宏定义，用于表示任务时间片被用完这种状态：
　　#defineOS_STAT_TS_USEUP0x40
　　2.2 相关函数的修改
　　对OS_TCBInit（）、OSTimeTick（）、OSTimeDly（）、OS_EventTaskWait（）、 OS_EventTaskRdy（）这5个函数的修改，是在μC/OSII基础上实现时间片调度法的关键。下面将一一对这几个函数的修改部分进行说明。
　　在初始化任务控制块的函数OS_TCBInit（）中，笔者添加以下代码让新创建的任务处于时间片就绪表中，并根据任务优先级对任务的时间片大小进行初始化。
　　
　　OSTimeTick（）函数在每个时钟滴答被调用，在时间片调度过程中起到了递减时间片计数器的作用。当计数器为0时，进行任务切换或是重新给各个任务分配时间片并开始新一轮调度。
　　OSTimeDly（）函数的作用是将任务延时一定的时间。这种情况下，应该把该任务从时间片调度表中清除。
　　当某个任务须等待一个事件的发生时，信号量、互斥型信号量、邮箱及消息队列会通过相应的PEND函数调用函数 OS_EventTaskWait（），使当前任务从就绪任务表中脱离就绪态，此时还需把当前任务从时间片调度表中清除。笔者在 OS_EventTaskWait（）函数中添加了以下代码：
　　
　　相应地，当某个事件发生了，信号量、互斥型信号量、邮箱及消息队列会通过相应的POST函数调用OS_EventTaskRdy（），从等待任务队列中使最高优先级任务脱离等待状态，此时还需要把该任务添加到时间片调度表中。笔者在OS_EventTaskRdy（）函数中添加了以下代码：
　　OSTSSGrp |= bity;
　　OSTSSTbl［y］ |= bitx;
　　3 应用实例
　　笔者首先把μC/OSII移植到开发板上（MCU是意法半导体生产的基于ARM7TDMI核的STR730［3］），然后如2小节所述对相关部分的源代码进行修改，接下来将优先级调度法和基于μC/OSII的时间片调度法进行比较。为此分别建立了2个任务 Task_TimeConsuming（）、Task_Audio（），任务的优先级分别是5、6。
　　
　　由于模拟的耗时任务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=59 ms，实验值与理论值是非常吻合的。
　　当然，这只是简单的验证实验。严格的测试还需要兼顾信号量、互斥型信号量、邮箱及消息队列相应的PEND、POST函数以及 OSTimeDly（）函数调用。鉴于篇幅关系，这里就不再赘述了。
　　结语
　　笔者已经成功地把这种基于μC/OSII的时间片调度法运用到车载信息娱乐系统的开发中。实践证明，对于含有耗时任务的系统，尤其是在需要严格控制耗时任务运行时间长度的场合，该调度算法会有一定的便捷性，也能保证系统的实时响应，而且整个算法只改动了μC/OSII中的少量代码；还可以根据实际需要调整各个任务的时间片大小，体现出了算法的实用性与灵活性。