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

嵌入式实时操作系统中实时调度算法综述摘要：实时调度是指在有限的系统资源下，为一系列任务决定何时运行， 并分配任务运行除CPU之外的资源，以保证其时间约束、时序约束和资源约束得到满足。一个实时系统可以由单处理器系统来实现，也可以用多处理器系统来实现。实时调度算法是保障实时系统时限性和高可靠性的最重要手段之一。 关键词：嵌入式；实时操作系统；实时调度算法；RTOS；RMS引言嵌入式系统在当今的生产和生活中得到了广泛的应用,鉴于嵌入式实时系统的特点,要求任务调度等实时内核功能精简和高效。综合了EDF 和RM调度策略的CSD 调度策略,更加适合嵌入式系统的特点,满足其内核的要求。任务调度策略是实时系统内核的关键部分,如何进行任务调度,使得各个任务能在其期限之内得以完成是实时操作系统的一个重要的研究领域。它的精简和高效,对提高低处理能力,小内存系统整体性能具有重大的意义。 RTOS概述RTOS，即：实时系统（Real-time operating system），实时系统能够在指定或者确定的时间内完成系统功能和外部或内部、同步或异步时间做出响应的系统。它的正确性不仅依赖系统计算的逻辑结果，还依赖于产生这个结果的时间。因此实时系统应该在事先先定义的时间范围内识别和处理离散事件的能力；系统能够处理和储存控制系统所需要的大量数据。对一般的程序来说，大多数是考虑指令执行的逻辑顺序，指令何时执行并不重要。而对实时应用系统的程序就不一样，当外部某激励出现时，系统必须以一定的方式和在限定的时间内响应它，如果已超时，那怕执行结果是正确的，系统也认为是失效的。实时操作系统通常被分为软实时操作系统和硬实时操作系统。前者意味着偶尔错过时限是可以容忍的；后者意味着执行过程不但必须正确而且必须准时。在实时操作系统中，系统将程序分成许多任务(或进程)，而每个任务的行为都预先可知，或者是有明确的功能，系统根据一定的调度原则，决定谁可取得执行权，这就是RTOS的核心所在。实时调度算法实时调度算法可以分为4类：单处理器静态调度算法、多处理器静态调度算法、单处理器动态调度算法、多处理器动态调度算法。下面分别分析嵌入式操作系统中采用的各种调度方法，以及这些调度方法是如何满足实时性应用的实时要求的。1 速率单调算法 速率单调算法是一个经典的算法，它是针对那些响应和处理周期性事件的实时任务的，它事先为每个这样的实时任务分配一个与事件频率成正比的优先级。 实现时，就绪队列中的所有任务按照优先级Priority排队，优先级最高的任务排在队首，当处于运行态的任务，由于某种原因挂起时，只要把就绪队列的首元素从就绪队列中取下，使运行任务指针pRunTask指向该元素即可，如果是处于其他状态的任务变为就绪状态，而挂于就绪队列时，则必须对运行任务和就绪队列首元素的任务进行比较，优先级高的任务占有。2 截止期最早优先算法 截止期最早的任务优先级最高，对于周期任务，其截止期即为下一周期开始的时间，有时，把这种算法称为期限驱动算法，就绪队列中的任务，按截止期排序，截止期早的任务排在队首，这个算法的处理，与速率单调算法类似，不同的是，现在是对截止期进行判断，按截止期最早优先策略处理。3 可达截止期最早优先算法 这个算法是对截止期最早优先策略的改进，就绪队列的任务，仍然按照截止期顺序排队，但是在调度时超过截止期的不予调度，如果记为t为系统当前时间，为任务估算执行时间，p为任务实际执行时间，d为截止期。则 表示该任务的截止期是当前可达到的，于是，只要在调度时，按照上式计算被调度就绪任务的d1，若大于，就进行调度，否则，就夭折它。 这种算法里，系统时钟管理部分中的时钟滴答中断处理程序，必须对运行任务的运行时间进行累计。空闲任务IDLE的截止期DeadTime应置为无限大，而估算时间PredictedTiem可为0，从而在进行任务调度时，可以保证就绪队列中至少有一个就绪任务，满足调度要求。4 最小裕度算法 在上述算法中，优先性由截止期时间的早晚而定，可能使一些不可达截止期的任务，因来不及处理而夭折，另外一种算法是：计算任务的富裕时间，称为裕度，裕度小的，优先级高，以弥补上述情况的不足。在这种算法里，时钟的滴答中断，不但要累计运行任务的执行时间，还要对就绪队列上的任务的裕度进行累减，实际上(3.1)式中的d1，便是这里所谓的裕度，由于正在运行的任务，其裕度不变，而就绪队列上的任务，其裕度随着时间的推移而减少，从而使得它们的优先权，动态地发生变化。5 其他的实时调度算法1、价值最高优先算法在这种算法里,每一个任务有一个价值函数,价值最大，优先级最高。2、价值比最大优先算法在这种算法里，定义一个价值比函数：其中，v为类似上面所定义的价值函数，t为当前时间，E为估算执行时间，p为已执行时间。这时，VD值越大，优先级越高。下面具体介绍单调速率算法：单调速率调度算法RMS（Rate Monotonic Scheduling）为每个周期进程指定一个固定不变的优先级，周期最短的进程优先级最高。周期越短，进程的到达频率越高，优先级也越高，这正是此策略被称为速率单调算法的原因。RMS算法也可用于多CPU环境,用于分配任务优先级。这种方法基于哪个任务执行的次数最频繁，执行最频繁的任务优先级最高。RMS的由来是从硬实时环境的初始定义开始的：1,所有的任务都是周期性的，各个任务请求的deadline呈周期性，同时具有恒定的时间间隔；2,所有任务都必须在下一次任务请求（即deadline）到来之前完成；3,所有的任务都是独立的，每一次任务请求不依赖于其他任务的执行或者初始化；4,每个任务都存在一个恒定且非时变的执行时间，即CPU不间断地执行该任务的时间；5,任何非周期的任务属于特殊任务，它们属于初始化或者是恢复错误的事件，仅当它们自身执行的时候才能取代周期性任务，同时非周期性任务不存在有deadline.RMS算法的实现(C+模板元程序实现示例)1，声明任务my_task的结构体变量：struct my_task enum cost = 100,period = 600,phasing = 50,droppable = 0,importance = 1000 ;static void do_task(const context& c) cout my_task:do_task() endl;period表示任务的响应周期；phasing 表示任务的逻辑定向；droppable 为布尔变量，表示是否该任务可以被挂起以保证其之后可以被调度；importance为整形变量，具体指定了CPU执行该任务的情愿度，具有低importance在执行较高优先级的任务之前被挂起；do_task 为功能性函子，具体指定即将被执行的具体任务；2， 使用RMA_Feasible函数（已被Schedule函数调用）循环查询判断任务是否可以被调度template struct check_i;template struct check_iTypelist, m, i enum task_result =task_feasibleTypelist,i:Result,Result = check_iTypelist,m,i+1:Result& task_result ; ;template struct check_iTypelist, m, m enum Result = task_feasibleTypelist,m:Result ;template struct RMA_Feasible enum m = Length:value,Result = check_i:Result ;3，判断可调度的充要条件不等式3)是否成立(核心算法实现)template struct sum_j /初始化结构体变量sum_j，表示typedef typename TypeAt:Result J;enum Cj = J:cost, /定义Cj为任务的开销,即CPU执行时间Tj = J:period, /定义Tj为任务的执行周期my_result = Cj * (t%Tj 0 ? 1 : 0) + (t / Tj),/定义my_result为 Result = sum_j:Result + my_result ; / 迭代求出 的值，存入Result变量中template struct get_t / 计算t值enum Ti = TypeAt:Result:period,Tk = TypeAt:Result:period,/分别读取任务i-1,k的周期，并存入Ti,Tk变量num_l = Ti/Tk,Result = (t_ix = num_l) ? get_t:Result : (t_ix + 1) * Tk ;/判断l是否取到了可能的最大值，若是则求出t的值，否则t_ix减去num_l，再判断下一个k是否能使l取到最大值template struct task_feasible typedef get_t t_type;enum t = t_type:Result,Result = (t 0) & ( sum_j:Result = t| task_feasible:Result ) ; /判断该任务是否满足不等式2，即是否sum_j=t，返回Result4，算法查错RMS算法在查错的时候，使用的C+的库的宏定义STATISTIC_CHECK，我们就能很容易地使特定的任务在声明的时候都是可行的。typedef Schedulemy_schedule;STATIC_CHECK(my_schedule:feasible,Schedule_Infeasible);Schedule_Infeasible宏定义定义的为字符串，通过编译器输出显示错误声明和提示： Loki:CompileTimeError ERROR_Schedule_Infeasible has incomplete type and cannot be defined将STATIC_CHECK宏定义放在Schedule:schedule()函数中，可以确保在CPU运行的时间调度任务都是可行的。硬件初始化操作系统初始化各任务参数初始化含,算法实现的流程图： STATIC_CHECK是否有误? Y N比较优先级并且排序 任务集是否可调度 挂起 N Y生成代码并执行任务查询任务集中各个任务的可调度性和CPU使用率 总而言之，算法实现的核心在于RMA分析（Rate Monotonic Analysis），通过对每个任务实现不等式3）的判定，对已知就绪的优先级最高的任务查询来它确定是否可以调度，从而实现算法。此算法优缺点分析：优点：1，RMS算法在静态调度中属于最优算法，任意的固定优先级算法能够实现的调度，在RMS算法中也能实现。尽管RMS算法的CPU利用率最小上确界为0.693，实际上的平均CPU利用率可达0.88。2，RMS算法可在运行前“离线”确定周期进程的执行顺序，运行时不必保留很多信息，同时可调度件测试简单，因此易于实现，运行时的调度开销相对较小，这是静态优先级调度算法对动态优先级调度算法的普遍优势。3，另外，优先级的预先确定也使系统过载的现象比较好控制。即使系统出现了暂时的过载，也能够确保最重要的任务的调度需求。4，在满足周期性任务的同时，仍有余力（约30%左右的CPU使用率）致力于对非周期性任务（例如系统和参数的初始化，错误处理）快速响应。同时支持扩展和固件升级，这对消费类产品而言意义重大。缺点：1，它的潜在CPU利用率小于动态优先级策略，在动态优先级的最优算法EDF(Earliest Deadline First)中最坏情况下的可调度CPU使用率为1.000。2，执行频率最高的任务并非最重要的任务。且较长周期的任务相对于较短周期的任务，更加容易错过deadline。3，由于RMS算法的静态调度属性，它运行时灵活性较差，自适应性弱。现今常用的实时性的操作任务，常常具有较灵活的使用率需求，但同时具有严格RMS算法完全建立在硬实时的条件下，主张所有被调度的周期性任务具有固定的优先级，这就显得强调在deadline之前的必须完成任务的思想超出了必要限度。具体而言，在特殊场合，一些任务的deadline是可以被错过的，只要在deadline前完成任务的要求能在一定百分率下得到满足。这种高灵活性使得RMS的最小上 界理论毫无提出之必要了。具体而言，在实时多媒体应用的调度之中，特点经常是：a，单个应用的执行次数常常是不定的；b，错过deadline尽管是不愿意出现的情况，但它确实是非致命的错误，这样在实时多媒体系统中使用过分强调在deadline之前任务的RMS算法就多少显得有些不合时宜了，会导致较低的CPU使用率，从而浪费原本稀缺的资源；目前，已证明动态调度算法不存在最优算法。如果实时任务只要求在截止期之前完成的条件下，EDF算法已被证明是单处理器静态调度算法中最优的；如果调度算法中的任务的属性要求任务必须在一个时间段内开始和结束，这类算法无论在单处理器或多处理器环境下仍然是一个难点，也是一个研究的热点。另外，前面提到的算法都是将一个个独立的任务分派到不同的处理器上运行，如果一个任务分割成若干个子任务在不同的处理器上运行，这一类算法的研究也是一个研究的难点和热点，因为这里还涉及到多个子任务间的同步关系。 单调速率优先级算法是基于硬实时条件需求下提出的，它的初衷是保证所有的周期性任务均能在截止期限之前完成。经证明，其在所有的静态