云计算中多层次公平性QoS约束任务调度算法*

郑迎凤， 宋 朝， 赵文彬

(1. 黄河科技学院 网络与信息技术研究所， 郑州 450000； 2. 石家庄铁道大学 信息科学与技术学院， 石家庄 050043)

随着数据量的指数级增长，越来越多的应用必须借助于云端资源来实现.云计算系统通过在云端整合各种类型的虚拟资源，可以实现对资源的统一化调度与管理[1].而当面对大规模多任务虚拟机资源分配与任务调度时，传统的分配方法往往只注重分配效率，而忽略了资源对于执行任务的公平性问题.云计算环境中的资源供求关系类似于商品经济模型，云资源提供者即等同于商品供应者，为用户提供各类资源.资源用户则等同于商品买家，为了获得资源需求，买家需要支付费用.基于市场经济模型的云任务调度算法即是建立资源提供者与资源消费者间的市场机制，并利用价格杠杆调整用户需求与资源分配[2].众所周知，高质量的服务与公平竞争原则是资源分配市场正常运行的基础.在云计算环境中，不同用户拥有不同类型的任务，随着用户数量的增加，云规模也将急剧扩展，此时，云计算的核心问题即是如何确保服务质量(quality of service，QoS)，并且为不同用户提供使用云资源的公平机会.换言之，云计算的目标是如何使服务的用户获得更好的满意度.

云计算是由经济原则决定的一种新的计算模型，云计算中的资源分配行为与社会财富的分配行为具有极大的相似性.云计算中的资源分配问题更适合于以社会福利的分配理论进行求解，它不仅强调效率，更注重资源分配的公平性[3].

文献[4]提出一种异构环境下的占优资源公平性分配(DRFH)算法，算法的目标是平衡多资源在任务上的公平分配，但算法得到的资源利用率相对较低；文献[5]对DRFH算法进行了改进，提出了异构云中的占优资源联合公平性分配(MDRF)算法，该算法虽然改善了资源利用率，但算法需要进行全局遍历，复杂性过高；为了满足公平性分配的条件，文献[6]设计了一种多资源分配公平性度量模型，并在此基础上提出了一种资源动态分配算法，为动态资源公平分配提供了定量分析工具；文献[7]提出了基于信誉因子增强的公平性资源分配算法，算法通过信誉因子对资源使用进行评估，并引入惩罚性分配机制，增强资源分配的公平性保障，但算法同样牺牲了资源的利用率；文献[8]为了满足不同的用户需求，解决资源分配效率低和不均的问题，提出基于全局优势的资源分配公平性(GDRF)算法，算法通过轮转方式，以全局优势资源共享比和全局优势资源权重实现资源的公平性匹配；文献[9]在文献[8]基础上进一步考虑了系统能耗的因素，从降低能耗的角度使资源得到公平利用；文献[10]提出一种QoS分级任务调度模型，并根据任务制定不同的QoS约束，设计一种基于Chord优化算法的任务调度策略，使得QoS约束的任务可以获得用户满意的执行时间；文献[11]综合考虑用户任务截止时间和预算两个QoS指标，提出了一种基于隶属度函数的多QoS约束任务调度算法.

基于以上工作，本文将从新的视角研究云任务调度公平性问题，通过利用社会资源分配理论建立了一种任务调度的多重公平性QoS约束，以期实现云任务调度在多QoS约束下，最大程度地增强用户对服务的满意度.

1 模型描述

云计算中实体主要包括：用户、资源提供者及调度系统，与之对应的研究目标则为用户任务、资源以及调度策略.将社会福利分配公平性理论与云计算的资源分配问题进行映射，如图1所示.此时需要解决的问题是用户任务的分类、任务公平性函数的定义、资源与任务的参数化以及任务与资源间的映射.

图1 问题映射Fig.1 Problem mapping

1.1 基于QoS偏好的任务分类机制

云计算环境中，QoS是用户在执行任务过程中对云服务满意度的一种度量.由于云计算的商业化特性，它需要为不同用户提供满足不同需求，即用户对资源需求拥有不同偏好，而用户本身的多样性，导致此时的任务调度与资源分配将具有更高的复杂性.本文将对用户任务依据QoS进行分类，重点考虑以下两类QoS参数：

