APP下载

浅谈μC/OS任务调度算法的硬件实现

2010-06-22邵贝贝

单片机与嵌入式系统应用 2010年9期
关键词:任务调度位数字节

邵贝贝

(清华大学 工程物理系,北京100084)

μC/OS是由美国嵌入式系统专家Jean J.Labrosse先生为嵌入式实时操作系统(RTOS)写的实时内核,最早连载在美国的《嵌入式系统编程》杂志1992年5月和6月刊上,源码发布在该杂志的BBS上。该实时内核最初是为Motorola的8位单片机MC68HC11写的,为便于普及,在后来关于μC/OS和μC/OS-ⅠⅠ的3本著作中[1-3],该内核提供的是PC上的源码。μC/OS-ⅠⅠ比μC/OS增加了很多功能,在任务调度算法上并无不同,故本文提及任务调度算法时不再区分μC/OS和μC/OS-ⅠⅠ。

一项对我国嵌入式应用工程师的统计表明[4],各类嵌入式应用工程师正在研究和使用的操作系统中,Linux占38%,μC/OS-ⅠⅠ 占 34%,WinCE 占 16%,VxWorks 占5%。这里,Linux加μC/OS-ⅠⅠ就超过了70%,这两个操作系统对中国嵌入式应用领域的影响可见一斑。它们的共同特点是源码公开。Linux不是实时的,也不是为嵌入式系统专门设计的,而μC/OS-ⅠⅠ是专门为嵌入式应用设计的实时操作系统。将μC/OS-ⅠⅠ嵌入到产品中用于牟利是要对使用权付费的,国内一些信誉好的企业购买μC/OS-ⅠⅠ使用权的例子很多,而一些不大重视信誉和知识产权的企业也不在少数。

μC/OS-ⅠⅠ用于教学与研究是免费的。近些年来,我国各类大学的嵌入式系统教学中纷纷采用μC/OS-ⅠⅠ作为教材。而μC/OS-ⅠⅠ也被移植到几乎所有的CPU上。各类杂志上发表的相关论文也数目可观,虽然大部分论文只谈到移植。

μC/OS-ⅠⅠ是为8位CPU写的RTOS小内核,任务调度算法巧妙,移植到任何处理器上都很好用。而对于一些有RTOS优先级算法硬件指令的16/32/64位的处理器,照搬 μC/OS-ⅠⅠ的8位算法、强行移植 μC/OS-ⅠⅠ未必恰当。

1 μC/OS的调度算法

μC/OS采用优先级至上的任务调度原则:“让进入就绪态任务中优先级最高的那个任务,一进入就绪态立刻就能立即运行”。这种基于优先级的任务调度原则,在嵌入式实时系统中最常用。μC/OS实现了一种巧妙的查表算法,利用这种算法能快速实现上述任务调度原则。这种查表算法的大致思路是,用8字节数组中的64位作为就绪任务表,每一位表示一个任务的状态,该位为1表示任务就绪,0为非就绪态。64位中第一个字节的b0位代表64个任务中优先级最高的任务,最后一个字节的b7位代表优先级最低的空闲任务。通过2次查用一张常数数组表,迅速找出任务就绪表中就绪态任务中优先级最高的那个。常数表中,按照0~7表示的8种不同权重,以一定规律排列128个0、64个1、32个2、16个3,8个4、4个5、2个6和1个7,再补上1个0后,共256字节。查表法避免了逐位检测各优先级位引起的执行时间的不确定性,程序简单,执行速度快,且时间是固定的,与就绪任务多少无关,与任务优先级无关。这是μC/OS任务调度的核心算法。在处理信号量、邮箱、消息队列等事件时,为了查找等待事件发生的任务列表中优先级最高的那个任务,也采用同样的算法,查的是同一张常数数组表。

μC/OS最初是为 Motorola的增强型8位处理器MC68HC11写的,算法精彩,将其移植到其他8位、16位处理器,这种8位机算法无懈可击。除任务就绪表外,μC/OS-ⅠⅠ在多处使用了上述调度算法。典型地,在事件控制块ECB中有:

这里,OS_EVENT_TBL_SⅠZE 的默认值为8,即以8个8位数的数组表示最多64个不同优先级的任务;OSEventGrp是OSEventTbl的索引字节,这就是μC/OS算法中著名的8+1个字节数据结构。当OSEventTbl中的某一个字节不为0时(表示该字节代表的8个任务中至少有1个在等待事件发生),OSEventGrp中的相应位置1。首先以OSEventGrp的值做偏移量,查那张256字节的常数表,获得1个0到7的数Y,作为优先级高3位,再根据Y的值,找出OSEventTbl中8个字节中最先出现的那个不为零的字节;然后再次查那张表,得到1个0到7的数X,找出字节中最靠近b0的那一位,作为优先级低3位的值,通过将Y左移3位再加上X的值,得到等待事件发生任务中优先级最高的那个任务的优先级。

在每个任务的任务控制块TCB中有下列定义,可以看出,任务优先级被拆分成两个8进制数X和Y,用来以空间换时间,加快优先级查找速度:

