动态负载调度

2024-05-09

动态负载调度（精选7篇）

动态负载调度篇1

摘要：随着网格计算技术的不断发展, 如何充分利用网络中广泛分布的动态计算资源越来越受到关注。为了充分提高并行计算中, 在多个动态计算资源上的具有任意可分特性的大规模应用的任务响应速度, 提出了一种探测缓存式动态调度算法PBDLS (Probing and Buffering Dynamic Load Scheduling) 。该算法利用探测技术对动态资源的运行状态进行实时跟踪, 根据预测结果自适应调整任务的分发量, 并提出任务预存策略, 用来最大限度地填补由于网络状态预测偏差导致的计算时间空闲时间, 从而全面提高任务执行效率。算法经2000多组仿真表明:在多种动态网络环境下, PBDLS算法的调度效率整体上优于现有的DA1、DA2和DLT算法, 并具有较好的稳定性。

关键词：任意可分负载,动态调度,并行计算

0引言

网格计算技术可以融合各种资源和服务, 在形成超大规模虚拟计算机的同时也将地域分布极广的人和组织联合起来, 为他们提供了一个资源共享、相互协作和交流的平台。要想获得一个高效运行的网格环境, 并行计算时任务调度效率的高低是关键因素之一。在并行计算领域, 处理的任务类型有所不同, 主要分为不可任意划分负载和任意可划分负载。与不可任意划分的任务相比, 后者可以被划分成相互独立的子任务, 由于这些子任务没有相互依赖的关系, 因此各个节点在处理任务的过程中不会产生额外的通讯开销。在图像处理、数据挖掘、信号处理等领域中, 很多应用[1,2,3]都具有任意可划分的特性 (在实际中存在最小的划分单元) 。

绝大多数任意可分任务的调度算法都是针对静态的计算资源, 这类资源的处理能力和网络带宽均是恒定的, 这些算法主要是按照一个特定的调度时序和调度轮数列出闭合式方程组, 通过求解方程组得到各个阶段调度器向每个节点分发的数据量大小, 使得各个节点在整个任务完毕之前均无空闲状态[4]。而对于动态资源, 由于其处理能力和网络带宽均是不可预知的动态变化, 因此很难提前确定一个恰当的调度时序。这方面的研究相对静态资源来说较少, 早期的有DA1、DA2算法[5], 近期主要是DLT算法[6]。但由于资源的动态特性导致调度算法不可能准确无误地预测各个节点上数据块的完成时间, 从而出现的通信竞争使得多个节点上会出现空闲时间, 因此调度效率会受到很大的影响。

本文提出一种针对动态资源的任意可分任务的调度算法PBDLS, 它利用探测技术来预测工作节点当前的状态, 并提出“任务预存”技术, 用来填补由于任务完成时间预测不准而在多个节点上出现的空闲时间, 与传统动态算法相比能够大大提高任务的调度效率。

1计算平台模型

本文研究的目标是由一个master和N个worker构成的星型网络拓扑计算平台, 如图1所示。对于一个可任意划分的任务, worker在处理完本轮所接收的任务后, 会给master返回结果数据, 而master以串行传输的方式发送、接收数据, 即同一时间内发送、接收操作不可重叠, master也不参与任务处理。对于任意一个worker, 计算时间可以与数据的发送、接收时间重叠。

2算法描述

2.1调度模型

对于一个worker, master到第i个worker的传输速率记为Bi;第i个worker向master返回数据的传输速率记为Ri;第i个worker的计算能力记为Si。在介绍PBDLS算法前, 需要先说明一下算法对于工作节点worker的计算能力和传输带宽的估测方法。如图2所示, 对于一个给定量的任务在一个worker上的处理过程分为任务分发、处理和回收三个节点, 则在算法需要记录几个变量:任务的启动时间STT (Start Time of Task) , 任务分发时消耗的通信时间DCT (Duration of Communication Task) , 任务所需的处理时间DPT (Duration of Processing Task) , 结果数据返回时间DRT (Duration of Returning Task) 。需要注意STT是一个时间点信息, 其余的的都是时间长度信息。

在实际应用中, 对于一个任务来说STT和DCT可以在主节点上分发任务时获得, DPT可以附加在返回数据中, 即数据返回完成后获得。由于DPT信息相对于返回数据来说非常小, 因此附加DPT对返回数据通信时间所造成的影响可以忽略。最后DRT信息在数据返回完成后可以获得。

对于一个已完成的大小为X的任务, 通过测量信息所获的的计算能力值为:

S $_{i}^{e}$ =X/DPTi (1)

所获得的从主节点到Pi的传输带宽为:

B $_{i}^{e}$ =X/DCTi (2)

所获得的从Pi到主节点的传输带宽为:

R $_{i}^{e}$ =X/RCTi (3)

2.2PBDLS算法

PBDLS算法分为两大阶段:初始探测预存阶段和多轮调度阶段。

初始探测预存阶段 master首先依次向每个worker发送两轮少量任务, 每个worker每轮接收的任务量相同, 记为η/2, 然后等待worker返回处理结果。该阶段主要是两个目的, 首先第一轮的少量任务是为了对各个worker进行性能探测, 即通过测量该任务的执行时间和数据传输时间可以获得当前worker的计算和传输能力的估测值, 利用这些估测值可以指导后续阶段任务的发送。第二轮少量任务的发送是为了填补第一轮任务在完成后进行数据返回时所留下的该worker上的计算空闲。接下来是多轮调度阶段。

多轮调度阶段该阶段master对请求返回数据的worker进行处理并向该worker发送一定量的新任务, 并期望该轮新发送任务在一个给定的时间τ内完成。则对于第i个worker, 其第j轮所接收的任务大小Li, j:

Li, j=τ/ (1/Bi, j-1+1/Ri, j-1+1/Si, j-1) (4)

另外, 由于所研究的模型中master不能并行收发数据, 因此master在处理完一个传输请求后, master的处理队列中可能有以下三种情况:有一个worker在等待返回数据;有多个worker在等待返回数据;没有worker等待返回。

对于第一种情况, master正常处理该请求, 并根据式 (4) 所计算出来的值向该节点发送新的任务。

对于第二种情况, master的处理队列这里采用了FIFO (First In First Out) 的结构, 因此优先处理先请求返回的worker。

对于第三种情况, 传统的算法处理都是master不做任何操作直到有请求到来, 而PBDLS算法在这种情况下会做以下处理:

设变量ntaski为第i个worker上当前的任务数, 如果ntaski≤1, 则让master再次向每个节点发送一定量任务, 发送量同该节点上轮的相同。如果ntaski>1, 则master不做任何操作。这样的处理方式同初始探测预存阶段的目的相同, 即利用多存一个任务来填补后续可能出现的计算空闲时间。同时由于ntaski条件的限制, 不会让某个worker缓存过多的任务, 从而造成负载过度失衡, 影响整体的调度效率。

图3给出了PBDLS算法在四个动态变化的worker上运行示例图。可以看到master首先顺次发送两轮任务, 其中第二个worker首先返回任务, 由于该节点上还有一个缓存任务, 所以该节点在返回第一轮的处理结果时继续处理缓存的任务, 因此填补了由于等待收发任务所形成的计算空闲, 提高了调度效率。

从上面对PBDLS算法的描述可以看出, 该算法是根据上一轮任务的发送和执行时间来获取估测值, 从而决定下一轮任务发送的大小, 同时在初始探测预存阶段和多轮调度阶段中按照一定的规则进行任务预存, 尽可能地填补由于任务收发而在各节点上形成的计算空闲时间, 进而大大提高了调度效率。

3对比算法

我们将用三种算法 (DA1、DA2和DLT) 与PBDLS算法比较。

DA1算法按照一个预先给定的访问时间值进行任务发送, 但是该算法需要在算法启动时预先知道动态计算资源当前的确切状态, 这与实际需求仍有些差距。

DA2算法是在每轮向各个worker发送固定大小的任务, 可以明显地看出, 由于没有自适应调整机制, 该算法在网络环境变化较大的时候其性能会快速下降。

DLT算法利用探测技术来预测网络中worker的工作状态, 把任务分多个阶段向各个worker发送, 尽量保证每个阶段的任务都同时完成。该算法在忽略任务返回量所占用的传输时间的情况下, 具有较好的调度效率, 否则, 由于返回时间的存在, 在一个特定阶段内, 任务只能一次返回, 从而会形成大量的计算空闲时间。

4实验结果与分析

