基于生产函数的云计算QoS任务调度算法

2022-08-15邓斌涛徐胜超

吉林大学学报(信息科学版) 2022年2期

邓斌涛, 徐胜超

(广州华商学院数据科学学院, 广州 511300)

0 引言

云计算通常由可动态伸缩资源构成, 可采用虚拟化技术将动态可伸缩资源传送给云计算系统的用户[1]。系统中的用户根据自身需求通过网络获取云计算资源, 降低用户终端在系统中的处理负担, 提高系统的计算能力[2]。云计算具有许多优点被广泛应用, 云计算系统通常存在自身的任务调度和资源分配策略, 但对其还没有准确的标准和规范[3]。目前云计算QoS任务调度算法存在用户满意度和调度效率较低的问题, 因此需要对云计算QoS任务调度算法进行分析和研究[4]。

李昆仑等[5]提出基于距离和共生演算法的任务调度算法。该算法通过模糊聚类算法对云计算中的资源和任务进行重排序放置, 在属性相似度的基础上指导分配任务, 缩小选择资源的范围, 通过学习和交叉机制对共生演算法进行改进, 采用加权求和方法建立驱动模型, 实现云计算QoS任务的调度。但该方法得到的调度结果不满足用户的需求, 存在用户满意度低的问题。田泰方等[6]针对雷达资源管理中的图像任务调度、时间孔径等问题, 提出了基于时间-孔径二维资源管理的雷达资源调度算法。该算法建立了雷达站孔划分的二维资源规划模型和能量资源约束；采用基于压缩孔径传感的逆合成孔径雷达成像技术, 在进行目标搜索和跟踪任务时, 利用该技术获取目标图像。但该算法中包含大量的算法, 计算所用的时间较长, 存在调度效率低的问题。陈暄等[7]对基于IFOA-GA(Improved Fruit Fly Optimization Algorithm-Genetic Algorithm)任务调度算法在云计算MapReduce模型中的应用进行了研究, 提出了采用改进的果蝇和遗传算法融合的算法用于处理任务调度, 但该算法构建的任务模型精准度较低, 存在用户满意度低的问题。为解决上述方法中存在的问题, 笔者提出基于生产函数的云计算QoS任务调度算法。

1 基于生产函数的任务调度目标函数

用户将提交请求传送到云计算系统中的云代理, 获取云计算系统中存在的资源。云计算系统中存在用户需要的网络带宽、存储和计算资源CPU(Central Processing Unit)等[8]。

设ti为云用户i对应的请求, 其表达式如下

ti={w,Si,ci,mi,bi,…}

(1)

其中w为标志字段；mi为用户请求i在云计算系统中申请的存储资源量；bi为用户请求i在云计算系统中申请的带宽资源量；Si为用户请求对应的期望报价；ci为用户请求i在云计算系统中申请的计算资源CPU。

通常由不同的云计算中心组成云服务器, 设D为其数据中心, 其表达式如下

D={1,2,…,k,…,n}

(2)

设Sj为数据中心中存在的资源, 其表达式如下

Sj={cj,pjc,mj,pjm,bj,pjb,…}

(3)

其中j∈D；cj为数据中心j中存在的计算资源量；pjb为数据中心j中带宽资源对应的成本价；pjc为计算资源在数据中心j中的成本价；bj为数据中心j中存在的带宽资源量；mj为数据中心j中存在的存储资源量；pjm为存储资源在数据中心j中对应的成本价。

假设带宽资源在云计算系统中充足, 内存资源和计算资源是用户请求的重点[9]。基于生产函数的云计算QoS任务调度算法引入生产函数, 在其基础上构建云计算QoS任务调度模型。

定义函数Y(c,m), 其表达式如下

Y(c,m)=acαmβ

(4)

在α+β=1的条件下将式(4)转化为

Y(c,m)=acαm1-α

(5)

其中Y(c,m)为总产值；c为投入云计算中的计算资源量；a为数据中心对应的综合业务能力；α为计算资源在云计算系统中对应的弹性系数；β为投入存储资源在云计算系统中对应的弹性系数；m为投入云计算系统中的存储资源量。参数a、α、β描述数据中心对应的服务能力, 不同数据中心D={1,2,…,k,…,n}对应的参数a、α、β都不相同。

设Y0为数据中心对应的维护成本, 假设一个数据中心在云计算系统中支付的维护成本是固定的, 投入资源量会对维护成本产生影响[10]。构建保证数据中心收益最大化的目标函数

(6)

(7)

设t为拉格朗日乘子, 通过t构建拉格朗日方程

N(c,m,t)=Y(c,m)+t(Y0-ωc-λm)

(8)

通过式(8)得到数据中心在云计算系统中的最优资源配置组合(c,m)。通过虚拟机vmj(c,m)的形式将资源配置传送给云计算新系统的云用户, 最大化数据中心在云计算系统中的收益[12]。

