随着嵌入式技术的发展，云计算、边缘计算等复杂计算场景对芯片的性能要求越来越高. 为了满足该应用需求，异构多核在现代计算机系统得到迅速发展. 然而，向大规模异构平台迁移非常困难. 软件层面的原因主要是大规模的、必要的程序并行导致软件调度的复杂度，即使在同构平台下这依然是大量学者致力研究的一个热点问题.

本文首次针对有向无环图（directed acyclic graph, DAG）并行任务模型在异构平台上进行全局固定优先级限制性可抢占的可调度性分析，所提到的异构平台由多个不同类型的处理器组成（每个类别的处理器个数大于等于1）. 由于异构融合的体系结构，多种不同类型的处理器集成在同一硬件，且并行软件中某些程序片段只能在特定的处理器执行. 因此，DAG任务的某些结点可以绑定到特定的一类处理器上执行. 而绑定处理器的操作，在一些主流的并行处理程序和操作系统都有对应的指令，例如：在OpenMP中可以通过proc_bind实现线程的绑定^[1]；在OpenCL中，通过clCreatCommand可以针对特定设备创建一组命令^[2]；在CUDA中，可以通过cudaSetDevise实现指令到目标设备的绑定^[3]. 而对任务的如此处理可以避免任务在不同速率的处理器上迁移，减少实现难度和不必要的迁移开销. 下文中，我们称绑定处理器的DAG任务为分类DAG任务.

在经典的调度策略中，一般忽略了任务抢占和迁移的开销. 然而，可抢占调度中频繁发生的抢占所造成的开销往往比不可抢占调度高很多，需要高度重视. 尤其在异构多核体系结构中，GPU中执行的任务片段是不可抢占的，因此一些实时系统的任务存在不可抢占域（即任务执行的某个片段不允许被抢占）. 因此，限制性可抢占的研究对于实时系统的任务执行是至关重要的.

关于分类DAG任务集的调度问题，难点主要存在2方面：1）DAG任务内部不同结点的互相影响；2）不同DAG任务结点间的互相影响. 尤其是限制性可抢占导致优先级翻转，即低优先级任务会对高优先级任务结点的执行造成阻塞. 因此，分类DAG的某个结点的执行会受到自身其他结点的干涉、高优先级任务的干涉以及低优先级任务的阻塞. 其中，自身结点的干涉已经在早期工作^[4]中解决. 本文重点解决高优先级任务的干涉、低优先级任务的阻塞的分析问题以及分类DAG的最差响应时间（worst case response time,WCRT）分析，主要创新点包括3个层面：

1）由于分类导致DAG任务的关键路径（得到WCRT的路径）不确定^[4]，从而增加高优先级任务干涉分析的难度. 结合经典的同构DAG理论和分类DAG的特点，本文提出了分类DAG高优先级分析方法.

2）解决了分类DAG限制性可抢占导致的优先级翻转问题. 本文将同构DAG的低优先级任务分析方法和分类DAG相结合，提出了分类DAG的低优先级任务阻塞的分析方法.

3）采用文献[4]的路径抽象方法并结合高、低优先级任务的分析，提出了分类DAG任务集的WCRT分析方法. 由于高、低优先级任务干涉计算的引入，本文对文献[4]路径抽象规则进行了创新.

1.   相关工作

在嵌入式实时系统中，某些任务的执行只能在规定的地方被抢占. 考虑到完全可抢占和完全不可抢占的优缺点，限制性可抢占的研究非常重要. 近年来关于这方面的研究也较突出. 如：文献[5]的工作针对多核全局最早截止期优先限制性可抢占任务做出了分析；文献[6-7]对非并行任务在全局调度策略下进行了响应时间分析；文献[8]针对多核并行任务的限制性可抢占问题进行了分析，并根据抢占策略的不同提出了对应的分析方法并进行了比较；文献[9]针对DAG的限制性可抢占问题进行了研究，特别是针对低优先级任务的阻塞在效率和精确度的不同上提出了不同的分析策略. 然而，限制性可抢占的研究工作还未考虑到资源的限制性. 随着异构体系结构的发展，资源限制性是必须要考虑和解决的问题.