利用SimGrid工具进行了仿真, 该工具可以自定义生成动态的网络环境, 即网络中的各个节点的计算能力及传输带宽都随机变化。比较算法是DA1、DA2和DLT算法。

仿真环境是一个具有10个worker的行星网络, 各个worker的计算能力与传输带宽随机变化, 其最大计算能力S=1任务/秒, 最大传输带宽B=R=30任务/秒, 总任务量Ltotal=2000, η=0.05, 数据返回比δ=1, 即一个任务执行完后得数据返回量与任务量相等。

用SimGrid生成两大组动态网络环境:低背景负载和高背景负载。低背景负载下, 计算能力和网络带宽的平均被占用率约为12.5%;高背景负载下计算能力和网络带宽的平均被占用率约为76.3%。

图4和图5分别给出了低、高背景动态负载下PBDLS与三种算法DA1、DA2、DLT的比较结果。两图中的纵坐标“相对处理能力T”是“理想完成时间”与调度仿真时间与的比值。“理想时间”指忽略所有传输时间时, 任务并行运行下的完成时间。设ϕ为表示某个后台负载率, 则理想完成时间大约为 $\frac{L_{t o t a l}}{(1 - ϕ) S Ν}$ 。两图中横坐标的参考调度轮数M定义如下:

$Μ = \frac{L_{t o t a l}}{L Ν}$ (5)

其中L为多轮调度阶段每个worker首次的发送量, N为worker的数量。由于对于任务可分任务的调度来说, 多轮调度的方式可以在各个worker之间形成计算时间覆盖传输时间的效果, 尤其是在静态多轮调度研究中, 适当的调度轮数下可以最大程度地进行时间覆盖, 从而整体上大大缩短收发任务时所形的计算空闲, 可以有效地提高任务执行效率。因此我们在这里引入参考调度轮数M, 即在动态环境下期望任务调度在几轮后结束, 通过调整M可以对算法进行更加全面的观察。

图4和图5中的每个点都是10组实验的平均值, 即每个点都按照对应的平均背景负载率生成10组动态网络环境进行仿真, 然后取其平均值的结果。从仿真实验结果可以看出, PBDLS算法整体上明显优于另外三种算法。同时PBDLS算法的, T随着参考调度轮数M的增加先上升后下降。这主要是因为在M较小时, 每个worker的初始发送量L较大, 这样PBDLS不能依靠足够的调度轮数去完成“时间覆盖”操作, 因此整体任务完成效率较低。M过大的时候, 由于L的取值过小, 虽然可以完成一些“时间覆盖”, 但是由于动态环境的不可预知性, 出现计算空闲的几率相应的也大大提高, 因此任务处理性能反会下降。

5结论

PBDLS算法针对动态网络环境, 通过探测技术对网络中的各个节点的计算能力和网络带宽进行跟踪, 同时提出“任务预存策略”, 尽可能地填补由于预测偏差而出现的计算空闲时间, 与同类算法相比, 大大提高了调度算法的效率, 且具有更加稳定的性能。

参考文献

[1]康雨, 闫相国, 郑崇勋, 等.医学可视化网格平台的设计与实现[J].西安交通大学学报, 2007, 41 (8) :1000-1002.

[2]Kwangil K, Robertazzi TG.Signature search time evaluation in flat filedatabases[J].IEEE Trans on Aerospace and Electronic Systems, 2008, 44 (2) :493-502.

[3]Hung T G, Robertzzi T G.Scheduling nonlinear computational loads[J].IEEE Trans on Aerospace and Electronic Systems, 2008, 44 (3) :1169-1182.

[4]Bharadwaj V, Ghose D, Man V, et al.Scheduling divisible loads in par-allel and distributed systems[M].Los Alemitos, USA:IEEE ComputerSociety Press, 1996.

[5]Drozdowski M.Selected Problems of Scheduling Tasks in MultiprocessorComputing Systems[M].Insytut InformatYki Plitechnika PoznanskaPress, 1997.

[6]Jia J, Bharadwaj V, Ghose D.Adaptive Load Distribution Strategies forDivisible Processing on Resource Unaware Mutillevel Tree Networks[J].IEEE Trans.Computers, 2007, 56 (7) :999-1005.

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

关键词：任务调度,完成时间,负载平衡

当今计算机技术已进入以网络为中心的计算时代,大量的应用都围绕着网络进行,对服务器的性能和可靠性提出越来越高的要求。例如,随着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为所有未调度的任务的集合。

(1)判断任务集合T是否为空,不为空,执行(2);否则跳到步骤(7);

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

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

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

(5)更新机器hj的期望就绪时间rj;

(6)更新其他任务在机器hj上的最早完成时间;回到(1)。

(7)此次映射事件结束,退出程序。

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)初始化变量μ=1;初始化机器的期望就绪时间向量r;给变量rlow和rhigh设定初值;

(2)定义变量μ1,该变量代表系统机器间负载平衡走向;初始化μ1<=0;

(3)任务调度集合T是否为空,T不为空,执行步骤(3);否则到步骤(7);

(4)若μ1<=0,μ>rlow,调用Min-min映射算法进行任务的映射;

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

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

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

(5)更新向量r;

(6)更新变量μ和μ1,回到步骤(3);

(7)算法结束。

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.

一种虚拟机负载均衡调度算法篇3

目前, 在商业发展和开源技术研究中有多种虚拟化架构, 其中包括剑桥大学的XEN。在Xen中, 多个虚拟机同时运行在相互隔离的虚拟环境中, 共享底层物理硬件, 包括处理器资源, 且各个虚拟机能够以接近物理计算系统的性能运作[2]。Xen中常用的三种CPU调度算法包括:BVT (借用虚拟时间算法) 、SEDF (最早截止时间优先算法) 和基于信任值算法 (Credit) , 三种算法各有不同的性能瓶颈, 因此, 如何实现高效调度成为虚拟化技术中面临的更大挑战。

专利CN102053858A中提出了一种虚拟机调度算法, 通过监测虚拟机的CPU调度以及状态标识信息, 解决了锁抢占问题, 从而在多处理器架构中实现更精确的可调度状态监测, 提高底层物理CPU资源的利用率[3]。华中科技大学的金海提出了一种Xen虚拟化环境中动态感知音频应用的CPU调度算法, 通过设置合适的时间片大小以及增加实时优先级等策略, 提高了Xen中音频应用的播放性能[4]。

本文提出了一种SMP (对称多处理器) 系统中的动态负载均衡调度算法 — 动态最早截止时间优先算法 (DLB_DEF) 来提高物理CPU利用率 , 从而减少空闲CPU。为了实现该算法, 我们设计了一种共享等待队列, 考虑到多处理器环境中cache和内存的同步关系, 使虚拟CPU在执行完任务之前都在同一个物理CPU上执行。仿真实验表明, 改进后的DLB_DEF算法能够优化系统性能, 并完全消除空闲物理CPU。

2SEDF算法以及SMP架构

2.1SEDF算法

在虚拟化计算环境中, 多个虚拟机通过分时调度策略共享物理处理器资源, 每个虚拟机就是一个域, 每个域对应一个或多个虚拟CPU (VCPU) [5]。因此, 如何公平高效地将物理CPU资源分配给多个虚拟机, 并使CPU有效利用率达到合理范围就是一个问题。

SEDF算法是一种基于最早截止时间策略的实时算法, 每个VCPU都会根据自身处理情况设置一个参数:最早截止期限 (deadline) , SEDF根据该时间参数决定VCPU的调度顺序[6], 而且VCPU的优先级根据deadline的改变而变化。SEDF算法将调度具有最早截止时间的VCPU, 从而保证虚拟机任务能及时完成。

每个域都设置一个三元组 (s, p, x) , 时间片s和周期时间p共同表示该域请求的CPU份额和时间, flag是一个boolean类型的值, 表示该域是否能够占用额外的CPU份额, 三个参数时间粒度的设置对调度的公平性影响很大。VCPU结构体的属性如图1所示, 每个PCPU包含2个双链表队列, 如图2所示。

runnableq队列中的VCPU都是处于running或runnable状态, 根据deadline参数排序, 队首的VCPU处于running状态, 而其他VCPU都处于runnable状态, 必须在deadline规定时间内执行调度;waitq队列中的VCPU处于runnable状态, 还未开始计时。

总之, SEDF算法可以通过参数动态配置VCPU的优先级, 因此在负载较大的实时系统中具有较高性能, 当系统负载较小时其CPU使用率可以达到100%, 然而, 随着负载逐渐增大, 一些任务就会发生时间错误, 错过截止期来不及处理而夭折。另外, SEDF算法不支持SMP架构, 从而不能实现对多CPU间全局负载均衡的控制。

