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

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

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

  μC/OSII是源码公开的嵌入式实时操作系统,其任务调度算法的实现颇为精彩。本文对该算法做了简要分析,指出对于一些有硬件算法指令的处理器,仅做移植并直接使用其软件算法是不明智的,相关硬件指令为μC/OSII的优化开辟了广阔的空间。

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

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

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

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

  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/OSII在多处使用了上述调度算法。典型地,在事件控制块ECB中有:

  INT8UOSEventTbl[OS_EVENT_TBL_SIZE];

  INT8UOSEventGrp;

  这里,OS_EVENT_TBL_SIZE 的默认值为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,用来以空间换时间,加快优先级查找速度:

  INT8UOSTCBX;/*=priority & 0x07;*/

  INT8UOSTCBY;/*=priority >> 3;*/

  INT8UOSTCBBitX;/*=OSMapTbl[priority & 0x07];*/

  INT8UOSTCBBitY;/*=OSMapTbl[priority >> 3];*/

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

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

发表评论

0条评论,0人参与

请输入评论内容...

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

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

暂无评论

暂无评论

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

粤公网安备 44030502002758号