资源限制性问题的研究曾经非常热门，也取得了一些研究成果，基于当时的条件这些成果考虑的任务模型相对简单. 例如文献[10-13]考虑的问题是2种处理器集合分配给2个任务，并且一个处理器集合是另一个集合的子集等，相关研究总结在综述类文献[14-15]. 可以发现，现有研究的问题和本文提出的分类DAG任务的可调度性问题存在差异. 针对分类DAG任务的可调度性研究，可查阅的文献较少，Han等人在文献[4]中提出单个分类DAG的响应时间分析，该文分析了单DAG分类任务可调度性，并提出了基于路径抽象的方法进行可调度性分析. 基于此研究以及并行任务分析和响应时间分析的经典理论^[16-18]，Han等人提出了基于联合策略的可调度性分析^[19]和全局固定优先级可调度性分析^[20]. 文献[21]提出的工作和本文的任务模型接近，该工作是基于分解策略提出的点到点（即计算路径中每个点的WCRT）的调度分析方法，然而该方法并未考虑资源限制的问题. 就单个分类DAG任务而言，文献[4]进行了算法对比，对比实验结果显示文献[21]算法比文献[4]算法明显消极.

本文的主要工作是基于文献[4]的理论基础，提出基于全局固定优先级的限制性可抢占调度策略的分类DAG任务的可调度性分析方法. 分类导致DAG任务的关键路径不确定，从而增加高、低优先级任务的分析难度. 本文将DAG分析的理论（基于路径的分析）和分类DAG任务相结合，成功解决了该难题. 最后，基于文献[4]的路径抽象算法，更新路径抽象规则，进行任务集的可调度性判定.

2.   任务模型

2.1   任务集模型的建立

本文对由N个分类DAG任务组成的任务集$G= \left\{{G}_{1},{G}_{2},… ,{G}_{N}\right\}$进行可调度性分析，该任务集执行的系统由不同种类的核组成. $S$是核类别的集合，对于每种类型$s\in S$具有${M}_{s}$（${M}_{s}\ge 1$）个核用于调度. 分类DAG任务${G}_{i}=\left({V}_{i},{E}_{i},C,{\gamma }_{i},{T}_{i},{D}_{i}\right)$，该元组中各个符号的定义为：

1）${V}_{i}$ 表示${G}_{i}$所有结点的集合，结点${v}_{i}^{j}\in {V}_{i}, 1\le j\le {n}_{i}$，${n}_{i}$为${G}_{i}$的结点数；

2）${E}_{i}$表示${G}_{i}$所有边的集合，结点$\left(u,v\right)\in {E}_{i},v,u\in {V}_{i}$；

3）C表示${G}_{i}$每个结点最差执行时间 （worst case execution time, WCET）的函数，$C\left({v}_{i}^{j}\right)$表示结点${v}_{i}^{j}$的WCET；

4）${\gamma }_{i}$ 表示${G}_{i}$每个结点类型的集合，${\gamma }_{i}^{j}$表示结点${v}_{i}^{j}$的类型；

5）${T}_{i}$ 表示${G}_{i}$相邻2个实例的最小释放时间间隔；

6）${D}_{i}$ 表示${G}_{i}$的相对截止期，即${G}_{i}$在时间点${r}_{i}$释放一个任务实例，必须在${r}_{i}+{D}_{i}$内完成该任务实例的执行.

如果存在边$\left(u,v\right)\in {E}_{i}$， $u$是$v$的直接前继结点，而$v$是$u$的直接后继结点；如果存在从$u$到$v$的路径，$u$是$v$的祖先结点，而$v$是$u$的子孙结点. 本文用$pre\left({v}_{i}^{j}\right), suc\left({v}_{i}^{j}\right),ans\left({v}_{i}^{j}\right)$和$des\left({v}_{i}^{j}\right)$分别表示结点${v}_{i}^{j}$的前继结点集合、后继结点集合、祖先结点集合以及子孙结点集合. 对于每个DAG任务，都假设其只有1个源结点和1个结束结点. 如果任务${G}_{i}$具有多个源结点和多个结束结点，可以通过给${G}_{i}$增加虚拟源结点（结点的WCET为0）和虚拟结点到${G}_{i}$的原源结点的有向边，使其变成单源结点. 用相同的方法使${G}_{i}$变成单结束结点的任务. ${\pi }_{i}=\{{v}_{i}^{1},{v}_{i}^{2},… ,{v}_{i}^{k}\}$是${G}_{i}$的一条路径，如果路径${\pi }_{i}$的${v}_{i}^{1}$是源结点且${v}_{i}^{k}$是结束结点，则${\pi }_{i}$是一条完整的路径. 由于任务是按照类别进行执行的，需要对每个任务的WCET之和进行标记，具体为：

1）$vol\left({G}_{i}\right)=\displaystyle\sum _{1\le j\le {n}_{i}}C\left({v}_{i}^{j}\right)$，表示任务${G}_{i}$所有结点的WCET之和；

