嵌入式实时操作系统的调度策略

嵌入式实时操作系统的调度策略

第２２卷第４期华东交通大学学报Ｖ０１．２２Ｎｏ．４

２００５年０８月

Ｊ埘ｌｍａｌｏｆＥａｓｔＣ１１ｉｍＪｉａｏｔｏｎｇＵ“ＶｅＩＳｉｔｙ

Ａｕｇ．，２００５

文章编号：１００５一ｃ１５２３（２００５）０４—０１１０一０３

嵌入式实时操作系统的调度策略

周

洁，李正凡

（华东交通大学信息工程学院，江西南昌３３００１３）

态以及动态调度算法，并总结了各自的优缺点．在此基础之上，对嵌入式实时内核∥０ｓ一Ⅱ的调度算法进行了优化．

文献标识码：Ａ

运行时，实时操作系统需要保存它的运行现场信

言

息、插入相应的队列、并依据一定的调度算法重新选择一个任务使之投入运行．调度算法实际上就是嵌人式系统与通用计算机系统不同，应用程序系统所采取的调度策略．大多数实时内核都采用基于优先级的调度算法．本文主要讨论与ＣＰＵ相关的调度原理和算法，并给出了一种在优先级个数有限的情况下优先级分配的有效方法．

１静态调度

静态调度是在系统开始运行前进行调度的，严格的静态调度在系统运行时无法对任务进行重新调度．静态调度的目标是把任务分配到各个处理机，并对每一处理机给出所要运行任务的静态运行顺序．静态调度算法实现简单，调度的额外开销小，调度是指在有限的处理单元上对具有某些已在系统超载时可预测性好．但也具有很大的局限性，例如资源利用率低、受系统支持的优先级个数限制以及灵活性和自适应性差等．下面介绍两种常见的静态调度算法．

１．１速率单调调度（ＲａｔｅＭｏｎｏｔｏＩｌｉｃＳｃｌｌｅｄｌｌＩｊｎｇ）

ＲＭｓ算法将最高优先级赋予最高执行频率的任务，以单调的顺序对剩余的任务分配优先级．由于采用抢占式的调度方式，高优先级的任务就绪后

收稿日期：２００４—１２一１８

作者简介：周洁（１９７９一），女，江西南昌人，华东交通大学助教，在读研究生

万　

方数据摘要：在资源有限的嵌入式系统中，任务调度器的好坏很大程度上决定了系统的性能．本文分析了实时系统中有代表性的静

关键词：嵌入式实时操作系统；多任务优先级；调度中图分类号：ｎＢ９２．３

Ｏ引

可以没有操作系统而直接在芯片上运行，但是为了合理地调度多任务、利用系统资源，系统一般以成

熟的实时操作系统（Ｒ哟ｓ）作为开发平台．实时操作

系统的首要任务是调动一切可利用的资源完成实时控制任务，其次才着眼于提高计算机系统的工作效率．实时并非指“快速”，实时的含义是在规定的时间内能够传递正确地结果．实时系统按严格的时间限制，可划分为硬实时和软实时系统．前者如果在不满足响应时限，响应不及时或者反应过早的情况下会造成灾难性的后果，而后者只会导致系统性能的退化．

知特征的任务集执行顺序的设计．在多任务嵌入式系统中，单纯通过提高处理器速度无法保证对重要性各不相同的任务进行合理地调度．这种任务调度只能由优化编写的系统软件来完成．在设计和实现嵌入式实时软件过程中，抢占多任务是一个普遍使用的结构，然而抢占多任务带来的代价包括ＣＰＵ带宽的浪费以及增加的内存总开销．当一个任务退出

嵌入式实时操作系统的调度策略

第４期

周洁，等：嵌入式实时操作系统的调度策略

立即抢占正在运行的任务．ｕｕ和脚ｌａＩｌｄ的理论证

们当前对最终期限的要求而定．当前请求的最终期明了下列公式，即用ＲＭｓ调度的独立的周期性任务限最近的任务具有最高的优先级，而请求最终期限总能满足其截止时间的要求．

