一种云计算中依赖任务的解耦并行调度方法

本发明属于云计算应用领域，涉及到云服务中任务依赖关系描述、解耦合 和并行调度等方法。

分布式计算技术已成为当前信息技术的主流，如移动计算和云计算等。云 环境下的大型应用服务往往被分解成多个任务来调度和执行，并且分解后的若 干任务之间往往存在着一定的约束和依赖关系，即具有较强的耦合性。任务间 依赖关系的存在对任务调度提出了新的挑战。当前，分布式环境中的任务调度 研究往往只是考虑任务间没有相互依赖关系即独立任务的简单情况，虽然一定 程度上解决了系统资源异构性和可用性问题，但不适用于具有依赖关系的任务 调度。而对于依赖任务调度问题的研究大多是基于某个特定环境或对称同构系 统。在云计算中，由于资源的异构性和分布性使得资源之间不仅处理能力存在 巨大差异，而且资源之间的网络连接状况也千差万别，因此云环境中的依赖任 务调度问题所要考虑的因素远比同构系统要多，其调度算法也要远比同构系统 复杂。虽然目前已有相当数量的异构系统依赖任务调度算法，但它们大多数是 对同构系统算法的改进，通常以依赖关系构建依次调度任务队列，实现单一性 能指标为目标的静态调度，难以根据系统资源的实时信息进行动态调度；忽略 了依赖任务调度的并行性，即不能有效解决耦合问题，使得系统资源不能得到 充分利用，降低了系统利用率；没有考虑通信开销代价和任务执行开销间的关 系，使得系统资源存在部分空闲[①Cathy H.Xia，George Michailidis， Nicholas Bambos.Dynamic on‑line task scheduling on parallel processors. Performance Evaluation Vol.46，2001，219‑233.②Tei‑Wei Kuo，Wang‑Ru Yang and Kwei‑Jay Lin.A class of rate‑based real‑time scheduling algorithms. IEEE Transaction on computers，Vol 51，No.6，June 2002，708‑720.③何琨， 赵勇，陈阳.分布式环境下多任务调度问题的分析与求解[J].系统工程理论与实 践.2007，5：119‑125.④石威，郑纬民.相关任务图的均衡动态关键路径调度算 法[J].计算机学报.2001，24(9)：991‑997.⑤桂小林，钱德沛.元计算环境下的 支持依赖任务的OGS算法研究[J].计算机学报.2002，25(6)：582‑586. ⑥Topcuoglu H，Wu M Y.Performance‑effective and low‑complexity task  scheduling for heterogeneous computing.IEEE Transactions on Parallel  and Distributed Systems.2002，13(3)：260‑274.]。因此在云计算中，如何提 高强耦合的依赖任务调度的并行性、实时性和动态性，以及为提高系统利用 率，对有依赖关系的任务请求进行合理的调度与部署，成为当前云计算要解决 的热点问题之一。

本发明解决的技术问题是根据云计算的异构性特征，提出了依赖任务关系 描述图，并构建了依赖任务的解耦并行调度方法。该方法首先以入度为零对任 务依赖关系进行解耦来构建就绪任务的集合，动态描述某个时刻可并行调度的 任务。然后根据实时资源评价，对就绪任务的集合进行分布式多目标调度，有 效地提高调度并行性。除了对资源评价外，在任务分配时还考虑任务执行和任 务间通信开销(E/C)，来决定是否用任务复制来代替其依赖数据传输，以减少 通信开销。整个调度方法可以对就绪任务集合中多个任务进行动态并行调度， 较好地兼顾实时性和并行性、通信开销和负载均衡等性能指标，通过动态调度 策略有效地提高系统的整体性能。

本发明的技术方案如下：

