线性树模型的Sporadic任务多核调度方法研究
黄姝娟, 李天森, 马志昊, 肖锋     
西安工业大学 计算机科学与工程学院, 陕西 西安 710021
摘要: 当前大多数的实时周期任务的调度模型都是以相互独立的固定周期任务为中心,很少考虑周期允许变化的任务模型以及处理器在调度过程中的模型。针对Sporadic实时周期任务,设计了一种基于线性树(line tree, LT)的任务模型和处理器模型,并提出了任务线性树(task line tree, TLT)模型到处理器线性树(processer line tree, PLT)模型的转化算法。该算法将所有实时周期任务的最小公倍数作为层数基准,根据完整job替换法则,利用迁移job的节点替换同层的非迁移job的空节点,利用任务周期可变,job可提前发布的情况达到最优的多核调度结果。实验结果表明,所提方法相比PEDF、GEDF以及RMFF算法,不仅具有较高的核利用率和较低的时限丢失率,同时减少了上下文切换次数和迁移次数。
关键词: 多核    实时调度    线性树    调度模型    调度算法    

片上多核处理器任务调度方法中,研究者早期考虑的是基于由Liu和Layland[1]提出的相互独立的实时周期任务模型[2-10],随着研究的深入,又开始研究执行时间可以随着关键级别变化而变化的混合关键任务模型[11-13]和具有制约关系以及带有周期性的DAG任务模型[14-19]。这些模型对应的调度算法大都是基于RM(rate-monotonous)算法和GEDF(global earliest deadline first)以及PEDF(partitioned earliest deadline first)算法。如文献[2, 4-5]和文献[3, 6-7]针对相互独立的实时周期任务,分别对RM算法及GEDF算法进行分析并提出新的调度算法。文献[8]针对PEDF中的划分算法,提出一种改进的基于幂函数划分的EDF算法。文献[9-10]则是结合PEDF和GEDF各自优点,提出了旨在允许部分任务迁移的semi-partitioned调度算法。文献[11]将PEDF改进的semi-partitioned算法应用在混合关键模型中。文献[13]则是将周期性的DAG图放在混合关键模型中讨论。文献[14-16]在GEDF算法下讨论DAG图的调度。文献[17]则提出一种PEDF-omp的调度算法, 旨在解决类似DAG图模型的OpenMP并行执行。文献[18]在big.LITTLE体系结构下研究不同类型周期任务的动态分区调度方法。文献[19]则针对既考虑周期性又考虑依赖关系的实时周期性任务, 提出基于可延迟时间越短越优先(PLTSF, probably lag time shortest first)的调度方法。

上述所有任务模型中都有一个前提假设, 就是所有周期任务均为固定周期。而在实际情况中,有些任务的周期是可以进行调整的。因此本文则针对周期可变的Sporadic任务,提出相应的task模型、job模型以及fragment模型,将实时周期任务划分为不同层数节点,根据每个节点的实时性、周期性以及节点之间的层次关系进行相应的线性树模型转化,并根据具有时间迁移特性的job以及可变周期的任务调整某些层节点的位置,使得尽可能多的节点成为处理器上能够满足时限的执行节点。实验表明,上述调度方法与PEDF、GEDF、RMFF(RM first fit)算法比较起来,在延迟时间、系统利用率、上下文切换次数、系统抢占次数、时限丢失率方面都较优。

1 实时可变周期任务模型 1.1 task模型

假设一个实时系统τn个实时周期性任务组成, 记为τ={τ1, τ2, …τn}。每个实时周期任务都包含5个参数, 即τi(ri, ei, pi, di, fi)(1≤in)。其中ri表示发布时刻(release time), 即处理器核可以执行该任务的时刻。ei表示任务τi最坏情况下的执行时间(worst-case execution time, WCET)。piτi的最长周期; di表示时限(deadline),要求eidipi。如果di=pi, 称该系统为隐含时限的系统(implicit deadline system), 将其任务称为隐含时限任务。如果di < pi, 称该系统为包含时限系统(constrained deadline system), 将其任务称为包含时限任务。如果两者没有强制性的约束条件则称为任意时限(arbitrary deadline system)系统。fi表示该任务周期即将发生变化的规则函数, 通过该函数可以知道该任务周期发生变化的规律以及该任务此时可提前发布的时间片数量。如果不允许周期变化, 则fi=0。