最远的任务被分配最低优先级．这个算法能够保证Ｃｌ／Ｔｌ＋Ｃ２／Ｔ２＋…＋Ｃｉ／Ｔｉ＋…＋Ｃ。／Ｔｎ≤Ｕ（ｎ）

在出现某个任务的最终期限不能满足之前，不存在＝ｎ（２“一１）

处理器的空闲时间【２Ｊ．该算法基于以下假设：

式中：Ｃ；为任务ｉ的最坏执行时间；Ｔｉ为任务ｉ１）任何任务不存在不可抢占的部分，且抢占的的周期．

代价可以忽略；

ＲＭＳ算法的优点是开销小，灵活性好，可调度２）只有处理器请求是有意义的，内存、Ｌ／０和性测试简单．在任务的截至时间等于其周期的条件其它资源请求可以忽略；

下，速率单调算法已被证明是静态最优的调度算

３）所有的任务都是无关的，不存在先后次序的法【ｌ｜．

约束；

１．２

截止时间单调调度（ＤＩ组ｄｌｉｎｅＭｏ肿ｔ０Ｉｌｉｃ

４）任务的相对最终期限与它的周期相等．ｓｃＩｌｅｄｌＩｌｉｎｇ）

因此抢占式ＥＤＦ调度算法对于给定周期性任ＤＭＳ是在速率单调调度的基础上发展起来的．务集可调度性的充分必要条件为：

不同的是任务的优先级按截止时间来分配．截止时间短的任务优先级高，截止时间长的任务优先级∑皇≤ｌ

ｉ－１

ｐｉ

低．

其中，ｅｉ，ｐｉ分别为任务集中任务ｉ（１ｓｉ＜ｎ）的截止时间调度具有与速率单调算法相同的优执行时间和周期．由此可知，抢占式ＥＤＦ调度算法点．但ＤＭＳ算法放松了对任务的周期必须等于其截最大的优势在于，对于任何给定的任务集，只要处止时间的限制．在任务的截止时间小于或等于其周理器的利用率不超过１００％，就能够保证它的可调期的情况下，ＤＭｓ已被证明是静态最优的调度算

度性．ＥＤＦ算法在系统的负载相对较低时非常有法．

效．但在系统负载较重时，系统性能急剧下降，引起大量任务错过截止期，甚至可能导致ｃＰＵ时间大量２动态调度

花费在调度上，在这时系统的性能还不如ｎＦｏ

（Ｆｉｒｓｔｈ

Ｆｉｒｓｔ

Ｏｕｔ）方法．

在嵌入式实时系统中动态调度依赖于任务的２．２最小松弛时间算法（ｋａＳｔ

ＳｌａｃｋＴｉｍｅＦｉ：ｒｓｔ）

优先级．优先级可以静态分配或者依据不同的特征ＬＳＦ算法计算任务的松弛时间，其中松弛时间参数，如截止时间、空闲时间或关键性（即任务的重为任务截止时间与剩余执行时间之差．该算法在任要程度或者价值）等进行动态分配．动态调度可以意时刻把最高优先级分配给具有最小松弛时间的是抢占式的或非抢占式的．前者用优化的标准动态任务，以此来保证紧急任务的优先执行．然而，由于调动任务，从而减少因超过截止时问而失败的任务等待任务的松弛时间是严格递减的，其等待执行的数，后者检查系统中每一个任务，看是否有新任务缓急程度也随时间越来越紧迫，因此在系统执行过可以加入调度列表，从而满足其截止时间的要求．程中，等待任务随时可能会抢占当前执行的任务．非抢占式内核的优点是易于分析、实现，利于保存ＬＳＦ算法造成任务之间的频繁切换或称为颠簸

额外的上下文切换，节省抢占式内核中由于采用互（ｔｌｌ幽ｉｎｇ）现象较为严重．颠簸现象增大了系统开

斥机制带来的开销，其缺点是可能使某些任务不能销，并限制了巧Ｆ算法的应用．

满足其截止时间的要求。几个比较著名的商用嵌入式实时操作系统，如ＱＮ）（、ｖＸｗｏｒｋｓ提供的都是“抢３静态和动态调度算法的选择

占式任务调度”．以下介绍的是两个著名的动态调度算法ＥＤＦ和ＬＳＦ．