(1)任务依赖关系的描述：通常用节点表示组成一个应用服务的各个任 务、有向边表示任务间的依赖关系，用计算时间和通信时间作为任务属性。而 在异构环境下，同一任务在不同处理机上执行时间不同，这种关系图不能很好 地适应异构计算和云计算。根据云计算异构性的特点，本发明提出包括计算 量、依赖数据传输量和存储资源需求量的依赖任务关系描述图，解决了异构环 境下同一任务在不同节点上执行时间不同的时域动态性问题。该任务关系描述 图具有图论中有向无环图(DirectedAcyclic Graph，DAG)的特征。

任务之间的依赖关系用一个五元组G＝(T，E，W，A，D)来表示，其中包 含了任务之间的关系及对系统存储资源的需求，本发明要求任务的存储资源需 求量不可超过节点的最大可利用存储空间值。

图中元素代表的含义如下：T为应用服务的n个任务组成的集合T＝ {T1，T2，......，Tn}。E是边的集合E＝(eij|0＜i，j≤n；i≠j)。应用服务中的任务的依赖关系 定义为：如果Tj必须在Ti执行完毕后才能运行，则从Ti到Tj就存在一条有向边 eij，并且Ti是Tj的前驱任务，Tj是Ti的后继任务。W为任务的计算量集合， W＝{Wi|0＜i≤n}。A为任务的最低存储资源需求的集合A＝{Ai|0＜i≤n}，Ai为Ti的 最低存储需求Ai＝{Rmem，Rstor}，其中Rmem为内存空间需求量，Rstor为存储空间需求 量。D为任务之间的依赖数据传输量矩阵，dij表示前驱任务Ti与后继任务Tj之 间的数据传输量。

(2)解耦合方法：

本发明中的解耦合方法的核心是入度值为零，即任务可被调度的必要条件 是在依赖关系图中某节点的入度值为零，也就是说其前驱任务均已执行完毕。

对任务依赖关系图根据图中节点入度值为零的条件来解耦合，并且建立一 个就绪任务集合ReadyTaskSet＝{Ti|0＜i≤n}，来动态描述某个时刻可并行调度的 任务。本发明的就绪集合定义为：某个时刻没有前驱任务或直接前驱任务都已 经完成的任务组成的集体，即入度值为零。集合中的任务，其优先级是相同 的，不分先后，任一成员只要所需的存储资源满足，即可被调度。初始时就绪 任务集合中的元素都是入度值为0的任务，当集合中的某个任务执行完毕并把 依赖数据传递给其后继任务后，就从就绪任务集合中删除该任务，并且隐藏 (或逻辑删除)依赖关系图该任务节点和从该任务节点发出的所有有向边。然 后从新的可见的(即不含隐藏的边和任务节点)图中选择所有入度为0的任务 加入就绪任务集合，直至全部任务调度完毕(或任务依赖关系图完全不可见)。

本发明中以入度值为零解耦合，当任务依赖关系图中任务的入度值为零时 就把该任务加入就绪任务集合，这样就可以描述某个时刻可被并行调度的多个 任务。当前大多数静态调度策略是基于队列结构，某个任务必须在等待队列中 其前面的任务都执行完毕且返回结果后才能被调度。即使两个任务之间没有依 赖关系也必须等待，这样就会引起系统资源的浪费，降低了资源利用率。本设 计根据任务依赖关系图动态生成入度为零的就绪任务集合，解决任务之间的强 耦合，减少了任务等待时间和系统资源空闲，提高了系统利用率。

(3)并行调度方法：在本发明中的调度方法中，由于就绪任务集合中的任 务没有依赖关系，任务相互独立可进行并行调度，因此就绪任务集合中的任务 有极强的并行性。任务调度就可以根据就绪集合ReadyTaskSet中任务的存储资 源需求和处理节点的实时空闲存储空间信息，对就绪任务集合中的各个任务并 行发起分布式多目标协商调度请求，调度中要考虑的目标包括最早完成时间、 通信开销和系统负载均衡等。然后根据资源评价的结果，任务调度为任务选择 具有最早完成时间的节点，而不仅仅是选择具有最早开始时间的节点。对于有 依赖关系的任务来说，整个调度长度是由最后一个任务的完成时间来计算的， 因此采用最早开始时间并不能真正完全描述一个调度策略的整体性能。通过并 行调度集合中的任务来提高系统的并行度，实现了对有依赖关系的多个任务请 求的更合理的调度与部署。

