μc/Os-Ⅱ就绪表算法介绍与具体改动
eeskill 2021-10-22

μc/Os-Ⅱ的就绪表设置、清除、查找算法,是高效的、跨平台的程序。它使用了两个查找数组OSMapTbl[8]和OSUnMapTbl[256],以提高查找就绪表的速度,尽快获取就绪任务的最高优先级。

Cortex-M3是ARM公司较新的一种架构版本,主要应用在单片机领域。基于它生产的32位芯片日益增多;cortex-M3只支持Thumb-2指令集,在效能和代码密度间能取得更佳的表现。

1 在ARM上改动算法的因由利弊

由于就绪表操作是在关中断状态下运行的,其执行影响到系统的中断响应时间,因此就绪表操作算法的效率是衡量实时操作系统优劣的基准之一。

在Cortex-M3所用的指令集中,一些指令功能不可小觑,如前导零计数clz、字内位反转rbit、位清除bic。其中的clz和bic为μc/Os就绪表的高优先级获取算法指出了另一条道路。

(1)改动后的优势

①节省存储空间。不再使用查找数组OSMapTbl[8]和OSUnMapTbl[256]。设立这两个数组的目的,是为了提高查找就绪表的效率。

②提升查找效率。clz是单周期指令,使用带移位的加法指令,大幅缩短运算时间。

③增加了μc/Os-Ⅱ支持的任务数量,从64提升到了1 024(2.84版支持的任务数量已经到了256,不过效率有所下降)。

(2)存在的不足

①Realview MDK(这里使用的是3.20版及其指令模拟器)尚不支持在C语言程序中使用Thumb-2指令内联汇编。使用内嵌汇编函数时,函数的调用(跳转返回)降低了执行效率。

②C语言对clz指令的支持尚有不足,故新算法跨平台性差。但鉴于ARM芯片应用广泛,指令又被ARM9之后的芯片广泛兼容,所以应用空间还算广阔。

2 μc/Os-Ⅱ就绪表算法介绍与具体改动

μc/Os-Ⅱ就绪表是一个数组,数组元素一位的值(1或0)对应了一个任务就绪与否,该位在数组中的位置表示任务的优先级。当需要调度已就绪的最高优先级任务运行时,就在就绪表中查找该任务。

2.1 μc/Os-Ⅱ就绪表算法简介

一种解决方法是,对数组各项依次判断是否为0:若>O,进入该项查找最小权的置1位位置;若=0,优先级加一个基数,查下一项,直至查到该优先级。

μc/Os-Ⅱ技高一筹,设置了一个对就绪表各项判断是否为0的变量,称之为就绪表组。就绪表组一位为0或1,对应就绪表一项的值是否为0。通过查找就绪表组最小权位的置1位位置,就确定了对应首个>0的就绪表项的下标,从而避免了循环,大幅度提高了效率。

2.2改动方式与源码

clz算法接受了μc/Os-Ⅱ的思路,再通过使用clz指令来进行优化。不同的是,clz是从右往左查,二进制的高权位对应高优先级,而μc/Os-Ⅱ优先级以值小为高。

考虑到有时用不到很多任务,这时用数组作就绪表不免浪费。因此当任务总数小于32时,就用32位无符号整数变量作就绪表。注意,此时就绪表组变量OSRdyGrp被当作就绪表使用。

常量OS_LES_TSK表示是否使用较小任务数,0表示使用最多32个任务,1表示使用最多1 024个任务。

常量RdySt是将32位整数的最高权位置1,以便移位使用。

2.3 C语言实现

以下算法利用内嵌clz指令的函数编写,实现了指定优先级任务在就绪表的设置、清除,在就绪表中查找就绪任务的最高优先级。

程序中的bx r14,有些资料上要求必须写,不过查看反汇编代码,编译程序已经给加上了。看来是编译程序已升级,会不会出错要看使用的编译器,建议还是按规范写上。由于内嵌函数调用返回耗时,查找算法未能充分发挥,需改进编译后的汇编代码以实现更高的效率,或使用汇编代码重写这部分程序。

2.4 THUMB-2汇编指令实现

用汇编语言写程序时的技巧:在最高优先级任务的设置、清除函数中,C语言运算符“︱=”对等汇编指令“orr”,“&=~”对等汇编指令“bic。这两条指令都可以进行预移位操作,大幅提高执行效率。可以查看反汇编源码,看C编译器是否利用了这一便利。

在查找函数中,可以省去C语言程序中的内嵌汇编调用,减少冗余指令。示意伪代码如下:

ldr rO, =OsRdyGrp;加载就绪表组变量OSRdyGrp地址

可以看出,除了数据加载指令外,查找的核心算法仅3条指令(使用<32个任务时,仅1条指令)。不过在实际设计算法的时候,还需要考虑指令流水线停顿,方能达到最佳的效果。

2.5 μC/OS-Ⅱ2.84版相关源码介绍

以下是翻译整理后的μC/OS-Ⅱ优先级查找算法源码(2.84版),较长的注释是添加的算法说明。

clz最高优先级查找算法,与μC/OS-Ⅱ的新算法有所不同:返回的结果分别是8位、16位整数。这是因为8位已经不能表示>255的值;过程中clz算法更多地使用16或32位整数,以充分利用芯片性能。

3 适用范围

等待任务列表使用了与就绪表操作相似的过程,注意要同时更改其数据类型和算法。算法虽然是在Cortex—M3上执行的,但适用于ARM9及其以后芯片。支持ARM指令集的芯片,可以在C语言中使用内嵌汇编,不必再编写汇编查找函数。

本文所叙述的算法适用于下述两种情况。

①使用μC/OS-Ⅱ系统:

◆要求更多的任务优先级;

