羅肖輝 徐美霞

（1.廣州商學(xué)院網(wǎng)絡(luò)中心 廣州 511363）（2.廣州商學(xué)院信息技術(shù)與工程學(xué)院 廣州 511363）

1 引言

作為新興的計算模式，云計算一直是目前最為熱點(diǎn)的研究領(lǐng)域，它被視為以科學(xué)研究為主的網(wǎng)格計算的商業(yè)化實(shí)現(xiàn)［1］。目前，對于云計算的定義業(yè)界仍未達(dá)成共識，具有代表性的一種觀點(diǎn)是：可以提供 IaaS［2］、SaaS［3］和 PaaS［4］等類型服務(wù)的資源池，資源池中的資源可以根據(jù)負(fù)載變化動態(tài)進(jìn)行配置，同時，資源的使用方式是采取即付即用方式。該定義強(qiáng)調(diào)了云計算環(huán)境的超大規(guī)模、虛擬化、可擴(kuò)展性、通用性及按需服務(wù)等特點(diǎn)。目前，各大廠商都相繼推出了云平臺，如谷歌的App Engine［5］、亞馬遜的 Amazon EC2［6］、IBM 的藍(lán)云［7］以及微軟 件的Azure OS［8］等?；谀M的方法允許用戶反復(fù)測試用戶的服務(wù)，而不需要大量的資金耗費(fèi)，并能夠在部署之前調(diào)節(jié)性能瓶頸。而作為新興的互聯(lián)網(wǎng)計算模式，目前的云仿真工具并不多，比較典型的有CloudSim［9］、SimCloud［10］及 云計 算平 臺［11］三 種。CloudSim云平臺［12］是墨爾本大學(xué)開發(fā)的開源仿真工具包，旨在量化針對不同應(yīng)用類型和不同服務(wù)模型的調(diào)度性能。

SimCloud是面向企業(yè)級的云平臺，它可以整合工程數(shù)值仿真軟件等資源，并配置動態(tài)的資源調(diào)度策略，為企業(yè)用戶提供統(tǒng)一、便捷、強(qiáng)大的云計算服務(wù)［13］。“云計算平臺”是李伯虎院士等提出的一種新型網(wǎng)絡(luò)化仿真平臺［14］。該平臺基于云計算理念，可以應(yīng)用于工程與非工程領(lǐng)域，實(shí)現(xiàn)線上資源的多用戶按需協(xié)同互操作與調(diào)度?！霸品抡嫫脚_”旨在改善仿真網(wǎng)格對多用戶在多粒度資源按需共享、協(xié)同、容錯遷移等方面的能力，進(jìn)而建立新的建模仿真模式“云仿真”。

鑒于CloudSim云平臺的開源性和使用的廣泛性，且提供虛擬引擎，有助于在一個數(shù)據(jù)中心節(jié)點(diǎn)上創(chuàng)建和管理多個獨(dú)立和協(xié)同的虛擬機(jī)服務(wù)，本文在CloudSim云平臺環(huán)境中研究了云計算的任務(wù)調(diào)度算法和基于節(jié)能的虛擬機(jī)部署算法，提出了五種任務(wù)調(diào)度算法和兩種節(jié)能算法，并通過平臺擴(kuò)展在CloudSim中實(shí)現(xiàn)了這七種算法，并配置了具體的云計算場景進(jìn)行了仿真實(shí)驗(yàn)與性能分析。

2 Cloud Sim體系結(jié)構(gòu)

CloudSim云平臺是一種開源模擬引擎，基于GridSim和離散事件驅(qū)動，可以模擬創(chuàng)建多種云計算環(huán)境中的實(shí)體，包括云數(shù)據(jù)中心、物理主機(jī)與虛擬機(jī)、各組件間的消息傳輸及時鐘管理等。并且，CloudSim作為通用的可擴(kuò)展的模擬框架，支持模擬新興的云計算基礎(chǔ)設(shè)施和管理服務(wù)。圖1是Cloud?Sim體系結(jié)構(gòu)。

2.1 用戶代碼層

用戶代碼層負(fù)責(zé)提供基本云實(shí)體，包括與主機(jī)（多臺機(jī)器、多規(guī)格）、應(yīng)用（任務(wù)及其需求）、虛擬機(jī)、大量用戶及其應(yīng)用類型和代理的調(diào)度策略的配置相關(guān)功能的用戶代碼。云應(yīng)用開發(fā)人員可在本層開發(fā)各種用戶需求分布、應(yīng)用的配置請求和云可用場景，進(jìn)行可靠性測試，從而實(shí)現(xiàn)自定義的云應(yīng)用調(diào)度算法。

