论文部分内容阅读
随着实时系统在各领域的广泛应用,任务调度技术在实时系统中扮演的角色越来越关键。针对实时系统多任务、多处理器和具有复杂优先约束等特点,论文在传统任务调度理论的基础上,重点研究了当代任务调度技术的新理论和新方法,特别是对不同环境和条件下的任务系统可调度性分析方法和调度算法进行了深入研究。 本文研究工作主要集中在以下几个方面: 针对速率单调分析技术在系统设计建模阶段缺乏对任务间优先约束关系及多处理器环境的考虑,提出基于可抢占时间Petri网的任务建模与检测方法。通过状态空间枚举和暂停变迁的概念,对具有优先约束的任务集在多处理器环境下进行建模与检测,并用仿真实例说明该方法在多处理器可抢占条件下,能够快速量化分析具有复杂属性的实时任务集合。 针对周期任务的可调度性判定问题,提出基于累积时间需求的任务可调度性分析方法和一种改进的抢占阈值任务响应时间分析方法。在对任务繁忙区的分析中,加入对任务释放抖动所需的额外响应时间的计算,提高了周期任务可调度性测试的精确性,解决了周期任务缺少通用可调度性分析方法的问题。 针对优先级驱动的任务调度过程中可能出现的非受控优先级逆转问题,提出一种基于抢占阈值理论的新型防范方法。在抢占阈值下重新定义了优先级逆转问题以及优先级继承协议和优先级限顶协议,通过加入有效优先级等概念,有效减少了任务抢占,避免发生优先级逆转现象。 针对任务具有优先约束的情况,研究了与或优先约束任务的调度算法。基于非精确模型强制任务概念,提出一种改进的顶点删除算法,解决了此类任务调度完成时间最小化问题。同时还提出一种与或优先任务最早开始时间算法,解决了时间跨度最小化问题。 针对实时系统多任务、多处理器特点,对多处理器环境下基于划分策略的任务分配算法可调度条件进行了分析,从任务分配调度算法所需处理器数量和任务集总利用率的角度比较多种任务分配算法的性能,并对算法利用率界限进行了分析。最后给出不同特征任务集选择不同分配算法的指导性原则。