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

《嵌入式实时操作系统中实时调度算法综述48562.docx》由会员分享，可在线阅读，更多相关《嵌入式实时操作系统中实时调度算法综述48562.docx（6页珍藏版）》请在优知文库上搜索。

1、嵌入式实时操作系统中实时调度算法综述摘要：实时调度是指在有限的系统资源下，为一系列任务打算何时运行，并安排任务运行除CPU之外的资源，以保证其时间约束、时序约束和资源约束得到满意。一个实时系统可以由单处理器系统来实现，也可以用多处理器系统来实现。实时调度算法是保障实时系统时限性和高牢靠性的最重要手段之一。关键词：嵌入式；实时操作系统；实时调度算法；RTOS；RMS引言嵌入式系统在当今的生产和生活中得到了广泛的应用，鉴于嵌入式实时系统的特点,要求任务调度等实时内核功能精简和高效。综合了EDF和RM调度策略的CSD调度策略,更加适合嵌入式系统的特点,满意其内核的要求。任务调度策略是实时系统内核的关

2、键部分,如何进行任务调度,使得各个任务能在其期限之内得以完成是实时操作系统的一个重要的讨论领域。它的精简和高效,对提凹凸处理力量,小内存系统整体性能具有重大的意义。RTOS概述RTOS,即：实时系统(Real-timeoperatingsystem),实时系统能够在指定或者确定的时间内完成系统功能和外部或内部、同步或异步时间做出响应的系统。它的正确性不仅依靠系统计算的规律结果，还依靠于产生这个结果的时间。因此实时系统应当在事先先定义的时间范围内识别和处理离散大事的力量；系统能够处理和储存掌握系统所需要的大量数据。对一般的程序来说，大多数是考虑指令执行的规律挨次，指令何时执行并不重要。而对实时应

3、用系统的程序就不一样，当外部某激励消失时，系统必需以肯定的方式和在限定的时间内响应它，假如己超时，那怕执行结果是正确的，系统也认为是失效的。实时操作系统通常被分为软实时操作系统和硬实时操作系统。前者意味着间或错过时限是可以容忍的；后者意味着执行过程不但必需正确而且必需准时。在实时操作系统中，系统将程序分成很多任务(或进程)，而每个任务的行为都预先可知，或者是有明确的功能，系统依据肯定的调度原则，打算谁可取得执行权，这就是RTOS的核心所在。实时调度算法实时调度算法可以分为4类：单处理器静态调度算法、多处理器静态调度算法、单处理器动态调度算法、多处理器动态调度算法。下面分别分析嵌入式操作系统中采

4、纳的各种调度方法,以及这些调度方法是如何满意实时性应用的实时要求的。1速率单调算法速率单调算法是一个经典的算法，它是针对那些响应和处理周期性大事的实时任务的，它事先为每个这样的实时任务安排一个与大事频率成正比的优先级。实现时,就绪队列中的全部任务依据优先级PriOrity排队,优先级最高的任务排在队首,当处于运行态的任务，由于某种缘由挂起时，只要把就绪队列的首元素从就绪队列中取下，使运行任务指针PRUnTaSk指向该元素即可，假如是处于其他状态的任务变为就绪状态，而挂于就绪队列时，则必需对运行任务和就绪队列首元素的任务进行比较，优先级高的任务占有CPU。2截止期最早优先算法截止期最早的任务优先

5、级最高，对于周期任务，其截止期即为下一周期开头的时间，有时，把这种算法称为期限驱动算法，就绪队列中的任务，按截止期排序，截止期早的任务排在队首，这个算法的处理，与速率单调算法类似，不同的是，现在是对截止期进行推断，按截止期最早优先策略处理。3可达截止期最早优先算法这个算法是对截止期最早优先策略的改进,就绪队列的任务,仍旧依据截止期挨次排队,但是在调度时超过截止期的不予调度，假如记为t为系统当前时间，E为任务估算执行时间，P为任务实际执行时间，d为截止期。则dx=d-(t+E-p)O表示该任务的截止期是当前可达到的，于是，只要在调度时，依据上式计算被调度就绪任务的dl,若大于0,就进行调度，否则

6、，就夭折它。这种算法里，系统时钟管理部分中的时钟滴答中断处理程序，必需对运行任务的运行时间进行累计。空闲任务IDLE的截止期DeadTime应置为无限大，而估算时间PrediCtedTiein可为0,从而在进行任务调度时，可以保证就绪队列中至少有一个就绪任务，满意调度要求。4最小裕度算法在上述算法中，优先性由截止期时间的早晚而定，可能使一些不行达截止期的任务，因来不及处理而夭折，此外一种算法是：计算任务的富有时间，称为裕度，裕度小的，优先级高，以弥补上述状况的不足。在这种算法里，时钟的滴答中断，不但要累计运行任务的执行时间，还要对就绪队列上的任务的裕度进行累减，实际上(3.1)式中的dl,便是

