面向物联网终端的任务相关性调度策略

向 敏，戴柯宇，周 恩，刘 榆，雷儒杰

重庆邮电大学 工业物联网与网络化控制教育部重点实验室，重庆 400065

1 引言

物联网作为新一代信息技术，可以广泛地应用于各个领域[1-3]。在物联网终端应用领域广，场景多，主要进行的工作大多利用RFID、信号采集、传感器等技术获取各类数据，然后通过通信技术与云端相连，根据具体的应用需求进行数据汇报或根据云端指令做出相应控制动作[4-5]。因此，物联网终端软件中的许多任务之间都存在一定的相关性，如果任务所依赖的前驱任务没有被执行，那么调度该任务会产生额外的等待开销甚至死锁，这将对系统整体实时性和稳定性产生极大影响[6]。如何动态地安排这些具有相关性的任务，使CPU 能够根据相关性进行任务调度，对系统实时性和稳定性具有重要意义。

对于考虑任务相关性的任务调度，目前已经有一些研究成果。Geng提出了一种结合任务之间相关性和依赖性的调度方案，以相关约束和依赖约束为条件设计了禁忌搜索扩展算法来缩短任务完成时间[7]。Wu 等人提出一种在多媒体云计算平台中的数据动态调度方法，利用动态任务之间存在的数据依赖性确定优先级来提高调度性能[8]。Boyer等人提出应用在分布式系统中任务调度算法，该调度利用随机排序技术搜索最佳时间表用以估计迁移任务执行时间，同时考虑了任务间的相关性进行平衡负载的任务迁移，减小了时间估计中的不确定性[9]。Zotkiewicz等人提出一种在数据中心使用的调度方法，利用任务间相互依赖性动态调度工作流，达成了降低服务器能耗的目的[10]。李文君等人提出一种考虑数据关联性的调度算法，在可重构系统中协调内部通信数量，减少了CPU 和FPGA 之间的通信开销[11]。

Wang 等人提出了一种数据依赖性驱动的调度方案，通过尽可能将具有相关性的任务数据放在同个计算节点来解决在大数据处理过程中产生过多数据迁移的问题[12]。丁男等人提出了一种多核系统中基于数据依赖性的调度算法，文中主要思路是将所有计算型任务通过评价函数量化它们相关性的大小，然后通过将相关性强的任务分配到同一个核内，避免了过多核间通信造成的时间开销，达到降低任务调度长度，提高实时性的目的[13]。这两篇文献的主要成果是根据任务的相关性，在空间上进行处理，将相关性强的任务放在同个计算区域，减少任务处理过程中不同计算区域间的可能产生的通信开销，但并没有在同个节点中利用相关性从时间上进行任务执行顺序的处理。黄姝娟等人针对有相关关系的周期任务提出了基于ST（Simple-Tree）的调度模型和可延迟时间越短越优先调度方法，提高了核利用率[14]，但缺少对具有相关性的非周期任务的处理。

为此，提出面向物联网终端软件的任务调度策略，将具有相关性的任务划分到一个作业轮询组，以优先级因子矩阵作为调度凭据，通过优先级因子增量矩阵来动态修改各任务优先级，通过对作业轮询组的调用完成需求功能，从时间上对任务执行顺序进行安排，减少了任务集执行时间和调度失败次数。对于非周期任务采用组成临时作业轮询组的优化处理方案，降低了实时性敏感非周期任务的响应时间。

2 基于任务相关性的任务模型

2.1 任务模型

为了对具有相关系的任务进行有效管理，终端软件部分将逻辑相关的任务组成一个相对独立的“作业轮询组”，整个软件实体由若干个作业轮询组构成。同时为了能够更加直观地表现任务相关性，利用有向无环图（DAG图）对任务间的相关性进行描述。相关的具体定义描述如下。

定义1（任务相关性描述图）使用DAG图来描述任务相关性，一个任务相关性描述图D={V,U}，其中V表示节点集合{S,a1,a2,a3,a4,…,F} 。为了便于在图中对任务流进行更清晰的展示，引入逻辑节点S、F，这两个节点不代表实体任务，仅表示逻辑上任务流的开始与结束。其中节点S表示逻辑开始，节点F逻辑结束。其他每个节点{a1,a2,a3,a4,…} 均表示一个实体任务。U⊂V×V表示有向边集合，每条有向边上的数字表示发出这条边的节点的任务时限，两个任务之间存在有向边表示这两个任务存在相关关系，且发出有向边的任务为有向边指向任务的前驱任务，后续任务只有在其前驱任务全部完成后才可执行。一个示例系统的任务相关性描述图如图1所示。

