基于CloudSim的作業(yè)調(diào)度算法評(píng)價(jià)模型設(shè)計(jì)與實(shí)現(xiàn)

王宇賓

摘 要： 針對(duì)云計(jì)算作業(yè)調(diào)度算法評(píng)價(jià)問題，引入經(jīng)濟(jì)學(xué)中的消費(fèi)者均衡理論和帕累托最優(yōu)理論，在CloudSim仿真框架中，構(gòu)建一個(gè)云計(jì)算作業(yè)調(diào)度評(píng)價(jià)模型，為選擇最優(yōu)的作業(yè)調(diào)度算法提供決策支持。同時(shí)，針對(duì)CloudSim在用戶交互上的不足，進(jìn)行可視化擴(kuò)展，使研究者能夠直觀地觀測(cè)仿真結(jié)果。最后，在CloudSim上進(jìn)行仿真實(shí)驗(yàn)，仿真結(jié)果表明，對(duì)于模擬的云計(jì)算服務(wù)，CloudSim自身提供的作業(yè)調(diào)度算法不是最優(yōu)算法。

關(guān)鍵詞： 云計(jì)算； CloudSim； 作業(yè)調(diào)度； 評(píng)價(jià)模型

中圖分類號(hào)： TN304.01?34 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 1004?373X（2015）14?0012?04

0 引 言

近年來，互聯(lián)網(wǎng)應(yīng)用越來越豐富，給用戶提供了多種多樣的服務(wù)。但隨著應(yīng)用的不斷增長，企業(yè)要處理的數(shù)據(jù)越來越多，提供的帶寬越來越大，IT的支出費(fèi)用也越來越高。國外互聯(lián)網(wǎng)技術(shù)巨頭公司如Google、Amazon、IBM等，紛紛針對(duì)上述問題提出了“云計(jì)算”的構(gòu)想。依據(jù)美國國家標(biāo)準(zhǔn)與技術(shù)研究院（NIST）的定義[1]，云計(jì)算是一種利用互聯(lián)網(wǎng)實(shí)現(xiàn)的共享資源池的計(jì)算模式，這種模式提供了在任何時(shí)間任何地點(diǎn)，根據(jù)需求便捷訪問的技術(shù)支持。云計(jì)算[2]由分布式計(jì)算和網(wǎng)格計(jì)算發(fā)展而來，利用非本地或遠(yuǎn)程的集群服務(wù)器的分布式計(jì)算機(jī)為互聯(lián)網(wǎng)用戶提供服務(wù)。云計(jì)算的關(guān)鍵技術(shù)包含資源管理和作業(yè)調(diào)度，但目前云計(jì)算作業(yè)調(diào)度算法之間的設(shè)計(jì)和評(píng)價(jià)并沒有一個(gè)統(tǒng)一的標(biāo)準(zhǔn)[3]。

云計(jì)算作業(yè)調(diào)度的核心是把計(jì)算資源合適地分配到用戶請(qǐng)求的服務(wù)上。用戶請(qǐng)求云計(jì)算服務(wù)的過程實(shí)際上是一個(gè)資源分配的過程。用戶付出一定的費(fèi)用請(qǐng)求服務(wù)，獲得相應(yīng)的資源，以最大化滿足自身需求。這與經(jīng)濟(jì)學(xué)中的消費(fèi)者均衡理論具有一定的相似性。因此，本文引入消費(fèi)者理論和帕累托最優(yōu)理論，通過擴(kuò)展CloudSim仿真框架，構(gòu)建了一個(gè)云計(jì)算作業(yè)調(diào)度評(píng)價(jià)模型，利用消費(fèi)者均衡理論來評(píng)價(jià)云計(jì)算服務(wù)請(qǐng)求者的需求是否得到最大滿足，利用帕累托最優(yōu)理論來評(píng)價(jià)云計(jì)算的資源分配是否達(dá)到最優(yōu)。

1 相關(guān)介紹

1.1 消費(fèi)者均衡理論

