-1-
一种基于 QoS 的资源调度算法
张颖
河海大学计算机与信息工程学院，江苏南京（210098）
摘 要：在对网格计算中现有的 Min-Min和 Max-Min任务调度算法的研究基础上，提出了
一种基于量化思想的资源调度算法，利用对现有资源以及任务的分级使得不同 QoS 的任务
可以得到相应等级的资源，从而解决了原有算法存在的对于高质量任务运行时间过长的问
题。
关键词：网格；资源调度；Min-Min；Max-Min
中图分类号：TP393
1. 引 言
网格将地理上分散的属于不同机构管理的运行不同软件的异构的各种高性能计算资源
用 Internet 连接，通过合理的组织充分利用起来，提供给用户一个高可靠、高性能的、可透
明访问的统一虚拟超级计算机环境[1]。而网格中的资源调度需要在包含大量不同计算机的网
格环境中,同时考虑各网格节点的计算性能、节点之间的通讯性能等参数,把不同的任务以最
合理的方式分配到相应的网格结点去完成。其重要性是不言而喻的。
如何评价一个资源调度算法的好坏要从四个方面去考虑：最优跨度(Optimal Makespan)、
负载均衡 (Load Balancing)、服务质量 QoS(Quality of Service)、经济原则 (Economic
Principles)[2]。
最优跨度指的是任务从开始执行到执行结束所经历的时间，是所有改进算法的主要目
标。负载均衡指的是网格资源的利用效率，即在网格中是否所有的资源都得到了有效的利用，
是否存在闲散资源等。服务质量 QoS，这里的 QoS 可以理解为用户所提交任务对资源的要
求。不同的任务对于资源的要求也不尽相同，在进行资源调度的同时要兼顾任务的 QoS，本
文的算法就是在原有算法基础上以 QoS 为切入点进行改进的。经济原则，用户在使用不同
的资源完成任务的同时应对资源的提供者缴纳一定的费用，作为对其提供资源的补偿。本文
的算法在形成分级的同时也就形成了一个计价系统，能够方便的计算使用资源者的应付款。
而经典算法 Min-Min 算法和 Max-Min 算法对于 QoS 高的任务的支持并不好，高 QoS
的任务得不到高质量的资源，使得整个任务的跨度过大。本文提出了一种基于 QoS 的算法，
对任务的 QoS 和资源的质量进行分级，使得不同 QoS 的任务得到同等级的资源，解决了原
有算法的缺陷。
2. Min-Min 算法与 Max-Min 算法
任务调度问题的实质就是在一个由 m 个需要调度的任务，n 个可用的资源(主机或集
群)[3] ，k 个数据储存单元构成的网格环境下，把 m 个任务 T = { t1 ,t2 , ……, tm }以合理的方
式调度到 n 个资源 R = { r1 ,r2 , ……, rn } 上去运行，目的是得到尽可能小的总执行时间
(makespan)。 m 个任务在 n 个不同资源上的预测执行时间 ETC( Expected Time to Compute)
是一个 m ×n 的矩阵。矩阵中的每一行代表某一个任务在 n 个资源上的不同执行时间, 每一
列代表在同一个资源上 m 个任务的不同执行时间。
记第 i 个任务在第 j 个资源上的预测最小完成时间(Minimum Completion Time) 为
MCT( i, j) ，则 m 个任务在 n 个不同资源上的预测最小完成时间也是一个 m ×n 的矩阵。
-2-
作为现有基础性的算法，Min-Min 算法[4]存在着先天的缺陷，先看一下该算法的主要内
容：
（1）对于任务集中的每一个任务ti，分别算出将它分配到n个资源上完成所需的最小完成
时间，如果在第k个资源上所用的时间最短，我们将其记为MinCT（i）=MCT(i,k)。这样就
可以得到一个含有m个元素的数组MinCT。
（2）找到在数组中最小的值，如果对应的是任务ta，对应的资源是rb，则将这个资源分
配给这个任务。
（3）从任务集中删除任务ta，刷新MCT矩阵。
经过研究发现这个算法资源负载均衡性很低，比如在遇到这样一种情况时：
现有以下的一个 ETC 矩阵，使用 Min-Min 算法进行分配。
按步骤首先得到 MinCT 为{1,2,4}。然后找到 ta为 t1将资源 r1分配给 t1。从任务集中将
t1 删除，然后刷新矩阵 MCT。如此分配下去可得到这次资源调度的结果，如柱状图所示:
Min－Min算法图示
1
2
4
0
1
2
3
4
5
6
7
8
r1 r2 r3
t3
t2
t1
图1
可见，所有的任务都在资源 h1 上完成，最后的 makespan 为 7，而资源 r2和 r3 一直处于
闲置状态。资源的负载均衡性很差。与其相比较，Max-Min 算法在资源负载性能上就要好
的多，它与 Min-Min 算法的不同在于第 2 步上，总是找到用时最长的那个任务和主机进行
分配。如柱状图显示：
r1 r2 r3
t1 1 2 4
t2 2 4 8
t3 4 8 16
-3-
Max－Min算法图示
444
0
1
2
3
4
r1 r2 r3
t3
t2
t1
图2
如上图可见，在这种分配方式之下，三个资源都利用上了，而最后的 makespan 为 4。
在负载平衡上达到了最优。
综上所述，当任务队列里存在着 QoS 相差很多的任务时，Min-Min 算法的弊端更是显
而易见的，如果任务的 QoS 较高，也就是说该任务对于执行的资源有较高要求时，如果好
的资源总是被一些 QoS 较低的任务占据着，那该任务将会一直处于等待状态。这样最后的
makespan 肯定会很高。这种情况该怎么解决呢？
3. 一种基于 QoS 的资源调度算法
算法思想
使用量化的思想，将任务和资源都按照一定的标准分级，再配以相对应的算法，使得高
质量的资源分配给高 QoS 的任务，在分级的同时将经济原则考虑在内，对于不同等级的资
源使用作出不同的补偿。这样就不会使得高级资源被低 QoS 的任务占用而使得高 QoS 的任
务一直处于等待状态。
根据网格系统中资源的状况，如 CPU 的等级，内存的大小等，制定一个等级标准。在
系统中的资源都按照标准定上等级。如有任务提出，根据同样的标准对 QoS 定级。不同的
任务对资源的要求不同体现在这个级别上。不同的级别对收费的要求也不同，根据时间在完
成之后收费。
对于那些想要任务在尽快时间内完成的用户，可以在提交任务时根据任务的等级提出一
个比其高的资源等级要求。在分配时先划分任务集，按照任务的期望级别从高到低将任务划
分，期望级别高的任务先进行调度，考虑 Max-Min 算法在规则矩阵时负载均衡性能高的优
势，在分配时选择用 Max-Min 算法。
算法步骤
以此为思路，给出以下算法：
扩充任务内容，任务集中的每个任务都包含一个任务等级 TL 和一个资源期望等级
EL。即 ti,2,3表示任务 ti要求至少 2 级的资源才能正常完成，但是用户希望使用 3 级的资
源尽快完成。同样的扩充资源集，使得每一个资源都包含一个资源等级 HL。如 Hi,2 表示这
-4-
是一个 2 级的资源。
假设分为 k 个级别，则具体过程如下：
（1） 根据EL将任务集分成k个子集为T1，T2……Tk，其中Tk中的元素皆为 ti,x,k（x<=k）；
（2） For i=k downto 1；
（3） 将 Ti 分为两个子集 TiH 和 TiL 其中 TiH 为 TL=EL 的任务，TiL 为 EL>TL 的任务；
（4） 对于 TiH 使用 Max-Min 算法进行分配；
（5） 对于 TiL 使用 Max-Min 算法进行分配；
（6） End for；
（7） End；
算法仿真
使用 GridSim 模拟器[5]对所提出的算法进行仿真研究。GridSim 提供了一系列 API,模拟
了一个网格的运行环境，能够随机地生成要求的资源数量以及资源内容、任务、网络带宽、
通讯延迟等参数。这就方便我们检验算法的可行性。假定将 QoS 分成四级，按照各等级所
占比例不同进行仿真，结果再与单纯使用 Min-Min 算法进行仿真的结果作比较，为了得出
一个一般性的结论，对每一次试验都进行 100 次仿真，每次仿真使用 100 个随机产生的任务，
求出平均值。以下是仿真的结果：
Min-Min算法与改进后算法的比较
164
165
166
167
168
169
170
171
172
173
174
Makespan
Makespan
Min-Min 改进算法
图3
可见在所提供的资源相对丰富的情况之下，改进后的算法比 Min-Min 算法提高了
%。
4. 小结
本文提出了一种基于量化思想的资源调度算法，在这种运行机制下，QoS 高的任务被优
先分配了高质量的资源，那么就不会出现由于高质量资源被占用而使得 QoS 高的任务一直
处于等待状态的问题，也不会出现由于 QoS 高的任务占用低质量资源而一直运行的问题。
而这个方案的最大的特点在于期望等级的设定。由于这个设定，用户多了与系统的交互。从
经济角度考虑，这样更符合商业规律。由于不同级别的资源的使用价格不同，那么除了任务
等级高的不得不用高等级的资源，任务等级低用户迫切需要解决问题，在这个时候设定一个
较高等级的期望等级，使用高等级的资源来快速完成就成为了一种很人性化的考虑。
-5-
但是这个算法还存在着问题，并没有将由于资源的异构性[6]导致资源的不连续性考虑进
去。比如在一个网格系统中有两台硬件配置相同的电脑一台安装的是 Windows 系统，另一
台安装的是 Unix 系统，那么同一个任务在这两台电脑上完成的时间肯定不同。这种算法适
用于在一个连续的计算网格系统中。至于在不连续的网格系统中是否可用还有待于进一步的
研究中。
参考文献
[1]WANG RC, CHEN RY, CHAO HC. Mobile IPv6 and AAA Architecture Based on WLAN[J ]. International
Journal of Network Management archive, 2004, 14 (5). 305 - 313.
[2]杨召庆，杨志义，周兴社，王云岚.校园计算网格作业自适应调度的研究和实现.微电子学与计算机.2006
年第 23 卷第 3 期
[3]魏天宇，曾文华，黄宝边. 基于 Min-Min 改进后的网格调度算法. 计算机应用. 2005 年 5 月
第 25 卷第 5 期
[4]BRAUN TD, SIEGEL HJ, BECK N. A Comparison of Eleven Static Heuristics for Mapping a Class of
Independent Tasks onto Heterogeneous Distributed Computing Systems [ J ]. Journal of Parallel and Distributed
Computing, 2001, 61 (1) : 810 - 837.
[5]CASANOVA H. Gridsim A Toolkit for the Simulation of Application Scheduling [A ]. Proceedings of the 1st
International Symposium on Cluster Computing and the Grid [C ], 2001. 430.
[6]RITCHIE G, LEVINE J. A Fast, Effective Local Search for Scheduling Independent Jobs in Heterogeneous
Computing Environments [A ]. Proceedings of the 22nd Workshop of the UK Planning and Scheduling Special
Interest Group (PLANSIG 2003) [C ], 2003.
Scheduling algorithm based on QoS
Zhang Ying
Computer & Information Engineering College, Hohai University, Nanjing, Jiangsu,（210098）
Abstract
Based on the research of existing scheduling algorithms Min-Min and Max-Min, A modified module
which is based on quantizing is proposed. This algorithm can make different tasks get the resources
that on the same grade to resolve the problem which is caused by existing scheduling algorithms. The
problem is the QoS is so high that the makespan is too long.
Keywords: grid; Schedule; Min-Min; Max-Min
作者简介：张颖，男，1981 年出生，硕士研究生，主要研究方向是分布式计算，网格。