2.2SMP架构

在SMP架构中, 多个处理器共享内存, 但每个处理器都对应一个私有cache, 大多数调度算法都遵循就近原则执行调度, 也就是说首选本地CPU来执行相应的任务, 从而提高cache命中率。当一个私有cache被修改后, 就要考虑内存和cache之间的一致性问题, 即不仅要确保修改后cache和相应内存之间的一致性, 而且要确保内存和其他cache之间的一致性。在执行过程中, VCPU可能会处于挂起状态, 比如时间片到或被其他事件阻塞, 此时VCPU虽然停止执行, 但是其对应的私有cache中还保存着运行时环境[7], 当处于挂起状态的VCPU被再次唤醒时, 使其在上次执行过的物理CPU上继续执行, 从而减少数据一致性产生, 即就近调度原则。

为了提高CPU资源的利用率, 就要重视cache和内存一致性带来的性能消耗问题。即VCPU在PCPU之间的频繁调度会产生严重的cache抖动, 进而使数据一致性问题产生额外的性能损耗, 严重降低CPU执行速度[8]。

3DLB_DEF算法的设计

通过上节中对SEDF算法的分析可知:SEDF在实时性环境中具有较好性能, 但不支持SMP架构, 如果一个CPU空闲, 它只能等待新的VCPU任务到来, 而此时其他CPU的任务量可能已经超载, 此时SMP架构中的多处理器系统的物理性能远低于具有相同处理器个数的系统。基于此研究结论, 本文提出一种基于SMP架构的虚拟机负载均衡调度算法——DLB_DEF算法。

在DLB_DEF算法中 , 共享队列share Waitq中的VCPU按照deadline参数进行排序, 且都处于runnable状态, 如图3所示为share Waitq结构体属性:

每个PCPU具有不同的等待时间权值, 即为对应runnableq队列中存放的VCPU的运行时间总和。当PCPU空闲时就从共享等待队列中调取VCPU任务, 同时, 考虑到cache就近原则, 将该VCPU任务上次执行过的PCPU记作pre_pcpu, 改进后CPU和VCPU的结构体属性分别如图4和图5所示:

假设物理机有M个可运行的PCPU, 如式 (1) 所示;式 (2) 为runnableq队列中的所有VCPU;式 (3) 为所有PCPU的weight集合;式 (4) 为weight集合中的最小时间权值。

改进后的动态负载均衡算法DLB_DEF与SEDF算法相同, PCPU都是优先调用具有最早截止期限的VCPU, 通过增加并实时更新共享等待队列share Waitq, 从而实现动态负载均衡。DLB_DEF算法如图6所示:

4仿真实验与结果

4.1仿真平台及环境配置

Schedsim是一种CPU调度模拟器, 提供了良好的接口, 能够实现先来先服务算法、短作业优先算法等多种常见的调度算法[9]。基于Schedsim, 本文设计并实现了SEDF算法和改进后的DLB_EDF算法, 并模拟了两种算法在不同数量处理器上的调度情况, 最后对两种算法调度的系统性能进行了分析和比较。

将SEDF和DLB_EDF中的一个VCPU任务记作一个进程, 由5个参数表示:进程ID号、优先级、就绪时间、执行时间和最早截止期限。为了满足仿真实验的需要, 假设PCPU个数最大为6, 配置5个进程池, 分别包含10、20、40、60、80个进程, 仿真实验步骤如下:

步骤1:创建的进程池至少符合以下要求:12个就绪时间相同而最早截止期限不同的进程, 22个就绪时间和最早截止期限都相同的进程, 32个执行时间不同而就绪时间和最早截止期限相同的进程, 42个分别具有不同的就绪时间、执行时间和最早截止期限的进程, 5就绪时间与执行时间之和大于最早截止期限的2个进程, 6将所有进程的最早截止期限设置为与优先级成反比。

步骤2:进程池中的所有进程入队。

步骤3:配置PCPU个数, 选择调度算法和调度模式。

步骤4:运行模拟器。

以下实验结果是以包含40个VCPU的进程池作为参考, 对每个进程池分别做10组测试, 并取10组数据的平均值。

4.2仿真结果分析

当两个算法的进程都完成时, 如图7、图8、图9分别为系统吞吐量、平均周转时间和平均应答时间的比较结果。

通过图7-9我们可以看到, 当PCPU个数为1时, 由于需要考虑cache就近原则, 因此DLB_DEF的系统吞吐量和任务完成率比SEDF算法略小, 但是平均周转时间以及平均响应时间比SEDF略大;当PCPU个数增多, 即在支持SMP架构的多处理系统中 , 具有负载均衡策略的DLB_DEF算法的各个性能指标都略超过SEDF, 系统吞吐量和任务完成率逐渐增大, 平均周转时间以及平均响应时间却逐渐减小。特别地, 当DLB_DEF和SEDF的系统吞吐量具有最大差值时, PCPU个数等于4, 即在PCPU为4时DLB_DEF算法具有最优性能。当PCPU个数继续增大为6时, SEDF算法由于空闲PCPU的出现而导致多种系统指标性能降低, 而此时, 在DLB_DEF算法中, 虽然PCPU个数增多, 但由于共享等待队列的互斥性, PCPU调用任务时等待互斥锁的解锁时间逐渐增大, 同时, 共享等待队列的更新也要占用更多时间, 因此, DLB_DEF算法的系统吞吐量、任务完成率、平均周转时间以及平均响应时间也逐渐达到平稳状态。

当PCPU个数逐渐增多时, 即具有更多处理器来执行系统任务时, SEDF和改进后的DLB_DEF算法的任务完成数和任务完成率都逐渐增大, 但是两者的完成率都达不到100%, 即有些VCPU由于错过截止时间而错过执行的机会, 但是DLB_DEF在总体上完成量比SEDF多。

5总结

本文主要对SEDF算法进行分析, 针对其不支持SMP架构的不足, 提出一种动态负载均衡算法DLB_DEF。该算法设计了一个共享等待队列存储VCPU任务, 并根据cache就近原则和PCPU的等待时间权值, VCPU可选择最优PCPU执行其任务。DLB_DEF算法不仅可以降低cache抖动带来的性能损耗, 还可以通过获取PCPU的最小等待权值来增大PCPU使用率。最后, 在Schedsim仿真环境中模拟SEDF和DLB_DEF, 仿真结果表明, DLB_DEF在系统吞吐量、平均周转时间和应答时间、进程完成率等性能指标上都略优于SEDF算法。目前仅在模拟环境中执行DLB_DEF算法, 下一步任务要将DLB_DEF嵌入到XEN源代码中并运行在真实虚拟环境中。

摘要：基于XEN的CPU调度算法已经广泛应用于很多实时系统中, 但是在多处理器系统中却很难实现负载均衡。本文提出一种虚拟机环境中支持SMP架构的CPU调度算法, 该算法在CPU调度算法中增加共享等待队列, 并基于cache缓存和内存的一致性问题, 使得虚拟环境中的多个处理器根据自身任务处理情况, 动态调整共享等待队列中VCPU的执行顺序, 这样就可以避免处理器空闲, 提高处理器使用率。通过仿真实验, 证明该算法支持CPU全局负载均衡, 可以避免cache和内存一致问题所产生的性能降低, 提高系统吞吐量, 降低VCPU执行的平均周转时间和响应时间, 使处理器资源得到充分利用。

关键词：XEN,虚拟机,CPU调度,SMP,负载均衡

参考文献

[1]怀进鹏, 李沁, 胡春明.基于虚拟机的虚拟计算环境的研究与发展[J].软件学报, 2007, 18 (8) :1016-1026.

[2]Paul Barham, Ian Pratt, Keir Fraser, et al, “Xen andthe art of virtualization, ”In SOSP’03:Proc of the nineteenth ACMsymposium on Operating systems principles, New York, ACM, 2003, 15:164-177.

[3]金海, 吴松, 石宣化, 等.一种虚拟CPU调度方法[P].中国专利, 102053858, 2011-05-11.

[4]Huacai Chen, Hai Jin, Kan Hu, et al.“Adaptiveaudio-aware scheduling in Xen virtual environment, ”In AICCSA’10:Proc of the ACS/IEEE International Conference on ComputerSystems and Applications.USA, IEEE Computer SocietyWashington, 2010:1-8.

