嵌入式系统的细粒度多处理器实时抢占式调度算法

李 扬 王春明

1(江苏商贸职业学院电子与信息学院 江苏 南通 226011) 2(南通大学计算机科学与技术学院 江苏 南通 226019)

0 引 言

如今AMD与Intel等处理器厂商已经发布8个核心以上的CPU，未来CPU的核心数量更可能达到百级，由此增加了多处理器、多任务调度问题的难度[1]。传统的研究大多集中于单处理器，而针对单处理器的诸多研究成功无法扩展至多处理器系统[2]。为了充分利用多核心处理器的计算能力，任务调度算法需要支持任务之间的并行化[3-4]，此外，对于多线程的任务，更可能发生同一任务的不同线程在多个处理器核心上并发执行的情况，因此，细粒度的任务调度算法成为一个亟待解决的问题[5]。

实时调度研究中有两个基本问题：(1) 调度算法需为任务或线程分配合适的优先级，且满足系统的截止期约束；(2) 为调度算法提供可调度性分析，证明算法满足系统的截止期约束[6-7]。以往的研究大多从单线程多任务、多处理器的实时调度方面解决上述两个问题。近期，出现多个考虑多线程多任务的多处理器调度研究，其中可调度性分析的研究为主要目标，但针对此场景的调度算法优化研究相对较少[8-10]。

单线程任务中，作业是基本的调度单位，该场景的实时调度算法根据优先级变化的时间点主要分为三类[11]：(1) 任务级固定优先级算法；(2) 作业级固定优先级算法；(3) 动态优先级算法。如果将线程作为调度单位，则为调度问题增加了一个维度，从而提升了问题的复杂度。

文献[12]提出了最优优先级分配算法(OPA)，该研究证明了OPA是任务级固定优先级分配问题的最优算法，本文期望将OPA算法扩展至线程级调度场景，但由此带来两个问题：线程级依赖关系与线程级调度算法的可调度性分析。本文首先采用任务分解方法[13]为各线程分配偏移时间与截止期；然后，基于干扰的线程级分析证明本文扩展调度算法与OPA算法兼容，从而证明本文线程级调度算法也是最优调度算法；最终，设计了完整的线程级调度算法。

1 系统模型

1.1 有向无环图(DAG)任务

(a) DAG任务

(b) 任务分解图1 任务示意图

1.2 任务分解

可将一个DAG任务分解为独立、有序的子任务集合，线程之间具有依赖关系与执行出口，为DAG任务的各线程分配对应的偏移与截止期。

将任务τ分解产生的线程集合设为τdecom，τdecom中线程的数量设为n。对于任务τi，定义任务的主线程为θi,1,τi中其他各线程θi,p表示为(Ti,p,Ci,p,Di,p,Oi,p)，其中Ti,p是最小间隔(等于Ti)，Ci,p与Di,p分别表示最坏情况的运行时间及其截止期，Oi,p为对应的偏移(从Oi,1=0开始)。

1.3 CPU平台与调度算法

假设多核CPU由m个相同的处理器组成，调度策略为全局任务-线程级固定优先级调度，每个线程θi,p可以动态地在处理器之间迁移，且为所有线程分配静态的优先级Pi,p。将优先级高于Pi,p的线程集合设为hp(θi,p)。

2 可调度性分析

DAG任务分解为线程级之后，各线程即设置了偏移与截止期，无需考虑线程间的依赖关系。基于干扰的可调度性分析兼容OPA，所以本文采用该方案[15]。

2.1 基于干扰的可调度性分析

线程级干扰可如下定义：

干扰Ik,q(a,b)：如果θk,q为ready状态,但[a,b)中更高优先级的线程正在运行,此时的时隙总和定义为干扰Ik,q(a,b)。

干扰I(k,q)→(k,q)(a,b)：[a,b)中θi,p正在运行，且θk,q为ready状态，此时的时隙总和定义为干扰I(k,q)→(k,q)(a,b)。

Ik,q(a,b)与I(k,q)→(k,q)(a,b)之间的关系是可调度性分析的重要基础，Ik,q(a,b)与I(k,q)→(k,q)(a,b)之间的关系可推导为[16]：

(1)

(2)

文献[15-16]定义了以下可调度性判定条件：

引理1 当且仅当所有线程θk,q满足以下条件，则m个相同处理器组成的多处理器平台中集合τdecom是可调度的：

(3)

文献[17]对引理1扩展，获得了以下线程级判定条件：

引理2如果τdecom是可调度的，则τ也是可调度的。

2.2 基于工作负载的可调度性分析

首先需要确保各线程的截止期早于任务的截止期(引理1)，然后需要计算其他线程对目标线程θk,q的干扰(式(3))。

