彭紅姣　李安南　曹新欣

摘要：該文對基于QoS約束的資源調(diào)度策略進(jìn)行了研究：根據(jù)用戶對QoS的偏好，建立資源調(diào)度模型。實(shí)現(xiàn)了基于QoS約束的資源調(diào)度算法。通過實(shí)驗，擴(kuò)展了CloudSim中的基礎(chǔ)類，在CloudSim平臺上對本文MMPS算法算法進(jìn)行模擬驗證。實(shí)驗結(jié)果表明，該文策略能更好地滿足服務(wù)質(zhì)量。

關(guān)鍵詞：云計算；任務(wù)調(diào)度；QoS；資源；cloudsim

中圖分類號：TP311 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2014）30-7027-02

近年來，互聯(lián)網(wǎng)需要處理的業(yè)務(wù)量快速增長，如何處理海量數(shù)據(jù)成為互聯(lián)網(wǎng)未來發(fā)展的關(guān)鍵。在這種背景下，基于分布式計算特別是網(wǎng)格技術(shù)的發(fā)展，產(chǎn)生了一種新型服務(wù)計算模型：云計算[1]，即將計算任務(wù)分布在大量計算機(jī)構(gòu)成的資源池上，使各種應(yīng)用系統(tǒng)能夠根據(jù)需要獲取計算力、存儲空間和信息服務(wù)，其核心問題是資源調(diào)度管理[2]。云計算資源調(diào)度是指在特定的云環(huán)境中，根據(jù)一定的資源使用規(guī)則，在不同的資源使用者之間進(jìn)行的資源調(diào)整過程?，F(xiàn)有的資源調(diào)度策略大多是通過虛擬機(jī)級別上的調(diào)度技術(shù)結(jié)合一定的調(diào)度策略來為虛擬機(jī)內(nèi)部應(yīng)用做資源調(diào)度，調(diào)度算法過于簡單，判斷需要進(jìn)行推測執(zhí)行任務(wù)的算法造成過多任務(wù)需要推測執(zhí)行，降低了整個任務(wù)的性能。所以在虛擬機(jī)級別上采用什么算法實(shí)現(xiàn)資源調(diào)度是暨待解決的一個難題。

目前，對于云計算資源調(diào)度資源分配的研究仍存在許多問題，各大云計算廠商關(guān)注的問題主要集中在虛擬機(jī)資源管理、任務(wù)調(diào)度、系統(tǒng)負(fù)載均衡上。而每個云計算廠商都以自己的基礎(chǔ)設(shè)施架構(gòu)來構(gòu)建，缺乏統(tǒng)一的規(guī)范和標(biāo)準(zhǔn)，使得云環(huán)境下的資源調(diào)度和資源管理呈現(xiàn)出多樣化的特點(diǎn)。云計算由分布式計算和網(wǎng)格計算發(fā)展而來，兩者的資源調(diào)度和分配經(jīng)過多年的研究已相當(dāng)成熟，對于云計算環(huán)境下的資源調(diào)度資源分配有一定的可借鑒性和相通性。但是以虛擬化技術(shù)為基礎(chǔ)，并側(cè)重于商業(yè)化模式的應(yīng)用理念使得云計算的資源調(diào)度資源分配具有自己的特點(diǎn)不能生搬硬套網(wǎng)格計算中的任務(wù)調(diào)度策略。

1 一種基于QOS約束簡化的資源調(diào)度策略

1.1 任務(wù)描述

用戶提交服務(wù)請求是一個隨機(jī)過程，任務(wù)到達(dá)云計算系統(tǒng)的時間應(yīng)服從隨機(jī)分布。從任務(wù)對計算資源需求角度看，任務(wù)類型具有多樣性，常見的包括計算密集型、通信密集型、數(shù)據(jù)密集型和I/O密集型等等[3]。

1.2 資源描述

云計算以一種簡化機(jī)制調(diào)度作業(yè)，把任務(wù)所需資源用虛擬機(jī)來表現(xiàn)，所謂的資源搜索從本質(zhì)上看就是搜索虛擬機(jī)，作業(yè)調(diào)度就是一種以優(yōu)化的方式將任務(wù)與資源進(jìn)行映射匹配。物理資源性能參數(shù)一般包括CPU、內(nèi)存、存儲空間、帶寬、I/O存取率、故障率等等，虛擬機(jī)也是一種物理資源。該文對虛擬機(jī)性能參數(shù)的選取包括：CPU、內(nèi)存、存儲空間以及帶寬。

1.3 Qos參數(shù)選取

