单处理器环境下实时调度算法研究

论文摘要

随着网络、通信、多媒体计算的迅猛发展,嵌入式系统得到了广泛的应用,实时系统的应用也逐渐从传统的科学研究、国防、工业控制等领域扩展到人类社会的方方面面。实时系统的研究主要集中在两个最关键的问题上,一个是对实时调度算法的研究,另一个是对实时任务集可调度性判定的研究。本文对应分别提出一种硬实时混合调度的可调度性判定算法IISS(Improved Idle Slack Stealing)和一种改进的最小空闲时间优先(LSF)调度算法DPTLSF(Dynamic Preemption Threshold LSF)。IISS算法主要是解决硬实时周期任务和偶发任务混合调度情况下的可调度性判定问题,以保证偶发任务的可调度性。基于调度与逆调度的概念,分析了最早截止期优先(EDF)调度中任意时刻的最大可挪用时间的计算方法；IISS算法将偶发任务安排在周期任务的执行空隙与推迟周期任务执行后出现的可挪用时间中执行。根据不同偶发任务特征,确定一个动态挪用时间点Tdynamic,得出偶发任务可调度性判定的充分条件。仿真结果表明,IISS算法的预测准确率比已有算法ISS有明显提高,并且对于不同实时任务集的判定更具灵活性。DPTLSF算法是针对经典LSF调度算法中任务上下文切换频繁及任务截止错失率较高的缺点提出的。通过分析不同空闲时间的任务抢占对LSF调度算法性能的不同影响,基于抢占阈值策略,设计合理的动态抢占阈值,来避免任务切换频繁造成的“颠簸“现象的发生。仿真结果表明,改进后的算法在不同处理器负载、不同周期任务数情况下,都能够显著地减少上下文切换次数,降低任务集的截止期错失率。

论文目录

• 摘要
• Abstract
• 插图索引
• 附表索引
• 第1章 绪论
• 1.1 实时调度的研究背景和研究意义
• 1.1.1 实时系统的应用背景
• 1.1.2 实时调度
• 1.1.3 研究目的与研究意义
• 1.2 实时调度研究现状
• 1.2.1 硬实时周期任务和非周期任务的混合调度算法研究现状
• 1.2.2 最小空闲时间优先（LSF）调度算法研究现状
• 1.3 本文的研究内容及主要工作
• 1.4 论文组织结构
• 第2章 基本理论与相关研究
• 2.1 实时系统相关理论
• 2.1.1 实时系统定义
• 2.1.2 实时系统的特点
• 2.1.3 实时系统分类
• 2.2 实时任务调度基础知识
• 2.2.1 实时任务调度理论的产生
• 2.2.2 实时任务的分类
• 2.2.3 实时调度的基本概念和相关术语
• 2.2.4 实时调度算法分类
• 2.2.5 实时调度基本策略
• 2.3 经典实时调度算法
• 2.3.1 周期任务常用调度算法
• 2.3.2 周期任务与非周期任务混合调度常用算法
• 2.4 任务集可调度性分析
• 2.4.1 RM算法的可调度性判定
• 2.4.2 EDF算法可调度性判定
• 2.4.3 静态优先级周期任务调度算法可调度性判定
• 2.5 本章小结
• 第3章 硬实时周期任务与偶发任务混合调度的可调度性判定
• 3.1 引言
• 3.2 系统模型
• 3.3 问题描述
• 3.4 EDF算法调度中空闲时间分布
• 3.5 EDF算法调度中可挪用时间
• 3.6 EDF算法调度中的最大可挪用时间
• 3.7 IISS算法
• 3.7.1 硬实时周期任务与偶发任务混合调度的可调度性判定分析
• 3.7.2 IISS算法设计
• 3.8 仿真实验
• 3.9 本章小结
• 第4章 基于动态抢占阈值的LSF调度算法研究
• 4.1 引言
• 4.2 LSF调度算法分析
• 4.2.1 任务模型定义
• 4.2.2 LSF调度算法
• 4.2.3 LSF调度算法的颠簸现象
• 4.3 抢占阈值策略
• 4.4 LSF算法改进
• 4.4.1 优先级的分配
• 4.4.2 抢占阈值的确定
• 4.5 仿真运行模型
• 4.6 算法实现分析
• 4.6.1 数据结构
• 4.6.2 任务产生器
• 4.6.3 任务调度器
• 4.6.4 完成与夭折策略
• 4.6.5 算法复杂度分析
• 4.7 仿真实验
• 4.7.1 仿真条件
• 4.7.2 两种性能指标
• 4.7.3 仿真结果与分析
• 4.8 本章小结
• 结论
• 参考文献
• 致谢
• 附录A 攻读硕士学位期间所发表的学术论文目录