一种分布式环境下的工作流任务调度方法

摘要

本发明公开了一种分布式计算环境下的工作流任务调度方法，使用有向无环图来描述工作流任务和资源，根据节点权值信息和边权值信息计算平均任务执行时间和平均任务传输时间，以据此判断工作流任务类型并进行分类模型处理，将具有数据依赖关系的任务分割成了若干个独立的任务集，每个任务集包含一个或者若干个任务，且每个任务集中的多个任务具有数据依赖关系，从而将工作流任务转化成了“独立任务”。任务集将计算数据量比较大或者数据传输量比较大的任务聚拢在一起，同时降低了需要独立分配的任务数量，从整体上提高了后期任务调度性能。另外，当工作流任务数量增加时，仅需加强对任务的聚拢操作，无需再对所有的任务进行处理，具有更好的扩展性。

说明书

技术领域

本发明属于分布式计算下工作流任务调度技术、工作流任务建模技术，特别涉及一种分布式计算环境下的工作流任务调度方法。

背景技术

分布式计算环境中任务调度是最重要的部分，并且在整个分布式基础设施中也发挥着不可替代的作用。分布式计算环境下的任务调度要求在考虑时间、成本、可靠性、可用性、吞吐量、资源利用率的情况下找到任务资源分配的最佳方案。

分布式计算环境下的任务调度主要分为独立任务调度和工作流任务调度。工作流任务中包含了若干个任务，且这若干个任务间具有数据依赖关系。现有的方法在进行工作流任务调度时，以降低任务执行成本为主要目标，例如，基于小位置值规则的粒子群优化任务调度方法，根据小位置值规则更新粒子位置信息，收敛速度快，能够最小化任务调度执行成本；基于双目标优化的异构最早时间完成算法，充分考虑用户对预算和截止时间的要求进行任务调度，并取得了较好的效果。但是，上述算法均未考虑工作流任务之间的数据依赖关系对任务调度效果产生的影响，导致工作流任务通信成本较高、执行完成时间较长，工作流任务调度效率低下。

发明内容

本发明为解决现有技术中存在的以上问题，提供了一种分布式计算环境下的工作流任务调度方法，考虑了工作流任务之间的数据依赖关系对任务调度效果产生的影响，降低了工作流任务通信成本以及执行完成时间，提高了工作流任务调度效率。

为了实现上述目的，本发明采用的技术方案是：

一种分布式计算环境下的工作流任务调度方法，包括以下步骤：

步骤1：使用有向无环图对需要进行调度的工作流任务进行描述，得到工作流任务有向无环图；使用有向无环图对分布式计算环境下的计算资源进行描述，得到计算资源有向无环图；

步骤2：根据工作流任务有向无环图以及计算资源有向无环图，计算平均任务执行时间t₁、平均数据传输时间t₂；

步骤3：若t₁＞t₂,则被调度工作流任务为计算密集型任务，进入步骤4；若t₁＜t₂,则所述工作流任务为IO密集型任务，进入步骤5；

步骤4：根据计算密集型任务的有向无环图的节点权值进行所述有向无环图的更新和分解，得到若干个任务集，进入步骤6；

步骤5：根据IO密集型任务的有向无环图的边权值进行所述有向无环图的更新和分解，得到若干个任务集，进入步骤6；

步骤6：将得到的若干个任务集根据各任务集的计算数据量进行排序，并将计算资源根据其计算能力大小进行排序；

步骤7：根据步骤6的排序结果，将计算数据量大的任务集分配给计算能力大的计算资源。

上述方案中，所述步骤1包括工作流任务有向无环图中节点的总数为I，其中，第i个节点的权值w_i表示任务计算数据量，i∈[1,2,…,I]；工作流任务有向无环图中边的总数为M,其中，第m个边的权值v_m表示任务之间的数据传输量，m∈[1,2,…,M]；计算资源有向无环图中节点的总数为J,其中，第j个节点的权值w_j表示资源计算能力，j∈[1,2,…,J]；计算资源有向无环图中边的总数为N,其中，第n个边的权值v_n表示资源间的数据传输能力，n∈[1,2,…,N]；