嵌入式实时系统中资源是非常有限的，所以开２．１

最早截止时间优先算法（Ｅａ棚俗ｔ砌ｄｌｉＩＩｅ

销要尽可能小．开销主要包括运行开销和调度开ｎｒｓｔ）

销．运行开销与队列分析和从调度队列中增加、删抢占式ＥＤＦ调度算法是一个动态优先级驱动除任务相关．每个任务在一个调度周期内至少被阻的调度算法，其中分配给每个任务的优先级根据它

塞和唤醒一次，所以任务调度器在一个周期内不得

万　

方数据

嵌入式实时操作系统的调度策略

１１２

华东交通大学学报

２００５年

不对一个任务进行两次选择．静态调度对时间触发系统的设计很适合，但它必需事先进行设计，综合考虑选择众多参数，通常需要过大范围地设计以能够处理最不可能的事件．动态调度适合设计事件触发的系统，在执行期间能够动态做出决定，并且它在资源利用方面比静态调度有更大的潜力．结合上面提及的几个著名算法进行分析、比较．如ＲＭＳ算法，它根据任务的执行频率设置优先级，有较小的运行开销，但执行频率最高的任务不一定是最重要的．而像ＥＤＦ和ＬＳＦ这样的动态调度策略需要较高的调度开销来在运行时对操作进行评估．因为抢占发生时，运行上下文的保存和恢复及相应的中断等额外开销大于任务正常结束，启动另一个任务的额外开销．此外，动态调度策略在调度量过大时对那些错过最终期限的操作不提供有效控制手段．当一个操作被加入调度队列以获得更高利用率时，所有操作的实时安全性就降低了．因此对所有操作来说，当系统过载时，操作错过截止期的几率增加了．通过上述分析，不难看出无论采用何种调度策略，都是各有优点和弊端的．

４对实时内核∥仍一Ⅱ任务调度算法的改

进

肚ｃ／０ｓ—ＩＩ是目前流行的一个开源免费的实时

内核．肿／０ｓ—ＩＩ２．６２可以管理６４个任务，保留了其

中８个给系统，所以应用程序最多可以有５６个任务．并且赋予每个任务的优先级必须是不相同的［３｜．这样的限制虽然简化了任务管理系统，但也给大型应用带来了很大的不便．通过上文对静态和动态调度策略的分析、比较，可以结合ＲＭｓ算法具有较小运行开销和ＥＤＦ算法具有较小调度开销的特点，得到一个改进的优先级分配算法，即在多个任务要求调度时，选择截止时间最短（即优先级最高）的任务运行；若任务优先级相同，则选择运行频率最高的任务运行．从而突破原系统对任务数量的限制，并且去除对每个任务必须有不同优先级的要求．

算法改进的关键之处是对优先级相同的任务建立散列表．在散列表中按照任务执行频率进行降序排列，这样就能保证该优先级散列表中的第一个任务就是在此优先级上执行频率最高的任务．任务

万　

方数据管理系统调用接口包括任务创建、任务删除、更改任务优先级、挂起任务、恢复任务、与任务堆栈操作相关的系统接口和其他一些接口函数等．本文只简要说明改进后任务创建和任务调度的算法，伪码如

下．

０‰ｋＣｒｅａｔｅ

｛分配给任务的优先级合法性检查；建立任务控制块；

建立任务堆栈０ｓＩｋｋｓｔｋＩＩｌｉｔ（）；ｉ“在该优先级上已有任务存在）｛比较任务的执行频率；

将该ＴＣＢ插入到散列表中（降序）；｝ｅＩｓｅ／／该任务是散列表中的第一个任务｛插入到已用任务控制块链表ＯｓＩ℃Ｂｕｓｔ中；｝｝

ＯＳＳｃｈｅｄ

｛ｉｆ（（ＯＳｋⅢｅｓｔｉｎｇ

ｏＳｈｌｔＮｅｓｔｉｎｇ）＝＝Ｏ）

查找就绪状态下优先级最高的任务；ｉｆ（此优先级＞当前运行任务的优先级）ｉｆ（此优先级任务数＞１）

｛在该优先级散列表中查找执行频率最高的任

务；

