嵌入式操作系统实时调度算法研究

徐德

嵌入式操作系统实时调度算法研究

徐 德

（中国人民银行乌鲁木齐中心支行，新疆 乌鲁木齐 834002）

摘要： 在嵌入式操作系统中，实时调度算法性能的好坏直接对系统的实时性起着决定性的作用。因此，该文介绍实时调度和实时调度算法的概念，分析了目前常见的静态优先级调度算法和动态优先级调度算法的不同。

关键词： 嵌入式操作系统；实时性；调度算法

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2014）13-3177-02

1 实时调度与实时调度算法

多任务的系统必须担负起调度任务的责任，不断地进行切换进程，以使CPU获得最大的利用率。当有多个任务就绪时，操作系统必须决定先运行那一个，对CPU访问权限裁决的过程被称为调度（Scheduling）。本质上调度其实就是系统根据调度算法策略与资源控制协议的规则，为一组处于就绪状态的任务分配资源并选择符合系统要求的任务组成一个队列到处理机上去依次执行，并而在这一过程中要保证所有任务对时限的要求。假如实时系统若有m个周期性任务，任务i的周期为Pi，其中每个事件任务需要Ci秒的CPU时间来处理，则只有满足以下条件：

[i=1mcipi1]

才可能处理所有负载。满足该条件的系统任务集认为是可调度的（Schedulable）。实时调度强调的是任务的时间约束，尤其是在硬实时系统的设计中，评价调度程序好坏与否不在于调度的公平性和最小响应时间，而是所有硬实时任务能否在最后截止期限内完成。在实时调度过程中使用的调度策略方法或资源控制协议，通常我们称为实时调度算法。

2 嵌入式操作系统常见的实时调度算法

嵌入式操作系统必须保证在确定的时间内对事件进行处理，因此必须要有一个良好的任务调度算法，它具有如下特点：

①公平，保证每个任务都能得到合理的CPU时间；

②高效，使CPU没有空闲，总是有任务在CPU上处于运行状态；

③响应及时，使交互用户的响应时间尽可能的短；

④利用率高，使单位时间内为尽可能多的任务服务。

很明显，在任何一个操作系统中同时满足这几个目标是不太现实的，必须在这几个方面进行相应的取舍与折中考虑，从而确定自己的调度算法。目前在嵌入式系统中常见的实时调度算法有单调速率调度算法（RMS），最早截止时间优先调度算法（EDF）等。还有一些在此基础上进行优化或者改进而成的算法，如截止期限单调调度算法（Deadline Monotonic Scheduling，DMS）、最小空闲时间优先调度算法（Least Laxity First，LLF）等。

1）速率单调调度算法

单调速率调度（RMS）算法是C.L.Liu和J.W.Layland在1973年引入提出的一种基于周期和多任务的静态优先级可抢占调度算法。RMS是针对周期任务的优先级调度算法，当任务的截止时间等于其周期时，RMS算法已被证明是静态最优的调度算法。C.L.Liu和J.W.Layland给出了RMS算法可调度的充分非必要条件，其中C为任务，T为周期，n为任务个数。

[C0T0+C1T1+……+CnTnn（21n-1）]

这种算法执行起来开销很小，可调度性测试简单，但最大的局限性就在于该算法不可能总使CPU被完全利用。在最差情况下可调度的范围为：

[Wn=n（21n-1]

从公式中不难看出：

①当系统中只有一个任务运行时，最差的可调度范围为100%；

②当系统中有多个任务运行时，可调度范围逐渐降低，达到极限值69.3%左右。

所以，当系统中的任务总量不超过n（21/n-1）时，RMS算法可以调度执行系统所有的任务并满足它们的时限要求。当系统超过此负载限制时，系统调度就有可能出现不能满足任务执行时限的现象。

2） 最早截止期限优先调度

最早截止期限优先调度算法（EDF）是一种基于优先级的抢占式动态最优调度算法，也称为死限驱动调度算法（Deadline Driver Scheduling，DDS）。该算法的任务优先级初始之时并不固定，而是随着启动时间的变化而动态地改变，以距离最后截止期限时间的长短来分配优先级，具体地说就是距离最后截止期限时间越短的任务越紧急，相应的任务优先级也就越高；距离最后截止期限时间越长的任务对完成截止时间要求越松弛，该任务的优先级也就越低。系统每时每刻总是在就绪队列中挑选最早到达绝对最后截止期限的任务在处理机上执行。事实上，EDF算法是一种最优的单处理器调度算法，对于相对期限等于周期且总资源利用率不大于n（21/n-1）的周期任务集，可由该算法进行调度。实践表明，EDF算法的优点在于系统负载较低时，效率较高，相对容易实现。缺点在于该算法理论上能对系统可调度负载进行优化，但不能解决系统负载较重时，系统性能急剧下降的问题。C.L.Liu和J.W.Layland给出了采用EDF算法可调度的充分必要条件，其中C为任务，T为周期，n为任务个数。