图1 样例系统任务相关性描述图

如图1中有向边(a1,a2)表示任务a1是任务a2的前驱任务，任务a2是任务a1的后续任务，且a1的任务时限为t1。仅与S、F节点相连的节点任务为孤立任务，例如图1中的任务a9和a10，孤立任务与其他任务之间无相关关系。

定义2（作业轮询组）通过任务相关性描述图，终端软件部分组成n个作业轮询组，每个作业轮询组包含最多m个任务，将逻辑相关的任务放入一个组里，形成一条相对独立的任务流。系统通过对作业轮询组的调度来完成既定功能。作业轮询组中的任务位置被排定后便不会更改，为了方便描述，文中用Vn,m来表示第n个作业轮询组的第m个任务，其中，n=1,2,…，m=1,2,…。

2.2 作业轮询组任务划分

在进行任务调度之前，首先需要将具有相关性的任务预先划分到同一个作业轮询组中。在进行任务划分的时候，如果区分颗粒太粗会造成过多任务被放入同一个作业轮询组，使得该机制作用降低；如果区分颗粒太细则会产生过多的作业轮询组消耗更多的内存空间。因此任务分组结果尤为重要。在此，提出作业轮询组中任务划分机制，为作业轮询组安排合适的成员任务，以降低调度失败任务切换次数。

在进行任务分组之前，首先需要根据输入任务相关性描述图确定最大作业轮询组n和组内最大任务容量m的值。输入任务相关性描述图D，输入任务数量Ntask，则n和m确定的步骤如下：

（1）从任务相关性描述图D中找到从S节点到F节点拥有最多任务节点数的路径Dmax，如果有多条最长路径则选取其中节点度数最少的路径。m的值为找到的第一个Dmax中包含任务节点数。

（2）从图D中删除Dmax所包含节点及边，然后按照步骤（1）的规则继续寻找拥有最多任务节点的路径Dmax，重复本步骤直到Dmax中只包含孤立任务。此时n的值为找到路径Dmax的数量。

（3）考虑到孤立任务数量不定，还需要判断n×m与Ntask的大小关系，根据式（1）确定n的值：

式（1）中，ceil(x)表示取不小于x的最小整数，如ceil( 3.1)=ceil( 3.9)=4。

通过上述步骤完成n、m值的确定工作，之后开始将任务相关性描述图中的任务按相关关系，划分到作业轮询组中。对于任意待分配任务Ve，描述该任务与任意作业轮询组Gx的相关性强度的任务划分函数如式（2）所示：

其中，R(Ve,Gx)代表任务Ve与作业轮询组Gx的相关性强度；tj表示作业轮询组Gx中第j个任务的任务时限，表示作业轮询组Gx中第j个任务与待分配任务Ve是否存在相关关系，如果是该值为1，否则为0。式（2）表示，对于待分配任务Ve，与作业轮询组的相关性强度取决这个作业轮询组中与Ve存在相关性的任务个数和它们的任务时限。作业轮询中存在越多与Ve具有相关性的任务，这些任务的时限越小，则Ve与这个作业轮询的相关性越强。

在进行任务划分的过程中，作业轮询组分配状态与已被分配任务数量的关系如表1所示。

表1 作业轮询组分配状态

对于还未分配到作业轮询组的任务，首先利用式（2）求得该任务与每个作业轮询组的相关性强度值，将该任务分配到相关性强度值最大的作业轮询组内。如果有任务根据式（2）输出的相关性强度全为0，则需要查询所有作业轮询组的分配状态，并按照以下步骤完成该任务的划分：

（1）当还存在作业轮询组的分配状态为未分配时，将待分配任务划分到这个未分配任务的作业轮询组中。

（2）当所有作业轮询组的分配状态都为分配中或分配满时，相关性强度全为0说明待分配任务与其他任务均没有相关关系，属于孤立任务，则将该任务随机分配至还未满的作业轮询组中。

以图1所示任务相关性描述图为例，演示任务划分过程。图1 中任务节点数最多的路径有两条，分别是(a1,a2,a3,a4)和(a1,a5,a6,a7)，选择其中度数更小的路径(a1,a2,a3,a4)=Dmax，如图2（a）中虚线所示，求得组内最大任务容量m=4。然后从图1中删除(a1,a2,a3,a4)，余下的图如图2（b）所示，从中找到任务节点数最多路径(a5,a6,a7)=Dmax。接着从图2（b）中删除(a5,a6,a7)，余下的图如图2（c）所示，由于其中仅包含孤立任务，结束寻找Dmax的步骤，此时n=2 。由于输入任务数量Ntask=10，根据式（1）可知，当n×m=8

