胡　芹，劉富春

(廣東工業(yè)大學(xué) 計算機學(xué)院，廣東 廣州 510006)

?

基于離散事件系統(tǒng)的云資源分配優(yōu)化控制

胡芹，劉富春

(廣東工業(yè)大學(xué) 計算機學(xué)院，廣東 廣州 510006)

摘要:如何對資源進行合理有效的分配一直是云計算領(lǐng)域的熱點問題.由于傳統(tǒng)的云資源分配算法不能有效屏蔽底層硬件資源的異構(gòu)化以及不同層的云服務(wù)類別，本文提出一種多參數(shù)資源打包的方法，構(gòu)建出基于離散事件系統(tǒng)的云資源分配控制模型，并給出了合理的資源分配算法.算法通過計算服務(wù)器端各資源包容量參數(shù)與客戶端資源需求量參數(shù)的貼近度來定義資源分配事件，并對事件發(fā)生與否的狀態(tài)實行分層控制，最終使得整個資源分配系統(tǒng)到達可接受狀態(tài).實驗表明，基于離散事件系統(tǒng)的云資源分配模型，能夠保證在可接受狀態(tài)下，不僅每個用戶的資源請求能夠得到合理的分配，且能實現(xiàn)云資源利用率最大化.

關(guān)鍵詞:云資源分配； 離散事件系統(tǒng)； 資源包； 資源利用率

云計算[1-2]為用戶提供靈活的計算能力和高效的數(shù)據(jù)存儲能力，云資源分配將用戶請求的虛擬機分配給各個底層物理機去處理[3]，由分布在不同地方的物理機提供用戶所需的資源，滿足用戶請求的執(zhí)行條件.在云環(huán)境下，資源分配的效率顯得非常重要，其對云平臺系統(tǒng)的綜合性能影響很大.當前，云計算下的資源分配已經(jīng)進行了大量的研究，已經(jīng)投入使用的著名的MapReduce調(diào)度模型[4]，通過3種角色(Master、Worker、User)的分工協(xié)作，能高效地為用戶請求分配合適的計算資源；文獻[5]提出了基于粒子群優(yōu)化算法的云資源分配，采用進化算法原理，依據(jù)用戶需求大小來適當?shù)胤峙滟Y源量；文獻[6-9]提出了基于Qos(Quality of service)任務(wù)分配和蟻群算法的資源分配與任務(wù)調(diào)度算法，先采取Qos算法，將不同的資源請求分類處理，再利用蟻群算法得到一組最優(yōu)的計算資源.文獻[10]分別研究了在分布式DES(Discrete Event Systems)監(jiān)控和協(xié)調(diào)器協(xié)調(diào)監(jiān)控中的兩類具體問題：作業(yè)調(diào)度問題TAP(Task Allocation Problem)、最少干預(yù)問題MIP(Minimal Intervention Problem)；文獻[11-14]研究了基于模擬退火的蟻群算法求解網(wǎng)格任務(wù)調(diào)度問題；文獻[15]研究了云環(huán)境中面向隨機任務(wù)的用戶效用優(yōu)化模型.然而以上研究都沒有考慮具體的資源分配模型.本文將成熟的離散事件系統(tǒng)(DES)的控制理論應(yīng)用到資源分配上，基于有窮自動機的資源分配的基礎(chǔ)，建立了DES云資源控制模型.將所有資源分配事件都看作是可控事件，通過控制可控事件的發(fā)生與不發(fā)生，保證提高資源利用率的事件有效發(fā)生.將用戶請求的虛擬機準確分配到具體的資源包，通過資源參數(shù)值與任務(wù)對應(yīng)參數(shù)值的對比，調(diào)整資源分配，在滿足資源利用率最大的同時，可以實現(xiàn)有效的資源分配.

1云資源分配模型

云資源分配是一個NP(Non-deterministic Polynomial)難問題，到目前為止還沒有確切的資源分配模型，但是存在對資源分配的多種優(yōu)化算法，一些啟發(fā)式算法將云資源分配問題轉(zhuǎn)換為NP難優(yōu)化問題[16-17].本文建立合理的DES資源分配模型，在該模型中，云計算數(shù)據(jù)中心是由大量的異構(gòu)的計算資源構(gòu)成的云資源池，這些海量的資源均是客戶端請求執(zhí)行所必須的，如CPU、內(nèi)存、存儲空間、防護服務(wù)、服務(wù)器、帶寬等.考慮到基本的云計算三層結(jié)構(gòu)模型，在每一層中，云提供服務(wù)可以抽象為“XaaS”，如基本架構(gòu)即服務(wù)“IaaS(Infrastructure as a Service)”,平臺即服務(wù)“PaaS(Platform as a Service)”，軟件即服務(wù)“SaaS(Software as a Service)”.為了屏蔽不同層的服務(wù)類別，本文將資源池的資源看作為容量不一的資源包，每個資源包中含有多種不同資源，將不同類別資源表征為該資源包具有的不同參數(shù)，如參數(shù)1為CPU數(shù)量，參數(shù)2為存儲容量，參數(shù)3為帶寬等等.同理，用戶任務(wù)請求所需資源類別也進行參數(shù)化處理，如某一個任務(wù)，所需要資源配置的參數(shù)1、參數(shù)2、參數(shù)3、…分別為完成該任務(wù)所需要的CPU、內(nèi)存、存儲空間、…的資源量.如此，每一層的服務(wù)對所有用戶都是透明的，用戶只需要申請和使用所需的資源即可，不需要關(guān)心資源是如何分配的.