2）${vol}^{s}\left({G}_{i}\right)=\displaystyle\sum _{1\le j\le {n}_{i}\wedge {\gamma }_{i}^{j}=s}C\left({v}_{i}^{j}\right)$，表示任务${G}_{i}$所有类别为s的结点的WCET之和；

3）$len\left({\pi }_{i}\right)=\displaystyle\sum _{{v}_{i}^{j}\in {\pi }_{i}}C\left({v}_{i}^{j}\right)$ 表示路径${\pi }_{i}$上的所有结点的WCET之和，即路径${\pi }_{i}$的长度；

4）$len\left({G}_{i}\right)=\underset{{\pi}_i \in {G}_{i}}{\mathrm{max}}\;len\left({\pi }_{i}\right)$ 表示任务${G}_{i}$的最长路径.

例1. 异构DAG并行任务模型如图1所示，任务执行在具有2种类别的处理器平台，白色圈表示类别1，灰色圈表示类别2，结点旁的数值表示任务的WCET.

图  1  分类DAG任务${G}_{1}$的示意图

Figure  1.  Illustration of typed DAG task ${G}_{1}$

下载: 全尺寸图片 幻灯片

2.2   任务调度策略

本文中任务采用全局固定优先级限制性可抢占策略进行调度. 任务按照优先级顺序排列，即如果$i < j$，则${G}_{i}$的优先级比${G}_{j}$高. 限制性可抢占是指任务的结点一旦开始执行，其执行不会被高优先级任务抢占.

本文将提出一种过量估计方法分析每个任务的WCRT上界，从而保证任务执行的安全性. 其中，任务${G}_{i}$的WCRT上界表示为${R}_{i}$.

3.   调度算法分析

本节将针对任务集$G=\{{G}_{1},{G}_{2},… ,{G}_{N}\}$进行可调度性分析，并假设${G}_{k}$是被分析任务，$k=1,2,…,N$.

3.1   整体分析

DAG任务WCRT上界分析方法多基于关键路径. 同构平台下，最长路径即为关键路径^[18]. 然而，这一结论已经不适用于分类DAG^[4]，最长路径分析方法得到的WCRT上界并不安全，增大了分类DAG的分析难度. 分类DAG任务进行可调度性分析需要解决2个问题：1）如何确定关键路径；2）已知关键路径，如何进行响应时间分析. 为了确保分析方法的安全可靠，解决问题1）最简单的方法是枚举所有路径，后面会介绍如何解决枚举问题. 针对问题2），本文基于路径进行解决. 首先，假设${G}_{k}$的关键路径是${\pi }_{k}$，${\pi }_{k}=\{{v}_{k}^{1}, {v}_{k}^{2},… ,{v}_{k}^{k}\}$.

路径${\pi }_{k}$的执行受到3种不同类型的干扰：第1种，任务内干涉$Intra\left({\pi }_{k}\right)$；第2种，其他高优先级任务的干涉；第3种，低优先级任务的阻塞.

由文献[4]的结论可知，路径${\pi }_{k}$受到的任务内干涉定义为与${\pi }_{k}$结点并行且实际干涉${\pi }_{k}$上结点执行的同类结点工作量之和与对应的处理器个数的比值，即

其中$ivs({\pi }_{k},s)$在文献[4]中定义为路径${\pi }_{k}$实际受到的任务内干涉.

根据文献[9]可知，路径${\pi }_{k}$受到的任务间干涉为路径上所有类别的高优先级任务的工作量加上低优先级任务的阻塞量之和与处理器个数总和的比值，即

其中，${W}^{s}\left({\pi }_{k}\right)$表示高优先级任务产生的工作量之和的上界，${B}^{s}\left({\pi }_{k}\right)$表示低优先级任务产生的工作量之和的上界. 根据式（1）（2），可以得到如下结论：

引理1. 路径${\pi }_{k}=\{{v}_{k}^{1},{v}_{k}^{2},… ,{v}_{k}^{\mathrm{k}}\}$是${G}_{k}$的一条完整路径，其WCRT上界

证明. 根据文献[9，18]，引理可证.证毕.

关键问题是如何计算$Inter\left({\pi }_{k}\right). Inter\left({\pi }_{k}\right)$包括2个部分，即高优先级任务的干涉和低优先级任务的阻塞，下面将对这2个部分产生的工作量上界进行分析.

3.2   高优先级干涉量分析

对于高优先级任务的干涉量计算，首先要确定在某个时间窗口里高优先级任务能够产生的每个类别的工作量上界. 在时间长度为$x$的窗口内，高优先级任务${G}_{i}$产生的工作量上界表示为${W}_{i}\left(x\right)$，产生类别为${s}$的工作量上界表示为${W}_{i}^{s}\left(x\right)，{W}_{i}^{s}\left(x\right)$计算过程详见引理2.

