基于QoS的改进Min–Min调度算法

林志杰, 张友斌, 顾静



基于QoS的改进Min–Min调度算法

林志杰1, 张友斌1, 顾静2

(1. 湖南幼儿师范高等专科学校教务处, 湖南常德, 415000; 2. 中南大学软件学院, 湖南长沙, 410075)

针对经典Min–Min调度算法存在负载不均, 资源利用率低, 处理时间长等问题, 提出了P–Min算法。该算法根据任务的优先级并结合贪心算法来实现调度。仿真结果表明: P–Min算法在负载均衡的资源利用率方面较Min–Min算法提高了17%, 任务总体执行时间调高了8.03%。

云计算; QoS; 贪心策略; 负载均衡; Min–Min; P–Min

云计算[1]由网格计算[2]、分布式计算等技术发展而来, 它提供一种“按需服务”的模式, 近年来, 该技术受到大量国内外学者的重视[3]。在云计算中, 任务调度是指通过一定的算法合理地安排各个任务的执行, 使其处理时间短且资源利用率高[4]。广泛应用于云计算中的任务调度算法有Min–Min算法[5]、Min-Max[6]算法及模拟退火算法等, 其中Min–Min算法是一种最为简单快捷的算法, 但是它忽略了任务对QoS[4–5]的要求。

本文提出一种基于QoS的改进Min–Min调度算法, 并设计仿真实验验证算法的有效性。

1 P–Min 调度算法分析

1.1 P–Min思想

Min–Min调度算法是基于任务运行时间进行调度的, 它尽可能地将小任务分配到执行速度快的资源上去执行, 从而使得任务总体完成时间最小[7]。Min–Min算法首先计算每个任务在个资源下的最小完成时间。然后将任务按照最小完成时间升序排序, 依次将每个任务分配到其最小完成时间所对应的资源上。Min–Min算法最大的缺点在于其负载不均[8–9]。针对Min–Min算法存在的不足, 本文提出一种基于QoS的改进Min–Min调度算法P–Min算法。其基本思想是根据任务的优先级从高到低分配相应的资源, 如果任务具有相同的优先级, 则处理时间越短的越先执行。如果存在多种分配方法, 则将任务分配给运行任务数最小的资源。

1.2 P–Min算法

几个变量定义: RT(j)表示资源Rj等待时间; CT(i, j)表示任务Ti在资源Rj上的预测完成时间, 且满足CT(i, j) = ETC(i, j) + RT(j); MCT(i)表示任务Ti的最小完成时间; host_MCT(i)表示任务Ti分配给资源host_MCT(i)。

P–Min算法描述如下:

For 任务集T中的每个任务Ti

For j = 1, 2, 3…m

初始化RT(j) = 0

计算任务Ti在各主机上的预测完成时间CT(i, j) = ETC(i, j) + RT(j)

End for

End for

While T 不为空 do

For 任务集合T中的每个任务Ti

计算其最小完成时间MCT(i)及相应的主机编号host_MCT(i)

End for

按照优先级从高到低的顺序找出最小完成时间的任务Ti

将任务Ti分配给编号为host_MCT(i)的主机

从任务中删除Ti

更新相应主机的就绪时间RT(host_MCT(p)) = MCT(i) + MCT(p)

更新预测完成时间矩阵CT

End while

2 仿真条件与任务

实验环境在个人PC机上进行, 软硬件配置为: CPU, Broadwell i7–5500U 2.4 GHz; 内存4 GB; 硬盘500 GB; 操作系统, Windows 7, 32位; 编程及实现, MyEclipse2014; 仿真平台, CloudSim[10]。

在CloudSim中模拟P–Min算法及Min–Min算法任务的调度情况, 主要验证任务总完成时间、任务总执行时间、系统资源利用率及任务响应时间4个指标。任务总完成时间为所有任务完成时间总和; 任务总执行时间为从第一个任务开始执行到最后一个任务完成所花的时间; 系统资源利用率表示系统资源使用程度; 任务响应时间为任务进入系统到该任务执行完成所花时间, 定义为等待时间与执行时间之和。

3 结果与分析

实验中有50个资源, 每个资源的处理能力随机产生, 范围为[50, 350]。随机产生300个任务, 任务执行时间范围为[500, 1 000]。随机为每个任务分配优先级, 优先级取值为{1, 2, 3, 4, 5}, 优先级越高数值越大。仿真结果见表1。

表1 仿真结果