1.2 job模型

在一个实时周期任务系统中, 所有任务在同一个时刻发布它们的第一个job, 将其称为同步系统, 否则称为异步系统。τi的第j(j≥1)次执行称为第j个job, 用τi, j(ri, j, ei, j, di, j, si, j)表示, 其中ri, jτi, j的最早可以开始执行的时间且ri, j=ri+(j-1)pi-si, j, di, jτi, j的绝对时限且di, j=ri+(j-1)pi+di, 如果di=pidi, j=ri+j×pi; ei, jτi, j的执行时间且ei, j=eisi, j=fi(j)表示τi, j允许提前发布的时间片数量, 如果si, j=0, 则表示不可以提前发布。

1.3 fragment模型

为了实现任务迁移和任务抢占, 现将τi, j根据ei, j的大小进一步划分为fragment, ei, j的第k个执行时间片用τi, jk(ri, jk, di, jk, si, jk)来表示。其中ri, jkτi, jk的最早可以开始执行的时间且ri, jk=ri, j+(k-1)-si, jk, di, jkτi, jk的最晚开始时间即di, jk=di, j-ei+k-1。由此可见ri, jkdi, jk。而si, jk为该τi, jk可提前执行的时间片数量。

本文的任务主要针对暗含时限的系统且都从时刻0开始, 那么任务可以简化为τi(ei, pi, fi)。如果任务不允许缩短周期, 则fi=0。该任务的第j个job记为τi, j(ri, j, ei, di, j, si, j), ri, j=(j-1)pi-si, j, di, j=j×pi, si, j=fi(j)。根据ei进一步划分为fragment, 用τi, jk(ri, jk, di, jk, si, jk)来表示。ri, jk=k-1+(j-1)pi-si, jk, di, jk=j×pi-ei+k-1, si, jk=si, j=fi(j)≤l, l=di-ei

2 TLT和PLT模型 2.1 相关定义

根据树定义Tree=(root, R), root为根节点, R为树中各节点之间的层次关系, 由树的特性可以知道树中的每个节点都有层次, 根为第一层, 根的孩子为第二层。若某个节点在第h层其孩子就在第h+1层, 树的深度为树中节点的最大层次。树T深度为H用layer(T)=H表示; 节点Pi所处的层次为h用layer(Pi)=h来表示。

假定一棵树型结构, 除了叶子节点外, 所有父节点都只有一个孩子节点, 这种树称为线性树LT(line tree)。

LT具有如下特征:

1) 树中第h层的节点数用Number(h)来表示。显然Number(h)=1。

2) 由于每层只有一个节点, 则该线性树上所有节点的个数等于该线性树的层数。

3) 节点之间具有一定的时间顺序关系。

线性树满足树的基本特征即在任意一棵树中:

1) 有且仅有一个特定的称为根的节点;

2) 当n>1时, 其余节点可分为n个互不相交的有限集合T1, T2, …, Tn, 其中每一个集合本身又是一棵树, 并且称为根的子树。

定义1  PLT(processor line tree)模型是由处理器核数M和所有任务周期的最小公倍数D决定的M棵线性树组成的森林, 记为F=(M, D)。其中M为线性树的个数, D为其中任何一个线性树的深度, 可以看出这M个线性树的深度都是D

定义2  TLT(task line tree)模型是由任务数量N和任务周期最小公倍数D决定的N棵线性树组成的森林, 记为F=(N, D)。其中N为线性树的个数, D为其中任何一个线性树的深度, 可以看出这N个线性树的深度都是D