消費(fèi)者均衡[4]是指在消費(fèi)者的偏好、收入以及商品的價(jià)格均不變的條件下，消費(fèi)者購買商品的數(shù)量組合達(dá)到一種相對(duì)靜止的狀態(tài)。在此狀態(tài)下消費(fèi)者不愿意增加商品的購買數(shù)量，同時(shí)也不愿意減少商品的購買數(shù)量，此時(shí)消費(fèi)者的總效用達(dá)到最大化。

假設(shè)消費(fèi)者的收入為[M]，消費(fèi)者購買并消費(fèi)X與Y兩種商品，X與Y的價(jià)格為[PX]與[PY]，所購買的X與Y的數(shù)量分別為[QX]與[QY]，X與Y兩種商品所帶來的邊際效用為[MUX]與[MUY]，每單位貨幣的邊際效用為[MUm]。因此，消費(fèi)者均衡的條件可以寫為：

[ PX·QX+PY·QY=M] （1）

[MUXPX=MUYPY=MUm] （2）

由式（2）推導(dǎo)可得：

[PXPY=MUXMUY] （3）

邊際替代率等于兩種商品的效用之比，即[MRSXY=MUXMUY]。因此，達(dá)到消費(fèi)者均衡時(shí)，邊際替代率和兩種商品的價(jià)格之比相等，在此情況下，消費(fèi)者效用極大化。

1.2 帕累托最優(yōu)理論

帕累托最優(yōu)[5]是指在某種既定的資源配置狀態(tài)下，任何資源分配的改變都不可能使得至少一個(gè)人的狀況變好的同時(shí)，又不使其他人的狀況變差。它是一種資源分配的理想狀態(tài)。由于云計(jì)算服務(wù)的請(qǐng)求是多個(gè)的，為多個(gè)請(qǐng)求分配一定的資源時(shí)，將涉及分配最優(yōu)問題。因此利用帕累托最優(yōu)理論可以評(píng)價(jià)云計(jì)算的資源分配是否達(dá)到最優(yōu)。

云計(jì)算系統(tǒng)中的資源都是有價(jià)格的，并且云計(jì)算的資源分配和社會(huì)上的資源分配一樣，都要極大化地滿足市場(chǎng)需求，盡量達(dá)到一種最優(yōu)狀態(tài)。所以，可以構(gòu)造一個(gè)基于消費(fèi)者均衡和帕累托最優(yōu)的云計(jì)算作業(yè)調(diào)度評(píng)價(jià)模型，用來評(píng)判云計(jì)算作業(yè)調(diào)度策略的優(yōu)劣。

1.3 CloudSim

CloudSim[6]是一款由澳大利亞墨爾本大學(xué)云計(jì)算和分布式系統(tǒng)實(shí)驗(yàn)室研發(fā)的云計(jì)算仿真框架，用于云計(jì)算基礎(chǔ)設(shè)施和應(yīng)用服務(wù)的建模、仿真和試驗(yàn)研究。CloudSim提供了虛擬化引擎，支持?jǐn)?shù)據(jù)中心在單一的物理計(jì)算節(jié)點(diǎn)上進(jìn)行建模和仿真，為虛擬化服務(wù)的空間共享和時(shí)間共享提供了靈活的分配處理內(nèi)核。自2009年推出以來，得到了廣泛的應(yīng)用，許多科研機(jī)構(gòu)和組織運(yùn)用CloudSim來進(jìn)行云計(jì)算仿真實(shí)驗(yàn)。CloudSim加快了云計(jì)算算法、方法和協(xié)議的研究與改進(jìn)，極大地推動(dòng)了云計(jì)算的發(fā)展[7]。

2 云計(jì)算作業(yè)調(diào)度評(píng)價(jià)模型

2.1 模型設(shè)計(jì)

