基于云計算的“用戶期待”任務(wù)調(diào)度算法的研究

劉之家 張體榮 謝雄程

（廣西師范學(xué)院計算機與信息工程學(xué)院，廣西 南寧 530001）

基于云計算的“用戶期待”任務(wù)調(diào)度算法的研究

劉之家 張體榮 謝雄程

（廣西師范學(xué)院計算機與信息工程學(xué)院，廣西 南寧 530001）

文章在云計算提供的各項服務(wù)質(zhì)量基礎(chǔ)上，提出了云計算任務(wù)調(diào)度的用戶期待函數(shù)，并根據(jù)用戶期待函數(shù)和服務(wù)質(zhì)量的任務(wù)分類，提出了用戶期待函數(shù)的任務(wù)調(diào)度算法，最后在云計算仿真平臺 CloudSim上進行仿真實驗與分析。實驗結(jié)果表明，該任務(wù)調(diào)度算法在調(diào)度時間、可靠性與費用等方面具有一定的優(yōu)勢。

云計算；服務(wù)質(zhì)量；任務(wù)調(diào)度；仿真

（一）引言

云計算是由分布式計算、并行計算、網(wǎng)格計算、虛擬技術(shù)、普適計算等概念混合演化而來的一種新型的計算模型。它將計算任務(wù)分布在大量計算機、存儲設(shè)備等組成的資源池上，用戶可以根據(jù)需要獲取計算能力、存儲空間和各種軟件服務(wù)，是一種以Internet為基礎(chǔ)向用戶提供信息服務(wù)的商業(yè)模式，其目標(biāo)是為用戶動態(tài)地提供可靠的、可定制的、服務(wù)質(zhì)量( QoS)保證的IT計算服務(wù)環(huán)境。然而，不同的用戶有不同的需求，云計算必須提供用戶滿意的服務(wù)，服務(wù)質(zhì)量 QoS成為了衡量用戶使用云計算服務(wù)滿意程度的標(biāo)準(zhǔn)。這樣對云計算的作業(yè)調(diào)度和資源分配提出了更高的要求。

多任務(wù)調(diào)度問題是計算機界公認(rèn)的NP難題，采用啟發(fā)式方法可以得到次最優(yōu)解，而固定優(yōu)先級調(diào)度策略可能會引起低優(yōu)先級線程饑餓和短程任務(wù)滯后，先到先處理調(diào)度策略可能會引起高價值任務(wù)錯失最佳處理時刻。因此，對云計算的任務(wù)調(diào)度進行研究具有重要的意義。

（二）基本理論

1.用戶期待函數(shù)的定義

在云計算中，服務(wù)質(zhì)量 QoS是衡量用戶使用云計算服務(wù)滿意程度的標(biāo)準(zhǔn)。云計算為互聯(lián)網(wǎng)上的各類用戶提供不同的服務(wù)，但由于用戶的多樣性，為了給用戶提供滿意的服務(wù)質(zhì)量，云計算的任務(wù)調(diào)度和資源必須得到合理的分配。文章通過引入資源分配的用戶期待函數(shù)對用戶資源量的需求進行分析，任務(wù)的用戶期待函數(shù)定義為：

其中， 為常量，且0<θ≤1，AR為任務(wù)的實際資源分配量，ER為任務(wù)期待的資源量。

2.基于QoS的任務(wù)分類

按照 QoS標(biāo)準(zhǔn)可將任務(wù)按完成時間、帶寬、可靠性、費用分為四類，可建立如下的量化標(biāo)準(zhǔn)：

（1）完成時間：任務(wù)的時間性QoS描述包括開始時間、最遲完成時間、總完成時間、結(jié)束時間等。

Twait是從任務(wù)提交到被分配處理資源的等待時間，Texec為任務(wù)執(zhí)行時間，Ttrans為任務(wù)傳輸時間。設(shè)任務(wù)的期待完成時間為Texpt，則用戶期待函數(shù)表示為：

（3）費用：虛擬機按照單位對資源計費，任務(wù)消費的全部費用costvm為：

P1表示資源數(shù)量，C參數(shù)表示單位資源價格，設(shè)costuser為用戶期待的費用，則用戶期待函數(shù)為：

