基于离散事件系统的云资源分配优化控制

胡　芹，刘富春

(广东工业大学 计算机学院，广东 广州 510006)



基于离散事件系统的云资源分配优化控制

胡芹，刘富春

(广东工业大学 计算机学院，广东 广州 510006)

摘要:如何对资源进行合理有效的分配一直是云计算领域的热点问题.由于传统的云资源分配算法不能有效屏蔽底层硬件资源的异构化以及不同层的云服务类别，本文提出一种多参数资源打包的方法，构建出基于离散事件系统的云资源分配控制模型，并给出了合理的资源分配算法.算法通过计算服务器端各资源包容量参数与客户端资源需求量参数的贴近度来定义资源分配事件，并对事件发生与否的状态实行分层控制，最终使得整个资源分配系统到达可接受状态.实验表明，基于离散事件系统的云资源分配模型，能够保证在可接受状态下，不仅每个用户的资源请求能够得到合理的分配，且能实现云资源利用率最大化.

关键词:云资源分配； 离散事件系统； 资源包； 资源利用率

云计算[1-2]为用户提供灵活的计算能力和高效的数据存储能力，云资源分配将用户请求的虚拟机分配给各个底层物理机去处理[3]，由分布在不同地方的物理机提供用户所需的资源，满足用户请求的执行条件.在云环境下，资源分配的效率显得非常重要，其对云平台系统的综合性能影响很大.当前，云计算下的资源分配已经进行了大量的研究，已经投入使用的著名的MapReduce调度模型[4]，通过3种角色(Master、Worker、User)的分工协作，能高效地为用户请求分配合适的计算资源；文献[5]提出了基于粒子群优化算法的云资源分配，采用进化算法原理，依据用户需求大小来适当地分配资源量；文献[6-9]提出了基于Qos(Quality of service)任务分配和蚁群算法的资源分配与任务调度算法，先采取Qos算法，将不同的资源请求分类处理，再利用蚁群算法得到一组最优的计算资源.文献[10]分别研究了在分布式DES(Discrete Event Systems)监控和协调器协调监控中的两类具体问题：作业调度问题TAP(Task Allocation Problem)、最少干预问题MIP(Minimal Intervention Problem)；文献[11-14]研究了基于模拟退火的蚁群算法求解网格任务调度问题；文献[15]研究了云环境中面向随机任务的用户效用优化模型.然而以上研究都没有考虑具体的资源分配模型.本文将成熟的离散事件系统(DES)的控制理论应用到资源分配上，基于有穷自动机的资源分配的基础，建立了DES云资源控制模型.将所有资源分配事件都看作是可控事件，通过控制可控事件的发生与不发生，保证提高资源利用率的事件有效发生.将用户请求的虚拟机准确分配到具体的资源包，通过资源参数值与任务对应参数值的对比，调整资源分配，在满足资源利用率最大的同时，可以实现有效的资源分配.

1云资源分配模型

云资源分配是一个NP(Non-deterministic Polynomial)难问题，到目前为止还没有确切的资源分配模型，但是存在对资源分配的多种优化算法，一些启发式算法将云资源分配问题转换为NP难优化问题[16-17].本文建立合理的DES资源分配模型，在该模型中，云计算数据中心是由大量的异构的计算资源构成的云资源池，这些海量的资源均是客户端请求执行所必须的，如CPU、内存、存储空间、防护服务、服务器、带宽等.考虑到基本的云计算三层结构模型，在每一层中，云提供服务可以抽象为“XaaS”，如基本架构即服务“IaaS(Infrastructure as a Service)”,平台即服务“PaaS(Platform as a Service)”，软件即服务“SaaS(Software as a Service)”.为了屏蔽不同层的服务类别，本文将资源池的资源看作为容量不一的资源包，每个资源包中含有多种不同资源，将不同类别资源表征为该资源包具有的不同参数，如参数1为CPU数量，参数2为存储容量，参数3为带宽等等.同理，用户任务请求所需资源类别也进行参数化处理，如某一个任务，所需要资源配置的参数1、参数2、参数3、…分别为完成该任务所需要的CPU、内存、存储空间、…的资源量.如此，每一层的服务对所有用户都是透明的，用户只需要申请和使用所需的资源即可，不需要关心资源是如何分配的.