引理2. 在长度为$x$的时间窗口内，高优先级任务${G}_{i}$能够产生的类别为$s$的工作量上界为

其中 $\alpha = \mathrm{m}\mathrm{i}\mathrm{n}\left(vo{l}^{s} \left({G}_{i}\right),\mathrm{m}\mathrm{a}\mathrm{x}\left(0,{M}_{s}\times \left(\left(x-\dfrac{vo{l}^{s}\left({G}_{i}\right)}{{M}_{s}}\right)\right.\right.\right. \mathrm{m}\mathrm{o}\mathrm{d}{T}_{i}-$$({T}_{i}-{R}_{i})\Big)\Big)\Big)$.

证明. 引理2能够得到证明基于2个层面的假设：

1） 当carry-in实例（该实例在窗口之前释放，在窗口内完成）和carry-out实例（该实例在窗口内释放，截止期在窗口外）的$s$类别的工作量平均分布在所有$s$类核上时（如图2所示），可以得到$s$类别的工作量上界.

图  2  ${G}_{i}$在x窗口内产生最大工作量的最坏情况

Figure  2.  worst-case scenario to maximum workload in x of ${G}_{i}$

下载: 全尺寸图片 幻灯片

2） 假设carry-out实例全部带入，可以得到高优先级任务的工作量上界，该假设基于假设1）.

首先，证明假设1）的正确性. 该假设忽略任务的内部结构，单纯考虑长度为$x$的时间窗口内能够产生的工作量的最大情况. 采用反证法，如果$vo{l}^{s}\left({G}_{i}\right)$的工作量分布在 ${M}_{s}'$个核且${M}_{s}' < {M}_{s}$，根据式（4），该设想显然不能增加窗口内的工作量，因此假设1）成立.

假设2）的证明依然采用反证法，假设carry-out带入的减少即窗口向左滑动$\varepsilon =\delta \times vo{l}^{s}\left({G}_{i}\right)/ {M}_{s}$的长度，$0 < \delta < 1$. 窗口向左滑动，会导致左边carry-in实例长度的增加，即carry-in实例在窗口内增加$\varepsilon$的长度. 而carry-in和carry-out实例s类的工作量是均匀分布在所有核上，所以最终的工作量总和不会发生改变，即假设2）成立. 接下来证明式（4）计算的正确性.

图2中，$x$的时间窗口的组成包括：长度为$vo{l}^{s}\left({G}_{i}\right)/{M}_{s}$的carry-out实例、body实例（释放和截止期都在窗口内的实例）个数的周期长度以及carry-in实例长度. 而body实例数量的上界为

x窗口还有carry-in的组成部分. 而carry-in的长度可由$\alpha$计算. 根据图2，carry-in长度不大于$vo{l^s}\left( {{G_i}} \right)/{M_s}$.

综上，引理2得证.证毕.

根据引理2，在长度为$x$的时间窗口内，所有高优先级任务${G}_{i}$产生的$s$类别的工作量上界为

3.3   低优先级阻塞分析

限制性可抢占导致优先级翻转的问题，即低优先级任务会阻塞高优先级任务的执行. 当路径${\pi }_{k}$上的某个结点${v}_{k}^{i}$可以执行时，即所有前继结点完成执行，而处理器被低优先级任务占用，从而造成对该结点的阻塞. 被低优先级任务占用的处理器个数为1~${M}_{s}$（少于${M}_{s}$个是因为处理器被高优先级任务或者前继结点占用），最坏情况要结合${v}_{k}^{i}$的情况进行讨论.

如果$i=1$即该结点是源结点，最多有${M}_{s}$个低优先级任务的结点阻塞其执行. 如果$1 < i\le {n}_{i}$，分成2种情况进行讨论：

1）${\gamma }_{k}^{i-1}=s$，则最多有${M}_{s}-1$个低先级任务的结点阻塞其执行. 因为只有${M}_{s}-1$个低优先级任务的结点和${v}_{k}^{i-1}$结点并行执行且未执行完造成对${v}_{k}^{i}$的阻塞，如图3所示.

图  3  ${\gamma }_{k}^{i-1}=s$时的情况

Figure  3.  Scenario for ${\gamma }_{k}^{i-1}=s$

下载: 全尺寸图片 幻灯片

