1. 引言
云计算通过互联网为远程用户提供可靠性高且廉价的计算资源,云计算中心通常会根据不同的业务需求来配备不同的服务模式进行数据传输和任务处理,例如一些用户需要在特定的时间内使用资源,而其他用户则对时间的要求不严格。根据云计算中心的服务等级协议(SLA)给用户赋予优先级,以保证高优先级用户的服务质量(QoS)。WHITE [1] 最早提出了抢占优先权排队系统。RAO [2] 研究了在非抢占优先权下的(M1 + M2)/G/1排队模型,得出稳定性条件。GAIL等 [3] 研究了具有多个服务台和两类优先权顾客的排队模型,并给出了两类顾客的分布表达式。徐秀丽 [4] 研究了带可变服务率和启动期的M/M/1休假排队模型。徐秀丽 [5] 研究了带(e, d)休假策略的M/M/c排队模型。郭闪闪 [6] 研究了带抢占优先权的排队系统,给出顾客的平均逗留时间等性能指标,建立收益函数并通过数值试验寻找最优参数。SI [7] 等研究了具有不耐烦顾客、服务台故障可修的M/M/c排队模型。
在互联网和信息技术不断进步的今天,各行业的计算资源都开始转移到云计算中心,用户对云计算中心性能需求的增长与系统能耗成本之间的矛盾日益凸显。为了满足用户的请求并能够获得最大的利润,许多学者将休假排队理论运用到云资源节能策略中。SAHOO和GOSWAMI [8] 提出了基于休假排队的虚拟机(VM)唤醒和休假策略。李吉良等 [9] 研究了半休眠模式下带唤醒阈值的VM调度策略,通过数值分析评估VM调度策略的系统性能。金顺福 [10] 等研究了基于唤醒阈值和休眠定时器双重控制的VM分簇调度策略,建立了带有(N,T)策略的多重休假排队模型,有效节约系统能耗。GUO等 [11] 研究了云任务随机到达且带有任务延时的VM调度问题。MA等 [12] 研究了同步休眠模式和异步休眠模式相结合的VM调度策略。JIN等 [13] [14] 研究了具有多种睡眠机制的VM调度策略以及带有唤醒阈值的集群VM分配策略,建立带有N策略和部分服务台异步休假的M/M/c排队模型进行建模分析。LI和JIN [15] [16] 研究了带有抢占优先权用户的多服务台排队模型和带有异构边缘MEC系统的云任务卸载策略。CUI等 [17] 研究了基于半休眠机制和可变服务率的云系统动态节能策略。
在上述研究的基础上,考虑到云计算中心为了根据不同的业务需求而提供不同的服务,为了保证高优先级顾客的Qos,引入优先权策略。同时引入c台VM同步半休眠策略以减少系统空闲时的能耗。最后考虑到VM的内存空间是有限的,过多的用户请求会导致内存溢出,因此设低优先级顾客的等待空间是有限的。建立一个带抢占优先权和服务台同步工作休假的M/M/c排队模型,推导出两类顾客的平均队长,内存溢出率、系统总能耗等稳态性能指标,并建立相应的系统收益函数,分析参数对稳态性能指标和系统收益的影响。
2. 模型描述
2.1. 用户到达规则
针对云计算中心的运行机制,将用户每一次对服务器进行访问的行为当作一次任务到达过程,根据云计算中心的SLA,本文将用户分为高优先级顾客(第一类顾客)和低优先级顾客(第二类顾客)。模型中假定两类顾客分别在两个缓冲器中各自排队,并设两类顾客的到达时间间隔分别服从参数为
和
的负指数分布。考虑到VM的内存空间是有限的,过多的用户请求会导致内存溢出,因此设第二类顾客的等待空间
是有限的。
2.2. 队列优先权控制规则
为了保证高优先级顾客的QoS,设第一类顾客具有抢占优先权,抢占规则为当第一类顾客到达系统后,如果系统中无空闲VM则抢占正在为第二类顾客服务的VM,第二类顾客将回到自己队列的首部位置重新等待服务。设两类顾客的服务时间分别服从参数为
和
的负指数分布。
2.3. 虚拟机休眠规则
针对虚拟机休眠策略,本文引入c台VM同步半休眠策略。即当c个VM均空闲时,系统将进入半休眠状态。若在半休眠状态内有新顾客的请求,则VM就会以较低的服务率来服务顾客,待半休眠状态结束时变成以正常的服务率来服务顾客;若半休眠状态结束时系统中仍无新顾客的请求,则进入下一个半休眠状态。设系统休眠长度服从参数为
的负指数分布,两类顾客在半休眠状态的服务时间分别服从参数为
和
的负指数分布。假设系统中两类顾客的到达时间、服务时间均相互独立,且均服从先到先服务FCFS的服务规则。
3. 模型建立与分析
3.1. 拟生灭过程
根据模型描述建立具有抢占优先权的M/M/c工作休假排队系统,设
和
分别表示高优先级顾客和低优先级顾客在时刻t的请求数。令
则
构成一个三维拟生灭过程,其状态空间为
考虑高优先级顾客,其状态0包含如下水平:
,状态i包含如下水平:
,将状态按字典序排列,无穷小生成元
如下
其中
为
阶方阵,
为
阶方阵,
为
阶矩阵,
为
阶方阵,
为
阶矩阵,
为
阶方阵。且
其中
其中
其中
3.2. 系统稳态性能分析
对系统的稳态性进行验证,令
是有限不可约生成元,
为
的平稳概率向量,其中由文献 [18] 可知系统存在稳态分布的条件为
。将
代入
中,可得到当
时,MarKov过程
是正常返的,即稳态分布存在。系统稳态分布可以表示为:
记稳态概率向量为
由拟生灭过程与矩阵几何解方法可知,求解系统稳态分布需要先求出矩阵方程
的最小非负解
,且谱半径
,同时
维矩阵
有左零向量,且稳态分布满足如下方程组
(1)
(2)
(3)
(4)
(5)
(6)
其中
为全1列向量。
然而高阶矩阵方程
很难直接求出率阵
的表达式,下面采用Neuts [18] 给出的迭代算法来求解率阵
。为保证算法的收敛性,给出算法的精度
,当
时,得到
的近似解,具体迭代步骤如下
Step 1:对系统的参数
,定义初始值,设置精度
,初始化率阵
Step 2:输入
Step 3:定义
Step 4:如果
则返回Step 3,否则进入Step 5
Step 5:
通过上述算法求解出率阵
后,由(1)~(6)可得到如下递推方程
(7)
(8)
(9)
(10)
(11)
由(7)~(11)可以递推地求出稳态概率向量。
4. 系统稳态性能指标
基于系统的稳态分布,得到在抢占优先权和同步半休眠模式下VM调度策略的稳态性能指标:
1) 第一类顾客的平均队长
2) 第二类顾客的平均队长
3) 服务台的利用率
4) 内存溢出率
5) 处于工作状态和半休眠状态的VM的总能耗
其中一台VM在工作状态时的能耗为W1,在半休眠状态时的能耗为W2,两类顾客在缓冲器中排队等待的能耗为W3。
5. 数值分析
在实际背景中,系统各稳态性能指标常因参数的变化而有所不同。本节通过数值模拟研究各参数对系统稳态性能指标的影响,令
。
见图1研究了第二类顾客的平均队长
与
和c的变化关系。当
时且
时,系统中为第一类顾客服务的VM数较多,第二类顾客接受服务的机会较小,
随
的增大而增大。当
时且
时,随着第一类顾客服务率的增大,第二类顾客接受服务的机会增大,
随
的增大而减小。当
或
时,
随
的增大而减小。当
一定时,VM数的增大使得第二类顾客接受服务的机会增大,
随c的增大而减小。
见图2研究了服务台利用率
与
和c的变化关系。当
时,c台VM均处于为顾客服务的状态,服务台的利用率为1。当
或
时,随着第一类顾客服务率的增大,顾客在系统中的平均逗留时间越小,
随
的增大而逐渐减小。当
一定时,VM数的增多使得顾客接受服务的机会增大,
随c的增大而减小。系统应适当调整VM数和服务率来实现队长、服务台利用率的优化。
Figure 1. The change of
with respect to
and c
图1.
随
和c的变化关系
Figure 2. The change of
with respect to
and c
图2.
随
和c的变化关系
见表1研究了在
的条件下,内存溢出率
与N和
的变化关系。当N一定且
较小时,第二类顾客接受服务的机会较少,发生内存溢出的概率增大。当N一定且
较大时,第二类顾客接受服务的机会增大,因此
随
的增大先增大后减小。当
一定时,N越大系统可以容纳的第二类顾客数越多,发生内存溢出的概率减小,因此
减小。系统可以通过适当调整系统容量和服务率来减少内存溢出。
Table 1. The change of P l with respect to N and μ 1
表1.
随N和
的变化关系
见图3研究了内存溢出率
与
和c的变化关系。当
时且
时,系统中为第二类顾客服务的VM数较少,系统中等待的第二类顾客数增多,发生内存溢出的概率增大,
随
的增大而增大。当
时且
时,第二类顾客接受服务的机会增大,发生内存溢出的概率减小,
随
的增大而减小。当
或
时,
随
的增大而减小。当
一定时,数数的增大使得第二类顾客接受服务的机会增大,
随c的增大而减小。
见图4研究了在
系统总能耗W与
和c的变化关系。当c一定时,
增大使系统中第二类顾客在缓冲器中排队等待的能耗减少,因此W随
的增大而减小。当
一定时,VM数越多,系统总能耗增加,因此W随c的增大而增大。
见表2研究了在c台VM同步半休眠策略下,半休眠参数
对系统总能耗W的影响,随着半休眠参数
的增大,VM处于半休眠状态的时间越短,系统总能耗W随
的增大而增大。当
一定时,系统中处于正常工作状态或者半休眠状态的VM数越多耗能就越大,因此系统总能耗W随VM数的增大而增大。系统应适当调整VM数和工作休假参数来实现系统总能耗的优化。
Figure 3. The change of
with respect to
and c
图3.
随
和c的变化关系
Figure 4. The change of W with respect to
and c
图4. W随
和c的变化关系
Table 2. The impact of system parameters ξ and c on W
表2. 系统参数
和c对W的影响
6. 系统收益优化
根据云数据中心服务一位顾客就会得到一份收益,设R1和R2分别表示服务完一位高优先级顾客和一位低优先级顾客所获得的收益,C1和C2分别表示高优先级顾客和低优先级顾客在系统内单位逗留时间所花费的成本,C3表示系统单位能耗所带来的损失,C4表示因内存空间有限所造成的内存溢出的损失。从社会的角度考虑整个系统,定义系统收益Us为系统中第一类顾客和第二类顾客完成服务后所获得到的总收益再减去因系统能耗和内存空间有限所造成的内存溢出的损失,具体表达式如下:
见图5研究了在
的条件下,系统收益Us与
和c之间的关系。当
且
时,系统中第二类顾客的平均队长增加,发生内存溢出的概率增大且因内存溢出所造成的损失增加,因此Us随
的增大而减小。当
且
时,第二类顾客因被抢占VM而终止服务的概率减小,系统因服务完更多地顾客而获得了更多地收益,因此Us随
的增大而增大。当
或
时,Us随
的增大而增大。当
(
)一定时,Us随c的增大而减小。当
(
)一定时,VM数为5时Us最大。
见图6研究了在
的条件下,系统收益Us与
和N之间的关系。当
一定时,第二类顾客的等待空间N越大,发生内存溢出的概率就越小,因此Us随N的增大而增大。当N一定时,发生内存溢出的概率先增大减小,所造成的损失相应的先增大后减小。
见表3研究了在
,系统收益Us与N和
之间的关系,当N一定,随着
的增大,第二类顾客在系统中的平均逗留时间减少,系统服务的顾客数增多,因此Us随
的增大而增大。当
(
)一定时,第一类顾客具有抢占优先权且第二类顾客的服务率较小,使得第二类顾客接受服务的机会较小,
Figure 5. The change of Us with respect to
and c
图5. Us随
和c的变化关系
Figure 6. The change of Us with respect to
and N
图6. Us随
和N的变化关系
顾客在系统内因逗留时间过长导致系统成本增加,因此Us随N的增大而减小。当
(
)一定时,服务率较大使得第二类顾客在系统中平均逗留时间较小,且内存空间N的增大使得第二类顾客有更多的机会接受服务,且因内存溢出所造成的损失减少,Us随N的增大而增大。因此在第一类顾客的服务率一定的情况下,系统应当适当扩大内存空间和提高第二类顾客服务率,使得系统收益增多。
Table 3. The impact of system parameters N and μ 2 on Us
表3. 系统参数N和
对Us的影响
7. 结论
本文基于所提出的VM同步半休眠策略,研究了一种基于抢占优先权且服务台同步工作休假的M/M/c排队模型。通过对系统进行描述,建立了三维Markov过程,得到其拟生灭过程及无穷小生成元矩阵,采用拟生灭过程理论求解出系统的稳态分布,得出系统中两类顾客的平均队长、内存溢出率、系统总能耗等稳态性能指标,并通过数值模拟讨论系统稳态性能指标随参数变化的关系,研究c台VM同步半休眠策略对系统总能耗的影响。最后,建立系统收益函数,研究参数对系统收益函数的作用规律。从而在保证两类顾客服务质量的前提下,通过适当调整VM数、内存空间和服务率增加系统收益。