基于CloudSim的作業(yè)調度算法評價模型設計與實現(xiàn)

王宇賓

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

關鍵詞： 云計算； CloudSim； 作業(yè)調度； 評價模型

中圖分類號： TN304.01?34 文獻標識碼： A 文章編號： 1004?373X（2015）14?0012?04

0 引 言

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

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

1 相關介紹

1.1 消費者均衡理論

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

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

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

[MUXPX=MUYPY=MUm] （2）

由式（2）推導可得：

[PXPY=MUXMUY] （3）

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

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

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

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

1.3 CloudSim

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

2 云計算作業(yè)調度評價模型

2.1 模型設計

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

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

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

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

圖1 云計算作業(yè)調度評價模型結構圖

2.2 框架擴展

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

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

圖2 擴展后的框架結構圖

3 仿真實驗

本文利用擴展后的CloudSim仿真框架進行作業(yè)調度的仿真實驗，以CloudSim框架自身提供的作業(yè)調度算法為仿真實驗的作業(yè)調度策略，通過構建的評價模型對算法進行評價分析。

3.1 參數設置

通過CloudSim構建仿真數據中心，數據中心提供8個虛擬機。每個虛擬機有內存X和硬盤Y兩種資源，每個虛擬機的參數設置如表1所示。假設內存和硬盤資源的價格分別為0.05元/MB和0.001元/MB。

表1 虛擬機配置

在本次實驗中設有兩個計算服務供服務請求者選擇，其效用公式分別為[U1=lnX+lnY]和[U2=X0.5·Y；]假設每個計算服務的費用M為15元。

3.2 仿真過程

仿真實驗的具體過程如下：

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

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

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

圖3 計算服務選擇頁面

圖4 仿真結果

3.3 結果分析

計算服務1在所有的虛擬機上的效用值如圖5所示，其中橫軸為虛擬機編號，縱軸為計算服務在不同虛擬機上運行時的效用值。計算服務1在所有的虛擬機上的邊際替代率如圖6所示，其中橫軸為虛擬機編號，縱軸為計算服務在相應虛擬機上運行時的邊際替代率。計算服務2在所有的虛擬機上的效用如圖7所示。服務2在所有的虛擬機上的邊際替代率如圖8所示。

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

圖5 計算服務1的效用

圖6 計算服務1的邊際替代率

圖7 計算服務2的效用

4 結 語

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

圖8 計算服務2的邊際替代率

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

參考文獻

[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è)調度算法研究與實現(xiàn)[D].北京：北京交通大學，2009.

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

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

[5] 劉玉龍，胡鵬.基于帕累托最優(yōu)的新安江流域生態(tài)補償標準[J].水利學報，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] 陳然.基于消費者均衡和帕累托最優(yōu)的云計算資源分配策略研究[D].昆明：云南大學，2011.