在一个公共周期[0, D)内, 建立TLT模型的方法是将每个任务对应一棵LT树, 就是根据τi, jk(ri, jk, di, jk, si, jk)中ri, jk将该任务在[0, D)时间段内的所有fragments放在和该树深度h(1≤hD)对应的节点上, 由于ri, jk是从0开始的, 所以当ri, jk=h-1时, 就把τi, jk放在第h层次的节点上, 如果该树的h层节点没有对应的τi, jk节点, 称该树具有空节点层。如τ1(2, 3, f1)在公共周期为6的时间段[0, 6)内, 该τ1共分为2个job, 第一次job为τ1, 1, 而τ1, 1(0, 2, 3, f1(1))可以分为τ1, 11(0, 1, f1(1))和τ1, 12(1, 2, f1(1))2个时间片段, 称之为fragment, 第二次job为τ1, 2(3, 2, 6, f1(2)), 而τ1, 2可以分为τ1, 21(3, 4, f1(2))和τ1, 22(4, 5, f1(2))2个时间片段, 该任务形成的LT树如图 1所示。其中h=3和h=6为空节点层。所以不同任务由于eipi不同, 分得的fragment数量也都不尽相同。而这些fragment最终形成TLT的各种节点。

图 1 τ1(2, 3, f1)在[0, 6)时间段的TLT模型

可以看出, 如果第一个job的τ1, 1允许周期缩短, 则缩短的时间片f1(1)≤3-2=1, 即τ1, 1τ1, 2之间的空节点层数。另外, 空节点层以上的节点也可以下移至空节点层处, 不影响该节点按时完成。

同样, PLT模型中线性树的节点也是处理器核上准备执行任务job的时间片段fragments, 由于与TLT模型线性树的数量不同, 通常情况下, M < N。因此, 需要相应的转化算法, 即通过转化算法将TLT模型中的fragments指派到PLT模型中的节点上。本文考虑任务的job节点可以迁移情况。

定理  给定任何一个时刻值t, 针对某个任务τi(ei, pi, fi), 如果fi=0判断该任务在该时刻有fragments发布的前提条件是qei, 其中, q的余数。

证明  由fragments发布的最早执行时间ri, jk可知, 如果t时刻有fragments发布, 那么必然有

ri, jk=t,由题意可知

(1)
(2)

将2个公式联立起来得

得证。

推论1  任何一个时刻t都能唯一对应于TLT模型的某一层。

证明  令t=n×D+k, 其中D为所有任务周期的最小公倍数, 因为k < D, 故可将t时刻对应于第n个[0, D]周期内的第h=k+1层。根据定理, 如果的余数pei, 则对应的fragments为τi, jp(n×(h-1), n×(h+pi-ei)), 其中, 否则就是空节点层。

推论2  一个TLT模型中某个任务τi(ei, pi, fi)形成的LT在h层不会出现空节点层的前提条件是。其中p的余数。

证明  根据推论1, 在TLT模型中, 任何时刻都可以对应其中一个层, 那么某个h层也可以对应其中某一个fragment的发布时刻, 但由于该fragment所在的job提前发布至h′层, 则该h层如果不为空节点层必然存在

(3)

假设h′层对应Ti, jk的发布时刻

式中,k=1,根据定理及公式(3)

,得证。

根据上述定理和推论, 可以得出在TLT模型中, 任何一个h层次对应的第个job所能提前的时间片函数, 对应的fragment为的余数q, 若则该层为空节点层。

2.2 实时系统的TLT模型和PLT模型

考虑一个任务系统Γ={τ1, τ2, …, τN}有N个任务要分配到M个处理器上, 该系统具有TLT模型和PLT模型分别简单记为TLTΓ={TLT1, TLT2, …, TLTN}和PLTΓ={PLT1, PLT2, …, PLTM}。所有任务的job被划分为不同的fragment分布在TLTΓ的不同节点上, 然后根据一定的指派算法被指派在PLTΓM棵PLT树节点上。其中所有PLTp(1≤pM)均为一棵深度为D的树, 这里D为所有任务周期的最小公倍数, D=[p1, p2, …, pn](D>1), PLTΓ中的一棵PLT树就对应一个处理器核调度的一个顺序。

假设系统中所有实时周期任务都已经确定, 且都是可以被抢占和被迁移的, 如果确定了PLT模型中所有节点, 那么也就确定了系统的调度方案。下面来说明确定每棵线性树各节点被指派fragments的方法。TLT模型中的LT树节点要么是空节点要么是job的fragments,即τi, jk。如某实时系统中的任务τ1(4, 6), τ2(2, 3), τ3(5, 6), τ4(2, 3), τ5(1, 2), τ6(2, 3, f6), 其中。要被分配到M=4的处理器核上进行调度。将实时系统6个任务对应到TLT的6棵树上, 如图 2所示。

