一种改进的网格任务调度算法

常民, 仇磊(河海大学 计算机与信息学院,江苏 南京 211100)

一种改进的网格任务调度算法

常民, 仇磊
(河海大学 计算机与信息学院,江苏 南京 211100)

任务调度算法是网格计算中研究的热点问题之一。其中，Min-Min调度算法是一个简单、快速、有效经典的任务调度算法，但该算法存在着负载不均衡的缺陷。针对此缺陷，在Min-Min算法的基础上提出了一种新的任务调度算法，该算法定义了一个向量RT={rt1,rt2,…,rti,…rtn}，rti代表第i个资源已经分配任务运行时间之和，并根据未被调度的任务数所占的比例，把任务分成两部分调度，不同的部分使用不同的规则进行调度。最后对改进的算法进行了有效性和合理性验证。

网格计算； 任务调度； Min-Min算法； 负载均衡； 分段

0 前言

网格计算即分布式计算，是计算机领域中研究的热点问题之一，它研究如何把那些需要巨大的计算能力才能解决的问题分成许多小的部分，然后把这些小的部分调度给许多计算机进行处理，最后把各个计算机处理的结果整合起来得到最终结果[1-2]。在网格计算中任务调度是研究的重点，也是一个NP完全问题。网格任务调度的目的就是合理调度任务，以使完成的总时间尽可能的最小化，同时提高资源的利用率。最经典的任务调度算法Min-Min算法具有简单、快速、有效的特点，但该算法存在着负载不均衡的缺陷。针对Min-Min的这种缺陷，也有很多学者提出了基于Min-Min算法的各种改进算法[1-5]。

本文在分析Min-Min算法的基础上提出了一种新的任务调度算法，根据未被调度的任务数所占的比例，把任务分成两部分调度，不同的部分使用不同的规则进行调度。最后对改进的算法进行了有效性和合理性的验证。

2 Min-Min算法

Min-Min算法是一个比较传统、经典的任务调度算法，具有简单、快速、有效的特点，算法的思想是首先映射小的任务，并且映射到执行快的机器上。假设有m个需要执行的任务T={t1,t2…,ti,…tm}，n个可用的资源节点R={r1,r2,…,rj,…rn}。该算法的形式化描述如下：

(2)判断任务集T是否为空，不为空则执行(3)，否则跳到(8)。

(3)对任务集中的所有任务，求出它们映射到所有可用资源上的最早完成时间存储到向量MCT(Minimum Completion Time)中。

(4)根据向量MCT找出最早完成时间最小的那个任务ti和所对应的资源rj。

(5)将任务ti调度到对应的资源rj上，并将该任务从任务集合T中删除。

(6)更新其它任务在资源rj上的最早完成时间，即加上上次被分配任务的资源的就绪时间。

(7)转到(2).

(8)退出任务调度。

Min-Min算法总是优先调度预期完成时间最短的任务，并且总是将任务调度到完成该任务最快的资源上，已达到最终完成时间最短，但当任务集中存在一些长任务时，那么这些任务就不会及时得到执行，很容易导致系统的负载不均衡。例如，以文献[1]的数据为例，如表1所示：

表1 任务在各个资源上的预计完成时间

表1给出了5个任务，3个资源以及每个任务ti在各个可用资源rj上的预计完成时间形成的矩阵ECT，其中X表示该任务在该资源上无法运行。由Min-Min调度算法可以得出调度序列为：t3调度到r1上，t2调度到r1上，t4调度到r1上，t5调度到r2上，t1调度到r1上。可见资源r3一直处于空闲状态，而大部分任务在资源r1上运行，导致了负载的不均衡，而且运行时间较长。

3 改进的任务调度算法

针对Min-Min算法在网格任务调度的缺点，文中在Min-Min的基础上提出了一种新的任务调度算法。该算法根据没有分配到资源的任务数，即剩余任务数所占的比例，把整个任务的调度过程分成两部分调度，不同的部分使用不同的规则进行调度。

3.1 与算法有关的参数定义

假设网格环境中有m个独立的任务，T={t1,t2…,ti,…tm}，其中ti代表第i个任务；n个参与调度的可用资源，R={r1,r2,…,rj,…rn}，其中rj代表第j个可用资源。

定义2：设向量RT={rt1,rt2,…,rti,…rtn}，初始值都为0，其中rti代表第i个资源已经分配的任务在第i个资源上执行时间之和。

定义3：设向量RCL={rcl1,rcl2,…,rcli,…,rcln}，初始值都为0，其中rcli代表第i个资源可以运行的任务数。该向量中的值由ECT矩阵算的，即计算资源所在的列不为X的数。