任务切换；

｝ｅｌｓｅ｛任务切换；｝／／该优先级上只有一个任

务

｝

５结束语

通过对实时系统中的静态以及动态调度算法进行分析、比较，以嵌入式实时内核肚／０ｓ一Ⅱ为例，结合砌腮算法具有较小运行开销和ＥＤＦ算法具有较小调度开销的特点，对肛／０ｓ—ＩＩ的任务调度策略进行了改进，是对嵌入式系统调度问题的一次有益探索．当然，改进的调度算法将实际的操作环境作了简化，只考虑了周期性任务组成的实时系统，在一定程度上限制了他们在工程实际中的应用．将非周期性的任务也加以全面考虑，是本文下一步的研

究工作．

（下转第１３３页）

嵌入式实时操作系统的调度策略

第４期姜志玲：简易智能电动车的设计

１３３

ＳｉＩｎｐｌｅ№ｌｌｉｇｅｎｔ珊删【Ｉｍｅｌｅｃｔｄｃａｌ

Ｃａｒ

ＪＩＡＮＧ蹦－ｌｉｌｌｇ

（Ｓｃ｝啪ｌ

０ｆⅡｅｃｔｒｉｃａＩ

ａ１１ｄ丑ｅｃ嘶五ｃＥＩｌ百ｎｅｅｒｉｌｌｇ，Ｅａｓｔ

ＣＩｌｉｍＪｉａｏｔｏＩｌｇＵｎｉｖｅ墙ｉｔ）ｒ，ＮａｎｃＩｍｇ

３３００１３，Ｃｌｌｉ衄）

Ａｂｓ白隐ｃｔ：，Ｉｈｅ

ｄｅｓｉ驴ｅｄｃａｒ，ｗｈｉｃｈｉｓｃｏｎｔＩＤｌｌｅｄ

ｂｙ

１６也ｉｔＭＣＵ—ＳＰＣＥ０６１ＡｕＩｌｄｅｒｃ０Ⅱｌｂｉｎｉｌｌｇｔｈｅｉ而ａｍｄｓｅｎＳｏｒ，ｒａｙ

Ｓｅｎｓｏｒ，ｍｅｔａｌｄｅｔｅｃｔｏｒ，ｐｈｏｔｏｅｌｅｃｔｒｉｃｓ埘ｔｃｈ，ｑｕｉｃｋｌｙｓ稍ｔｃｈＳｅｎｓｏｒ，ｉｓ

ａ

ｋｉｎｄｏｆｉｎｔｅｌｌｉｇｅｎｔｃａｒ．Ｔｈｅｎｌａｉｎｃｏｎｔｒｏｌｓｙｓ—

ｔ锄，ｗｈｉｃｈ

ｃｈ００Ｓｅｓｌｉｎ夥ａｎｇ’ｓ

ｏｆｏｒｄｙｏｐｅｍｔｅｓ

ｑｕｉｃｋｌｙ，ｂｕｔ幽ｈａｓｆｕｎｃｔｉｏｎｓ

ｓｕｃｈ

ａｓ

ｓｉＩｌｌｐｌｅ

ｃｏ曲ｇｕｍｔｉ锄，ｅｌｅｃ咖ｔｏｒ’ｓ

ｓｉ蟛ｅｃｈｉｐ

１６．ｂｉｔｓＰｃＥ０６１Ａ

ａｓ

ＣＰＵ，ｎｏｔｅｘａｃｔ

ｃｏｎｔｒｏｌ，ｓｔｅａｄｉｌｙ

ａｄ啪ｃｅ，ＳｏＬｕｌｄ

ｒｅａｌｐｌａｙ．

ＫＩｅｙ

ｗ０删ｓ：ｉｎｔｅｌｌｉｇｅｎｔ

ｃａｒ；ＳＰＣＥ０６ｌＡ；ｓｅｎｓｏｒ

孚眵尊够孚蚌乎蚌宇蚌亭蜉乎辨净哆净蚌淖哆孚啦淖蜉孚够水哆淖啦乎曲社韭孚韭串韭蹲蜉守韭守牡母蟑净哆孚眵淳哆辩９乎蛐孚哆净蜱社眵孚蜱守蜉净韭班哆净Ｂ守韭乎牡孚蛆乎蚌鹕，乎驻孚蟑守鲈社蜉孚蚌淖哆

