工程科学与技术   2017, Vol. 49 Issue (2): 190-195
负载自适应的异构MPSoC任务调度算法研究
谢盈1,3,4, 吴尽昭2, 熊菊霞1,2,3, 张晖1,3     
1. 中国科学院 成都计算机应用研究所, 四川 成都 610041;
2. 广西民族大学 广西混杂计算与集成电路设计分析重点实验室, 广西 南宁 530006;
3. 中国科学院大学, 北京 100049;
4. 西南民族大学 计算机科学与技术学院, 四川 成都 610041
基金项目: 国家自然科学基金资助项目(11371003;11461006);广西自然科学基金资助项目(2012GXNSFGA060003);广西教育厅科研资助项目(201012MS274);西南民族大学中央高校基本科研业务费专项资金资助项目(2015NZYQN28)
摘要: 在异构MPSoC中,并行任务通过调度算法被分配到各个处理器核上运行,因而任务调度算法的优劣将直接影响异构MPSoC的应用性能。根据处理器核类型和任务间依赖关系,以减小任务间通信开销为目标,提出一种具备负载自适应能力的异构MPSoC任务调度算法。首先,将待调度任务集划分为多个并行任务子集;其次,在考虑处理器核负载的基础上,根据并行任务子集集合、处理器核集合及任务子集在各个核上的执行效率生成赋权二部图;最后,利用赋权二部图最大权匹配方法,将并行任务子集合理地调度到负载适应的处理器核上运行,以降低任务集的平均调度长度,并提高处理器核利用率,从而实现异构MPSoC应用性能的提升。仿真实验在不同的任务总数、任务最大前驱数、核类型、核数量的应用场景下,通过任务集平均调度长度、处理器核利用率两项指标对提出算法进行了定量分析。结果表明,提出算法能有效降低任务集平均调度长度,在实现负载自适应的同时提高异构MPSoC处理器核的利用率。
关键词: 异构MPSoC    负载自适应    任务划分    任务调度    
Research of Load-adaptive Task Scheduling Algorithm on Heterogeneous MPSoC
XIE Ying1,3,4, WU Jinzhao2, XIONG Juxia1,2,3, ZHANG Hui1,3     
1. Inst. of Chengdu Computer Application, Chinese Academy of Sci., Chengdu 610041, China;
2. Guangxi Key Lab. of Hybrid Computational and IC Design Analysis, Guangxi Univ. for Nationalities, Nanning 530006, China;
3. Univ. of Chinese Academy of Sci., Beijing 100049, China;
4. School of Computer Sci. and Technol., South West Univ. for Nationalities, Chengdu 610041, China
Abstract: In heterogeneous MPSoC, the parallel tasks were dispatched to each cores by task scheduling algorithm.Therefore, the performance of heterogeneous MPSoC directly was affected by task scheduling algorithm.A novel task scheduling algorithm with load-adaptive capability was proposed.In order to reduce the communication overheads, the algorithm divided task-set into task-subsets based on core types and tasks dependencies.Taking into the account of the cores load, then weighted bipartite graph was then created by task-subsets, cores and the execution efficiency of the task-subsets on each core.Finally, task-subsets were dispatched to appropriate load cores by finding a maximum weight matching in the weighted bipartite graph.In this way, the average scheduling length of task-set was reduced and the utilization of cores was improved, which jointly improved the performance of the heterogeneous MPSoC.Under the simulation scenarios with different number of tasks, maximum number of predecessors, number of core types, and number of cores, the proposed algorithm was quantitatively analyzed in terms of the average scheduling length of task-set and the utilization of the cores.The results showed that the proposed algorithm could effectively reduce the average scheduling length of task-set, and improved the utilization of heterogeneous MPSoC cores while achieving-adaptive loading.
Key words: heterogeneous MPSoC    load-adaptive    tasks division    tasks dispatch    

异构MPSoC (heterogeneous multi-processor system-on-chip) 把具有不同结构、功能、功耗及运算能力的多个处理核集成到一个芯片中,可满足不同应用领域的需求,如图像处理、数据仓库、数字信号处理等[1-2]。针对特定的应用背景,异构MPSoC除了集成通用处理器核外,还集成了其他专用处理器核,如DSP、GPU等,大幅增强了系统的信息处理能力[3-4]。为此,异构MPSoC被广泛应用于各类应用系统中,如IBM的Cell处理器[3]、NVIDIA的Tegra 4处理器[4]等。在实际应用中,任务通过调度算法被分配到异构MPSoC中的各个处理器核上运行,任务调度算法的优劣将直接影响异构MPSoC系统的性能[5-6],是被广泛关注的研究热点。