2.2 云資源層

該層負(fù)責(zé)物理資源建模。云中的硬件可以通過擴(kuò)展數(shù)據(jù)中心實(shí)體實(shí)現(xiàn)，數(shù)據(jù)中心作為云系統(tǒng)的核心部分，負(fù)載管理物理主機(jī)，并對主機(jī)處理能力和存儲進(jìn)行分配，以及管理內(nèi)核的調(diào)度。在Cloud?Sim云平臺中，一個實(shí)體就是一個實(shí)例化組件，一個CloudSim組件可定義為一個類或者一個Cloud?Sim模型的類集。

圖1 CloudSim體系結(jié)構(gòu)

2.3 云服務(wù)層

盡管VM上下文是相互獨(dú)立的（通常指主存和輔存空間），但仍會共享CPU內(nèi)核和系統(tǒng)總線。因此，VM的可用資源仍受主機(jī)處理能力限制。為了實(shí)現(xiàn)不同環(huán)境下對不同調(diào)度策略的模擬，目前的CloudSim支持兩層VM調(diào)度［15］：主機(jī)層和VM層。主機(jī)層中的VM調(diào)度直接指定VM可獲取的處理能力，而VM層中，VM為在其內(nèi)運(yùn)行的獨(dú)立任務(wù)單元分配固定的處理能力。

兩層VM調(diào)度均實(shí)現(xiàn)了時間共享和空間共享。以下分析兩者在應(yīng)用任務(wù)調(diào)度性能上的區(qū)別。如圖2，某主機(jī)可運(yùn)行兩個VM，該主機(jī)擁有兩個CPU內(nèi)核，每個VM請求兩個內(nèi)核并執(zhí)行四個任務(wù)，T1、T2、T3、T4占用VM1，而T5、T6、T7、T8占用VM2。

圖2（a）中，VM主機(jī)層和任務(wù)單元均采用空間共享?？臻g共享中，VM請求兩個CPU內(nèi)核，對應(yīng)時間內(nèi)只能運(yùn)行一個VM。同樣的原因，對于VM1，其任務(wù)單元分配模式也是一樣的，由于一個任務(wù)單元只需一個CPU內(nèi)核，因此可以同時運(yùn)行任務(wù)單元T1和T2。此時，T3和T4在隊(duì)列中等候。則VM完成任務(wù)集T的完成時間是：

圖2 四種VM調(diào)度場景

其中，StartTime(T)表示云任務(wù)集的開始時間，MI(T)表示任務(wù)集T執(zhí)行的總指令數(shù)。這種策略下，一個有N個CPU內(nèi)核的主機(jī)總?cè)萘靠杀硎緸?/p>

其中，Cap(i)為內(nèi)核處理能力。

圖2（b）中，VM采用空間共享，任務(wù)單元采用時間共享。通過使用時間共享策略，VM完成任務(wù)集T的估計完成時間是：

其中，F(xiàn)inishTime(T)表示任務(wù)完成時間，NowTime(T)表示仿真時間，Cores(T)表示任務(wù)集的內(nèi)核需求量。時間共享下，單個VM可同時運(yùn)行多個任務(wù)。此時，主機(jī)總能力為

圖2（c）中，VM采用時間共享，任務(wù)單元采用空間共享。此時，內(nèi)核通過時間片原理將其處理能力在VM中進(jìn)行分配，而時間片本身以空間共享方式分配至任務(wù)。由于內(nèi)核共享，VM的可用處理能力是變化的。而任務(wù)單元是空間共享，表明內(nèi)核只執(zhí)行一個任務(wù)單元。

圖2（d）中，VM和任務(wù)單元均采用時間共享。此時，VM共享處理能力，并且同時將共享內(nèi)核分配至所有任務(wù)單元。

2.4 網(wǎng)絡(luò)層

實(shí)現(xiàn)云計算實(shí)體的復(fù)雜網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)等仿真實(shí)體進(jìn)行建模。CloudSim云平臺中的云實(shí)體（數(shù)據(jù)中心，主機(jī)，SaaS提供商及終端用戶）的內(nèi)部網(wǎng)絡(luò)是抽象的網(wǎng)絡(luò)概念。CloudSim實(shí)體間的網(wǎng)絡(luò)通信延時是通過延時矩陣模擬的，延時單位以毫秒表示。由延時矩陣的含義可知，通過事件管理引擎實(shí)現(xiàn)實(shí)體i到實(shí)體 j的消息傳遞的總時間為t+d，t是仿真開始時間，d是傳輸延時。