以上是μC/OS任务调度算法的简要介绍,Jean J.Laborosse先生最先用这种算法实现了RTOS中基于优先级的调度策略,是μC/OS任务调度算法的精华与核心技术。

2 优先级算法指令

对于32位和64位处理器,特别是一些精简指令流类型的处理器,其内部有可直接用于RTOS优先级算法的硬件指令。以PowerPC处理器[5]为例,予以说明。这里顺便解释一下,PowerPC是ⅠBM、Motorola和Apple三家公司于90年代初期联合设计的32位处理器,90年代后期出现增强型32位处理器,大量用于嵌入式系统,特别是汽车、通信等行业。本世纪初期,还出现了64位的处理器。在64位PowerPC处理器指令中,有2条可供RTOS算法使用的指令:

上述指令也可简称为CLZ指令。设某通用源寄存器RS中有一个64位数,b0是高位,b63是低位,执行cntlzd指令后,在目标寄存器RD中返回源寄存器RS中64位数的前导零的数目。返回0表示b0不为0,即该64位数没有前导0;返回n表示bn不为0,bn位的前面n位(b0~bn-1)共有n个零;返回64表示RS寄存器中所有位都为0。

如果用一个64位数表示64个任务的优先级,从b0开始到b63,b0为最高优先级,b63表示最低优先级,使用cntlzd指令,可迅速找出优先级最高的那个任务。RⅠSC类型的处理器,执行1条指令一般只需要1个CPU时钟周期。执行该指令,仅一个CPU时钟周期就可完成对64个不同优先级任务的判选。在这类处理器上直接移植和套用μC/OS-ⅠⅠ软件算法,显然不合理。

对于32位的PowerPC,也有汇编指令cntlzw。数出一个32位数前置零的数目。指令执行后,RD中返回指定源寄存器RS中32位数的前置零的数目,返回0表示b0不为0,即没有前导0,返回32表示寄存器RS中所有的位都为0。这一条指令可从32个任务中迅速找出优先级最高的那个任务。若使用2个32位数表示64个不同任务的优先级,则下面是使用该指令实现μC/OS-ⅠⅠ算法的示意性代码。

这样,很少几条指令,就完成了μC/OS中需要查表来完成的算法,不仅速度快,还省去了程序中256字节的那张常数表。上述实现方法并非唯一的,还可进一步优化。对于增强型32位PowerPC[6],还有一条指令可对2个地址连续的32位数做并行操作,同时数出前导零的数目。此时若低32位不为0,则最高优先级者被立即找出;若为0,则取高32位中的优先级再加32即可。

其他32位机,如MⅠPS的处理器,也有同类指令。一些处理器还有与上述指令对称的“数出前置1的数目”指令。总之,在有类似CLZ指令的处理器上,直接移植和使用μC/OS-ⅠⅠ的任务调度算法并不合理。移植后需要摒弃μC/OS-ⅠⅠ中的软件算法,代之以硬件指令算法指令,实现RTOS任务调度算法的优化。

早期的ARM系列处理器并不支持CLZ指令,但从ARM Cortex开始,或者说ARM v5及以后的ARM类CPU,如Cortex-A8、Cortex-M3等,开始支持 CLZ指令。因此对于Cortex单片机,也没有必要套用μC/OS算法,这类处理器可运行μC/OS-ⅠⅠⅠ[7]。μC/OS-ⅠⅠⅠ是在μC/OS-ⅠⅠ的基础上发展起来的商业产品,目前还只能在ST的ARM Cortex 32位微控制器上实现。Cortex有RTOS硬件算法指令,不再需要使用μC/OS的查表算法。μC/OS-ⅠⅠⅠ还增加了同优先级任务的时间片轮转调度法等很多新功能,已经是一个全新的RTOS商业产品了,不再是μC/OS-ⅠⅠ的升级版。由于目前μC/OS-ⅠⅠⅠ产品单一且源码不再开放,以及价格方面等原因,我们还无法预见其未来。因此,深入研究和讨论μC/OS-ⅠⅠ的移植和优化是很有意义的。

除了上面提到的几种处理器,还有一些16位处理器也支持CLZ这样的RTOS运算指令。在这类处理器上强行移植和直接使用μC/OS-ⅠⅠ也会有弄巧成拙的感觉。

以16位的MC9S12XE系列和XF系列单片机为例,片内有2个CPU,一个是传统的CⅠSC类型的CPU S12,另外一个是名为XGate的RⅠSC类型CPU,XGate中有一条类似指令BFFO(Bit Field Find First One)指令格式为:

意为找出第一个1,和数出前导零的数目其实是一回事。目标寄存器RD中得到源寄存器RS中16位数的第一个1的位置,如果RS中为全零,则C标志置位。在XGate处理器上,特别是使用v2内核的处理器,可以利用BFFO指令优化μC/OS-ⅠⅠ任务调度算法。且对于μC/OS-ⅠⅠ的改进并不限于用BFFO指令替代查表算法,还可以尝试将RTOS和其管理的任务分别加载到2个CPU上。内核和任务调度在RⅠSC类型的XGate上运行,被管理的任务放到CⅠSC类型的S12处理器上运行;XGate v1CPU虽然有BFFO指令,由于中断无法嵌套,无法完整地运行XGate,但至少可以将XGate-ⅠⅠ中的时钟节拍函数放到XGate上运行[8]。具有硬件优先级算法指令的处理器,以及多内核单片机,为μC/OS-ⅠⅠ的改进和性能优化开拓了丰富的想象空间。在决定移植和使用μC/OS-ⅠⅠ之前,应该仔细研究一下拟用处理器的指令集,切莫盲目移植了事。