2）${\gamma }_{k}^{i-1}\ne s$，则最多有${M}_{s}$个低优先级任务的结点阻塞其执行. 因为前继结点的执行不占用s类别的核，因此${v}_{k}^{i}$可以执行时最多有${M}_{s}$个低优先级任务的结点未完成执行，如图4所示.

图  4  ${\gamma }_{k}^{i-1}\ne s$时的情况

Figure  4.  Scenario for ${\gamma }_{k}^{i-1}\ne s$

下载: 全尺寸图片 幻灯片

${\Delta }_{k}^{{M}_{s}}$和${\Delta }_{k}^{{M}_{\mathrm{s}}-1}$分别表示最大的${M}_{s}$个和${M}_{s}-1$个不可抢占低优先级结点的工作量之和，即

其中：${G}_{i > k}$表示所有的低优先级任务；$\underset{{G}_{i > k}}{\stackrel{{M}_{s}}{\mathrm{m}\mathrm{a}\mathrm{x}}}$和$\underset{{G}_{i > k}}{\stackrel{{M}_{s}-1}{\mathrm{m}\mathrm{a}\mathrm{x}}}$分别表示所有的低优先级任务中的 ${M}_{s}$个和${M}_{s}-1$个最大的不可抢占结点的工作量之和；而$\underset{1\le j\le {n}_{j}}{\stackrel{{M}_{s}}{\mathrm{m}\mathrm{a}\mathrm{x}}}$和$\underset{1\le j\le {n}_{j}}{\stackrel{{M}_{s}-1}{\mathrm{m}\mathrm{a}\mathrm{x}}}$分别表示${G}_{i}$的${M}_{s}$个和${M}_{s}-1$个最大的不可抢占结点的工作量之和. 式（6）（7）分别计算了所有低优先级任务中最大的${M}_{s}$个和${M}_{s}-1$个最大的不可抢占结点的工作量之和，如此定义是因为最大的结点来自于不同的任务.

综上，被分析路径上的某个结点阻塞量的计算总结见引理3.

引理3. 结点${v}_{k}^{i}$是路径${\pi }_{k}=\{{v}_{k}^{1},{v}_{k}^{2},… ,{v}_{k}^{k}\}$上的第i个结点，其类别为${\gamma }_{k}^{i}=s$，则它的阻塞量上界为

证明. 根据式（6）（7），引理3得证.

证毕.

路径${\pi }_{k}=\{{v}_{k}^{1},{v}_{k}^{2},… ,{v}_{k}^{k}\}$的s类的阻塞量之和

4.   分析过程

基于文献[4]提出的路径抽象算法，进行响应时间分析.

算法基本思路：对于结点${v}_{k}^{i}$，每条经过它的路径均可用一个元组表示$\left\langle{{v}_{k}^{i},\Delta \left({\pi }_{k},{v}_{k}^{i}\right),R({\pi }_{k},{v}_{k}^{i})}\right\rangle$，其中$\Delta \left({\pi }_{k},{v}_{k}^{i}\right)$用来记录路径上计算过的并行结点（任务内干涉），$R({\pi }_{k},{v}_{k}^{i})$表示该路径上的结点${v}_{k}^{i}$的响应时间. 经过${v}_{k}^{i}$的每条路径都有一个元组与之对应，同样的元组可以被合并成为一个，不同的2个元组如果符合一定的条件可以被其中一个元组替换. 替换的基本原则是被替换掉的元组不会导致比替换它的元组更大的WCRT上界. 经过元组的合并和替换操作过滤掉不必要的元组，达到减少路径的目的. 对DAG任务中的每个结点进行相同操作，直至最终结点. 最终结点上所有元组中最大的$R({\pi }_{k},{v}_{k}^{i})$即为任务${G}_{k}$的WCRT上界.

接下来，对$\Delta \left({\pi }_{k},{v}_{k}^{i}\right)$, $R({\pi }_{k},{v}_{k}^{i})$和替换规则进行定义.

定义1^[4]. 对于${G}_{k}$的一条路径${\pi }_{k}=\{{v}_{k}^{1},{v}_{k}^{2},… ,{v}_{k}^{k}\}$，$\Delta \left({\pi }_{k},{v}_{k}^{i}\right)$定义为距离路径上结点${v}_{k}^{i}$最近的所有类别结点的集合，即

其中

定义2. 路径${\pi }_{k}=\{{v}_{k}^{1},{v}_{k}^{2},… ,{v}_{k}^{k}\}$中从源结点开始到${v}_{k}^{i}$的所有类型的集合，定义为