2.5 虛擬機(jī)服務(wù)層

虛擬機(jī)服務(wù)層主要用來管理任務(wù)單元的操作和虛擬機(jī)的生命周期。

2.6 用戶接口結(jié)構(gòu)層

該層實(shí)現(xiàn)任務(wù)單元和虛擬機(jī)間的接口創(chuàng)建。根據(jù)以上的層次結(jié)構(gòu)，將CloudSim的類劃分為如圖3所示的基礎(chǔ)類設(shè)計圖和如圖4所示的內(nèi)核模擬引擎類。

3 任務(wù)調(diào)度算法

對 CloudSim的 DatacenterBroker類的 bind?cloudlet ToVm（）進(jìn)行擴(kuò)展，實(shí)現(xiàn)任務(wù)與VM的綁定，圖5是任務(wù)調(diào)度流程及實(shí)現(xiàn)類。通過重載bind?cloudlet ToVm（int cloudletId，int VmId），設(shè)計五種任務(wù)調(diào)度算法。

圖3 CloudSim的基礎(chǔ)類設(shè)計圖

圖4 CloudSim內(nèi)核模擬引擎類圖

圖5 CloudSim云平臺下的任務(wù)調(diào)度方式

1）SSA（Sequenced Scheduling Algorithm，順序調(diào)度算法）：順序?qū)⑷蝿?wù)分配至所有VM，然后，重新分配新到來的任務(wù)時以第一個VM作為目標(biāo)，直至完成所有任務(wù)。SSA算法可以保證每個VM執(zhí)行的任務(wù)數(shù)量大致相同，實(shí)現(xiàn)負(fù)載均衡。

2）FCFSA（First Come First Service Algorithm，先來先服務(wù)調(diào)度算法）：按照先來先分配的方式，將任務(wù)分配至VM后，新到任務(wù)直接分配至最先完成任務(wù)的VM上，直至完成所有任務(wù)。FCFSA算法可以降低VM空閑時間，但處理能力較強(qiáng)的VM可能會負(fù)載過重，無法實(shí)現(xiàn)負(fù)載的均衡分配。

3）STFA（Shortest Task First Algorithm，短任務(wù)先調(diào)度算法）：將任務(wù)按大?。∕illion Instructor）升序排列之后，順序調(diào)度至VM。

4）BSA（Balance Scheduling Algorithm，均衡調(diào)度算法）：將任務(wù)按大?。∕illion Instructor）對其進(jìn)行降序排列，然后將VM按處理能力（MIPS）對其進(jìn)行降序排列，任務(wù)集和VM集重新排序后，再調(diào)用SSA算法對任務(wù)進(jìn)行調(diào)度。BSA算法的主要目標(biāo)是將長任務(wù)盡量調(diào)度到處理能力更強(qiáng)的VM上，而處理能力較弱的VM則執(zhí)行短任務(wù)，以便實(shí)現(xiàn)任務(wù)與VM之間的均衡調(diào)度，但這樣會降低部分VM的資源利用率。

5）GSA（reed Scheduling Algorithm，貪婪調(diào)度算法）：首先，將任務(wù)按大?。∕illion Instructor）對其進(jìn)行降序排列，將VM按MIPS進(jìn)行升序排列。定義矩陣E(i，j)，計算任務(wù)大小與VM處理能力的比值，并將值存入矩陣，然后在矩陣中作貪婪選擇：從E(0，j)中的任務(wù)開始，將其分配至最后一列VM，如果該調(diào)度結(jié)果最優(yōu)，完成分配；否則，將該任務(wù)調(diào)度至使當(dāng)前結(jié)果最優(yōu)的VM。

4 云節(jié)能技術(shù)

虛擬化技術(shù)（Virtulization Technology）可以通過在一個物理主機(jī)上實(shí)例化多個虛擬機(jī)的方式來解決數(shù)據(jù)中心的高能耗問題，從而改善資源利用率，增加投資回報率。在云計算環(huán)境中，向用戶提供確保以服務(wù)等級協(xié)議SLA定義的可靠QoS服務(wù)也是必不可少的，因此，對于云資源供應(yīng)商而言，高能效與高性能間必須達(dá)到平衡，以解決能耗問題的同時提供高可靠QoS保障。

4.1 能耗模型

通常情況下，CPU是云系統(tǒng)能耗中能耗最高的部件，作者將主要關(guān)注CPU在能耗管理方面的問題。而且，對于計算機(jī)密集型應(yīng)用，CPU的利用率與云系統(tǒng)負(fù)載是成正比的。本文實(shí)驗(yàn)部分，筆者將使用基于DVFS技術(shù)的線性額定關(guān)系功耗模型計算CPU的功能。

