施進發(fā)，焦合軍

（1.鄭州航空工業(yè)管理學院 管理科學與工程學院，河南 鄭州450015；2.河南工程學院 計算機科學與工程系，河南 鄭州451191；3.西安理工大學 計算機科學與工程學院，陜西 西安710048）

0 引 言

云計算作為一種商業(yè)計算模型，能為用戶提供所需的計算資源，它是網格計算、虛擬化、效用計算及負載均衡等一系列分布式計算技術發(fā)展融合的產物。云計算以面向服務的形式提供資源，而且其平臺可能比網格、傳統(tǒng)集群具有更大的規(guī)模，因此云計算平臺提供的計算性能很可能高于超級計算機[1]。從另外一方面說網格、效用計算、集群等技術提供的服務往往針對特定的應用，其規(guī)模和靈活性不及云計算技術。資源調度是云計算環(huán)境下各種系統(tǒng)的共性問題，現有的調度方式可分為兩類:批調度模式和在線調度模式[2]。批調度將任務集合成一批統(tǒng)一調度，每次映射和調度都會考慮每個任務的執(zhí)行時間；在線調度時，每個到達的作業(yè)都要立即處理并分配到資源，這樣可以簡化調度。近年來，QoS保證機制成為研究熱點，資源調度中也引入各種QoS，目的在于有足夠的資源來滿足用戶的QoS要求，并使得資源利用率最高。因此，在實現過程中都面臨著基于QoS的資源最優(yōu)調度問題，很少根據不同在線應用對資源需求的不同加以區(qū)分和權衡，造成一些資源的閑置或由于負載失衡而無法工作。

本文提出了一種多維度QoS度量方法CRSMQ，該方法給出了云資源調度的各類QoS定量的數學模型，然后給出了具有偏好系數的資源分配算法，最后通過分析及模擬實驗表明該優(yōu)化算法簡單有效，提高了系統(tǒng)的資源利用率和保證用戶對資源使用的有效性，獲得較優(yōu)的資源分配方案。

1 云資源多維度QoS的數學模型

1.1 資源定義

云計算應用的發(fā)展必然會導致云中的基礎設施資源（例如服務器和存儲設備等）大量集中，由此，資源調度管理的優(yōu)劣將直接影響到數據中心整體的資源利用率、服務能力以及服務等級協議 （service level agreement，SLA）。另外，隨著數據中心規(guī)模的增擴，手動或人工管理數目龐大的物理資源集群已變的很不現實，如今，更加需要一種自適應的資源管理方法，以自動響應數據中心運行情況變化。由此，這也成為云計算在基礎設施模式下需要重點解決和突破的關鍵技術問題[3]。用戶任務集合T＝｛t1，t2，…，tn｝中n個相互獨立的任務分配到參與調度的資源集合M＝｛m1，m2，…，mm｝中m個虛擬服務器資源上，資源規(guī)模小于用戶提交的任務數量。

云端的可用資源主要包括硬件資源和虛擬資源[4]，為了方便管理，我們采用可調度單元描述可用資源，對于硬件資源，一個調度單元是一個物理主機；對于虛擬資源，一個調度單元用二元組T（C，M）確定，其中C代表任務需求的CPU數量，M表示任務需求內存數量。一個虛擬服務器Vi上能夠提供的可調度單元數為

其中，Ci為虛擬服務器Vi的CPU數量，Mi代表虛擬服務器Vi的內存數量。

由此可以得到，云端的可用資源總數N為

1.2 偏好因子及效用函數建模

云計算的各種能力最終以服務的形式呈現給用戶，用戶和服務供應商通過SLA來協商服務質量的參數和等級，但是在現有的云計算SLA規(guī)范中，尚缺乏一套行之有效的安全質量描述及量化機制[5]。用戶難以清晰地表達其對安全QoS的要求。根據QoS特性的不同，將云資源QoS參數分成了用戶QoS需求和系統(tǒng)QoS需求，其中，用戶QoS需求描述資源提供的QoS水平，主要包括資源的負載、費用、網絡帶寬和安全性等。而系統(tǒng)QoS需求用來描述對云計算的服務質量有影響的系統(tǒng)環(huán)境方面的QoS參數，包括負載均衡等。效益函數表示完成任務獲得的QoS滿意程度，有遞增函數和遞減函數組成，對于遞增函數，其值越大，效益越大，如網絡帶寬；對于遞減函數，其值越大，效益越底，如負載、開銷等。