资源包含有的资源以及任务请求资源情况均可以用一个n×m阶矩阵表示，具体表示如下：

(1)

在资源分配过程中，要求任务请求的各个参数资源总量不得超过资源包中各个参数资源的资源总量，且资源包各个参数资源总量不得超过资源池中该类资源的资源总量，即要求满足

(2)

初始化资源分配调度也是一个n×m阶矩阵，为

其中，A[Tx,Py]∈{0,1}，值为1表示第x个任务获得了第y个资源包的资源，为0则表示没有获得.当为任务请求分配资源时，要求保证每个任务都可以分配一个确定的资源包，一个包可以被多个任务共享.因此，资源分配矩阵中的每一行有且只有1，每一列存在一个或者多个1.

云资源分配的最理想状况是任务群被分配的总资源量等价于资源池中的总资源量，即

然而，这种理想的状态目前尚不能达到，因为存在部分资源不能完全被利用.若要实现分配之后的各个资源包的资源参数能够最大限度地满足任务需求的各个参数的资源量，求出资源包的容量值与用户请求资源的容量欧氏距离距离越小，表明资源包容量与用户请求资源量的贴近度越大.对于任意给定的x∈N，要得到最大的贴近度，即找出唯一y∈N，存在

D(x,y)=min{D(x,y)|x,y∈N},

D(x,y)=

(3)

则返回资源分配结果，令

为了达到资源的最优分配，要求满足所分配的资源包能够得到最大化利用，即利用率之和最大.

(4)

2构造DES控制模型

构造资源分配系统的DES控制模型，设系统Φ={Q,Σ,δ,q0,qa}，状态集Q={q0,q1,…,qk}，qi={∃i∈N,P1∪P2…∪Pi}表示在该状态下，存在一个或多个资源包以供选择；事件集Σ为并行执行的任务T串，如{Ti},{TiTj},{TiTjTk},…；转移函数δ:Q×Σ*→Q，当为某个用户任务分配资源包之后，系统跳转到另一个状态；q0,qa∈Q，q0={∀i∈N,P1∪P2…∪Pi}表示系统的起始状态，在起始状态，任意的资源包都可供选择，qa为资源分配系统的接受状态，在该状态下，所有等待的用户请求都可以获得资源包，且资源包的利用率最大.

对于该资源分配系统，资源分配事件L⊆Σ*分为可满足事件Lc、不可满足事件Lu和可接受事件La.其中可满足事件

表示只有在当前状态中的某个确定的资源包参数能够满足该事件串中的所有事件的子串所对应的资源需求量，该事件才是可满足的；不可满足事件

表明存在某个资源包的参数不能满足对应请求的资源参数，显然，以Lu为子串的所有事件串均为不可满足事件；可接受事件

La={∀Tj∈s:max(U)}⊆Lc的发生能够满足资源包的最大化利用.

在该资源分配系统中，一个资源包可以同时满足多个用户请求，资源包和用户请求之间是一对多的关系，所有可满足事件的发生都可以是并行的.由于在并行状态下的多个事件串的发生，不具有可观性；又由于每个用户请求只能被一个资源包服务，资源包与任务请求之间不具有交叉性，因此，在该分配模型中，可以考虑系统中资源包分配的串行执行情况，分别考虑当前状态中每一个资源包在各个事件串发生后的状态.最后通过分析比较，确定可接受事件串，控制不可满足事件的不发生，以及控制可接受事件的发生来确保系统资源利用率最大化.