通常，對于CPU而言，空閑時服務(wù)器的功耗仍然是滿載時的70%，表明設(shè)置空閑服務(wù)器成休眠模式可以降低系統(tǒng)的總體能耗，本文的功耗模型為

其中，Pmax為系統(tǒng)滿載時的最大功耗，k為空閑時系統(tǒng)功耗比例，u為CPU的利用率。

通常，云系統(tǒng)中的負(fù)載執(zhí)行是動態(tài)變化的，因此，u通常表示為u(t)，那么，總能耗E可定義為

4.2 SAL違例

云環(huán)境中的服務(wù)質(zhì)量QoS是以服務(wù)等級協(xié)議SLA進(jìn)行表示，基于些特征屬性時行定義（最大化吞吐量，最小化響應(yīng)時間或延遲）。

SLA違例表示為：所有VM請求的MIPS（Uj，r(t)）與實(shí)際分配的 MIPS（Uj，a(t)）之差與虛擬機(jī)在其生命周期內(nèi)請求的MIPS總數(shù)之比：

其中，M表示VM數(shù)量。

4.3 節(jié)能算法

在CloudSim云平臺中實(shí)現(xiàn)三種節(jié)能算法：DVFS、NPA以及STH算法。

1）DVFS（動態(tài)電壓頻率調(diào)整），算法思想是：考慮到執(zhí)行任務(wù)時CPU利用率的不充分，降低CPU供電電壓和時鐘頻率的方式達(dá)到降低CPU性能的目的，該方法不僅可以極大降低CPU的功耗，還可以保證服務(wù)性能。

2）STH算法。通過設(shè)置一個CPU利用率的閾值，在調(diào)度過程中始終保持其利用率不高于該閾值。其目的是為CPU預(yù)留部分處理能力，以滿足對資源的動態(tài)增加需求，避免VM合并帶來的SLA違例。若調(diào)度過程中CPU利用率高于閾值，則調(diào)用VM遷移算法降低利用率至閾值以內(nèi)。

3）主機(jī)滿載算法MPA：保持主機(jī)的最大功耗狀態(tài)進(jìn)行任務(wù)執(zhí)行。MPA算法作為性能分析的比較算法。

4.4 任務(wù)調(diào)度的實(shí)體間通信

圖6顯示了CloudSim進(jìn)行任務(wù)調(diào)度時實(shí)體間的通信流程。仿真初始化時，DataCenter實(shí)體通過CIS實(shí)體進(jìn)行注冊，DataCenterBroker在CIS中查詢信息以獲取云提供商列表，DataCenterBroker會選擇CIS建議的云來部署應(yīng)用。任務(wù)被分配到各自的VM之后，會持續(xù)更新任務(wù)處理過程。此時，DataCenter會調(diào)用 updateVMsProcessing（）管理主機(jī)。主機(jī)層上，updateVMsProcessing（）會觸發(fā)up?dateCloulets-Processing（），以指示VM更新任務(wù)單元狀態(tài)。該方法與updateVMsProcessing（）有類似的作用，不同之處在于updateClouletsProcessing（）方法在VM層上。調(diào)用updateClouletsProcessing（）方法后，VMs將返回任務(wù)單元的下一個期望完成時間，并傳送所有完成時間中的最小值至DateCenter實(shí)體。

圖6 CloudSim實(shí)體通信流程

5 Cloud Sim擴(kuò)展與任務(wù)調(diào)度

通過擴(kuò)展CloudSim，實(shí)現(xiàn)所提算法，并對擴(kuò)展后的仿真工具包進(jìn)行了重編譯，并對算法性能進(jìn)行了分析。

5.1 任務(wù)調(diào)度實(shí)驗(yàn)分析

創(chuàng)建一個云數(shù)據(jù)中心，主機(jī)數(shù)量、虛擬機(jī)和云任務(wù)的數(shù)量分別為1、4和8。具體參數(shù)如表1～表4所示，表1為用戶任務(wù)單元參數(shù)，表2為虛擬機(jī)VM相關(guān)參數(shù)，表3為數(shù)據(jù)中心相關(guān)參數(shù)，表4為主機(jī)相關(guān)參數(shù)。

表1 云用戶任務(wù)單元（Cloudlet）參數(shù)列表

表2 虛擬機(jī)（VM）列表

表3 數(shù)據(jù)中心（Datacenter）列表

