单调速率调度算法RMS.docx

嵌入式系统单调速率调度算法的特点及实现余蓝涛 作者简介：余蓝涛（1991-）江西省人 天津大学精密仪器与光电子工程学院 测控技术与仪器 本科生 联系方式： 学号：3008202079(天津大学 精密仪器与光电子工程学院 天津 300072 ) 摘要：嵌入式系统对强大实时处理能力的需求和相对紧张的内存及内核资源的现实，对嵌入式操作系统任务调度提出了较高的要求。因此任务调度的算法的分析，实现和优化，对实现嵌入式系统的实时性有着重大的意义。从算法提出的理论基础出发，深入分析了经典的单调速率调度算法的思想，特点，具体实现并重点评价了该算法的优点和局限性。关键词： 单调速率调度 算法 实时 嵌入式系统Abstract：The zest for powerful real-time processing of embedded system and the reality of relatively scare memory and kernel resource pave way for the high request for task scheduling. Therefore, the analysis, implementation and optimization of task scheduling algorithm have a vast meaning for the real-time system. Based on theoretical basis of classic rate-monotonic scheduling algorithm, this paper not only analyzes fundamental thought, characteristics, practical implementation of this classic algorithm in depth, but also rate its advantages and disadvantages.Key words: Rate-monotonic Scheduling, Algorithm, Real-time, Embedded System一，引言现在嵌入式系统得到高速的发展。它的发展为几乎所有的电子产品注入了新的活力。它在国民经济各领域和我们日常生活中发挥了越来越重要的作用。嵌入式系统在航天、军事、工控以及家电等方面得到了广泛应用。囿于体积，能耗，价格等方面的约束，嵌入式系统处理器速度比较慢，存储器容量也有限。而传统的操作系统为了取得较高的性能，要求硬件设备具有强大的处理能力，大容量的存储能力以及对网络的支持功能，这使得传统的操作系统难以简单地移植到嵌入式系统中。这就导致了嵌入式操作系统由于受到系统的限制，往往内存资源都非常的有限，要求操作系统的内核都非常的精炼，对于系统中的资源操作系统内核需要进行统一的分配和调度。嵌入式操作系统调度策略一直以来都是嵌入式操作系统的研究中的一个热点。任务调度是嵌入式操作系统内核的关键部分，如何进行任务调度，使得各个任务能在其截止期限内得以完成是嵌入式操作系统的一个重要的研究领域。二，嵌入式实时操作系统绝大部分嵌入式系统都是实时系统，而且多是实时多任务系统。所谓“实时”,是指系统的正确性不仅仅依赖于计算的逻辑结果而且依赖于结果产生的时间16。结果产生的时间就是通常所说的截止期限(deadline),描述系统实时性的指标主要有： a,对紧急事件可预见性的快速响应； b,高度的可调度性，所谓调度性是指系统在任务时间需求能够满足下的最高资源利用率，也就是平均每秒的及时执行的任务数量；c,在暂时超负荷情况下的系统稳定性，即当系统超负荷运转导致不能满足所有任务的deadline需求时，仍然能够保证关键任务的deadline需求；2对于“实时”而言，截止期限的要求是必须得到满足的，但是区分具体应用场合，这种时限要求的严格程度又有所不同。如果这种要求是绝对的，即不满足截止期限的要求计算结果就毫无意义甚至可能造成无法预料的结果或系统致命的错误，那就称之为硬实时系统(Hard Real Time System)；在硬实时系统中如果出现了这样的情况就意味着巨大的损失和灾难，比如说日本福岛核电站中的堆芯温度控制系统如果没有对堆芯过热做出及时的冷却处理，后果不堪设想。当不满足截止期限的要求时计算结果的可调度性逐渐减弱但是并不足以造成严重后果，系统仍然继续调度直至任务完成，则称为软实时系统(Soft Real Time System)。软实时系统是指如果在系统负荷较重的时候允许发生错过deadline 的情况而且不会造成太大的危害比如说程控电话系统允许在100个电话中有一个接不通。硬实时系统和软实时系统的实现区别主要是，在选择调度算法上选择基于优先级调度的算法足以满足软实时系统的需求而且可以提供高速的响应和大的系统吞吐率,而对硬实时系统来说需要使用的算法就应该是调度方式简单反应速度快的实时调度算法了。三，优先级调度算法调度，也称dispatcher。这是内核的主要职责之一，就是确定该轮到哪个任务运行了。优先级抢占调度算法中，每个任务根据其重要程度的不同而被赋予一定的优先级。优先级抢占调度算法是指在系统运行过程中高优先级的任务可以中断低优先级的任务，让处在就绪态的优先级最高的任务先运行。目前多数实时内核采用优先级可抢占的调度算法，主要原因有以下几点：5首先，处理异常的任务可能需要抢占正在运行的任务，以便及时对异常做出响应；第二，任务的重要性不同，优先级可抢占使一些重要任务有可能抢占正在运行的任务；第三，允许任务抢占可得到更为有效的调度；根据不同的优先级分配方法，基于优先级的调度算法可以分为如下两种类型：1,静态调度：静态调度是在系统开始运行前进行调度的，严格的静态调度在系统运行时无法对任务进行重新调度。静态调度的目标是把任务分配到各个CPU，并对每一个CPU给出所要运行任务的静态运行顺序。静态调度算法实现简单，调度的额外开销小，在系统超载时可预测性好。但也具有很大的局限性，例如资源利用率低、受系统支持的优先级个数限制以及灵活性和自适应性差等。2,动态调度：在嵌入式实时系统中，动态调度依赖于任务的优先级。优先级可以静态分配或者依据不同的特征参数，如截止时间、空闲时间或关键性(即任务的重要程度)等进行动态分配。动态调度可以是抢占式的或非抢占式的。当检查到一事件时，动态抢占式算法立即决定是运行与此事件相关的任务，或继续执行当前的任务；对于动态非抢占式算法，它仅仅知道有另一个任务可以运行，在当前任务结束后，它才在就绪的任务中选择一个来运行。优先级调度算法在实时进程调度中使用很广泛，静态优先级调度算法根据应用的属性来分配优先级，其可控性较强，而动态优先级调度算法在资源分配和调度时具有更大的灵活性。一个好的调度模型和调度算法应该能够满足以下四个要求：1)易于使用(Ease To Use)：在系统中对于分配资源的各种任务，调度算法不需要大量的搜索操作就可以找到可行性调度；2)易于纠偏(Ease To Check)：任务程序发生改变时，调度不必从头做起；3)易于扩展(Ease To Extend)：一定程度上违反了系统的假设条件时，调度不应该改变；4)应确保可调度性(Must Guarantee Predictability)：在给定时间限定的条件下，调度必须能够保证所有任务的执行；静态优先级调度模型是实时系统中比较流行的一种调度模型。这种模型在系统运行前给每个任务分配固定的优先级和运行周期，当任务到达时向系统发出执行请求，这个请求必须在下一个周期开始之前完成，每个任务的执行情况相互独立。固定优先级调度模型可描述各种情况下系统的最坏运行情况，用定义好的算法来调度任务，而不需像循环调度模型那样对特定的情况用特定的调度方案，因此使系统便于维护和升级。5单调速率调度算法RMS（Rate Monotonic Scheduling）为每个周期进程指定一个固定不变的优先级，周期最短的进程优先级最高。周期越短，进程的到达频率越高，优先级也越高，这正是此策略被称为速率单调算法的原因。RMS算法也可用于多CPU环境,用于分配任务优先级。这种方法基于哪个任务执行的次数最频繁，执行最频繁的任务优先级最高。RMS的由来是从硬实时环境的初始定义开始的：1,所有的任务都是周期性的，各个任务请求的deadline呈周期性，同时具有恒定的时间间隔；2,所有任务都必须在下一次任务请求（即deadline）到来之前完成；3,所有的任务都是独立的，每一次任务请求不依赖于其他任务的执行或者初始化；4,每个任务都存在一个恒定且非时变的执行时间，即CPU不间断地执行该任务的时间；5,任何非周期的任务属于特殊任务，它们属于初始化或者是恢复错误的事件，仅当它们自身执行的时候才能取代周期性任务，同时非周期性任务不存在有deadline.RMS调度算法从何而来呢？假设使用1,2,m表示m个周期任务，任务申请周期和运行时间分别表示为T1,T2,Tm和C1,C2,Cm。定理1: 若所有进程在临界时刻启动的请求都能满足最后期限要求，则整个进程集可调度。即进程在临界时刻启动的请求响应时间最长。图1：在m执行之前的1运行1证明：如图1所示，假定m为1,2,m优先级最低的任务，在t1时刻任务m发出了运行请求，显然在图1所示的t1到t1+Tm时间间隔之间请求运行的周期性占先任务会推迟m完成时刻，除非m在t2到来之前完成它。当t2向t1方向移动的时候，m任务完成的时刻要么不变，要么被推迟，所以断定，在t2向t1方向无线趋近，直至与t1重合的时候，能够做到m完成任务的延时最长。 根据定理1可以假定，有两个任务1和2，对应的指定周期T1T2。假设1的优先级更高，此时根据定理1，可得：1T2T1 T2T1表示不超过T2T1的最大整数，在1)式中T2T1C1表示在T2时间段内，任务1的执行次数C1+C2T2; 1) 如果假设2的优先级更高，此时显然有：C1+C2T1; 2)因为有： T2T1C1+T2T1C2T2T1T1T2 2)式导出了1)式，换句话说，只要保证了T1Tj，交换i,j的优先级之后，不难发现结果的任务依然是可行的。由于其对任意式子都成立，于是命题成立。 因此，单调速率调度算法在静态优先级调度算法中属于最优算法，所以该算法的CPU使用率必然大于等于其余的静态优先级调度算法。 基于单调速率调度的算法中，定义U为Processor Utilization.(CPU的使用率)，由于CiTi为每一个任务i的CPU执行率，对系统有：U=i=1mCiTi;由于优先级调度算法最终结果是可以调度的，所以U必须存在着一个最小上界，那就是在这个最小上界之下的CPU的运行率的任务一定是可以调度的。 定理3:在两个固定优先级任务的情况下，经过计算，最小上界为U=2(212-1).1经推广到m个固定优先级的任务条件下，此时的最小上界为： U=m21m-1;1由罗必塔法则，求得极限为ln2。为直观表示，使用Matlab显示,根据Matlab R2008b版本的计算U-m的关系程序，代码如下：syms m y;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(processing rate of CPU); %y轴标注为CPU使用率grid on; %显示网格对应的U-m变化曲线如图2所示： 图2：U-m曲线图图2中显示该曲线无限趋近于ln2，即0.693。这就意味着，任何周期大小周期性任务一旦使用RMS调度算法均能满足调度要求，即在deadline之前完成。同时CPU总运行率不会超过最小上界0.693。需要指出的时候，它仅仅是必要条件，事实上该最小上确界是比较保守的，是绝对最坏情况下(pessimistic)的值。Lehoczky,Ding和Sha分析表明2，用RMS算法可调度CPU利用率高于0.9的周期进程集的情况并不罕见，且通过对均匀分布的任务，RMS算法平均可调度CPU使用率可达0.88.同时经过严格的证明，得出的任务可调度的充分必要条件：对任意 i ,1im;存在: tlTk1ki,1lTiTk;使得： j=1iCjtTj tTj为大于tTj的最小整数t 3）通常在实际设计实时操作系统中使用静态调度算法的时候，上面的测试需要在编译之前通过，方能确保在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，表示j=1iCjtTjtypedef 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为 CjtTj Result = sum_j:Result + my_result ; / 迭代求出 j=1iCjtTj 的值，存入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运行的时间调度任务都是可行的。硬件初始化操作系统初始化各任务参数初始化含Ci,Ti算法实现的流程图： STATIC_CHECK是否有误? Y N比较优先级并且排序 任务集是否可调度 挂起 N N Y生成代码并执行任务 查询任务集中各个任务的可调度性和CPU使用率 图3：RMS算法实现框图总而言之，算法实现的核心在于RMA分析（Rate Monotonic Analysis），通过对每个任务实现不等式3）的判定，对已知就绪的优先级最高的任务查询来它确定是否可以调度，从而实现算法。五，优缺点分析优点：1，RMS算法在静态调度中属于最优算法，任意的固定优先级算法能够实现的调度，在RMS算法中也能实现。尽管RMS算法的CPU利用率最小上确界为0.693，实际上的平均CPU利用率可达0.88。22，RMS算法可在运行前“离线”确定周期进程的执行顺序，运行时不必保留很多信息，同时可调度件测试简单，因此易于实现，运行时的调度开销相对较小，这是静态优先级调度算法对动态优先级调度算法的普遍优势。33，另外，优先级的预先确定也使系统过载的现象比较好控制。即使系统出现了暂时的过载，也能够确保最重要的任务的调度需求。4，在满足周期性任务的同时，仍有余力（约30%左右的CPU使用率）致力于对非周期性任务（例如系统和参数的初始化，错误处理）快速响应。同时支持扩展和固件升级，这对消费类产品而言意义重大。缺点：1，它的潜在CPU利用率小于动态优先级策略，在动态优先级的最优算法EDF(Earliest Deadline First)中最坏情况下的可调度CPU使用率为1.000。2，执行频率最高的任务并非最重要的任务。且较长周期的任务相对于较短周期的任务，更加容易错过deadline。33，由于RMS算法的静态调度属性，它运行时灵活性较差，自适应性弱。现今常用的实时性的操作任务，常常具有较灵活的使用率需求，但同时具有严格RMS算法完全建立在硬实时的条件下，主张所有被调度的周期性任务具有固定的优先级，这就显得强调在deadline之前的必须完成任务的思想超出了必要限度。具体而言，在特殊场合，一些任务的deadline是可以被错过的，只要在deadline前完成任务的要求能在一定百分率下得到满足。这种高灵活性使得RMS的最小上 界理论毫无提出之必要了。具体而言，在实时多媒体应用的调度之中，特点经常是：3a，单个应用的执行次数常常是不定的；b，错过deadline尽管是不愿意出现的情况，但它确实是非致命的错误，这样在实时多媒体系统中使用过分强调在deadline之前任务的RMS算法就多少显得有些不合时宜了，会导致较低的CPU使用率，从而浪费原本稀缺的资源；六，总结与展望单调速率优先级算法是基于硬实时条件需求下提