系统初始状态包含所有未被分配的资源包，考虑资源池中的每一个资源包Pm，假设某个事件是可满足事件，则考虑该可满足事件的扩充串(enlarge语言)，直到找出在该资源包下最大的可满足事件Lc，并修改状态集Q中Pm的参数，其他资源包保持不变，若Ti是属于该可满足语言，则将Pm资源包分配给任务Ti，修改事件集Σ′=Σ-Ti,使得已经获得资源包的用户请求退出缓冲池，接下来考虑包Pn(n≠m)，转移函数δ:Q×Σ′→Q，直到所有任务都可以得到分配.假设系统存在2个资源包P1,P2，3个任务T1,T2,T3,如图1所示，在q0状态下考虑资源包P1，若任务事件T1属于可满足事件，接下来考虑事(81.5件T1T2,T1T3,T1T2T3是否为可满足事件，即判断Σ*中所有包含可满足事件T1的所有串是否仍为可满足事件，找出包含T1的最大可满足串；接下来判断，若事件T2不属于可满足事件，即状态4不存在，则不用考虑包含T2的事件串，即不会出现状态q5.

图1　某个资源包下的状态迁移

确定各个资源包的可满足事件串，若Ti,Tj,…,Tt⊂Lc根据式(3)可得Lc与资源包Py的参数贴近度，资源参数距离D(Lc,y)越小，表明参数贴近度越大.

(5)

3算法实现

输入：任务请求队列T、资源池P；

输出：资源分配矩阵A.

执行：

1) 初始化资源分配控制系统起始状态

根据式(1)初始化请求队列T、资源包P;

确定起始状态q0；

2) 定义可满足事件集

For所有资源包Py，

For任意的事件集

L={T1∪T2∪…∪Tm.

If不等式(2)成立，

L属于Py的可满足事件集Lc；

ElseL属于Py的不可满足事件集Lu；

3) 计算可满足事件串资源与资源包的距离

对任意的资源包Py，

For(y=1;y

For(∀Li∈Lc)

根据等式(4)，求得Py与Li的距离D值.

4) 根据距离D，确定分配方案

For任意的Py，存在min(Py,Li)，

Else If∃Lk⊂Lc,Tx⊂Lk存在且

min(Pj,Lk){j≠y,Lk∩Li=φ，

将Tx分配给Pj，令

5) 计算资源利用率，定义可接受事件

根据等式(3)，计算资源利用率U，定义可接受事件为满足Umax的任务串；

6) 返回分配矩阵A

控制可接受事件的有效发生，得到最佳分配矩阵A.

4仿真实验

本文给出一个云资源分配的子系统，该系统中资源池中有5种资源R1、R2、R3、R4、R5，分别是CPU、存储空间、内存、服务器、带宽的容量.存在3个资源包P1、P2、P3，5个用户请求T1、T2、T3、T4、T5.资源包参数分配情况如表1所示，用户任务请求资源参数分配情况如表2所示.

表1　资源包参数分配情况

表2　用户请求资源参数分配情况

首先，考虑在先来先服务(First Come First Service， FCFS)算法下的云资源分配情况，假设任务请求的顺序是T1→T2→T3→T4→T5，根据FCFS算法，T1将最先获得资源分配，根据先后顺序类推，T5最后获得资源分配.当T1到达时，满足各个资源参数条件的资源包有P1,P3，将T1分配给P1；当T2到达时，将其分配给P2，同理得出分配矩阵

在此示例中，先来先服务算法，虽然可以实现资源分配，但是先来先服务算法存在一个很大的弊端，其没有从全局的角度出发，先到达的任务很有可能占用了一部分资源，使得缩减之后的资源包不能满足后到达的任务，从而导致一些请求始终得不到资源分配.接着，考虑本文的基于离散事件系统的云资源分配算法，在q0状态，依次考虑事件集Σ中最小子串在各个资源包下是否为可满足事件，考虑资源包P1下，事件T1、T2、T3、T4、T5均为可满足事件；在资源包P2下，可满足事件为T2、T5；在资源包P3下，可满足事件为T1、T2、T3、T5.如图2～图4所示.

图2　在资源包P1下的可满足最小事件

图3　在资源包P2下的可满足最小事件

图4　在资源包P3下的可满足最小事件