（上接第１１２页）参考文献：

［２］硒ｉｓｈｍｃＭ，ｓＩｌｉｎＧＫ。Ｒｅ小ＴｉＩｎｅＳｙｓｔｅｍ［Ｍ］．ｃ０１１Ｉｍｂｌｌｓ，

［１】Ⅱｕ

ｃＬ，ＬａｙＬａｎｄ

Ｊｗ．Ｓｃｈｅｄｕｌｉｎｇ

ａ１９０甜１ＩＩＩ

ｆｏｒ

ｍｕｌ邱ＩＤ一

０Ｈ：ＭｃＧｍｗ．咖Ｃ０ｍｐ枷ｅｓ，Ｉｎｃ．１９９７．

舒蛐蚵ｎｇ

ｉｎ

ａ

ｌ瑚ｄ

ｒｅａｌ．石ｎｌｅ

ｅｎｖｉ删１ｎ瑚ｔ［Ｊ］．Ｊｏｕｎｌａｌ

０ｆ出ｅ

［３］ＪｅａｎＪ．蹦珊雠．ｐＣ／０Ｓ＿ＩＩｎｅＲｅ小ＴｉＩＩｌｅＫｅｍｅｌ［Ｍ］．北

ＡＣＭ，１９ｒ７３，２０（１）：４０一６１．

京：北京航空航天大学出版社，２００３．

Ｓｃｈｅｄｕｌｉｎｇ

Ｓｔｒａｔｅ科ｏｆＥｍｂｅｄｄｅｄ盈蝴－ｔｉｍｅｏｐｅｒａｔｉｏｎ

ｓｙｓｔ咖

（Ｓｃｈｏｏｌ０ｆ砌＾０珊鲥ｏｎＥｎ西ｎｅｅｒｉｒＩｇ，ＥａｓｔＣ硒１ａＪｉａｏｔ０甥Ｕ证ｖｅｒｓｉｔ）ｒ，№ｎｃｈａｌｌｇ３３００１３，Ｃｌｌｉ腿）

Ａｂｓ臼ｍｃｔ：‰ｋ

ｓｃｈｅｄｕｌｅｒ

ｌａｒ铲ｌｙｄｅｔｅｍｌｉｎｅｐｅｒｆｏ跏锄ｃｅ０ｆｔｈｅｅｍｂｅｄｄｅｄｓｙｓｔｅｍ谢ｔ１１Ｉｉｒｌｌｉｔｅｄｒｅｓｏｕｒｃｅｓ．７ｎｌｉｓｐ印ｅｒａｎａｌ—

ｙｓｅｓｔ），ｐｉｃａｌｓ诅ｔｉｃｓｃｈｅｄｕｌｉｎｇａ１９０ｄｔｈ璐ａｎｄ

ｄｙｎａＩｌｌｉｃｐａｐｅｒ

ｔｈｅ池ｄｄｅｄ

ｓｃｈｅｄｕｌｉｎｇａ１９０ｒｉｔｈｌｍ，锄ｄ

ｓ呦商ｚｅｓ

ｔｈｅｉｒｍｅｒｉｔｓａｎｄｆａｕｌｔｓ．Ｔｈｉｓ

ａｌｓｏ叩ｔｉＩＴｌｉｚｅｓ

ｓｃｈｅｄｕｌｉｎｇ

ａｌ鲥ｔ１１ｍ

ｏｆ

ｒｅａｌ—ｔｉｍｅｋｅｍｅｌ弘ｃ／０Ｓ－ＩＩｂａｓｅｄ

０ｎ

ｔｈｅｓｅ．

№ｒｗｏｒｄｓ：ｅｍｂｅｄｄｅｄ

ｒｅａｌ—ｔｉⅡｌｅｏｐｅｒａｔｉｏｎｓｙｓｔｅｍ；ＩｎｕｌｔｉｔａＳｋ；ｐｒｉｏｒｉｔ）ｒ；ｓｃｈｅｄｕｌｉｎｇ

万　

方数据