目前,启发式调度技术[7-8]因设计简单且能够获得较好的次优解,深受研究者的青睐,涌现出大量研究成果,如EZ算法[9]、TDS算法[10]、EDF算法[11]、CPOP算法[12]等。EZ算法以减少任务节点间通信开销为目的,将多个节点合并为簇,再以簇为单位进行任务映射。但在异构MPSoC环境下,算法由于没有考虑节点任务的类型,不能合理映射到适合的处理器核上,从而导致处理器核利用率低。TDS算法有选择性地复制前驱任务到处理器核重复执行,以增加处理器核计算开销为代价消除任务间的通信开销,但该算法可能因前驱任务开销过大而造成系统性能下降。EDF算法、CPOP算法等,都是根据任务属性构造任务优先级队列,依次将队列中的任务分配到能使其开始时间最早的处理器核上,但该类算法只对任务进行一次分配,未考虑任务优先级动态变化问题,灵活性较差。为解决以上问题,并将启发式调度技术应用于异构MPSoC,研究人员有针对性地提出HEFT算法[13]、DPA算法[14]等算法。HEFT算法将EDF算法应用于异构环境,根据任务到叶子节点的最大路径ranku的非递增顺序构造优先级队列,是异构环境下很多其他调度模型的基础,但该算法未考虑ranku的动态变化问题,不能保证在每次调度时选择当前具有最大ranku值的任务。DPA算法根据任务的价值和剩余执行时间定义任务的剩余价值密度,综合任务剩余价值密度和任务紧迫程度构造任务优先级列表,但该算法每次只选择一个任务进行映射,效率较低。

本文提出一种负载自适应的异构MPSoC任务调度算法 (heterogeneous load-adaptive task scheduling,HLTS),根据处理器核类型和任务间依赖关系,以减小任务间通信开销为目标,将待调度任务集划分为并行任务子集,并通过赋权二部图最大权匹配,将任务子集调度到负载适应的处理器核上运行,降低任务集的调度长度,提高处理器核的利用率。

1 负载自适应的异构MPSoC任务调度算法 1.1 公式系统模型

异构MPSoC由包含k种不同类型的N个处理器核组成,记为Ek={P1, P2, …, Pk}。其中,Pi表示i-type类型的处理器核集合,是一个4元组,Pi={Corei, Ratei, Volumei, Queuei}。

1) Corei={core1i, core2i, …, coreiNi}表示i-type类型的处理器核集合。其中,coreji表示第ji-type类型的处理器核,i∈{1, 2, …, k},1≤jNi$ \sum\limits_{i = 1}^k {{N_i}} = N $。异构MPSoC环境所有处理器核集合为:

$ \mathop \cup \limits_{i = 1}^k \;Cor{e^i} = \mathop \cup \limits_{i = 1}^k \;\mathop \cup \limits_{j = 1}^{{N_i}} \;core_{_j}^{^i}。$

2) Ratei={rate1i, rate2i, …, rateiNi}为Corei中各处理器核对应的运算速率集合,处理器核的运算速率由主频、流水线、缓存等因素共同决定,为简化模型,使用rateji刻画处理器核coreji的运算速率。

3) Volumei={v1i, v2i, …, viNi}为Corei中各处理器核对应存储容量集合。其中,vji表示处理器核coreji的存储容量。

4) Queuei={q1i, q2i, …, qiNi}为Corei中各处理器核对应的等待队列的集合。其中:qji表示处理器核coreji所维护的等待队列;|qji|为队列长度,表示coreji上排队等待执行的任务数。

Ek中不同类型的处理器核用于处理不同的计算需求,在对任务进行分配时需要根据任务类型将任务映射到具备相应能力的处理器核上运行,并尽可能降低任务集调度长度,提高处理器核利用率。调度长度是指完成任务集中所有任务所需时间的最大值。

n个具有依赖关系的待调度任务组成的任务集可通过DAG图表示,DAG=((task, type, weight), comm, VT)。

1) task={T1, T2, …, Tn}为任务节点集合,n≥1。Ti对应任务集中的第i个任务。