1) 任务完成时间.对于用户的实时性任务，通常要求任务完成时间应尽可能短.

2) 网络带宽.若用户运行对网络通信带宽要求较高，则应优先考虑满足带宽需求.

为了根据不同的QoS参数度量用户满意度，需要对不同的QoS参数建立不同的量化评估标准.

1.2 公平性约束

根据社会福利分配公平性原理，在云计算任务调度环境下建立了双重公平性约束，如图2所示.图2中符号含义说明如下：cx为局部结构的目标特征；Cx为参考结构的目标特征；gox为局部结构的分配值；GOx为参考结构的分配值.

在云任务调度环境中，图2中变量可作如下映射：cx为用户任务的特征；Ex为用户任务的期望资源；Cx为参考结构中用户任务的QoS特征；gox为用户任务实际的资源分配；GOx为一般期望效用，即认可的合理分配标准.

图2 多重约束Fig.2 Multiple constraints

由于cx与Cx之间具有相似性，因此GOx对于决定gox具有参考性.为用户任务进行资源分配时，gox与GOx之间所建立的约束关系将导致两者趋于一致与收敛，即gox将等同于公平性分配.换言之，Cx、GOx与gox之间将形成约束关系，以确保资源选择的公平性，Ex与gox之间进行定义公平性评估函数以评估资源分配的公平性.

在云计算环境中，资源使用的公平性主要体现为：云调度系统能够根据用户的任务特征和QoS偏好，为任务提供合理有效的资源，使得不同的用户获得所需求的服务满意度.定义云计算环境下的任务公平性和系统公平性如下：

1) 任务公平性.对于任务而言，如果实际获得的资源分配量是最大程度地接近于任务所期望的资源分配量，则称任务的执行具有公平性.

对于任务Ti的公平性，可以通过评估函数进行定义，即

(1)

式中：α为一个常值，α∈(0，1]；Ma，i为任务Ti实际分配的资源量；Me，i为任务Ti期望分配的资源量.任务公平性具有以下3种情形：

① 如果Ma，i=Me，i，则Fi=0，表明此时的资源分配达到公平性分配；

② 如果Fi>0，则表明任务获得了多于期望值的资源量，称为过多非公平性分配；

③ 如果Fi<0，则表明任务未获得期望的资源量，称为过少非公平性分配.

在实际云计算任务调度环境中，资源实际分配量高于任务对资源的期望数量将有助于提高用户的服务质量，因此，实际环境中允许出现过多非公平性分配.公平性评估函数即是用来评估资源分配结果是否满足公平性约束.

2) 系统公平性.令T={T1，T2，…，Tn}表示云系统中的任务集合，F={F1，F2，…，Fn}表示与其对应的公平性评估函数集合，则整个云系统的公平性评估函数可表示为

(2)

当F达到最小值时，则表明整个用户获得了最大化的资源分配公平性要求，此时整个云系统的公平性要求也是最佳的，该参数即可用来优化整个系统的全局公平性.

1.3 一般期望约束

由于用户任务需要由系统提供的资源执行，而用户任务本身由于不同的应用特征所具有的QoS偏好也不相同.根据图2的含义，在参考结构中QoS偏好对应的资源分配量即称为一般期望，且属于公平性分配.因此，资源分配与任务调度过程中的公平性约束即是通过一般期望约束，根据用户任务的QoS特征，建立资源与任务间的最优映射过程.

根据一般期望约束的含义，即可优化在局部结构中的资源分配过程.用户任务的QoS特征与任务和资源间的映射关系即可对应为图2中Cx与GOx间的关系.Cx与GOx间的映射关系可用于Cx与gox间的映射约束，因此，用户任务可逐渐获得公平性的资源分配.

另外，资源分配过程的公平性约束可以通过一般期望约束完成，因此，需要根据用户任务的QoS特征建立任务与资源间的映射关系.

1.4 任务与资源模型