显然，${v}_{k}^{i}$为结束结点时$\gamma \left({\pi }_{k},{v}_{k}^{i}\right)$表示整条路径的类型集合. 本文采用$len({\pi }_{k},{v}_{k}^{i})$表示从源结点到${v}_{k}^{i}$的路径长度，即

从源结点到${v}_{k}^{i}$的所有s类别阻塞量之和为

定义3. 对于${G}_{k}$的一条路径${\pi }_{k}=\{{v}_{k}^{1},{v}_{k}^{2},… ,{v}_{k}^{k}\}$，$R({\pi }_{k}, {v}_{k}^{i})$定义为

其中$L\left({\pi }_{k},{v}_{k}^{i}\right)$定义为

$\displaystyle\sum_{v\in \phi \left({\pi }_{k},{v}_{k}^{i}\right)}\dfrac{C\left(v\right)}{{M}_{s}}$是文献[4]中关于任务内关涉的计算，与元组的抽象息息相关. 其中，重要计算参数定义为

由于其他任务干涉的增加，导致文献[4]算法中元组替换的规则不再适用，需要增加新的替换规则满足增加的其他任务干涉的分析，具体见引理4.

引理4. 当任务${G}_{k}$的2个路径${\pi }_{k}^{1}$和路径${\pi }_{k}^{2}$汇聚在${v}_{k}^{i}$结点时，2条路径分别由元组$\left\langle{{v}_{k}^{i},\Delta \left({\pi }_{k}^{1},{v}_{k}^{i}\right),R({\pi }_{k}^{1},{v}_{k}^{i})}\right\rangle$和$\left\langle{{v}_{k}^{i},\Delta \left({\pi }_{k}^{2},{v}_{k}^{i}\right),R({\pi }_{k}^{2},{v}_{k}^{i})}\right\rangle$表示，前者为元组1，后者为元组2. 当元组1和元组2满足条件1）~3）时，元组2可以被元组1替换.

1） $\gamma \left({\pi }_{k}^{1},{v}_{k}^{i}\right)=\gamma \left({\pi }_{k}^{2},{v}_{k}^{i}\right)$；

2） $R\left({\pi }_{k}^{1},{v}_{k}^{i}\right)\ge R\left({\pi }_{k}^{2},{v}_{k}^{i}\right)$；

3） 对于任意类型s，条件①②必须成立：

① $\delta \left({\pi }_{k}^{1},{v}_{k}^{i},s\right)=\perp$；

② $\left(\delta \left({\pi }_{k}^{1},{v}_{k}^{i},s\right)\ne \perp \right)\wedge \left(\delta \left({\pi }_{k}^{2},{v}_{k}^{i},s\right)\ne \perp \right)\wedge$　　　$\left(par\left(\delta \left({\pi }_{k}^{1},{v}_{k}^{i},s\right)\right)\right)\cap \left(des\left(\delta \left({\pi }_{k}^{2},{v}_{k}^{i},s\right)\right)\right)=\varnothing$；

证明. 替换规则2）和3）已经在文献[4]中证明. 本文只需证明规则1）的必要性. 采用反证法，如果规则1）不成立，则以下2种情况之一成立：

1）$\gamma \left({\pi }_{k}^{1},{v}_{k}^{i}\right)\subset \gamma \left({\pi }_{k}^{2},{v}_{k}^{i}\right)$. 设路径1和路径2经过结点${v}_{k}^{i}$, $\gamma \left({\pi }_{k}^{1},{v}_{k}^{i}\right)=\{{s}_{1},{s}_{2}\}$，$\gamma \left({\pi }_{k}^{2},{v}_{k}^{i}\right)=\{{s}_{1},{s}_{2},{s}_{3}\}$. 在${v}_{k}^{i}$到结束结点的搜索过程中，2条路径都不会再增加新的类别. 路径长度在增大，而高优先级任务干涉的计算是非递减的，从而造成${s}_{3}$类别的高优先级任务造成的干涉逐渐增大. 因此路径2不能被替换.

2）$\gamma \left({\pi }_{k}^{1},{v}_{k}^{i}\right)\supset \gamma \left({\pi }_{k}^{2},{v}_{k}^{i}\right)$. 设路径1和路径2经过结点${v}_{k}^{i}$，到达后继结点${v}_{k}^{i+1}. {\gamma }_{k}^{i+1}=s$且$s\in \gamma \left({\pi }_{k}^{1},{v}_{k}^{i}\right)-\gamma \left({\pi }_{k}^{2},{v}_{k}^{i}\right)$，即到达结点${v}_{k}^{i+1}$路径2会增加1个新的类别$s$，从而导致在结点${v}_{k}^{i+1}$路径2增加的高优先级任务干涉比路径1增加得多，因此路径2不能被替换.