2) type=(t1, t2, …, tn) 为任务类型向量,任务Ti的任务类型为titi∈{1, 2, …, k}。

3) weight=(w1, w2, …, wn) 为任务权重向量,wi表示任务Ti的计算开销,wi∈R+

4) comm=(ci, j)n×n 为任务间通信开销矩阵,ci, j≥0。其中,ci, j=0表示任务TiTj没有通信依赖关系,ci, j>0表示任务TiTj间通信开销为ci, j

VT为虚拟起始节点,VT的计算开销为0,任务类型为0,VT到其直接后续的通信开销为0。

图 1所示,DAG图表示了n个任务的计算开销、任务类型、任务间依赖关系和通信开销。其中,T6T3T4的直接后续,任务节点间的通信开销为c3, 6S4, 6。后续任务需要使用其所有直接前驱任务的输出结果或占用的系统资源,因此,T6要等T3T4执行结束后,才能开始被调度执行。若任务类型不相等,如t3t4,则T3T4将被分配到不同类型的处理器核上运行。

图1 任务集DAG图 Fig. 1 DAG graph of task set

1.2 HLTS算法

为充分利用异构MPSoC的系统资源,在考虑任务类型并满足任务间依赖关系的前提下,HLTS算法以减小任务间通信开销为目标,将含有n个任务的任务集划分为m个并行任务子集,并依据赋权二部图最大权匹配的思想,将多个任务子集同时映射到负载适应的处理器核上并行运行,以降低任务集的调度长度,并提高处理器核的利用率。由此,HLTS算法可以表示如下:

$ \begin{align} &\{{{T}_{1}}, {{T}_{2}}, \cdots, {{T}_{n}}\}\xrightarrow{\text{division}}\{Tas{{k}_{1}}, Tas{{k}_{2}}, \cdots, Tas{{k}_{m}}\} \\ &\{Tas{{k}_{1}}, Tas{{k}_{2}}, \cdots, Tas{{k}_{m}}\}\xrightarrow{\text{HL-Mapping}}\{core_{_{x}}^{^{{{k}_{x}}}}, \cdots, core_{_{y}}^{^{{{k}_{y}}}}\} \\ \end{align} $

任务的直接前驱所在的集合称为前驱任务子集。任务分配以任务子集为单位,同一任务子集中的任务都在同一处理器核上执行。任务Ti的最大前驱开销MaxPredCost (Ti) 是Ti的所有同类型前驱任务子集的计算开销与通信开销之和的最大值, 有:

$ \begin{array}{l} MaxPredCost({T_i}) = \\ \left\{ \begin{array}{l} {\rm{max}}((\sum\limits_{h = 1}^{|Tas{k_j}|} {{r_h}} + {c_{j, i}}), (\sum\limits_{h = 1}^{|Tas{k_i}|} {{r_h}-{r_i}} )), {T_i} \in Tas{k_i};\\ {\rm{max}}((\sum\limits_{h = 1}^{|Tas{k_j}|} {{r_h}} + {c_{j, i}})), {T_i} \notin Tas{k_i}; \end{array} \right.\\ \;\;\;\;\;\;\;\exists {T_j}, \left( {{t_j} = {t_i}} \right) \wedge \left( {{T_j} \in pred\left( {{T_i}} \right)} \right) \wedge \\ \;\;\;\;\;\;\;\;\;\left( {{T_j} \in Tas{k_j}} \right) \wedge ({T_i} \notin Tas{k_j}) \end{array} $ (1)

其中:tj=ti表示任务TjTi具有相同任务类型;Tjpred(Ti) 表示任务TjTi的直接前驱;TaskjTj所在的任务子集,也是Ti的前驱任务子集;TiTaski表示Ti还未进行划分,TiTaski表示Ti已经划分到任务子集Taski中。

HLTS算法任务子集划分过程中,对任意任务Ti,若其任务类型与其所有直接前驱的任务类型都不相同,则Ti单独形成任务子集。如果Ti的多个具有相同类型的直接前驱分属于p个不同的任务子集,根据式 (1) 计算Ti的最大前驱开销MaxPredCost(Ti)(TiTaski),并将Ti加入到具有最大前驱开销的直接前驱Tj所在的任务集Taskj中,形成新的任务子集Taski。为进一步减小任务间通信开销,对于剩余的p-1个前驱任务子集,重新计算MaxPredCost(Ti)(TiTaski),若其中某个前驱任务子集Taskh合并到Taski中能减小Ti的最大前驱开销,即minimize(MaxPredCost(Ti)),则合并TaskhTaski中,否则,不合并。遍历完所有任务后,在生成的任务子集中删除冗余集合,最终得到m个任务子集。HLTS算法任务子集划分过程伪代码如下:

输入:待划分任务集:

for (i=1;i < =n; i++){

  if (Ti只有一个直接前驱Tj)

    if (ti==tj) Taski={Ti, Tj};

    else Taski={Ti}

  else{//Ti有多个直接前驱

    if (所有前驱任务子集类型≠ti)

      Taski={Ti};

else{

      计算MaxPredCost(Ti);

      Taskj具有MaxPredCost(Ti);

      Taski={Ti}∪Taskj;

      计算MaxPredCost(Ti);

      if ((minimize (MaxPredCost(Ti))==TURE))

      Taski=TaskiTaskh;

    }

  }

}//该阶段生成m个任务子集

for (i=1;i<=m; i++)

  for (j=i+1;j<=m; j++)

    if (TaskiTaskj) delete Taski;

//该阶段删除冗余任务子集

输出:完成划分的任务子集。

在任务集划分为m个并行任务子集后,如何在异构MPSoC环境下,将任务子集合理地调度到负载自适应的处理器核上运行,是HLTS算法下一步需要解决的问题。

处理器核coreji上的负载Loadji为当前等待队列qji中所有任务计算开销之和, 有:

$ Load_{_j}^{^i} = \sum\limits_{h = 1}^{|{q_{_j}^{^i}}|} {{w_h}}, i \in \left\{ {1, 2, \cdots, k} \right\} $ (2)

t时刻,平均负载AvgLoadti为所有i-type类型的处理器核负载的算术平均值,有:

$ AvgLoad_{_t}^{^i} = \frac{1}{{{N_i}}}\sum\limits_{j = 1}^{{N_i}} {Load_{_j}^{^i}}, {N_i} \le N $ (3)

在任务分配时,选择负载不高于平均负载的核进行分配。由式 (2) 和 (3) 可知,在t时刻系统可用的处理器核集合为:

$ Core = \mathop \cup \limits_{i = 1}^k \;\mathop \cup \limits_{j = 1}^{{N_i}} core_{_j}^{^i}(Load_{_j}^{^i} \le AvgLoad_{_t}^{^i}) $ (4)

待分配任务子集到处理器核的映射关系可表示为赋权二部图G=(Task, Core, E)。其中:顶点集Task对应待分配的任务子集;顶点集Core表示当前系统可用的处理器核集合;ETask中顶点到Core中顶点的边,表示任务子集和处理器核的映射关系。边的权重ei, j定义为:

$ {e_{i, j}} = \left\{ \begin{array}{l} 0, {t_i} \ne {k_j};\\ \frac{{rate_{_j}^{^{{k_j}}}}}{{\sum\limits_{h = 1}^{|q_{_j}^{^{kj}}|} {{r_h}} + \sum\limits_{h = 1}^{|Tas{k_i}|} {{r_h}} }}, {t_i} = {k_j} \end{array} \right. $ (5)

式中,ti为任务子集Taski中所有任务的任务类型, kj为处理器核corejkj的核类型。在异构MPSoC环境下,要根据任务类型将任务分配到适应的处理器核上运行,所以,当tikj时,ei, j=0;当ti=kj时,ei, j为在当前负载下corejkj执行完负载任务和任务子集Taski中所有任务的效率。

根据以上分析,HLTS算法任务映射是在赋权二部图G中寻找覆盖顶点集合Task的最大权匹配。

在赋权二部图G的顶点集TaskCore上确定一个函数LL满足

$ \begin{array}{l} L(Tas{k_i}) + L(core_{_j}^{^{{k_j}}}) \ge {e_{i, j}}, \\ \forall \;Tas{k_i} \in Task, \forall \;core_{_j}^{^{{k_j}}} \in Core \end{array} $

则称L为图G的一个顶点标号。L(Taski) 或L(corejkj) 称为顶点Taski或顶点corejkj的一个标号。如:

$\left\{ \begin{array}{l} L(Tas{k_i}) = \mathop {{\rm{max}}}\limits_{core_{_j}^{^{{k_j}}} \in core} ({e_{i, j}}), Tas{k_i} \in Task;\\ L(core_{_j}^{^{{k_j}}}) = 0, core_{_j}^{^{{k_j}}} \in core \end{array} \right. $

即为图G的一个顶点标号。

EL={Taskicorejkj|L(Taski)+L(corejkj)=ei, j}, 则具有边集ELG的生成子图被称为对应于顶点标号L的等价子图,记为GL

HLTS算法任务映射MapSegment过程如下:

1) 以下标递增的顺序,选择min (|Task|, |Core|) 个任务子集构成Task′,根据式 (4) 更新可用处理器核集合,得到赋权二部图G=(Task′, Core, E)。

2) 给出G的任意顶点标号L,求出GL,并在GL中以Taski的下标递增的顺序,选一个最大匹配M

3) 若M覆盖了Task′顶点集中的所有顶点,GL即为G的最大权匹配,转到步骤6);否则,选择Task集合中未被M覆盖,且下标最小的顶点x,令X={x}, Y=∅。

