基于级联调度的相关性任务集共享资源冲突消解算法

沈阳

（广州工程技术职业学院 信息工程学院，广东 广州 510075）

0 引 言

分布式多处理器系统的处理器之间的结构可以是多种的，如SMP、NoC-MP、Mesh-MP。不同的来源导致它们之间的关系不同，如共享主存与总线的结构、基于片上网络交换的结构。另外，一个或多个相关性任务集执行过程中，某些子任务之间不存在直接相关性，它们可以被分配在不同的处理器上并发执行。它们可能会在某个时间段产生对存储器、网络及外设之类的共享资源的共用、竞争和协同，从而在这些任务间产生间接相关性。

文献[2]面向时间约束网络STN，提出的基于度的自动冲突消解方法，任务在执行过程中若无法在执行时间窗口执行，则动态找出冲突源及其数量，并由系统及时调整约束以达到消解潜在的资源冲突。文献[3，4]使用Petri网模型提出基于优先级的资源冲突检测和消解算法。文献[5]从资源总量角度，整体对任务的需求进行规划，在任务优先级约束条件下对资源进行匹配，从而提高资源共享和使用效率，降低资源的冲突。李津等人在移动边缘计算网络中任务调度与资源配置方面展开的研究，将边缘计算卸载的时延，通过排队论的方式进行建模，求解该模型需要进行混合整数非线性规划。通过拆分子问题分别求解的方式，提出了联合资源分配和任务调度算法。

文献[7]对相关性任务之间的竞争问题展开研究，评估了在不同控制要求下的一致性问题。文献[8]从概念层面分析了冲突产生的原因，并对资源组织和资源利用进行了规范化描述。在此基础上，提出了时间、资源和任务约束下的任务分解、调度和冲突解决模型。文献[9，10]提出两阶段优化算法，第1阶段是项目时序约束优化阶段，采用蚁群算法（ACO）进行任务列表的优化求解，通过对信息素增量规则的改进、串联进度生成机制（SSGS）及资源冲突消解策略的使用，使蚁群算法的求解效率和质量得以提高；第2阶段是资源约束优化阶段，以第1阶段求得的优化任务列表为输入，逐项对人力资源约束进行核查与调整，最终生成项目调度的优化方案。文献[11]采用了多个调度代理通过共享的集群资源使用状态信息并发地进行调度决策工作，然后通过冲突检测算法解决这些并发生成的调度决策之间冲突问题。

上述文献研究从各个角度对共享资源冲突消解展开研究，但没有深入考虑并发任务对多种共享资源的使用情况，以及由时间特性而导致的资源冲突问题，这里的共享资源指在某一时刻只能被一个任务所占用，具有排他性。由于子任务的并发性，在某一时刻可能会出现多个子任务竞争某类共享资源的情况，当子任务对该类共享资源的需求总量超出该资源的总量时就会引发冲突甚至死锁。为此需要提前检查调度方案中可能出现的资源冲突状况，并通过调整相关任务的时间关系，从而实现资源冲突的消解，使并发任务可以顺利且尽快执行完成。

1 相关计算模型的定义

