实时系统调度算法的抢占控制模型及其遗传算法实现

论文摘要

嵌入式实时系统主要面向现实世界中与时间因素相关的应用需求,在工业控制、航空航天和军事设备等众多领域里有着广泛的应用,它所关注的不仅是计算结果在逻辑上的正确性,而且还有输出结果时间上的及时性。另外,嵌入式实时系统的处理能力和内存容量往往是有限的,这需要调度算法能恰当地排列任务执行顺序,在保证系统可调度性的同时使用更少的资源。基于上述原因,本文首先根据实时系统的特点和需求对现有调度算法存在的缺点和不足进行分析,提出了一种基于非抢占时间片的抢占控制优化模型。该模型以任务的最差响应时间小于其时限作为任务可调度性判断的充要条件,因此该模型应该能够在保证任务可调度性的同时,使任务集合在执行期间发生的总抢占次数最小,其结果就是既保证了任务集合的可调度性又降低了由于抢占而引起的资源开销。然后,使用遗传算法对优化模型进行了脱机实现。为了提高遗传搜索的效率,本文中遗传算法初始个体的设计采用了以次优值为启发性初值的方法。由于遗传运算过程中会产生非法解(即产生的任务抢占次数使整个任务集合不可调度),本文采用了一种惩罚函数的方式来解决此问题。最后,本文通过实测对计算结果进行检验和分析。进行实验的软件平台为嵌入式实时操作系统WebitOS。通过在WebitOS上使用C语言编程将遗传算法计算出来的结果加以实现,同时创建大量的任务在不同调度算法下对其进行检验。结果显示基于非抢占时间片的抢占控制优化模型确实能够在保证任务的可调度性、实时性的同时,有效减少不同调度算法下任务发生抢占的次数。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 嵌入式实时系统
• 1.2 嵌入式实时系统的一般特点
• 1.2.1 实时性
• 1.2.2 资源有限
• 1.3 抢占控制的意义
• 1.4 论文的结构安排
• 第二章 嵌入式实时系统的一般模型
• 2.1 周期性任务模型
• 2.1.1 任务的时间参数
• 2.1.2 任务的执行时间
• 2.1.3 固定和抖动的释放时间
• 2.1.4 非周期和偶发任务
• 2.1.5 任务特征的符号化表示
• 2.2 调度算法
• 2.2.1 调度概述
• 2.2.2 调度算法分类研究
• 2.2.3 经典调度算法可调度性分析
• 2.3 小结
• 第三章 基于时间片的抢占控制模型
• 3.1 带有抢占次数约束的任务模型
• 3.2 实时调度的抢占控制模型
• 3.2.1 固定优先级调度的抢占控制优化模型
• 3.2.2 动态优先级调度的抢占控制优化模型
• 3.3 小结
• 第四章 抢占控制模型的遗传算法实现
• 4.1 遗传算法介绍
• 4.1.1 遗传算法的发展过程
• 4.1.2 遗传算法的基本原理
• 4.2 遗传算法与抢占控制优化模型结合的可行性分析
• 4.2.1 遗传算法的特征及优缺点
• 4.2.2 选择遗传算法的理由
• 4.3 抢占控制优化模型的遗传算法程序实现
• 4.3.1 总体设计
• 4.3.2 初始种群的产生
• 4.3.3 染色体的编码及适应度计算
• 4.3.4 遗传算子
• 4.3.5 约束条件及罚函数
• 4.4 小结
• 第五章 实验设计与结果分析
• 5.1 实验平台环境
• 5.1.1 硬件平台
• 5.1.2 软件平台
• 5.2 定时器模块的配置
• 5.2.1 工作模式的选择
• 5.2.2 T/C工作过程分析
• 5.3 抢占控制优化模型的操作系统实现
• 5.3.1 总体设计
• 5.3.2 进程控制块数据结构
• 5.3.3 定时器初始化函数
• 5.3.4 进程创建函数
• 5.3.5 定时器中断处理函数
• 5.4 实验结果分析
• 5.4.1 算法性能分析
• 5.4.2 抢占次数的优化效果
• 5.5 小结
• 第六章 总结与展望
• 参考文献
• 致谢
• 攻读硕士期间发表的论文