基于多核处理器的最早截止期优先调度算法研究.pdf
摘要
实时调度算法作为实时系统中安排任务执行和资源分配的关键技术，旨在确保
所有任务能够在截止期前完成，以提高系统的可靠性和性能。硬实时调度算法广泛
应用于航空航天、汽车控制、工业自动化等对时间敏感的领域。随着无人汽车等相
关领域的不断发展，实时调度算法的应用环境也变得越来越复杂，这对实时调度算
法的性能提出了更高的要求。与此同时，为了满足人们对高性能计算的需求，实时
系统越来越多地采用多核处理器平台，这不仅提高了系统的整体性能和响应速度，
还增强了系统的可用性和容错性。但是多核处理器环境也比单核处理器更加复杂，
特别是异构多核处理器。因此，基于多核处理器的实时调度算法的研究非常重要，
特别是任务的优先级分配、处理器分配和任务抢占策略等因素会直接对实时系统的
可调度性、吞吐量和抢占延迟产生影响。
本文的工作内容包括以下部分：
(1)提出一种基于异构多核处理器平台的最慢速度拟合-最早截止期优先调度算
法。该算法对最早截止期优先调度算法的处理器分配策略问题进行研究，提出一种
将最高优先级的任务分配给执行速度最慢的空闲处理器的策略。然后通过理论证明
分析，得到该算法的可调度性分析结果。最后通过实验结果表明该算法在任务迁移
次数和有效处理器利用率方面具有良好的表现。
(2)提出一种最适抢占式-最早截止期优先调度算法。该算法针对同构多核处理
器平台上最早截止期优先调度算法的固定点抢占问题，提出一种高优先级任务选择
最合适的固定抢占点进行抢占的策略。通过该算法的可调度性分析结果和实验结果
证明该算法具有良好的可调度性和较少的任务抢占次数。
关键词：最早截止期优先调度算法；可调度性分析；多核处理器；任务抢占
I
目录
摘要I
ABSTRACTII
1绪论1
1.1研究背景与意义1
1.2国内外研究现状2
1.2.1实时调度算法2
1.2.2任务抢占3
1.3主要研究内容4
1.4本文结构5
2相关理论及系统模型7
2.1实时调度算法分类7
2.1.1静态调度和动态调度7
2.1.2抢占式调度，非抢占式调度和抢占受限式调度8
2.1.3同构多核处理器调度和异构多核处理器调度10
2.2系统模型及定义11
2.2.1任务模型11
2.2.2多核处理器平台12
2.2.3干扰，工作量和时间划分13
2.2.4可调度性分析15
2.3本章小结15
3基于异构多核处理器的SSF-EDF调度算法研究17
3.1引言17
3.2SSF-EDF调度算法17
3.2.1算法概述17
3.2.2算法示例18
3.3可调度性分析18
3.3.1下界19
3.3.2上界21
3.3.3可调度性分析24
3.4仿真实验与分析24
3.4.1实验方法25
3.4.2评价指标25
3.4.3实验结果与分析26
3.4.4实验总结31
3.5本章小结32
4基于同构多核处理器的BP-EDF调度算法研究33
4.1引言33
4.2BP-EDF调度算法33
4.2.1算法概述33
4.2.2算法示例34
4.3可调度性分析35
4.4仿真实验与分析39
4.4.1实验方法39
4