在任务调度过程中用到的几个评价定义如下：

定义1C(m，i，n，j)表示两个耦合任务间的依赖数据通信开销，即分配到处 理节点Pi的前驱任务Tm与分配到Pj的后继任务Tn之间的数据通信开销：

$C(m,i,n,j)=\left\{\begin{array}{cc}0;& i=j\\ {\mathrm{band}}_{\mathrm{ij}}*d_{\mathrm{mn}};& i\≠j\end{array}\right.$

其中，bandij表示异构节点间的通信速率，dmn表示任务间依赖数据的传输量。

定义2CT(m，i，j)表示要复制两个耦合任务中的前驱任务时，需要的任务传 输开销，即把一个前驱任务Tm从处理节点Pi传输到Pj的通信开销：

$\mathrm{CT}(m,i,j)=\left\{\begin{array}{cc}0;& i=j\\ {\mathrm{band}}_{\mathrm{ij}}*\left|T_m\right|;& i\≠j\end{array}\right.$

其中，|Tm|表示任务Tm的程序规模大小。

定义3任务Ti在处理节点Pj上的最早可能完成时间记为epft(Ti，Pj)，计算 公式为：

epft(Ti，Pj)＝epst(Ti，Pj)+w(Ti，Pj)

epst(Ti，Pj)为任务Ti在Pj上的最早可能开始时间，w(Ti，Pj)为任务Ti在Pj上的执行 时间，w(Ti，Pj)＝Wi/FRj，即任务计算量/处理器的处理能力，处理器的处理能力 FR用CPU主频与指令周期的乘积来计算，FR＝FREQcpu*TIME。

当系统中只有一个节点Pj的全部存储资源才能满足某个任务Ti的存储需求 Ai，并且当时该节点上已有任务在执行，则任务Ti就必须等待，直到为Pj分配 的所有其他任务执行完毕并释放资源后，任务Ti才能被调度执行。在任务Ti等 待的过程中，可能出现Pj的剩余资源再次分配给其他需求资源量小的任务的情 况，即剩余资源不断地再分，这样Ti就会因为长时间得不到资源而引起“饿死” 和死锁的现象。

为了避免上述可能出现的现象，给出相应的策略对任务调度进行控制。Pj 上已分配的所有任务中最晚执行完成的任务的结束时间LAFT是Ti的最早可能 执行时间。对于执行节点Pj，采用下面的策略进行调度：在就绪任务集合 ReadyTaskSet中只选择能在Ti的LAFT时刻之前执行完成的任务分配到Pj中， 这样当到达LAFT时刻时，任务Ti就可以调度到Pj上执行，而不会被“饿死”； 对于系统中除了Pj以外的其他节点，即{P1，P2，...Pj‑1，Pj+1，...Pp}，仍然按照上面 (定义1‑定义3)的评价定义进行调度决策。通过以上策略对特殊情况下的任 务进行调度控制，可以提高调度效率。

(4)通信开销的评价及控制方法：调度任务时要在系统中选择使其具有最 早可能完成时间的节点，即任务Ti的执行节点PTi＝{Pj|min{epft(Ti，Pj)}}。在调度 决策时为了减少不必要的数据传输，本发明还对任务执行开销和任务间通信开 销(E/C)进行了综合衡量。设依赖任务Tu和Tk间依赖数据的传输时间为 C(u，i，k，j)，传输前驱任务的时间为CT(u，i，j)，前驱任务在新节点上执行的时间为 w(Tu，Pj)，CT(u，i，j)与w(Tu，Pj)的和称为任务复制开销，即 Ccopy(u，i，j)＝CT(u，i，j)+w(Tu，Pj)。当C(u，i，k，j)＞Ccopy(u，i，j)时，则复制前驱任务Tu到 Pj节点上再执行一次，形成本地数据为其后继任务Tk服务，以减少任务间的通 信开销。若某个任务有多个前驱，则选择传输数据与任务复制开销差距最大的 任务，即Copytask＝{Tu|max{C(u，i，k，j)‑Ccopy(u，i，j)}}，Pi≠Pj进行任务复制

通过以上几个方面的决策，使调度满足并行性、通信开销和负载均衡等多 方面的性能。

本发明的效果和益处是通过引入任务的计算量、依赖数据传输量和任务对 存储资源的需求量解决异构环境中不同节点的性能差异，描述任务在各节点上 执行性能的时域动态性，构造了云计算中异构环境下任务依赖关系图；利用依 赖任务入度值为零的解耦方法，由入度值为零的任务组成了无优先次序的就绪 任务集合，集合中任一任务只要存储资源的需求满足即可被调度；并行调度方 法同时兼顾了实时性和负载均衡，减少了基于队列的调度方式引起的资源空 闲。该解耦并行调度方法充分考虑了调度的整体性能，采用最早完成时间为评 价条件，设计了防止饿死和死锁的调度策略，是一种调度依赖关系任务的有效 和并行的方法。该方法适用于云计算等分布式异构系统环境，例如网格计算、 普适计算等分布式计算环境，为未来计算机网络的应用与发展提供技术支持。

图1是任务模型图。

图2是调度过程运行顺序图。

图3是图1所示的任务模型的调度示意图。图中箭头所示为任务间的数据 传输。

以下结合技术方案和附图详细叙述本发明的实施例。

1.任务依赖关系的描述：图1所示为一个含有10个依赖任务的服务中任务 的依赖关系图(圆圈节点代表任务T；有向边E表示任务间的依赖关系；方框 内数字表示任务的计算量W；边上数字代表任务之间的依赖数据传输量D；尖 括号内表示任务的最低存储资源需求A，图中只给出了部分任务的最低存储资 源需求)。

2.入度值为零解耦合方法：任务管理根据任务依赖关系图中任务入度值为 零的条件来解耦合，并且建立就绪任务集合ReadyTaskSet来动态描述某个时刻 可并行调度的任务。初始时就绪任务集合中的元素都是入度值为0的任务。以 图1为例，初始时就绪任务集合ReadyTaskSet＝{T1}，即此时只有T1可以被调 度。只要某个节点的可用内存大于T1的最低内存需求量并且可用磁盘空间大于 T1的最低磁盘需求量，即empty_mem＞Rmem1&&empty_stor＞Rsize1，且能最早完 成等，T1即可执行。当T1执行完毕并把依赖数据传递给后继任务 T2，T3，T4，T5，T6后，就从就绪任务集合中删除T1，并且在图中删除该任务节点和 其发出的所有有向边。然后从新的关系图中选择所有入度为0的任务，即 T2，T3，T4，T5，T6加入就绪任务集合，ReadyTaskSet＝{T2，T3，T4，T5，T6}。此时只要节点 能最早完成且存储资源满足任务要求，这五个任务即可同时执行。同理若T3执 行完毕，就把T7加入就绪任务集合，而不论其余任务节点T2，T4，T5，T6是否执行 完毕。整个过程具有具有极强的并行性和较高的资源利用率。

3.调度方法：系统中每个节点的空闲内存容量、空闲磁盘容量称为该节点 的实时存储资源信息，即RS＝。每当任务请求或释放 资源后要实时更新节点存储资源：RS＝RS+(‑1)k*Ai，其中当有任务Ai申请Pj的 可用存储资源即任务到达第j个节点时，k＝1；当任务完成释放存储资源时， k＝0。这样就很好地表现了节点资源的动态性变化，为调度过程提供了可靠、 实时的资源信息。当就绪任务集合ReadyTaskSet不为空时，并行对就绪任务集 合中的各个任务发起分布式多目标协商调度请求。调度方法根据任务的存储资 源需求和处理节点的实时资源信息，首先选择可以满足某个任务Tk资源需求的 若干节点P1，P2，...Pj，然后再计算Tk在P1，P2，...Pj中每个节点上的最早开始时间 epst(Tk，Pj)和最早完成时间epft(Tk，Pj)。其中计算epst(Tk，Pj)时，要对依赖数据传 输开销和任务复制开销的进行比较，即对其前驱任务Tu与该任务之间的通信时 间C(u，i，k，j)和把前驱任务Tu的任务复制开销Ccopy(u，i，j)进行比较。当 C(u，i，k，j)＞Ccopy(u，i，j)时，就把Tu在Pj上重新执行一次，以形成本地数据为Tk服 务，减少数据通信开销，降低网络负载。若Tk有多个前驱，则复制数据传输时 间和任务复制开销的差距最大的任务，即 Copytask＝{Tu|max{C(u，i，k，j)‑Ccopy(u，i，j)}}，Pi≠Pj。这样最早开始时间用公式 epst(Tk，Pj)＝max{epft(Tu，Pi)+min{C(u，i，k，j)，Ccopy(u，i，j)}}来计算，公式中Tu为Tk的 前驱任务，Pi是Tu的执行节点。然后计算最早完成时间 epft(Tk，Pj)＝epst(Tk，Pj)+w(Tk，Pj)。最后为任务Tk选择具有最小的最早完成时间的 节点，即任务Tk的执行节点PTk＝{Pj|min{epft(Tk，Pj)}}。这样利用该调度方法可以 实现任务的并行执行，提高了系统的并行度，实现了对有依赖关系的多个任务 请求的更合理的调度与部署。

总体来说，整个解耦并行调度方法的具体调度过程如下：首先根据任务依 赖关系图计算每个任务的入度值。建立一个就绪任务集合，初始时就绪任务集 合中的元素为入度值为零的任务，即入口任务。集合中的成员为一组相互独 立的任务可进行并行调度，然后提取就绪任务集合中任务的信息进行分布式多 目标协商调度，根据系统资源的实时情况把任务分配到系统中使该任务具有最 早可能完成时间的节点上。在选择任务的执行节点时，综合评价多个目标进行 调度决策，包括通信代价、节点负载、任务执行时间等。当出现任务Ti需求的 存储资源是系统中某个节点Pj所能提供的全部存储资源，并且Pj上已有任务在 执行的特殊情况时，采用特殊的调度控制策略：对于执行节点Pj，在就绪任 务集合中只能选择可以在当前时刻与Pj上已分配的任务中最晚执行结束的时间 LAFT这段时间间隙中能执行完成的任务分配到Pj上，以使任务Ti在LAFT时刻 可以被调度到Pj上执行，而不会被“饿死”；对于系统中除了Pj以外的其他节 点，仍然按照上面(定义1‑定义3)的评价定义进行调度决策。每实际执行完一 个任务，就把该任务从就绪任务集合中移除，并在依赖关系图中删除该任务， 并且删除从该任务节点发出的所有有向边(这里的删除是指从逻辑上删除，并 不是真正地删除任务节点或边，而是利用标记来标识任务是否被调度或执 行)。然后从新的图中选择所有入度为零的任务加入就绪任务集合，直至所有 任务调度完毕。

具体调度方法的伪代码如下所示：

针对图1所示的任务依赖关系图，利用本文提出的解耦并行调度方法在三 个异构节点组成的云环境中进行调度，调度结果如图3所示。此外，模拟调度 实验表明，与典型的静态调度算法HEFT[Topcuoglu H，Wu M Y. Performance‑effective and low‑complexity task scheduling for  heterogeneous computing.IEEE Transactions on Parallel and Distributed  Systems.2002，13(3)：260‑274.]相比，应用本方法的调度长度减少了 20％‑30％。