面向能耗优化的分布式实时系统调度算法研究

摘要

实时系统，特别是运行在安全关键应用领域的分布式实时系统，具有十分严格的及时性和可靠性要求。随着当前系统能耗已经成为计算系统的重要设计约束，如何在实时系统设计中进行能耗优化，已经成为实时系统研究中亟待解决的问题。实时调度是保障实时系统及时性和可靠性的重要方法。实时系统能耗优化调度将能耗优化机制与既有的实时调度策略相结合，从系统整体行为中挖掘其潜在的节能能力，已成为实时系统能耗优化设计最有效的策略。 本论文<'1>以分布式实时系统的能耗优化调度算法设计为方向，分别对分布式强实时系统的可调度性验证的形式化方法、实时任务调度、容错实时调度等关键问题进行了深入的研究，提出一系列相关方法和策略，以期进一步完善实时系统能耗优化调度方法。 实时系统的可调度性验证是确保实时系统满足及时性的重要手段，是实时系统设计中的关键技术。分布式实时系统大量复杂特征的引入，需要采用更严谨的形式化验证方法来判断实时系统是否满足定时约束。针对这一现状，本论文在对当前已有实时系统的形式化描述模型的表达能力和建模难度进行分析比较的基础上，提出了一种与频率相关的时间Petri网——FRTPN模型，以及基于该模型的可调度性验证方法。FRTPN引入变迁频率设置空间以及频率相关的静态引发时域，支持面向频率调节的能耗优化调度研究；同时它增加一类抑制弧支持容错机制的建模：另外，本论文在借鉴现有时间Petri网相关验证技术的基础上，给出了FRTPN模型的基于状态类的可调度性验证方法，并通过对检查点容错策略进行建模验证了FRTPN模型的有效性。 基于动态电压调整(DVS)技术的实时能耗优化调度方法已经成为实时系统能耗优化设计的最有效策略。针对现有分布式实时系统离线DVS调度算法采用的系统描述模型普遍缺乏全面准确刻画任务特征的能力，难以支持复杂分布式实时系统的可调度性验证的问题。本论文以FRTPN模型上的实时系统可调度验证为基础，提出了一种基于能耗/时间渐变率的启发式离线DVS调度算法，综合考虑了频率调整对系统能耗与松弛时间造成的影响，并以此为指导对待调频任务进行选择。另外，本论文还对任务分配进行了深入研究，提出了一种以任务利用率均匀化为目标的任务分配方法，以减少频率切换过程导致的能耗开销。在上述算法实现过程中，本论文根据FRTPN模型状态空间的变化规律，优化系统状态空间的生成过程，提高了算法的实现效率。容错技术是保障实时安全关键系统可靠性的重要手段，而基/副版本容错调度是目前解决分布式实时系统容错问题的有效方法。针对当前基/副版本容错实时调度中缺乏对能耗优化机制考虑的问题，本论文对基/副版本容错系统的DVS能耗优化调度展开研究。首先提出一种离线设置处理器执行频率的静态容错DVS调度算法，在此基础上提出能够在线收集动态松弛时间并进行再分配的动态容错DVS调度算法，最后提出一种以尽量推迟副版本释放时间为目标的基/副版本时限优化分配算法。模拟试验表明，上述算法能够有效地改善容错实时系统的能耗开销。 综上所述，本论文所做工作的主要贡献与创新特色体现在以下三个方面： (1)提出了一种能够有效对系统的能耗特征和容错机制建模的频率相关时间Petri网模型——FRTPN及其相关可调度性验证方法，能够满足复杂的分布实时系统的建模及面向能耗优化的实时系统可调度性验证需求。 (2)提出了一种以系统能耗/时间渐变率为指导的离线DVS调度算法(ETGBS)以及一种以任务利用率均匀化为目标的任务分配算法(UBTA)，有效降低系统的能耗开销。 (3)首次开展了基/副版本容错系统的能耗优化调度研究，提出了相应的静态DVS调度算法(PBSS)、动态DVS调度算法(PBDS)以及基/副版本的时限优化分配算法(PBDA)，在满足分布式容错实时系统的及时性、可靠性的前提下，降低系统能耗。

目录

文摘

英文文摘

论文说明：图表目录

中国科学技术大学学位论文相关声明

致谢

第1章绪论

1.1研究背景

1.2研究内容

1.3论文的组织结构

第2章实时系统低能耗调度理论

2.1实时调度理论

2.1.1基本概念

2.1.2实时调度算法

2.1.3实时调度算法研究现状

2.1.4实时系统的可调度性验证

2.2容错实时调度理论

2.2.1基本概念

2.2.2容错实时调度算法研究现状

2.3实时系统的能耗优化调度理论

2.3.1 CMOS电路功耗模型

2.3.2能耗优化技术

2.3.3实时系统的能耗优化调度

2.3.4实时能耗优化调度算法研究现状

2.3.5容错实时系统能耗优化调度问题

2.4本章小结

第3章分布式实时系统可调度性验证的形式化方法研究

3.1实时系统形式化描述模型概述

3.2频率相关的时间Petri网(FRTPN)

3.2.1问题的提出

3.2.2模型定义

3.2.3 FRTPN模型上的能耗分析

3.3基于FRTPN模型的实时系统可调度性验证

3.4分布式容错实时系统的FRTPN模型

3.4.1分布式实时系统

3.4.2基于检查点的容错机制

3.5本章小结

第4章基于FRTRN模型的面向能耗优化的调度

4.1实时系统能耗优化调度概述

4.2模型描述

4.2.1系统模型

4.2.2能耗模型

4.3 FRTPN模型上的DVS调度

4.3.1能耗渐变率驱动的DVS调度算法

4.3.2存在的问题

4.3.3基于能耗/时间渐变率的DVS调度算法

4.4 FRTPN模型上的任务分配

4.4.1存在的问题

4.4.2设计思路

4.4.3算法描述

4.5算法的优化实现

4.6模拟实验及结果分析

4.7本章小结

第5章面向能耗优化的容错实时调度

5.1问题的提出

5.2系统模型和问题描述

5.2.1系统模型描述

5.2.2问题描述与分析

5.3基/副版本静态DVS调度

5.3.1设计思想

5.3.2静态DVS调度算法

5.4基/副版本动态DVS调度

5.4.1基/副版本任务执行频率的设置

5.4.2松弛时间的回收

5.4.3动态DVS调度算法

5.4.4算法的可调度性分析

5.5基/副版本时限的优化分配

5.5.1设计思想

5.5.2算法描述

5.6模拟实验及结果分析

5.6.1实验方案

5.6.2实验结果分析

5.7本章小结

第6章总结与展望

6.1论文工作总结

6.2进一步工作

参考文献

攻读学位期间发表的学术论文目录