7、这里所谓的裕度，由于正在运行的任务，其裕度不变，而就绪队列上的任务，其裕度随着时间的推移而削减，从而使得它们的优先权，动态地发生变化。5其他的实时调度算法1、价值最高优先算法在这种算法里,每一个任务有一个价值函数,价值最大，优先级最高。2、价值比最大优先算法在这种算法里，定义一个价值比函数：VD=叭:P)E-p其中，V为类似上面所定义的价值函数，t为当前时间，E为估算执行时间，p为已执行时间。这时，VD值越大，优先级越高。下面详细介绍单调速率算法：单调速率调度算法RMS(RateMonotonicScheduling)为每个周期进程指定一个固定不变的优先级，周期最短的进程优先级最高。周期越短，

8、进程的到达频率越高，优先级也越高,这正是此策略被称为速率单调算法的缘由。RMS算法也可用于多CPU环境,用于安排任务优先级。这种方法基于哪个任务执行的次数最频繁，执行最频繁的任务优先级最高。RMS的由来是从硬实时环境的初始定义开头的：1,全部的任务都是周期性的，各个任务恳求的deadline呈周期性，同时具有恒定的时间间隔；2,全部任务都必需在下一次任务恳求(即deadline)到来之前完成；3,全部的任务都是独立的，每一次任务恳求不依靠于其他任务的执行或者初始化；4,每个任务都存在一个恒定且非时变的执行时间，即CPU不间断地执行该任务的时间；5,任何非周期的任务属于特别任务，它们属于初始化或

9、者是恢复错误的大事，仅当它们自身执行的时候才能取代周期性任务，同时非周期性任务不存在有deadline.RMS算法的实现（C+模板元程序实现示例）1,声明任务my_task的结构体变量：structmy_taskenumcost=100,period=600,phasing=50,droppable=0,importance=1000;staticvoiddo_task（constcontext&c）cout*my_task:do_task（）*endl;）；Period表示任务的响应周期；phasing表示任务的规律定向；droppable为布尔变量，表示是否该任务可以被挂起以保证其之后可以

10、被调度；importance为整形变量，详细指定了CPU执行该任务的情愿度，具有低importance在执行较高优先级的任务之前被挂起；do-task为功能性函子，详细指定即将被执行的详细任务；2,使用RMA.Feasible函数（已被SChedUIe函数调用）循环查询推断任务是否可以被调度templatestructcheck_i;templatestructcheck_iTypelist,m,ienumtask_result=task-feasibleTypelist,i:Result,Result=check_iTypelist,m,i+l:Result&task_result;；tem

11、platestructcheck_iTypelist,m,menumResult=task_feasibleTypelist,m:Result;；templatestructRMA.Feasibleenumm=Length:rvalue,Result=check_i:Result;；3,推断可调度的充要条件不等式3）是否成立（核心算法实现）templatestructsum_j/初始化结构体变量SUnl_j,表示Ej=ICjfjtypedeftypenameTypeAt:ResultJ;enumCj=J:cost,定义Cj为任务的开销，即CPU执行时间Tj=J:period,定义Tj为任务的执

12、行周期my_result=Cj*(t%Tj0?1:0)+(t/Tj),定义my_result为CjfjResult=sum_j:Result+mjfresult;/迭代求出j=jfl的值，存入ReSUlt变量中templatestructget_t/计算t值enumTi=TypeAt:Result:period,Tk=TypeAt:Result:period,分别读取任务iT,k的周期，并存入Ti,Tk变量num=Ti/Tk,Result=(t_ix=num)?get-t:Result:(t_ix+1)*Tk):)；推断1是否取到了可能的最大值，若是则求出t的值，否则tJX减去num，再推断下

13、一个k是否能使1取到最大值templatestructtask_feasibletypedefget-tt_type;enumt=t_type:Result,Result=(t0)&(sum_j:Result=11task_feasib1e:Result);)；推断该任务是否满意不等式2,即是否SUnLJCt,返回ReSUit4,算法查错RMS算法在查错的时候，使用的C+的库的宏定义STATlSTIJCHECK,我们就能很简洁地使特定的任务在声明的时候都是可行的。typedefScheduleIny.schedule;STATIC_CHECK(my_schedule:!feasible,Sch

14、edule_Infeasible);SChedUIeJnfeasible宏定义定义的为字符串，通过编译器输出显示错误声明和提示：4Loki:CompiIeTimeErrorERROR_Schedule_Tnfeasible,hasincompletetypeandcannotbedefined将STATIC_CHECK宏定义放在SChedUle:SChedUIe()函数中，可以确保在CPU运行的时间调度任务都是可行的。硬件初始化总而言之，算法实现的核心在于RMA分析（RateMonotonicAnalysis）,通过对每个任务实现不等式3）的判定，对已知就绪的优先级最高的任务查询来它确定是否可以调度，从而实现算法。此算法优缺点分析：优点：1, RMS算法在静态调度中属于最优算法，任意的固定优先级算法能够实现的调度，在RMS算法中也能实现。尽管RMS算法的CPU采用率最小上确界为0.693,实际上的平均CPU采用率可达0.88。