考虑两个场景计算最大工作负载：i≠k与i=k，原因在于i=k表示两个干扰线程属于同一个任务，说明τi中作业释放的偏移已经自动给定。

2.2.1i≠k情况的负载最大化

为了简化描述，对于时间段(x,y]，如果作业的启动时间在x之前，截止期在(x,y]内，则简称为前置作业；如果作业的启动时间与截止期均在(x,y]内，则简称为期内作业；如果作业的启动时间在(x,y]内，截止期在y之后，则简称为后置作业。

假设τi的作业为周期地启动，定义Δi(x,y)为(x,y] 中前置任务启动时间点与x的差值，如图2所示。

图2 τi中所有线程的最大工作负载

对于一个给定的Δi(x,y)，如果(x,y]时长为l，可将(x,y]时间段分为前置时段CIi(l,Δi(x,y))，期内时段BDi(l,Δi(x,y))以及后置时段COi(l,Δi(x,y))，三种时段可表示为：

CIi(l,Δi(x,y))=min(Ti-Δi(x,y),l)

(4)

(5)

COi(l,Δi(x,y))=l-CIi(l,Δi(x,y))-BDi(l,Δi(x,y))

(6)

对于给定的Δi(x,y)，(x,y]中每个线程的负载贡献度(如图2所示)可计算为：

(7)

式中：

对于偶发任务：此时可简单地检查(x,y]中θi,p的运行量，则Δi(x,y)上界为Wi,p(l,Δi(x,y))。

考虑任务τi中Δi(x,y)的所有可能值，优先级高于θk,q的所有线程工作负载之和即为τi对线程θk,q的最大干扰的上界，表示为：

(8)

2.2.2i=k情况的负载最大化

该情况下τk的作业被同一个任务干扰，因此可自动地决定τk中作业启动的偏移时间。为了计算i=k情况的最大工作负载，本文仅需要考虑与线程θk,q重叠的部分执行窗口，使用式(7)可计算这些线程的负载贡献量。因此，τk中优先级高于线程θk,q的其他所有线程最大负载计算为：

Ck,q+1)

(9)

基于式(8)和式(9)计算的干扰上界，为本文线程级调度算法设计了以下可调度性判定：

理论1对于m个相同的处理器平台的线程级调度算法，如果每个线程θk,q满足以下的不等式，则集合τdecom为可调度。

(10)

证明上文所述Wk(Dk,q)是θk,q运行窗口中优先级高于pk,q的最大运行量。当且仅当A优先级高于B时，A才对B产生干扰，式(3)左式的上界为式(10)的左式。根据引理1，可证明该理论。

3 线程级最优优先级分配算法

问题描述为：给定一个分解线程的集合τdecom，为每个线程θi,q∈τdecom分配优先级Pi,p，因此根据基于工作负载的可调度性判定(理论1)认为分解集合为可调度的。

OPA算法通过优先级分配为各任务分配一个优先级，如果所有任务τi满足以下两个条件，则该可调度性判定为OPA兼容：

条件1：任务τi的可调度性对其他优先级的任务顺序不敏感。

条件2：如果交换τk与τi之间的优先级使得τk的优先级提高，交换前后τk的可调度性不变。

算法1为本文改进的OPA调度算法，该算法从优先级最低的线程开始迭代地为所有线程分配优先级，其中τdecom为操作系统中待分配优先级的线程集。第k次迭代中，τdecom分为两个不相交的子集：A(k)与R(k)，其中：

1)A(k)表示第k步之前已分配优先级的线程子集；

2)R(k)表示剩余线程的子集。

理论1的可调度性判定是OPA兼容的，说明该判定满足线程级可调度性的条件1与条件2，因此算法1的优先级分配过程正确，证明方法如下：

理论2理论1的可调度性判定兼容算法1。

证明根据本文的可调度性判定证明线程级调度算法满足条件1与条件2：

(1) 满足条件1证明：式(10)的左式计算了每个任务对线程θk,q干扰的上界，任务的干扰上界计算为优先级高于θk,q的其他线程工作负载之和。而该计算过程不依赖相应的优先级顺序。因此，满足条件1。

(2) 满足条件2证明：交换θk,q与θi,p优先级，θk,q的优先级提高。因为θk,q的优先级提高，所以hp(θk,q)交换后变得更小。因此，式(8)、式(9)的Wi(Dk,q)与Wk(Dk,q)交换之后变得更小，满足条件2。

算法1线程级OPA调度算法

输入：τdecom

输出：调度状态

1:k←0,A(1)←∅,R(1)←τdecom