图2 任务划分示意图

结合式（2），计算任务与各作业轮询组的相关性强度，并根据计算结果进行作业轮询组任务划分，其统计结果如表2所示。

表2 任务划分结果

2.3 作业轮询组优先级管理

作业轮询组以优先级机制进行调度，系统通过对作业轮询组的调度来进行功能表达。在作业轮询组内，同样也以优先级为依据对组内任务进行调度，为描述方便，以父优先级因子表示作业轮询组的优先级因子，子优先级因子表示组内任务的优先级因子。在作业轮询组中的任务被划分完毕后，包含最多m个任务的第x个作业轮询组的父优先级因子ςx表示为：

其中，αx,j的取值为0或1，表示第x个作业轮询组中的第j个位置是否已经被分配实体任务，如果该位置有实体任务则αx,j为1，否则为0；tx,j表示任务Vx,j的任务时限；wx,j表示任务Vx,j的等待时间，wx,j的初始值为1，如果任务处于就绪状态而没有被调度则等待时间会一直累加，直到任务被调度后恢复为初始值1。

3 基于任务相关性的调度策略

3.1 基于任务相关性的动态调度算法

利用上文提出的任务划分机制将作业轮询组成员安排完毕后，提出基于任务相关性的任务调度算法，算法的整体描述如下：通过任务时限确定父优先级因子和子优先级因子，依次选取当前父优先级因子最大的就绪作业轮询组进行执行。每个作业轮询组在执行完毕之后将失效，当前作业周期将不会再被调度，直到所有作业轮询组都执行完毕，新周期开始时会将所有作业轮询组状态设置为就绪。在一个作业轮询组被执行时，组内以任务为最小调度单位，总是执行当前优先级最高的就绪任务。每个任务执行完毕触发一次调度计算，此时会根据任务就绪表生成一个优先级因子增量矩阵，通过增量矩阵动态改变父优先级因子和子优先级因子来达到使具有相关性任务快速完成的目的。

系统的优先级因子矩阵Φ是调度的唯一依据。通过式（4）可以发现，系统运行过程中父优先级因子和子优先级因子都是依赖于任务时限和任务等待时间。为了在运行过程中根据任务相关性动态改变优先级，系统在每一个任务执行完毕后输出一个相关性增量矩阵ΔΦ，利用ΔΦ叠加到任务优先级因子矩阵Φ上的方式进行优先级修改。ΔΦ的产生步骤如下：

（1）对于系统中任意任务Vp,q可以根据任务相关性描述图生成对应的相关性信息矩阵Ep,q，βi,j为Ep,q矩阵中第i行第j列的元素，βi,j数值与对应任务的相关性关系如表3所示。

表3 相关性信息矩阵数值含义

根据矩阵Ep,q在对应任务位置处的数值可确定两个任务之间的相关关系。矩阵Ep,q和任务相关性描述图一一对应。以图1中的任务V1,1为例，该任务的相关性信息阵为：

矩阵E1,1说明了任务V1,2、V2,1和V3,1都与V1,1具有相关性，且V1,2、V2,1与V3,1是V1,1的后续任务。

在得到任务Vp,q的相关性信息矩阵后，可以计算该任务的增量因子。

由式（5）可知，任务的增量因子由该任务的后续任务的优先级因子和增量因子两部分组成，如果任务处于一条相关任务流中，在进行任务的增量因子计算时，会将其后续任务的优先级因子叠加到该任务上，保证了前驱任务会获得更高的优先级；如果该任务为孤立任务或该任务没有后续任务，则求解的增量因子为0，不会改变优先级因子矩阵Φ中的数值。因为任务的增量因子与该任务的后续任务的增量因子有关，所以计算增量因子是一个从任务流末端向前递归的过程。

（2）根据任务相关性描述图，求得各任务节点距离任务完成节点F所需要经过的最大节点数ε。例如将图1中的任务分组并按ε大小排序后的任务相关性描述图如图3所示。

图3 按ε 大小排序后的任务相关性描述图

完成ε值的确定工作后，按ε从小到大的顺序，利用式（5）递归求解各任务的增量因子。例如，对于图3所示系统，首先求解ε=0 的任务V1,4、V2,3、V3,1、V3,2的增量因子，然后求解ε=1 的任务V1,3、V2,2、V2,4的增量因子，再求解ε=2 的任务V1,2、V2,1的增量因子，最后求解ε=3 的任务V1,1的增量因子。

