文档详情

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

发布:2017-07-27约3.39万字共10页下载文档
文本预览下载声明
高技术通讯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 研究背景与相关工作 要按照固定的顺序执行子任务才能保证原始任务的 正确完成,例如网络应用中的数据包处理,可以分解 目前已经有很多的算法可以解决多核处理器上
显示全部
相似文档