[5]Hyunsik Choi, Saeyoung Han, Sungyong Park and EunjiYang, “A CPU Provision Scheme Considering Virtual MachineScheduling Delays in Xen Virtualized Environment, ”TENCON’09:2009 IEEE Region 10 Conference.2009:1-6.

[6]Xinjie Zhang, Dongsheng Yin, “Real-time Improvementof VCPU Scheduling Algorithm on Xen, ”In CSSS’11:ComputerScience and Service System.2011:1506-1509.

[7]常建忠, 刘晓建.虚拟机协同调度问题研究.计算机工程与应用, 2011, 47 (6) :38-41.

[8]Min Lee, A.S.Krishnakumar, P.Krishnan et al.“Supporting Soft Real-Time Tasks in the Xen Hypervisor, ”InVEE'10:Proceedings of the 6th ACM SIGPLAN/SIGOPSinternational conference on Virtual execution environments[J].New York, ACM, 2010, 45:97-108.

动态负载调度篇4

LVS集群是现有集群解决方案中应用最广泛的一种,也是研究的重点,它可以建立在已有普通服务器的基础之上,它的通用结构如图1所示,是一组服务器通过高速的局域网或者地理分布的广域网相互连接,这组服务器就是提供服务的真实服务器,用户看不到提供服务的这组真实服务器,而只能看见一台作为调度器(调度器上配置有虚拟IP地址,简称VIP)的服务器,该调度器负责接收大量客户端计算机的请求,并决定哪个集群中的服务器可以应答用户的请求。与计算机通常在网络上交换数据包的方式相同,客户端计算机、调度器和真实服务器是通过IP地址彼此进行通信的。在客户端看来,访问集群系统提供的服务就像访问一台高性能服务器一样。由于调度器进行调度的过程是在Linux操作系统的内核中完成的,并且调度器上并不提供真实的服务和信息,只是一个虚拟的服务,因此简称为LVS(Linux Virtual Server)。

2 常用4种负载均衡调度算法及核心思想

在LVS集群中进行负载均衡的核心软件,就是运行在调度器上的IPVS软件,而IPVS软件中已实现了8种调度算法,其中目标地址散列调度算法(简称DH)和源地址散列调度算法(简称SH)这2种负载均衡算法主要是用在防火墙集群中的,而基于局部性的最少链接算法(简称LBLC)和带复制的基于局部性最少链接算法(简称LBLCR)这2种负载均衡算法主要是用在Cache集群中的,不是本文研究的重点。本文主要研究常用的4种调度算法的核心思想,并深入分析常用4种调度算法的优缺点。

1)轮叫调度算法(Round-Robin Scheduling,RR)

RR算法存放在ip_vs_rr.c文件中,就是当调度器收到请求后,在它的服务器列表中挑出下一台服务器,在无穷的循环中遍历它们。

2)加权轮叫调度算法(Weighted Round-Robin Scheduling,WRR)

WRR算法存放在ip_vs_wrr.c文件中,就是基于集群节点可处理多少负载来给每个集群节点配置一个合适的权重或等级,即权值Wi,然后将权重与循环技术一起使用,以便选择收到新请求时要使用的下一个集群结点,而不管当前的活动连接数。具有权重2的服务器将收到具有权值1的服务器的2倍的新连接数,如果将服务器的权值Wi为0,就不在允许服务器接收任何用户请求。

3)最小连接调度算法(Least-Connection Scheduling,LC)

LC算法存放在ip_vs_lc.c文件中,就是当调度器收到请求后,调度器查看活动和非活动连接数量,将用户的请求发送给连接数最小的那台服务器。

调度器上计算当前连接数的具体方法是:对于每一个集群节点,调度器将集群节点目前正在服务的活动连接数的数量乘以256,然后加上它不活动的连接数(即最近使用的连接数),来得到每个节点的总连接数。

4)加权最小连接调度算法(Weighted Least-Connection Scheduling,WLC)

WLC算法存放在ip_vs_wlc.c文件中,就是将最小连接方法和每个服务器的权重Wi结合起来,再进行服务器的选择。当前每个节点总连接数的计算方法如上所示。如果将服务器的权值Wi为0,就不在允许服务器接收任何用户请求。

加权最小连接调度的核心思想如下所示:

基本参数定义:假设有一组服务器S={S0,S1,...,Sn-1},W(Si)表示服务器Si的权值,C(Si)表示服务器Si的当前连接数。调度的具体过程:当前的新用户请求会被发送服务器Sm,当且仅当服务器Sm满足以下条件:判断条件可以简化为:C(Sm)*W(Si)

3 常用4种负载均衡算法的分析

LVS集群中已有8种负载均衡算法,但在实际负载均衡算法的应用中,RR、WRR、LC和WLC是经常使用的几种负载均衡算法。

LVS集群中常用的负载均衡算法包括两大类,第一:静态负载均衡算法:它不考虑每台服务器当前实际的负载情况,而只是根据事先定好的调度策略进行任务请求的分配,将用户请求轮转依次分配给各服务器,并且考虑到了权值W(Si),保证权值为0的服务器不被调度,该算法实现简单且容易配置,但不能真正保证各服务器负载均衡。RR和WRR就属于静态负载均衡算法。第二:动态负载均衡算法:动态算法将服务器当前实际的连接数作为实际的负载情况,同时考虑到各服务器的处理能力并赋以相应的权值W(Si),将用户的请求发送给连接数最小或者加权连接数最小的后台服务器,充分利用每台服务器的系统资源,从而减小用户请求服务的响应时间。LC和WLC就属于动态负载均衡算法。

下面来详细地分析一下这4种常用负载均衡算法的优缺点。

1)RR算法

该算法简单,它无需记录每个服务器当前总连接数,是一种静态算法,假设所有服务器处理性能均相同,但没有考虑服务器的当前连接数等负载情况和响应速度,不适用于集群中服务器处理性能差距较大的情况,而且当用户请求服务所需系统资源比较多时,该算法容易导致服务器间的负载不平衡。

2)WRR算法

该算法简单和高效,也无需记录每个服务器当前总连接数,是一种静态算法,WRR算法是在RR算法的基础上,并考虑了服务器的处理性能差异,以权值W(Si)表示各服务节点的处理能力,但仍然没有考虑服务器的当前连接数等负载情况和响应速度,而且当有些用户请求服务所需资源较多时,单独的WRR算法容易导致服务器间的负载不平衡。

3)LC算法

LC算法是动态的均衡算法,它要记录每台服务器当前总连接数量,是一种动态算法,比RR算法和WRR算法的负载均衡效果要好一些。

在调度的过程中,以服务器的当前连接数作为衡量服务器负载的关键指标,但是,在各个服务器处理性能差距比较大的情况下,该算法的负载均衡效果不理想,同时,该算法只用当前连接数来衡量服务器的负载情况,没有全面考虑服务器的负载情况,当某些用户请求所需的系统资源比较多的情况下,也会使得集群系统的负载不均衡。

4)WLC算法

WLC算法是动态的均衡算法,它要记录每台服务器当前总连接数量,是一种动态算法,是常用4种负载均衡算法中负载均衡效果最好的一种算法。该算法既克服了某些调度算法只适用于各节点服务器处理能力相差不大的集群系统中,也考虑了各个服务节点的实际性能的差异,以权值W(Si)表示服务节点的处理能力,从而在各个服务结点之间合理的分配负载,是负载均衡效果最好的一种动态负载均衡算法。但是仍然存在着以下几个不足的地方:

(1)以当前连接数来表示每台服务器节点的综合负载不够精确

当前连接数并不能较准确的表示服务器节点的负载情况,因为用户请求的服务所需的时间和所要消耗的服务器资源千差万别,它依赖于很多因素。当有些用户的连接请求需要较多的系统资源时,比如会占用大量的内存和CPU资源,那么仅以当前连接数来衡量服务器节点的负载不够全面和精确。

(2)对每台服务器权值W(Si)的设置不够科学和灵活

WLC算法中用到的权值是管理员根据每台服务器的实际硬件配置为每台服务器指定的一个固定的整数值,是由管理员手动设置的,只能依靠经验作大概的估计,仅凭主观判断设定的权值不一定能很好的反映服务器节点的实时处理能力,且不能在调度的过程中动态地修改该权值。

通过上面详细的分析,可以发现,动态负载均衡算法要比静态负载均衡算法更有实用性,负载均衡效果更好,而在实际的应用中WLC算法是LVS集群中默认的算法,也是这4种负载均衡算法中效果最好的算法,本文就是在WLC算法的基础之上进行改进,即集群中的服务器需要每隔一个固定的周期向调度器汇报自己的负载情况,调度器然后根据负载情况动态地调节每台服务器的权值,再将新的权值和已有的WLC算法结合起来,选取负载最轻的服务器节点处理用户的请求。

