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

嵌入式实时操作系统中实时调度算法综述摘要：实时调度是指在有限的系统资源下，为一系列任务打算何时运行，并安排任务运行除CPU之外的资源，以保证其时间约束、时序约束和资源约束得到满意。一个实时系统可以由单处理器系统来实现，也可以用多处理器系统来实现。实时调度算法是保障实时系统时限性和高牢靠性的最重要手段之一。关键词：嵌入式；实时操作系统；实时调度算法；RTOS；RMS引言嵌入式系统在当今的生产和生活中得到了广泛的应用，鉴于嵌入式实时系统的特点,要求任务调度等实时内核功能精简和高效。综合了EDF和RM调度策略的CSD调度策略,更加适合嵌入式系统的特点,满意其内核的要求。任务调度策略是实时系统内核的关键部分,如何进行任务调度,使得各个任务能在其期限之内得以完成是实时操作系统的一个重要的讨论领域。它的精简和高效,对提凹凸处理力量,小内存系统整体性能具有重大的意义。RTOS概述RTOS,即：实时系统(Real-timeoperatingsystem),实时系统能够在指定或者确定的时间内完成系统功能和外部或内部、同步或异步时间做出响应的系统。它的正确性不仅依靠系统计算的规律结果，还依靠于产生这个结果的时间。因此实时系统应当在事先先定义的时间范围内识别和处理离散大事的力量；系统能够处理和储存掌握系统所需要的大量数据。对一般的程序来说，大多数是考虑指令执行的规律挨次，指令何时执行并不重要。而对实时应用系统的程序就不一样，当外部某激励消失时，系统必需以肯定的方式和在限定的时间内响应它，假如己超时，那怕执行结果是正确的，系统也认为是失效的。实时操作系统通常被分为软实时操作系统和硬实时操作系统。前者意味着间或错过时限是可以容忍的；后者意味着执行过程不但必需正确而且必需准时。在实时操作系统中，系统将程序分成很多任务(或进程)，而每个任务的行为都预先可知，或者是有明确的功能，系统依据肯定的调度原则，打算谁可取得执行权，这就是RTOS的核心所在。实时调度算法实时调度算法可以分为4类：单处理器静态调度算法、多处理器静态调度算法、单处理器动态调度算法、多处理器动态调度算法。下面分别分析嵌入式操作系统中采纳的各种调度方法,以及这些调度方法是如何满意实时性应用的实时要求的。1速率单调算法速率单调算法是一个经典的算法，它是针对那些响应和处理周期性大事的实时任务的，它事先为每个这样的实时任务安排一个与大事频率成正比的优先级。实现时,就绪队列中的全部任务依据优先级PriOrity排队,优先级最高的任务排在队首,当处于运行态的任务，由于某种缘由挂起时，只要把就绪队列的首元素从就绪队列中取下，使运行任务指针PRUnTaSk指向该元素即可，假如是处于其他状态的任务变为就绪状态，而挂于就绪队列时，则必需对运行任务和就绪队列首元素的任务进行比较，优先级高的任务占有CPU。2截止期最早优先算法截止期最早的任务优先级最高，对于周期任务，其截止期即为下一周期开头的时间，有时，把这种算法称为期限驱动算法，就绪队列中的任务，按截止期排序，截止期早的任务排在队首，这个算法的处理，与速率单调算法类似，不同的是，现在是对截止期进行推断，按截止期最早优先策略处理。3可达截止期最早优先算法这个算法是对截止期最早优先策略的改进,就绪队列的任务,仍旧依据截止期挨次排队,但是在调度时超过截止期的不予调度，假如记为t为系统当前时间，E为任务估算执行时间，P为任务实际执行时间，d为截止期。则dx=d-(t+E-p)O表示该任务的截止期是当前可达到的，于是，只要在调度时，依据上式计算被调度就绪任务的dl,若大于0,就进行调度，否则，就夭折它。这种算法里，系统时钟管理部分中的时钟滴答中断处理程序，必需对运行任务的运行时间进行累计。空闲任务IDLE的截止期DeadTime应置为无限大，而估算时间PrediCtedTiein可为0,从而在进行任务调度时，可以保证就绪队列中至少有一个就绪任务，满意调度要求。4最小裕度算法在上述算法中，优先性由截止期时间的早晚而定，可能使一些不行达截止期的任务，因来不及处理而夭折，此外一种算法是：计算任务的富有时间，称为裕度，裕度小的，优先级高，以弥补上述状况的不足。在这种算法里，时钟的滴答中断，不但要累计运行任务的执行时间，还要对就绪队列上的任务的裕度进行累减，实际上(3.1)式中的dl,便是这里所谓的裕度，由于正在运行的任务，其裕度不变，而就绪队列上的任务，其裕度随着时间的推移而削减，从而使得它们的优先权，动态地发生变化。5其他的实时调度算法1、价值最高优先算法在这种算法里,每一个任务有一个价值函数,价值最大，优先级最高。2、价值比最大优先算法在这种算法里，定义一个价值比函数：VD=叭:P)E-p其中，V为类似上面所定义的价值函数，t为当前时间，E为估算执行时间，p为已执行时间。这时，VD值越大，优先级越高。下面详细介绍单调速率算法：单调速率调度算法RMS(RateMonotonicScheduling)为每个周期进程指定一个固定不变的优先级，周期最短的进程优先级最高。周期越短，进程的到达频率越高，优先级也越高,这正是此策略被称为速率单调算法的缘由。RMS算法也可用于多CPU环境,用于安排任务优先级。这种方法基于哪个任务执行的次数最频繁，执行最频繁的任务优先级最高。RMS的由来是从硬实时环境的初始定义开头的：1,全部的任务都是周期性的，各个任务恳求的deadline呈周期性，同时具有恒定的时间间隔；2,全部任务都必需在下一次任务恳求(即deadline)到来之前完成；3,全部的任务都是独立的，每一次任务恳求不依靠于其他任务的执行或者初始化；4,每个任务都存在一个恒定且非时变的执行时间，即CPU不间断地执行该任务的时间；5,任何非周期的任务属于特别任务，它们属于初始化或者是恢复错误的大事，仅当它们自身执行的时候才能取代周期性任务，同时非周期性任务不存在有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为布尔变量，表示是否该任务可以被挂起以保证其之后可以被调度；importance为整形变量，详细指定了CPU执行该任务的情愿度，具有低importance在执行较高优先级的任务之前被挂起；do-task为功能性函子，详细指定即将被执行的详细任务；2,使用RMA.Feasible函数（已被SChedUIe函数调用）循环查询推断任务是否可以被调度template<classTL,intm,inti>structcheck_i;template<classHead,classTai1,intm,inti>structcheck_i<Typelist<Head,Tail>,m,i>enumtask_result=task-feasible<Typelist<Head,Tai1>,i>:Result,Result=check_i<Typelist<Head,Tai1>,m,i+l>:Result&&task_result;；template<classHead,classTail,intm>structcheck_i<Typelist<Head,Tail>,m,m>enumResult=task_feasible<Typelist<Head,Tai1>,m>:Result;；template<classTaskSet>structRMA.Feasibleenumm=Length<TaskSet>:rvalue,Result=check_i<TaskSet,m,1>:Result;；3,推断可调度的充要条件不等式3）是否成立（核心算法实现）template<classTL,inti,intt,intj=0>structsum_j/初始化结构体变量SUnl_j,表示Ej=ICjfjtypedeftypenameTypeAt<TL,j>:ResultJ;enumCj=J:cost,定义Cj为任务的开销，即CPU执行时间Tj=J:period,定义Tj为任务的执行周期my_result=Cj*(t%Tj>0?1:0)+(t/Tj),定义my_result为CjfjResult=sum_j<TL,i,t,j+l>:Result+mjfresult;/迭代求出j=jfl的值，存入ReSUlt变量中template<classTL,inti,intt_ix,intk=0>structget_t/计算t值enumTi=TypeAt<TL,i-l>:Result:period,Tk=TypeAt<TL,k>:Result:period,分别读取任务iT,k的周期，并存入Ti,Tk变量num=Ti/Tk,Result=(t_ix>=num)?get-t<TL,i,t_ix-num_l,k+l>:Result:(t_ix+1)*Tk):)；推断1是否取到了可能的最大值，若是则求出t的值，否则tJX减去num，再推断下一个k是否能使1取到最大值template<classTL,inti,intt_ix=0>structtask_feasibletypedefget-t<TL,i,t_ix>t_type;enumt=t_type:Result,Result=(t>0)&&(sum_j<TL,i,t>:Result<=11task_feasib1e<TI.,i,t_ix+1>:Result);)；推断该任务是否满意不等式2,即是否SUnLJCt,返回ReSUit4,算法查错RMS算法在查错的时候，使用的C+的库的宏定义STATlSTIJCHECK,我们就能很简洁地使特定的任务在声明的时候都是可行的。typedefSchedule<TYPELTST_2(taskA,taskB)>Iny.schedule;STATIC_CHECK(my_schedule:!feasible,Schedule_Infeasible);SChedUIeJnfeasible宏定义定义的为字符串，通过编译器输出显示错误声明和提示：4Loki:CompiIeTimeError<0>ERROR_Schedule_Tnfeasible,hasincompletetypeandcannotbedefined将STATIC_CHECK宏定义放在SChedUle:SChedUIe()函数中，可以确保在CPU运行的时间调度任务都是可行的。硬件初始化总而言之，算法实现的核心在于RMA分析（RateMonotonicAnalysis）,通过对每个任务实现不等式3）的判定，对已知就绪的优先级最高的任务查询来它确定是否可以调度，从而实现算法。此算法优缺点分析：优点：1, RMS算法在静态调度中属于最优算法，任意的固定优先级算法能够实现的调度，在RMS算法中也能实现。尽管RMS算法的CPU采用率最小上确界为0.693,实际上的平均CPU采用率可达0.88。2, RMS算法可在运行前“离线”确定周期进程的执行挨次，运行时不必保留很多信息,同时可调度件测试简洁，因此易于实现，运行时的调度开销相对较小，这是静态优先级调度算法对动态优先级调度算法的普遍优势。3,此外，优先级的预先确定也使系统过载的现象比较好掌握。即使系统消失了临时的过载，也能够确保最重要的任务的调度需求。4,在满意周期性任务的同时，仍有余力（约30%左右的CPU使用率）致力于对非周期性任务(例如系统和参数的初始化，错误处理)快速响应。同时支持扩展和固件升级，这对消费类产品而言意义重大。缺点：1,它的潜在CPU采用率小于动态优先级策略，在动态优先级的最优算法EDF(EarlieStDeadlineFirst)中最坏状况下的可调度CPU使用率为L000。2,执行频率最高的任务并非最重要的任务。且较长周期的任务相对于较短周期的任务,更加简洁错过dead1ine。3,由于RMS算法的静态调度属性，它运行时敏捷性较差，自适应性弱。现今常用的实时性的操作任务，常常具有较敏捷的使用率需求，但同时具有严格RMS算法完全建立在硬实时的条件下，主见全部被调度的周期性任务具有固定的优先级，这就显得强调在deadline之前的必需完成任务的思想超出了必要限度。详细而言，在特别场合，一些任务的deadline是可以被错过的，只要在deadline前完成任务的要求能在肯定百分率下得到满意。这种高敏捷性使得RMS的最小上界理论毫无提出之必要了。详细而言，在实时多媒体应用的调度之中，特点常常是：a,单个应用的执行次数常常是不定的；b,错过deadline尽管是不情愿消失的状况，但它的确是非致命的错误，这样在实时多媒体系统中使用过分强调在deadline之前任务的RMS算法就多少显得有些不合时宜了，会导致较低的CPU使用率，从而铺张原本稀缺的资源；目前，已证明动态调度算法不存在最优算法。假如实时任务只要求在截止期之前完成的条件下，EDF算法已被证明是单处理器静态调度算法中最优的；假如调度算法中的任务的属性要求任务必需在一个时间段内开头和结束,这类算法无论在单处理器或多处理器环境下仍旧是一个难点，也是一个讨论的热点。此外，前面提到的算法都是将一个个独立的任务分派到不同的处理器上运行，假如一个任务分割成若干个子任务在不同的处理器上运行，这一类算法的讨论也是一个讨论的难点和热点，由于这里还涉及到多个子任务间的同步关系。单调速率优先级算法是基于硬实时条件需求下提出的,它的初衷是保证全部的周期性任务均能在截止期限之前完成。经证明，其在全部的静态优先级调度算法之中为最优算法。但是由于嵌入式系统硬实时和软实时兼备的特性,过分强调截止期限的重要性会减弱算法的敏捷性，铺张系统资源。将来需要研讨将随机过程与概率统计思想与单调速率调度思想形成一个连续统一体，以满意当今嵌入式系统任务调度之需求。参考文献：1孙旭祥浅析实时操作系统的任务调度通信对抗2005年其次期2杨立身，王中海嵌入式实时操作系统任务调度算法改进3徐端全嵌入式系统原理与设计北京航空航天高校出版社4张莉莉，张峰实时调度算法综述软件导刊第7卷第10期2022年10月5王知学:嵌入式操作系统调度算法讨论.J中国科学院自动化讨论所2003