任務ti關于資源mj的w個不同維度的效益函數構成w－QoS空間，其中uij（k）代表第k維效益值，這里引入表示w維的布爾向量P，若P[k]＝1，則表示該云服務用到了第k維所對應的QoS指標；若為0，則第k維所對應的QoS指標沒有用到，效益值分布在[0，1]區(qū)間內，用戶QoS歸一化的總的效益值可以用下式來表示

系統(tǒng)的平均效用值可以表示為下式，其中qj為資源mj的虛擬CPU數，x為資源數量，y為維數，任務ti在資源mj上執(zhí)行所消耗的CPU時間分別為sij

在對QoS進行分別度量后，需要對整體服務水平進行評價，按照QoS目標不同，調整可用資源的性能配比參數，期待向量用來約束資源選擇過程的公平性，對于第i個任務期待向量表示為[Li1，Li2，…，Liw，…，Li（w＋y）]，其中Lij為任務ti對第k維QoS特性的期待，定義客元為任務的客觀屬性的物元，即任務的特征名稱加特征值，記作Oti。定義主元為用戶對任務完成所需資源的期待，任務ti的主元S可嵌套表示，主元本身具有可拓性，為相互約束、相互影響和相互矛盾的期待關系建立了可行的研究方法[6]。任務元是有上述的主元和客元合成的，記為

針對任務存在的多重期待偏好，主元的合成計算可以使用權值的數學期望表示，綜合期待的計算公式為

由此，主元可拓期待和常規(guī)期待及任務元合成表示為任務元，即

其中SiN是常規(guī)期待；SiE是可拓期待。通過SiE可拓部分交換可以完成任務期望的合成。當任務分配資源與實際分配資源的期望值能夠得到最大程度上的一致，這時我們稱之為任務公平。設公平評判函數為

ε為均衡常量，且0＜ε≤l，PSi是任務ti的期待資源量，ATi是ti的實際分配資源量。當PSi與ATi一致時，即期待分配的資源與實際分配的資源相等，函數值等于零，得出正義即公平；以Ji＞0時，稱為過多的不公平分配；當小于0時，任務得到較少分配，稱為過少的不公平分配。后二者均表現出非正義性，但對于云計算環(huán)境資源調度來說，用戶任務的期待低于資源分配量可以提供更好的服務質量，過多的不公平分配是允許的。這個函數可以用來評判資源分配的結果是否正義即公平。

2 在線調度模型的建立

為了提高運算速度和調度精度.對樣本進行歸一化處理。實驗過程中，本文針對云服務用戶網絡帶寬、開銷和優(yōu)先級別等關鍵特征，進行QoS維度空間的效用優(yōu)化，用戶提交任務的同時提交其QoS請求，根據QoS的請求對資源進行篩選，獲得可用資源中的最佳資源。

算法的詳細步驟如下:

輸入單位開銷、維度偏好因子、以及任務集合T與資源信息；

輸出分配方案及QoS指標；

初始化:任務數、維度初值、各維度最大值和最小值。

（1）對任務集合里的每個任務ti，查詢所有資源信息。

（2）對資源進行排序，根據式 （5）將預加載任務計算在所有資源上的負載信息，求得其QoS請求。

（3）為了提高運算速度和調度精度，對數據進行歸一化處理，映射到[0，l]區(qū)間

其中xij為資源mj在維度i的效用指標值，curxij為當前效用值。

（4）根據偏好因子，計算Uuser及Usystem和資源的效用向量的歐式距離U，從U中得到最小歐式距離對應的資源mj。

（5）預分配任務到資源mj上后記錄下，將任務發(fā)送至資源mj，建立任務與資源之間的映射。

（5）記錄任務及相關信息。

（6）返回步驟 （1），直到所有任務集合中的任務處理完畢。