定义4：设向量RCT=={rct1,rct2,…,rctj,…,rctm}，初始值都为0，其中rctj代表能够运行第j个任务的资源数。

定义5：设总任务数为m，没有分配到资源的任务数为k，则没有分配到资源的任务所占的比率为∝=m/k。

3.2 改进算法的描述

设在网格环境中，有m个独立的任务，n个可用的资源，改进算法的描述如下：

(1)初始化向量RT，RCL值都为0；

(2)for in任务集T；

(3)for in 资源集R；

(4)计算ECT矩阵；

(5)end for；

(6)end for；

(7)遍历ECT矩阵，计算向量RCL和RCT；

(8)遍历向量RCT，选择值为1的对应的任务，分配给相应的资源，并把该资源运行任务的完成时间加到相应的rti上，同时把该任务从任务集中删除并更新ECT矩阵；

(9)选取ECT矩阵中第一个没有分配过的任务，取完成该任务用时最小的资源运行该任务,同时将时间加到对应资源的rti上，同时把该任务从任务集中删除并更新ECT矩阵；

(10)while gt;=0.5

(11)if 还有资源没有分配过任务

(12)if 该任务在不同的资源上运行时间相同

(13)选择rcli最小的对应资源运行该任务，同时把该任务从任务集中删除并更新ECT矩阵；

(14)end if

(15)else if rcli相同

(16)选择rti值最小的运行该任务，同时把该任务从任务集中删除并更新ECT矩阵；

(17)end else if

(18)end if

(19)else

(20)选择rti值最小的运行该任务，同时把该任务从任务集中删除并更新ECT矩阵；

(21)end else

(22)end while

(23)while lt;0.5

(24)选择rti值最小的运行该任务，同时把该任务从任务集中删除并更新ECT矩阵；

(25)end while

4 实验验证

以表1为例，根据改进的算法可以得出：RCL={4,5,3}，RCT=={2,3,3,3,1}，调度的序列为：t5调度到r2上，t1调度到r1上，t2调度到r2上，t3调度到r3上，t4调度到r1上。与Min-Min算法的结果比较如图1所示。

从图1结果可知，本文改进算法完成任务的时间效率比Min-Min算法得到了有效提高，而且任务的在资源上的分配即负载均衡也得到了有效的改善。

5 结论

文中在对Min-Min算法的研究之后，在Min-Min算法的基础上提出了一种新的任务调度算法，并根据未被调度的任务数所占的比例，把任务分成两部分调度，不同的部分使用不同的规则进行调度。最后实验表明改进后的算法的有效性和合理性。

(a)

(b)图1 改进后的算法和Min-Min算法任务调度完成时间比较参考文献

[1] 赵英, 李栋. 改进的Min-Min网格任务调度算法[J]. 电子设计工程, 2012, 20(12):55-57.

[2] 罗宇平. 基于Min-Min改进后的网格调度算法[J]. 微电子学与计算机, 2009, 26(3).

[3] Fang Y, Wang F, Ge J. A task scheduling algorithm based on load balancing in cloud computing [M]//Web Information Systems and Mining. Springer Berlin Heidelberg, 2010: 271-277.

[4] Lee Y H, Leu S, Chang R S. Improving job scheduling algorithms in a grid environment[J]. Future generation computer systems, 2011, 27(8): 991-998.

[5] Wu M Y, Shu W, Zhang H. Segmented min-min: a static mapping algorithm for meta-tasks on heterogeneous computing systems[C]// Heterogeneous Computing Workshop, 2000. (HCW 2000) Proceedings. 9th. IEEE, 2000:375-385.

AnImprovedSchedulingAlgorithminGridComputing

Chang Min, Chou Lei
(School of Computer and Information, Hohai University Jiangsu, Nanjing 211100，China)

Task scheduling algorithm is one of the hottest issues in grid computing. Min-Min scheduling algorithm is a simple, fast and efficient classical task scheduling algorithm, but the algorithm has the defect of load imbalance. Based on the Min-Min algorithm, this paper proposes a new task scheduling algorithm. It defines a vector RT= {rt1, rt2… rti… rtn}, and rti represents the running time sum of the first i resource that have been allocated to tasks. And according to the proportion of the number of non-scheduled tasks, a task is divided into two parts to schedule, different parts use different rules for scheduling. Finally, the validity and rationality of the improved algorithm are verified.

Grid computing; task scheduling; Min-Min algorithm; load balancing; segmentation

常 民(1989-),男,硕士研究生,研究方向：数据挖掘.仇 磊(1992-),男, 硕士研究生,研究方向：数据挖掘.

1007-757X(2017)11-0030-02

TP301.6

A

2017.08.08)