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

《嵌入式实时操作系统中实时调度算法》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、嵌入式实时操作系统中实时调度算法概述摘要：在实时任务调度中，基于优先级的实时调度算法最为常见，任务的优先级都是基于任务的某些特征参数（如任务周期）计算而得，因此优先级所采取的标准比较片面，容易导致某些任务不能被满足或者系统资源不能被充分利用。基于此综合了两个或两个以上的特征来作为任务的优先级进行任务调度的算法应运而生，NSRL基于RM的并进行改进，改善了系统性能，提高了资源利用率。关键字：嵌入式系统实时调度算法RMNSRL引言嵌入式实时操作系统具有嵌入式和实时性双重特点。作为一种嵌入式操作系统，它不乏嵌入式软件共有的可裁剪、低资源和低功耗等特点；作为实时操作系

2、统，除了满足应用的功能需求，还要满足应用提出的实时性要求。实时操作系统所遵循的最重要的设计原则是：采用各种算法和策略始终保证系统行为的可预测性。实时操作系统的首要任务是调动一切可利用的资源完成实时控制任务。如何使任务集内各任务满足各自的时限，使系统得以正常、高效率工作的任务调度算法一直是实时系统领域内研究的重心。实时调度的分类调度的实质是对资源的分配，而实时系统的调度强调的是任务的时间约束。实时调度的分类方式有多种。如表1所示：表1实时调度系统分类表分类标准分类结果根据所解决问题的性质静态调度、动态调度根据任务是否可以被抢占抢占式调度、非抢占式调度根据任务的实

3、时性要求硬实时调度、软实时调度根据实时系统运行环境单处理机调度、多处理机调度根据调度器的体系结构集中式调度、分布式调度静态调度算法是在系统编译的时候决定从就绪任务队列中选择哪个任务来运行，一般是以RMS算法为基础，适用于问题需求比较明确的一些情况，额外开销小，稳定性和可预测性好。动态调度算法则是指调度器在运行期间才决定选择哪个就绪任务来运行，一般以EDF、LLF为主，灵活性好，适合子任务不断生成，并且在任务生成之前其特性并不知道的动态实时系统中。硬实时系统指系统要有确保的最坏情况下的服务时间，即对于事件的响应时间的截止期限是无论如何都必须得到满足，比如航天中的

4、宇宙飞船的控制系统。　　软实时是指统计意义上的实时，一般整体吞吐量大或整体响应速度快，但不能保证特定任务在指定时期内完成，如实时多媒体系统。RM调度算法所谓RM调度，就是为每一个周期任务指定一个固定的优先级，该优先级按照任务周期的长短顺序排列，任务周期越短，其优先级越高，以单调的顺序对剩余的任务分配优先级。RM算法基于以下假设：1．没有任务具有不可优先抢占段，而且优先抢占的耗费是可忽略的。2．只有数据处理的需求是重要的，内存和其他资源请求是可忽略的。3．所有任务都是独立的、同时不存在优先约束。4．任务集合中的所有任务都是周期性的。5．任务的相对时限等于它的周期

5、。RM算法实现机制简单，调度开销较低，被广泛应用于硬实事调度领域，然而其仅以任务周期作为优先级的判定条件，在无线宽带移动等实时性要求较高额领域中，RM算法不能合理的对它进行调度，处理器的利用效率相对较低。改进的实时调度算法NSRLNSRL算法基于RM调度算法，在任务控制块TCB中加入两个参数importance和laxity，分别表示任务的重要度和该任务在本周期可以成功调度的最晚时刻，即裕度为零的时刻。在该算法中，在运行前指定由任务的周期和重要度共同决定任务的优先级，即周期短的任务，优先级高，重要度高的任务，当且仅当裕度为零时优先级高，其他时间优先级由周期决定

6、。该算法分几种情况讨论：1)如果任务的周期相同，则按照任务的重要度高低来运行。2)如果任务的重要程度相同，则仍然按照原来的RM调度算法进行调度。3)如果任务的周期和重要度都相同，则按照先来先服务的原则进行调度。4)如果任务的优先级不同，例如任务X和任务Y，如果任务X的周期比任务Y的周期短，但任务Y的重要度比任务X的重要度高，则任务Y可以抢占任务X的CPU，当且仅当任务Y的裕度为零时(保证了重要任务Y的截止期限)。算法步骤如下：步骤l初始化TCB，设置时钟的初始时间。步骤2更新计数器。步骤3该时刻没有完成的任务当中，重要度最高的任务设为p1，优先级最高的任务设为

7、p2，如果没有找到这样的任务p1或者p2，让CPU空跑到下个最近的任务的开始时间，返回步骤2。如果此时p1的裕度为零(设置当前的时间为T)，让p1运行到完成，返回步骤2，否则，运行p2。步骤4如果p2的截止时间在下个高优先级的任务到达之前或者T之前，运行p2到完成；否则，p2运行到高优先级任务到达的时刻和T中的最小时刻。步骤5返回步骤2，再次调度。在系统轻载的情况下，NSRL可以保证重要任务的截止期限得到满足，同时充分利用系统资源。在超载情况下，采用RM算法，短周期任务按照优先级高低调度，周期相同则按照先来先服务进行调度，因此后到来的任务或者周期较长的任务只能

8、部分调度，或者不能调度，任务的大部分的