彭紅姣　李安南　曹新欣

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

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

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

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

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

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

1.1 任務(wù)描述

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

1.2 資源描述

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

1.3 Qos參數(shù)選取

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

1.4 負(fù)載均衡策略

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 結(jié)束語

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

參考文獻(xiàn)：

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

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

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

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

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

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

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

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

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

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

3 結(jié)束語

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

參考文獻(xiàn)：

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

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

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

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

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

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

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

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

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

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

3 結(jié)束語

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

參考文獻(xiàn)：

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

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

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

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

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

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

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