依次考虑每个可满足事件的扩充(enlarge)串，找出在各个资源包下分配多个任务的可满足事件串，若资源包Pi不能同时满足n个任务串，则不用再考虑其是否满足(n+1)个任务串，资源分配情况如图5～图7所示.

图5　在资源包P1下分配2个任务的可满足事件

图6在资源包P2下分配2个任务的可满足事件

Fig.6Satisfiable event of allocating two tasks under

Resource PacketP2

图7　在资源包P1下分配3个任务的可满足事件

在资源包P2下已经不存在可以分配3个任务的可满足事件，则不用再考虑.本文列出所有可满足事件，并根据式(5)求出距离D的值，如表3所示.

根据资源控制分配算法，在所有可满足事件串中，找出符合条件的可接受事件串.在资源包P1下存在最小D值的可满足串是T1T2T4，假设将P1分配给T1T2T4,在P2中将不再考虑T1T2T4，此时存在最小D值的可满足事件串为T5，在P3不考虑任务T1、T2、T4、T5，存在最小D值的可满足串为T3,假定方案一为将P2分配给T5，P3分配给T3.同理，考虑资源包P2、P3、P4、P5的可满足串，最终可得出两个分配矩阵

表3　该资源分配系统中所有可满足事件

根据式(4)求出资源利用率UA1=1.463 2,UA2=1.317 2，由于UA1>UA2，分配矩阵A1的资源利用率较大，取A1为最优分配.定义P1下的事件串T1T2T4为可接受事件，同理，P2下的T5以及P3下的T3也定义为可接受事件，控制可接受事件的有效发生，能实现资源的最优分配.

本文基于离散事件系统的云资源分配控制算法，从全局的角度定义出所有资源分配的可满足事件和可接受事件，通过对可满足事件的梳理以及控制可接受事件串的有效发生，不仅有效避开了FCFS算法陷入僵局的弊端，也保证了资源的利用率，是一个可行且有效的算法.

5结语

本文提出基于DES的云资源分配优化控制策略，通过将资源参数化，形式化描述资源的优化分配过程，有效将离散事件系统控制理论应用到云资源分配模型中，保证提高资源利用率的事件有效发生，满足资源利用率最大的同时实现最快最有效的分配.

参考文献：

[1]MELL P, GRANCE T. The NIST definition of cloud computing 800-145[S]. Gaithersburg,MD: National Institute of Science and Technology,2010,53(6):50-50.

[2] 刘鹏.云计算[M].北京:电子工业出版社,2010.

[3] 王笑宇,程良伦. 云计算下的多源信息资源云体系及云服务模型研究[J].计算机应用研究,2014,31(3):784-788.

WANG X Y, CHENG L L. Study of multi-source information resources cloud systems and cloud services model on cloud computing[J]. Application Research of Computers,2014,31(3):784-788.

[4] XIONG K Q, HE Y X. Power-efficient Resource Allocation in MapReduce Clusters[C]∥Integrated Network Management(IM 2013),IFIP/IEEE International Symposium. Ghent:IEEE,2013:603-608.

[5] CHEN Y M, TSAI Shin-Ying. Optimal provisioning of resource in a cloud service[J]. IJCSI International Journal of Computer Science Issue,2010,7(6):95-99.

[6] CALHEIROS R N, RANJAN R, BUYYA R. Virtual machine provisioning based on analytical performance and QoS in cloud computing environments[C]∥Parallel Processing(ICPP),International Conference. Taipei City:IEEE,2011:295-304.

[7] 华夏渝,郑骏,胡文心.基于云计算环境的蚁群优化计算资源分配算法[J].华东师范大学学报(自然科学版),2010,1(1):127-134.

HUA X Y, ZHENG J, Hu W X. Ant colony optimization algorithm for computing resource allocation based on cloud computing environment[J]. Journal of East China Normal University:Natural Science Edition,2010,1(1):127-134.

[8] 王静宇,谭跃生.云计算环境下资源分配与任务调度研究[J].中南大学学报,2010,41(S):47-49.

WANG J Y, TAN Y S. Research of resource allocation and job scheduling in cloud computing[J]. Journal of Central South University,2010,41(S):47-49.