4 结束语

通过上面对每一种算法的分析后,发现每种算法都有它适合的实际情况,因此采用集群搭建所需的高性能网络服务时,可以根据已有的条件和实际的情况选择合适的负载均衡算法,只有采用适合自己情况的算法才能达到理想的负载均衡效果。

参考文献

[1]郑灵翔,刘君尧,陈辉煌.Linux下的负载均衡集群LVS实现分析与测试[J].厦门大学学报:自然科学版,2002,41(6):726-730.

[2]刘玉艳,沈明玉.LVS负载均衡技术在网络中的应用[J].合肥工业大学学报:自然科学版,2007,30(12):1592-1595.

[3]陈超.利用LVS中的IP负载均衡技术建立可伸缩性网络服务[J].四川理工学院学报:自然科学版,2006,19(4):81-85.

动态负载调度篇5

云计算是当前计算机技术发展的前沿, 而负载均衡问题则是云计算相关研究的一个热点问题。Zhang bo, Gao ji[1]等通过分析对比常见的集群负载均衡算法, 提出针对云计算中服务器、云之间的云负载均衡算法CBL, 该算法在负载均衡度和任务加载时间上都有良好的表现, 但是复杂度较高;Yi Zhao和Wenlong Huang[2]提出了基于虚拟机的实时迁移的分布式负载均衡算法;Zehua Zhang和Xuejie Zhang[3]采用Max-Min负载均衡机制思想, 最大负载量与最小负载量之差小于某一值, 再结合复杂网络理论, 提出了基于复杂网络的负载均衡算法, 但是本文中应用的Max-Min算法思想只能使资源负载大致均衡, 因此对实现负载均衡的考虑不够全面。

任务调度是云计算的核心技术, 其调度算法性能的优劣对系统整体运行效率有重要的影响。众所周知, 云计算的任务到资源的映射在大部分情况下都是一个NP问题, 研究云计算任务调度算法对提高整个云计算系统的性能有着重要的意义。任务调度[4]是把不同的任务以最合理的方式分配到相应的资源上去完成。任务调度算法的好坏直接影响到整个云环境的工作性能。本文研究批模式下的启发式调度算法, 并假定各个任务相互独立, 经典的启发式调度算法包括Minmin算法[5]、Sufferage[6]算法、GA算法和SA算法。

