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

摘要

为解决多核处理器系统中的实时任务调度问题,尤其是实时任务和非实时任务的混合调度问题,在对最早截止时间优先(EDF)算法进行改进的基础上,提出多核处理器混合任务调度算法——EDF-segment算法.EDF-segment算法可以整理调度混合任务时出现的碎片,并通过对碎片的迁移、合并提高处理器的利用率,从而提高系统处理混合任务的性能.通过EDF-segment算法不但可以解决混合任务的调度问题,还可以避免使用EDF算法时造成的多核处理器利用率下降,在保证实时任务处理延迟的前提下提升多核处理器的利用率.经过理论推导和实验分析证明,EDF-segment算法可以有效地应用于多核处理器系统中.%In order to schedule the real-time tasks in multicore processor systems, especially to handle the hybrid tasks composed of real-time tasks and non-real-time tasks, this paper presents a hybrid task scheduling algorithm based on the improvement of the earliest deadline first (EDF) algorithm, called the EDF-segment algorithm. The EDF-segment algorithm can arrange the segments caused by hybrid task scheduling, and migrate and merge segments between cores to enhance the processor utilization. The EDF-segment algorithm can not only solve the hybrid tasks scheduling, but also avoid the reduction of the multicore processor utilization by using the EDF algorithm, and enhance the utilization with the guarantee that real-time tasks can be processed on time. Proved by theoretical and experimental analysis, the EDF-segment algorithm can be effectively applied to multicore processor systems.