证毕.

最终，本文提出的分析方法综合为算法1，来判定任务集的可调度性.

算法1. 任务集可调度性分析算法.

输入：任务集G，处理器池$M=\left\{{M}_{s}\right|s\in S\}$；

输出：是否可以被调度.

① LimitedPreScheduling（G,M）；

② for each task ${G}_{k}$ in G

③ 　$TS=\left\{\left\langle{{v}_{k}^{1},\left\{{v}_{k}^{1}\right\},C\left({v}_{k}^{1}\right)}\right\rangle\right\}$；

/* 从任务${G}_{k}$的源结点开始更新元组集合*/

④ 　while$(\exists \left\langle{v,\Delta ,R}\right\rangle\in TS;v\ne {v}_{\mathrm{s}\mathrm{n}\mathrm{k}})$ do

/*针对元组中的每个元组进行下面的计算*/

⑤ 　　for each ${v}'\in suc\left(v\right)$ do

/* 从结点v搜索至结点${v}'$*/

⑥　　　基于$\left\langle{v,\Delta ,R}\right\rangle$和式（14）计算$\left\langle{{v}',{\Delta }',{R}'}\right\rangle$；

⑦ 　　　if （$\nexists \left\langle{{v}',{\Delta }',{R}'}\right\rangle\in TS$ or $\left\langle{{v}^{*},{\Delta }^{*},{R}^{*}}\right\rangle$

根据代替规则可代替$\left\langle{{v}',{\Delta }',{R}'}\right\rangle$）

⑧ 　　　　$TS=TS\cup \{\left\langle{{v}',{\Delta }',{R}'}\right\rangle\}$；

⑨ 　　　end if

⑩ 　　end for

⑪ 　　$TS=TS\backslash \left\{\left\langle{v,\Delta ,R}\right\rangle\right\}$；

⑫ 　end while

⑬ 　for each $\left\langle{v,\Delta ,R}\right\rangle\in TS$ do

/* 结束结点${v}_{\mathrm{s}\mathrm{n}\mathrm{k}}$所有元组中具有最大R的

即为任务${G}_{k}$的WCRT上界*/

⑭ 　　${R_{{\rm{tmp}}}} = \cup \left\{ {R \in \left\langle {v,\Delta ,R} \right\rangle } \right\}$；

⑮ 　　${R}_{k}=\mathrm{max}\left(R_{{\rm{tmp}}}\right)$；

⑯　 end for

⑰　 if ${R}_{k} > {D}_{k}$

⑱　　 return不可调度的；

⑲　 end if

⑳ end for

㉑ return可调度的.

算法1针对任务集中的每个任务进行路径抽象，计算其WCRT上界. 算法1的行③~⑫是针对每个任务${G}_{k}$，从源结点开始搜索至结束结点，针对每个结点基于其前继结点的元组进行该结点的元组计算，计算出新的元组进行元组合并和替换操作，直至结束结点. 结束结点所有元组中最大的$R$即为${G}_{k}$的WCRT上界（行⑬~⑯）. 如果${R}_{k} > {D}_{k}$说明该任务不可调度，直接结束计算返回整个任务集不可被调度；否则，继续分析下一个任务. 如果最后1个任务被分析完，且满足截止期的要求则整个任务集可被调度（行⑰~㉑）.

基于文献[4]，算法1对DAG任务每个结点的响应时间分析时增加了其他任务的干涉计算. 在算法1过程中增加了新的合并和替换规则以保证最终计算的安全性.

定理1. 任务集G是否可以被调度，可以由算法1来判定.

证明. 综合理论和算法1的伪代码分析，定理1得证.证毕.

5.   实　　验

本文采用仿真实验，分别从算法的准确性和效率层面进行算法的验证. 对任务集的可调度性产生影响的参数包括：任务集利用率、处理器个数、任务集内任务个数、结点个数、类别数以及每个任务的并行度. 首先，对这些参数设置一组默认参数，然后基于该默认参数进行对应参数实验变化的验证实验. 异构平台相关的实验数据基于OpenAMP^[22]项目支持的硬件平台作为基础数据，对类别数和每种类别核数量的范围进行适当地增大，观察这2组参数对算法性能的影响. 而任务集的默认参数则结合实际情况和其他DAG任务集的相关参数进行设置. 默认参数设置为：

1）异构平台上核类别的数量在[2,15]随机生成，每个类别核的数量${M}_{s}$在[2,10]随机生成；每个类别s的利用率在$[1,{M}_{\mathrm{s}}/3]$的范围内随机生成；

2）任务集中，任务的数量在[2,20]的范围内随机生成；

3）用UUnifast方法^[23]为每个任务的s类别分配利用率；

4）对于每一个任务，周期在[100,1000]之内随机生成，默认每个任务的相对截止期等于周期；

5）每次随机选取1000个任务集分析平均性能.

对单个任务的参数进行设置，主要依据文献[4]，具体参数设置为：

1）每个DAG任务的任务结构采用文献[24]提出的方法生成. 任务的结点数在[15,30]的范围内随机生成；任意2个结点之间是否生成边，需要随机选定；假设选定为增加该边，需进一步判定，即增加该边后并行度Pr的值满足要求，则增加边，否则不增加；Pr值在[0,1]之间随机选择，注意Pr值越大说明并行度越低，Pr值为1则所有结点为串行.

2）采用UUnifast方法将已分配的利用率分配给每个结点，注意利用率是按类别分配的，结点的WCET值等于分配的利用率与周期的乘积.

算法的正确性采用接受率进行验证，接受率定义为可以被调度的任务集占所有被测试的任务集的比率. 图5（a）~（f）展示的是各个参数下的接受率. 其中，图5（a） ~ （d）是整个任务集参数对接受率的影响，图5（e） ~ （f）是单个任务中重要参数对接受率的影响. 图5（a）中，因为利用率增大，而每个类别的处理器个数不变，使得接受率逐渐下降；图5（b）中，由于利用率固定，每个类别的处理器个数增加，从而导致接受率逐渐提升；图5（c）表明，其他参数不变的情况下，任务集中任务个数越多任务越难以调度；图5（d）表明，类别越多，相同利用率下分给每个类别的利用率就会减少，而类别的增加也会导致处理器个数增加，从而使得接受率提升；图5（e）表明，单个任务内部结点个数对接受率的影响不显著；图5（f）表明，单个任务内部并行度越高（Pr值越低）接受率越高，这是因为并行度大则并行执行的可能性增大，从而提高接受率. 综上分析，实验数据符合各参数的性质和对实际任务可调度性的影响.

图  5  各种参数下的任务接受率

Figure  5.  Acceptance ratio of tasks under different parameters

下载: 全尺寸图片 幻灯片

图6（a） ~ （f）是对应接受率实验的各个参数下的效率实验. 其中，效率趋势中的每个点是所有1000个参加测试的任务集的平均分析时间. 注意，该时间随着分析设备硬件性能的不同会有所不同，其变化趋势可以表明与相关参数的关联性. 同样地，图6（a） ~ （d）为与任务集相关的参数，而图6（e）（f）是和单个任务相关的参数. 图6（a）（b）（d）中时间效率的变化趋势分别和图5（a）（b）（d）类似，这是因为接受率低，说明不可调度的任务集增多，在第1次出现不可调度任务时停止对任务集的分析从而出现平均分析时间下降的现象. 图6（c）的实验结果为时间效率先升高后降低. 图6（c）升高趋势的原因是当任务集接受率差不多时，任务集中任务个数增多，导致平均分析时间变长；图6（c）降低趋势的原因是由于接受率降低太多. 图6（e）中曲线变化表明，时间效率对任务内的结点个数是敏感的，当任务内的结点数增多时，时间效率呈增长趋势，且增长速度非常大. 图6（f）中时间效率变化趋势类似于图6（c），即先增后降，当任务集都可调度时任务分析时间随并行度下降而升高，当并行度降低到一定程度时接受率下降过多，导致任务集大量开始不可调度，从而导致平均分析时间下降.

图  6  各种参数下的效率

Figure  6.  Efficiency under different parameters

下载: 全尺寸图片 幻灯片

实验结果表明，本文提出的算法具有很好的接受率且任务的平均分析时间在嵌入式实时系统离线分析时间的可接受范围内，各个参数实验数据均符合实验预期.

6.   结　　论

本文针对异构平台上任务执行进行资源限制即规定任务只能执行在某一类处理器上这一特殊模型，进行了基于全局固定优先级限制性可抢占调度策略的可调度性分析. 首先，提出了整体的分析思路；然后，针对高优先级任务的干涉和低优先级任务的阻塞进行了分析；最后，结合最新的异构模型提出了一个整体的分析方法. 实验结果表明，本文提出的算法性能良好，能够在有效时间内完成任务的分析，且任务的可调度性和各个参数的关系符合实验预期.

作者贡献声明：韩美灵提出了算法思路并撰写论文；孙施宁负责实现算法并设计了相关实验方案；邓庆绪提出研究思路并指导修改论文.