单调速率调度算法RMS..docxVIP

嵌入式系统单调速率调度算法的特点及实现余蓝涛(天津大学 精密仪器与光电子工程学院 天津 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一，引言现在嵌入式系统得到高速的发展。它的发展为几乎所有的电子产品注入了新的活力。它在国民经济各领域和我们日常生活中发挥了越来越重要的作用。嵌入式系统在航天、军事、工控以及家电等方面得到了广泛应用。囿于体积，能耗，价格等方面的约束，嵌入式系统处理器速度比较慢，存储器容量也有限。而传统的操作系统为了取得较高的性能，要求硬件设备具有强大的处理能力，大容量的存储能力以及对网络的支持功能，这使得传统的操作系统难以简单地移植到嵌入式系统中。这就导致了嵌入式操作系统由于受到系统的限制，往往内存资源都非常的有限，要求操作系统的内核都非常的精炼，对于系统中的资源操作系统内核需要进行统一的分配和调度。嵌入式操作系统调度策略一直以来都是嵌入式操作系统的研究中的一个热点。任务调度是嵌入式操作系统内核的关键部分，如何进行任务调度，使得各个任务能在其截止期限内得以完成是嵌入式操作系统的一个重要的研究领域。二，嵌入式实时操作系统绝大部分嵌入式系统都是实时系统，而且多是实时多任务系统。所谓“实时”,是指系统的正确性不仅仅依赖于计算的逻辑结果而且依赖于结果产生的时间[1][6]。结果产生的时间就是通常所说的截止期限(deadline),描述系统实时性的指标主要有： a,对紧急事件可预见性的快速响应； b,高度的可调度性，所谓调度性是指系统在任务时间需求能够满足下的最高资源利用率，也就是平均每秒的及时执行的任务数量；c,在暂时超负荷情况下的系统稳定性，即当系统超负荷运转导致不能满足所有任务的deadline需求时，仍然能够保证关键任务的deadline需求；[2]对于“实时”而言，截止期限的要求是必须得到满足的，但是区分具体应用场合，这种时限要求的严格程度又有所不同。如果这种要求是绝对的，即不满足截止期限的要求计算结果就毫无意义甚至可能造成无法预料的结果或系统致命的错误，那就称之为硬实时系统(Hard Real Time System)；在硬实时系统中如果出现了这样的情况就意味着巨大的损失和灾难，比如说日本福岛核电站中的堆芯温度控制系统如果没有对堆芯过热做出及时的冷却处理，后果不堪设想。当不满足截止期限的要求时计算结果的可调度性逐渐减弱但是并不足以造成严重后果，系统仍然继续调度直至任务完成，则称为软实时系统(Soft Real Time System)。软实时系统是指如果在系统负荷较重的时候允许发生错过deadline 的情况而且不会造成太大的危害比如说程控电话系统允许在100个电话中有一个接不通。硬实时系统和软实时系统的实现区别主要是，在选择调度算法上选择基于优先级调度的算法足以满足软实时系统的需求而且可以提供高速的响应和大的系统