文獻(xiàn)[8]把上述消費(fèi)者均衡理論和帕累托最優(yōu)理論與CloudSim結(jié)合起來，構(gòu)建出一個(gè)云計(jì)算作業(yè)調(diào)度評(píng)價(jià)模型。在模型中，輸入的是若干個(gè)云任務(wù)、每個(gè)云任務(wù)獲得的資源以及所有能夠分配的資源的組合，輸出的是每個(gè)云任務(wù)的效用值和邊際替代率。最后通過云任務(wù)的效用值判斷云任務(wù)的需求滿足情況，根據(jù)云任務(wù)的邊際替代率來判斷整個(gè)云計(jì)算系統(tǒng)作業(yè)調(diào)度算法的優(yōu)劣。模型的具體表述如下：

（1） 選取云計(jì)算系統(tǒng)中的內(nèi)存和硬盤作為需要分配的兩種資源，分別用[X]和[Y]表示，其價(jià)格分別為[PX]和[PY]。

（2） 云計(jì)算系統(tǒng)有一組服務(wù)的請(qǐng)求者，映射為一組云任務(wù)[T1，T2，…，Tn]。每個(gè)云任務(wù)的效用分別為[U1=UX，Y]，[U2=UX，Y]，[…]，[Un=UX，Y]，每個(gè)請(qǐng)求者愿意付出的費(fèi)用為[M]，云計(jì)算系統(tǒng)中存在一組虛擬機(jī)[C1，C2，…，Ck]，每個(gè)虛擬機(jī)中的內(nèi)存和硬盤大小都不相同。

（3） 服務(wù)請(qǐng)求者請(qǐng)求云服務(wù)，云計(jì)算系統(tǒng)通過作業(yè)調(diào)度算法Algo將云任務(wù)調(diào)度到相應(yīng)的虛擬機(jī)上，每個(gè)云任務(wù)獲得了一定數(shù)量的內(nèi)存和硬盤資源。模型計(jì)算每個(gè)云任務(wù)的效用值[Un]和邊際替代率[MRSn]，然后計(jì)算云任務(wù)[Tn]在其他虛擬機(jī)上運(yùn)行時(shí)的[Unk]和[MRSnk]，若[Un]大于其他的[Unk]，并且所有云任務(wù)的邊際替代率都相等，那么表明每個(gè)云任務(wù)的需求得到最大滿足，云計(jì)算系統(tǒng)的資源分配達(dá)到最優(yōu)。此時(shí)，可以判斷作業(yè)調(diào)度算法Algo是一個(gè)好的算法，值得應(yīng)用到云計(jì)算的作業(yè)調(diào)度中。若未能滿足上述要求，則判定作業(yè)調(diào)度算法Algo仍有改進(jìn)和優(yōu)化的余地。模型結(jié)構(gòu)如圖1所示。

圖1 云計(jì)算作業(yè)調(diào)度評(píng)價(jià)模型結(jié)構(gòu)圖

2.2 框架擴(kuò)展

為了便于計(jì)算服務(wù)請(qǐng)求的提交和以可視化的方式展示仿真結(jié)果，本文對(duì)CloudSim仿真框架進(jìn)行擴(kuò)展，增加了一個(gè)視圖層，用ExtJs技術(shù)實(shí)現(xiàn)，從而提高框架的交互性。擴(kuò)展后的框架結(jié)構(gòu)主要有三層，分別為視圖層，中間層和核心層。

云服務(wù)請(qǐng)求者在視圖層中選擇計(jì)算服務(wù)并提交，中間層將計(jì)算服務(wù)映射成云任務(wù)，將其提交給核心層。核心層接受中間層傳遞的云任務(wù)后，將云任務(wù)提交到CloudSim中進(jìn)行計(jì)算仿真。當(dāng)作業(yè)調(diào)度算法將云任務(wù)調(diào)度到虛擬機(jī)后，每個(gè)云任務(wù)便獲得了一定數(shù)量的內(nèi)存和硬盤，作業(yè)調(diào)度評(píng)價(jià)模型先計(jì)算每個(gè)云任務(wù)的效用值和邊際替代率，再計(jì)算當(dāng)該云任務(wù)在其他虛擬機(jī)上執(zhí)行時(shí)應(yīng)該得到的效用值和邊際替代率，然后將計(jì)算的數(shù)據(jù)結(jié)果返回給中間層。最后在視圖層中以統(tǒng)計(jì)圖的形式顯示出來，擴(kuò)展后的框架結(jié)構(gòu)如圖2所示。