（7）更新資源狀態(tài)和信息，從集合中刪除該任務。

假設任務規(guī)模為n，資源數目為m，則整個算法的時間復雜度為O（mn）。

3 仿真實驗

3.1 模擬環(huán)境與參數設置

為了驗證該算法在云資源調度中的可行性，對開源CloudSim進行擴展，重載相關方法，實現自己的調度策略。建立了任務長度為[10000mips，50000mips]的資源調度環(huán)境，各個任務間相互獨立，其主要參數如表1所示。虛擬機具有優(yōu)先級性能，虛擬機數服從高斯分布，每臺虛擬機的VCPU數能提供[1，4]之間，虛擬資源的調度單元T＝（1，1），不考慮內存數量，如果Ci＝3則共有3個調度單元。

使用Ant工具重編譯重寫DataCenterBroker、Virtual－Machine等類，對上述算法進行測試模擬。為了評價本文所提出的優(yōu)化算法在云資源調度中的性能，與同等條件下的Strict time算法、Min－min算法和Fair share這3種在線調度策略進行對比分析，其中Strict time算法以任務完成時間最短為優(yōu)化目標，Fair share是為任務公平分配資源的算法。Min－min算法基于計算兩次最小值來完成資源的調度，兩次最小值分別指首先計算每個任務在相應資源上的最小完成時間，然后從這些最小完成時間中擇其最小[7]。其特點是優(yōu)先調度小任務，這樣就不能確保云計算資源負載平衡，對于以資源共享和追求最大可能利用資源的云計算來說就是非常嚴重的問題。

表1 算法參數設置

3.2 在線調度算法的復雜度模擬

圖1反應了云系統(tǒng)中任務執(zhí)行的效率，橫軸代表任務數，縱軸代表執(zhí)行時間，模擬中我們發(fā)現，資源數量是影響算法執(zhí)行時間的主要因素，對比表1，從圖1中可以看出，在資源相對少的情況下優(yōu)化算法的時間間隔略大于Strict time算法和Min－min算法，這是由于優(yōu)化算法均衡的考慮了QoS要求，任務數量與資源數量的比例增加提高了對資源的爭搶力度，公平共享算法的執(zhí)行時間則始終很大[8]。存在一個任務數與資源數量比的闕值，在此闕值之后，時間開銷隨比例表現得較為緩慢，但在此闕值之前，則表現得非常好。實際應用中可根據此闕值來限定系統(tǒng)中競爭資源的任務數，如圖2所示。

圖1 時間跨度比較

3.3 在線調度算法的負載均衡程度

圖2 任務資源比例

圖3 橫軸代表資源節(jié)點，縱軸代表獲得的任務數，可以看出，在分派了1000個任務后，優(yōu)化算法的負載均衡程度明顯優(yōu)于此前表現很好的Strict time算法和 Min－min算法:相對于Strict time算法，性能平均提升在17%左右。Fair share算法雖然具有資源共享的功能，但是沒有考慮用戶和系統(tǒng)的QoS需求，只是在資源少任務多得情況下簡單地按順序分配。Strict time算法由于沒有考慮用戶的資源需求，容易形成 “資源碎片”，造成較多任務等待的問題[9]。

圖3 負載均衡程度的比較

3.4 在線調度算法的用戶滿意程度

選擇與具有最小歐氏距離的資源，作為執(zhí)行任務的基本單位，其公平性評判函數Ji的計算變成

結合定義，這個閾值體現了云計算環(huán)境對于過多的不公平約束弱于過少的不公平約束，能將Ji的負值（過少分配的情況）約束在較小空間。參考閾值以原始Ji為基準，結合以上所述，得到用戶滿意度，如圖4所示。

圖4 用戶滿意度比例

圖為4個算法的平均J值比較，J值大于0時表示得到了高于自己期待的資源分配，J值小于0代表得到的資源不能符合期待，J＝0表示用戶獲得了與期待資源一致的資源分配。從而得出調度算法的資源分配能更好的符合用戶期待。

4 結束語