表4 主機(jī)（Host）列表

5.2 實(shí)驗(yàn)結(jié)果與分析

圖7和圖8分別是單個任務(wù)的完成時間和任務(wù)完成總時間。綜合兩個圖可以看出，GSA算法的完成時間是最短的，主要原因是由于GSA在所有VM上對任務(wù)做貪心選擇策略，而STFA沒有考慮VM處理能力間的差異，其任務(wù)完成時間最長。同時，SSA與FCFSA的完成時間是大致相等的，這主要是由于兩種算法在開始階段的任務(wù)分配方式是順序的，但隨著任務(wù)量的增加，尤其任務(wù)量遠(yuǎn)大于VM數(shù)量時，F(xiàn)CFSA將具有更大的優(yōu)勢?？傮w看來，BSA算法是次優(yōu)算法。

圖7 單個任務(wù)的完成時間

圖8 任務(wù)完成總時間

5.3 節(jié)能算法實(shí)驗(yàn)分析

創(chuàng)建以下云場景，包括一個數(shù)據(jù)中心，主機(jī)數(shù)量變化范圍為［10，50］，部署虛擬機(jī)變化范圍為［20，60］，云任務(wù)的變化范圍為［20，60］。虛擬機(jī)請求的MIPS分別為｛250，500，750，1000｝，虛擬機(jī)其他 參 數(shù) 如 下 ：pesNumber=1，ram=128，bw=2500，size=2500。主機(jī)處理能MIPS=｛1000，2000，3000｝，主機(jī)其他參數(shù)如下：raw=10000，storage=10000，bw=10000，云任務(wù)大小為150000MI。

圖9 算法性能比較

圖9從能耗、虛擬機(jī)遷移次數(shù)及SLA違例三個方面比較了STH算法、DVFS算法及MPA算法的性能?？梢钥闯?，STH算法的能耗是最少的，因?yàn)镾TH算法通過虛擬機(jī)的動態(tài)遷移與合并，基于當(dāng)前的動態(tài)資源需求減少物理節(jié)點(diǎn)的使用數(shù)量，從而達(dá)到節(jié)省能耗的目的。MPA算法中主機(jī)功耗一直維持最大，因此能耗也最大，DVFS算法可以根據(jù)任務(wù)需求自適應(yīng)調(diào)整CPU的頻率，這極大降低了CPU能耗。DVFS算法和MPA算法均屬于靜態(tài)算法，不存在虛擬機(jī)的遷移操作，且均得到了任務(wù)請求的資源，故不存在SLA違例。

圖10 STH固定閾值對于算法性能

圖10考察了閾值算法STH中固定閾值對于算法性能的影響?？傮w看來，當(dāng)增加固定閾值時，能耗會降低，但會增加SLA的違例次數(shù)，原因在于隨著閾值的增大，虛擬機(jī)合并的機(jī)會也會增多，這樣虛擬機(jī)遷移也會更加頻繁。可以看出，閾值的選擇需要折衷，并非越大越好，因?yàn)槟芎呐c性能是需要均衡考慮的。

6 結(jié)語

本文詳細(xì)分析與研究了CloudSim云平臺的工作原理，主要剖析了CloudSim在仿真機(jī)制中提供的層次模型，在以上工作的基礎(chǔ)上，研究了云環(huán)境中的任務(wù)調(diào)度問題，提出了五種任務(wù)調(diào)度算法，算法均只考慮了任務(wù)的執(zhí)行時間，忽略了主機(jī)能耗。進(jìn)一步針對這一問題，在CloudSim云平臺中實(shí)現(xiàn)了兩種節(jié)能算法。通過擴(kuò)展CloudSim的相關(guān)類，對以上七種算法進(jìn)行了仿真實(shí)驗(yàn)分析，仿真結(jié)果證明了算法的有效性。而進(jìn)一步的研究在于：1）改進(jìn)文中的固定閾值算法，利用負(fù)載預(yù)測機(jī)制，根據(jù)任務(wù)屬性，動態(tài)地進(jìn)行任務(wù)及虛擬機(jī)的部署，以便最大限度地實(shí)現(xiàn)能耗與性能的均衡；2）資源分配的負(fù)載均衡問題。負(fù)載均衡機(jī)制可以通過虛擬機(jī)遷移盡量減輕物理節(jié)點(diǎn)的負(fù)載，避免產(chǎn)生熱點(diǎn)問題，提高云資源利用效率，滿足用戶對資源的需求，為云環(huán)境下高效的資源利用提供良好的基礎(chǔ)。