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

嵌入式实时操作系统中实时调度算法概述 摘要：在实时任务调度中，基于优先级的实时调度算法最为常见，任务的优先级都是基于任务的某些特征参数（如任务周期）计算而得，因此优先级所采取的标准比较片面，容易导致某些任务不能被满足或者系统资源不能被充分利用。基于此综合了两个或两个以上的特征来作为任务的优先级进行任务调度的算法应运而生，NSRL基于RM的并进行改进，改善了系统性能，提高了资源利用率。 关键字：嵌入式系统 实时调度算法 RM NSRL 引言 嵌入式实时操作系统具有嵌入式和实时性双重特点。作为一种嵌入式操作系统，它不乏嵌入式软件共有的可裁剪、低资源和低功耗等特点；作为实时操作系统，除了满足应用的功能需求，还要满足应用提出的实时性要求。实时操作系统所遵循的最重要的设计原则是：采用各种算法和策略始终保证系统行为的可预测性。实时操作系统的首要任务是调动一切可利用的资源完成实时控制任务。如何使任务集内各任务满足各自的时限，使系统得以正常、高效率工作的任务调度算法一直是实时系统领域内研究的重心。 实时调度的分类 调度的实质是对资源的分配，而实时系统的调度强调的是任务的时间约束。实时调度的分类方式有多种。如表1所示： 表1实时调度系统分类表 分类标准 分类结果 根据所解决问题的性质 静态调度、动态调度 根据任务是否可以被抢占 抢占式调度、非抢占式调度 根据任务的实时性要求 硬实时调度、软实时调度 根据实时系统运行环境 单处理机调度、多处理机调度 根据调度器的体系结构 集中式调度、分布式调度 静态调度算法是在系统编译的时候决定从就绪任务队列中选择哪个任务来运行，一般是以RMS算法为基础，适用于问题需求比较明确的一些情况，额外开销小，稳定性和可预测性好。 动态调度算法则是指调度器在运行期间才决定选择哪个就绪任务来运行，一般以EDF、LLF为主，灵活性好，适合子任务不断生成，并且在任务生成之前其特性并不知道的动态实时系统中。 硬实时系统指系统要有确保的最坏情况下的服务时间，即对于事件的响应时间的截止期限是无论如何都必须得到满足，比如航天中的宇宙飞船的控制系统。 　　 软实时是指统计意义上的实时，一般整体吞吐量大或整体响应速度快，但不能保证特定任务在指定时期内完成，如实时多媒体系统。 RM调度算法 所谓RM调度，就是为每一个周期任务指定一个固定的优先级，该优先级按照任务周期的长短顺序排列，任务周期越短，其优先级越高，以单调的顺序对剩余的任务分配优先级。RM算法基于以下假设： 1．没有任务具有不可优先抢占段，而且优先抢占的耗费是可忽略的。 2．只有数据处理的需求是重要的，内存和其他资源请求是可忽略的。 3．所有任务都是独立的、同时不存在优先约束。 4．任务集合中的所有任务都是周期性的。 5．任务的相对时限等于它的周期。 RM算法实现机制简单，调度开销较低，被广泛应用于硬实事调度领域，然而其仅以任务周期作为优先级的判定条件，在无线宽带移动等实时性要求较高额领域中，RM算法不能合理的对它进行调度，处理器的利用效率相对较低。 改进的实时调度算法NSRL NSRL算法基于RM调度算法，在任务控制块TCB中加入两个参数importance和laxity，分别表示任务的重要度和该任务在本周期可以成功调度的最晚时刻，即裕度为零的时刻。在该算法中，在运行前指定由任务的周期和重要度共同决定任务的优先级，即周期短的任务，优先级高，重要度高的任务，当且仅当裕度为零时优先级高，其他时间优先级由周期决定。 该算法分几种情况讨论： 1)如果任务的周期相同，则按照任务的重要度高低来运行。 2)如果任务的重要程度相同，则仍然按照原来的RM调度算法进行调度。 3)如果任务的周期和重要度都相同，则按照先来先服务的原则进行调度。 4)如果任务的优先级不同，例如任务X和任务Y，如果任务X的周期比任务Y的周期短，但任务Y的重要度比任务X的重要度高，则任务Y可以抢占任务X的CPU，当且仅当任务Y的裕度为零时(保证了重要任务Y的截止期限)。算法步骤如下： 步骤l 初始化TCB，设置时钟的初始时间。 步骤2 更新计数器。 步骤3 该时刻没有完成的任务当中，重要度最高的任务设为p1，优先级最高的任务设为p2，如果没有找到这样的任务p1或者p2，让CPU空跑到下个最近的任务的开始时间，返回步骤2。如果此时p1的裕度为零(设置当前的时间为T)，让p1运行到完成，返回步骤2，否则，运行p2。 步骤4 如果p2的截止时间在下个高优先级的任务到达之前或者T之前，运行p2到完成；否则，p2运行到高优先级任务到达的时刻和T中的最小时刻。 步骤5返回步骤2，再次调度。 在系统轻载的情况下，NSRL可以保证重要任务的截止期限得到满足，同时充