◆要求产品性能优越或是时间关键的应用,想进一

步提高效率;

◆学习、研究或希望优化μC/OS-Ⅱ以扩展其应用范围。

②未使用μC/OS-Ⅱ系统:

◆移植改造其他操作系统的就绪表算法;

◆编写新操作系统或执行调度程序;

◆编程爱好者借鉴、改进编程方法。

结 语

Cortex-M3推出时,笔者就认定它是单片机过渡到ARM的有力工具,其小存储量使得它更适合用小型实时系统。在学习μC/OS-Ⅱ的过程中,发现其就绪表操作算法经过改动或许更好,于是就做了本文所述的试验。

声明: 本文转载自其它媒体或授权刊载,目的在于信息传递,并不代表本站赞同其观点和对其真实性负责,如有新闻稿件和图片作品的内容、版权以及其它问题的,请联系我们及时删除。(联系我们,邮箱:evan.li@aspencore.com )
0
评论
热门推荐
  • 相关技术文库
  • C语言
  • 编程
  • 软件开发
  • 程序
  • 10种排序算法C语言展示

    以前也零零碎碎发过一些排序算法,但排版都不太好,又重新整理一次,排序算法是数据结构的重要部分,系统地学习很有必要。 排序算法 平均时间复杂度 最差时间复杂度 空间复杂度 数据对象稳定性 冒泡排序 O(n2) O(n2) O(1) 稳定 选择排序 O(n2) O(n2) O(1) 数

    05-11
  • 嵌入式驱动开发四个方向

    嵌入式大体分为以下四个方向: 一、嵌入式硬件开发:熟悉电路等知识,非常熟悉各种常用元器件,掌握模拟电路和数字电路设计的开发能力。熟练掌握嵌入式硬件知识,熟悉硬件开发模式和设计模式,熟悉ARM32位处理器嵌入式硬件平台开发、并具备产品开发经验。精通

    05-06
  • Python“常用”代码片段

    整理的一些“常用”代码片段,分享给大家。 1、冒泡排序 lis = [56,12,1,8,354,10,100,34,56,7,23,456,234,-58] def sortport(): for i in range(len(lis)-1): for j in range(len(lis)-1-i): if lis[j] > lis[j+1]: lis[j],lis[j+1] = lis[j+1],lis[j] retur

    05-06
  • 嵌入式术语中英文对照表

    ▎ A ASIC(专用集成电路) Application-Specific Integrated Circuit. A piece of custom-designed hardware in a chip. 专用集成电路。一个在一个芯片上定制设计的硬件。 address bus (地址总线) A set of electrical lines connected to the processor a

    05-07
  • C语言的十条杀手锏

    我们平常所说的执行效率就是使用相同的算法在相同输入条件下完成相同计算所产生的系统开销,目前来说一般会更多关注执行时间方面的开销。所有语言编写的代码最终要运行,都要转化成机器码。在更短的时间内完成相同的事那么效率就高。 下面说说如何提高C语言程

    04-30
  • Matlab用于二维图形绘制

    续上篇Matlab系列篇的二维图形,本篇将完成剩下二维图形部分篇章..... 交互式绘图 交互式绘图的意思就是可以使用鼠标对图形进行操作,具体的实现看待会的演示,首先了解几个会用到的函数:ginput、gtext和zoom,其中ginput只能用于二维图形绘制,另外两个还适

    04-28
  • 用Python 快速把物料编码快速匹配到BOM 里

    我们在处整理BOM时,有一件比较麻烦的工作,就是要从物料库里找到对应的元器件的物料编码并填入BOM中。我们通常的做法就是在物料库里每种物料逐一搜索,把对应的元器件的物料编码找出来,并填到BOM里。这种工作虽然没什么难度,但是如果BOM的元器件种类很多,

    04-21
  • 程序世界:线性代数是一种特定语言

    线性代数是什么? 在大学数学学科中,线性代数是最为抽象的一门课,从初等数学到线性代数的思维跨度比微积分和概率统计要大得多。很多人学过以后一直停留在知其然不知 其所以然的阶段,若干年之后接触图形编程或机器学习等领域才发现线性代数的应用无处不在,

    04-19
  • 一个故事讲什么是卷积

    引子 很多朋友和我一样,工科电子类专业,学了一堆信号方面的课,什么都没学懂,背了公式考了试,然后毕业了。 先说"卷积有什么用"这个问题。(有人抢答,"卷积"是为了学习"信号与系统"这门课的后续章节而存在的。我大吼一声,把他拖出去枪毙!) 讲一个故事:

    03-29
  • C语言函数为什么不能返回数组?

    C语言函数为什么不能返回数组? 在C语言程序开发中,我们不可以编写下面这样的代码: char f(void)[8] {char ret;// ...fill...return ret;}int main(int argc, char ** argv) {char obj_a[10]; obj_a = f();} 不可以编写这样的代码 这其实就是不能在C语言函

    03-15
  • 初学C语言,你的“行囊”需要准备什么呢?

    今天,我能够自称是一个混IT的人,并能以此谋生,将来大家能一次谋生,都要感谢两个人: 克劳德.香农和约翰.冯.诺依曼,是他们发现了所有的数字化信息,不论是一段程序,一封email,一部电影都是用一连串的1和0进行编码的; 是他们发现了我们可以利用一个预先

    03-15
  • 如何让ARM代码执行速度更快?

    通过一定的风格来编写C程序,可以帮助C编译器生成执行速度更快的ARM代码。下面就是一些与性能相关的关键点: 1.对局部变量、函数参数和返回值要使用signed和unsigned int类型。这样可以避免类型转换,而且可高效地使用ARM的32位数据操作指令。 2.最高效的循环

    03-12
下载排行榜
更多
广告
X
广告