（4）可靠性：對于可靠性要求較高的用戶任務(wù)來說，選擇可靠性高的資源為其提供服務(wù)，能夠顯著提高其服務(wù)質(zhì)量。設(shè)虛擬機的故障率為p，用戶期待的任務(wù)完成率psucc由用戶指定，則用戶期待函數(shù)為：

當(dāng)用戶任務(wù)有多方面 QoS需求時，可將上面討論的完成時間、帶寬、費用、可靠性的用戶期待評判函數(shù)進行綜合，得到綜合的用戶期待函數(shù)：

根據(jù)以上四點描述，完成時間表示對實時性要求較高的用戶，需要任務(wù)在盡可能少的時間內(nèi)完成。當(dāng)客戶對通信帶寬要求較高時，則需要優(yōu)先考慮帶寬要求。可靠性表示對長期運行任務(wù)的用戶，需要云計算提供穩(wěn)定可靠的性能，如云存儲服務(wù)。此外，云計算按需付費，使用費用是用戶關(guān)注的一個因素，對于希望廉價的服務(wù)的用戶來說，費用是一個衡量標(biāo)準(zhǔn)。

（三）研究方法

云計算環(huán)境的特點包括了支持基礎(chǔ)設(shè)施的建模與仿真，支持?jǐn)?shù)據(jù)中心、服務(wù)代理人、調(diào)度和分配策略的平臺。它提供虛擬化引擎，在數(shù)據(jù)中心節(jié)點上幫助建立和管理多重的、獨立的、協(xié)同的虛擬化服務(wù)。對虛擬化服務(wù)分配處理核心時能夠在時間共享和空間共享之間靈活切換。

1.云計算的任務(wù)調(diào)度模型

任務(wù)調(diào)度模型的工作方式如圖 1所示，云信息服務(wù)和數(shù)據(jù)調(diào)度中心實現(xiàn)資源發(fā)現(xiàn)和信息交互，是任務(wù)調(diào)度的核心。設(shè)計的調(diào)度算法可在數(shù)據(jù)調(diào)度中心中實現(xiàn)，從而實現(xiàn)調(diào)度算法的模擬。

圖1 云計算的任務(wù)調(diào)度模型

2.任務(wù)調(diào)度流程

云計算調(diào)度的數(shù)據(jù)流程如圖 2所示，數(shù)據(jù)中心的資源創(chuàng)建以后向 CIS云信息服務(wù)注冊，由數(shù)據(jù)中心調(diào)度管理信息的交互過程。

圖2 調(diào)度數(shù)據(jù)流

3.用戶期待函數(shù)的任務(wù)調(diào)度算法流程

Step 1：給定任務(wù)參數(shù)表，表中含有用戶所期待的資源與用戶的任務(wù)大小。

Step 2：獲取虛擬機的資源，根據(jù)資源分別計算虛擬機的性能。

Step 3：按QoS的任務(wù)類型計算綜合Jzh，為了方便計算，可用expJzh代替。Step 4：根據(jù)Step 2與Step 3 的計算結(jié)果將虛擬機與任務(wù)按性能與用戶期待值從大到小進行對應(yīng)的映射與綁定，任務(wù)數(shù)按虛擬機數(shù)進行平均分配。

Step 5：執(zhí)行并統(tǒng)計和返回所有任務(wù)的總花費。

（四）仿真實驗

1.仿真平臺

云計算的仿真平臺目前有澳大利亞墨爾本大學(xué)設(shè)計的CloudSim，它是在網(wǎng)格實驗室和 Gridbus基礎(chǔ)上建立的。仿真的過程分為以下步驟進行：

（1）初始化GridSim庫

GridSim.init(num_user,calendar,trace_flag,exclu de_from_file, exclude_from_processing, report_name);

（2）創(chuàng)建數(shù)據(jù)中心

在仿真平臺中，一個數(shù)據(jù)中心由一臺或多臺 Machine組成，而一臺Machine可由一個或多個PEs或CPUs組成。本實驗程序創(chuàng)建了兩個數(shù)據(jù)中心，每個數(shù)據(jù)中心有兩臺Machine，其中一臺Machine由4個PEs組成，另一臺由2個PEs組成。