本文基于CRMSQ算法的云計算資源調度策略，不同于云系統(tǒng)中普遍采用的調度算法，針對現有云計算資源調度算法不能很好的兼顧負載平衡和調度執(zhí)行時間，引入系統(tǒng)偏好因子的概念[10－11]。綜合考慮各項QoS需求，能有效地完成云計算環(huán)境中計算資源搜索與分配的工作，在任務資源數滿足一定比例的情況下執(zhí)行效率比一般的資源調度策略高，在時間跨度和負載均衡程度方面有明顯的提高，具有較好的實用性和擴展性。需要改進的工作有:研究系統(tǒng)偏好因子及用戶QoS權重對系統(tǒng)的影響，用戶數和有效時間關系等問題。

[1]WANG Jiajun，LV Zhihui，WU Jie，et al.Cloud computing technology development analysis and applications discussion[J].Computer Engineering and Design，2010，31 （20）:4404－4409（in Chinese）.[王佳雋，呂智慧，吳杰，等.云計算技術發(fā)展分析及其應用探討[J].計算機工程與設計，2010，31 （20）:4404－4409.]

[2]Calheiros R N，Ranjan R，Beloglazov A，et al.CloudSim:A toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms[J].Software:Practice and Experience.2011，41 （1）:23－50.

[3]WANG Jing，FANG Wei，CHEN Jingyi，et al.Survey on adaptive resource management techniques in cloud computing environment[J].Computer Engineering and Design，2012，33（6）:2127－2132 （in Chinese）.[王晶，方偉，陳靜怡，等.云計算環(huán)境下的自適應資源管理技術綜述.計算機工程與設計，2012，33 （6）:2127－2132.]

[4]YUAN Wencheng，ZHU Yian，LU Wei.Exploring virtualized resource management mechanism for cloud computing[J].Journal of Northwestern Polytechnical University，2010，28（5）:704－708 （in Chinese）.[袁文成，朱怡安，陸偉.面向虛擬資源的云計算資源管理機制[J].西北工業(yè)大學學報，2010，28 （5）:704－708.]

[5]WANG Wei，LUO Junzhou，SONG Aibo.A GQoP guaranteed grid QoS adaptive scheduling algorithm[J].Journal of Computer Research and Development，2011，48 （7）:1168－1177（in Chinese）.[王巍，羅軍舟，宋愛波.一種具有GQoP保證的網格QoS自適應調度算法[J].計算機研究與發(fā)展，2011，48 （7）:1168－1177.]

[6]ZHAO Chunyan.Research on scheduling algorithm and realization based on cloud computing[D].Beijing Jiaotong University，2009（in Chinese）.[趙春燕.云環(huán)境下作業(yè)調度算法研究與實現[D].北京交通大學，2009.]

[7]ZUO Liyun，ZUO Lifeng.Cloud computing scheduling optimization algorithm based on reservation category[J].Computer Engineering and Design，2012，33 （4）:1357－1361 （in Chinese）.[左利云，左利鋒.云計算中基于預先分類的調度優(yōu)化算法[J].計算機工程與設計，2012，33 （4）:1357－1361.]

[8]Ghalem Belalem，Fatima Zohra Tayeb，Wieme Zaoui.Approaches to improve the resources management in the simulator cloudSim[C]／／ICICA.Heidelberg:Springer Verlag Press，2010:189－196.

[9]GONG Hongcui，YU Jiong，HOU Yong，et al.User QoS and system index guided task scheduling in computing grid[J].Computer Engineering，2009，35 （7）:52－54 （in Chinese）.[龔紅翠，于炯，侯勇，等.用戶QoS及系統(tǒng)指標指導的計算網格任務調度[J].計算機工程，2009，35 （7）:52－54.]

[10]Armbrust M，Fox A，Griffith R，et al.Above the clouds:A berkeley view of cloud computing.[R].USA:University of California at Berkley，2009.

[11]Kimj S，Nam B，Marsh M，et al.Creating a robust desktop Grid using peer to peer services[EB／OL].[2009－10－16].FTP:／／ftp.cs.umd.edu／pub／hpsl／papers／paperspdf／ngs07.pdf.