论文摘要
实时调度算法是嵌入式实时系统设计和实现的关键问题之一，也是保障实时系统两个必备特性（时限性和可靠性）的重要方法，是实时系统中重要而活跃的研究领域。在众多的实时调度算法中，速率单调（Rate Monotonic，RM）和最早截止期限优先（Earliest Deadline First，EDF）分别是静态调度和动态调度领域中经典的调度算法。RM算法属于静态调度算法，在系统运行前决定任务的调度，实现简单，在满足前提条件的情况下可以保证实时任务集的成功调度。EDF算法属于动态调度算法，在系统运行时决定任务的调度，CPU利用率可以达到100％（理想情况下）。虽然RM和EDF算法以其各自所具备的优良性能在嵌入式实时系统中得到了广泛应用，但是我们也不能忽视它们本身存在的实时性问题。本文是在考虑“任务调度开销时间”的情况下，通过优化EDF调度算法中各个任务的启动时间来提高EDF调度算法的实时性能的。首先介绍实时调度算法的应用背景：实时系统、嵌入式系统、实时操作系统和嵌入式实时操作系统。接着对现有的实时调度模型、实时调度基本理论、调度策略和实时调度算法进行了分析和研究。对RM和EDF实时调度算法进行了详细分析，并举例说明了它们的调度过程。然后介绍了本文用到的优化算法—DNA遗传算法（Deoxyribonucleic acid Genetic Algorithm，DNA-GA），及其基本理论和操作方法，并说明了DNA（Deoxyribonucleic acid）算法的生物学基础和遗传算法的基本理论。最后，通过使用DNA-GA对EDF调度算法中各个任务的启动时间进行离线优化，离线计算各实时任务的启动时间，运用这些优化的启动时间作为在线实时系统使用EDF调度算法的参数进行实时任务调度，以此来提高实时系统的实时性能。本文模拟了基于DNA-GA的最早截止期限优先调度算法的优化调度，并比较了优化前后因抢占引起的调度开销。实验结果表明：使用DNA遗传算法可以对实时任务的启动时间进行优化，可以减少实时任务因抢占引起的调度开销。说明了使用DNA遗传算法对EDF调度算法进行优化的可行性和有效性。该结论对实时调度算法的研究和使用有一定的理论和实践意义。本文的创新之处在于使用DNA遗传算法对EDF调度算法中各个任务的启动时间进行优化，实现了DNA遗传算法在嵌入式实时调度算法领域的运用。