设在某段时刻[t-,t+]存在并发任务序列：T={t |=1,2,…,，系统中的共享资源集用R={R|=1,2,…,表示，其中R表示一种共享资源类型，共享资源R的资源总数记为||。用 表示任务t所需资源R的数量，任务t在其整个执行时间x内对资源R的占用量记为j，即 ，整体表示为t(x)|R(j),…,R（k)，例如(40)|(20),(10)表示任务的执行时间为40，该任务在执行时对资源的占用量为20，对资源的占用量为10。

图1给出一个具有共享资源竞争关系的相关性任务集示例图，其中直接相关性指任务间具有紧前约束关系，在图中用实线箭头表示，间接相关性指任务间存在资源竞争关系，在图中用虚线和双虚线表示。表1是该相关性任务集中各任务的执行时间和所需共享资源类型及数量。

图1 具有共享资源竞争关系的相关性任务集示例图

表1 任务执行时间和所需资源情况

假设系统中存在的资源数量为：||=40，||=20，||=20。由表1中执行时间以及共享资源使用状况可知，任务、和对资源的使用上存在冲突，任务、和对和资源的使用上存在冲突。那么{,,}和{,,}这两个任务集合内部存在间接相关性，这两个间接相关性表示为：TR={,,}和TR={,,}。为表示任务间的直接相关性和间接相关性，本文引入2种连接边，即FS和SS，FS表示“完成－开始”的关系，即原有的直接依赖关系（一般来说FS= =0）；SS表示“开始－开始”的关系，是资源冲突引起并发任务间的滞后关系。例如SS=10表示并发任务和存在资源冲突，使开始执行后10个单位时间才能执行。

相关性任务集中由关键任务组成的最长路径为关键路径。而本文的相关性任务集中存在两种关键任务形式：（1）直接前驱任务约束条件下，自由时差为0的后继任务，若任务自由时差不为0，则该任务不是关键任务。（2）共享资源约束条件下，资源自由时差为0的任务，资源自由时差（Resource Free Float, RFF）是指任意任务t在使用某种共享资源时，由于其他任务也在等待该资源，因为任务t没有弹性使用该资源的自由时间，例如RFF=0，则说明任务t是资源约束下的关键任务，若RFF=10说明任务t可以延迟10个时间单位执行，即任务t不是关键任务。

2 资源冲突消解算法

本文的资源冲突消解算法MRMTCD（Multi-resource multi-task conflict digestionalgorithm, MRMTCD）首先按相应规则（2.1节）确定并发任务优先级和共享资源优先级，并给出单资源冲突消解算法（2.2节），然后在单资源冲突消解算法的基础上，通过级联调度的方式实现多资源多任务冲突消解算法（2.3节），最终实现整个相关性任务集的资源冲突消解过程。

2.1 优先级获取原则

2.1.1 任务优先级

本文资源冲突消解算法中任务选择顺序取决于任务优先级的高低。若产生资源冲突的并发任务中存在关键任务，则关键任务优先进行资源分配。若并发任务中存在多个关键任务或全部为非关键任务，采用先来先服务原则，先处理关键任务的资源请求，再处理非关键任务的资源请求。若两个任务的最早开始时间相同，则按最小自由时差优先的原则确定调度顺序。

2.1.2 资源优先级

如果出现同一任务请求多种资源或者多个并发任务竞争多种资源的情况，就必须考虑这些资源的优先级问题，由于不同类型的资源（如通信线路、访存等）很难用同一种单位的数据直接量化，因此本文采用计算资源的负载率来表示资源的优先级，资源负载率是指在同一时间段存在多种资源冲突时，各资源的最大使用率，是在这个时间段中该资源最大使用量与资源容量之比。

例如共享资源R的负载率的计算为：首先在找出TR并发任务集中的最早开始时间（如式（1））和最晚结束时间（如式（2）），然后找出该时间段中R的最大占用量maxR（如式（3）（4）），最后用maxR与|R|之比求出R的负载率maxRLoadR（如式（5））。

2.2 单资源冲突消解算法

单资源冲突消解算法按任务优先级依次进行任务和共享资源的分配，用当前任务所需资源量与剩余资源量进行比较，如果剩余资源量满足该任务的资源需求，则进行资源分配，该任务没有SS紧前约束，不受资源约束限制，如果剩余资源量不能满足该任务的资源需求，则该任务的执行开始时间逐步后移，直到某一时刻该资源的剩余资源量满足该任务的资源需求。

下面给出单资源冲突消解算法的流程描述：

输入：相关性任务集TR，需要使用资源R的并发任务集TR，资源R的剩余资源数RR

输出：冲突消解后的并发任务集TR

步骤1：当并发任务集TR为空时结束本算法，否则按公式6从TR中取出优先集最高的任务t（优先集获取原则见上一节），并跳转到步骤2。

步骤2：计算任务t的最早开始时间ES，并跳转到步骤3。

步骤4：重新计算TR的关键路径，并跳转到步骤1。

2.3 多资源冲突消解算法

多资源冲突消解算法按资源优先级对冲突资源进行排序，先处理负载率高的冲突资源。多资源冲突消解过程其实是单资源冲突消解的级联调度过程。该算法分时间段进行资源冲突消解，可以减少任务间耦合的产生，并使相关性任务集的整体完成时间延迟最小化。

下面给出多资源冲突消解算法的流程描述：

步骤1：以式（9）计算T中所有任务的最早开始时间ES，并跳转到步骤2。

步骤2：遍历T，依次获取任务，该任务尚未进行资源冲突消解，否则，结束该算法。

步骤3：遍历R，获取任务所使用的所有资源类型，计算这些资源的负载率，并按负载率非递增排序，放入队列QueueR中。

步骤4：当QueueR为空时跳转到步骤5，否则依次取出队首资源R，并按以下步骤进行处理。

（1）使用2.2节的单资源冲突消解算法计算TR中所有任务的最早开始时间ES，同时更新连接边（FS）的集合。

（2）添加延迟关系边(SS)，即优先获取资源的任务与延迟获取该资源的任务之间建立“开始—开始”的延迟关系。

（3）计算TR中任务的所有后续任务的最早开始时间，并更新连接边。

步骤5：计算各个任务的资源自由时差：

（1）首先计算直接依赖关系FS中，以任务为直接前驱时，即任务的最晚开始时间LS。

（2）各个任务的资源自由时差RFF。

步骤6：重新计算关键路径，RFF=0的任务为关键任务，并跳转到步骤2。

3 实例分析

以图1和表1给出的相关性任务集为例，根据多资源冲突消解算法自左向右解决资源冲突，依次找出资源冲突任务集TR={,,}和TR={,,}。按照任务优先级获取原则进行依次调度，若存在多任务多资源冲突情况，则按照资源优先级（资源负载率）进行调度。表2给出了资源冲突消解完成后的任务调度情况，表3给出了在资源冲突消解完成的基础上进行和资源冲突消解完成后的任务调度情况。图2给出了在资源冲突消解完成时相关性任务集共享资源冲突消解调度结果图。

表2 R1资源冲突消解完成后数据

表3 R2和R3资源冲突消解完成后数据

图2 相关性任务集共享资源冲突消解结果

图3示出的相关性任务集，在图1的基础上添加了基于资源冲突消解的SS连接边，使在该相关性任务集在资源约束条件下建立了关键路径的连通性，图中灰色底纹的任务是资源自由时差RFF=0的关键任务。关键路径为→→→→→，说明在资源冲突消解完成后，整个相关性任务集的完成时间为120个单位时间，比原先任务集延迟了20个单位时间。

图3 添加了基于资源冲突消解的SS连接边的相关性任务集

4 结 论

本文基于关键路径和资源使用率优先调度而提出了一种共享资源冲突消解算法，属于启发式算法，它能够实现多资源多任务并发情况下的有效调度。与目前领域中共享资源约束下任务调度的研究成果相比，本算法有如下创新点：（1）给出了基于共享资源竞争关系的相关性任务集的表示方式。（2）提出了基于级联调度的资源冲突消解的算法，通过分时间段利用任务优先级和资源优先级进行冲突消解。因此本算法对于深入研究分布式多处理器环境下任务并发调度优化具有相应意义，同时对实际情况上相关性任务受多资源约束这一现实问题的研究取得一定的进展。