資源包含有的資源以及任務(wù)請求資源情況均可以用一個n×m階矩陣表示，具體表示如下：

(1)

在資源分配過程中，要求任務(wù)請求的各個參數(shù)資源總量不得超過資源包中各個參數(shù)資源的資源總量，且資源包各個參數(shù)資源總量不得超過資源池中該類資源的資源總量，即要求滿足

(2)

初始化資源分配調(diào)度也是一個n×m階矩陣，為

其中，A[Tx,Py]∈{0,1}，值為1表示第x個任務(wù)獲得了第y個資源包的資源，為0則表示沒有獲得.當為任務(wù)請求分配資源時，要求保證每個任務(wù)都可以分配一個確定的資源包，一個包可以被多個任務(wù)共享.因此，資源分配矩陣中的每一行有且只有1，每一列存在一個或者多個1.

云資源分配的最理想狀況是任務(wù)群被分配的總資源量等價于資源池中的總資源量，即

然而，這種理想的狀態(tài)目前尚不能達到，因為存在部分資源不能完全被利用.若要實現(xiàn)分配之后的各個資源包的資源參數(shù)能夠最大限度地滿足任務(wù)需求的各個參數(shù)的資源量，求出資源包的容量值與用戶請求資源的容量歐氏距離距離越小，表明資源包容量與用戶請求資源量的貼近度越大.對于任意給定的x∈N，要得到最大的貼近度，即找出唯一y∈N，存在

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

D(x,y)=

(3)

則返回資源分配結(jié)果，令

為了達到資源的最優(yōu)分配，要求滿足所分配的資源包能夠得到最大化利用，即利用率之和最大.

(4)

2構(gòu)造DES控制模型

構(gòu)造資源分配系統(tǒng)的DES控制模型，設(shè)系統(tǒng)Φ={Q,Σ,δ,q0,qa}，狀態(tài)集Q={q0,q1,…,qk}，qi={?i∈N,P1∪P2…∪Pi}表示在該狀態(tài)下，存在一個或多個資源包以供選擇；事件集Σ為并行執(zhí)行的任務(wù)T串，如{Ti},{TiTj},{TiTjTk},…；轉(zhuǎn)移函數(shù)δ:Q×Σ*→Q，當為某個用戶任務(wù)分配資源包之后，系統(tǒng)跳轉(zhuǎn)到另一個狀態(tài)；q0,qa∈Q，q0={?i∈N,P1∪P2…∪Pi}表示系統(tǒng)的起始狀態(tài)，在起始狀態(tài)，任意的資源包都可供選擇，qa為資源分配系統(tǒng)的接受狀態(tài)，在該狀態(tài)下，所有等待的用戶請求都可以獲得資源包，且資源包的利用率最大.

對于該資源分配系統(tǒng)，資源分配事件L?Σ*分為可滿足事件Lc、不可滿足事件Lu和可接受事件La.其中可滿足事件

表示只有在當前狀態(tài)中的某個確定的資源包參數(shù)能夠滿足該事件串中的所有事件的子串所對應(yīng)的資源需求量，該事件才是可滿足的；不可滿足事件

表明存在某個資源包的參數(shù)不能滿足對應(yīng)請求的資源參數(shù)，顯然，以Lu為子串的所有事件串均為不可滿足事件；可接受事件

La={?Tj∈s:max(U)}?Lc的發(fā)生能夠滿足資源包的最大化利用.

在該資源分配系統(tǒng)中，一個資源包可以同時滿足多個用戶請求，資源包和用戶請求之間是一對多的關(guān)系，所有可滿足事件的發(fā)生都可以是并行的.由于在并行狀態(tài)下的多個事件串的發(fā)生，不具有可觀性；又由于每個用戶請求只能被一個資源包服務(wù)，資源包與任務(wù)請求之間不具有交叉性，因此，在該分配模型中，可以考慮系統(tǒng)中資源包分配的串行執(zhí)行情況，分別考慮當前狀態(tài)中每一個資源包在各個事件串發(fā)生后的狀態(tài).最后通過分析比較，確定可接受事件串，控制不可滿足事件的不發(fā)生，以及控制可接受事件的發(fā)生來確保系統(tǒng)資源利用率最大化.

