，，

( 广东工程职业技术学院 信息工程学院，广州 510520)

0 引言

云计算中任务调度主要研究的是如何将合适的虚拟机调度分配给用户提交的任务使用。用户提交的任务被分割成n个子任务，形成n个子任务的排队队列，队列中的任务通过调度器发送到m个虚拟机上执行计算[1]。云任务调度就是以实时掌握云环境下虚拟机的负载状态为前提，根据云任务排队状态将虚拟机资源进行科学调度、分配，均衡各虚拟机的负载，达到云任务执行效率最高且成本低的目标。具体执行过程是：根据执行效率高的虚拟机与执行效率低的虚拟机之间的负载状态及云任务排队状态，均衡排队队列的队长，优先使用执行效率高的虚拟机，目的就是使得那些处于排队状态的任务能够得到最快响应并开始执行，从而大大缩短任务执行时间和服务成本，有效提高任务执行效率。云计算中的任务调度问题已被证明为一类Np-hard问题，传统调度算法在有效时间内得到满意解的效果并不理想，但是，通过对云任务调度问题进行建模，分析影响虚拟机服务性能的因素，获取该模型中的任务等待时间、系统资源利用率等性能指标来评估模型的综合性能。

目前，一些学者从多方面入手来求解云计算任务调度问题，但是，在云任务调度模型分析与研究并不多。参考文献[2]根据M/G/1排队论，给出了求解云任务调度的可靠性的均衡调度算法。参考文献[3]提出了一种基于M/M/n/n+r排队系统的云计算中心任务调度分析模型，求解该模型的用户请求响应时间及QoS性能指标，参考文献[4]确定了基于M/M/n排队模型的云计算资源调度模型，以降低任务服务时间和能耗为调度目标。参考文献[5]给出了一种适用于云计算服务的有效QoS约束调度方案。

不同于已有的研究工作，本文设计了一种基于M/Geom/C/∞排队系统的云任务调度模型，以虚拟机的服务可靠性为效用函数，运用排队论分析任务在虚拟机上执行的任务调度策略。该调度策略保证了排队队长较短、任务等待时间较短、平均响应时间较快，仿真结果证实了其有效性。

1 云计算中的任务调度

云计算任务调度描述：

云计算中任务调度的实质是把用户提交的任务分解为n个独立的子任务集合T={t1,t2,…tn}，并通过调度器将子任务发送到m个虚拟机vm={vm1,vm2,…vmm}上去执行，任务调度的目标是尽量让排队队列中任务的等待时间较短、响应时间较快，在虚拟机上执行时间相对较短。具体描述如下：

定义1：云任务调度系统中有k个用户，其中Ui(1≤i≤k)为第i个用户提交的任务，用户Ui提交任务的平均速率λi服从负指数分布。

定义2：对用户提交的任务进行分割，获得n个待调度的云任务队列T={t1,t2,…tn}，其中ti(1≤i≤n)为第i个子任务，这n个子任务被调度器分配到虚拟机上执行，子任务ti并行发送，每个子任务只能分配到一个虚拟机上执行。

定义3：VM={vm1,vm2,…vmm}是云环境中m个虚拟机的集合，其中m

2 基于M/Geom/C/∞排队系统的云任务调度算法

2.1 排队系统

排队问题可以描述为服务与被服务的关系，由输入过程、排队规则和服务规则这3个部分组成。输入过程是指任务到达排队系统的过程，考察的是任务到达排队系统的规律。可以用一定时间内任务到达数的概率分布或前后两个任务相继到达的间隔时间等来描述。排队规则则可采用最常见的先到者先服务模式。服务机构就是指排队系统中多个虚拟机。

L={L-c|L≥c,J=1},

W={W|L≥c,J=1}

(1)

其中:L是期望队长，系统中排队等待的任务数。W是在服务台全忙时请求服务的期望等待时间，根据上述性能指标确定服务台的平均利用率[6-7]。

2.2 排队模型描述

排队模型的选择对提高云任务调度的效率非常关键作用，它还决定了调度系统对资源的利用率。所以要根据目标与现状，加入一定的目标约束条件，设计一种适合云任务调度系统的排队模型，提高调度系统运行效能[8-10]。由于排队系统的特征，排队模型可以有许许多多的组合，本文采用M/Geom/C/∞形式表示云任务调度中的排队模型。其中：M表示任务到达间隔时间服从负指数概率分布，Geom表示服务时间服从几何概率分布，C为虚拟机台数，∞表示任务来源总体数无限。M/Geom/C/∞排队模型属于等待制排队模型，模型如图1所示。

图1 云任务调度中排队系统仿真模型

2.2.1 仿真模型组成部分

1)任务请求服务到达为固定速率λ的负指数分布，负指数分布用“M”表示，有无记忆性，即Markov性。

(2)

3)等待服务时间X服从参数p几何分布P{X=k}=(1-p)pk,0

k=0,1,…

(3)

的数学期望和概率母函数分别是：

(4)

2.2.2 模型所使用到的数量指标

3)在时刻t排队系统中恰有n个任务的概率为Pn(t)，而P0(t)为系统空闲率；

4)排队队列中平均任务数称为队长，记作L；

5)排队队列中等待服务的平均任务数称为等待队长，记作Lq；

6)任务从进入排队队列到接受完服务后离开系统的平均时间称为平均逗留时间，记作W；

7)任务在系统内排队等待服务的平均时间称为平均等待时间，记作Wq。

2.2.3 云任务调度流程

1)在M/Geom/C/∞排队系统中，任务到达间隔服从负指数分布，以{Qn,n≥0}表示时隙分点n处观察到的队长(队列中的任务数)过程。当时刻n落在某到达间隔之内时，Qn的值取决于时刻n处剩余到达间隔的长度，剩余到达间隔分布满足Markov性质；

