基于改进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 研究背景与相关工作
要按照固定的顺序执行子任务才能保证原始任务的
正确完成,例如网络应用中的数据包处理,可以分解 目前已经有很多的算法可以解决多核处理器上
显示全部