4) 若GL中集合X的邻集NGL(X)⊃Y,则转到步骤5);否则,NGL(X)=Y时,计算

$ \varepsilon =\underset{\begin{smallmatrix} Tas{{k}_{i}}\in X \\ core_{_{j}}^{kj}\in Y \end{smallmatrix}}{\mathop{\text{min}}}\,(L(Tas{{k}_{i}})+L(core_{j}^{{{k}_{j}}})-{{e}_{i,j}}) $

且由

$ {L^\prime }\left( v \right) = \left\{ \begin{array}{l} L\left( v \right)-\varepsilon, v \in X;\\ L\left( v \right) + \varepsilon, v \in Y;\\ L\left( v \right), 其他 \end{array} \right. $

给出新的顶点标号L′,用L′代替L。转到步骤2)。

5) 在NGL(X) 去除Y集后选取一个顶点y,如果y被匹配M覆盖,且yzM,则X=X∪{z},Y=Y∪{y},转到步骤4);否则,在GL中找一条M-可增长路P,将P加入匹配M,再转步骤3)。

6) 若未分配完所有任务子集,转到步骤1);否则,算法结束。

2 仿真实验及结果分析

仿真实验设置以下参数:任务总数n∈{25, 50, 75, 100, 125, 150},任务的最大前驱数max_in_degree∈{1, 3, 5, 7},处理器核类型k=3,处理器核个数分别为2、4、6。根据nmax_in_degreek的值,通过DAG图生成器可以生成72种不同类型的DAG图,用以表示任务类型和任务间依赖关系,再通过随机函数确定DAG图中每个任务节点的计算开销和任务间通信开销。

图 2为HLTS算法、HEFT算法和DPA算法平均调度长度的比较。由图 2可以看出,在任务数相同的情况下,HLTS算法的平均调度长度更小。

图2 不同任务数的平均调度长度 Fig. 2 Average scheduling length of different task's number

HLTS算法在考虑异构MPSoC处理器核类型、任务计算开销和任务间通信开销的基础上,将任务集划分为任务子集,以任务子集为单位每次将多个任务同时映射到适应的同类型处理器核。HEFT和DPA算法根据任务优先级,每次只分配一个任务到能够优先执行该任务的处理器核上,且没有充分考虑处理器核的负载。因此,当任务数越多,处理器核负载越大时,HLTS算法的平均调度长度明显优于HEFT和DPA算法。

图 34统计了k=3,处理器核个数分别为2、4、6,N=12(N为处理器核总个数,下同); 以及k=2,处理器核个数分别为2、2,N=4两种情况下,系统运行HLTS、HEFT和DPA算法的平均处理器核利用率。

图3 处理器核利用率 (k=3) Fig. 3 Utilization ratio of cores (k=3)

图4 处理器利用率 (k=2) Fig. 4 Utilization ratio of cores (k=2)

图 34均可以看出运行HLTS算法的异构MPSoC处理器核利用率更高。且由于HLTS算法每次分配一批任务到可用处理器核,而不是一个个地分配,其处理器核利用率在任务集运行之初增长较快。

值得注意的是,由图 34的对比可知,HLTS算法在处理器核异构性更大,核数更多的情况下,系统核利用率明显优于HEFT和DPA算法。

3 结论