图 2 实例对应的TLT模型

以该实例来说明TLT模型与PLT模型之间的转化方法, 如图 3所示。

图 3 实例中TLT模型与PLT模型之间的转化方法

得到PLT的结果如图 4所示。

图 4 转化为PLT的最终结果

图 4结果可以看出, 在一个公共周期内, τ5τ6的迁移次数都是1次, 在迁移过程中job没有被切割开, 都是整体迁移, 整个过程没有抢占及上下文切换开销。因为抢占及上下文切换开销发生在节点fragments,即τi, jk(k < ei)的孩子是τu, vw(ui), 即该job的所有fragments还未完成, 下层节点由别的job占用。

3 延迟因子及TLT-PLT转化方法 3.1 延迟因子确定

如果一个fragments,即τi, jk(ri, jk, di, jk, fi(j))始终没有机会被指派到PLT模型中LT树的某层, 则称为fragments丢失。如果一个fragments,即τi, jk(ri, jk, di, jk, fi(j))被指派到PLT树h层, 当di, jk+1≥h, 则称该层为fragments的时限满足层,当di, jk+1 < h, 则称该层为fragments的时限延迟层。该节点为延迟节点。所有fragment丢失节点都为延迟节点。

定义3  定义每个节点的延迟因子为hlate(τi, jk)=h-di, jk, 如果hlate(τi, jk)>1则该节点为延迟节点, 如果hlate(τi, j-1k)=h-di, j-1k < 1则该节点τi, jk可申请该周期内的连续节点发布时间提前至ri, jx+h-di, j-1x (x=1, …, k), 如果系统在允许范围内, 则该节点为可提前发布时间节点。

定义4  在指派算法S下, 定义一个层次分配函数为hs(x), 该函数表示fragments x被指派在哪个层, 定义Is(x)表示指派在哪棵线性树上。如果没有被指派则这两个函数值均为0。

在指派算法S下, 如果一个任务Ti在公共周期内发布的所有τi, j的所有fragments都被指派到LT树上, 且都时限满足, 那么该任务在S下可调度, 如果系统内所有任务都可调度, 那么该系统在S下可调度。

3.2 TLT-PLT转化算法

本文根据PLT空节点层和TLT需要迁移的节点层的情况实现TLT向PLT的转化算法。

算法:TLT-PLT转化算法

  Input: Enter TLT Set

     N: The number of tasks

     M: The number of processors

  Output: Header Pointer of PLT

1: i=1;

2: While iM do

  /*Select minimum quantity empty layer number of LT from TLT into PLT*/

3: j=findMiniEmptyLayer(TLT);

4: Trans(j, TLT, PLT);

5:Delete(j, TLT); /*Delete the LT from TLT set*/

6: i=i+1;

7: end While

  /*count the node layer number before every empty layer for every LT in TLT */

8: Count(TLT, nodeLayerTLT);

9: Count_emptyLayer(PLT, emptyLayerPLT); /

  *count the empty layer for every LT in PLT*/

10: While TLT set is not NULL do

  /*Select the maximum number of the nodeLayerTLT equal or smaller than the number of emptyLayerPLT */

11: flag=FindSame(nodeLayerTLT, emptyLayerPLT)

12: if(flag!=-1 & & Layer is equal)

  /*move the node layer of LT in TLT into the empty layer of PLT*/

13: Trans(flag, nodeLayerTLT, emptyLayerPLT, TLT, PLT);

  /*move the node layer of LT in PLT to the same empty Layer */

14: else if (flag!=-1 & & Layer is not equal)

15: Move(emptyLayerPLT, PLT);

16: Trans(flag, nodeLayerTLT, emptyLayerPLT, TLT, PLT)

17: else if(advancedPermitted(flag, function))

18: Advance(flag, TLT); /*count the advanced function if the node is permitted advanced */

19: else

20: FragmentMiss (flag, TLT); /*put the LT node into the fragment miss set*/