Min-min调度算法总是把最早完成时间最小的任务分配到相应的资源上, 以尽量缩短任务的总完成时间, 但是该算法会导致系统的负载不均衡[7]。Sufferage算法先计算出每个任务在所有资源上的最早完成时间的最小值a和次最小值b的差值即sufferage值, 然后通过比较选择Sufferage值较大的任务分配到相应的资源上, 该算法的不足之处就是增加了算法本身的时间复杂度。文献[11为了缩短任务的总完成时间提出了一种具有双适应度的遗传算法[8]DFGA (Double-Fitness genetic algorithm) , 但是该算法的运行时间远远大于MinMin算法和Sufferage算法。文献[12]提出了一种改进蚁群算法[9]的云环境任务调度算法, 该算法跟DFGA调度算法同属于智能启发式调度算法, 它们都具有运行时间过大的缺点。在云计算任务调度算法中, 都是以任务的执行时间跨度 (makespan) 、资源负载均衡度、任务平均完成时间、任务完成效率等指标作为优化目标, 为了弥补以上所提到算法的不足之处, 完成任务调度的优化目标, 本文提出了一种基于系统整体负载均衡与最小完成时间 (LB-ECT) 算法。

1、LB-ECT算法

本算法的基本定义如下:

定义1 m个相互独立的任务的集合, T={t1, t2…, tm}。

定义2 n个计算资源的当前负载的集合, L={l1l2, …, ln}。

定义3 m个任务在n个资源上的预测最小完成时间 (Predict the Minimum Completion Time, PM-CT) 为m*n矩阵:

其中, 元素cij表示任务ti在资源rj上的预测最小完成时间。

在云计算的任务队列中, 每个用户都希望自己的任务能够在预期的时间内执行完成, 而从任务的调度方面, 最好的结果是把每个任务都调度到预测最小完成时间的资源上, 兼此资源是负载最小的。本算法就是从系统的整体负载均衡与任务的总的完成时间尽量缩短的角度出发, 通过下面的公式使任务调度在二者之间寻求到一个互补。首先我们应初始化矩阵PMCT, 同时还要初始化集合L, 然后遍历矩阵中的所有元素找出一个最小的预测最小完成时间值

其中, 1≤i≤m, 1≤j≤n。

在集合L中找到一个最小的负载

本算法在任务调度过程中, 通过以下公式来选择任务与资源的配对:

其中ljcmin为矩阵PMCT包括的所有元素中数值最小的执行时间对应的资源的负载值, cijlmin为集合L中负载值最小的资源上的任务所对应的预测完成时间。

若最后的比较结果公式 (3) 成立, 那么就说明两个任务的最小完成时间差别比其所分配的资源的负载的差值更大。那么就选择从PMCT矩阵中得到的最小的预测最小完成时间相应的任务和资源进行配对。

若最后的比较结果公式 (4) 成立, 那么就说明两个任务所分配的资源的负载比其最小完成时间差别比其的差值更大。那么就选择从集合L中选择负载最小资源并从矩阵PMCT中找到与其对应的预测最小完成时间的任务进行配对。

LB-ECT算法流程图如图1所示:

PMCT矩阵和集合L已知, 集合T非空, 根据以上定义, 下面是算法流程的详细步骤:

(1) 初始化集合T和集合L;

(2) 初始化矩阵PMCT;

(3) While T非空, 循环执行步骤 (4) ～步骤 (7) ;

(4) %For i=1 to n, For j=1 to m, 在PMCT矩阵中找到最小完成时间的任务cmin, 并在集合L中找到其所在资源上对应的负载ljcmin;

(5) %For i=1 to n, 在集合L中找到最小负载min, 并在PMCT矩阵中找到其对应的资源上最小完成时间任务cijlmin;

(6) %计算公式 (3) ;

(7) If 最小完成时间的任务分配到其对应的资源上

Else把最小负载资源上的最小完成时间的任务进行配对。

2、性能分析与仿真实验

在多任务、多资源的云计算仿真环境中, 分别采用Min-min算法、Sufferage算法和LB-ECT算法对任务进行调度。通过收集仿真实验数据, 分析各个算法的性能, 我们验证了LB-ECT算法在负载均衡, 任务的总完成时间方面的优越性。其中, 负载均衡度按下式计算, 表示各个资源的均衡负载的指标, 数值越小表示负载越均衡。

2.1 负载均衡度

图2给出了资源数为30时, 在不同任务数下进行20次实验得到的负载均衡度的平均值。

由图2可知, 三种算法的负载均衡度随着任务数的增多而减少, 即负载均衡性能都有提升。LB-ECT算法的负载均衡行略高于Sufferage算法, 而远高于Min-min算法。如上所述, 实验验证了LB-ECT算法在负载均衡方面还是有优势的。

2.2 任务总完成时间

图3给出了资源数为30, 在不同任务数下进行20次实验得到的任务总完成时间值。

由图3可知, 三种算法的总完成时间随着任务的增多而增多, 但是LB-ECT算法的总完成时间大多数情况总是比Sufferage算法少, 而Min-min调度算法的总完成时间总是比前两者消耗的要多。实验验证了LB-ECT算法在缩短任务的总完成时间方面有很大的优越性。

3、结论

本文研究了多种网格任务调度算法, 剖析在Min-min调度算法和Sufferage调度算法的优缺点的基础之上, 设计了适用于云计算环境的LB-ECT算法, 一种基于Min-min算法和Suffrage算法的优点提出基于系统整体负载均衡与最小完成时间 (LB-ECT) 算法。在下一步工作中, 笔者将在设计任务调度策略时, 加入针对资源异常情况进行应急处理的策略, 并在其中加入更多QoS方面的考虑, 从而优化现有算法。

摘要：本文针对当前云计算系统负载不均衡和任务完成效率有待提高的问题, 提出了一种基于系统整体负载均衡与最小完成时间LB-ECT算法。根据云计算环境下资源需求动态变化, 利用任务在虚拟机上执行时间的预测进行任务到虚拟机上的分配、调度, 优化系统的整体效率。采用云计算仿真平台CloudSim对本算法进行仿真实验与分析, 实验仿真结果表明, LB-ECT算法能够有效提高系统的整体负载均衡能力, 明显缩短任务的总完成时间。

动态负载调度篇6

关键词：HSDPA,分组调度算法,正比公平调度算法,系统负载,NS2

1 引言

根据GSA(全球移动供应商联盟)2007年11月的最新统计,全球71个国家已经部署了154张3.5G HSDPA商用网络,我国目前正在测试TD-HSDPA技术。HSDPA是3GPP在R5标准[1]中为了满足上下行数据传输不对称的需求而提出的技术,相比于W-CDMA R99引入了高速下传共享信道(HS-DSCH:High Speed-downlink Shared Channel)。HSDPA把功能实体(包括调度算法)置于Node B(基站),并采用AMC(Adaptive Modulation and Coding) 、HARQ(Hybrid Automatic Retransmission Query)和快速调度等为核心的关键技术,下行传输速度在没有信道编码的情形下可达到14.4Mbit/s, 较W-CDMA R99版的2Mbit/s高出许多,延迟现象亦因功能实体置于NoteB和采用很短的TTI(2ms)而大幅降低。NodeB中的调度算法是发挥HSDPA系统性能的关键技术。接下来将对HSDPA中的调度算法进行仿真和研究, 并提出了一种依赖负载的正比公平调度算法。

2 经典的无线调度算法

分组调度的基本问题:网络节点中的调度器以比较低的计算复杂度对存放在队列中的多个业务流分组按照某种调度规则进行调度,以满足各个业务流的QoS要求。对于分组调度算法,一方面考虑系统吞吐量,用户公平性等指标;另一方面要考虑算法实现的复杂度,特别是在HSDPA系统中。

经典的无线分组调度算法有轮询算法(RR: Round Robin)、最大载干比算法(Max C/I: Maximum Carrier to Interference)和正比公平算法(PF: Proportional Fair)。

2.1 轮询算法(RR)

RR算法假设所有用户具有相同的优先级,保证以相等的机会为系统中所有用户轮流循环分配无线传输资源。每个用户对应一个队列以存放待传数据,在调度时,非空的队列而且信道状况可以支持数据传输的队列以轮询的方式接受服务以传送数据。其基本思想是,以牺牲吞吐量为代价,公平地为系统内的每个用户提供资源。RR算法实现简单,但由于RR算法不考虑不同用户无线信道的具体情况,虽然保证了用户时间公平性,但吞吐量是极低的。通常RR调度算法的结果被作为时间公平性的上界和算法性能的下届。

2.2 Max C/I算法

Max C/I调度算法对所有待服务UE按照其接受信号C/I进行排序,挑选具有最好链路条件的用户赋予最高的优先级,然后发送数据。所选用户:

$k = \arg \max {(C / Ι)_{i} (t)}$

Max C/I调度算法利用"多用户分集效应"来实现系统容量最大化。无线信道状态好的用户优先级高,使得数据正确传输的几率增加,错误重传的次数减少,整个系统的吞吐量得到了提升。

虽然Max C/I能够适应无线信道的时变性,但是完全不考虑用户间的公平性。在此算法下,距离Node B 近的UE由于信道质量好会频繁得到服务,而远离Node B的UE由于C/I传输机会大大减少,甚至得不到传输的机会。这种调度算法的系统容量可以作为其它调度算法的上届和公平性的下届。

2.3 正比公平调度算法(PF)

以上两种算法只关注了系统性能的一个方面,由高通公司提出的应用在CDMA2000 1x系统[2]中的PF算法兼顾了用户间的公平性和系统的吞吐量。PF算法给小区内每个用户赋予一个优先级,然后挑选优先级最高的用户进行服务。优先级计算和所选用户如下:

$k = \arg \max (\frac{R_{i}^{n}}{U_{i} (n)})$

式中R $_{i}^{n}$ 是第i个用户在调度时隙n时信道质量所能支持的传输速率,Ui(n)是时隙n前某个时间窗内用户i所获得的平均传输速率。随着用户速率的提高,其优先级会降低,而没有得到服务的用户平均速率会降低,其优先级会提高,从而获得传输机会。PF算法是目前公认比较好的算法。

在NS2 + EURANE的平台上,上述三种调度算法在HSDPA系统下性能比较如表 1所示。仿真场景和系统参数见第四节。各调度算法的性能曲线见图 2和图 3。

接下来的仿真结果表明,在HSDPA系统中,Max C/I算法完全根据时变的信道状况进行用户调度,可以最大限度地提高频谱利用率,系统吞吐量最高,缺点是用户间的公平性最差。特别是远离基站(或信道质量较差)的用户在负载较大的情况下,根本得不到系统服务。从图 3可以看出,当用户数多于12个时,这类用户的平均速率就降为0了。

实验结果表明RR算法完全不考虑用户间的信道差异,所得到的吞吐量最低。值得指出的是,在HSDPA系统下,RR算法调度结果的公平性并不是最好的,而公平性最好的是PF算法(见图 3)。这种现象可以解释为:RR算法只是保证调度机会公平,但不能保证调度结果公平。在HSDPA系统中,由于采用了AMC技术,使得信道质量高的用户可以获得高的传输速率。所以在同样的时隙资源下,基站附近的用户的传输速率就要高于远离基站的用户。

仿真结果还表明PF调度算法综合考虑了用户的信道条件差异和对于公平性的要求,在吞吐量和公平性之间取折衷,系统吞吐量较高,用户公平性也相对最好,非常适用于HSDPA的调度算法。

3 正比公平调度算法的不足与改进

当不同用户经历相似的信道条件时,利用正比公平调度算法得到的调度结果很公平。为方便讨论,现定义信道质量统计平均较好(基站附近或传播环境好)的用户为一类用户(UE1),信道质量统计平均较差(远离基站或传播环境差)的用户为二类用户(UE2)。在HSDPA系统中,依据正比公平调度的结果,UE1会比UE2获得明显高的平均速率。图3所示的速率曲线也证实了这一点。

如今,虽然移动用户的移动性比较大,但是相当比例的移动用户多数情况下只在相对固定的两三个地点(家里、工作场所或学校)小范围移动。这两三个地点的信号质量经常有明显的统计意义上的差别,不同的用户很明显地归属于一类用户或二类用户。移动用户很难接受这种付费相同,平均速率差别明显的无线接入服务。

为弥补PF算法的公平性缺失,自适应比例公平(APF)算法[3]和DRC(Data Rate Control)准则[4]等改进算法被提出来。在APF算法中,用户的优先级定义如下:

$Ρ_{i} (t) = \frac{R_{i}^{C_{i}} (t)}{U_{i}}$

Ci是用户i的控制参数,过数十个TTI更新一次。更新的计算准则如下:

$C_{i} = {\begin{cases} C_{i} + Δ c i f [\frac{R_{i}}{U_{i}} - \frac{1}{Ν} \sum_{j = 1}^{Ν} \frac{R_{i}}{U_{i}}] ＜ - ε \\ C_{i} - Δ c i f [\frac{R_{i}}{U_{i}} - \frac{1}{Ν} \sum_{j = 1}^{Ν} \frac{R_{i}}{U_{i}}] ＞ ε \end{cases}$

Δc的选择依赖于收敛速度的选择和收敛值附近的波动。 DRC准则相当于APF中的Ci统一取一个常数C。

APF算法可以改善公平性,然后公平性的增强是以牺牲约10%的系统吞吐量为代价的。另外,APF算法中额外的监控更新模块需要对每个用户进行监控进而更新用户控制参数,APF算法在算法结构上比较复杂,而且Ci和Δc的值也不易选择。DRC准则无差别对待每一个用户,除了一些特定情景外也不能保证用户的公平性[3]。

接下来提出了一种依赖负载的正比公平调度算法(LDPF:Load-Dependent PF),其改进思路是:低负载时降低一类用户的速率补偿二类用户的速率,高负载时仍然采用PF算法,通过这种低负载和高负载时的时间分集,改善用户间的长时公平性。从图 3可以看出,当系统负载轻时(少于7个用户),UE1和UE2的速率都比较高,牺牲一点吞吐量是可以接受的。

LDPF算法的优先级计算公式如下:

$k = \arg \max (\frac{R_{i}^{n}}{U_{i} (n)} * f (l o a d, U_{i} (n)))$

其中修正函数

$f (l o a d, U_{i} (n)) = {\begin{cases} (\frac{\bar{U (n)}}{U_{i} (n)})^{Ρ}, l o a d ＜ β * L o a d_{\max} \\ 1, l o a d \geq β * L o a d_{\max} \end{cases}$

Loadmax为系统最大负载,load为系统的即时负载,β为负载阈值调整系数(0<β<1),P为奖惩因子(正整数),表征奖惩力度。β和P需要预先设定,在调度过程中无需改变。 $\bar{U^{n}}$ 为时隙n系统中各用户的U $_{i}^{n}$ 的均值。

当系统负载低于阈值(β*Loadmax )时,U $_{i}^{n}$ 低于 $\bar{U^{n}}$ 的用户的优先级得到奖励在PF算法的基础上乘以 $(\frac{\bar{U (n)}}{U_{i} (n)})^{Ρ}$ 倍 ;U $_{i}^{n}$ 高于 $\bar{U^{n}}$ 的用户的优先级受到惩罚而降低为PF算法的 $(\frac{\bar{U (n)}}{U_{i} (n)})^{Ρ}$ 。传输函数实现了一类用户让出更多的传输机会给二类用户。当两个用户传输速率相等时,系统会优先调度信道质量较好的用户。

当系统负载高于阈值(β*Loadmax ) 时,仍然采用PF算法。系统高负载时,在兼顾公平性的前提下,系统吞吐量显得更为重要。在文献[5]中,作者指出,PF算法能够实现比例意义上的公平性:如果有其它的算法能够使某个特定用户的容量提高x%,则在此算法下,所有其它用户所下降的容量之和的比例将超过x%。

乘以修正函数后LDPF算法相比于PF算法复杂度增加不多,易于实现和控制,适应HSDPA系统快速调度的要求。

4 算法的仿真

现采用加州伯克利大学开发的优秀的开源网络仿真软件NS2仿真HSDPA系统下无线分组调度算法,并评估LDPF调度算法的性能。NS2的标准版本不支持UMTS或HSDPA的MAC层。但NS2易于扩展,爱立信公司的研究机构开发了支持UMTS/HSDPA功能的扩展模块EURANE(Enhanced UMTS Radio Access Network Extensions)。EURANE扩展模块增加了三种基本节点:无线网络控制器(RNC),基站(BS)和用户设备(UE),并支持FACH,RACH,DCH和HS-DSCH传输信道。

4.1 仿真场景和系统参数

仿真实验中使用单小区的网络拓扑和业务类型,如图 1所示,系统参数参见表 2。在实现LDPF算法时,flow_max=20视作系统最大负载Loadmax, β=1/3,P=1。

4.2 仿真步骤

鉴于国内文献中罕见使用NS2仿真HSDPA系统,现简要介绍仿真步骤供参考。

S1:在标准的ns-2.30中目录下加EURANE的源代码补丁,使用命令patch -p1 < <patch_file>;

S2:重新编译NS2, 这样NS2就支持UMTS/HSDPA的相关功能了;

S3:在～ns-2.30/umts/hsdpalink.cc(h)中加入PF和LDPF调度算法程序和修改相关的文件;然后重新编译NS2;

S4:根据设置的仿真场景和系统参数,编写Otcl脚本,并通过在脚本中设置scheduler_type_的值来选择调度算法;

S5:用gawk语言统计实验输出的trace文件,得到所需要的数据。

更多的基于EURANE模块的仿真介绍参考文献[7]。

4.3 仿真结果

实验分别仿真了不同用户数下四种不同调度算法的性能,仿真结果如图 2和图 3所示,图中统计的速率是TCP数据包的传输速率。

仿真实验结果表明,LDPF算法在系统高负载下(多于7个用户),系统吞吐量和用户公平性与PF算法一致,如图 2和图 3所示。在系统低负载下(少于7个用户),LDPF算法的系统吞吐量比PF算法略有下降,但高于RR算法,如图2所示。与此同时,LDPF算法也提高了UE2的平均速率,降低了UE1的平均速率,如图3所示,实现了对UE1的补偿。可以增大P的值而增加补偿力度。两类用户都维持了较高的传输速率,所以在系统低负载的情况下损失一点吞吐量并无大碍。仿真结果证明LDPF算法实现了预先的设计目的:通过在低负载时牺牲一点系统吞吐量换取用户间的公平性。

5 结论

以上用NS2 + EURANE平台仿真了HSDPA系统中分组调度算法(RR, Max C/I和PF)的系统吞吐量和用户公平性,并分析了在HSDPA系统中RR算法调度结果的公平性略逊于PF算法的原因。为了弥补正比公平调度算法公平性缺失, 提出了依赖负载的正比公平(LDPF)调度算法。仿真结果表明LDPF调度算法在系统低负载时有效地补偿了先前的低速率用户,通过这种低负载和高负载时的时间分集,改善了用户间的长时公平性。LDPF调度算法也适用于TD-HSDPA等可以采用PF调度算法的场合。

参考文献

[1] 3GPP TR 25.858. High speed downlink packet access: Physical layer aspects (release 5) [S].

[2] 3GPP, C.S0024 v2.0. cdma2000 High Rate Packet Data Air Interface Specification, October 2000[S].

[3] Ghassane Aniba and Sonia Aissa. Adaptive Proportional Fairness for Packet Scheduling in HSDPA[J]. IEEE Communications Society Globecom 2004:4033-4037.

[4]H.Kim,K.Kim,Y.Han and J.Lee.An Efficient Al-gorithm for Qos in Wireless Packet Data Transmission[A],Proc.Personal,Indoor and Mobile Radio Commu-nications(PIMRC'2002)[C],vol.5,pp.2244-2248,September 2002.

[5]A.Jalali,R.Padovani and R.Pankaj.Data Throughputof CDMA-HDR:A High Efficiency-High Data RatePersonal Communication Wireless System[A].Proc.Ve-hicular Technology Conference(VTC-S'2000)[C],vol.3,pp.1854-1858,May 2000.

[6] Gao, Yue-Hong; Zhang, Xin; Yang, Da-Cheng. An Combined Scheduling Algorithm for HSDPA Mode of TD-SCDMA Wireless Communications[A].Networking and Mobile Computing, 2007. WiCom 2007. International Conference on 21-25 Sept. 2007[C], Page(s):779 - 782.

动态负载调度篇7

近年来关于云计算中的负载均衡问题是一个研究热点，如今已经有许多的负载均衡算法被提出以满足不同的优化目标。

最大最小算法(Max-Min)和最小最小算法(Max-Min)是一种启发式的调度算法，他们以任务的总执行时间最短为优化目标，Max-Min算法的核心思想是每次先计算任务在各个资源上的预计算时间，然后对最大最早完成时间的任务进行调度。对于元任务集合中长任务少短任务多的情况下，算法的执行效果较好。但是如果具体应用条件发生了变化，MaxMin算法的优势可能就不存在了[2]。

Max-Min算法和Max-Min算法却正好相反，它是先计算出任务在资源上的预计执行时间，再将最小且是最早完成时间的任务调度到资源节点上，这样会使任务的处理速度较快，任务完成时间短，但是由于每次都是把任务分配给执行最快的资源，这样很容易造成负载的严重不均，甚至一些服务器空载[3]。

基于此，本文提出了一种基于云环境下针对任务类型匹配的资源调度算法，该算法针对任务集中长短任务的不同分布情况来采取不同的调度算法，通过云仿真软件CloudSim3.0验证了该调度策略良好的调度效果。

1 相关工作

云计算环境下，有大量的负载均衡算法用于将任务调度到相应的计算资源上执行，根据优化的目标不同，算法各有优缺点。当前有国内外学者都相继提出了针对Max-Min算法和Max-Min的缺点的改进算法，Mao等人提出了利用任务状态表预测虚拟机实时负载和任务预计完成时间来动态调度任务[1]，这种方法虽然能够实现较好的负载均衡，但是由于需要维持任务状态表的实时更新，所以会使得开销比较大，任务响应时间偏长。Santhosh B等人提出了一种改进的Max-Min算法[4]，每次将任务集中的和平均任务长度最接近的任务分配给完成时间最短的任务。Upendra Bhoi等人提出一种增强型的Max-Min任务调度算法[5]，针对元任务集中大任务数很少而小任务很多的情况，提出了一种将最大任务优先调度到执行速度最慢的资源上。O.M.Elzeki等人提出一种改进Max-Min算法[6]，针对小型云计算环境下，将最大执行时间的任务分配给最小完成时间的任务。郑莉等人提出一种基于用户优先级的负载均衡算法[7]，该算法针对Min-Min算法进行改进，一开始用Min-Min算法进行任务分配处理，然后选择负载较重的资源进行资源的重新分配，观察负载重资源上的最短任务，并计算它在其他资源上的完成时间，如果小于任务跨度，那么将此任务从最终负载上移除，用其他资源进行处理。

上述介绍的种种算法，虽然在原有算法的基础上做出了一些改进，但是由于大都在特定的仿真环境下，比如说增强的Max-Min算法，作者给出的实验数据是长任务很少，而短任务很多的情形，所以所得结果会比原有算法性能更优，但是考虑到云环境下任务的动态特点，所以这些算法没有较强的适应能力。基于现有算法的局限性，提出了一种基于任务类型匹配的资源调度策略(TTM)，在此调度策略下通过与用单一使用Max-Min或者Min-Min算法相比较，验证了此算法在任务动态环境下具有较好的效果。

2 云环境下负载调度模型

2.1 负载均衡任务调度模型

负载均衡是云计算的主要问题之一，负载可以是内存、CPU处理能力、网络或者是时延负载[8]。它需要在不同的节点之间共享工作负载，从而提高资源利用率和系统的性能。本文通过深入分析了Max-Min算法和Max-Min算法的优缺点和所使用的场景，设计了一个新的调度策略，根据任务集中的任务长度分布情况来调用相应的算法，调度模型如图1所示。

此调度过程为，首先用户提交任务，通过作业管理器管理用户提交的任务，计算任务所需要的性能要求和其他的一些因素限制，运用不同的负载均衡算法将任务分配给不同的虚拟机去执行，当然这里的虚拟机是在物理服务器中创建的，所以考虑的是物理服务器的负载。

2.2 任务类型匹配负载均衡算法设计

云计算环境下由于任务的大小不一，云计算数据中心各节点的处理能力也不同，所以负载的的定义很复杂[9]，为了简化起见，做了2点假设。

1)各任务之间是独立的，互相之间没有依赖关系;

2)虚拟机的处理能力只考虑他的执行速度(MIPS)，没有考虑带宽和内存等其他因素。为了描述模型的方便，先做一些相关定义。

定义1:任务执行时间(TET)。

任务执行时间是一个任务在某个资源节点上的处理时间，假设任务i的长度为lengthi，虚拟机j的执行速度为MIPSj，那么任务i在虚拟机j上的执行时间为

定义2:任务预期完成时间(TCT)。

任务预期完成时间是任务在考虑分配给哪个虚拟机时要考虑的问题，看看任务在哪个虚拟机上能最快处理完成，即为准备时间，放在处理能力最强的虚拟机上完成时间不一定短，这个和执行时间不同。它等于开始执行的时间BETij加上Tij。

定义3:平均资源利用率和时间跨度。

资源利用率表示为所有虚拟机在整个任务处理过程中的资源平均利用率

式中:RUj表示虚拟j的资源利用率;Tei和Tbi表示任务i在资源上执行的结束时间和开始时间;T表示整个任务集处理完成所用时间;为所有资源平均资源利用率。时间跨度表示为任务全部处理完所需要的时间

定义4:集中任务预期完成时间标准差。

由于各个任务之间是独立的，所以标准差计算公式为

定义5:负载均衡度。

负载均衡度定义为各个虚拟机之间负载量的差别程度，用β表示

式中:m表示虚拟机的个数;S表示资源利用率的标准方差，当S越小是表明负载均衡度越高。

2.3 策略执行过程

对于到达的一批假设任务集为T{t1,t2,t3，…，tm}，他们的长度分别为length1,length2，…，lengthn，首先将到达的任务集中的任务按照长度进行升序或者降序排列，为了讨论方便假设为降序，在排好序的任务中找到连续几个值大于SD的地方，通过此方法可以找到任务长度明显变化的地方，记为Po，所以对于任务集中的任务分布可能有如下3种情形:

1)情形1，即如果Po<S/2，那么说明短任务数大于长任务数，此时应用Max-Min算法效果会比使用Min-Min效果好。

2)情形2，即如果Po>S/2，那么说明短任务数小于长任务数，此时应用Min-Min算法效果比较好些。

3)情形3，即如果任务长度间的差值没有大于SD，说明任务之间的长度都差不多，此时选择Min-Min算法处理下个任务，算法流程图如图2所示。

