单调速率调度算法RMS

嵌入式系统单调速率调度算法的特点及实现余蓝涛1(天津大学精密仪器与光电子工程学院天津300072)摘要：嵌入式系统对强大实时处理能力的需求和相对紧张的内存及内核资源的现实，对嵌入式操作系统任务调度提出了较高的要求。因此任务调度的算法的分析，实现和优化，对实现嵌入式系统的实时性有着重大的意义。从算法提出的理论基础出发，深入分析了经典的单调速率调度算法的思想，特点，具体实现并重点评价了该算法的优点和局限性。关键词：单调速率调度算法实时嵌入式系统Abstract：Thezestforpowerfulreal-timeprocessingofembeddedsystemandtherealityofrelativelyscarememoryandkernelresourcepavewayforthehighrequestfortaskscheduling.Therefore,theanalysis,implementationandoptimizationoftaskschedulingalgorithmhaveavastmeaningforthereal-timesystem.Basedontheoreticalbasisofclassicrate-monotonicschedulingalgorithm,thispapernotonlyanalyzesfundamentalthought,characteristics,practicalimplementationofthisclassicalgorithmindepth,butalsorateitsadvantagesanddisadvantages.Keywords:Rate-monotonicScheduling,Algorithm,Real-time,EmbeddedSystem一，引言现在嵌入式系统得到高速的发展。它的发展为几乎所有的电子产品注入了新的活力。它在国民经济各领域和我们日常生活中发挥了越来越重要的作用。嵌入式系统在航天、军事、工控以及家电等方面得到了广泛应用。囿于体积，能耗，价格等方面的约束，嵌入式系统处理器速度比较慢，存储器容量也有限。而传统的操作系统为了取得较高的性能，要求硬件设备具有强大的处理能力，大容量的存储能力以及对网络的支持功能，这使得传统的操作系统难以简单地移植到嵌入式系统中。这就导致了嵌入式操作系统由于受到系统的限制，往往内存资源都非常的有限，要求操作系统的内核都非常的精炼，对于系统中的资源操作系统内核需要进行统一的分配和调度。嵌入式操作系统调度策略一直以来都是嵌入式操作系统的研究中的一个热点。任务调度是嵌入式操作系统内核的关键部分，如何进行任务调度，使得各个任务能在其截止期限内得以完成是嵌入式操作系统的一个重要的研究领域。二，嵌入式实时操作系统绝大部分嵌入式系统都是实时系统，而且多是实时多任务系统。所谓“实时”,是指系统的正确性不仅仅依赖于计算的逻辑结果而且依赖于结果产生的时间[1][6]。结果产生的时间就是通常所说的截止期限(deadline),描述系统实时性的指标主要有：1作者简介：余蓝涛（1991-）江西省人天津大学精密仪器与光电子工程学院测控技术与仪器本科生联系方式：[e-mail]13821157281学号：3008202079a,对紧急事件可预见性的快速响应；b,高度的可调度性，所谓调度性是指系统在任务时间需求能够满足下的最高资源利用率，也就是平均每秒的及时执行的任务数量；c,在暂时超负荷情况下的系统稳定性，即当系统超负荷运转导致不能满足所有任务的deadline需求时，仍然能够保证关键任务的deadline需求；[2]对于“实时”而言，截止期限的要求是必须得到满足的，但是区分具体应用场合，这种时限要求的严格程度又有所不同。如果这种要求是绝对的，即不满足截止期限的要求计算结果就毫无意义甚至可能造成无法预料的结果或系统致命的错误，那就称之为硬实时系统(HardRealTimeSystem)；在硬实时系统中如果出现了这样的情况就意味着巨大的损失和灾难，比如说日本福岛核电站中的堆芯温度控制系统如果没有对堆芯过热做出及时的冷却处理，后果不堪设想。当不满足截止期限的要求时计算结果的可调度性逐渐减弱但是并不足以造成严重后果，系统仍然继续调度直至任务完成，则称为软实时系统(SoftRealTimeSystem)。软实时系统是指如果在系统负荷较重的时候允许发生错过deadline的情况而且不会造成太大的危害比如说程控电话系统允许在100个电话中有一个接不通。硬实时系统和软实时系统的实现区别主要是，在选择调度算法上选择基于优先级调度的算法足以满足软实时系统的需求而且可以提供高速的响应和大的系统吞吐率,而对硬实时系统来说需要使用的算法就应该是调度方式简单反应速度快的实时调度算法了。三，优先级调度算法调度，也称dispatcher。这是内核的主要职责之一，就是确定该轮到哪个任务运行了。优先级抢占调度算法中，每个任务根据其重要程度的不同而被赋予一定的优先级。优先级抢占调度算法是指在系统运行过程中高优先级的任务可以中断低优先级的任务，让处在就绪态的优先级最高的任务先运行。目前多数实时内核采用优先级可抢占的调度算法，主要原因有以下几点：[5]首先，处理异常的任务可能需要抢占正在运行的任务，以便及时对异常做出响应；第二，任务的重要性不同，优先级可抢占使一些重要任务有可能抢占正在运行的任务；第三，允许任务抢占可得到更为有效的调度；根据不同的优先级分配方法，基于优先级的调度算法可以分为如下两种类型：1,静态调度：静态调度是在系统开始运行前进行调度的，严格的静态调度在系统运行时无法对任务进行重新调度。静态调度的目标是把任务分配到各个CPU，并对每一个CPU给出所要运行任务的静态运行顺序。静态调度算法实现简单，调度的额外开销小，在系统超载时可预测性好。但也具有很大的局限性，例如资源利用率低、受系统支持的优先级个数限制以及灵活性和自适应性差等。2,动态调度：在嵌入式实时系统中，动态调度依赖于任务的优先级。优先级可以静态分配或者依据不同的特征参数，如截止时间、空闲时间或关键性(即任务的重要程度)等进行动态分配。动态调度可以是抢占式的或非抢占式的。当检查到一事件时，动态抢占式算法立即决定是运行与此事件相关的任务，或继续执行当前的任务；对于动态非抢占式算法，它仅仅知道有另一个任务可以运行，在当前任务结束后，它才在就绪的任务中选择一个来运行。优先级调度算法在实时进程调度中使用很广泛，静态优先级调度算法根据应用的属性来分配优先级，其可控性较强，而动态优先级调度算法在资源分配和调度时具有更大的灵活性。一个好的调度模型和调度算法应该能够满足以下四个要求：1)易于使用(EaseToUse)：在系统中对于分配资源的各种任务，调度算法不需要大量的搜索操作就可以找到可行性调度；2)易于纠偏(EaseToCheck)：任务程序发生改变时，调度不必从头做起；3)易于扩展(EaseToExtend)：一定程度上违反了系统的假设条件时，调度不应该改变；4)应确保可调度性(MustGuaranteePredictability)：在给定时间限定的条件下，调度必须能够保证所有任务的执行；静态优先级调度模型是实时系统中比较流行的一种调度模型。这种模型在系统运行前给每个任务分配固定的优先级和运行周期，当任务到达时向系统发出执行请求，这个请求必须在下一个周期开始之前完成，每个任务的执行情况相互独立。固定优先级调度模型可描述各种情况下系统的最坏运行情况，用定义好的算法来调度任务，而不需像循环调度模型那样对特定的情况用特定的调度方案，因此使系统便于维护和升级。[5]单调速率调度算法RMS（RateMonotonicScheduling）为每个周期进程指定一个固定不变的优先级，周期最短的进程优先级最高。周期越短，进程的到达频率越高，优先级也越高，这正是此策略被称为速率单调算法的原因。RMS算法也可用于多CPU环境,用于分配任务优先级。这种方法基于哪个任务执行的次数最频繁，执行最频繁的任务优先级最高。RMS的由来是从硬实时环境的初始定义开始的：1,所有的任务都是周期性的，各个任务请求的deadline呈周期性，同时具有恒定的时间间隔；2,所有任务都必须在下一次任务请求（即deadline）到来之前完成；3,所有的任务都是独立的，每一次任务请求不依赖于其他任务的执行或者初始化；4,每个任务都存在一个恒定且非时变的执行时间，即CPU不间断地执行该任务的时间；5,任何非周期的任务属于特殊任务，它们属于初始化或者是恢复错误的事件，仅当它们自身执行的时候才能取代周期性任务，同时非周期性任务不存在有deadline.RMS调度算法从何而来呢？假设使用表示m个周期任务，任务申请周期和运行时间分别表示为和。定理1:若所有进程在临界时刻启动的请求都能满足最后期限要求，则整个进程集可调度。即进程在临界时刻启动的请求响应时间最长。图1：在执行之前的运行[1]证明：如图1所示，假定为优先级最低的任务，在时刻任务发出了运行请求，显然在图1所示的到时间间隔之间请求运行的周期性占先任务会推迟完成时刻，除非在到来之前完成它。当向方向移动的时候，任务完成的时刻要么不变，要么被推迟，所以断定，在向方向无线趋近，直至与重合的时候，能够做到完成任务的延时最长。根据定理1可以假定，有两个任务和，对应的指定周期。假设的优先级更高，此时根据定理1，可得：[1]⌊⌋2如果假设的优先级更高，此时显然有：因为有：⌊⌋⌊⌋⌊⌋式导出了式，换句话说，只要保证了，不论是的优先级高于，的优先级高于的两种情况下都是可以调度的。推而广之，那么，似乎在设计调度算法的时候，倘若我们将调度频率独立于运行时间的话，让较高使用频率的任务具有较高的优先级，较低使用频率的任务具有较低的优先级的话，使用这种单调速率的方法来定义固定优先级的任务似乎是更加合理的选择了。定理2：如果一个可执行的静态优先级调度算法存在于某些可调度任务中，那么单调速率优先级算法必然在该任务中是可以调度的。[1]证明：令为一可行的（可调度）优先级调度算法，假设为两个相邻优先级的任务，且的优先级更高，假定，交换的优先级之后，不难发现结果的任务依然是可行的。由于其对任意式子都成立，于是命题成立。因此，单调速率调度算法在静态优先级调度算法中属于最优算法，所以该算法的CPU使用率必然大于等于其余的静态优先级调度算法。基于单调速率调度的算法中，定义U为ProcessorUtilization.(CPU的使用率)，由于⁄为每一个任务的CPU执行率，对系统有：∑⁄;由于优先级调度算法最终结果是可以调度的，所以U必须存在着一个最小上界，那就是在这个最小上界之下的CPU的运行率的任务一定是可以调度的。定理3:在两个固定优先级任务的情况下，经过计算，最小上界为.[1]经推广到m个固定优先级的任务条件下，此时的最小上界为：()[1]由罗必塔法则，求得极限为ln2。2⌊⌋表示不超过的最大整数，在式中⌊⌋表示在时间段内，任务的执行次数为直观表示，使用Matlab显示,根据MatlabR2008b版本的计算U-m的关系程序，代码如下：symsmy;y=m*(2^(m^(-1))-1);lim=limit(y,m,inf);%求出式子的极限m=1:1:100;%从0到100取m值,步长为1y=m.*(2.^(m.^(-1))-1);%用m表示y,其中m为数组plot(m,y,'-b');%作图，横坐标为m，纵坐标为yx=[0,100];y=[double(lim),double(lim)];line(x,y,'Color',[.4.8.8]);%作渐近线，颜色为淡蓝色xlabel('m');%x轴标注为m的大小ylabel('U(processingrateofCPU)');%y轴标注为CPU使用率gridon;%显示网格对应的U-m变化曲线如图2所示：图2：U-m曲线图图2中显示该曲线无限趋近于，即0