云計算目的是為不同用戶提供應(yīng)用服務(wù)，在資源需求方面各類用戶的期望不一樣，如：實(shí)時性，低費(fèi)用，穩(wěn)定的網(wǎng)絡(luò)等。QoS作為衡量服務(wù)滿意度的一個重要標(biāo)準(zhǔn)，云計算對用戶的服務(wù)可以通過QoS來評價，該文主要考慮三個QoS參數(shù)：完成時間、網(wǎng)絡(luò)帶寬、費(fèi)用。

1.4 負(fù)載均衡策略

負(fù)載均衡是把系統(tǒng)中的資源按性能進(jìn)行負(fù)載分配。目前主流操作系統(tǒng)在任務(wù)分配方面使用了一種簡單方案：根據(jù)物理機(jī)CPU性能按比例分?jǐn)?。常用的?fù)載指標(biāo)（Index）包括CPU就緒隊列長度、進(jìn)程響應(yīng)時間、內(nèi)存使用情況、磁盤訪問頻度，CPU和I/O利用率等，以及異構(gòu)節(jié)點(diǎn)處理能力上的差別。

1.5 任務(wù)與資源映射模型

云計算環(huán)境下資源優(yōu)化分配可描述為：當(dāng)任務(wù)隨機(jī)到達(dá)計算節(jié)點(diǎn)時，根據(jù)任務(wù)的類型、長度和計算節(jié)點(diǎn)的執(zhí)行狀態(tài)（主要是負(fù)載量），從任務(wù)開始執(zhí)行到結(jié)束期間，當(dāng)云計算系統(tǒng)總代價最小時，最大限度地滿足QoS。該文云計算系統(tǒng)總代價包括兩個部分：節(jié)點(diǎn)負(fù)載量和任務(wù)計算代價。因此，該文所研究的問題就轉(zhuǎn)化為——基于多目標(biāo)約束的最優(yōu)解問題?；赒oS約束的任務(wù)計算代價粗粒度綜合評價表達(dá)式如（1） 所示：

[Costvm=（Jft-eiF）2+（Jbw-eiB）2+（Jcs-eiS）2] （1）

當(dāng)Costvm值越小，任務(wù)與虛擬機(jī)的匹配度越高，任務(wù)得到的服務(wù)質(zhì)量越高；當(dāng)Costvm值越大，任務(wù)與虛擬機(jī)的匹配度越低，任務(wù)得到的服務(wù)質(zhì)量越低；當(dāng)Costvm=0時，任務(wù)與虛擬機(jī)匹配度最高，即完全匹配。

2 實(shí)驗仿真與結(jié)果分析

2.1 實(shí)驗仿真數(shù)據(jù)

云計算系統(tǒng)調(diào)度模型，物理環(huán)境不變條件下，調(diào)度系統(tǒng)性能優(yōu)劣主要取決于資源映射和調(diào)度規(guī)則，是整個調(diào)度系統(tǒng)核心。該文實(shí)現(xiàn)了一種基于QoS簡單約束的最小代價最大服務(wù)概率算法（Minimum cost and Maximum Probability of Service， MMPS）算法。

本文MMPS算法仿真實(shí)驗在CloudSim上進(jìn)行，根據(jù)任務(wù)執(zhí)行成本、虛擬機(jī)負(fù)載量和任務(wù)分配帶寬進(jìn)行了實(shí)驗對比，選取5個虛擬機(jī)、9個任務(wù)，實(shí)驗環(huán)境涉及的相關(guān)參數(shù)見表1。

2.2 實(shí)驗結(jié)果分析

為驗證MMPS算法有效性和進(jìn)一步增加實(shí)驗的對比性，該文選擇順序分配策略，貪心策略和隨機(jī)分配策略作為對比實(shí)驗，全部任務(wù)總執(zhí)行時間實(shí)驗結(jié)果如表2所示。

MMPS算法的任務(wù)總執(zhí)行時間最短，貪心策略算法任務(wù)總執(zhí)行時間略長于MMPS算法，順序分配算法的任務(wù)總執(zhí)行時間最長。MMPS算法比貪心策略算法節(jié)省了約8.55%的時間，MMPS算法比順序分配算法節(jié)省了約30.31%的時間。隨機(jī)分配策略每一次執(zhí)行結(jié)果都會有所不同，但都會比MMPS算法和貪心策略算法執(zhí)行時間長。

全部任務(wù)執(zhí)行時間分布圖1所示，MMPS算法的0號任務(wù)與其他幾種算法時間大致相同，1號任務(wù)花費(fèi)的時間比其他的任務(wù)都多，2號任務(wù)少于順序分配策略，從3號任務(wù)開始，執(zhí)行時間都少于或者接近其他幾種調(diào)度算法，該文的MMPS調(diào)度算法在執(zhí)行時間上比其他三種算法更高效。endprint

2.3 算法時間復(fù)雜度分析

