DAG模型：面向云计算的任务优化调度技术研究成果

在图论中，如果一个有向图无法从任意顶点出发经过若干条边回到该点，则这个图是一个有向无环图，即DAG图［105］。在多数据中心的云环境中，多数据中心的数据量大，并且数据中心分布在不同的地理位置，同时，数据中心具有异构性。针对这些特点，可以将数据作为用户任务，因而使用DAG对工作流进行建模。

在建模过程中，由于受制于某些任务必须比另一些任务较早执行，必须将任务集合排序为一个队列，则该集合可以由一个DAG图来呈现。在DAG中，每个顶点表示一个任务，每条边表示一种限制约束，利用拓扑排序算法生成一个有效的序列。DAG中的可达性关系构成了一个局部顺序，而任何有限的局部顺序也都可以由DAG的可达性来呈现。

工作流的例子如图6-2所示。图中的d1、d2、d3、d4、d5表示数据中心的五个数据集。d1为原始数据集，d2～d5为中间数据集，a1、a2、a3、a4表示工作流中的四个子任务，箭头表示任务和数据之间的依赖关系。如数据集d2由任务a1产生，任务a2和a3的执行需要依赖于d2，所以a2和a3必须等到a1执行结束才能开始执行。

图 6-2　任务执行顺序图

云工作流应用表示为DAG，记为V（A，E），A=｛a，a2，…，an｝是任务的集合，E表示各个任务之间的优先关系和依赖关系。

没有父任务的任务称为初始任务，表示为astart，没有后续任务的任务称为结束任务，表示为aend，除此以外，每个任务均有父任务以及子任务，并且只有其所有的父任务己经完成，它才能开始执行，为了便于表达，设定无执行时间的虚拟任务分别表示工作流的起始和结束，记为、。

在任务等待执行时，若具有相同深度的任务在执行时出现死锁，则其等待时间不能小于同深度任务的执行时间，以此保证整个工作流的执行完成。

对于一个给定的云工作流应用，每个任务的执行都是非抢占的。每一个应用任务ai都需要在一个云节点pj上执行任务，云节点的集合为P=｛p1，p2，pj，…，pm｝，其执行时间表示为Tij，该时间与任务的大小及节点的计算速度相关，Tij表示任务ai的数据到达云节点pj的时间，即任务ai的父任务产生，并发送到任务ai的所有数据的时间和。

任务的平均执行时间定义为公式（6-1）：(www.xing528.com)

任务的平均通信量定义为公式（6-2）：

其中，Dij表示任务在DAG图中ai、aj间的传输数据量，表示云节点之间的平均带宽。

设为ai的全部父任务的集合，为ai的全部子任务的集合。如果云节点pj可以开始接受任务，则执行的最早时间为，定义如公式（6-3）所示：

其中，，任务在云节点pj上的最早开始时间和最早完成时间为。

任务在云节点pj的开始时间为，结束时间为。当一个工作流任务都被调度之后，任务的结束时间。若一个工作流任务都被调度之后，具有多于1个的，则其调度时间长度为，其中k∈V。