基于负载平衡的任务调度算法

摘要:分布式计算中,一个好的任务调度算法不但要考虑所有任务的完成时间,使其值尽量小,同样要考虑到整个系统机器间的负载平衡问题。文章对异构计算环境下的原子任务调度算法进行了分析,针对Min-min算法可能引发的负载不平衡问题,结合分布式计算环境的特点,提出了一种适用于分布式计算的任务调度算法。

关键词:任务调度;完成时间;负载平衡

中图分类号:TP393文献标识码:A文章编号:1009-3044(2009)33-9269-03

An Algorithm for Tasks Scheduling Based on Laod Balance

YIN Lu

(Department of Computer Science, Huaiyin Instiute of Technology, Huaian 223001, China)

Abstract: In grid computing, a good algorithm for tasks scheduling should not only decrease the makespan of all tasks but also balance the load among the resources in the grid system. We first analyse the scheduling of meta-tasks in the heterogeneous environment, then according to the load imbalance question in the Min-min algorithm, propose an improved algorithm that suits to be used in the grid environment.

Key words: tasks scheduling; makespan; load balance

当今计算机技术已进入以网络为中心的计算时代,大量的应用都围绕着网络进行,对服务器的性能和可靠性提出越来越高的要求。例如,随着Internet的飞速发展和用户的剧烈增长,比较热门的Web站点会因为被访问次数急剧增长而不能及时处理用户的请求,导致用户长时间地等待甚至遭到拒绝,大大降低了服务质量。对于CPU密集型的应用,比如说带有数据库操作的Web服务,服务器性能瓶颈问题则更加突出。为了解决服务器的性能问题,分布式计算的概念就应用而生。

分布式计算研究如何把一个需要非常巨大的计算能力才能解决的问题分成许多小的部分,然后再分配给许多计算机进行处理这些小的部分问题,最后把这些小部分问题所对对应的计算结果综合起来得到最终的结果。由此可见,分布式计算所需的资源不仅有计算资源、存储资源还要有通信资源。那么如何使用这些资源高效的完成计算任务是分布式系统的研究重点之一。这就涉及到了计算任务的调度的问题。对于普通用户而言,它仅向分布式系统提交任务,但如何快速的完成这些任务,这就是调度程序要做的事情了。因此,分布式调度程序就是按照某种调度策略把用户提交的任务分配给分布式系统中的可用资源的重要模块,也是分布式计算的核心。

从上述分析可以看出,任务调度应该包括任务映射和调度两个方面。任务映射是逻辑地为每个任务匹配一个最合适的机器,以便最小化应用程序的执行时间或完成时间。任务调度则将任务传输到其映射的机器上运行。但本文所讲的任务调度主要强调的是前者即任务到资源的映射。以最小完成时间为优化目标的任务调度问题一直以来都是NP完全问题[1],针对这类问题科学家做了大量努力,但至今未能见到一个有效的解决办法,然而随着计算机技术的发展并考虑到计算机计算能力的提高,所以在工程实践应用中解决这类问题时,常采用贪心法又叫静态启发式算法,这类算法基本思想就利用计算机的快速性来进行穷举,但随着问题规模的增加其效能会降低太快,所以在实际应用中常采用动态启发式算法,针对于异构计算环境中原子任务的调度,动态启发式算法又分为在线模式启发式算法和批模式启发式算法。但这二个算法优点和缺点都比较明显,前者会导致负载不平衡,而后者会导致分配时间增加。为此,本文提出了一种算法来结合二者的优点从而保证任务调度的快速性和负载平衡性。

1 调度模型的建立

为了较好的描述分布式计算中的任务调度问题,我们采用数学模型的方法进行形式化的描述。分布式环境中资源的范围很广泛,它指加入到分布式系统中、所有可被共享的资源。所到达的任务可能是计算型也可能是数据存储型。为了描述问题的简单,本文所指的任务包括两类子任务:计算子任务和数据传输子任务。计算子任务是该任务中需要消耗计算资源的部分;传输子任务代表获得计算所需输入的数据通信即该任务中需要消耗存储资源和通信资源的部分。不考虑任务之间的依赖性。有如下定义:

1)参与调度的任务集合为T={t1,t2…tn},其中ti代表的是任务i。

2)参与调度的异构机器集合为H={h1,h2…hm},其中hj代表的是机器j。

3)定义任务ti在机器hj上的期望执行时间eij为机器hj在不考虑其它负载情况下执行任务ti所需要的时间。

4)定义任务ti在机器hj上的期望完成时间cij为任务ti映射到机器hj上执行完的时间。

5)定义机器hj的期望就绪时间为rj,则向量r存储了所有机器的期望就绪时间。

6)据(3)(4)(5)的定义有cij=rj+eij。

7)定义系统中有f个文件服务器或者数据仓库,S={s1,s2……sf}。

8)定义矩阵data,dataij表示子任务vi向文件服务器或数据仓库sj存取数据所需要的数据传输时间。

2 算法描述

2.1 Min-min

Min-min算法是一种实现起来很简单的算法,算法的执行时间也很快,具有较好的性能。该算法的目的是将大量的任务指派给不仅完成它最早,而且执行它最快的机器。算法的思想是首先映射小的任务,并且映射到执行快的机器上。执行过程为:计算要参与映射事件的任务集中每个任务在各个机器上的期望完成时间,找到每个任务的最早完成时间及其对应的机器;从中找出具有最小最早完成时间的任务,将该任务指派给获得它的机器;指派完成后,更新机器期望就绪时间并将已完成映射的任务从任务集合中删除。重复上面的过程,直到所有的任务都被映射完。该算法形式化描述如下:

假定T为所有未调度的任务的集合。

① 判断任务集合T是否为空,不为空,执行②;否则跳到步骤⑦;

② 对于任务集中的所有任务,求出它们映射到所有可用机器上的最早完成时间cij;

③ 根据②的结果,找出最早完成时间最小的那个任务ti和所对应的机器hj;

④ 将任务ti映射到机器hj上;并将该任务从任务集合中删除;

⑤ 更新机器hj的期望就绪时间rj;

⑥ 更新其他任务在机器hj上的最早完成时间;回到①。

⑦ 此次映射事件结束,退出程序。

Min-min算法完成一次映射事件的时间复杂度为O(n2m),其中n为一次映射事件需要完成映射的任务总数,m为可用的机器总数。

2.2 Max-min

Max-min启发算法非常类似于上面提到的Min-min启发算法。同样要计算每一任务在任意可用机器上的最早完成时间。不同的是Max-min算法首先调度大任务。任务到资源的映射是选择最早完成时间最大的任务映射到所对应的机器上。时间复杂度同Min-min一样也为O(n2m),其中n为一次映射事件需要完成映射的任务总数,m为可用的机器总数。

在Min-min算法中,每次都是选择小任务映射到执行快的机器上,这种映射会使得更多的任务映射到某一台或几台机器上,从而使得整个分布式系统中可用机器的负载不平衡。而Max-min算法同Min-min相反,它首先调度大的任务,一定程度上平衡负载。因此综合这两种算法的思想提出一种新的算法,该算法在对任务集合执行一次映射事件的过程中,会根据当前系统的负载平衡情况,动态的选择Min-min算法和Max-min算法中的一种来进行任务资源的映射。在本文中,称这种改进的新算法为MM算法。

2.3 MM算法

MM算法的思想借鉴于SA(Switching Algorithm)算法,SA是异构计算环境下,用来对任务进行在线模式映射的一种启发式算法。

分布式计算环境中,任一资源mi的期望就绪时间为ri,设所有机器的最大期望就绪时间为rmax,最小的期望就绪时间为rmin;设变量μ表示系统中机器间的负载平衡指数,μ=rmin/rmax,显然μ∈[0,1]。rmin=rmax=0,表明当前系统中所有机器都处于空闲状态,等待着任务的映射;μ=0,表明当前系统中存在处于空闲状态的机器;μ=1,表明当前系统中任务的分配基本处于平均状态。在算法中,为了轮回的调用Min-min和Max-min算法,设定了两个边界值rlow和rhigh。映射事件开始时,初始化变量μ=1。首先使用Min-min算法,当变量μ的值下降到rlow时,改用Max-min算法;当变量μ的值上升到rhigh时,在改用Min-min算法。如此轮回调用这两个启发式算法,直到此次映射事件结束。