21: end if

22: Delete(flag, TLT);

23: end While

上述算法核心思想如下:

首先, 从TLT中找出M个空节点层数较少的LT转移到PLT中, 并从TLT中删除这些节点。

其次, 计算TLT中每个LT的空节点层数之前的连续节点数, 计算PLT中连续空节点层数的数量。

最后, 从大到小在TLT中找出连续节点层数与PLT中连续空节点数层数相同的PLT树, 如果匹配则直接将这些节点与对应的PLT中的空节点层进行交换, 并删除TLT中交换过的节点; 如果没有匹配的则将PLT中的节点进行层数下移至数量相同的空节点层, 再进行交换并删除TLT中交换过的节点; 如果找不到对应的层数, 或者TLT中无法再通过下移空节点层来匹配TLT中的节点层则将剩余节点放置到fragment丢失集合中。

3.3 处理器预分配算法

下面就是利用TLT-PLT转化算法的整体方案。

首先, 根据系统中所有实时周期任务τi={ri, ei, pi, di, fi}(1≤in)的属性值计算所有任务周期的最小公倍数D, 然后计算每个任务在整个公共周期内的job数量和每个job的相关执行属性τi, j(ri, j, di, j, ei, j, fi(j)), 再根据job数量以及属性值计算不同的fragment的相关属性τi, jk (ri, jk, di, jk, fi(j))。

其次, 根据τi, jk (ri, jk, di, jk, fi(j))的相关属性值以及所有任务数量ND, 建立一棵深度为D数量为N的TLT树集合{TLT1, TLT2, …, TLTn}, 该集合中每一棵树都是线性树, 每个树深度都为D

再次, 将其按照TLT-PLT转化算法将TLT树转化为PLT树, 就可以将τi, jk (ri, jk, di, jk, fi(j))指派到层数为hM棵PLT树中进行执行。

3.4 应用实例处理器分配结果

2.2节的实例在GEDF、PEDF、RMFF以及TLT-PLT 4种调度算法的处理器分配结果如表 1~4所示, 在6个时间片内的性能统计如表 5所示。

表 1 实例在GEDF调度算法下的运行结果
处理器 时间
(0, 1] (1, 2] (2, 3] (3, 4] (4, 5] (5, 6]
P1 τ5, 11 τ3, 11 τ3, 12 τ3, 13 τ2, 21 τ2, 22
P2 τ6, 11 τ6, 12 τ1, 11 τ1, 12 τ1, 13 τ1, 14
P3 τ4, 11 τ4, 12 τ5, 21 τ6, 21 τ6, 22
P4 τ2, 11 τ2, 12 τ4, 21 τ4, 22 τ5, 31
注: P1处理器上τ2, 21抢占了τ3, 14, τ3, 14τ3, 15丢失。
表 2 实例在PEDF调度算法下的运行结果
处理器 时间
(0, 1] (1, 2] (2, 3] (3, 4] (4, 5] (5, 6]
P1 τ1, 11 τ1, 12 τ1, 13 τ1, 14
P2 τ3, 11 τ3, 12 τ3, 13 τ3, 14 τ3, 15
P3 τ2, 11 τ2, 12 τ4, 11 τ2, 21 τ2, 22
P4 τ5, 11 τ6, 11 τ6, 12 τ5, 21 τ6, 21 τ5, 31
注: P3处理器上τ2, 21抢占了τ4, 12, P4处理器上τ5, 31抢占了τ6, 22, τ4, 12τ6, 22丢失。
表 3 实例在RMFFF调度算法下的运行结果
处理器 时间
(0, 1] (1, 2] (2, 3] (3, 4] (4, 5] (5, 6]
P1 τ1, 11 τ1, 12 τ1, 13 τ1, 14
P2 τ2, 11 τ2, 12 τ5, 21 τ2, 21 τ2, 22 τ5, 31
P3 τ3, 11 τ3, 12 τ3, 13 τ3, 14 τ3, 15
P4 τ4, 11 τ4, 12 τ6, 11 τ4, 21 τ4, 22
注: P4处理器上τ4, 21抢占了τ6, 12, τ5, 11τ6, 12丢失。
表 4 实例在TLT-PLT调度算法下的运行结果
处理器 时间
(0, 1] (1, 2] (2, 3] (3, 4] (4, 5] (5, 6]
P1 τ5, 11 τ3, 11 τ3, 12 τ3, 13 τ3, 14 τ3, 15
P2 τ6, 11 τ6, 12 τ1, 11 τ1, 12 τ1, 13 τ1, 14
P3 τ2, 11 τ2, 12 τ6, 21 τ6, 22 τ2, 21 τ2, 22
P4 τ4, 11 τ4, 12 τ5, 21 τ4, 21 τ4, 22 τ5, 31
表 5 实例在6个时间片内4种算法下的性能比较
算法 抢占及上下文切换次数 Fragment丢失率 核利用率
GEDF 1 2 0.917
PEDF 2 2 0.833
RMFF 1 2 0.833
TLT-PLT 0 0 1.0
4 实验及结果分析