[9] 刘东,常静,魏文红,等.基于MPI的并行蚁群算法的研究与实现[J].广东工业大学学报,2008,25(1):38-42.

LIU D,CHANG J,WEI W H, et al. Research and I mplementation of parallel ant colony optimization algorithm based on MPI[J]Journal of Guangdong University of Thechnology,2008,25(1) :38-42.

[10]SCHMIDT K, BREINDL C. Maximally permissive hierarchical control of decentralized discrete event systems[J]. Automatic Control, IEEE Transactions,2010,56(4):723-737.

[11] 张浩荣. 云环境下基于蚁群算法的资源调度策略研究[D]. 广州:广东工业大学计算机学院,2014.

[12] 姜晓涛. 基于模拟退火的蚁群算法求解网格任务调度问题[D]. 合肥：安徽大学计算机科学与技术学院，2012.

[13] NURMI D, WOLSKI R. The eucalyptus open-source cloud-computing system[C]∥Cluster Computing and the Grid,9th IEEE/ACM International Symposium.Shanghai:IEEE2009:124-131.

[14] 张浩荣,陈平华,熊建斌.基于蚁群模拟退火算法的云环境任务调度[J].广东工业大学学报,2014,31(3):77-82.

ZHANG H R,CHEN P H,XIONG J B. Task scheduling algorithm based on simulated annealing ant colony algorithm in cloud computing environment[J].Journal of Guangdong University of Technology,2014,31(3):77-82.

[15] 郑湃,崔立真,王海洋,等. 云计算环境下面向数据密集型应用的数据布局策略与方法[J].计算机学报, 2010,33(8):1472-1480.

ZHENG P, CUI L Z, WANG H Y, et al. A data placement strategy for data intensive applications in cloud[J]. Chinese Journal of Computers, 2010,33(8):1472-1480.

[16] SAN M. Cloud computing gives emerging markets a lift[J]. IT Professional,2011,13(6):60-62.

[17] 唐卓,朱敏,杨黎.云环境中面向随机任务的用户效用优化模型[J]. 计算机研究与发展,2014,51(5):1120-1128.

TANG Z, ZHU M, YANG L. Random task-oriented user utility optimization model in the cloud environment[J]. Journal of Computer Research and Development,2014,51(5):1120-1128.

Optimization Control of Cloud Resource Allocation Based on DES

Hu Qin, Liu Fu-chun

(School of Computers, Guangdong University of Technology, Guangzhou 510006, China)

Abstract:How to allocate resources reasonably and effectively has been an important problem in the field of cloud computing. For traditional cloud resource allocation algorithms can not effectively shield the isomerization of underlying hardware resources, and they also can not neglect the categories of different layers’ cloud service, this paper proposes a multi-parameter resource packing method, and constructs a cloud resource allocation control model based on discrete event system. Besides, it gives a reasonable resource allocation algorithm. By calculating the close degree of capacity parameters from each resource package over the servers and the resource demands of the clients, the algorithm defines the resource allocation events, and hierarchically controls the states’ occurrence or nonoccurrence. Finally, the entire resource allocation system will reach an acceptable state. The experiments show that the cloud resource allocation model based on the discrete event system can guarantee that under the acceptable state, not only each resource request can get a reasonable allocation, but also the resource can get a maximal utilization.

Key words:cloud resource allocation; discrete event systems(DES); resource packages; resource utilization rate

中图分类号:TP301.1

文献标志码:A

文章编号:1007-7162(2016)01- 0029- 07

doi:10.3969/j.issn.1007- 7162.2016.01.006

作者简介:胡芹(1989-)，女，硕士研究生，主要研究方向为离散事件系统的监督与控制应用.通信作者: 刘富春(1971-)，男，教授，主要研究方向为离散事件系统理论.E-mail: liufch@gdut.edu.cn.

基金项目:国家自然科学基金资助项目(61273118)；广东省高校省级重大科研项目(2014KZDXM033)；广东省公益研究与能力建设专项资金项目(2015A030402006)

收稿日期:2015- 01- 15