基于改进EDF的多核处理器混合任务调度算法.pdf

高技术通讯2012年第22卷第3期：231—239 doi：10．3772／j．issn．100243470．2012．03．002 基于改进EDF的多核处理器混合任务调度算法① 郭秀岩②一‘ 张 武③” 王劲林一+ 吴 刚+ (‘中国科学技术大学自动化系网络传播系统与控制安徽省重点实验室 合肥230027) (“中国科学院声学研究所国家网络与新媒体技术工程研究中心 北京100190) 摘 要 为解决多核处理器系统中的实时任务调度问题，尤其是实时任务和非实时任务 的混合调度问题，在对最早截止时间优先(EDF)算法进行改进的基础上，提出多核处理器 出现的碎片，并通过对碎片的迁移、合并提高处理器的利用率，从而提高系统处理混合任 务的性能。通过EDF．segment算法不但可以解决混合任务的调度问题，还可以避免使用 EDF算法时造成的多核处理器利用率下降，在保证实时任务处理延迟的前提下提升多核 处理器的利用率。经过理论推导和实验分析证明，EDF—segment算法可以有效地应用于 多核处理器系统中。 关键词 混合任务调度，最早截止时间优先(EDF)算法，时间片整理，多核处理器 分类和视频点播系统中的数据流处理，都有类似的 0 引言 要求。这样就产生了一类特殊的混合任务系统，在 该任务系统中所有的任务都由子任务组成，子任务 随着计算机技术的迅猛发展，各种新兴应用层 有固定的执行顺序，相互之间有严格的依赖关系，并 出不穷。这些应用对任务处理的实时性、I／O吞吐 且最后一个子任务为实时任务，而之前的子任务为 量等性能参数有极高的需求，传统的单核处理器的 非实时任务。虽然传统的混合任务系统中也包含实 处理能力已经不足以满足这些需求。随着多核框架 时任务和非实时任务，但是通常实时任务和非实时 的逐渐流行，越来越多的应用以多核处理器作为实 任务之间没有严格的依赖关系。本文以数据包处理 现的基础。多核处理器不但在实现难度和功耗上优 任务为例，总结出一类特殊的混合任务模型，结合最 于单核处理器，而且可以同时处理多个任务，能极大 deadline 早截止时间优先(earliestfirst，EDF)算法、 地提高系统的并行性，从而提高系统的总体性能。 Pfair算法等多核任务调度算法研究了此类任务如 在使用多核处理器调度任务时，通常要通过有向无 何在多核处理器上进行调度，并对EDF算法进行了 循环图(directedacyclicgraph，DAG)将任务分解为 改进，提出了一种EDF-segment算法，通过该算法可 子任务，根据子任务的特点对其进行调度。为了充 以提高多核处理器在调度这类任务时的CPU利用 分利用多核处理器在任务并行处理上的优势，以提 率。 高系统性能，必须合理地在多核间分配、调度任务。 将一个复杂的任务分解为多个子任务时。通常 1 研究背景与相关工作 要按照固定的顺序执行子任务才能保证原始任务的 正确完成，例如网络应用中的数据包处理，可以分解 目前已经有很多的算法可以解决多核处理器上