本文的仿真实验平台是在4核Intel core(TM)2 Quad CPU 2.66 GHz内存为3.4G的硬件环境下运行Ubuntu Linux10.04 2.6.33 -29实时内核, 采用Codeblocks-v10.05编写仿真测试程序。在实验设计时, 选择了处理器核数MN个任务总利用率之间3种不同的关系: 「Usum >m, 「Usum =m, 「Usum < m, 针对随机输入的实时周期任务进行了多组实验求得平均值, 为了进行实验结果对比分析, 使用如下的性能评价指标:

上下文切换和抢占次数。通过计算不同任务job之间上下文切换次数以及job的fragment被打断情况的计数来统计抢占次数, 说明不同算法的额外开销。开销太大则耗时多, 任务响应时间长。

核利用率。在算法分配过程中如果PLT模型中线性树有空节点层, 则说明核在该层处于空闲状态, 为了描述核利用情况定义核利用率为该核对应的线性树的非空节点个数与树深度的比值。该比值是PLT模型对核利用情况的一个反映。该值越大说明该模型和调度方法对核的利用越充分。

Fragment丢失率。由于PLT模型中的工作在调度过程中存在时限不满足情况, 为了考察时限不满足严重程度定义fragment丢失率为fragment丢失时限节点的数量总和与所有fragments数量总和的比值。

根据以上的评价指标, 对可并行执行的工作分别采用GEDF算法、PEDF算法、RMFF算法以及TLT-PLT转化算法进行调度, 在500个时间片内对系统的上下文切换次数以及抢占次数、核利用率以及fragment丢失率进行了统计。

图 5展示了在3种情况下, 每种情况随机输入10组数据得出的上下文切换次数和抢占次数的平均值。从图 5中可以看出在负载量较大情况下, TLT-PLT算法的上下文切换及抢占次数明显小于GEDF、PEDF和RMFF算法, 而在负载量小的情况下对比不是很明显, 因此本文仅针对负载量较大的情况, 3种算法的核总利用率和fragment丢失率的情况分别如图 6图 7所示。

图 5 3种情况下上下文切换和抢占次数测试
图 6 4种算法核利用率增长情况
图 7 固定时间片下4种算法的fragment丢失率

核利用率效果如图 6所示。结果显示出采用TLT-PLT算法的核利用率效果和GEDF基本接近且速度快, 而比PEDF和RMFF要好得多。原因是GEDF是允许任务迁移且由最近时限来决定优先级, 效率高迁移开销大; 而PEDF是不允许任务迁移利用率较低; RMFF通过利用率进行首次适应匹配, 也不允许迁移, 利用率也比较低。而TLT-PLT算法结合三者的优点, 即允许部分任务迁移又利用LT的空闲节点进行节点空闲节点自适应匹配, 且通过调整发布时间可以快速使得任务被调度, 因此效率较高。

图 7中可以看出任务的fragment丢失率随着时间的持续而增长, 但TLT-PLT增长的趋势较低。分析原因发现由于GEDF算法和RMFF以及PEDF算法优先级是根据自身的参数(时限和利用率)来决定的, 并没有综合考虑任务的实际执行情况, GEDF由于迁移频繁而导致有些任务来不及执行就放弃了, PEDF和RMFF算法不能根据时间灵活迁移导致很多任务无法及时执行。而TLT-PLT算法从一开始就利用最小公倍数分时间段考虑任务在实际执行过程中出现的迁移情况以及fragment是否能满足的问题, 并通过调整发布时间使得fragment尽量减少丢失, 所以得到最好的效果。