3 移植和优化中还应思考的问题

因为越来越多的RⅠSC类型处理器有了能用于RTOS任务调度算法的硬件指令,μC/OS-ⅠⅠ调度算法可以用硬件指令迅速完成,而不必依赖原来的软件查表算法,大大简化了程序,提高了运算速度。但由于RⅠSC类型的处理器,没有直接对存储器操作的指令,所有操作都只能通过CPU内部寄存器完成,不能如同8位处理器那样直接对存储器做位操作,这类RⅠSC类型处理器中有很多内部寄存器,可以设一些寄存器变量类型的指针来操作。如何用好寄存器变量,是要仔细研究的。

RⅠSC类型的CPU一般没有让存储器的某一位置位或把存储器的某一位清零的指令。往往需要先读存储器到CPU寄存器,再使用“与”、“或”等指令让寄存器某一位复位或置位,再写回到存储器。这一连串的操作可能需要保护,防止其间被中断。可以想象,若移植μC/OS-ⅠⅠ,在填写任务就绪表的时候,操作并不简单,要考虑全面,避免任何疏漏和隐患。另外还有编译器方面的问题。我们看到,上述讨论中涉及了不少汇编指令,如同cntlz,在C语言中是无法直接表达的,编译器对这样的汇编指令能支持到什么程度,是用户要细心研究的。现在,越来越聪明的编译器能将我们写的C程序按照执行速度或代码长度等用户定义的条件进行优化,能优化到什么程度?什么条件下能把类似cntlz这样的指令优化进去?这些都是要研究的。

对于中高端的处理器,一般都有系统态模式和用户态模式(有的CPU称之为保护模式),过去看到的很多移植文章都对此不予理会,让CPU完全工作在系统态。如果让RTOS内核工作在系统态,任务工作在用户态,有助于提高系统安全性。这类讨论也是过去那些关于μC/OS-ⅠⅠ移植的文章中极少见到的。

4 小 结

μC/OS-ⅠⅠ是在中国嵌入式系统应用中很有影响力的RTOS内核,已经被移植到几乎所有能想到的处理器上。其技术亮点体现在优先级调度算法上。由于当初是为8位处理器写的,对于8位处理器和多数16位处理器,运行μC/OS-ⅠⅠ是很不错的选择。处理器硬件技术的不断发展,为RTOS任务调度算法的实现方法开拓了广阔的想像空间。一些原来需要软件实现的算法可以硬件化。典型地,对于32/64位和部分高端16位处理器,有可用于RTOS优先级算法的硬件指令,例如文中提到的Power-PC、MⅠPS、ARM Cortex和 XGate等,直接移植μC/OS-ⅠⅠ代码,套用其调度算法实际上很不合理。使用CLZ或BFFO等硬件指令替代μC/OS-ⅠⅠ中的软件算法,可大大简化μC/OS-ⅠⅠ代码并优化RTOS性能。本文提到的方法也决非唯一。技术在发展,对于μC/OS-ⅠⅠ,千万不要移植了事,尽管已经讨论了十来年,仍然需要静下心来学习并做些深入细致的研究,希望今后能够看到更多深入探讨μC/OS-ⅠⅠ优化的文章。

[1]Labrosse Jean J.μC/OS The real Time Kernel[M].R&D Publication,1992.

[2]Labrosse Jean J.μC/OS-ⅠⅠ The real Time Kernel[M].R&D Publication,1999.

[3]Labrosse Jean J.μC/OS-ⅠⅠ The real Time Kernel[M].2nd E-dition.R&D Publication,2002.

[4]《电子产品世界》编辑部.2008年度嵌入式应用调查报告[J].电子产品世界,2009,16(1).

[5]Freescale.e200z6PowerPC Core Reference Manual,2004.

[6]ⅠBM.Book E:Enhanced PowerPC Architecture,2002.

[7]Labrosse Jean J.μC/OS-ⅠⅠⅠ The real Time Kernel[M].Micrium Press,2009.

[8]邵贝贝,等.嵌入式系统中的双核技术[M].北京航空航天大学出版社,2008.

猜你喜欢

任务调度位数字节
No.8 字节跳动将推出独立出口电商APP
五次完全幂的少位数三进制展开
连续自然数及其乘积的位数分析
No.10 “字节跳动手机”要来了?
基于改进NSGA-Ⅱ算法的协同制造任务调度研究
基于时间负载均衡蚁群算法的云任务调度优化
简谈MC7字节码
云计算环境中任务调度策略
云计算中基于进化算法的任务调度策略
遥感卫星CCD相机量化位数的选择