首页 > 嵌入式软件 > Uc/os II

μ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.3C语言实现

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

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

2.4THUMB-2汇编指令实现

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

在查找函数中,可以省去C语言程序中的内嵌汇编调用,减少冗余指令。示意伪代码如下:
ldr rO,=OsRdyGrp;加载就绪表组变量OSRdyGrp地址

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

本文引用地址: http://embed.21ic.com/software/ucos/201806/62938.html

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-Ⅱ的过程中,发现其就绪表操作算法经过改动或许更好,于是就做了本文所述的试验。

换一批

延伸阅读

[疯狂史] 为什么电脑第一个磁盘永远是C盘?

为什么电脑第一个磁盘永远是C盘?

刚有个人电脑时,上就运行着著名的MS-Dos和windows系统,而第一个磁盘(系统盘)总是以C盘开始,但是为什么呢?......

关键字:电脑 磁盘 C盘

[趣科技] 让普通物体秒变智能!加州大学展示一款基于 WiFi的便携贴产品

让普通物体秒变智能!加州大学展示一款基于 WiFi的便携贴产品

“智能”联网设备可以让日常生活变得更加轻松,但它们通常需要搭配电池来使用。好消息是,加州大学圣迭戈分校的研究团队,刚刚展示了一款基于 WiFi、名叫 LiveTag 的解决方案。其采用低成本的标签打印方......

关键字:智能设备 WIFI

[真心话] 软件开源活动领航人Eric Raymond:C语言时代行将落幕

软件开源活动领航人Eric Raymond:C语言时代行将落幕

这几天来,我(Eric Raymond)在思考那些正在挑战C语言的系统编程语言领袖地位的新潮语言,尤其是Go和Rust。思考的过程中,我意识到了一个让我震惊的事实——我有着35年的C语言经验。每周我都要写很多C代码,但是我已经记不清楚上一次......

关键字:Eric Raymond C语言

[真心话] 电子工程师安身立命的八大看家本领,你学会了几个?

电子工程师安身立命的八大看家本领,你学会了几个?

作为一个电子工程师(electronic engineer)必备技能:抄板,焊板,画板,仿真,编程,调试,创意,坚持。八大技能,你几级了?......

关键字:电子工程师

[新鲜事] 阿根廷队告别俄罗斯世界杯,罗永浩:梅西巅峰期已过

阿根廷队告别俄罗斯世界杯,罗永浩:梅西巅峰期已过

6月30日晚,俄罗斯世界杯的赛场上上演16强焦点之战,阿根廷对法国。面对拥有身高、年龄、速度等优势,并坚持打高吊、防反的法国队,阿根廷队显得没有什么办法。虽然两次被幸运女神眷顾并一度以2:1领先,但法国队最......

关键字:阿根廷 世界杯

[真心话] 陈一舟发文忆人人网一路坎坷历程,回不到过去了...

陈一舟发文忆人人网一路坎坷历程,回不到过去了...

近日,一篇名为《13年后重新登陆人人网,你会看到你青春的截止日期》的文章刷屏,引起不少网友的回忆,有人突然发现,原来自己大学毕业后就再也没登录过人人网。2009年8月4日,校内网更名为人人网,成为大学生最活跃......

关键字:陈一舟 人人网
条评论

我 要 评 论

网友评论

大家都爱看

  • 扇出型晶圆级封装的优势和挑战!

    我们有能力创造一些能保持前代性能并且更好更小的电子设备,例如今天的可穿戴设备、智能手机或平板电脑,这是由于很多因素超过摩尔定律而快速发展,从而能够从底层的嵌入组件发展到今天把它们封…

    2018-03-29
  • Xilinx推出革命性的新型自适应计算产品

    自适应和智能计算的全球领先企业赛灵思公司(Xilinx, Inc.,(NASDAQ:XLNX)),近日宣布推出一款超越FPGA功能的突破性新型产品,名为ACAP(Adaptive Compute Acceleration Platform,自适应计算加速…

    2018-03-20
  • 赛普拉斯为树莓派3 B+ IoT单板计算机提供强大稳定的无

    先进嵌入式系统解决方案的领导者赛普拉斯(纳斯达克代码:CY)近日宣布其Wi-Fi&#174;和蓝牙&#174;combo解决方案为全新的树莓派 3 B+(Raspberry Pi 3Model B+)IoT单板计算机提供强大稳定的无线连接…

    2018-03-20
  • 观看直播领红包,SEED-A10加速卡助力人工智能

    随着云服务器、云计算的发展,大家对硬件加速的需求越来越多,但是随着设备功耗的上升、性能需求越来越高,常规加速设备以及开始不能满足需求,因此FPGA逐渐在硬件加速中找到了自己的位置,而艾…

    2018-03-19
  • 特朗普:博通不得以任何形式收购高通

    白宫周一(3月12日)晚发出声明,川普(特朗普)总统出于“国家安全”考量、禁止新加坡博通公司(Broadcom)收购美国高通公司(Qualcomm)。

    2018-03-14