[C0T0+C1T1+……+CnTn1]

由于EDF算法在运行时系统开销较大，特别是在过载情况下，由于大量任务错过最后截止期限引发CPU频繁的任务调度，消耗了大量的CPU时间，这时候系统的性能可能还不如先来先服务FIFO（First In First out）调度算法稳定。另外EDF算法在实际应用中可能会出现优先级倒置的现象，所以EDF算法在实际应用中还存在一些问题。

3）最短空闲时间优先调度

最短空闲时间优先调度算法（LLF）也叫最小松弛时间优先调度算法，是在EDF算法的基础之上发展起来的一种动态调度算法。该算法首先根据任务完成的截止时间和剩余的执行时间来计算任务的空闲时间，即空闲时间=截止时间-剩余执行时间；然后再根据任务的空闲时间来动态分配优先级，空闲时间越短，优先级越高，空闲时间越长，优先级越低。在执行的过程中，随着时间的向前推进，等待任务的空闲时间越来越短，相应的任务等待执行的紧急程度也就越来越紧迫，因此，等待任务随时可能会抢占当前执行的任务，从而造成了任务之间的相互竞争，导致了任务之间的频繁切换现象较为严重，大大增加了系统时间开销，其实际应用受到了一定的限制。endprint

3 嵌入式操作系统实时调度算法分析比较

1）固定优先级调度算法

在实时调度算法中，固定优先级调度算法事先根据任务的属性，如任务的周期、截止期限等为系统中的所有任务静态分配一个优先级。当任务的截止期限等于周期时，提出了RMS调度算法，它根据任务的执行周期长短的不同来决定优先级，即任务的周期越小优先级越高，任务的周期越大优先级越低。以RMS为代表的固定优先级调度算法，一方面不仅具有运行时间开销小和易于实现的优点，而且在系统超载情况下，仍然可以保证高优先级的任务得到执行；但另一方面却是不能充分地利用系统资源。

2）动态优先级调度算法

在实时调度算法中，动态优先级调度算法根据任务资源需求的变化以及任务的属性，如任务周期、截止期限等动态地决定任务的优先级。当任务的截止期限等于周期时，提出了EDF调度算法，该算法根据就绪队列中任务的截止期限分配优先级，距离绝对截止期限的最近的任务具有最高的优先级，即任务的绝对截止期限越小优先级越高，任务的绝对截止期限越大优先级越低。以EDF为代表的动态优先级调度算法，一方面可以充分地利用系统的资源；但是另一方面在系统负荷严重超载时，系统性能很不稳定，导致大多数任务在截止期限到来之时仍无法满足。

3）静态优先调度算法与动态优先调度算法的比较

静态调度是指系统脱机地进行调度可行性分析后生成一个可调度表，在运行的过程中，调度表中的信息不再发生任何变化。该类调度算法假定系统实时任务的属性是提前已知的并且在执行过程中很少发生变化，特别适合于对那种确定问题的求解，具有较好的可预测性。

动态调度与静态调度刚好相反，是根据任务在执行过程中的动态属性来选择某个就绪任务到处理机上去执行。此类调度算法它仅仅只根据目前就绪任务的相关属性来决定调度序列，而对以后将要到达的任务的特性完全不知，也不进行任何评估。这类算法的优点是它能够对运行环境的变化做出反应，具有较高的灵活性，特别适用于那些在运行过程中不断添加新任务且特性又不明确的动态实时系统。但是该类算法的运行时间开销一般比静态调度算法大。

参考文献：

[1] 赵慧斌，李小群.改善Linux核心可抢占性方法研究与实现[J].计算机学报，2004.27：240-250.

[2] 苏曙光，刘云生.基于RTHAL的Linux研究与实现[J].计算机科学，2009，7：143-148.

[3] 顾胜元，杨丹.嵌入式实时动态内存管理机制[J].计算机工程， 2009，20：250-257.

[4] 文星，张辉宜.嵌入式Linux的实时性改进技术[J].计算机技术与发展，2006，16（10）.

[5] 左天军，左园园.Linux操作系统的实时化分析[J].计算机科学，2004，31（5）：110-112.

[6] 赵明富.Linux嵌入式系统实时性分析与实时化改进[J].计算机应用研究，2004（4）.

[7] 赵明富.嵌入式Linux操作系统的实时化研究[J].西南师大学报，2003，28（3）.endprint