侵权投诉
订阅
纠错
加入自媒体

μC/OS任务调度算法的硬件实现简要分析

2013-10-28 10:53
路过的码农
关注

  2  优先级算法指令

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

  cntlzd (Count Leading Zeros Double Word)

  cntlzw (Count Leading Zeros Word)

  上述指令也可简称为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指令,可迅速找出优先级最高的那个任务。RISC类型的处理器,执行1条指令一般只需要1个CPU时钟周期。执行该指令,仅一个CPU时钟周期就可完成对64个不同优先级任务的判选。在这类处理器上直接移植和套用μC/OSII软件算法,显然不合理。

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

  初始化:

  Prio = 0;

  让寄存器变量指向任务就绪表;

  找出最高优先级程序:

  读入优先级表的第1个32位数;

  不为零则直接使用CLZ指令;

  Prio = 32;

  读入优先级表的第2个32位数;

  CLZ指令:

  CNTLZW RD,RS;

  RD += Prio;/*最高优先级*/

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

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

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

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

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

  BFFORD,RS

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

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

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

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

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

  4  小结

  μC/OSII是在中国嵌入式系统应用中很有影响力的RTOS内核,已经被移植到几乎所有能想到的处理器上。其技术亮点体现在优先级调度算法上。由于当初是为8位处理器写的,对于8位处理器和多数16位处理器,运行μC/OSII是很不错的选择。处理器硬件技术的不断发展,为RTOS任务调度算法的实现方法开拓了广阔的想像空间。一些原来需要软件实现的算法可以硬件化。典型地,对于32/64位和部分高端16位处理器,有可用于RTOS优先级算法的硬件指令,例如文中提到的PowerPC、MIPS、ARM Cortex和XGate等,直接移植μC/OSII代码,套用其调度算法实际上很不合理。使用CLZ或BFFO等硬件指令替代μC/OSII中的软件算法,可大大简化μC/OSII代码并优化RTOS性能。

<上一页  1  2  
声明: 本文由入驻维科号的作者撰写,观点仅代表作者本人,不代表OFweek立场。如有侵权或其他问题,请联系举报。

发表评论

0条评论,0人参与

请输入评论内容...

请输入评论/评论长度6~500个字

您提交的评论过于频繁,请输入验证码继续

暂无评论

暂无评论

文章纠错
x
*文字标题:
*纠错内容:
联系邮箱:
*验 证 码:

粤公网安备 44030502002758号