云计算^[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云资源控制模型.将所有资源分配事件都看作是可控事件，通过控制可控事件的发生与不发生，保证提高资源利用率的事件有效发生.将用户请求的虚拟机准确分配到具体的资源包，通过资源参数值与任务对应参数值的对比，调整资源分配，在满足资源利用率最大的同时，可以实现有效的资源分配.

云资源分配是一个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、内存、存储空间、…的资源量.如此，每一层的服务对所有用户都是透明的，用户只需要申请和使用所需的资源即可，不需要关心资源是如何分配的.

本文重点考虑为已经到达任务处理缓冲池中的的用户请求分配资源，设资源池中的资源为R={R₁, R₂, …, R_n}，R_i表示资源池中的第i类资源，资源池中共有n种资源；用户请求的任务队列为T={T₁, T₂, …, T_n}, 其中T_x表示第x个用户请求；P={P₁, P₂，…，P_n}表示资源包队列，其中P_y表示第y个资源包；C_Ri^T_x表示第x个用户任务所需要的R_i类资源量，C_Ri^P_y表示第y个资源包所拥有的资源R_i的量.如此，资源包的资源分配情况可以形式化为P_i={C_R1^P_i, C_R2^P_i, …, C_Rn^P_i}，单个用户请求资源需求量可以形式化为T_i={C_R1^T_i, C_R2^T_i, …, C_Rn^T_i}，在资源包和请求中，若不存在此类资源，则将此类资源参数量设置为0.

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

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

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

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

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

然而，这种理想的状态目前尚不能达到，因为存在部分资源不能完全被利用.若要实现分配之后的各个资源包的资源参数能够最大限度地满足任务需求的各个参数的资源量，求出资源包的容量值与用户请求资源的容量欧氏距离

距离越小，表明资源包容量与用户请求资源量的贴近度越大.对于任意给定的x∈N，要得到最大的贴近度，即找出唯一y∈N，存在

则返回资源分配结果，令

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

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

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

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

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

${\mathit{L}_\mathit{a}} = \left\{ {\left. {\forall {T_j} \in s:\max \left( U \right)} \right\}} \right. \subseteq {L_c} $的发生能够满足资源包的最大化利用.

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

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

图 1(Figure 1)

图 1 某个资源包下的状态迁移 Figure 1 State migration in a resource package

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

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

输出：资源分配矩阵A.

执行：

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

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

确定起始状态q₀；

2) 定义可满足事件集

 For所有资源包P_y，

  For任意的事件集

    L={T₁∪T₂∪…∪T_m.

   If不等式(2) 成立，

    L属于P_y的可满足事件集L_c；

   Else L属于P_y的不可满足事件集L_u；

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

 对任意的资源包P_y，

 For(y=1;y < m; y+ +)，

   For(∀L_i∈L_c)

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

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

 For任意的P_y，存在min(P_y, L_i)，

   If T_x⊂L_i，将T_x分配给P_y，令A[T_x, T_y]=1, A[T_x, T_y]=0；

Else If∃L_k⊂L_c, T_x⊂L_k存在且

  min(P_j, L_k){j≠y, L_k∩L_i=ϕ，

  将T_x分配给P_j，令

A[T_x, T_j]=1, A[T_x, T_y]=0；

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

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

6) 返回分配矩阵A

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

本文给出一个云资源分配的子系统，该系统中资源池中有5种资源R₁、R₂、R₃、R₄、R₅，分别是CPU、存储空间、内存、服务器、带宽的容量.存在3个资源包P₁、P₂、P₃，5个用户请求T₁、T₂、T₃、T₄、T₅.资源包参数分配情况如表 1所示，用户任务请求资源参数分配情况如表 2所示.

表 1(Table 1)

表 1 资源包参数分配情况 Table 1 Parameters allocation of resource packets 资源包 R1 R2 R3 R4 R5 P1 7 10 5 13 15 P2 2 5 7 8 10 P3 9 8 10 6 4

表 1 资源包参数分配情况 Table 1 Parameters allocation of resource packets

表 2(Table 2)

表 2 用户请求资源参数分配情况 Table 2 Parameters allocation of user requested resource 用户请求 R1 R2 R3 R4 R5 T1 4 2 1 2 2 T2 1 2 1 4 3 T3 5 3 4 1 4 T4 2 3 0 1 5 T5 1 3 3 0 4

表 2 用户请求资源参数分配情况 Table 2 Parameters allocation of user requested resource

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

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

图 2(Figure 2)

图 2 在资源包P1下的可满足最小事件 Figure 2 Satisfiable minimal event under Resource Packet P1

图 3(Figure 3)

图 3 在资源包P2下的可满足最小事件 Figure 3 Satisfiable minimal event under Resource Packet P2

图 4(Figure 4)

图 4 在资源包P3下的可满足最小事件 Figure 4 Satisfiable minimal event under Resource Packet P3

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

图 5(Figure 5)

图 5 在资源包P1下分配2个任务的可满足事件 Figure 5 Satisfiable event of allocating two tasks under Resource Packet P1

图 6(Figure 6)

图 6 在资源包P2下分配2个任务的可满足事件 Figure 6 Satisfiable event of allocating two tasks under Resource Packet P2

图 7(Figure 7)

图 7 在资源包P1下分配3个任务的可满足事件 Figure 7 Satisfiable event of allocating three tasks under Resource Packet P1

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

表 3(Table 3)

表 3 该资源分配系统中所有可满足事件 Table 3 All satisfiable events of resource allocation system Packages Events D Events D Events D Events D Events D P1 T1 19.467 9 T2 18.466 2 T3 17.860 5 T4 18.520 2 T5 19.467 9 T1vT2 14.071 2 T2vT3 12.4097 T3vT4 13.190 9 TvT5 Unsatisfied T1vT3 14.491 3 T2vT4 13.038 4 T3vT5 14.628 7 T1vT4 14.352 7 T2vT5 14 T3vT4vT5 11.445 5 T1vT5 15.231 5 T2vT3vT4 7.937 2 T1vT2vT3 9.539 3 T2vT3vT5 9.643 6 T1vT2vT4 8.888 1 T2vT4vT5 9.327 3 T1vT2vT5 9.746 7 T1vT3vT4 10.816 6 T1vT3vT5 12.124 3 T1vT4vT5 11 P2 T1 12.206 5 T2 10.535 7 T3 10.344 0 T4 11.269 4 T5 11 T2vT5 5.830 95 P3 T1 12.727 9 T2 13.638 2 T3 10.099 5 T4 14.142 1 T5 13.190 9 T1vT2 9.848 8 T2vT3 Unsatisfied T3vT5 Unsatisfied T1vT3 6.855 6 T2vT5 Unsatisfied T1vT5 Unsatisfied T2vT3vT5 Unsatisfied T1vT2vT5 Unsatisfied T1vT3vT5 Unsatisfied

表 3 该资源分配系统中所有可满足事件 Table 3 All satisfiable events of resource allocation system

根据资源控制分配算法，在所有可满足事件串中，找出符合条件的可接受事件串.在资源包P₁下存在最小D值的可满足串是T₁T₂T₄，假设将P₁分配给T₁T₂T₄, 在P₂中将不再考虑T₁T₂T₄，此时存在最小D值的可满足事件串为T₅，在P₃不考虑任务T₁、T₂、T₄、T₅，存在最小D值的可满足串为T₃, 假定方案一为将P₂分配给T₅，P₃分配给T₃.同理，考虑资源包P₂、P₃、P₄、P₅的可满足串，最终可得出两个分配矩阵

根据式(4) 求出资源利用率U_A1=1.4632, U_A2=1.3172，由于U_A1 > U_A2，分配矩阵A₁的资源利用率较大，取A₁为最优分配.定义P₁下的事件串T₁T₂T₄为可接受事件，同理，P₂下的T₅以及P₃下的T₃也定义为可接受事件，控制可接受事件的有效发生，能实现资源的最优分配.

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

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