求得各任务的增量因子后，将每个任务的增量因子按任务位置排列为矩阵形式就得到了系统优先级因子增量矩阵。

在任务的调度过程中，每次触发任务切换时会从任务流末端开始计算就绪表中所有任务的增量因子进而形成优先级因子增量矩阵，然后将增量矩阵与优先级因子矩阵进行叠加，从而改变系统中各任务的优先级，让前驱任务被优先调度，以保证后续任务的实时性，使一条任务流能更加高效地执行。增量矩阵ΔΦ的作用过程如图4所示。

3.2 具有相关性的非周期任务优化处理

图4 增量矩阵作用流程图

在物联网终端中各项任务按周期性可分为周期任务和非周期任务[15]。周期任务在系统启动之后会按照规定的周期周而复始地运行下去，如环境数据周期采集、定时上传监控数据等[16]。非周期任务则是不能提前预计到达时间的任务，这类任务对实时性的要求一般都更高，在任务到达时需要快速响应，否则可能造成难以预料的后果[17]。当非周期任务具有任务相关性时，影响其响应时间的不但与它达到的时刻有关，还与该非周期任务所依赖的前驱任务执行情况相关。针对非周期任务提出优化处理方案步骤如下：

（1）对于任意非周期任务Vp,q，根据其相关性矩阵信息Ep,q确定该任务的相关性。

（2）如果Ep,q=0，说明Vp,q是孤立任务，则以上文所述算法进行调度。否则找到Vp,q的前驱任务集是任务相关性描述图中所有可以通过有向边到达Vp,q的任务节点集合，如图1中的任务a7的前驱任务集然后将Vp,q与一起组成一个临时作业轮询组。

（3）系统中断正在执行的任务，对临时作业轮询组进行执行，执行完毕后临时作业轮询组解散，系统从被中断处继续执行。

某系统已经完成任务划分工作，它的任务相关性如图5 所示，其中V1,3为非周期任务。以该系统为例，对非周期任务优化处理方案进行描述。

图5 示例系统任务相关性描述图

如图5所示，当具有相关性的非周期任务V1,3达到后，先计算增量矩阵用以更新优先级因子矩阵Φ，然后找到V1,3的前驱任务集{V1,1,V1,2,V2,1,V2,2,V2,3}，然后将前驱任务集与非周期任务V1,3一起建立一个临时作业轮询组。这个临时作业轮询组会中断当前任务，获得CPU使用权，在临时作业轮询组执行完毕之后再接着执行刚才被中断的任务，与此同时，将V1*,3中所有任务状态都置为失效。非周期任务处理过程如图6所示。

图6 非周期任务处理示意图

特别地，如果当前因有多个非周期任务到达而产生多个临时作业轮询组，则利用式（4）来计算各个临时作业轮询组的优先级因子，判断它们的执行顺序，然后再以本节所述流程进行执行和返回。

3.3 算法复杂度分析

在本节中将对前文提出的调度算法进行复杂度分析。算法的伪代码如下：

输入：任务相关性描述图D

输出：当前需要调度的任务号

1.BEGIN：

2.Ini（tV，D）；//根据相关性描述图进行任务划分

3.WHILE（1）

4.IF（AperiodicTask）//判断非周期任务是否到达

5.BuildTemGroup（）；//建立临时作业轮询组

6.RETURN TemGroupTaskNum；//返回调度的任务号

7.END IF

8.IF（TASKEND）//判断当前任务执行是否完毕

9.UpdatePrio（r）；//任务执行完毕后更新增量矩阵

10.IF（GroupEnd）//判断当前组是否完毕

11.IF（AllGroupEnd）//判断一个轮询周期是否完毕

12.FindGroupTask（）；//查找优先级最高的作业轮询组和任务

13.RETURN TaskNum；

14.END IF

15.ELSE//当前组未执行完毕

16.FindTask（）；//查找当前组剩余优先级最高的任务

17.RETURN TaskNum；

18.END IF

19.ELSE//当前任务还未执行完毕

20.RETURN TaskNum；//直接返回当前任务

21.END IF

22.END WHILE

从伪代码中易知：第2行任务划分过程的时间复杂度为O(n×m)，由于任务划分仅发生于系统初始化过程中，产生的时间影响可忽略；第9 行更新增量矩阵的时间复杂度为O(n×m)；第12 行查找优先级最高的作业轮询组和任务的时间复杂度是O(n×m)；第16 行查找组内优先级最高的任务的时间复杂度是O(m)。综合以上各部分复杂度，算法的总体时间复杂度为O(2 ×(n×m)+m)。