3 实验仿真结果及分析

为了验证本算法的有效性，采用CloudSim 3.0软件进行仿真实验，这是一款由澳大利亚墨尔本大学开发的云计算仿真工具，主要考察两个指标:任务总执行时间(Makespan)和负载均衡度(Load Balancing Level)，实验表明提出的算法优于单一采用Max-Min算法和Min-Min算法。

针对上述3种情形进行仿真实验，仿真中将资源数定位取10，一批任务的数量为1 000，刚开始任务是长度随机排列的，任务到达由泊松随机过程建模。仿真结果如图3、图4所示。

通过图3中的3种情形得比较可以看出，提出的算法在3种情形下均具有较短的时间跨度，情形1中由于有许多的段任务，而长任务量很少，多虚拟机并发执行的时间短，所以用Max-Min算法耗时比较长，而此时用Max-Min算法效果比较好。情形2恰好相反，短任务很少，长任务多，此时应用Max-Min算法就没有什么优势。情形3中子任务之间的长度差别很小，所以用Max-Min算法执行时间也较短。

同样以上3种仿真情形中使用TTM算法均具有较好的负载均衡效果，由于Max-Min算法的负载均衡效果本身要优于Min-Min算法，特别是当短任务很少、长任务多的情形。因此对于以上3种情形的负载均衡水平采用TTM算法会具有较好的性能。