DataCenter datacenter0 = createDatacenter("Datacenter_0");

DataCenter datacenter1 = createDatacenter("Datacenter_1");

（3）創(chuàng)建Broker

DatacenterBroker broker = createBroker();

int brokerId = broker.get_id();

（4）創(chuàng)建虛擬機

VirtualMachine vm1 = new VirtualMachine(new VMCharacteristics(vmid, brokerId, size, memory, bw,vcpus, priority, vmm, new TimeSharedVMScheduler()));

（5）創(chuàng)建云任務(wù)

cloudletList = new CloudletList();

Cloudlet cloudlet1 = new Cloudlet(id, length,file_size, output_size);

Cloudlet1.setUserID(brokerId);

（6）啟動仿真

GridSim.startGridSimulation();

（7）統(tǒng)計結(jié)果

CloudletList newList = broker.getCloudletList();

GridSim.stopGridSimulation();

printCloudletList(newList);

datacenter0.printDebts();

datacenter1.printDebts();

具體的仿真程序編寫過程可參考CloudSim網(wǎng)站提供的編程樣例。

2.實驗數(shù)據(jù)

本實驗采用前面兩類任務(wù)的調(diào)度來模擬用戶期待函數(shù)的任務(wù)調(diào)度，如表1所示包含有8個任務(wù)，表中的參數(shù)分別表示為任務(wù)標(biāo)識、長度、提交到數(shù)據(jù)中心的文件大小、數(shù)據(jù)中心輸出文件的大小、任務(wù)期待的帶寬。表2包含了4個虛擬機的參數(shù)，分別表示虛擬機的身份標(biāo)識、CPU個數(shù)、內(nèi)存大小、帶寬、虛擬機性參數(shù)。其中虛擬機性能參數(shù)大小等于 CPU個數(shù)，即內(nèi)存大小與帶寬的乘積，這個值越大，表示虛擬機的性能越好。

表1 任務(wù)參數(shù)表

表2 虛擬機參數(shù)列表

3.實驗方法與分析

文章的任務(wù)調(diào)度算法在仿真環(huán)境中實現(xiàn)任務(wù)的調(diào)度有兩種方法實現(xiàn)，一種是重載CloudSim的DatacenterBroker類的bindCloudletToVM()方法，該方法是將單一的任務(wù)綁定到指定的單一虛擬機上運行，在重載的方法里可實現(xiàn)自己的任務(wù)調(diào)度策略，但是重載后需重新編譯CloudSim，這種方法屬于內(nèi)部嵌入的方式。另一種方法是在編寫仿真程序時通過調(diào)度算法算出各個任務(wù)的優(yōu)先級，再調(diào)用bindCloudletToVM方法將任務(wù)與虛擬機進行綁定，此種方法屬于外部接口方式。文章的仿真程序采用外部接口方式，云任務(wù)與虛擬機的綁定部分代碼如下所示：

broker.bindCloudletToVM(cloudlet[0].getCloudlet Id(),vm[3].getVmId());

broker.bindCloudletToVM(cloudlet[1].getCloudlet Id(),vm[3].getVmId());

broker.bindCloudletToVM(cloudlet[2].getCloudlet Id(),vm[1].getVmId());

broker.bindCloudletToVM(cloudlet[3].getCloudlet Id(),vm[0].getVmId());

broker.bindCloudletToVM(cloudlet[4].getCloudlet Id(),vm[2].getVmId());

broker.bindCloudletToVM(cloudlet[5].getCloudlet Id(),vm[2].getVmId());

broker.bindCloudletToVM(cloudlet[6].getCloudlet Id(),vm[0].getVmId());

broker.bindCloudletToVM(cloudlet[7].getCloudlet Id(),vm[1].getVmId());