云计算利用虚拟化技术将主机资源映射至虚拟机层，因此，云任务的调度主要实现于应用层与虚拟机层.云计算使用户任务所需资源以虚拟机形式进行匹配，其资源映射过程即是寻找特定虚拟机资源的过程.

虚拟机的资源特征集合表示为

RCi={RCi，1，RCi，2，RCi，3}

(3)

式中，RCi，1、RCi，2、RCi，3分别为云系统中虚拟机的CPU资源、内存资源和带宽资源.

虚拟机的性能集合表示为

Pi={Pi，1，Pi，2，Pi，3}

(4)

式中，Pi，k为虚拟机特征RCi，k所对应的性能取值.

为了约束资源分配过程的公平性，需要根据用户任务的不同QoS目标调整所选虚拟机资源的性能比率参数.

任务类型i的一般期望集合表示为

GEi={GEi，1，GEi，2，GEi，3}

(5)

且

(6)

式中，GEi，1、GEi，2、GEi，3分别为CPU数量权值、内存权值和带宽权值.

1.5 公平性评估函数计算

一般利用式(1)作为公平性评估函数评估资源分配结果的公平性.Fi值的计算需要通过用户任务的期望资源分配量与实际资源分配量的比值获得.由于用户任务的QoS参数和云计算资源的参数之间拥有非一致的维度关系，并且两者之间的映射关系是非线性的，因此需要建立维度的QoS需求与云计算资源参数之间的直接映射关系.期望资源分配量对应于Ex，实际资源分配量则对应于gox，一般期望的映射关系则对应于Cx与GOx之间的关系.

利用一般期望映射关系向量与实际资源分配中的归一化资源参数向量的最小Euclidean距离约束gox与GOx之间的趋同，即可将社会福利公平性分配思想完美地融入云任务调度问题中.

1.5.1 任务完成时间

云任务调度系统中，任务完成时间被选取作为评估标准.假设云计算中虚拟机资源集合为VM={VM1，VM2，…，VMm}，其中，m表示虚拟机资源的总量.对于用户任务Ti，具体处理过程如下：

1) 产生满足任务执行条件的候选虚拟机资源集合VMi={VM1，VM2，…，VMk}，其中，k表示能够满足执行任务Ti条件的虚拟机资源总量.

2) 根据一般期望偏好约束从集合VMi中选择最满足任务期望的虚拟机执行用户任务.

3) 对虚拟机的性能参数作归一化处理，归一化后其取值范围为0～1之间，以实现一般期望值向量的统一比较.令Xij={X1j，X2j，…，Xij}表示VMi性能参数相同集合，归一化后其值可表示为

(7)

式中：curXij为性能参数的当前值；minXij为性能参数的最小值；maxXij为性能参数的最大值.

利用式(5)将资源参数与用户任务的一般期望GEi进行匹配，并计算两者之间的Euclidean距离.当距离最小时，表明两者间的相似性最佳.向量X={X1，X2，…，Xn}与向量Y={Y1，Y2，…，Yn}间Euclidean距离的计算方法为

(8)

任务Ti实际的总完成时间为tf=tw+te+ts，即任务提交至任务完成返回结果之间的时间，其中，tw为任务提交后任务等待资源处理的时间，te为任务在虚拟机资源上执行的时间，ts为任务的传送时间.

任务Ti的期望完成时间texpt由用户根据期望值指定分配，因此，式(1)可转换为

(9)

1.5.2 网络带宽

带宽需求适合于较频繁的通信应用请求环境.本文首先根据式(7)对资源参数进行归一化处理，然后，根据式(8)计算带宽期望偏好的一般期望值向量的Euclidean距离，最后，将所调度任务映射至Euclidean距离最小的虚拟机上执行.令BWvm表示对于任务Ti从虚拟机上所获得的实际带宽，BWuser表示用户任务期望的带宽要求，因此，式(1)可转换为

(10)

1.5.3 综合一般期望效用

由于用户任务通常具有多种类型的QoS需求，所以此时需要使用综合一般期望，并从该点出发，选择与GEi拥有最小Euclidean距离的虚拟机资源作为任务Ti的执行资源.对于一般期望值初始向量的调整，可以通过定义阈值|Fi|≤1进行约束，当|Fi|>1时，系统会自动调整一般期望值.任务可通过重复调度以获取合理的一般期望向量.

