基于DNA-GA的最早截止期限优先调度算法优化

摘要

实时调度算法是嵌入式实时系统设计和实现的关键问题之一，也是保障实时系统两个必备特性(时限性和可靠性)的重要方法，是实时系统中重要而活跃的研究领域。 在众多的实时调度算法中，速率单调(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遗传算法在嵌入式实时调度算法领域的运用。

目录

文摘

英文文摘

声明

第一章绪论

1.1选题背景

1.2实时调度研究现状

1.3论文的组织结构

第二章实时系统

2.1实时系统的特性及其分类

2.1.1实时系统特性

2.1.2实时系统分类

2.2嵌入式系统

2.3实时操作系统

2.3.1实时操作系统及其一般特征

2.3.2实时操作系统的发展

2.4几个代表性的嵌入式实时操作系统

第三章实时调度

3.1实时调度相关理论

3.1.1实时调度模型

3.1.2实时调度基本理论

3.1.3调度策略

3.1.4实时调度方法的分类

3.2 RM与EDF实时调度算法

3.2.1 RM调度算法

3.2.2 EDF调度算法

3.3 RM与EDF算法的调度实例

3.3.1 RM调度算法的调度

3.3.2 EDF算法的调度

第四章DNA遗传算法

4.1遗传算法

4.1.1遗传算法的生物学基础及特点

4.1.2遗传算法的应用

4.1.3遗传算法的基本概念

4.1.4遗传算法的操作

4.1.5遗传算法与调度

4.2 DNA计算的生物学基础

4.3 DNA遗传算法

4.3.1 DNA遗传算法基本概念

4.3.2 DNA遗传算法的假设

4.3.3 DNA遗传算法的结构

4.3.4 DNA遗传算法的优点

第五章抢占式EDF调度算法优化

5.1抢占式EDF调度算法模型

5.2优化EDF调度算法

5.3实验

5.3.1实验一

5.3.2实验二

第六章总结与展望

参考文献

致谢

攻读学位期间发表的学术论文