圖2 擴(kuò)展后的框架結(jié)構(gòu)圖

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

本文利用擴(kuò)展后的CloudSim仿真框架進(jìn)行作業(yè)調(diào)度的仿真實(shí)驗(yàn)，以CloudSim框架自身提供的作業(yè)調(diào)度算法為仿真實(shí)驗(yàn)的作業(yè)調(diào)度策略，通過構(gòu)建的評(píng)價(jià)模型對(duì)算法進(jìn)行評(píng)價(jià)分析。

3.1 參數(shù)設(shè)置

通過CloudSim構(gòu)建仿真數(shù)據(jù)中心，數(shù)據(jù)中心提供8個(gè)虛擬機(jī)。每個(gè)虛擬機(jī)有內(nèi)存X和硬盤Y兩種資源，每個(gè)虛擬機(jī)的參數(shù)設(shè)置如表1所示。假設(shè)內(nèi)存和硬盤資源的價(jià)格分別為0.05元/MB和0.001元/MB。

表1 虛擬機(jī)配置

在本次實(shí)驗(yàn)中設(shè)有兩個(gè)計(jì)算服務(wù)供服務(wù)請(qǐng)求者選擇，其效用公式分別為[U1=lnX+lnY]和[U2=X0.5·Y；]假設(shè)每個(gè)計(jì)算服務(wù)的費(fèi)用M為15元。

3.2 仿真過程

仿真實(shí)驗(yàn)的具體過程如下：

（1） 在CloudSim中實(shí)現(xiàn)作業(yè)調(diào)度算法。在CloudSim中實(shí)現(xiàn)作業(yè)調(diào)度算法需要覆蓋CloudSim中DatacenterBroker類的bindCloudletToVM（）方法，該方法將單一的任務(wù)綁定至指定的單一虛擬機(jī)上運(yùn)行，在覆蓋的方法中可以實(shí)現(xiàn)自己的作業(yè)調(diào)度算法。本次實(shí)驗(yàn)使用CloudSim平臺(tái)自身提供的作業(yè)調(diào)度算法。

（2） 啟動(dòng)服務(wù)器，運(yùn)行仿真框架。本次實(shí)驗(yàn)采用B/S模式，將實(shí)現(xiàn)了作業(yè)調(diào)度算法后的CloudSim封裝成jar包，導(dǎo)入服務(wù)器端，在瀏覽器的網(wǎng)頁中進(jìn)行仿真實(shí)驗(yàn)。

（3） 選擇云服務(wù)，評(píng)價(jià)分析。仿真框架運(yùn)行后，在瀏覽器中顯示可供選擇的計(jì)算服務(wù)，如圖3所示。選擇計(jì)算服務(wù)1和計(jì)算服務(wù)2，然后提交。跳轉(zhuǎn)后的頁面顯示仿真結(jié)果，如圖4所示。需要說明的是，模型計(jì)算出來的效用值比較大，不利于比較，因此對(duì)每個(gè)云服務(wù)的效用值作了同比例的縮小，以便直觀地比較分析。

圖3 計(jì)算服務(wù)選擇頁面

圖4 仿真結(jié)果

3.3 結(jié)果分析

計(jì)算服務(wù)1在所有的虛擬機(jī)上的效用值如圖5所示，其中橫軸為虛擬機(jī)編號(hào)，縱軸為計(jì)算服務(wù)在不同虛擬機(jī)上運(yùn)行時(shí)的效用值。計(jì)算服務(wù)1在所有的虛擬機(jī)上的邊際替代率如圖6所示，其中橫軸為虛擬機(jī)編號(hào)，縱軸為計(jì)算服務(wù)在相應(yīng)虛擬機(jī)上運(yùn)行時(shí)的邊際替代率。計(jì)算服務(wù)2在所有的虛擬機(jī)上的效用如圖7所示。服務(wù)2在所有的虛擬機(jī)上的邊際替代率如圖8所示。