本程序中有4個虛擬機，每個虛擬機處理2個任務(wù)。根據(jù)式4計算expJbw值，這與計算Jbw值的效果是等價的，式中取1。如表3所示，表中“按帶寬VMID”表示按帶寬條件進行任務(wù)與虛擬機的映射，實驗測得 Processing Cost的值為1370.25。同理，再進行“按完成時間”計算expJT，然后進行任務(wù)與虛擬機的映射，實驗測得 Processing Cost的值為1089.75。expJT的計算可由輸入數(shù)據(jù)中心的文件大小與輸出數(shù)據(jù)中心的文件大小比值進行估算。

經(jīng)過與表5中Processing Cost為1265.25的值進行比較可知，單純的按帶寬進行任務(wù)調(diào)度效果反而不如系統(tǒng)默認(rèn)的最小完成時間調(diào)度算法效率高，但按完成時間測試得到的結(jié)果略高于最小完成時間調(diào)度算法。因此，考慮將“按帶寬VMID”與“按完成時間”二者綜合起來計算函數(shù)f(expJ)的綜合值，測試結(jié)果如表4所示。

表3 云任務(wù)與虛擬機映射表

表4 用戶期待函數(shù)的任務(wù)調(diào)度算法實驗結(jié)果

表5 最小完成時間調(diào)度算法實驗結(jié)果

對比表4與表5的實驗結(jié)果，從單個任務(wù)的最小完成時間來說，用戶期待函數(shù)的調(diào)度算法與最小完成時間的調(diào)度算法相比沒有優(yōu)勢，如任務(wù) 6按最小完成時間算法時的花費值為24，而用戶期待函數(shù)調(diào)度則花費值為84，二者相差較大。但從整體花費上相比，用戶期待函數(shù)調(diào)度的綜合花費為1089.75，要優(yōu)于最小完成時間的調(diào)度算法的花費值1265.25。因此，用戶期待函數(shù)的調(diào)度算法從平均性能來說要比最小完成時間更好地滿足用戶需求。

（五）結(jié)束語

隨著云計算技術(shù)的發(fā)展與應(yīng)用，對云計算服務(wù)質(zhì)量的要求不斷提高。文章通過引入用戶期待函數(shù)對用戶任務(wù)調(diào)度策略進行研究。仿真實驗結(jié)果表明，用戶期待函數(shù)的任務(wù)調(diào)度算法與傳統(tǒng)的最小完成時間任務(wù)調(diào)度算法從平均性能來說具有一定的優(yōu)勢，而研究更理想更有效的云計算任務(wù)調(diào)度算法是下一步的工作目標(biāo)。

[1]宋遠(yuǎn)駿,楊孝宗,李德毅,崔東華.多機多任務(wù)實時系統(tǒng)云調(diào)度策略[J].計算機學(xué)報,2000,23(10):1107-1110.

[2]陳全,鄧倩妮.云計算及其關(guān)鍵技術(shù)[J].計算機應(yīng)用,2009,2(9):2562-2568.

[3]郭本俊,王鵬,陳高云,黃健.基于 MPI的云計算模型[J].計算機工程,2009,35(24).

[4]Rodrigo N. Calheiros, Rajiv Ranjan, Cesar A. F. De Rose,Rajkumar Buyya.CloudSim.A Novel Framework for Modeling and Simulation of Cloud Computing Infrastructures and Services[R]. Technical Report, GRIDS-TR-2009-1,2009.

[5]張海賓,唐琳莎,劉立祥.網(wǎng)格調(diào)度綜述[J].計算機工程與設(shè)計,2009,30(9):2151-2154.

TP301.6

A

1008-1151(2011)04-0075-03

2011-01-21

國家自然科學(xué)基金（60864001），廣西教育廳基金項目（200911MS144）

劉之家（1963－），男（壯族），廣西南寧人，廣西師范學(xué)院計算機與信息工程學(xué)院講師，研究生，研究方向為網(wǎng)絡(luò)技術(shù)、云計算；張體榮（1965－），男，廣西全州人，廣西師范學(xué)院計算機與信息工程學(xué)院工程師、企業(yè)管理咨詢師，研究生，研究方向為管理軟件、云應(yīng)用；謝雄程（1972－），男，廣西南寧人，廣西師范學(xué)院計算機與信息工程學(xué)院講師，碩士，研究方向為計算機網(wǎng)絡(luò)。