μC／OS- III对任务调度的改进

黄土琛，宫辉，邵贝贝

（1.清华大学 工程物理系，北京100084；2.清华大学 粒子技术与辐射成像教育部重点实验室）

引 言

μC／OS是一个基于优先级调度的可剥夺型实时多任务内核。在一个可剥夺型的实时内核中，最高优先级的任务一旦处于就绪状态，就会立即抢占正在运行的低优先级任务的运行权。在μC／OS－II中，任务调度是完全基于优先级的，不同的任务被赋予不同的优先级。V2.80以前的版本中，μC／OS－II最多支持64级优先级，在 V2.80后的版本里增加到了256级。优先级的数目决定了最多可支持的任务数目，当然还要除去一些内核占用的优先级。而在μC／OS－III中，内核支持任意数目的优先级，由用户根据实际需求来配置。更为重要的是，μC／OS－III增加了对时间片轮转调度算法的支持，也就是说，允许不同的任务使用同一个优先级。这样，任务的数量就可以不受优先级数目的限制了。本文将介绍μC／OS－III在优先级查找算法上的改进，以及时间片轮转调度算法的实现。

1 μC／OS -II最高就绪优先级的查找算法

本文以 V2.80以前的版本为例，简单回顾μC／OS－II中查找就绪的最高优先级算法的实现。以64级优先级为例，如图1所示，内核通过一个8×8的位映射表OSRdyTbl［］来记录任务的就绪状态。为了加快查表过程，又将64级优先级分为8组，用一个8位的整型OSRdyGrp来记录每一组的就绪状态。如果任务处于就绪态，其在位映射表OSRdyTbl［］中对应的位就会被置1。只要一组中有任务处于就绪态，则OSRdyGrp中对应的位就会被置1。OSRdyGrp和OSRdyTbl［］合起来又叫“就绪表”。因此，查找就绪的最高优先级任务分两步：首先在OSRdyGrp中查找就绪的最高优先级所在的组；然后在OSRdyTbl［］里查找其在该组中的位置，便可得到具体的优先级编号。

图1 μC／OS- II的就绪表

OSRdyTbl［］中的元素，从低位LSB到高位 MSB对应的优先级编号是递增的，也就是说，优先级的级别是逐渐降低的。因此，两次的查找过程，本质都是要得到一个8位无符号数的最低非零位。这个算法在μC／OS－II中是巧妙地通过一个“掩码表”OSUnMapTbl［］来实现的。OSUnMapTbl［］有256个元素，将8位的无符号数作为索引查找OSUnMapTbl［］，便得到该数最低非零位的位置，关于该表的具体内容可查阅μC／OS－II的源代码。利用事先计算好的一张表，通过查表操作来替代计算过程，这是典型的通过增加代码量来换取速度的思想（增加的代码量仅为256字节）。在获得就绪的最高优先级编号后，通过就绪任务列表OSTCBPrioTbl［］就可以得到相应的任务控制块指针了，整个过程的关键代码示意如下：

在V2.80以后的版本中，支持的优先级数目增加到256，此时8×8的位映射表OSRdyTbl［］会被扩展到16×16，OSRdyGrp也增加到16位，但“掩码表”OSUnMapTbl［］仍然没有变，因为保存一张216个元素的表是不实际的。因此，对于16位的无符号数的最低非零位的查找过程分两步：先查低8位，如果没找到再查高8位。

2 μC／OS- III最高就绪优先级查找算法的改进

随着32位微控制器的广泛普及，尤其是ARM的Cortex－M系列的推广，微控制器的价格越来越低廉，性能却越来越高。μC／OS－III也特别针对一些新的微控制器的特性进行了代码优化。在μC／OS－III里，就绪表包括两部分：就绪优先级位映射表OSPrioTbl［］，用来标明哪个优先级下有任务就绪；就绪任务列表OSRdyList［］，包含指向各个就绪任务的指针。OSPrioTbl［］元素的位宽取决于数据类型CPU＿DATA（在cpu.h里定义），由用户根据所使用的处理器来确定，如32位的处理器CPU＿DATA定义为32位整型。

μC／OS－III允许的不同优先级数目由用户根据需求来配置（os＿cfg.h中的宏OS＿CFG＿PRIO＿MAX）。如果某一优先级下有任务就绪，那么在就绪优先级位映射表OSPrioTbl［］中，该优先级对应的位就会被置1。图2以CPU＿DATA为32位整型为例，展示了 OSPrioTbl［］的结构。

由图2可看出，和μC／OS－II不同的是，优先级是按左到右的顺序编号，并且随着位映射表索引的递增，优先级编号也增加（优先级级别降低）。之所以采用这样的顺序，是为了便于使用一种特殊的硬件指令——计算前导零数目（Count Leading Zeros，CLZ），如今很多处理器都支持该指令或类似指令。该指令和μC／OS－II中查找掩码表的作用本质是一样的，但该硬件指令可以大大地提高查找最高优先级的速度。

当要查找包含就绪任务的最高优先级时，程序会逐项扫描就绪优先级位映射表OSPrioTbl［］，直到遇到第一个非零项为止。一旦找到第一个非零项，再加上该项的前导零数目，就可以得到所需的优先级，见下述代码。计算前导零数目函数CPU＿CntLeadZeros（）是一个与CPU相关的函数，前面提到，现在很多CPU都有专门的硬件指令，可以充分利用该指令来加速计算过程。如果CPU没有类似指令，那这部分功能就只能由普通的C代码来实现。

图2 CPU＿DATA声明为32位时OSPrioTbl［］的结构