上述方案中，所述步骤2中平均任务执行时间t₁计算公式为：

$t_1=\frac{\underset{i=1}{\overset{I}{\Sigma }}{w}_i}{\underset{j=1}{\overset{J}{\Sigma }}{w}_j}$

平均数据传输时间t₂计算公式为：

$t_2=\frac{\underset{m=1}{\overset{M}{\Sigma }}{v}_i}{\underset{n=1}{\overset{N}{\Sigma }}{v}_n}$

上述方案中，所述步骤4包括以下几个步骤：

步骤4.1：计算工作流任务有向无环图从根节点到每一个叶子节点路径上节点权值之和；

步骤4.2：根据步骤4.1的计算结果选取工作流任务有向无环图中节点权值之和最大的路径，将选取的路径上的节点聚拢为一个根节点，将聚拢得到的根节点的权值更新为选取的路径各节点权值之和，将更新后的根节点从工作流任务有向无环图中剔除，被剔除的根节点构成一个独立的任务集；

步骤4.3：重复步骤4.2，直至工作流任务有向无环图中的节点均为独立的任务集，得到若干个任务集，进入步骤6。

上述方案中，所述步骤5包括以下几个步骤：

步骤5.1：计算工作流任务有向无环图从根节点到每一个叶子节点路径上边权值之和；

步骤5.2：根据步骤5.1的计算结果选取工作流任务有向无环图中边权值之和最大的路径，将选取的路径上的节点聚拢为一个根节点，将聚拢得到的根节点的权值更新为选取的路径各节点权值之和，将更新后的根节点从工作流任务有向无环图中剔除，被剔除的根节点构成一个独立的任务集；

步骤5.3：重复步骤5.2，直至工作流任务有向无环图中的节点均为独立的任务集，得到若干个任务集，进入步骤6；

上述方案中，所述步骤6中任务集的计算数据量为任务集中各任务的计算数据量之和。

本发明的有益效果是：

1)本发明中工作流任务模型处理时划分任务集的方法将计算数据量比较大或者数据传输量比较大的任务聚拢在一起，降低了需要独立分配的任务数量，从整体上提高了后期任务调度性能。

2)当工作流任务数量增加时，本发明仅需加强对任务的聚拢操作，无需再对所有的任务进行处理，具有更好的扩展性。

3)本发明考虑了工作流任务之间的数据依赖关系对任务调度效果产生的影响，通过工作流任务模型处理，将具有复杂数据依赖关系的工作流任务简化为看似相互独立的任务集，方便了后期进行高效的任务调度，降低了工作流任务通信成本以及执行完成时间，提高了工作流任务调度效率，满足了用户对任务高效处理的需求。

附图说明

图1为本发明中工作流任务模型处理示意图；

图2为本发明中任务调度流程；、

图3为本发明中计算密集型工作流任务有向无环图；

图4为本发明中步骤4.1示意图；

图5为本发明中步骤4.2示意图；

图6为本发明中步骤4.3示意图

图7为本发明中IO密集型工作流任务有向无环图；

图8为本发明中步骤5.1示意图；

图9为本发明中步骤5.2示意图；

图10为本发明中步骤5.3示意图；

具体实施方式

为使本发明的目的、技术方案和优点更加清楚，下面将结合附图对本发明作进一步地详细描述。

本发明提出了一种分布式计算环境下的工作流任务调度方法，参见图1-2，整个方法的实现包括以下步骤：

步骤1：使用有向无环图对需要进行调度的工作流任务进行描述，得到工作流任务有向无环图；使用有向无环图对分布式计算环境下的计算资源进行描述，得到计算资源有向无环图；工作流任务有向无环图中节点的总数为I，其中，第i个节点的权值w_i表示任务计算数据量，i∈[1,2,…,I]；工作流任务有向无环图中边的总数为M,其中，第m个边的权值v_m表示任务之间的数据传输量，m∈[1,2,…,M]；计算资源有向无环图中节点的总数为J,其中，第j个节点的权值w_j表示资源计算能力，j∈[1,2,…,J]；计算资源有向无环图中边的总数为N,其中，第n个边的权值v_n表示资源间的数据传输能力，n∈[1,2,…,N]；

