施進(jìn)發(fā)，焦合軍

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

0 引 言

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

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

1 云資源多維度QoS的數(shù)學(xué)模型

1.1 資源定義

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

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

其中，Ci為虛擬服務(wù)器Vi的CPU數(shù)量，Mi代表虛擬服務(wù)器Vi的內(nèi)存數(shù)量。

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

1.2 偏好因子及效用函數(shù)建模

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

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

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

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

針對(duì)任務(wù)存在的多重期待偏好，主元的合成計(jì)算可以使用權(quán)值的數(shù)學(xué)期望表示，綜合期待的計(jì)算公式為

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

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

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

2 在線調(diào)度模型的建立

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

算法的詳細(xì)步驟如下:

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

輸出分配方案及QoS指標(biāo)；

初始化:任務(wù)數(shù)、維度初值、各維度最大值和最小值。

（1）對(duì)任務(wù)集合里的每個(gè)任務(wù)ti，查詢所有資源信息。

（2）對(duì)資源進(jìn)行排序，根據(jù)式 （5）將預(yù)加載任務(wù)計(jì)算在所有資源上的負(fù)載信息，求得其QoS請(qǐng)求。

（3）為了提高運(yùn)算速度和調(diào)度精度，對(duì)數(shù)據(jù)進(jìn)行歸一化處理，映射到[0，l]區(qū)間

其中xij為資源mj在維度i的效用指標(biāo)值，curxij為當(dāng)前效用值。

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

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

（5）記錄任務(wù)及相關(guān)信息。

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

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

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

3 仿真實(shí)驗(yàn)

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

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

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

表1 算法參數(shù)設(shè)置

3.2 在線調(diào)度算法的復(fù)雜度模擬

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

圖1 時(shí)間跨度比較

3.3 在線調(diào)度算法的負(fù)載均衡程度

圖2 任務(wù)資源比例

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

圖3 負(fù)載均衡程度的比較

3.4 在線調(diào)度算法的用戶滿意程度

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

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

圖4 用戶滿意度比例

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

4 結(jié)束語

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

[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）.[王佳雋，呂智慧，吳杰，等.云計(jì)算技術(shù)發(fā)展分析及其應(yīng)用探討[J].計(jì)算機(jī)工程與設(shè)計(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，F(xiàn)ANG 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）.[王晶，方偉，陳靜怡，等.云計(jì)算環(huán)境下的自適應(yīng)資源管理技術(shù)綜述.計(jì)算機(jī)工程與設(shè)計(jì)，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ì)算資源管理機(jī)制[J].西北工業(yè)大學(xué)學(xué)報(bào)，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保證的網(wǎng)格QoS自適應(yīng)調(diào)度算法[J].計(jì)算機(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è)調(diào)度算法研究與實(shí)現(xiàn)[D].北京交通大學(xué)，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）.[左利云，左利鋒.云計(jì)算中基于預(yù)先分類的調(diào)度優(yōu)化算法[J].計(jì)算機(jī)工程與設(shè)計(jì)，2012，33 （4）:1357－1361.]

[8]Ghalem Belalem，F(xiàn)atima 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)指標(biāo)指導(dǎo)的計(jì)算網(wǎng)格任務(wù)調(diào)度[J].計(jì)算機(jī)工程，2009，35 （7）:52－54.]

[10]Armbrust M，F(xiàn)ox 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.