在每个数据中心采用执行资源配置算法可建立虚拟机vmj(cj,mj), 最大化云计算提供方的利益。通过用户请求ti={w,Si,ci,mi,bi,…}和价格pj定义数据中心j在云计算系统中请求的虚拟机总数nj, 有

取临界值, 存在多个解, 通过不同的数据中心构建vm个虚拟机, 组成集合u={n1,n2,…,nj,…}, 并将其传送到系统的云代理中, 建立响应时间和用户效用、虚拟机方案之间的关系, 并将其作为指标对用户的满意度进行判断[13]。

基于生产函数的云计算QoS任务调度算法在效用利用率的基础上构建与获取资源和用户报价相关的用户效用函数。

用户向系统传输请求的同时也会向系统提交报价, 作为报价约束条件, 设获取资源量和用户满意度之间成正比, 其表达式如下

(12)

其中U为效用函数,t为响应时间。

在用户期望报价的约束条件下, 构建云计算QoS任务调度目标函数

(13)

2 云计算QoS任务调度算法

基于生产函数的云计算QoS任务调度算法采用离散粒子群优化算法对云计算QoS任务调度目标函数进行求解, 实现云计算QoS任务的调度, 具体步骤如下。

1) 设NP为种群规模； [ωmin,ωmax]为惯性权重范围；Imax为最大迭代次数；c1、c2为学习因子, 对上述参数进行初始化处理。

2) 通过正态分布的方式在约束范围内对可行粒子进行初始化处理, 并获得可行粒子对应的速度和位置, 确定全局最优解gbest和局部最优解pbest[14]。

3) 根据任务调度目标函数以及调度预算和截止时间约束, 获得云计算QoS任务调度问题的描述表达式

(14)

(15)

其中eij为计算节点rj中执行任务需要的时间；di为任务云计算系统中的截止时间；pj为计算节点rj过程中每秒对应的使用成本；Rresj(i)为节点rj对应的可靠性；R(i,j)为最大化任务调度对应的可靠性。如果满足粒子任务与调度预算和截止时间存在关联性的条件, 则认为是可行的, 当不符合时, 粒子无法计算, 以此减少计算所用的时间[15], 通过反复迭代和筛选形成了可行域Ω。

根据上述分析, 获得适应度函数Fit(x)的表达式

(16)

4) 通过

vi=ωvi+c1r1(pbesti-xi)+c2r2(gbesti-xi)

(17)

对粒子的速度进行更新。其中r1、r2为区间[0,1]内的常数；学习因子c1用于描述粒子向pbest靠近的程度；学习因子c2用于描述粒子向gbest靠近的程度。

5) 通过

xi=xi+vi

(18)

(19)

对粒子的位置进行更新。

6) 当迭代次数与最大值Imax相等时, 进行下一步, 否则返回步骤3)。

7) 输出全局最优解gbest和局部最优解pbest, 获得最优的云计算QoS任务调度方案, 完成云计算QoS任务调度。

3 实验结果与分析

为验证基于生产函数的云计算QoS任务调度算法的整体有效性, 需要对基于生产函数的云计算QoS任务调度算法进行测试, 测试的实验环境为Intel core2 Duo 2.33 GHz处理器, 操作系统为Windows XP。

分别采用基于生产函数的云计算QoS任务调度算法(方法1)、基于距离和共生演算法的任务调度算法(方法2)和基于IFOA-GA(Improving Fruit Fly Optimization Algorithm Genetic Algorithm)的任务调度算法(方法3)进行测试, 对比3种不同算法对任务调度后, 用户的满意度测试结果如图1所示。

图1 3种不同算法的任务满意度

分析图1可知, 采用基于生产函数的云计算QoS任务调度算法对任务调度后, 在多次迭代中用户的满意度均在90%以上, 高于基于距离和共生演算法的任务调度算法和基于IFOA-GA的任务调度算法对任务调度后用户的满意度。因为基于生产函数的云计算QoS任务调度算法在获取资源和用户报价相关效用函数的基础上构建了云计算QoS任务调度目标函数, 提高了用户的满意度。

为进一步验证基于生产函数的云计算QoS任务调度算法的整体有效性, 分别采用基于生产函数的云计算QoS任务调度算法(方法1)、基于距离和共生演算法的任务调度算法(方法2)和基于IFOA-GA的任务调度算法(方法3)进行测试, 对比3种不同算法的任务调度时间, 测试结果如图2所示。

图2 3种不同算法的任务调度时间

分析图2可知, 在多次迭代中采用基于生产函数的云计算QoS任务调度算法调度任务所需的时间均少于基于距离和共生演算法的任务调度算法和基于IFOA-GA的任务调度算法调度任务所需的时间。因为基于生产函数的云计算QoS任务调度算法判断粒子是否符合调度预算和截止时间的约束条件, 不符合即为不可行粒子, 丢弃不可行粒子, 减少计算量, 缩短了任务调度所需的时间, 提高了基于生产函数的云计算QoS任务调度算法的调度效率。