4)kj是一个到达间隔内恰好完成j个任务的概率，{kj,j≥0}是一个概率分布，νj是到达间隔大于休假时间V，并且在休假结束后的剩余到达间隔内恰好完成j个任务的概率；

5)虚拟机服务台寿命为X，服从参数为α(0≤α<∞)的负指数分布。服务台失效后立即进行修理，其修理时间Y是任意分布。

2.3 模型分析

2.3.1 嵌入马尔可夫链

2.3.2 系统平衡条件和系统转移率阵

下面分两种情况，导出MC的转移概率：

1) 0≤i

2)i≥c,j≤c.到达间隔长为k，则在这k个时隙上必有第r个时隙。该时隙开始时，系统任务数大于c；而该时隙结束时系统有l个任务，j≤l≤c.并且在该时隙上恰好完成了m个服务，c-l+1≤m≤c.

注意到转移概率的时齐性，嵌入马尔可夫链的初始概率分布为平稳分布，因此该排队系统为平稳分布。

2.3.3 系统稳态分布

下面应用矩阵几何技术来讨论该模型的平稳结果。

而且

1) 当θ≠μ(1-δ)时，有

(5)

(6)

(7)

(8)

在系统达到统计平衡下(ρ<1)，任务到达时看到队长的平均数为

1)当θ≠μ(1-δ)时，有

(9)

(10)

2.3.4 条件随机分解结果

对于一个多虚拟机服务台排队系统，只有当所有服务台全忙时，才能充分地反映出这个系统的本质特征。对应的无休假经典M/M/C排队系统中，同名条件随机变量记为L0和W0,它们的PGF分别是

(11)

当ρ<1时，M/Geom/C/∞排队中(L-,J)的分布是

(12)

1) 当ρ<1时，M/Geom/C/∞排队中到达前夕的稳态队长L-可分解成两个独立随机变量之和：

(13)

(14)

由稳态队长的随机分解结构，容易得出下列平均队长公式：

(15)

另外，在服务台忙的条件下，讨论系统中排队等待任务数的分布。设：

Q(1)={L--1|j=1}

(16)

由常数σ的定义，有：

(17)

根据定理可得出：

P{Q(1)=j}=P{L-=j+1|J=1}=

(18)

(2) 当ρ<1时，M/Geom/C/∞系统中稳态等待时间W可分解为两个独立随机变量之和：

W=W0+Wd,

(19)

其中:W0是对应经典无休假系统中的等待时间，其分布由稳态等待时间给出；附加延迟与休假时间V同分布，有PGF:

(20)

3 算法仿真与结果分析

本节通过Matlab编程绘图，以图表的形式展示基于M/Geom/C/∞排队系统的云任务调度模型的一些稳态概率变化曲线图。

假定参数设置如下：到达率0.7个/分，服务率(0.03，0.5)个/分，平均服务时间0.6分/个，期望服务水平80%。

结合数值例子，表1给出了期望队长和期望等待时间随着服务率变化的数据，从表中也可以看出仿真系统的服务台平均利用率较高。

表1 系统的稳态指标仿真值

图2和图3分别给出了排队系统的期望队长、期望等待时间随着服务率变化的理论值与仿真值。

图2 期望队长随服务率变化的趋势

图3 等待时间随服务率变化的趋势

从图2和图3可以看出，随着服务率的增大，队长和等待时间均减小。并且从图中可以看出排队系统期望队长、期望等待时间的理论值与仿真值比较接近，验证了本文中云任务调度模型的有效性、合理性。

4 结论

本文将排队论相关知识应用于云环境下的任务调度模型分析与研究中，提出了一个基于M/Geom/C/∞排队系统的云任务调度模型。结合排队论工具对云任务调度过程的分析，利用嵌入马尔可夫链理论方法研究任务调度排队系统，寻找到既可以缩短调度过程中任务排队等待的时间，又能提高系统虚拟机资源利用率的调度方案。仿真实验得到了该模型的平稳分布及相关性能指标，验证了其有效性。

[1]胡德敏、户 静、余 星.云计算环境下基于微粒群的虚拟机任务调度算法[J].计算机测量与控制，2014，22(4)：1189-1192.

[2]王 勇，等.云环境下基于可靠性的均衡任务调度算法研究[J].计算机科学，2015，42(6A)：325-330.

[3]何怀文，等. 基于M/M/n/n+r排队模型的云计算中心服务性能分析[J].计算机应用，2014，34(7)：1843-1847.

[4]游卓浩.基于M/M/n排队模型的云资源调度策略研究[D] .成都：电子科技大学，2014，6.

[5]Lee Liangteh, Liu Kangyuan, Chiang Mingjen. An Effective QoS-Constrained Scheduling Scheme for Cloud Computing Services[J] . Journal of Electronic Science and Technology，2013，11(2)：161-168.

[6]汪 浩，黄明和，龙 浩.基于G/G/1-FCFS、M/G/1-PS和M/G/∞排队网络的Web服务组合性能分析[J].计算机学报，2013，36(1)：22-37.

[7]方 欢，陆 阳，黄镇谨，等.基于CPN仿真的排队系统建模及性能分析[J] . 系统仿真学报，2013，25(2)：228-234.

[8]Pandey S,Nepal S. Cloud computing and scientific application: Big data, scalable analytics, and beyond[J].Future Generation Computer Systems,2013,29(7):1774-1776.

[9]Zhang Qi, Cheng Lu, Boutaba Raouf. Cloud computing:state-of-the-art and research challenges[J].Internet Serv Appl,2010,6(1):7-18.

[10]Gu J, Hu J, Zhao T, et at. A new resource scheduling strategy based on genetic algorithm in cloud computing environment[J]. Journal of Computers, 2012, 7(1): 42-52.