5 结论

随着多核技术在嵌入式领域的快速发展,围绕片上多处理器实时调度问题进行了大量的研究工作,所提出的调度模型和调度算法大都只针对任务模型。本文从线性树模型出发,根据Sporadic任务周期可变的情况,建立实时周期任务的task模型、job模型以及fragment模型,提出实时周期任务在多核处理器上的TLT模型和PLT模型和相应的转化算法,不仅维持了系统利用率和减少时限丢失情况,而且还使得切换次数和抢占次数降到比较低的水平。文章首先描述了TLT任务模型和PLT模型,接着说明了该模型的相关性质和相关定理,随后定义了延迟因子以及相应的转化算法。仿真实验表明所采用的TLT-PLT转化算法不但比PEDF、GEDF、RMFF算法在核利用率以及时限丢失率方面都较优而且还减少了抢占次数和上下文切换次数。

参考文献
[1] LIU C L, LAYLAND J W. Scheduling algorithms for multiprogramming in a hard-real-time environment[J]. Journal of Association for Computing Machinery, 1973, 20(1): 46-61. DOI:10.1145/321738.321743
[2] 王涛, 刘大昕. 多处理器单调速率任务分配算法性能评价[J]. 计算机科学, 2007, 34(1): 272-277.
WANG Tao, LIU Daxin. The performance evaluation of rate monotonic tasks assignment algorithms on multiprocessor[J]. Computer Science, 2007, 34(1): 272-277. (in Chinese) DOI:10.3969/j.issn.1002-137X.2007.01.072
[3] BERTOGNA M, CIRINEI M, LIPARI G. Schedulability analysis of global scheduling algorithms on multiprocessor platforms[J]. IEEE Trans on Parallel and Distributed Systems, 2009, 20: 553-566. DOI:10.1109/TPDS.2008.129
[4] 张忆文, 王成, 张惠臻. 基于RM策略的资源受限偶发任务调度算法[J]. 华中科技大学学报, 2017, 45(7): 115-121.
ZHANG Yiwen, WANG Cheng, ZHANG Huizhen. Sporadic tasks scheduling algorithm with resources constraints based on RM scheme[J]. Journal of Huazhong University of Science and Techndogy, 2017, 45(7): 115-121. (in Chinese)
[5] ZHANG Shaohui. Research on rate monotonic algorithm and schedulability analysis in real-time system[J]. American Journal of Computer Sciences and Applications, 2019, 2(20): 1-6.
[6] YANG K, ANDERSON J. On the soft real-time optimality of global EDF on uniform multiprocessors[C]//Processing of 2017 IEEE Real-Time Systems Symposium, Paris, France, 2017: 319-330
[7] ZHANG Y, GUO Z, WANG L, et al. Integrating cache-related preemption delay into GEDF analysis for multiprocessor scheduling with on-chip cache[C]//Processing of 2017 IEEE Trustcom/ BigData- SE/ICESS, Sydney, Australia, 2017: 815-822
[8] 王浩, 张凤登. CAN总线中改进的EDF调度算法可调度性分析[J]. 计算机测量与控制, 2020, 28(8): 238-241.
WANG Hao, ZHANG Fengdeng. Schedulability analysis of improved EDF scheduling algorithm in CAN-bus[J]. Computer Measurement & Control, 2020, 28(8): 238-241. (in Chinese)
[9] HOBBS C, TONG Z, BAKITA J, et al. Statically optimal dynamic soft real-time semi-partitioned scheduling[J]. Real-Time Systems, 2021, 57(1/2): 97-140.
[10] TIAN Yuchu, DAVID Charles Levy. Handbook of real-time computing[M]. Singapore: Springer Singapore, 2019.
[11] ZHANG F. Improvement to semi-partitioned cyclic executives for mixed-criticality scheduling on multiprocessor platforms[J]. IEEE Access, 2020, 8(223): 606-617.
[12] MAJUMDER S, NIELSEN J F D, BAK T. PaRTAA: a real-time multiprocessor for mixed-criticality airborne systems[J]. IEEE Trans on Computers, 2020, 69(8): 1221-1232.
[13] MEDINA R, BORDE E, PAUTET L. Generalized mixed-criticality static scheduling for periodic directed acyclic graphs on multi-core processors[J]. IEEE Trans on Computers, 2021, 70(3): 457-470. DOI:10.1109/TC.2020.2990229
[14] SUN J, GUAN N, JIANG X, et al. A capacity augmentation bound for real-time constrained-deadline parallel tasks under GEDF[J]. IEEE Trans on Computer-Aided Design of Integrated Circuits and Systems, 2018, 37(11): 2200-2211. DOI:10.1109/TCAD.2018.2857362
[15] SUN J, GUAN N, CHANG S, et al. Capacity augmentation function for real-time parallel tasks with constrained deadlines under GEDF scheduling[J]. IEEE Trans on Computer-Aided Design of Integrated Circuits and Systems, 2020, 39(12): 4537-4548. DOI:10.1109/TCAD.2020.2966486
[16] JIANG X, GUAN N, LIU D, et al. Analyzing GEDF scheduling for parallel real-time tasks with arbitrary deadlines[C]//Processing of in 2019 Design, Automation & Test in Europe Conference & Exhibition, Florence, Italy, 2019: 1537-1542
[17] WANG Y, JIANG X, GUAN N, et al. Partitioning-based scheduling of openmp task systems with tied tasks[J]. IEEE Trans on Parallel and Distributed Systems, 2021, 32(6): 1322-1339. DOI:10.1109/TPDS.2020.3048373
[18] MASCITTI A, CUCINOTTA T, MARINONI M, et al. Dynamic partitioned scheduling of real-time tasks on ARM big.LITTLE architectures[J]. Journal of Systems and Software, 2021, 173(1): 1-14.
[19] 黄姝娟, 朱怡安, 李兵哲, 等. 具有依赖关系的周期任务实时调度方法研究[J]. 计算机学报, 2015, 38(5): 999-1005.
HUANG Shujuan, Zhu Yian, LI Bingzhe, et al. Real-time scheduling method for dependency period tasks[J]. Chinese Journal of Computers, 2015, 38(5): 999-1005. (in Chinese)
Research on multi-core scheduling method for Sporadic task by line tree mode
HUANG Shujuan, LI Tiansen, MA Zhihao, XIAO Feng     
School of Computer Science and Engineering, Xi'an Technological University, Xi'an 710021, China
Abstract: At present, most of the scheduling models for real-time periodic tasks are established based on independent fixed periodic tasks and few by considering the task model with period allowed to change and the processor model in the scheduling process. In this paper, a task model and processor model based on line tree(LT) for sporadic real-time periodic tasks are designed, and a transformation algorithm from task line tree(TLT) model to processor line tree(PLT) model is proposed. The algorithm takes the least common multiple of all real-time periodic tasks as the benchmark of layer number, and based on the complete job replacement rule, the minimum common multiple of all real-time periodic tasks is used as the reference of layer number. In order to achieve the optimal multiprocessor scheduling result, the method of replacing the empty node of non-migrating job with the node of migrating job and the condition of allowing job to publish tasks ahead of time with variable cycle are used. Experimental results show that comparing with PEDF, GEDF and RMFF, the present method not only has higher core utilization and lower time loss rate, but also reduces the number of context switching and migration.
Keywords:      real-time scheduling    line tree    scheduling model    scheduling algorithm    
西北工业大学主办。
0

文章信息

黄姝娟, 李天森, 马志昊, 肖锋
HUANG Shujuan, LI Tiansen, MA Zhihao, XIAO Feng
线性树模型的Sporadic任务多核调度方法研究
Research on multi-core scheduling method for Sporadic task by line tree mode
西北工业大学学报, 2022, 40(4): 935-943.
Journal of Northwestern Polytechnical University, 2022, 40(4): 935-943.

文章历史

收稿日期: 2021-10-13

相关文章

工作空间