系統(tǒng)初始狀態(tài)包含所有未被分配的資源包，考慮資源池中的每一個資源包Pm，假設(shè)某個事件是可滿足事件，則考慮該可滿足事件的擴充串(enlarge語言)，直到找出在該資源包下最大的可滿足事件Lc，并修改狀態(tài)集Q中Pm的參數(shù)，其他資源包保持不變，若Ti是屬于該可滿足語言，則將Pm資源包分配給任務(wù)Ti，修改事件集Σ′=Σ-Ti,使得已經(jīng)獲得資源包的用戶請求退出緩沖池，接下來考慮包Pn(n≠m)，轉(zhuǎn)移函數(shù)δ:Q×Σ′→Q，直到所有任務(wù)都可以得到分配.假設(shè)系統(tǒng)存在2個資源包P1,P2，3個任務(wù)T1,T2,T3,如圖1所示，在q0狀態(tài)下考慮資源包P1，若任務(wù)事件T1屬于可滿足事件，接下來考慮事(81.5件T1T2,T1T3,T1T2T3是否為可滿足事件，即判斷Σ*中所有包含可滿足事件T1的所有串是否仍為可滿足事件，找出包含T1的最大可滿足串；接下來判斷，若事件T2不屬于可滿足事件，即狀態(tài)4不存在，則不用考慮包含T2的事件串，即不會出現(xiàn)狀態(tài)q5.

圖1　某個資源包下的狀態(tài)遷移

確定各個資源包的可滿足事件串，若Ti,Tj,…,Tt?Lc根據(jù)式(3)可得Lc與資源包Py的參數(shù)貼近度，資源參數(shù)距離D(Lc,y)越小，表明參數(shù)貼近度越大.

(5)

3算法實現(xiàn)

輸入：任務(wù)請求隊列T、資源池P；

輸出：資源分配矩陣A.

執(zhí)行：

1) 初始化資源分配控制系統(tǒng)起始狀態(tài)

根據(jù)式(1)初始化請求隊列T、資源包P;

確定起始狀態(tài)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)

根據(jù)等式(4)，求得Py與Li的距離D值.

4) 根據(jù)距離D，確定分配方案

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

Else If?Lk?Lc,Tx?Lk存在且

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

將Tx分配給Pj，令

5) 計算資源利用率，定義可接受事件

根據(jù)等式(3)，計算資源利用率U，定義可接受事件為滿足Umax的任務(wù)串；

6) 返回分配矩陣A

控制可接受事件的有效發(fā)生，得到最佳分配矩陣A.

4仿真實驗

本文給出一個云資源分配的子系統(tǒng)，該系統(tǒng)中資源池中有5種資源R1、R2、R3、R4、R5，分別是CPU、存儲空間、內(nèi)存、服務(wù)器、帶寬的容量.存在3個資源包P1、P2、P3，5個用戶請求T1、T2、T3、T4、T5.資源包參數(shù)分配情況如表1所示，用戶任務(wù)請求資源參數(shù)分配情況如表2所示.

表1　資源包參數(shù)分配情況

表2　用戶請求資源參數(shù)分配情況

首先，考慮在先來先服務(wù)(First Come First Service， FCFS)算法下的云資源分配情況，假設(shè)任務(wù)請求的順序是T1→T2→T3→T4→T5，根據(jù)FCFS算法，T1將最先獲得資源分配，根據(jù)先后順序類推，T5最后獲得資源分配.當T1到達時，滿足各個資源參數(shù)條件的資源包有P1,P3，將T1分配給P1；當T2到達時，將其分配給P2，同理得出分配矩陣

在此示例中，先來先服務(wù)算法，雖然可以實現(xiàn)資源分配，但是先來先服務(wù)算法存在一個很大的弊端，其沒有從全局的角度出發(fā)，先到達的任務(wù)很有可能占用了一部分資源，使得縮減之后的資源包不能滿足后到達的任務(wù)，從而導(dǎo)致一些請求始終得不到資源分配.接著，考慮本文的基于離散事件系統(tǒng)的云資源分配算法，在q0狀態(tài)，依次考慮事件集Σ中最小子串在各個資源包下是否為可滿足事件，考慮資源包P1下，事件T1、T2、T3、T4、T5均為可滿足事件；在資源包P2下，可滿足事件為T2、T5；在資源包P3下，可滿足事件為T1、T2、T3、T5.如圖2～圖4所示.

圖2　在資源包P1下的可滿足最小事件

圖3　在資源包P2下的可滿足最小事件

圖4　在資源包P3下的可滿足最小事件