設(shè)系統(tǒng)中共有m臺虛擬機(jī)和n個任務(wù)，小堆排序的時間復(fù)雜度為O（nlogn）；VM歸一化的時間復(fù)雜度為O（m）；VM計算任務(wù)負(fù)載量的時間復(fù)雜度為O（mn）；任務(wù)計算代價的時間復(fù)雜度為O（mn）。

資源匹配過程最好情況是任務(wù)一次就匹配成功，時間復(fù)雜度為 O（1）；最壞情況下每個任務(wù)都需要匹配m次，n個任務(wù)共需要匹配m×n次，時間復(fù)雜度為O（mn）。因此，整個資源匹配過程最好情況下時間復(fù)雜度為O（l），最壞情況下時間復(fù)雜度為O（mn）。

3 結(jié)束語

云計算系統(tǒng)是一個特殊的超大規(guī)模集群系統(tǒng)，資源調(diào)度策略和負(fù)載均衡策略可作為影響云計算系統(tǒng)性能的重要因素之一。該文研究了云計算環(huán)境下基于QoS簡單約束的資源調(diào)度策略，借鑒作業(yè)調(diào)度的基本思想，建立資源調(diào)度模型。再根據(jù)物理資源與QoS參數(shù)的映射關(guān)系，建立云計算環(huán)境下的資源分配模型，深入研究了云計算仿真平臺CloudSim體系結(jié)構(gòu)，對CloudSim中基礎(chǔ)類：ExtendedExample2類和DatacenterBorker類等進(jìn)行相應(yīng)的擴(kuò)展，重新對源代碼進(jìn)行編譯，在CloudSim平臺上實(shí)現(xiàn)了MMPS算法的仿真，實(shí)驗結(jié)果表明MMPS算法效果較為顯著，能較好地滿足用戶服務(wù)質(zhì)量。

參考文獻(xiàn)：

[1] 劉鵬.云計算 [J].2版.北京：電子工業(yè)出版社，2011.

[2] 陳全，鄧倩妮.云計算及其關(guān)鍵技術(shù)[J].計算機(jī)應(yīng)用，2009，29（9）：2562-2567.

[3] 秦勇，肖文俊，黃翰，等.一種基于QoS度量的Pareto并行路由尋優(yōu)方法[J].計算機(jī)學(xué)報，2009，32（3）：463-472.

[4] 羅作民，張景，李軍懷，等.網(wǎng)格計算及其關(guān)鍵技術(shù)綜述[J].計算機(jī)工程與應(yīng)用，2004，39（30）：18-22.

[5] 宋杰，李甜甜，閆振興，等.一種云計算環(huán)境下的能效模型和度量方法[J].軟件學(xué)報， 2012，23（2）：200-214.

[6] 雷炳翰，何軍，何翔，等.基于QoS的網(wǎng)格負(fù)載調(diào)度算法[J].計算機(jī)工程，2009，35（24）：96-98.

[7] 宴婧.云環(huán)境下基于QoS約束的工作流任務(wù)調(diào)度算法研究與實(shí)現(xiàn)[D].重慶：重慶大學(xué)，2011.endprint

2.3 算法時間復(fù)雜度分析

設(shè)系統(tǒng)中共有m臺虛擬機(jī)和n個任務(wù)，小堆排序的時間復(fù)雜度為O（nlogn）；VM歸一化的時間復(fù)雜度為O（m）；VM計算任務(wù)負(fù)載量的時間復(fù)雜度為O（mn）；任務(wù)計算代價的時間復(fù)雜度為O（mn）。

資源匹配過程最好情況是任務(wù)一次就匹配成功，時間復(fù)雜度為 O（1）；最壞情況下每個任務(wù)都需要匹配m次，n個任務(wù)共需要匹配m×n次，時間復(fù)雜度為O（mn）。因此，整個資源匹配過程最好情況下時間復(fù)雜度為O（l），最壞情況下時間復(fù)雜度為O（mn）。

3 結(jié)束語

云計算系統(tǒng)是一個特殊的超大規(guī)模集群系統(tǒng)，資源調(diào)度策略和負(fù)載均衡策略可作為影響云計算系統(tǒng)性能的重要因素之一。該文研究了云計算環(huán)境下基于QoS簡單約束的資源調(diào)度策略，借鑒作業(yè)調(diào)度的基本思想，建立資源調(diào)度模型。再根據(jù)物理資源與QoS參數(shù)的映射關(guān)系，建立云計算環(huán)境下的資源分配模型，深入研究了云計算仿真平臺CloudSim體系結(jié)構(gòu)，對CloudSim中基礎(chǔ)類：ExtendedExample2類和DatacenterBorker類等進(jìn)行相應(yīng)的擴(kuò)展，重新對源代碼進(jìn)行編譯，在CloudSim平臺上實(shí)現(xiàn)了MMPS算法的仿真，實(shí)驗結(jié)果表明MMPS算法效果較為顯著，能較好地滿足用戶服務(wù)質(zhì)量。