异构MPSoC针对特定的应用背景,集成了多种类型的处理器核,大幅增强了系统的信息处理能力。在实际应用中,任务通过调度算法被分配到各类型处理器核上运行,任务调度算法已成为异构MPSoC的性能瓶颈。本文提出的HLTS算法,根据处理器核类型和任务间依赖关系,以减小任务间通信开销为目标,将待调度任务集划分为并行任务子集,并通过赋权二部图最大权匹配,将任务子集调度到负载适应的处理器核上运行。仿真实验结果表明,提出的算法有效降低了任务集的调度长度,提高了处理器核的利用率。

参考文献
[1]
Agerwala T, Chatterijee S. Computer architecture:Challenge and opportunities for the next decade[J]. IEEE Micro, 2005, 25(3): 58-69. DOI:10.1109/MM.2005.45
[2]
Patterson D, Hennessy J. Computer organization and design:The hardware/software interface[M]. 4th Ed. Boston, MA: Morgan Kaufmann Publishers, 2008.
[3]
Kahle J A, Day M N, Hofstee H P, et al. Introduction to the cell multiprocessor[J]. IBM Journal of research and development, 2005, 49(4): 589-604.
[4]
Lindholm E, Nickolls J, Oberman S, et al. NVIDIA Tesla:A unified graphics and computing architecture[J]. IEEE Computer Society, 2008, 28(2): 39-55.
[5]
Jiang Jianchun, Zeng Suhua, Qiu Baomei.A task scheduling model and method for control-oriented multicore systems[C].The 27th Chinese Control and Decision Conference (CCDC), Qingdao, 2015:5492-5497.
[6]
Yao X, Geng P, Du X.A task scheduling algorithm for multi-core processors[C].2013 International Conference on Parallel and Distributed Computing, Applications and Technologies (PDCAT), Taipei, 2013:259-264.
[7]
Zhang Keliang, Wu Baifeng.Task scheduling greedy heuristics for GPU heterogeneous cluster Involving the weights of the processor[C].2013 IEEE 27th International Conference on Parallel and Distributed Processing Symposium Workshops & PhD Forum (IPDPSW), Cambridge.2013:1817-1827.
[8]
Gogos C, Valouxis C, Alefragis P, et al. Scheduling independent tasks on heterogeneous processors using heuristics and column pricing[J]. Future Generation Computer Systems, 2016, 60: 48-66. DOI:10.1016/j.future.2016.01.016
[9]
Cheshmi K, Mohammadi S, Versick D, et al.A clustered GALS NoC architecture with communication-aware mapping[C].201523rd Euromicro International Conference on Parallel, Distributed, and Network-Based Processing, Turku, 2015:425-429.
[10]
Darbha S, Agrawal D P. Optimal scheduling algorithm for distributed memory machines[J]. IEEE Transactions on Parallel and Distributed Systems, 1998, 9(1): 87-91. DOI:10.1109/71.655248
[11]
Zhao Qingling, Gu Zonghua, Zeng Haibo. Resource synchronization and preemption thresholds within mixed-criticality scheduling[J]. ACM Transactions on Embedded Computing Systems (TECS), 2015, 14(4): 81.
[12]
Lin Yisong, Yang Xuejun, Tang Tao, et al. An integrated energy optimization approach for CPU-GPU heterogeneous systems based on critical path analysis[J]. Chinese Journal of Computers, 2012, 35(1): 123-133. [林一松, 杨学军, 唐滔, 等. 一种基于关键路径分析的CPU-GPU异构系统综合能耗优化方法[J]. 计算机学报, 2012, 35(1): 123-133. DOI:10.3724/SP.J.1016.2012.00123]
[13]
Topcuoglu H, Hariri S, Wu M Y. Performance effective and low-complexity task scheduling for heterogeneous computing[J]. IEEE Transactions on Parallel and Distributed Systems, 2002, 13(3): 260-274. DOI:10.1109/71.993206
[14]
Xia Jiali, Chen Hui, Yang Bing. A real-time task scheduling algorithm based on dynamic priority[J]. Chinese Journal of Computers, 2012, 35(12): 2685-2695. [夏家莉, 陈辉, 杨兵. 一种动态优先级实时任务调度算法[J]. 计算机学报, 2012, 35(12): 2685-2695. DOI:10.3724/SP.J.1016.2012.02685]