论文部分内容阅读
随着多核处理器的飞速发展,越来越多的嵌入式实时系统设计者选择多核处理器作为硬件平台,以满足各类应用不断增长的高性能与低功耗的需求。更高精确度和更高效率的多核处理器实时调度技术已成为这一发展趋势的迫切需要。在过去的四十年中,面向单核处理器的实时调度技术已经发展得比较成熟。相比之下,面向多核并行体系结构的实时调度,无论从理论方面还是系统实现方面依然面临着巨大挑战。基于这一背景,本文研究面向多核体系结构的实时调度技术,旨在突破多处理机模型调度中的重要基本理论难题,并解决在多核平台上构建实时系统的实际挑战。多处理机调度主要分为全局调度和划分(及半划分)调度。本文分别针对这两类调度算法中的关键理论问题给出了新的理论结果(包括全局调度的关键时刻、全局调度的有限响应时间条件、半划分调度中的资源利用率界限),并提出了一系列调度技术来提高多处理机系统的平均实时性能(包括不可抢占全局调度技术、任务实例级别优先级分配技术、半划分调度中基于响应时间的划分技术、半划分调度中参数化的资源利用率界限)。主要贡献点概括如下:(1)建立了多处理机全局调度近似关键时刻的概念,在此基础上提出了一种针对可抢占全局固定优先级调度的响应时间分析新技术,在不牺牲分析效率的前提下大幅度提高了分析的精确度。在这一理论基础之上,建立了可抢占全局固定优先级调度下任务具有有限响应时间的一般性条件。(2)提出了一种新的针对不可抢占全局固定优先级调度的可调度性分析技术,并结合大量的模拟实验,推翻了从单处理机实时调度中衍生出来并被普遍接受的关于“可抢占调度的实时性能总是好于不可抢占调度”的错误观念,并对这种现象进行了深入分析,系统分析了如何利用不可抢占调度来提高系统的实时性能。(3)提出了一种固定实例优先级的全局调度算法及相应的分析技术。该算法结合了固定任务优先级分配与最早截止期优先(EDF)两类算法的优点,通过发掘任务实例之间的优先级顺序来大幅度提高系统的可调度性。该算法在设计阶段仅对有限个具体的任务实例进行优先级分配,以构建运行时系统的负载抽象表达;在运行时,通过复用上述优先级分配方案实现高效的在线调度。(4)将单处理机调度中著名的Liu&Layland资源利用率界限推广到多处理机调度模型,解决了实时调度领域一个近四十年悬而未决的重要理论问题。提出一种具有Liu&Layland资源利用率界限的半划分调度算法,使用与装箱问题中的“最坏适用递减”启发式算法类似的任务划分顺序,来使任务切割只发生在高优先级任务中,并利用高优先级任务具有较大松弛时间的特性,来抵消任务切割所带来的负载增长效应。(5)将单处理调度中大部分的参数化资源利用率界限扩展到了多处理机调度。提出一种具有参数化资源利用率的半划分调度算法,该算法在大部分情况下满足单处理机RMS调度中任意已知的参数化资源利用率界限。此外,该算法由于使用响应时间分析来决定一个处理器上可以接纳的最大负载,因此获得了比现有算法更好的平均实时性能。此外,本文还研究了面向共享缓存的多核实时调度技术。多核处理器的一个全新特性是存在大量的片上共享硬件资源(如共享缓存等),对共享资源的并行访问使得一个任务的执行时间依赖于其它同时执行的任务,因此动摇了传统实时调度中“已知任务的最坏情况执行时间”这一基本假设,为多核实时调度及可调度性分析带来了前所未有的挑战。本文提出了一种全新的共享缓存敏感的多核实时调度及可调度性分析技术。该方法首先通过划分共享缓存来减少任务间干涉从而提高了系统的时间可预测性,在此基础上,从“处理机”和“缓存”两个维度上解决资源分配与调度的问题,并相应的给出了两种可调度性判定的方法。综上,本文研究了面向多核处理器的实时调度问题,内容涵盖了多个调度算法种类(全局与划分,可抢占与不可抢占,固定任务优先级与固定实例优先级)。本文的研究成果为面向多核处理器的实时系统的设计与分析提供了重要的理论依据,并对解决在多核系统上部署实时系统的实际问题具有很好的参考价值。