μC/OS—Ⅱ混合调度算法的硬件实现

李岩+王简+迟欢欢+崔浩鑫

摘要：针对μC/OS-Ⅱ过于单一的调度算法引起的应用局限性，提出一种混合调度算法。在原有的基于优先级的抢占式调度算法基础上，扩展了同级调度。对于具有同一优先级的多任务的任务组，按照用户设定的优先级阈值进行划分，优先级高于该阈值为实时任务组，否则为非实时任务组。同级实时任务组采用较公平的时间片轮转算法，同级非实时任务组采用开销较少的先来先服务算法。算法基于FPGA实现，由VHDL描述，通过ISE 10.1仿真，仿真结果表明，硬件任务调度器保证了调度的正确性。提高了系统的实时性。

关键词：实时操作系统；调度算法；硬件任务调度器

DOI：10.15938/j.jhust.2016.03.008

中图分类号：TP316.2 文献标志码：A 文章编号：1007—2683（2016）03—0039—04

0引言

随着大规模集成电路技术的发展，嵌入式系统的软、硬件界限越来越模糊，理论上任何操作指令既可以由软件实现，也可以由硬件实现。而且硬件逻辑在执行过程中可以与处理器并行，相较于纯软件实现的实时操作系统，可以极大的发挥系统的并行特性，使系统的处理效率提高到6～50倍。因此实时操作系统的硬件化在嵌入式领域拥有广阔的发展空间。

μC/OS-Ⅱ是一个基于优先级的抢占式实时内核，不支持同级调度，对任务实时性也没有划分。但实际应用有时却需要同级调度，如同等地位的多点信息采集，而且没有必要对非实时任务采用实时任务的调度算法。另外，仅依靠算法改进已无法显著的提高RTOS的实时性。文章针对以上问题，在μC/OS-Ⅱ原有算法的基础上扩展了同级调度。通过原内核的调度算法选出优先级最高的就绪同级任务组。对同级实时任务组内的任务采用时间片轮转算法，对同级非实时任务组内的任务采用先来先服务算法。并实现基于该算法的硬件任务调度器，降低系统开销低，提高系统实时性。

1硬件任务调度器的设计原理

1.1算法的设计

操作系统的任务调度算法多种多样，但是每种调度算法都有自己的应用局限性，比如短任务优先算法可能产生长任务“饥饿”的现象，混合调度算法虽然不是完美的调度策略，但是将几种调度算法的特性适当的折中，优点尽量突出，缺点尽量回避，就可以满足具体应用场合的需求。针对～C/OS—n原有的单一调度算法的应用局限性，提出一种混合调度算法。

算法启用μC/OS-Ⅱ内核预留的任务标识符OSTCBId作为任务的唯一标识，使得一个优先级对应一个任务组，该任务组由4个OSTCBId不同的同级任务组成。算法分为两级调度。通过查找μC/OS-Ⅱ的就绪表和优先级判定表，第一级调度选择出优先级最高的就绪的同级任务组，第二级调度对上面的同级任务组进行组内任务的调度。

第二级调度需要用户事先设定一个优先级阈值。若同级任务组的优先级小于该阈值，则该任务组为实时的，否则为非实时的。对于实时任务组内的任务采用较公平的时间片轮转算法，但是频繁的任务切换必然增加系统开销。先来先服务算法是时间片轮转算法的退化算法，不利于短任务，但是非实时任务可接受较长的响应时间，所以对非实时任务组内的任务采用先来先服务算法，从而减少任务切换带来的不必要开销。

1.2调度器的数据结构

在μC/OS-Ⅱ中，每个任务都需要一个任务控制块TCB来管理。调度器通过一组FPGA片内寄存器实现TCB队列。TCB的参数包括任务标识符OS-TCBId、任务状态OSTCBStat、等待时间OSTCBWait、栈顶指针OSTCBStkPtr、栈底指针OSTCBStkBottom、事件控制块指针OSTCBEventPtr。该数据结构保留了部分μC/OS-Ⅱ的TCB参数，最重要的修改是增加等待时间OSTCBWait，其初值为0，随时钟节拍不断增加，被执行后清零。

第一级调度的核心数据结构是就绪表和优先级判定表。就绪表由2个变量OSRdyTbl[]和OSRdyG～组成，基于FPGA片内寄存器实现。优先级判定表OSUnMapTbl[]由FPGA片内RAM实现。第二级调度的核心数据结构是优先级阈值Prio-Threshold，基于FPGA片内寄存器实现。

2硬件任务调度器的电路实现

2.1调度器的整体设计

调度器支持64个优先级，每个优先级最多支持4个同级任务，以任务状态为触发信号，输出下一个要执行的任务标识符。调度器的整体设计如图1所示。

在第一级调度中，将所有同级任务组的优先级状态PrioStat都输入到就绪表的内部变量OSRdyTbl[]和OSRdyGrp中，再将这两个变量输入给任务组调度电路，从而得到最高的就绪组优先级Prio。

