本科毕业论文： RM调度算法实现.doc

中文摘要 实时系统为了提供实时性的支持，必须对CPU和其他资源进行有效的调度和管理。在多任务实时系统中，资源的调度和管理更加复杂。任务调度算法ABSTRACT In order to provide real time supports,real time system must schedule and monitor efficiently with CPU and other resources.In real time system with more than one task,the scheduling and monitoring are more complicated.Using different task scheduling algorithm for different real time system to produce suitable schedule,is good for advance the work efficiency of real time system.So, whether having suitable schedule algorithm，is very important for real time system. This Paper will introduce a classical static-priority scheduling algorithm——RM(Rate-Monotonic) algorithm. RM algorithm assigns the priority to the task basis on the period of the task,the shorter the period of the task,the higher priority it has. With the experience of this algorithm using MFC,the content of RM algorithm will be incarnated in the code. This Paper will have particular expatiation and analysis on RM algorithm’s principium, algorithm design and implementation,and mathematics base. Key Words：RM algorithm，Real-time System，task scheduling 1. 绪 论 实时系统概述 随着计算机与信息技术的发展，实时系统在日常工作和生活中占有越来越大的比重，广泛应用于国防、科研、交通、通信等各个重要领域，如在电子制导武器中，利用实时系统对搜集的信息进行实时的处理，然后控制导弹的飞行方向，从而有效地摧毁目标。在通讯网络系统中，专用交换机、路由器、硬件防火墙等设备，通常是通过实时系统来实现数据信息的实时处理。 实时系统不仅应用广泛，而且要求严格。POSIX 1003.b中指出，实时系统指系统能够在限定的响应时间内提供所需水平的服务。Donald Gillies 提出了一个对实时系统更为通俗的定义：一个实时系统是指计算的正确性不仅取决于程序的逻辑正确性，也取决于结果产生的时间，如果系统的时间约束条件得不到满足，将会发生系统出错。实时系统应用的特殊性就决定了其实现的严格性，这种约束主要的是时限约束。 时限约束是指在规定的时间内，完成相关的计算任务。实时系统的这种实时性在很大程度上取决于实时任务调度算法。实时调度是指在有限的系统资源（如 CPU 等）下，为一系列任务决定何时以及在哪个处理器上运行，并分配任务运行所需要的资源，以保证其时间约束（即截止期限）、时序约束和资源约束得到满足。实时调度算法的好坏，直接影响到系统的吞吐量（单位时间内系统可以处理任务的数量）、系统的响应时间，甚至是任务能否得以成功调度。对实时调度算法的研究，是实时领域的一个重要的研究课题。 实时调度算法总体上可以分为两类：静态调度算法和动态调度算法。静态调度算法是一种可预测的方法，要求对任务集和任务的约束有确定的了解，如任务的截止期限、执行时间、周期、时序约束等。Liu 和 Layland 提出的速率单调（Rate Monotonic—RM）算法及其以后的一系列扩展算法是静态调度算法的典型代表。在动态调度算法领域，最早截止期限优先（EarliestDeadlineFirst—EDF）算法占有重要的地位。当前，在国内外学术界对实时调度算法的研究主要针对硬实时与软实时相结合的任务调度、在多种条件制约下的任务调度、多处理器调度等，他们对于各自的特定的实时系