假设一个实时系统$ \tau $由n个周期性任务组成，记为$\tau = \left\{ {{\tau _1},{\tau _2}, \cdots ,{\tau _n}} \right\}$。每个周期任务都包含4个参数。即$ {\tau _i}\left( {{r_i},{e_i},{p_i},{d_i}} \right)(1 \leqslant i \leqslant n)$，其中$ r_i$表示发布时刻(release time)，即处理器核响应的时刻，$ e_i$表示任务$ T_i$最坏情况下的执行时间(worst-case execution time, WCET），$ p_i$是$ {\tau _i}$的周期时间，$ d_i$表示时限(deadline)，$ {e_i} \leqslant {d_i} \leqslant {p_i}$。若$ {d_i} = {p_i}$，称该系统为隐含时限系统(implicit deadlines)，将其任务称为隐含时限任务。如果$ {d_i} < {p_i}$，称该系统为包含时限系统(constrained deadline system)，将其任务称为包含时限任务。如果两者没有强制性的约束条件则称为任意时限系统(arbitrary deadline system)。用$ {\tau _i}\left( {{r_i},{e_i},{p_i},{d_i}} \right)$表示包含或任意时限系统，$ {\tau _i}\left( {{r_i},{e_i},{p_i} } \right)$表示暗含时限系统。$ {\tau _i}$的第$ j\left( {j \geqslant 1} \right)$个job，用$ {J_{i,j}}$表示。一个任务的第一个job可以在任何时刻被发布。将$ {J_{i,j}}$的发布时间记为$ {r_{i,j}}$，将其绝对时限$ {d_{i,j}}$定义为$ {r_{i,j}} + {d_i}$，$ {J_{i,j}}$的执行时间记为$ {e_{i,j}}$。

Sporadic任务模型指$ n$个重复发生的任务$\tau = $$ \left\{ {{\tau _1},{\tau _2} ,\cdots ,{\tau _n}} \right\}$，每个$ {{\tau _i}}$具有3个参数特征：$ {e_i}$($ {{e_i} \geqslant 0} $)指示WCET；周期$ {p_i} > {e_i}$，指示一个$ {\tau _i}$连续两次job之间的最小间隔。时限$ {d_i} \geqslant {e_i}$，指示$ {\tau _i}$的每个job在它发布之后到其完成时的最大时间间隔。$ {\tau _i}$是顺序执行的，在同一个时间只有一个job在执行。Sporadic任务模型与周期模型不同之处在于两个连续job发布的时间间隔不固定，其中最小的时间间隔成为该任务的周期。周期型任务模型可以视为Sporadic任务模型的一个特殊情况，即该任务中连续job发布是由固定$ {p _i}$时间单元分割的。本文着重讨论隐含时限的周期任务和Sporadic任务都存在的系统。

多核模型：$ P = \left\{ {{P_1},{P_2} , \cdots ,{P_M}} \right\}$为含有M个具有相同处理能力的处理器集合。在某个时间段内，分配到某个处理器$ P_m$上的任务$ {\tau _i}$的第$ j$次job被激活，那么在该处理器上执行该任务的第$ j$次job的时间片段记为$ {T_{i,j,m}}$。

由以上可知，实时系统中的周期任务具有4个重要属性：发布时间$ {r_i}$、时限$ {d_i}$、最坏执行时间$ {e_i}$和周期$ {p_i}$。

定义1　对于一个隐含时限的实时系统$ \tau$，如果该系统的所有任务都从0时刻发布，那么该任务可以表示为${\tau _i}({e_i},{p_i})$。该任务的利用率因子${u_i}$定义为$U{\rm{(}}{\tau _i}{\rm{) = }}{u_i}{\rm{ = }}\dfrac{{{e_i}}}{{{p_i}}}$，该系统任务的总利用率$U(\tau )\mathop = \limits^{{\rm{def}}} $$ \displaystyle\sum\limits_{{\tau _i} \in \tau } {U({\tau _i})} $。

定义2　对于任一周期任务$ {\tau _i}$，如果$ U\left( {{\tau _i}} \right) \geqslant \dfrac{1}{2}$，则称该周期任务为高利用率任务集合，用S^H表示；如果$ U\left( {{\tau _i}} \right) < \dfrac{1}{2}$，则称该周期任务为低利用率任务集合，用S^L表示。显然，任何一个周期任务要么属于S^H要么属于S^L[15]。

定义3　在一个具有n个实时周期任务$\tau {\rm{ = }} \{ {\tau _1},{\tau _2}, $$ \cdots ,{\tau _{{n}}}\}$的系统中，当所有实时周期任务都属于$ S^H$，即$ U\left( {{\tau _i}} \right) \geqslant \dfrac{1}{2}$，$ i \in \{ 1,2, \cdots ,n\} $，则称该系统为高利用率任务系统，即$ S^H$系统。

定义4　假定某个处理器核$ P_m$，已经分配了实时周期任务${\rm{\{ }}{\tau _1},{\tau _2},\cdots ,{\tau _{{k}}}\} $且$\displaystyle\sum\limits_{i = 1}^k {U({\tau _i})} \leqslant 1$，则定义该处理器核所能继续分配任务的剩余利用率因子为${U_{{\rm{res}}}} = 1 - \displaystyle\sum\limits_{i = 1}^k {U({\tau _i})} $。

定理1　对于高利用率任务系统，如果该系统所有任务利用率因子之和为处理器数量M，则该系统可以被调度的必要条件是一定存在需要迁移的任务。

证明：假设一个$ S^H$系统中有n个实时周期任务$ \tau = \left\{ {{\tau _1},{\tau _2}, \cdots ,{\tau _n}} \right\}$，该系统有M个处理器，且系统任务利用率总和$U(\tau ) = \displaystyle\sum\limits_{{\tau _i} \in \tau } {U({\tau _i})} = M$。因为该系统为高利用率系统，其中任何一个任务$ {{\tau _i}}$的利用率因子均满足$ 1 > U\left( {{\tau _i}} \right) > \dfrac{1}{2}$，那么会出现该任务和任何一个任务的利用率因子之和均大于1的情况，这种情况下，如果该任务能够被系统调度，则该任务只能独享或和多个任务共享一个处理器，否则会出现丢失时限现象。如果独享一个处理器，就会出现其他任务的利用率之和大于M−1的情况，即$ U(\tau ){=} $$ {\displaystyle \sum \limits_{{\tau }_{j}\in \tau (j\ne i)}U({\tau }_{j})}>M-1$，使得其他任务组成的系统成为无法调度的系统。因此，该系统如果能够被调度，就必须让该任务和其他任务共享多个处理器，即为迁移任务。

定义5　如果存在高利用率系统$ S^H$，在某种调度算法S下，定义该系统迁移度$ {\rm{migrat}}\_{\lambda _s}$为所有任务需要迁移的次数之和与所有任务利用率因子总和的比值。迁移度越小说明需要迁移的次数也越少，系统迁移开销也就越少。定义该系统任务的分割度$ {\rm{split}}\_{\lambda _s}$为被分割的任务数量与系统任务总数量的比值。任务分割度越少，说明需要被迁移的任务数量越少，系统的执行效率就越好。

将具有6个暗含时限的实时周期任务${\tau _1}(4,6)$、${\tau _2}(2,3)$、${\tau _3}(5,6)$、${\tau _4}(2,3)$、${\tau _5}(1,2)$、${\tau _6}(2,3)$分配到4个处理器上，从0时刻发布，按照GEDF调度方法会得到调度图序列如图1所示。可以看出，${\tau _2}$和${\tau _4}$在3个处理器上来回迁移，${\tau _5}$也在两个处理器上迁移，${\tau _3}$和${\tau _6}$仍然有丢失时限发生。可以看出这种调度迁移开销太大且仍有时限丢失现象。而semi-partitioned算法将调度过程分为两个阶段：离线分配阶段和执行阶段。在分配阶段只允许少部分任务为迁移任务，其他任务不允许迁移。EDF-fm算法、EDF-os算法和EDF-MSTL算法区别在于离线分配阶段：EDF-fm算法类似深度优先分配，即将一个处理器份额全部占用完之后再分配下一个处理器，如图2所示，所以任务最多在两个处理器上迁移。EDF-os算法类似广度优先遍历，先将任务按照利用率从高到低降序排列，然后将和处理器数量相同的任务依次分配到处理器上作为非迁移任务，再从第一个处理器上依次分配该处理器的剩余份额，如图3所示。

图  1  GEDF算法执行12个时间片结果

图  2  EDF-fm算法任务分配的份额

图  3  EDF-os算法任务分配的份额

这两种算法中的迁移任务都会按照一定的比例将不同数量的job分配到指定的处理器上，比例计算方法为：

式中，${f_{i,j}}$为第i个任务分配到第j个处理上job数量的比例；${s_{i,j}}$为该第i个任务在第j个处理器上获得的份额。本例中EDF-fm算法分配给任务对应的份额矩阵为：

EDF-fm算法任务对应的job比例矩阵为：

从这里可以看到${\tau _2}(2,3)$被分配到处理器P₁和P₂上，分配的job比例为1∶1；那么调度时就会将奇数项job配到P₁，偶数项job分配到P₂。${\tau _3}(5,6)$在P₂和P₃分配的job的比例为4∶1，那么5个job中就有一个job被分配到P₃处理器上。${\tau _5}(1,2)$在P₃和P₄处理器上job分配的比例为1∶2。同理，可以得到EDF-os算法的分配份额和任务job的执行比例。

这两种算法在执行阶段，迁移任务要比非迁移任务优先级高，而当某处理器执行两个迁移任务时，该处理器为非第一次分配处理器的迁移任务优先级最高。

EDF-os算法分配给任务对应的份额矩阵为：

EDF-os算法任务对应的job比例矩阵为：

EDF-fm和EDF-os具体执行结果如图4和图5所示。

图  4  EDF-fm算法执行12个时间片结果

图  5  EDF-os算法执行12个时间片结果

EDF-fm算法被分割的任务为$ {{\tau _2}}$、$ {{\tau _3}}$、$ {{\tau _5}}$，这3个任务分别被迁移了1次，故该调度算法下的迁移度$ {\rm{migrat}}\_{\lambda _s} = \dfrac{3}{4} = 0.75$，任务分割度$ {\rm{split}}\_{\lambda _s} = \dfrac{3}{6} = 0.5$。

EDF-os算法被分割的任务为$ {{\tau _5}}$、$ {{\tau _6}}$，这两个任务分别被迁移了2次和1次，故该调度算法下的迁移度$ {\rm{migrat}}\_{\lambda _s} = \dfrac{3}{4} = 0.75$，任务分割度$ {\rm{split}}\_{\lambda _s} = \dfrac{2}{6} = \dfrac{1}{3}$。

EDF-MSTL算法分配给任务对应的份额矩阵为：

图  6  EDF-MSTL算法执行12个时间片结果

EDF-MSTL算法任务对应的job比例矩阵为：

对应的该调度算法下的迁移度$ {\rm{migrat}}\_{\lambda _s} = \dfrac{2}{4} = $$ 0.5$，任务分割度$ {\rm{split}}\_{\lambda _s} = \dfrac{2}{6} = \dfrac{1}{3}$。系统总体的迁移度和任务分割度是最少的，调度结果如图6所示。

EDF-MSTL调度方法描述如下：

1) 首先将n个任务的利用率因子按照从大到小顺序排列放入集合$ S^H$，m个处理器顺序放入集合P中，初始化矩阵${{{s}}_{n,n}}$，${s_{i,i}} = {u_i}$，其他值为0。