实验结果表明, P–Min算法与Min–Min算法相比, 在任务总体执行时间上调高了8.03%, 在系统资源利用率上提高了17%, 其原因在于Min-Min算法总是将小任务放到最快的资源上去执行, 使得处理速度较慢的资源空闲, 处理速度较快的资源CPU利用率过高, 从而增加了任务的总执行时间, 降低了系统的资源利用率。P–Min算法通过给任务设定不同的优先级使得不管是大任务还是小任务都在系统资源上有效执行, 从而降低了任务的总执行时间和提高了系统的平均资源利用率。

P–Min算法与Min–Min算法相比, 在平均任务响应时间方面提高了10%, 其原因在于Min–Min算法总是将小任务放到最快的资源上去执行, 使得大任务的等待时间过长从而增加了系统的平均任务响应时间。P–Min算法通过给任务分配不同的优先级使得大小任务都得到有效地执行, 从而降低了系统的平均任务响应时间。

与P–Min算法相比, Min–Min算法在任务总完成时间上性能比较优秀, 其原因在于该算法每次将最小的任务放在最快的资源上执行, 因此它每次的执行时间都是最短的。

4 结论

本文提出了一种新的调度算法P–Min算法, 该算法根据任务的优先级从高到低分配相应的资源。如果任务具有相同的优先级, 则处理时间越短的越先执行。如果存在多种分配方法, 则将任务分配给运行任务数最小的资源。仿真试验表明: 该算法在任务总执行时间, 平均系统资源利用率和平均任务响应时间方面都比Min–Min算法更好。本文中任务的优先级是已知的, 但是云计算环境中的任务并不一定具有优先级, 因此, 如何定义任务的优先级是以后研究的重点。

参考文献：

[1] 李建峰, 彭舰. 云计算环境下基于改进遗传算法的任务调度算法[J]. 计算机应用, 2011, 31(1): 184–186.

[2] 张海宾, 莫琳莎, 刘立祥. 网格调度综述[J]. 计算机工程与设计, 2009, 30(9): 2 151–2 153.

[3] Agarwal A, Kumar P. Multidimensional QoS Oriented Task Scheduling In Grid Environments [J]. International Journal of Grid Computing & Application, 2011, 2(1): 28–37.

[4] 刘宴兵, 陈杰, 熊仕勇. 基于QoS相似度的网格任务调度算法[J]. 重庆邮电大学学报, 2009, 21(3): 416–420.

[5] 吴高峰, 蒋玉明, 杨林, 等. 基于QoS改进的Min-Min网格调度算法[J]. 微计算机信息, 2009(27): 110–112.

[6] Etminani K, Naghibzadeh M. A min-min max-min selective algorithm for grid task scheduling [C]// Tashkent: In 3th IEEE/IFIP International Conference in Central Asia on Internet, 2007.

[7] Engin O, Ceran G, Yilmaz M K. An efficient genetic algorithm for hybrid flow shop scheduling with multiprocessor task problems [J]. Applied Soft Computing, 2011, 11(3): 3 056–3 065.

[8] Ahmadi A A, Olshevsky A, Parrilo P A, et al. NP-hadness of deciding convexity of quartic polynomials and related problems[J]. Mathematical Programming, 2013, 137(1/2): 453–476.

[9] Duy T V T, Inoghchi Y. A prediction-based green scheduler for datacenters in clouds [J]. IEICE Transactions on Information and Systems, 2011, 94(9): 1 731–1 741.

[10] Calheiros R N, Ranjan R, Beloglazov A, et al. CloudSim: a toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms [J]. Software-Practice and Experience, 2011, 41(1): 23–50.

(责任编校: 江河)

Improved Min-Min scheduling algorithm based on QoS

Lin Zhijie1, Zhang Youbin1, Gu Jing2

(1. Teaching Affairs Office, Hunan College for Preschool Education, Changde 415000, 2. China; School of Software, Central South University, Changsha 410075, China)

The classical Min-Min scheduling algorithm exists the problems of load unbalance, the low resource utilization rate and long processing time. To solve these problems, a scheduling algorithm named P-Min is proposed, which is based on task priority and combined greedy scheduling strategy to schedule. Experimental results show that, as compared with the Min-Min algorithm, the P-Min Algorithm improves 18% in load balance and 8.03% in the overall task execution time, respectively.

cloud computing; QoS; greedy strategy; load balance; Min-Min; P-Min

10.3969/j.issn.1672–6146.2015.03.003

TP 393.01

1672–6146(2015)03–0011–03

林志杰, 461635278@qq.com。

2015–03–17