2:DO{

3:k←k+1

4:IF(thread_level_sch(A(k),R(k))==FAILURE);

5:returnFALSE;

//不可调度

6: }WHILE(R(k)!=NULL)

7:returnTRUE;

//可调度

算法2thread_level_sch函数

输入：A(k),R(k)

输出：分配结果

1:FOREACHthreadθp,q∈R(k) {

2:IF(θp,q可调度，根据理论1，R(k)中其他线程的优先级均高于k)THEN{

3: 为θp,q分配优先级k；

4:R(k+1)←R(k){θp,q}；

5:A(k+1)←A(k){θp,q}；

6:returnSUCCESS；

7: }

8: }

9:returnFAILURE；

4 动态截止期的线程级调度算法

4.1 算法设计

上文考虑了线程静态偏移与截止期的情况，本算法的决策目标为各线程的偏移、截止期与优先级三个目标，所以根据理论1的可调度性分析，并行任务系统是可调度的。本文动态截止期的线程级优先级分配策略的主要思想为：首先通过算法1分配优先级，如果算法1分配失败，则调节一些线程的偏移与截止期，使得调节后某个线程可成功地分配优先级，如果找到该调节方法，则继续使用算法1分配优先级；否则，认为调度失败，如算法3所示。算法3中输入为操作系统中待分配优先级的线程集，输出为调度的状态。

将线程结束时间与截止期之间的最小距离定义为线程θk,q的富余时间，表示为Sk,q。根据理论1的可调度性判定，Sk,q可近似为:

(11)

线程间赠予富余时间的目标是为受赠线程分配一个优先级，使得受赠线程变为可调度，然而由此可能对其他可调度的线程产生边际效应。考虑该问题，本文设计了以下三个子问题解决策略：

(1) 受赠线程的决策策略：应当保证已分配优先级线程具有足够的富余时间，所以决策策略为最小化总赠予时间的量。据此将所需赠予时间最少的线程作为受赠线程，时期变为可调度状态，见算法4的第3行。

(2) 赠予线程的决策策略：确定受赠线程后，建立一个赠予线程候选集合(算法4第4行)，属同一个任务的候选线程已经分配了优先级，应当能够赠予富余时间，且不影响所有线程的可调度性。为了避免破坏已分配优先级线程的可调度状态，本文选择候选集合中归一化富余时间量最大的线程作为赠予线程(算法4第6行)。

(3) 赠予时间量的分配：

引理3如果线程θk,q的截止期Dk,q减小，则对θk,q最坏情况的干扰随之单调减小。

证明式(8)、式(9)中，分别计算了τi与τk的最大执行量。式(7)中给定t，Wi,p(Di,p,t)与Wk,q(Dk,q,t)随Dk,q下降而单调下降。式(8)中，因为需要调节Δi(x,y)使得Wi(Dk,q)最大化，所以Wk(Dk,q)不会随Dk,q下降而提高，因此，可看出Wi(Dk,q)与Wk(Dk,q)随Dk,q下降呈单调下降。由此证明引理3。

引理3说明如果赠予线程减小其截止期(将富余时间赠予受赠线程)，赠予线程可能获得其他的富余时间。因此，每个赠予步骤中将赠予时间设置较小，从而增加找到其他富余时间的概率(算法第7行)，赠予完成后，每个赠予线程保持更新其富余时间量，以期找到其他的富余时间(算法11行)。

算法3动态截止期的线程级调度算法

输入：τdecom

输出：调度状态

1:k←0,A(1)←∅,R(1)←τdecom

2:DO{

3:IF(thread_level_sch(A(k),R(k))==FAILURE) {

4:IF(deadline_change(A(k),R(k))==FAILURE) {

5:returnFALSE;

6: }

7: }WHILE(R(k)!=NULL);

8:returnTRUE

算法4deadline_change函数

输入：A(k),R(k)

//A(k)已调度的任务集，R(k)尚未调度的任务集

输出：分配结果

1:F←R(k);

2:DO{

5: 保存τs中所有线程的当前偏移与截止期；

10:returnSUCCESS;

12: }

13: 保存τs中所有线程的偏移与截止期；

14: }WHILE(F!=NULL)

15:returnFAILURE

4.2 计算复杂度分析

5 仿真实验与结果分析

5.1 仿真环境

为了简化表达，定义以下术语：Ci表示τi(∑qCi,q)内所有线程最差情况的运行时间总和，Usys表示系统利用率，Li是τi最坏情况的执行时间，LUsys定义为任务τi∈τ中最大的Li/Di值。