4 仿真验证

本章中，通过仿真实验来对本文所调度策略的有效性进行评估。为了体现一般性，实验中使用的任务实例为实际应用中的数据采集终端，运行环境为32 位处理器，72 MHz 主频。主要对比对象为典型动态调度最早时限优先调度（EDF）和应用在uCOS-Ⅲ、Linux2.6 中的时间片轮转（RR）[18]。具体评价指标为任务集执行时间、任务调度失败次数、非周期任务平均响应时间。

对任务集执行时间的评估方法为，将一个数据采集终端软件任务进行任务划分，然后执行5 000个周期，对比具有相关性任务数量不同的情况下任务集执行时间；对任务调度失败次数的评估方法为，将任务集中具有相关性任务数量进行固定，对比执行任务数量不同的情况下调度失败的次数。使用到的预配置任务集属性如表4所示。

表4 预配置任务集属性表

任务集执行时间仿真结果如图7 所示，其中横坐标表示任务相关性描述图中与S、F节点无关的有向边U数量的多少，该参数体现了系统中任务相关性的强弱。

图7 任务集执行时间

由图7 可以看出在任务图中有向边数量为0，即所有任务均为孤立任务时，EDF 调度和RR 调度均会优于本文所提策略。在本文所提策略中，任务间不存在相关性时，增量矩阵为0 矩阵，在调度阶段仍然会花费时间去搜寻查找就绪任务的关联关系，这会产生一定的时间浪费。而随着任务图中有向边数量的增加，任务相关性逐渐加强，EDF 调度和RR 调度执行作业集的时间会逐渐增多，而本文所提策略的执行时间几乎不变，在任务图有向边数量超过3时，本文所提策略已经优于EDF调度和RR调度。

任务调度失败次数仿真结果如图8 所示。横坐标为任务完成数量，为了保证仿真结果的有效性，在本次仿真中所使用任务集的任务图有向边数量被固定为7。纵坐标为任务进行过程中调度失败的次数，为因前驱任务尚未执行就对后继任务进行调度引发调度失败的次数，该指标显示了调度在具有相关性的任务环境下的可靠性。

图8 任务调度失败次数

由图8可以看出，在任务完成数量为1 000时，本文提出策略调度失败次数少于EDF和RR调度，同时随着任务完成数量的增加，本文所提策略的优势更加明显。这是因为本文所提策略在任务划分阶段就根据相关性对任务进行了处理，尽可能地保证了任务的后继任务在其前驱任务全部完成之后才执行，有效地减少了任务调度失败次数。而EDF仅以任务时限为调度依据，可能出现时限更短的后继任务比时限稍长的前驱任务更优先调度而引起调度失败。由于RR调度在每个时间片都可能引发调度，所以调度失败的次数会更多。

对于非周期任务响应时间的仿真方案为，分别将表4中不同的任务设置为非周期任务，在任务集执行过程中对比不同调度下非周期任务的响应时间。为了保证随机性，对于非周期任务，它们的到达时间将会在[100，1 000]之间随机产生。三种调度非周期任务平均响应时间如图9所示。

图9 非周期任务平均响应时间

由图9 可以看出，相较于其他两种调度，本文所提出的调度策略能够更及时地响应非周期任务，且随着该非周期任务所需前驱任务的数量增加，本文所提策略优势更加明显。这是因为经过任务相关性处理，本文所提策略在非周期任务处于就绪表中的时候就提前将所需前驱任务优先级提高，同时列为单独的一个作业轮询组。这样在非周期任务的前驱任务数量增加时，对响应时间的影响仅为增加前驱任务的执行时间。而对于其他两种调度，根据执行时间或到达时间对非周期任务进行调度需要耗费一定时间，同时在前驱任务数量增加后，调度其所有前驱任务以确保非周期任务顺利执行将会耗费更多的调度次数。

5 结束语

针对物联网终端的应用场景多样，任务之间存在相关性的情况，本文提出了一种基于任务相关性的调度策略。该策略在初始化过程中就对任务进行划分，将相关性强的任务划分为一个作业轮询组。针对周期任务，通过增量矩阵动态改变任务优先级，让任务总是能在其前驱任务完成之后再被调度，避免调度失败产生额外的运行周期；针对时间敏感的非周期任务，通过建立临时作业轮询组，缩短其响应时间，提高系统实时性。该策略根据相关性动态地配置任务优先级，能够在物联网终端特别是应用场景复杂多变的可重构终端应用中发挥作用。