论文部分内容阅读
实时系统,特别是运行在安全关键应用领域的分布式实时系统,具有十分严格的及时性和可靠性要求。随着当前系统能耗已经成为计算系统的重要设计约束,如何在实时系统设计中进行能耗优化,已经成为实时系统研究中亟待解决的问题。实时调度是保障实时系统及时性和可靠性的重要方法。实时系统能耗优化调度将能耗优化机制与既有的实时调度策略相结合,从系统整体行为中挖掘其潜在的节能能力,已成为实时系统能耗优化设计最有效的策略。本论文以分布式实时系统的能耗优化调度算法设计为方向,分别对分布式强实时系统的可调度性验证的形式化方法、实时任务调度、容错实时调度等关键问题进行了深入的研究,提出一系列相关方法和策略,以期进一步完善实时系统能耗优化调度方法。实时系统的可调度性验证是确保实时系统满足及时性的重要手段,是实时系统设计中的关键技术。分布式实时系统大量复杂特征的引入,需要采用更严谨的形式化验证方法来判断实时系统是否满足定时约束。针对这一现状,本论文在对当前已有实时系统的形式化描述模型的表达能力和建模难度进行分析比较的基础上,提出了一种与频率相关的时间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),在满足分布式容错实时系统的及时性、可靠性的前提下,降低系统能耗。