采用文献[18]的方法生成DAG任务，对于任务τi，其参数如下设置：节点数量ni均匀选择于区间[1,Nmax]内，其中Nmax为单个任务的线程数量上限。每对节点之间边随机地生成，概率为p。根据Ci,p值所属的三个范围[1,5]、(6,10]、(11,40]，分别为任务τi与每个线程分配一个类型(轻型、中等、重型)，同时确定Ti(=Di)参数，因此Ci/Ti值分别在[0.1, 0.3]，(0.3, 0.6]或(0.6, 1.0]随机地选择。

为了全面地测试本算法对并行DAG任务的性能，共设计了三种测试统计量：(1) 系统利用率;(2) 并行度;(3) 节点总数量。第一组实验评估了系统对Usys的调度性能变化情况，结果如图3所示。第二组实验评估了算法对不同任务内并行度的调度性能变化情况，结果如图4所示。第三组实验评估了算法对τ中节点总数量的调度性能变化情况，结果如图5、图6所示。将本文算法与基本OPA算法[12]、B_task_EDF[19]以及C_task_EDF[20]三种算法进行横向比较，评估本算法的性能。

图3 不同Usys的调度性能变化情况

图4 不同任务内并行度的调度性能变化情况

图5 对τ中节点总数量的调度性能变化情况

图6 本调度算法的计算时间与任务内节点总数量的关系

5.1.1 第一组实验的任务集生成方法

步骤1：随机地将任务逐个加入任务集中；

将U*从1增加至8，步长设为0.4，因此实验的任务集数量为18 000。

5.1.2 第二组实验的任务集生成方法

设置m=8、Nmax=10、p为变量因子，生成1 000个任务集，步骤如下：

步骤1：使用上述参数生成m个任务的任务集；

步骤2：如果任务集的Usys大于m，则忽略该任务集并返回步骤1；

步骤3：采用此时的任务集进行实验，然后向该任务集添加一个任务，并返回步骤2直至生成1 000个任务集。

对于节点间的边，如果p=0，则没有边(不存在父线程)，此时任务内的并行度为最大；如果p=1，每个节点均与其他节点连接，说明一个任务内同时仅一个线程运行；随着p值增加，每个DAG任务τi内边的数量增加，由此导致关键的执行路径Li变长，然后LUsys增加。

为了针对不同的任务内并行度进行仿真，在10个不同的p值下，进行仿真实验，p值从0.1增加至1，步长为0.1，共有10 000个仿真。

5.1.3 第三组实验的任务集生成方法

第三组实验采用第一组实验的参数设置，将任务逐个加入任务集直至τ中节点数量达到给定的节点总数量，任务的节点数量范围为[1，给定的总节点数量-τ中节点数量]。将节点总数量从10增加至100，p=0.5，U*=m/2。每个数据点包含1 000个仿真，共有10 000个仿真。

5.2 实验结果与分析

从图3中可看出，U*从1到5.8，本算法的检测率远超过其他三个算法。将本算法与OPA基本算法相比，可看出本文细粒度的调度算法(线程为调度单位)明显提高了调度算法的性能，同时本算法优于两个EDF的增强算法，可看出本算法中采用线程级调度、动态线程截止期等设计具有显著的效果。

图4所示为检测率与p值的关系，p值增加引起每个DAG任务的边数量增加，从而使得节点间依赖的关系度升高。从图中可看出，线程级优先级分配算法在p值较小时具有较好的性能，而当p值为1时，本算法与基本OPA算法、C_task_EDF性能接近，此时一个DAG任务中所有节点均被连接，任务均为单线程任务。B_task_EDF的检测率随着p值的增加而降低，主要原因是该方法的调度性判定LUsys是否小于阈值m/(2m-1),随着p值的增加，LUsys值升高，导致可调度性下降。

为了测试本算法对不同数量线程的性能，将线程数量设为因变量，统计系统检测率的变化情况。图5中可看出，节点数量较多时，本算法优于其他三个算法。节点数量越多，本算法调节线程截止期的机会越多，因此可调度性越高。

图6是本算法计算时间与任务内节点数量的关系，可看出节点数量越高，算法的计算时间越高。虽然对于100个线程的任务，本算法的计算时间约为2.2 s，但是本算法将实时系统的检测率提高到约60%。

6 结 语

现有实时系统调度算法将任务作为调度单位，严重限制了多线程任务的调度性能，并且已有的算法大多对一些经典的调度算法进行可调度性分析，以期通过优化可调度性判定条件提高算法的可调度性。然而受限于原调度算法的性能限制，通过收紧可调度性判定条件所获得的性能提升往往较为有限。本文提出了一种细粒度的线程级多处理器实时调度算法，并给出了详细的可调度性分析，仿真实验结果表明，本算法对于多线程任务的实时系统具有较好的性能，对高线程数量的任务具有明显地优势。