觀察仿真結(jié)果可知，通過作業(yè)調(diào)度算法進(jìn)行資源分配后，計(jì)算服務(wù)1在虛擬機(jī)1上執(zhí)行，計(jì)算服務(wù)2在虛擬機(jī)2上執(zhí)行。但計(jì)算服務(wù)1的效用值在虛擬機(jī)1上不是最大，計(jì)算服務(wù)2的效用值在虛擬機(jī)2上也不是最大的。同時(shí)，二者的邊際替代率也不相等。由此，可以判斷該算法不是最優(yōu)，還有優(yōu)化余地。

圖5 計(jì)算服務(wù)1的效用

圖6 計(jì)算服務(wù)1的邊際替代率

圖7 計(jì)算服務(wù)2的效用

4 結(jié) 語

本文將消費(fèi)者均衡和帕累托最優(yōu)理論引入云計(jì)算作業(yè)調(diào)度中，建立了一個(gè)基于消費(fèi)者均衡和帕累托最優(yōu)的云計(jì)算作業(yè)調(diào)度評(píng)價(jià)模型，并將模型嵌入CloudSim仿真框架中，同時(shí)對(duì)CloudSim進(jìn)行了可視化擴(kuò)展，使得框架的調(diào)用簡(jiǎn)單明了，擴(kuò)展后的CloudSim具有很好的交互性。研究者使用CloudSim進(jìn)行云計(jì)算作業(yè)調(diào)度實(shí)驗(yàn)時(shí)，可以利用該評(píng)價(jià)模型評(píng)價(jià)作業(yè)調(diào)度策略，以便尋找合適的作業(yè)調(diào)度算法。

圖8 計(jì)算服務(wù)2的邊際替代率

利用平臺(tái)自身提供的作業(yè)調(diào)度算法進(jìn)行仿真實(shí)驗(yàn)，演示了如何利用該評(píng)價(jià)模型作云計(jì)算的作業(yè)調(diào)度分析。不過，目前模型的應(yīng)用還處于初步階段，仿真實(shí)驗(yàn)僅限于計(jì)算資源為兩種，計(jì)算服務(wù)為兩個(gè)的情況。在現(xiàn)實(shí)當(dāng)中而云計(jì)算系統(tǒng)中需要考慮的資源遠(yuǎn)超兩種，計(jì)算服務(wù)一般也是多個(gè)的，下一步的研究工作需要對(duì)模型作進(jìn)一步的擴(kuò)展。

參考文獻(xiàn)

[1] MELL P， GRANCE T. The NIST definition of cloud computing [EB/OL]. [2012?03?11]. http：//www. wenku.baidu.com/view.

[2] 趙春燕.云環(huán)境下作業(yè)調(diào)度算法研究與實(shí)現(xiàn)[D].北京：北京交通大學(xué)，2009.

[3] 吳吉義，平玲娣，潘雪增，等.云計(jì)算：從概念到平臺(tái)[J].電信科學(xué)，2009（12）：23?30.

[4] 宋承先.現(xiàn)代西方經(jīng)濟(jì)學(xué)：微觀經(jīng)濟(jì)學(xué)[M].上海：復(fù)旦大學(xué)出版社，1994.

[5] 劉玉龍，胡鵬.基于帕累托最優(yōu)的新安江流域生態(tài)補(bǔ)償標(biāo)準(zhǔn)[J].水利學(xué)報(bào)，2009，39（6）：703?708.

[6] Roamware. CloudSim [EB/OL]. [2013?02?25]. http：//www.chinavalue.net.

[7] 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.

[8] 陳然.基于消費(fèi)者均衡和帕累托最優(yōu)的云計(jì)算資源分配策略研究[D].昆明：云南大學(xué)，2011.