图  7  EDF-MSTL计算任务份额的流程图

2) 找到具有最小利用率因子的任务${u_n}$，将其拆分为两部分${u_n} = {u_i} + {u_j}$，其中${u_i}$与第一个具有最大利用率因子任务的利用率之和为1，即${u_i} + {u_1} = 1$，设置${s_{n,k}} = {u_i}$，${s_{n,n}} = {u_j}$，并将这两个利用率因子从集合$ S^H$中删除，如果${u_j}$为0，则也将其从$ S^H$中删除，将处理器k从集合P中删除。

3) 在剩下的$ S^H$集合中继续重复步骤1)的工作，直到处理器集合为空为止。得到${s_{n,m}}$即为所分配份额。根据该份额通过式(1)计算${f_{n,m}}$。利用${f_{n,m}}$中的值，在调度执行过程中进行按比例分配相应的任务job，可以得到相依的执行序列。具体计算任务份额的算法流程图如图7所示。

本文测试的环境是在一个Intel®Core™2 Quad Q8400多核平台上。分别采用EDF-fm，EDF-os，EDF-MSTL这3种调度方法进行比较。测试方法随机产生1000个任务集，每个任务集中产生50个参数不等的Sporadic软实时周期任务，所有周期任务都满足利用率大于0.5，执行时间小于时限，时限小于或等于周期。在整个仿真实验过程中，为了描述算法之间的性能差异，采用多次模拟求平均值的方法得到某时间段内的系统吞吐率以及任务切换job数量所占总job数的比例，如表1所示。

另外，选择对应这10个任务集的平均任务迁移度和任务分割度两个方面进行性能对比。从表1、图8和图9可以看出，EDF-算法和EDF-MSTL算法在系统吞吐率、任务切换job数、任务迁移度和任务分割度方面，后者算法明显占据优势。

图  8  3种算法任务迁移度

图  9  3种算法的任务分割度

本文的目的是为了解决在嵌入式多核平台下，任务全部属于高利用率因子集合的软实时系统中的实时周期任务的调度问题。在EDF-fm和EDF-os算法的基础上，提供一种基于最少迁移度的多核实时调度方法，减少了现有技术中存在由于迁移带来的过多开销以及上下文切换次数，在任务量很大的情况下可以大大提高系统的整体效率。