1.6 算法设计

满足多重公平性约束的多QoS云任务调度算法CTS_QFC(cloud tasks scheduling QoS algorithm meeting fairness constraint)的详细过程如下：

1) 根据用户任务的QoS分类，建立用户任务的一般期望，以此作为资源分配与任务调度的公平性约束；

2) 根据参数化的用户任务特征及与其对应的一般期望约束，选择最佳虚拟机资源执行用户任务；

3) 基于以上资源分配结果计算公平性评估函数的值，并统计用户满意度和调整模型.

2 仿真实验

本节利用仿真方法测试和验证任务调度算法CTS_QFC的有效性，仿真工具选取CloudSim平台，实验主要是通过扩展CloudSim中的DataCenterBroker类的bindCloudletToVM函数实现本文的任务调度算法.将最优执行时间OCT算法与文献[4]的DRFH算法选取为比较算法，OCT算法的主要目标是以任意次序将每一个任务调度至最小完成时间的资源上执行.

2.1 实验配置

为了与任务分类保持一致，不同任务的一般期望值的初始值是给定的，第1类任务GE1={0.7，0.1，0.2}，第2类任务GE2={0.3，0.2，0.5}，三个维度分别表示CPU数量权值、内存量权值和带宽权值.

创建包括10个任务的用户任务组，具体的参数配置如表1所示.表2为一组具有不同性能和偏好的虚拟机资源参数配置.

表1 任务参数配置Tab.1 Parameters setting of tasks

表2 虚拟机资源参数配置Tab.2 Parameters setting of virtual machine resources

2.2 实验结果与分析

各算法任务完成时间如图3所示.整体看来，CTS_QFC算法的执行效率差于OCT算法，但对于任务0～4，由于对计算能力的QoS偏好，其执行时间依然短于OCT算法.DRFH算法只注重公平性而忽略了执行效率，其执行时间普遍长于本文算法.

用户满意度比较结果如图4所示.F=0表明用户获得了与期望一致的资源分配量；F>0表明用户获得了高于期望值的资源分配量；F<0表明用户没有获得与期望相符合的资源分配量.可以看出，CTS_QFC算法得到的资源分配结果更加符合用户的期望；OTC算法未考虑公平性分配问题，在任务4与7上均没有得到满足期望的资源分配；DRFH算法公平性方面强于OTC算法而弱于本文算法CTS_QFC，只有任务8上没有得到期望资源分配，主要原因在于DRFH算法仅考虑了性能较强的占优资源的公平性分配问题.

图3 任务执行时间Fig.3 Execution time of tasks

图4 用户满意度Fig.4 Satisfaction of users

图5为第1类任务0～4所获得的CPU数量的对比图.可以看出，CTS_QFC算法可以更好地满足第1类任务对计算能力的需求，以更好的公平性满足用户的QoS偏好.另外两种算法并未对任务按照QoS偏好进行分类，所分配的CPU数量只与用户任务本身的要求相关，与任务的QoS偏好是无关的，其资源分配量是随机的.

图5 计算能力偏好型任务Fig.5 Tasks of computing capacity preference

图6为第2类任务5～9所获得的网络带宽量的对比图.可以看出，该组任务对高带宽拥有更高要求，CTS_QFC算法能够更好地满足其对该类资源的需求，以更好的公平性满足用户的QoS偏好.

图6 带宽能力偏好型任务Fig.6 Tasks of bandwidth capacity preference

3 结 论

本文利用社会福利分配中公平性分配理论对云任务调度问题进行分析与研究，提出了一种满足公平性约束的云任务调度QoS算法.算法通过建立任务调度的多重公平性约束，将用户任务对QoS的偏好进行分类，并利用定义的一般期望约束评估资源分配过程的公平性，通过评估结果实时修正资源分配公平性.实验结果表明，算法不仅可以保证任务的执行效率，还可以更好地满足任务调度与资源分配的公平性约束.