步骤2：根据工作流任务有向无环图以及计算资源有向无环图，计算平均任务执行时间t₁、平均数据传输时间t₂；

平均任务执行时间t₁计算公式为：

$t_1=\frac{\underset{i=1}{\overset{I}{\Sigma }}{w}_i}{\underset{j=1}{\overset{J}{\Sigma }}{w}_j}$

平均数据传输时间t₂计算公式为：

$t_2=\frac{\underset{m=1}{\overset{M}{\Sigma }}{v}_i}{\underset{n=1}{\overset{N}{\Sigma }}{v}_n}$

步骤3：若t₁＞t₂,则被调度工作流任务为计算密集型任务，进入步骤4；若t₁＜t₂,则所述工作流任务为IO密集型任务，进入步骤5；

步骤4：根据计算密集型任务的有向无环图的节点权值进行所述有向无环图的更新和分解，得到若干个任务集，进入步骤6；

步骤4.1：计算工作流任务有向无环图从根节点到每一个叶子节点路径上节点权值之和；

步骤4.2：根据步骤4.1的计算结果选取工作流任务有向无环图中节点权值之和最大的路径，将选取的路径上的节点聚拢为一个根节点，将聚拢得到的根节点的权值更新为选取的路径各节点权值之和，将更新后的根节点从工作流任务有向无环图中剔除，被剔除的根节点构成一个独立的任务集；

步骤4.3：重复步骤4.2，直至工作流任务有向无环图中的节点均为独立的任务集；进入步骤6；

步骤5：根据IO密集型任务的有向无环图的边权值进行所述有向无环图的更新和分解，得到若干个任务集，进入步骤6；

步骤5.1：计算工作流任务有向无环图从根节点到每一个叶子节点路径上边权值之和；

步骤5.2：根据步骤5.1的计算结果选取工作流任务有向无环图中边权值之和最大的路径，将选取的路径上的节点聚拢为一个根节点，将聚拢得到的根节点的权值更新为选取的路径各节点权值之和，将更新后的根节点从工作流任务有向无环图中剔除，被剔除的根节点构成一个独立的任务集；

步骤5.3：重复步骤5.2，直至工作流任务有向无环图中的节点均为独立的任务集；进入步骤6；

步骤6：将得到的若干个任务集根据任务集的权值大小进行排序，并将计算资源根据其计算能力大小进行排序；

步骤7：根据步骤6的排序结果，将权值大的任务集分配给计算能力大的计算资源。

实施例1

结合图3中工作流任务有向无环图对该实施例进行说明：

步骤1：使用有向无环图对需要进行调度的工作流任务进行描述，得到工作流任务有向无环图，如图3所示；使用有向无环图对分布式计算环境下的计算资源进行描述，得到计算资源有向无环图；工作流任务有向无环图中节点的总数为5，其中，第i个节点的权值w_i表示任务计算数据量，i∈[1,2,…,5]；工作流任务有向无环图中边的总数为4,其中，第m个边的权值v_m表示任务之间的数据传输量，m∈[1,2,3,4]；计算资源有向无环图中节点的总数>j表示资源计算能力，j∈[1,2,…,J]；计算资源有向无环图中边的总数为N,其中，第n个边的权值v_n表示资源间的数据传输能力，n∈[1,2,…,N]；

步骤2：根据工作流任务有向无环图以及计算资源有向无环图，计算平均任务执行时间t₁、平均数据传输时间t₂；该实施例中则：

$t_1=\frac{\underset{i=1}{\overset{I}{\Sigma }}{w}_i}{\underset{j=1}{\overset{J}{\Sigma }}{w}_j}=\frac{5+3+4+7+2}{1}=21;$

$t_2=\frac{\underset{m=1}{\overset{M}{\Sigma }}{v}_i}{\underset{n=1}{\overset{N}{\Sigma }}{v}_n}=\frac{1+5+4+2}{1}=12$

步骤3：由于t₁＞t₂,则被调度工作流任务为计算密集型任务，进入步骤4；

