文档介绍：中国科学技术大学博士学位论文考虑缓存预热时间的多核实时调度算法和分析姓名:盛伟申请学位级别:博士专业:计算机系统结构指导教师:周学海;李曦201105摘要摘要由于功耗和散热的问题,处理器的设计正往多核方向发展。多核处理器不仅应用在~般的计算机系统中,而且正不断的应用到嵌入式系统中。这样的系统往往也是实时系统。在实时系统中,计算的正确性不仅依赖于结果的正确性而且依赖于结果产生时间的正确性。多核处理器带给实时系统的不仅是高效的处理能力丽且还有复杂的任务调度。在单处理器系统中,计算任务最坏情况执行时间(WCEZ)时,一般认为任务的缓冲行都在缓存中,通过静态分析用缓存延迟得到。然而在多核处理器系统中,有的核上的缓存并没有任务的缓冲行。当任务运行在这样的核上时,会增大任务的WCET,增大的这部分时间称为缓存预热时间。解决缓存预热时间对多核实时调度产生的影响是一个重要的问题。可调度性分析是研究实时调度的重要手段,主要有两种方法:模拟和利用率的边界测试。模拟的方法尽管实现简单,但它只检测了系统运行的有限路径,所以得到的可调度任务集数目并不可靠。利用率边界测试往往只能推导出充分条件,由此获得的可调度任务集数目较为悲观。由于这些原因,研究者提出使用模型检测的方法,对多处理器调度算法进行可调度性分析。但他们都没有考虑缓存预热时间对可调度性分析的影响。针对这一问题,本论文基于模型检测,提出一种考虑了缓存预热时间的可调度性分析的方法,并以静态优先级调度算法单调速率(I洲)为例,说明了这种方法的有效性。在采用多核gM算法的调度系统中,缓存预热时间会导致一些任务集错失截止时间。为了降低缓存预热时间带来的不可预测性,研究者提出新的硬件架构PushBlock,预先将任务的缓冲行迁移到目的核缓存中。当任务在目的核上运行时,就不会产生缓存预热时间。然而,现有的调度算法并不支持这种架构。针对这个问题,本论文以静态优先级调度算法RM为基础,结合这种新架构所提供的功能,给出了三种策略,提出了一个新的静态优先级调度算法,提高了系统实时性,减少了错失截止时间的任务集。在静态优先级调度中,系统运行时,任务优先级是固定的。这可能导致一个高优先级任务长时间占有CPU,而低优先级的任务必须等待。因此,产生了动态优先级调度。在系统运行时,它可以改变任务的优先级,增强了对环境的调整能力。不幸的是缓存预热时问仍然会导致采用了动态优先级调度算法的系统错失截止时间。另外,目前的多核动态优先级调度算法并没有建立在新架构PushBlock上,无法利用预迁移机制提高算法的性能。针对这些问题,本论文以经典摘要的动态优先级调度算法最短截止时间优先(EDF)为基础,提出了适应缓存预热时间的动态优先级调度算法。通过实验,展示了新算法良好的性能。综上所述,本论文研究中所做出的主要贡献体现在以下三个方面:1)针对以往的可调度性分析没有考虑缓存预热时间的问题,提出了基于模型检测,考虑缓存预热时间的可调度性分析方法,并以RM算法为例,验证了方法的有效性。2)针对缓存预热时间导致经典的静态优先级调度算法RM实时性降低的问题,给出了降低缓存预热时间的三种策略,,既保留了RM算法的良好性能,同时提高了适应缓存预热时间的能力。3)针对缓存预热时间导致经典的动态优先级调度算法EDF实时性降低的问题,,与EDF算法相比增强了算法的实时性。关键词:实时系统,多核调度,可调度性分析,任务迁移,缓存预热时间AbstractABSTRACTAsthepowerconsumptionandthermaldissipationproblems,,andareconstantlyappliedintoembeddedsystems,whichareusuallyreal-timesystems。Inthesesystems,—,(WCET、