在第二级调度中，以第一级调度的输出结果Prio为选择条件，选择一个同级任务组输入给同级任务调度电路，电路内部根据优先级阈值Prio-Threshold选择适当的调度算法，从而得到该任务组中的下一个要执行的任务标识符Cur_Id，即调度器的最终输出结果。

2.2任务组调度电路的实现

任务组调度电路需要两个时钟周期的执行时间，通过查找就绪表和优先级判定表得到优先级最高的就绪任务组。任务组调度电路如图2所示。

第1个时钟周期，计数器为1，选择器将OSRdyGrp输入译码器，转换成RAM中相应地址，读取OSUnMapTbl[]的数据，由分配器更新优先级高三位Y。

第2个时钟周期，计数器为0，以y为选择条件，将OSRdyTbl[]中相应元素输入选择器，再输入译码器，转换成RAM中相应地址，读取OSUnMapT-bl[]的数据，由分配器更新优先级低三位X。然后运算器完成（Y<<3）+X，输出最高就绪任务组优先级Prio。

2.3同级任务调度电路的实现

同级任务调度提供两种可选的策略。若任务组调度电路的输出Prio小于优先级阈值Prio_Thresh-old，则该任务组为实时的，通过RR电路实现组内任务的时间片轮转算法，否则为非实时的，通过FCFS电路实现组内任务的先来先服务算法。同级任务调度电路如图3所示。

RR电路主要实现时间片轮转算法，在同级任务组中从第一个就绪的任务开始，依次循环的给每个就绪任务分配一个时间片的处理器时间。FCPS电路主要实现先来先服务算法，在同级任务组中根据就绪任务的任务等待时间OSTCBWait，选择出等待时间最长的就绪任务，使之优先运行，以此类推。

State是任务组状态寄存器。若State=1010，则组内1号和3号任务就绪。Current是当前任务寄存器，有且只有一位为1。若Current=0010，则正在执行的任务是3号任务。Nell和Next2是下一个执行任务寄存器，有且只有一位为1。若Nextl=1000，则下一个执行的是1号任务。

若Prio

若Prio>=Prio—Threshold，则将State输入FCFS电路，电路比较全部就绪任务的OSTCBWmt，选出等待时间最长的任务，在Next2中将其对应的位置设为1，其他位置设为0.Sel设为Next2。

最后以Sel为选择条件，输出相应的任务编号Cur_Id。

3实验结果分析

为了验证算法硬件实现的正确性和高效性，整个设计基于FPGA实现，采用VHDL语言描述，通过ISE 10.1进行功能仿真，硬件调度器的功能仿真图如图4所示。

仿真结果分析如下：

1）在Ons时不妨设置优先级阈值prio_threshold为5。

2）在5ns时建立优先级为2的2号任务，由于只有一个就绪任务，输出的下一个要执行的任务标识符out_cur_taskid为2。

3）在10ns时建立优先级为1的1号任务，由于1号任务的优先级最高，out_cur_taskid为1。

4）在15ns、20ns、25ns、30ns时，依次建立优先级为3的3号任务和4号任务，以及优先级为6的6号任务和7号任务，由于1号任务的优先级最高，out_cur__taskid仍为1。

5）在40ns时将1号任务挂起，由于2号任务优先级在就绪任务中最高，out_cur_taskid为2。

6）在45ns时将2号任务挂起，同级且实时的3号任务和4号任务的优先级在就绪任务中最高，由out_cur_taskid可以看出，3号任务和4号任务基于时间片轮转执行。

7）在90ns时查询4号任务，由输出端口可以看到4号任务的参数。

8）在100ns和105ns时分别挂起3号任务和4号任务，同级且非实时的6号任务和7号任务的优先级在就绪任务中最高，系统采用先来先服务调度算法，由于6号任务先建立，故out_cur_taskid为6。

9）在115ns时删除6号任务，out_cur_taskid为7，符合先来先服务算法的预计结果。

10）在130ns时恢复2号任务，由于2号任务优先级高于7号任务，out_cur_taskid为2。

以上任务调度过程模拟了任务的创建、删除、挂起、恢复、查询涉及的调度情况，以及存在同级实时任务组和同级非实时任务组的调度情况，可以看出调度器实现了调度算法的预计功能。调度器消耗的的硬件资源如表1所示。

由以上分析可知，实验结果验证了硬件任务调度器的正确性和高效性，而且对于硬件资源的消耗也比较合理，符合了系统设计的需求。

4结论

文章提出的混合调度算法保留μC/OS-Ⅱ原有的基于优先级的抢占式调度算法，以保证系统的兼容性和实时性。在此基础上扩展了同级调度，对于同级实时任务组内的任务采用时间片轮转算法，实现同级调度的公平性；对于同级非实时任务组内的任务采用先来先服务算法，从而减少不必要的系统开销。算法在扩展同级调度的同时，尽可能减少功能改进产生的开销，并且基于FPGA实现，独立的硬件逻辑较充分的发挥了系统潜在的并行性和实时性。如果硬件任务调度器能与实时内核的其它部分有更深入的结合，那么调度芯片与处理器并行的模式必将成为未来嵌入式系统的一种发展趋势。