4 结束语

本文主要针对云计算环境中的负载均衡问题进行了研究，在深入分析当前的两种经典的启发式负载均衡算法基础上，通过比较他们的优缺点，提出一种基于任务类型匹配的负载均衡算法，并通过CloudSim云仿真环境验证了此算法的可行性，提出的算法不仅加快了系统响应时间而且有效地平衡了虚拟机之间的负载，提高了用户的服务质量。由于研究工作是在已有的负载均衡算法上做的调度策略创新，而不是在原有的算法上做的改进，而且对于任务调度有较多因素没有考虑，比如通信的开销、执行任务的花费等，所以这也会是下一步的研究工作。

摘要：针对云计算环境下大量并行计算节点容易产生计算节点之间的负载不均问题,提出了一种基于任务类型匹配的负载均衡方案。该方案针对任务集中的多种不同长度的子任务类型情况进行判定,并对当前主流的Max-Min和Min-Min两种启发式负载均衡算法进行分析,综合其优缺点,并针对任务集的类型采用不同的算法进行任务调度。实验结果表明在该负载均衡的策略下,提出的方案具有比单一应用Max-Min或者Min-Min算法具有更好的负载均衡特性和更短的完成时间。

关键词：云计算,任务调度,负载均衡,Max-Min,Min-Min

参考文献

[1]MAO Y,CHEN X,LI X.Max-min task scheduling algorithm for load balance in cloud computing[C]//Proc.International Conference on Computer Science and Information Technology.[S.l.]:Springer India,2014:457-465.

[2]KANAKALA R,REDDY V K.Performance analysis of load balancing techniques in cloud computing environment[J].Telkomnika Indonesian Journal of Electrical Engineerin,2015,13(3):568-573.

[3]苏淑霞.面向云计算的任务调度算法研究[J].安徽大学学报:自然科学版,2014,38(5):24-30.

[4]SANTHOSH B.MANJAIAH D H.An improved task scheduling algorithm based on Max-Min for cloud computing[C]//Proc.International Conference on Advances in Computer&Communication Engineering.Bengaluru,India:IJIRCCE,2014:84-88.

[5]BHOI U,RAMANUJ P N.Enhanced Max-Min task scheduling algorithm in cloud computing[J].International Journal of Application or Innovation in Engineering&Management(IJAIEM),2013,2(4):259-264.

[6]ELZEKI O M,RESHAD M Z,ELSOUD M A.Improved Max-Min algorithm in cloud computing[J].International Journal of Computer Applications,2012,50(12):22-27.

[7]郑莉.云计算环境下资源调度关键技术研究[D].北京:北京邮电大学,2014.

[8]KHERANI F,VANIA J.Load balancing in cloud computing[J].International Journal of Engineering Development and Research(IJEDR),2014,12(1):907-912.

【动态负载调度】推荐阅读：

动态负载均衡06-09

动态负载平衡09-21

动态优化调度09-18

通信卫星动态调度问题07-15

负载控制07-21

负载电流10-19

负载策略05-23

模拟负载06-22

负载能力07-03