另外Min-min算法和Max-min算法所执行的均是原子任务到资源的映射。在分布式系统中,一个计算任务所需要的数据往往是存放在另一个地方的数据库或数据仓库中,也就是说将一个任务分为计算子任务和数据传输子任务更为合理。但此处我们不将任务划分为更多的子任务,不考虑更多任务之间的依赖关系。对于分布式环境中包含计算子任务和数据传输子任务这样的任务,在调用Min-min启发算法或Max-min启发算法的过程中,需要同时考虑任务的数据传输和计算在存储资源和计算资源上的综合性能,所以需要修改这两个算法中求最短完成时间的部分。将传输和计算子任务看作一个整体,计算总的完成时间,并统一调度[7],即确定使之最快完成的一对(存储和计算)资源。

MM算法的执行过程如下:

① 初始化变量μ=1;初始化机器的期望就绪时间向量r;给变量rlow和rhigh设定初值;

② 定义变量μ1,该变量代表系统机器间负载平衡走向;初始化μ1

③ 任务调度集合T是否为空,T不为空,执行步骤③;否则到步骤⑦;

④ 若μ1rlow,调用Min-min映射算法进行任务的映射;

若μ1

若μ1>0,μ>rlow,调用Max-min映射算法进行任务的映射;

若μ1>0,μ=rhigh,改用Min-min映射算法进行任务的映射;

⑤ 更新向量r;

⑥ 更新变量μ和μ1,回到步骤③;

⑦ 算法结束。

2.4 算法分析

MM算法是在不影响Min-min的最小完成时间的前提下,为了降低由该算法所引发的系统中机器间负载不平衡问题而提出的。在MM算法中,对于每一任务在映射前,都要首先判断系统的当前负载平衡指数,最坏的情况下需花费O(m)(m为系统中计算资源总数),在每次映射中,调用Min-min或Max-min的时间复杂度均为O(mfn2),其中m为系统中计算资源总数、f为系统中存储资源总数。

3 结束语

本文介绍了异构计算环境下适用于原子任务调度的经典的批模式的启发算法:Min-min和Max-min。针对Min-min算法可能引发的负载不平衡,采用轮回调度Min-min和Max-min的策略,生成了一种新的映射算法MM。在分布式计算环境下,资源更是处于一种异构的环境,并且计算资源和存储资源等往往处于一种分布的状态。更多的任务不在是原子任务,而是包含计算和数据传输两部分。考虑任务的数据传输和计算在存储资源和计算资源上的综合性能,在MM算法中,修改了Min-min算法和Max-min算法中求最早完成时间的方法。对计算资源和存储资源进行统一调度,更好的适应于分布式计算系统。最后在Matlab 7的仿真平台下进行模拟实验,仿真结果表明该算法确实可行有效。当然对于任何启发式算法,其性能都受很多因素的影响。比如任务到达的速度,任务中长短任务的比例,任务中计算和数据传输比例等,所以值得改进的地方也还有不少,重点研究各个因素对MM算法性能的影响。

参考文献:

[1] 王磊,黄文奇.求解工件车间调度问题的一种新的邻域搜索算法[J].计算机学报,2005,28(5):60-67.

[2] 张德富,李新.求解作业车间调度问题的快速启发式算法[J].计算机集成制造系统-CIMS,2005(2):89-93.

[3] 谢志强,刘胜辉,乔佩利.基于ACPM和BFSM的动态Job-Shop调度算法[J].计算机研究与发展,2003,40(7):79-85.

[4] Casanova H.Simgrid:a Toolkit for the simulation of Application Scheduling[C]. Proceedings of the 1st International Symposium on Cluster Computing and the Grid (CCGRID'01), 2001.