逐项地扫描位映射表OSPrioTbl［］好像不是很高效。然而，当优先级的级数比较少时，这个查找过程还是相当快的。比如说，对于很多应用，32级优先级已经能满足要求，这时如果使用支持硬件CLZ指令的32位微控制器，只需一条汇编指令就能完成查找过程。即使优先级数目增加到64级（这已经可以满足绝大多数系统的需求了），上述过程也可以进行流水线优化，仅需多加一条IF语句就可以。请注意，在μC／OS－III里，任务数量不再限制于优先级数目，因为μC／OS－III允许任意数量的任务运行在同一个优先级（优先级0和 OS＿CFG＿PRIO＿MAX－1除外）。

因为μC／OS－III允许多个任务运行在同一个优先级，因此就绪任务列表（数组OSRdyList［］）也进行了改动，比之前稍微复杂了一些，这将在下一节提到。

3 μC／OS- III时间片轮转调度的细节

和μC／OS－II相比，μC／OS－III在调度方面一个大的改进就是增加了对时间片轮转调度的支持。所谓时间片轮转调度，就是两个或更多的任务拥有相同的优先级时，一个任务运行一段指定的时间（即时间片），然后轮到下一个任务。如果一个任务不需要执行完其时间片，也可以主动放弃CPU的控制权而让下一个任务运行。μC／OS－III允许用户为不同的任务指定不同的时间片长度（任务的时间片长度是在任务建立时指定的，在运行时也可以改变），并且可以在运行时使能或者禁止时间片轮转调度。

在μC／OS－III中，一个优先级下允许存在多个任务，因此就绪任务列表OSRdyList［］也变得复杂了，其元素不再是简单地指向一个任务，而是构成一个双向链表，链接对应优先级下所有就绪的任务，如图3所示。图中，优先级“prio”下有两个就绪任务，其任务控制块OS＿TCB构成一个双向链表，HeadPtr指向链表头部，TailPtr指向链表尾部，Entries域用来记录该优先级下就绪的任务数目。最高优先级0和最低优先级OS＿CFG＿PRIO＿MAX－1供内核使用，用户任务不能使用这两个优先级。

图3 μC／OS- III的就绪任务列表示意图

μC／OS－III的任务调度过程和μC／OS－II类似，找到就绪的最高优先级后，用优先级号作为索引，查找就绪任务列表OSRdyList［］，从对应的双向链表头部（即OSRdyList［hightest priority］.HeadPtr）便可获得最高优先级任务的控制块指针。如果该指针和当前运行任务的控制块指针不一致，则表明需要进行任务切换。也就是说，当获得就绪的最高优先级后，μC／OS－III调度的总是其对应的双向链表头部的任务，与该优先级下存在多少任务无关。换句话说，一个优先级下存在多个任务，这对调度过程来说似乎是“透明”的。

既然μC／OS－III每次调度的都是双向链表头部的任务，那么同一优先级下的多个任务又是如何实现轮转调度的呢？这个细节的实现由函数OS＿SchedRoundRobin（）来完成。该函数在每次时钟节拍到来时，由OSTimeTick（）（direct post模式）或 OS＿IntQTask（）（deferred post模式）调用。OS＿SchedRoundRobin（）函数的伪代码如下：

OS＿SchedRoundRobin（）首先检查时间片轮转调度是否使能，然后将当前任务时间片计数器减1。如果时间片计数器已减到零，OS＿SchedRoundRobin（）就会检查当前优先级下是否还有其他就绪任务。如果有，并且调度器也没被上锁的话，会将当前任务的控制块OS＿TCB从双向链表的头部移到尾部，而之前处于双向链表第二个位置的任务将会移到头部位置，成为下一个运行的任务。在退出时钟节拍中断时会进行任务调度，假设没有其他更高优先级的任务就绪，这时μC／OS－III依然会检查到当前优先级对应的双向链表头部位置的任务已发生变化，因此会进行任务切换，这就实现了同一优先级下多个任务的轮转调度。

值得注意的是，在建立任务时，如果在指定的优先级下已经存在其他任务，μC／OS－III会把新建的任务插入到对应优先级所指向的双向链表的尾部。而当一个任务转入就绪态时，如果和当前正在运行的任务是在同一优先级下，则转入就绪态的任务将会被插入到双向链表的尾部；如果转入就绪态的任务和当前正在运行的任务的优先级不一样，则转入就绪态的任务将会被插入到双向链表的头部。

结 语

μC／OS－III在基于优先级的抢占式调度算法基础上，增加了对时间片轮转调度算法的支持，从而允许多个任务运行在同一优先级。μC／OS－III允许用户为不同的任务指定不同的时间片大小，而且在运行时还可以动态改变，也可以在运行时使能或禁止时间片轮转调度，从而给用户提供了很大的灵活性。同时，对查找就绪的最高优先级任务的算法也进行了改进，充分利用特殊的硬件指令，极大地提高了查找的速度。

［1］Jean J Labrosse.μC／OS－II源码公开的实时嵌入式操作系统［M］.邵贝贝，等译.北京：中国电力出版社，2001.

［2］Jean J Labrosse.嵌入式实时操作系统μC／OS－II［M］.邵贝贝，等译.2版.北京：北京航空航天出版社，2003.

［3］Jean J Labrosse.μC／OS－III the Real Time Kernel for the Freescale Kinetis［EB／OL］.［2012－07－25］.http：／／micrium.com／page／downloads／os－iii＿projects.

［4］邵贝贝.浅谈μC／OS任务调度算法的硬件实现［J］.单片机与嵌入式系统应用，2010（9）：5－7.

［5］龚光华，车惠军.μC／OS优先级调度机制在PowerPC上的优化［J］.单片机与嵌入式系统应用，2010（10）：9－11.