參考文獻(xiàn)：

[1] 劉鵬.云計算 [J].2版.北京：電子工業(yè)出版社，2011.

[2] 陳全，鄧倩妮.云計算及其關(guān)鍵技術(shù)[J].計算機(jī)應(yīng)用，2009，29（9）：2562-2567.

[3] 秦勇，肖文俊，黃翰，等.一種基于QoS度量的Pareto并行路由尋優(yōu)方法[J].計算機(jī)學(xué)報，2009，32（3）：463-472.

[4] 羅作民，張景，李軍懷，等.網(wǎng)格計算及其關(guān)鍵技術(shù)綜述[J].計算機(jī)工程與應(yīng)用，2004，39（30）：18-22.

[5] 宋杰，李甜甜，閆振興，等.一種云計算環(huán)境下的能效模型和度量方法[J].軟件學(xué)報， 2012，23（2）：200-214.

[6] 雷炳翰，何軍，何翔，等.基于QoS的網(wǎng)格負(fù)載調(diào)度算法[J].計算機(jī)工程，2009，35（24）：96-98.

[7] 宴婧.云環(huán)境下基于QoS約束的工作流任務(wù)調(diào)度算法研究與實(shí)現(xiàn)[D].重慶：重慶大學(xué)，2011.endprint

2.3 算法時間復(fù)雜度分析

設(shè)系統(tǒng)中共有m臺虛擬機(jī)和n個任務(wù)，小堆排序的時間復(fù)雜度為O（nlogn）；VM歸一化的時間復(fù)雜度為O（m）；VM計算任務(wù)負(fù)載量的時間復(fù)雜度為O（mn）；任務(wù)計算代價的時間復(fù)雜度為O（mn）。

資源匹配過程最好情況是任務(wù)一次就匹配成功，時間復(fù)雜度為 O（1）；最壞情況下每個任務(wù)都需要匹配m次，n個任務(wù)共需要匹配m×n次，時間復(fù)雜度為O（mn）。因此，整個資源匹配過程最好情況下時間復(fù)雜度為O（l），最壞情況下時間復(fù)雜度為O（mn）。

3 結(jié)束語

云計算系統(tǒng)是一個特殊的超大規(guī)模集群系統(tǒng)，資源調(diào)度策略和負(fù)載均衡策略可作為影響云計算系統(tǒng)性能的重要因素之一。該文研究了云計算環(huán)境下基于QoS簡單約束的資源調(diào)度策略，借鑒作業(yè)調(diào)度的基本思想，建立資源調(diào)度模型。再根據(jù)物理資源與QoS參數(shù)的映射關(guān)系，建立云計算環(huán)境下的資源分配模型，深入研究了云計算仿真平臺CloudSim體系結(jié)構(gòu)，對CloudSim中基礎(chǔ)類：ExtendedExample2類和DatacenterBorker類等進(jìn)行相應(yīng)的擴(kuò)展，重新對源代碼進(jìn)行編譯，在CloudSim平臺上實(shí)現(xiàn)了MMPS算法的仿真，實(shí)驗結(jié)果表明MMPS算法效果較為顯著，能較好地滿足用戶服務(wù)質(zhì)量。

參考文獻(xiàn)：

[1] 劉鵬.云計算 [J].2版.北京：電子工業(yè)出版社，2011.

[2] 陳全，鄧倩妮.云計算及其關(guān)鍵技術(shù)[J].計算機(jī)應(yīng)用，2009，29（9）：2562-2567.

[3] 秦勇，肖文俊，黃翰，等.一種基于QoS度量的Pareto并行路由尋優(yōu)方法[J].計算機(jī)學(xué)報，2009，32（3）：463-472.

[4] 羅作民，張景，李軍懷，等.網(wǎng)格計算及其關(guān)鍵技術(shù)綜述[J].計算機(jī)工程與應(yīng)用，2004，39（30）：18-22.

[5] 宋杰，李甜甜，閆振興，等.一種云計算環(huán)境下的能效模型和度量方法[J].軟件學(xué)報， 2012，23（2）：200-214.

[6] 雷炳翰，何軍，何翔，等.基于QoS的網(wǎng)格負(fù)載調(diào)度算法[J].計算機(jī)工程，2009，35（24）：96-98.

[7] 宴婧.云環(huán)境下基于QoS約束的工作流任務(wù)調(diào)度算法研究與實(shí)現(xiàn)[D].重慶：重慶大學(xué)，2011.endprint