黄姝娟，肖 锋，曹子建

(西安工业大学计算机与工程学院 西安 710021)

当前嵌入式多核平台对具有严格时间限制的复杂应用提供了强有力的计算执行能力[1]。然而随着嵌入式系统复杂性的攀升，实时调度也更具挑战性[2]。在嵌入式多核平台下，大部分算法基于Partitioned[3]或Global[4-5]调度方法，近年来Semipartitioned[6-7]调度方法逐渐获得大家的重视。该类调度算法吸取了前两者的优点，即在Partitioned调度算法的基础上允许少部分任务迁移，被建议用在支持暗含时限的软实时Sporadic任务系统中[8]。此后，还被应用于混合关键系统中[9-12]。然而，无论哪种应用，该类调度算法始终要求在一定的时限延迟的基础上进行讨论，而且任务迁移仅在job的边界上进行，否则系统开销太大。但随着当前多核能力的提高，嵌入式系统的集成度越来越高，导致高利用率的任务也越来越集中，系统运行的负荷增大，因此Semi-partitioned调度算法划分方案的精确性以及减少迁移和系统运行开销就成为研究热点。

目前针对高利率集合的semi-partitioned调度算法，如EDF-fm[13](earliest-deadline- first-based fixed and migrating)和 EDF-os[14](earliest-deadline-firstbased optimal semi-partitioned)，都存在迁移次数较多和上下文切换开销较大的问题。本文在这两种调度算法的基础上，提出一种基于最少迁移度和分割度(earliest-deadline-first-based migrating and splitting tasks least, EDF-MSTL)的调度方法，旨在提高系统效率的同时，减少分割任务的数量和不必要的迁移和任务切换开销。

1 Sporadic实时系统任务调度模型

假设一个实时系统 τ由n个周期性任务组成，记为 τ ={τ1,τ2,···,τn}。每个周期任务都包含4个参数。即 τi(ri,ei,pi,di)(1≤i≤n)， 其中ri表示发布时刻(release time)，即处理器核响应的时刻，ei表示任务Ti最坏情况下的执行时间(worst-case execution time, WCET），pi是 τi的 周 期 时 间，di表 示 时 限(deadline)，ei≤di≤pi。……