步骤4：根据计算密集型任务的有向无环图的节点权值进行所述有向无环图的更新和分解，得到若干个任务集，进入步骤6；

步骤4.1：如图4所示，计算工作流任务有向无环图从根节点到每一个叶子节点路径上节点权值之和，分别为15和10；

步骤4.2：根据步骤4.1的计算结果选取出工作流任务有向无环图中节点权值之和最大的路径5-3-7，如图5所示，将选取的路径上的节点聚拢为一个根节点，将聚拢得到的根节点的权值更新为选取的路径各节点权值之和，即15，将更新后的根节点从工作流任务有向无环图中剔除，被剔除的根节点构成一个独立的任务集(5,3,7)；该任务集包含任务5、任务3、任务7，且计算数据量为15；更新后的工作流任务有向无环图中的节点均为独立的任务集；

步骤4.3：如图6所示，得到三个任务集，分别为(5,3,7)、(2)、(4)，各任务集计算数据量分别为15、2、4；

步骤6：将得到的若干个任务集根据任务集的权值大小进行排序，并将计算资源根据其计算能力大小进行排序；

步骤7：根据步骤6的排序结果，将权值大的任务集分配给计算能力大的计算资源。

实施例2

结合图7中IO密集型工作流任务有向无环图对该实施例进行说明：

步骤1：使用有向无环图对需要进行调度的工作流任务进行描述，得到工作流任务有向无环图，如图7所示；使用有向无环图对分布式计算环境下的计算资源进行描述，得到计算资源有向无环图；工作流任务有向无环图中节点的总数为5，其中，第i个节点的权值w_i表示任务计算数据量，i∈[1,2,…,5]；工作流任务有向无环图中边的总数为4,其中，第m个边的权值v_m表示任务之间的数据传输量，m∈[1,2,3,4]；计算资源有向无环图中节点的总数为J,其中，第j个节点的权值w_j表示资源计算能力，j∈[1,2,…,J]；计算资源有向无环图中边的总数为N,其中，第n个边的权值v_n表示资源间的数据传输能力，n∈[1,2,…,N]；

步骤2：根据工作流任务有向无环图以及计算资源有向无环图，计算平均任务执行时间t₁、平均数据传输时间t₂；该实施例中则：

$t_1=\frac{\underset{i=1}{\overset{I}{\Sigma }}{w}_i}{\underset{j=1}{\overset{J}{\Sigma }}{w}_j}=\frac{1+2+3+4+5}{1}=15;$

$t_2=\frac{\underset{m=1}{\overset{M}{\Sigma }}{v}_i}{\underset{n=1}{\overset{N}{\Sigma }}{v}_n}=\frac{3+5+2+6}{1}=16$

步骤3：由于t₁＜t₂,则所述工作流任务为IO密集型任务，进入步骤5；

步骤5：根据IO密集型任务的有向无环图的边权值进行所述有向无环图的更新和分解，得到若干个任务集，进入步骤6；

步骤5.1：如图8所示，计算工作流任务有向无环图从根节点到每一个叶子节点路径上边权值之和，分别为5和9；

步骤5.2：根据步骤5.1的计算结果选取出工作流任务有向无环图中边权值之和最大的路径为1-2-5，如图9所示，将选取的路径上的节点聚拢为一个根节点，将聚拢得到的根节点的权值更新为选取的路径各节点权值之和，即8，将更新后的根节点从工作流任务有向无环图中剔除，被剔除的根节点构成一个独立的任务集(1,2,5)；该任务集包含任务1、任务2、任务5，且计算数据量为8；更新后的工作流任务有向无环图中的节点均为独立的任务集；

步骤5.3：如图10所示，得到三个任务集，分别为(1,2,5)、(4)、(3)，各任务集计算 数据量分别为8、4、3；

步骤6：将得到的若干个任务集根据任务集的权值大小进行排序，并将计算资源根据其计算能力大小进行排序；

步骤7：根据步骤6的排序结果，将权值大的任务集分配给计算能力大的计算资源。

以上所述仅为本发明的较佳实施例，并不用以限制本发明，凡在本发明的精神和原则之内，所作的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。