依次考慮每個可滿足事件的擴充(enlarge)串，找出在各個資源包下分配多個任務(wù)的可滿足事件串，若資源包Pi不能同時滿足n個任務(wù)串，則不用再考慮其是否滿足(n+1)個任務(wù)串，資源分配情況如圖5～圖7所示.

圖5　在資源包P1下分配2個任務(wù)的可滿足事件

圖6在資源包P2下分配2個任務(wù)的可滿足事件

Fig.6Satisfiable event of allocating two tasks under

Resource PacketP2

圖7　在資源包P1下分配3個任務(wù)的可滿足事件

在資源包P2下已經(jīng)不存在可以分配3個任務(wù)的可滿足事件，則不用再考慮.本文列出所有可滿足事件，并根據(jù)式(5)求出距離D的值，如表3所示.

根據(jù)資源控制分配算法，在所有可滿足事件串中，找出符合條件的可接受事件串.在資源包P1下存在最小D值的可滿足串是T1T2T4，假設(shè)將P1分配給T1T2T4,在P2中將不再考慮T1T2T4，此時存在最小D值的可滿足事件串為T5，在P3不考慮任務(wù)T1、T2、T4、T5，存在最小D值的可滿足串為T3,假定方案一為將P2分配給T5，P3分配給T3.同理，考慮資源包P2、P3、P4、P5的可滿足串，最終可得出兩個分配矩陣

表3　該資源分配系統(tǒng)中所有可滿足事件

根據(jù)式(4)求出資源利用率UA1=1.463 2,UA2=1.317 2，由于UA1>UA2，分配矩陣A1的資源利用率較大，取A1為最優(yōu)分配.定義P1下的事件串T1T2T4為可接受事件，同理，P2下的T5以及P3下的T3也定義為可接受事件，控制可接受事件的有效發(fā)生，能實現(xiàn)資源的最優(yōu)分配.

本文基于離散事件系統(tǒng)的云資源分配控制算法，從全局的角度定義出所有資源分配的可滿足事件和可接受事件，通過對可滿足事件的梳理以及控制可接受事件串的有效發(fā)生，不僅有效避開了FCFS算法陷入僵局的弊端，也保證了資源的利用率，是一個可行且有效的算法.

5結(jié)語

本文提出基于DES的云資源分配優(yōu)化控制策略，通過將資源參數(shù)化，形式化描述資源的優(yōu)化分配過程，有效將離散事件系統(tǒng)控制理論應(yīng)用到云資源分配模型中，保證提高資源利用率的事件有效發(fā)生，滿足資源利用率最大的同時實現(xiàn)最快最有效的分配.

參考文獻：

[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].北京:電子工業(yè)出版社,2010.

[3] 王笑宇,程良倫. 云計算下的多源信息資源云體系及云服務(wù)模型研究[J].計算機應(yīng)用研究,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] 華夏渝,鄭駿,胡文心.基于云計算環(huán)境的蟻群優(yōu)化計算資源分配算法[J].華東師范大學(xué)學(xué)報(自然科學(xué)版),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] 王靜宇,譚躍生.云計算環(huán)境下資源分配與任務(wù)調(diào)度研究[J].中南大學(xué)學(xué)報,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的并行蟻群算法的研究與實現(xiàn)[J].廣東工業(yè)大學(xué)學(xué)報,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] 張浩榮. 云環(huán)境下基于蟻群算法的資源調(diào)度策略研究[D]. 廣州:廣東工業(yè)大學(xué)計算機學(xué)院,2014.

[12] 姜曉濤. 基于模擬退火的蟻群算法求解網(wǎng)格任務(wù)調(diào)度問題[D]. 合肥：安徽大學(xué)計算機科學(xué)與技術(shù)學(xué)院，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] 張浩榮,陳平華,熊建斌.基于蟻群模擬退火算法的云環(huán)境任務(wù)調(diào)度[J].廣東工業(yè)大學(xué)學(xué)報,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] 鄭湃,崔立真,王海洋,等. 云計算環(huán)境下面向數(shù)據(jù)密集型應(yīng)用的數(shù)據(jù)布局策略與方法[J].計算機學(xué)報, 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] 唐卓,朱敏,楊黎.云環(huán)境中面向隨機任務(wù)的用戶效用優(yōu)化模型[J]. 計算機研究與發(fā)展,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-)，女，碩士研究生，主要研究方向為離散事件系統(tǒng)的監(jiān)督與控制應(yīng)用.通信作者: 劉富春(1971-)，男，教授，主要研究方向為離散事件系統(tǒng)理論.E-mail: liufch@gdut.edu.cn.

基金項目:國家自然科學(xué)基金資助項目(61273118)；廣東省高校省級重大科研項目(2014KZDXM033)；廣東省公益研究與能力建設(shè)專項資金項目(2015A030402006)

收稿日期:2015- 01- 15