多核平台上混合关键性任务实时调度算法研究

论文摘要

多核处理器架构技术在现代嵌入式系统的设计与实现当中的应用越来越广泛,以满足各种应用日益增长的高性能和低功耗的需求。多处理器平台强大的计算能力为将多个不同关键性级别的功能子系统集成到统一的共享资源平台提供了支持。正因为此,混合关键性系统也己成为现代嵌入式实时系统设计的流行趋势。在过去的几十年里,传统的实时任务系统在单核处理器平台和多核处理器平台上都取得了很大的发展。相比之下,混合关键性系统的调度问题,无论是从理论方面还是系统的实际应用方面都面临着巨大的挑战。混合关键性系统的调度问题,即使在单处理器平台中都极具挑战性,在多处理器平台则更为困难。目前关于混合关键性系统调度问题的研究主要还是集中于单处理器平台,但是现在很多应用已经或者即将运行在多处理器平台上,因此多处理器平台上混合关键性系统调度问题的研究己成为迫切需求。本文将目前资源利用率最高的单处理器混合关键性调度算法EDF-VD扩展到多处理器平台中。首先本文结合传统的划分调度策略提出了适用于多处理器混合关键性系统的MC-PEDF划分调序算法。尽管比之前的算法有更好的可调度件能,但分析发现传统的划分策略不能有效地平衡不同关键性级别下的负载,故其不完全适用于混合关键性系统。为了克服传统策略的不足,本文提出了新型的划分调度策略OCOP（One Criticality One Partition）。OCOP允许系统在关键性模式切换时对实时任务集进行重新划分,进而更好的平衡各个处理器在不同关键性模式中的资源利用率。基于OCOP,本文提出了第二个划分调度算法MC-MP-EDF。基于随机生成任务集的仿真实验结果表明,相较于MC-PEDF和已有的算法,MC-MP-EDF能够显著的提高系统的可调度性,尤其是在处理器数量较多的系统中。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 课题背景
• 1.2 研究目标和意义
• 1.3 国内外研究现状
• 1.4 论文的组织结构
• 第2章 相关理论与技术
• 2.1 实时系统相关理论
• 2.1.1 实时系统任务模型和基本概念
• 2.1.2 实时任务分类
• 2.2 多处理器调度算法的基本理论
• 2.3 可调度性分析
• 2.3.1 可调度性判定方法
• 2.3.2 调度算法的质量评价
• 2.4 需求界限函数
• 2.5 混合关键性问题的提出
• 2.6 现有理论成果概述
• 2.6.1 传统任务系统多处理器调度
• 2.6.2 混合关键性任务实时调度
• 2.7 本章小结
• 第3章 混合关键性系统模型
• 3.1 混合关键性系统的模型
• 3.2 混合关键性系统的运行时行为
• 3.3 混合关键性系统可调度性
• 3.4 调度算法的可持续性
• 3.5 遗留作业
• 3.6 混合关键性系统的DBF函数
• 3.6.1 混合关键性系统DBF函数定义
• 3.6.2 混合关键性任务相对截止期的调整
• 3.7 本章小节
• 第4章 基于传统划分策略的MC-PEDF算法
• 4.1 多处理器划分调度的基本方法
• 4.1.1 混合关键性任务的排序
• 4.1.2 处理器的选择策略
• 4.2 MC-PEDF算法
• 4.2.1 MC-PEDF的划分算法
• 4.2.2 MC-PEDF的运行时调度算法
• 4.2.3 MC-PEDF的时间复杂性和正确性分析
• 4.3 本章小结
• 第5章 多次划分策略和MC-MP-EDF算法
• 5.1 传统划分策略的局限性
• 5.2 混合关键性模型中的新型划分策略OCOP
• 5.3 MC-MP-EDF算法描述
• 5.3.1 MC-MP-EDF的划分算法
• 5.3.2 MC-MP-EDF的运行时调度算法
• 5.3.3 算法正确性分析
• 5.3.4 算法复杂度分析
• 5.4 本章小结
• 第6章 实验测评及分析
• 6.1 随机任务集生成算法
• 6.2 实验结果分析
• 6.3 本章小结
• 第7章 结论与展望
• 7.1 结论
• 7.2 未来作业与展望
• 参考文献
• 致谢
• 科研项目和论文发表情况