蘇命峰，王國軍，李仁發(fā)

（1. 中南大學(xué)計(jì)算機(jī)學(xué)院, 湖南 長(zhǎng)沙 410083；2. 廣州大學(xué)計(jì)算機(jī)科學(xué)與網(wǎng)絡(luò)工程學(xué)院，廣東 廣州510006；3. 湖南大學(xué)信息科學(xué)與工程學(xué)院，湖南 長(zhǎng)沙 410082）

1 引言

新形勢(shì)下，人工智能、大數(shù)據(jù)、物聯(lián)網(wǎng)的發(fā)展如火如荼，云計(jì)算的應(yīng)用越加廣泛，對(duì)云計(jì)算提供海量、高效運(yùn)算能力的要求越來超高。云計(jì)算環(huán)境復(fù)雜多變，存在節(jié)點(diǎn)異構(gòu)、數(shù)量巨大、易于失效、云資源需求動(dòng)態(tài)變化、存在不確定性等特點(diǎn)，如何高效利用云計(jì)算資源，充分滿足云用戶（CU, cloud user）的云計(jì)算服務(wù)需求，同時(shí)考慮云計(jì)算服務(wù)提供商（CSP, cloud service provider）利益，需要加強(qiáng)云資源管理，優(yōu)化云任務(wù)（CT, cloud task）調(diào)度，這成為云計(jì)算迫切需要解決的問題。

云計(jì)算資源調(diào)度問題是 NP完全問題[1]，為解決這一最具挑戰(zhàn)的問題，將大規(guī)模、動(dòng)態(tài)、不確定的用戶應(yīng)用，以云任務(wù)形式調(diào)度至物理位置分隔、資源異構(gòu)、多重約束的云資源環(huán)境中，實(shí)現(xiàn)云資源的最大效用。為提升云用戶和云資源提供商的服務(wù)與被服務(wù)質(zhì)量，同時(shí)需要對(duì)多個(gè)目標(biāo)函數(shù)進(jìn)行優(yōu)化，比如云用戶主要關(guān)注云任務(wù)執(zhí)行時(shí)間和系統(tǒng)可用性等，云計(jì)算服務(wù)提供商主要考慮云系統(tǒng)的能耗、經(jīng)濟(jì)性、可靠性等。

云計(jì)算資源調(diào)度多關(guān)注單目標(biāo)優(yōu)化，文獻(xiàn)[2]關(guān)注云任務(wù)執(zhí)行時(shí)間，面向多用戶云計(jì)算服務(wù)提出2DFQ（two-dimensional fail queuing）方法，基于長(zhǎng)、短云任務(wù)隊(duì)列區(qū)別對(duì)待，解決Azure平臺(tái)高并發(fā)訪問下的猝發(fā)性調(diào)度問題。文獻(xiàn)[3]關(guān)注云任務(wù)最終完成時(shí)間，在多資源云集群權(quán)衡公平、性能、效率，提出了altruistic調(diào)度，優(yōu)先long-term云任務(wù)暫時(shí)讓出部分short-term云任務(wù)的分配資源以取得更高效率和更低任務(wù)完成時(shí)間。文獻(xiàn)[4]關(guān)注云任務(wù)響應(yīng)時(shí)間，提出max-min-cloud云任務(wù)調(diào)度算法優(yōu)化云工作量分配，在多租戶異構(gòu)虛擬機(jī)的云環(huán)境實(shí)現(xiàn)高效云資源供給。云系統(tǒng)能耗也是研究熱點(diǎn)，文獻(xiàn)[5]關(guān)注云數(shù)據(jù)中心能耗，針對(duì)提出的sliding-scheduled方案，預(yù)測(cè)云任務(wù)資源需求，設(shè)計(jì)了快速自適應(yīng)啟發(fā)式虛擬機(jī)配置方案，實(shí)現(xiàn)了最大化云資源處理量和最小化能源消耗。文獻(xiàn)[6]關(guān)注云系統(tǒng)能耗，提出了具有machine啟動(dòng)時(shí)間感知的虛擬機(jī)擴(kuò)展策略，設(shè)計(jì)了實(shí)時(shí)任務(wù)調(diào)度算法以保障任務(wù)完成時(shí)間和節(jié)能。文獻(xiàn)[7]關(guān)注系統(tǒng)可用性，提出了一種容錯(cuò)流調(diào)度、應(yīng)用增量聚類算法進(jìn)行云任務(wù)流的快速自動(dòng)識(shí)別與高效調(diào)度。文獻(xiàn)[8]關(guān)注云計(jì)算負(fù)載均衡，在云計(jì)算中采用隨機(jī)算法進(jìn)行虛擬機(jī)調(diào)度，試圖解決組合優(yōu)化knapsack問題。此外，文獻(xiàn)[9-10]關(guān)注網(wǎng)絡(luò)虛擬性能優(yōu)化，分別提出了用戶空間的 NF（network function）調(diào)度服務(wù)鏈管理架構(gòu)和非負(fù)矩陣分解方法，為網(wǎng)絡(luò)虛擬化平臺(tái)提供公平、高效、動(dòng)態(tài)的資源調(diào)度。文獻(xiàn)[11]關(guān)注云計(jì)算安全，提出了云計(jì)算環(huán)境下基于后驗(yàn)概率的隱蔽信道檢測(cè)方法。

云計(jì)算資源調(diào)度的多目標(biāo)優(yōu)化，文獻(xiàn)[12]關(guān)注負(fù)載均衡和性能，提出了高效流調(diào)度解決方案，采用D-CLAS（discretized coflow-aware least-attained service）方法將任務(wù)流分為少量?jī)?yōu)先級(jí)隊(duì)列。文獻(xiàn)[13]提出了一種快速自適應(yīng)啟發(fā)式虛擬機(jī)配置的sliding-scheduled方案，預(yù)測(cè)云任務(wù)資源需求，分配可變化的云資源供給窗口，實(shí)現(xiàn)最大化云資源處理量和最小化能源消耗。文獻(xiàn)[14]關(guān)注云計(jì)算系統(tǒng)能耗和性能，在異構(gòu)云環(huán)境調(diào)度中提出了一種memetic優(yōu)化方法。文獻(xiàn)[15]關(guān)注云任務(wù)完工時(shí)間和經(jīng)濟(jì)成本，設(shè)計(jì)了一種連續(xù)合作博弈的 MOG（muliti-objective game）調(diào)度算法，并保證云資源效率和公平度。文獻(xiàn)[16]關(guān)注CPS（cyber-physical system）任務(wù)的響應(yīng)時(shí)間和可靠性，基于遺傳算法求解多目標(biāo)線性規(guī)劃資源模型最優(yōu)解。

云計(jì)算資源調(diào)度可以分為虛擬資源調(diào)度和物理資源調(diào)度，文獻(xiàn)[17-21]關(guān)注云數(shù)據(jù)中心的任務(wù)指派、任務(wù)回滾、云工作流部署等虛擬資源調(diào)度問題。文獻(xiàn)[22-26]關(guān)注云計(jì)算環(huán)境中虛擬機(jī)的調(diào)度、合并、放置等物理資源調(diào)度問題。

以上研究較多關(guān)注單個(gè)目標(biāo)優(yōu)化，多目標(biāo)優(yōu)化主要從用戶或者云計(jì)算資源提供商的單一視角考慮云計(jì)算虛擬或物理資源調(diào)度，缺少基于虛擬和物理資源調(diào)度，同時(shí)從云用戶和云計(jì)算資源提供者的利益相關(guān)角度，綜合考慮多個(gè)目標(biāo)統(tǒng)籌優(yōu)化；較多關(guān)注云資源靜態(tài)調(diào)度，缺少云資源動(dòng)態(tài)自適應(yīng)調(diào)度。

基于以上分析，本文研究大規(guī)模高并發(fā)多任務(wù)異構(gòu)云環(huán)境下基于利益相關(guān)視角的多維 QoS（quality of service）云資源調(diào)度，主要貢獻(xiàn)如下。

1) 提出了MQoS（multidimensional quality of service cloud resource scheduling algorithm）云資源調(diào)度算法，綜合考慮 minimumL、maximumS、maximumR，基于虛擬和物理資源調(diào)度進(jìn)行云計(jì)算任務(wù)的合理分配與資源調(diào)度，在具備無后效性的 4種云應(yīng)用場(chǎng)景取得較高多維QoS度。

2) 提出了多維 QoS云計(jì)算體系結(jié)構(gòu)，基于云用戶和云服務(wù)提供商的利益相關(guān)視角，綜合量化云任務(wù)執(zhí)行時(shí)間、云任務(wù)最終完成時(shí)間、云系統(tǒng)能耗、云系統(tǒng)可用性、云系統(tǒng)經(jīng)濟(jì)5個(gè)指標(biāo)，取得云計(jì)算系統(tǒng)最大效用。

3) 設(shè)計(jì)了高任務(wù)差高資源差、高任務(wù)差低資源差、低任務(wù)差高資源差、低資源差低任務(wù)差4種云計(jì)算應(yīng)用場(chǎng)景，系統(tǒng)評(píng)估MQoS、FIFO（first in, first out cloud resource scheduling algorithm）、M2EC（multi-metric energy consumption virtual machines scheduling algorithm）3種調(diào)度算法的多維QoS度和云數(shù)據(jù)中心負(fù)載均衡差。

2 系統(tǒng)模型與體系結(jié)構(gòu)

2.1 云資源二級(jí)調(diào)度模型

云計(jì)算具有超大規(guī)模、資源虛化、按需服務(wù)、高可靠性、高可擴(kuò)展等特點(diǎn)。云計(jì)算將計(jì)算、存儲(chǔ)、網(wǎng)絡(luò)等硬件資源加入資源池，利用虛擬化技術(shù)，為CU提供若干虛擬機(jī)（VM, virtual machine），接收用戶請(qǐng)求的云任務(wù)，將任務(wù)執(zhí)行完畢并返回結(jié)果。云計(jì)算的資源分為物理資源和虛擬資源，其中，物理資源即物理機(jī)（PM, physical machine），包括計(jì)算、存儲(chǔ)、網(wǎng)絡(luò)等硬件設(shè)備；虛擬資源指利用虛擬化技術(shù)得到的虛擬機(jī)，以云服務(wù)器、云存儲(chǔ)、云數(shù)據(jù)庫等呈現(xiàn)給 CU。云計(jì)算的資源調(diào)度可以分為虛擬資源調(diào)度和物理資源調(diào)度，如圖1所示。虛擬資源調(diào)度為一級(jí)調(diào)度，將CU提交的任務(wù)，根據(jù)用戶需求，運(yùn)用合適的策略調(diào)度至滿足要求的VM上執(zhí)行；物理資源調(diào)度為二級(jí)調(diào)度，根據(jù)VM的性能要求和PM的可用資源等信息，將VM映射至合適的PM上運(yùn)行。通過這兩級(jí)調(diào)度，需要盡可能滿足CU需求，兼顧C(jī)SP利益，實(shí)現(xiàn)云計(jì)算最大效應(yīng)。本文所用符號(hào)及其含義如表1所示。

圖1 云資源二級(jí)調(diào)度模型

表1 主要符號(hào)及其含義

2.2 多維QoS云計(jì)算體系結(jié)構(gòu)

為了實(shí)現(xiàn)高效云資源調(diào)度，基于CU和CSP的利益相關(guān)視角，面向虛擬和物理資源調(diào)度提出多維QoS云計(jì)算體系結(jié)構(gòu)，如圖2所示，分為4層，從下往上依次為硬件資源層、多維QoS層、虛擬資源層和云用戶層。

圖2 多維QoS云計(jì)算體系結(jié)構(gòu)

硬件資源層：由n個(gè)位于不同地理位置的云數(shù)據(jù)中心（CDC, cloud data center）組成，每個(gè)CDC擁有數(shù)量、性能不同、同構(gòu)或異構(gòu)的物理服務(wù)器、網(wǎng)絡(luò)設(shè)備、存儲(chǔ)設(shè)備等硬件。CDC將這些冗余的硬件設(shè)備加入云資源池，通過虛擬化技術(shù)，可以同時(shí)運(yùn)行性能配置不同、操作系統(tǒng)各異的多個(gè)VM。

多維QoS層：面向CU和CSP協(xié)調(diào)和實(shí)現(xiàn)多維QoS服務(wù)目標(biāo)，通過云計(jì)算的VMM/Hypervisor資源調(diào)度，優(yōu)化管理、實(shí)時(shí)監(jiān)控，取得最少的云任務(wù)執(zhí)行時(shí)間、云任務(wù)最終完成時(shí)間和云系統(tǒng)能耗，獲得最大的云系統(tǒng)可用性、云系統(tǒng)經(jīng)濟(jì)，充分滿足CU和CSP的利益。

虛擬資源層：CDC根據(jù)CU需要，創(chuàng)建若干擁有不同配置、不同操作系統(tǒng)的VM，可以快速、靈活地實(shí)現(xiàn) VM 的創(chuàng)建、遷移、掛起、停機(jī)等操作。每個(gè)VM可以為多個(gè)CU服務(wù)，但在同一時(shí)間只能執(zhí)行一個(gè)CU提交的云任務(wù)。遇到高并發(fā)訪問請(qǐng)求時(shí)，可以實(shí)時(shí)增開多個(gè)VM并行工作；當(dāng)任務(wù)空閑時(shí)，可以關(guān)閉多余的VM，以實(shí)現(xiàn)可擴(kuò)展、彈性計(jì)算服務(wù)。

云用戶層：用戶接入Internet，可以在任何地點(diǎn)、任何時(shí)間，以任何方式訪問CU申請(qǐng)的VM，提交云服務(wù)請(qǐng)求，就像訪問本地物理服務(wù)器一樣，給CU提供同樣，甚至更好、便捷的服務(wù)體驗(yàn)。

3 問題建模與量化

3.1 云資源調(diào)度建模

多維QoS云資源調(diào)度，基于CU和CSP的利益相關(guān)視角，從多個(gè)維度合理調(diào)度CU資源請(qǐng)求，優(yōu)化虛擬和物理資源調(diào)度實(shí)現(xiàn)云計(jì)算系統(tǒng)的最大效用，包括提高CU的云計(jì)算體驗(yàn)度，實(shí)現(xiàn)最小完成時(shí)間；提高CSP的效益，實(shí)現(xiàn)系統(tǒng)的高可用和高能效。

定義1多維QoS云計(jì)算。QoS在網(wǎng)絡(luò)中定義為服務(wù)質(zhì)量，用來解決網(wǎng)絡(luò)時(shí)延和擁塞，為用戶提供更好的網(wǎng)絡(luò)通信服務(wù)。在云計(jì)算中，QoS指CSP為CU提供按需定制、按需付費(fèi)的云服務(wù)質(zhì)量。多維QoS云計(jì)算定義為基于CU和CSP的利益相關(guān)視角，從 CET（cloud task execution time）、CFT（cloud task final completion time）、CEC（cloud system energy consumption）、CA（cloud system availability）、CE（cloud system economy）5個(gè)維度，進(jìn)行云計(jì)算任務(wù)的合理分配與資源調(diào)度，對(duì)云計(jì)算環(huán)境的用戶體驗(yàn)、系統(tǒng)能耗、系統(tǒng)經(jīng)濟(jì)、可用性等進(jìn)行客觀評(píng)價(jià)，量化為多維QoS度性能指標(biāo)，以充分滿足CU和CSP的利益。

定義2多維QoS云資源調(diào)度模型。該模型是一個(gè)五元組模型，其中，由n個(gè)CU組成的用戶集合，每個(gè)用戶提交的CT相互獨(dú)立，互不干擾，云任務(wù)請(qǐng)求總體呈Poisson分布；，由Cn個(gè)地理位置獨(dú)立、互不影響的CDC組成的云數(shù)據(jù)中心集合，其中，第i個(gè)云數(shù)據(jù)中心，其中，是第i個(gè)云數(shù)據(jù)中心的第j臺(tái)物理機(jī)；Q是一個(gè)多維QoS等級(jí)，其量化值為多維QoS度Qs；O是在多維QoS云計(jì)算環(huán)境中定義的目標(biāo)函數(shù)，具體如式(1)所示，通過CET、CFT、CEC、CA、CE這5個(gè)難度進(jìn)行具體量化；Θ為實(shí)現(xiàn)多維QoS云資源調(diào)度的優(yōu)化算法。

以云任務(wù)執(zhí)行時(shí)間為例，云任務(wù)集在虛擬資源集中的虛擬機(jī)上執(zhí)行的時(shí)間，可以構(gòu)成云任務(wù)執(zhí)行時(shí)間關(guān)系矩陣A，具體如式(3)所示，其中，CETij為云任務(wù)CTj在虛擬機(jī)vmi上的執(zhí)行時(shí)間。

3.2 多維QoS性能指標(biāo)量化

在多維QoS云計(jì)算環(huán)境中，主要選取云任務(wù)執(zhí)行時(shí)間CET、云任務(wù)最終完成時(shí)間CFT、云系統(tǒng)能耗CEC、云系統(tǒng)可用性CA和云系統(tǒng)經(jīng)濟(jì)CE，進(jìn)行具體性能指標(biāo)量化。

3.2.1 云任務(wù)執(zhí)行時(shí)間

一個(gè)CU提交的CTj在第k個(gè)CDC的第i個(gè)虛擬機(jī)上執(zhí)行，其執(zhí)行時(shí)間CETijk包括虛擬機(jī)啟動(dòng)時(shí)間云任務(wù)運(yùn)行時(shí)間和虛擬機(jī)關(guān)機(jī)時(shí)間，如式(4)所示。

對(duì)于同一類型的虛擬機(jī)vmi，其和是一個(gè)固定常量。主要取決于云任務(wù)長(zhǎng)度L和虛擬機(jī)的平均服務(wù)速率S[14]。

定義3云任務(wù)執(zhí)行時(shí)間CET。在時(shí)間段T內(nèi)，不考慮云任務(wù)排隊(duì)等因素，在多維QoS云計(jì)算環(huán)境中所有虛擬機(jī)直接執(zhí)行 CU提交云任務(wù)的時(shí)間總和。一個(gè)CSP由n個(gè)CDC組成，每個(gè)CDC通過虛擬化技術(shù)擁有若干個(gè)VM，其中第k個(gè)數(shù)據(jù)中心擁有mk個(gè)VM，每個(gè)VM可以運(yùn)行若干云任務(wù)，其中，第j個(gè) VM 上運(yùn)行nj個(gè)云任務(wù)。云任務(wù)執(zhí)行時(shí)間CET如式(5)所示。

3.2.2 云任務(wù)最終完成時(shí)間

CTj在第k個(gè)CDC的第i個(gè)VM上執(zhí)行，其云任務(wù)最終完成時(shí)間CFTijk為其云任務(wù)等待時(shí)間（CWT, cloud task wait time）與其云任務(wù)執(zhí)行時(shí)間CETijk之和，如式(6)所示。任務(wù)等待時(shí)間，如式(7)所示，其中，為分配到虛擬機(jī)vmi的CTj執(zhí)行前vmi需要處理的云任務(wù)數(shù)量。

云任務(wù)的CWT取決于其虛擬機(jī)上運(yùn)行的云任務(wù)數(shù)量和每個(gè)云任務(wù)的執(zhí)行情況。在大規(guī)模高并發(fā)多任務(wù)云計(jì)算環(huán)境下，云任務(wù)隊(duì)列的云任務(wù)數(shù)量越多，云任務(wù)的執(zhí)行處理時(shí)間越長(zhǎng)，云任務(wù)的排隊(duì)等待時(shí)間越長(zhǎng)。第k個(gè)CDC的第i個(gè)VM上執(zhí)行的云

結(jié)合式(6)，可以得出在第k個(gè)CDC的第i個(gè)VM上執(zhí)行的CTj，其云任務(wù)最終完成時(shí)間為

定義4云任務(wù)最終完成時(shí)間CFT。在時(shí)間段T內(nèi)，在多維QoS云計(jì)算環(huán)境中將所有云任務(wù)提交給虛擬機(jī)，經(jīng)過任務(wù)排隊(duì)等因素，最終得到執(zhí)行所需要的時(shí)間總和，主要關(guān)注多維QoS云計(jì)算的用戶體驗(yàn)。云計(jì)算環(huán)境由n個(gè)CDC組成，每個(gè)CDC通過虛擬化技術(shù)擁有若干VM，其中，第k個(gè)數(shù)據(jù)中心擁有mk個(gè)VM，每個(gè)VM可以運(yùn)行若干云任務(wù)，其中第j個(gè)VM上運(yùn)行nj個(gè)云任務(wù)。其最終完成時(shí)間CFT如式(8)所示。

3.2.3 云系統(tǒng)能耗

第k個(gè)CDC的第l個(gè)物理機(jī)pmkl的云系統(tǒng)能耗CECkl，可以通過物理機(jī)pmkl在時(shí)間段T=[T0-Tn-1]內(nèi)的能耗PCpmkl(χ(t))累加得到，如式(9)所示。

基本能耗可以理解為物理機(jī)的待機(jī)能耗，一般來說，同一種類型的物理機(jī)的基本能耗是一個(gè)固定常量。動(dòng)態(tài)能耗為物理機(jī)提供云服務(wù)時(shí)所需要消耗的電能，根據(jù)提供云服務(wù)的不同而不同，云服務(wù)類型包括CPU密集型、數(shù)據(jù)密集型、I/O密集型等。物理機(jī)的能耗由 CPU、RAM、存儲(chǔ)等設(shè)備的能耗組成。由于 CPU是最主要的電能消耗設(shè)備，為了簡(jiǎn)化問題，物理機(jī)的待機(jī)能耗和動(dòng)態(tài)能耗可以通過CPU的電能消耗來計(jì)算[27]，如式(11)所示。

定義5云系統(tǒng)能耗CEC。在多維QoS云計(jì)算環(huán)境中全部數(shù)據(jù)中心的所有物理機(jī)在單位時(shí)間內(nèi)的能量消耗之和。云計(jì)算環(huán)境由n個(gè)CDC組成，其中第k個(gè)CDC擁有個(gè)物理機(jī)，整個(gè)云計(jì)算系統(tǒng)在時(shí)間段T內(nèi)的云系統(tǒng)能耗CEC，如式(12)所示。

結(jié)合式(9)～式(12)，可以得出云系統(tǒng)能耗CEC為

3.2.4 云系統(tǒng)可用性

第k個(gè)CDC的第m個(gè)虛擬機(jī)vmkm的云系統(tǒng)可用性CAkm，可以通過計(jì)算虛擬機(jī)vmkm在時(shí)間段T內(nèi)的系統(tǒng)正常運(yùn)行的概率或時(shí)間占用率得到，如式(13)所示。

定義6云系統(tǒng)可用性CA。為在多維QoS云計(jì)算環(huán)境中所有虛擬機(jī)正常提供云服務(wù)的平均概率。云計(jì)算環(huán)境由n個(gè)CDC組成，其中第k個(gè)CDC擁有個(gè)虛擬機(jī)，那么，整個(gè)云計(jì)算環(huán)境在時(shí)間段T內(nèi)的云系統(tǒng)可用性CA，如式(14)所示。

結(jié)合式(13)和式(14)，可以得到云系統(tǒng)可用性CA為

3.2.5 云系統(tǒng)經(jīng)濟(jì)

第k個(gè)CDC的第l個(gè)物理機(jī)pmkl的云系統(tǒng)經(jīng)濟(jì)CEkl，可以通過物理機(jī)pmkl在時(shí)間段T內(nèi)的云計(jì)算收益（CCR, cloud computing revenue）與經(jīng)濟(jì)成本（EC, economic cost）計(jì)算得出，如式(15)所示。

其中，HSCpmkl(T)為第k個(gè)CDC的第l個(gè)物理機(jī)pmkl在時(shí)間段T的硬件軟件成本，包括硬件采購和軟件成本；SOMCpmkl(T)為第k個(gè)CDC的第l個(gè)物理機(jī)pmkl在時(shí)間段T的系統(tǒng)運(yùn)維成本，包括服務(wù)器能耗、制冷能耗、系統(tǒng)管理等成本。

定義7云系統(tǒng)經(jīng)濟(jì)CE。在多維QoS云計(jì)算環(huán)境中所有物理機(jī)在單位時(shí)間內(nèi)的平均經(jīng)濟(jì)效益。一個(gè)云計(jì)算環(huán)境由n個(gè)CDC組成，其中第k個(gè)CDC擁有個(gè)物理機(jī)，那么，整個(gè)云計(jì)算環(huán)境在時(shí)間段T內(nèi)的云系統(tǒng)經(jīng)濟(jì)CE如式(17)所示。

結(jié)合式(15)～式(17)，可以得出云系統(tǒng)經(jīng)濟(jì)CE為

3.3 多維QoS度量

3.3.1 數(shù)據(jù)的歸一化

多維QoS云計(jì)算的Qs可以通過CET、CFT、CEC、CA、CE這5個(gè)維度量化得出。這5個(gè)維度組成五維QoS指標(biāo)向量P=(CET-1, CFT-1, CEC-1,CA, CE)。對(duì)每個(gè)QoS指標(biāo)測(cè)量n次，那么五維QoS性能指標(biāo)向量P可以轉(zhuǎn)換為一個(gè)n行5列的矩陣An×5=(aij)n×5。不失一般性地，如果有m維QoS性能指標(biāo)，就可以得到一個(gè)n行m列的矩陣An×m=(aij)n×m，其中，aij是第j維性能指標(biāo)的第i次測(cè)量值。

多維QoS云計(jì)算的5個(gè)維度具有不同的量綱和單位，為了消除不同評(píng)價(jià)指標(biāo)的差異，實(shí)現(xiàn)不同量綱和單位的可對(duì)比性，需要對(duì)每個(gè)維度進(jìn)行數(shù)據(jù)標(biāo)準(zhǔn)化處理。首先，將矩陣An×m進(jìn)行z-score標(biāo)準(zhǔn)化處理，利用原始數(shù)據(jù)的均值和標(biāo)準(zhǔn)差，處理后的數(shù)據(jù)將符合標(biāo)準(zhǔn)正態(tài)分布，如式(18)所示。

3.3.2 數(shù)據(jù)的量化

多維 QoS量化需要為每個(gè)維度的性能指標(biāo)確定合適的權(quán)重。在多維 QoS云計(jì)算環(huán)境中，基于CU和CSP的利益相關(guān)視角，針對(duì)CET、CFT、CEC、CA和CE確定五維性能指標(biāo)的權(quán)重向量W=(wCET,其中，wj∈[0,1]是第j維的性能指標(biāo)權(quán)重，并且。將多維 QoS性能指標(biāo)矩陣與五維性能指標(biāo)權(quán)重向量WT進(jìn)行乘法計(jì)算，可以得到多維Qs度的組合QsT，如式(20)所示。

4 云資源調(diào)度算法

4.1 FIFO云資源調(diào)度算法

FIFO云資源調(diào)度算法[8]按照云任務(wù)提交的先后次序，將任務(wù)指派到虛擬機(jī)，然后將虛擬機(jī)按順序依次部署到有空閑資源的物理機(jī)上執(zhí)行。FIFO云資源調(diào)度算法是一種最簡(jiǎn)單、最基本的調(diào)度算法，沒有對(duì)云任務(wù)調(diào)度和虛擬機(jī)部署進(jìn)行任何優(yōu)化。FIFO云資源調(diào)度算法如算法1所示。

算法1FIFO云資源調(diào)度算法

輸入CU隊(duì)列Qcus，CT隊(duì)列Qcts，VM 隊(duì)列Qvms，PM隊(duì)列Qpms，CDC隊(duì)列Qdcs，五維性能指標(biāo)權(quán)重向量W=(wCET,wCFT,wCEC,wCA,wCE)

輸出多維QoS度Qs

FIFO云資源調(diào)度算法的輸出是多維 QoS度Qs。步驟 1)～步驟 4)接收 CU的請(qǐng)求，將其對(duì)應(yīng)的CT按先后次序進(jìn)行排列，并加入CT隊(duì)列Qcts。步驟5)～步驟7)將CDC中的虛擬機(jī)依次加入VM隊(duì)列Qvms。步驟 8)～步驟 17)將 CU請(qǐng)求的 CT按先后次序分配至VM，并部署到CDC的PM上依次運(yùn)行。步驟 18)根據(jù)式(5)、式(8)、式(12)、式(14)和式(17)，分別計(jì)算CET、CFT、CEC、CA和CE。步驟19)～步驟20)計(jì)算最終的多維QoS度，并返回Qs值。FIFO云資源調(diào)度算法的時(shí)間復(fù)雜度為O(1)。

4.2 MQoS云資源調(diào)度算法

MQoS云資源調(diào)度算法基于多重Greedy算法，綜合考慮最小云任務(wù)長(zhǎng)度（minimumL）、VM最大平均服務(wù)速率（maximumS）和PM最多剩余硬件資源（maximumR），面向虛擬和物理資源調(diào)度進(jìn)行云計(jì)算任務(wù)的合理分配與資源調(diào)度，從5個(gè)維度綜合量化云計(jì)算系統(tǒng)的多維 QoS度。在第 5節(jié)中，MQoS云資源調(diào)度算法在具有無后效性的4種應(yīng)用場(chǎng)景下，相比傳統(tǒng)方法具有明顯優(yōu)勢(shì)。MQoS云資源調(diào)度算法如算法2所示。

算法2MQoS云資源調(diào)度算法

輸入CU隊(duì)列Qcus，CT隊(duì)列Qcts，VM 隊(duì)列Qvms，PM隊(duì)列Qpms，CDC隊(duì)列Qdcs，五維性能指標(biāo)權(quán)重向量W=(wCET,wCFT,wCEC,wCA,wCE)

輸出多維QoS度Qs

MQoS云資源調(diào)度算法的輸出是多維 QoS度Qs，Qs值越大，云計(jì)算系統(tǒng)效用越大。步驟1)～步驟4)接收CU的請(qǐng)求，將其對(duì)應(yīng)的CT按云任務(wù)長(zhǎng)度大小進(jìn)行升序排列，并加入到 CT隊(duì)列Qcts。步驟5)～步驟7)將CDC中PM上的虛擬機(jī)按平均服務(wù)速率高低進(jìn)行降序排列，并加入VM隊(duì)列Qvms。步驟 8)～步驟 17)使用多重 Greedy 算法思想，將每個(gè)CU請(qǐng)求的云任務(wù)分配到VM上高效運(yùn)行，同時(shí)，將每一個(gè)VM部署到當(dāng)時(shí)擁有最多剩余硬件資源的PM上，以取得最大多維QoS效用。步驟 18)根據(jù)式(5)、式(8)、式(12)、式(14)和式(17)，分別計(jì)算 CET、CFT、CEC、CA和 CE。步驟19)～步驟 20)計(jì)算最終的多維 QoS度，并返回Qs值。MQoS云資源調(diào)度算法的時(shí)間復(fù)雜度為

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

本節(jié)搭建云計(jì)算實(shí)驗(yàn)環(huán)境，設(shè)置實(shí)驗(yàn)參數(shù)，設(shè)計(jì)無后效性的4種云計(jì)算應(yīng)用場(chǎng)景，分別在不同云任務(wù)數(shù)和不同虛擬機(jī)數(shù)的情況下，依次運(yùn)行MQoS、FIFO、M2EC這3種調(diào)度算法，評(píng)估它們?cè)谠瀑Y源調(diào)度中的多維QoS度和云數(shù)據(jù)中心負(fù)載均衡差，并進(jìn)行具體分析。在M2EC多維能耗虛擬機(jī)調(diào)度算法[27]中，云計(jì)算服務(wù)提供商將接收的云用戶服務(wù)請(qǐng)求指派到虛擬機(jī)，然后依次將虛擬機(jī)隊(duì)列按虛擬機(jī)性能從高到低排序，將服務(wù)器隊(duì)列按物理機(jī)性能從高到低排序，再基于改進(jìn)的首次適合下降（FFD，first fit decreasing algorithm）算法[28-30]將虛擬機(jī)優(yōu)化部署到合適的物理服務(wù)器上。M2EC多維能耗虛擬機(jī)調(diào)度算法的時(shí)間復(fù)雜度為O(nlbn)。

5.1 實(shí)驗(yàn)環(huán)境與設(shè)置

本文硬件實(shí)驗(yàn)平臺(tái)為一臺(tái)x86服務(wù)器，硬件配置為 Intel Xeon E5-2650v4 CPU，32 GB DDR4 RAM，1 TB SAS/SATA硬盤，1 Gbit/s以太網(wǎng)卡；操作系統(tǒng)為Windows Server 2012 R2。

軟件采用CloudSim 4.0云計(jì)算仿真平臺(tái)，該平臺(tái)是由澳大利亞墨爾本大學(xué)網(wǎng)格實(shí)驗(yàn)室推出的云計(jì)算仿真軟件。CloudSim 4.0繼承了GridSim的編程模型，是在離散事件模擬包SimJava上開發(fā)的基于Java的函數(shù)庫，擴(kuò)展實(shí)現(xiàn)了一系列接口，包括提供虛擬化引擎，實(shí)現(xiàn)基于大型云計(jì)算數(shù)據(jù)中心的虛擬化技術(shù)，以及虛擬化云的建模和仿真功能。本文應(yīng)用 CloudSim構(gòu)建云計(jì)算仿真環(huán)境，應(yīng)用于MQoS、FIFO、M2EC這3種調(diào)度算法，進(jìn)行云計(jì)算系統(tǒng)的性能測(cè)試與分析。

5.2 實(shí)驗(yàn)參數(shù)與設(shè)置

在實(shí)驗(yàn)過程中，借鑒亞馬遜公開的 AWS（Amazon Web service）云數(shù)據(jù)中心數(shù)據(jù)設(shè)置18個(gè)CDC，每個(gè)CDC根據(jù)規(guī)模的不同配備200～500臺(tái)PM（節(jié)點(diǎn)），如表1所示，每個(gè)節(jié)點(diǎn)擁有性能不等的CPU、RAM、網(wǎng)絡(luò)帶寬等。根據(jù)CU的不同需求，設(shè)計(jì)了通用型、計(jì)算型、內(nèi)存型、存儲(chǔ)型等4種類型的虛擬機(jī)(VM)模板，如表2所示。

表1 CDC配置參數(shù)

表2 虛擬機(jī)模板參數(shù)

為了充分評(píng)估 MQoS、FIFO和 M2EC這 3種調(diào)度算法在多維 QoS云計(jì)算環(huán)境下的系統(tǒng)性能，在實(shí)驗(yàn)中模擬高資源差高任務(wù)差（HR-HT,difference of high resource and high task）、高資源差低任務(wù)差（HR-LT, difference of high resource and low task）、低資源差高任務(wù)差（LR-HT, difference of low resource and high task）、低資源差低任務(wù)差（LR-LT, difference of low resource and low task）這4種無后效性的云計(jì)算應(yīng)用場(chǎng)景。其中，高任務(wù)差指云任務(wù)差達(dá)到[1, 500]，表示不同CU提交的不同云任務(wù)，其云任務(wù)長(zhǎng)度的數(shù)值差達(dá)到 1:500；低任務(wù)差指云任務(wù)差為[1, 10]，表示不同CU提交的不同云任務(wù)差別不大，其云任務(wù)長(zhǎng)度的數(shù)值差控制在 1:10以內(nèi)；高資源差指虛擬機(jī)的平均服務(wù)速率差達(dá)到[1,100]，表示不同的CU租用通用型、計(jì)算型、內(nèi)存型、存儲(chǔ)型等虛擬機(jī)，其不同虛擬機(jī)的平均服務(wù)速率數(shù)值差在100:1之間；低資源差指其虛擬機(jī)的平均服務(wù)速率差為[1,10]，表示不同的 CU租用通用型、計(jì)算型、內(nèi)存型、存儲(chǔ)型等虛擬機(jī)，其不同虛擬機(jī)的平均服務(wù)速率差值控制在 10:1以內(nèi)。具體如表3所示。

表3 4種云計(jì)算應(yīng)用場(chǎng)景設(shè)置

在實(shí)驗(yàn)中，模擬 4種應(yīng)用場(chǎng)景中，依次設(shè)置1×104～9×104個(gè) CU，分別產(chǎn)生 1×104～9×104個(gè)云任務(wù)，每個(gè)CU提交的云任務(wù)在時(shí)間維度服從Poisson分布。將云任務(wù)交給CDC，分別運(yùn)用MQoS、FIFO、M2EC這3種調(diào)度算法，進(jìn)行任務(wù)指派與調(diào)度資源，依次計(jì)算得到CET、CFT、CEC、CA、CE這5個(gè)QoS維度值，最終計(jì)算多維QoS度。為了提高測(cè)量的準(zhǔn)確度與穩(wěn)定性，每個(gè)應(yīng)用場(chǎng)景的每個(gè)測(cè)試點(diǎn)分別測(cè)試3次，取結(jié)果取平均值。實(shí)驗(yàn)的具體參數(shù)如表4所示。

表4 實(shí)驗(yàn)參數(shù)設(shè)置

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

通過多維QoS度、云數(shù)據(jù)中心負(fù)載均衡差這2個(gè)性能指標(biāo)對(duì)MQoS、FIFO、M2EC這3種調(diào)度算法進(jìn)行云資源調(diào)度的性能分析與評(píng)估。

5.3.1 多維QoS度

多維QoS度由CET、CFT、CEC、CA、CE這5個(gè)性能指標(biāo)與五維性能指標(biāo)權(quán)重向量WT進(jìn)行矩陣乘積計(jì)算得出。云計(jì)算系統(tǒng)的 Qs越大，意味著CU提交的云任務(wù)執(zhí)行時(shí)間越少，云任務(wù)最終完成時(shí)間越少，給CSP帶來的云系統(tǒng)能耗越低、產(chǎn)生的云系統(tǒng)經(jīng)濟(jì)越高，云系統(tǒng)可用性越高，讓CU的體驗(yàn)也越好，以實(shí)現(xiàn)云計(jì)算系統(tǒng)的最大效用，充分滿足CU和CSP的利益。

首先，設(shè)計(jì)HR-HT、HR-LT、LR-HT、LR-LT這4種具有無后效性的云計(jì)算應(yīng)用場(chǎng)景，分別在不同CU規(guī)模下，評(píng)測(cè)MQoS、FIFO、M2EC這3種調(diào)度算法的多維QoS度。MQoS云資源調(diào)度算法基于CU和CSP的利益相關(guān)視角，綜合考慮最小云任務(wù)長(zhǎng)度、最大VM平均服務(wù)速率和最多PM剩余硬件資源等因素合理調(diào)度虛擬和物理資源，從多個(gè)維度量化云資源使用，優(yōu)化云任務(wù)執(zhí)行時(shí)間、云任務(wù)最終完成時(shí)間，降低云系統(tǒng)能耗、提高云系統(tǒng)經(jīng)濟(jì)、可用性等，在4個(gè)應(yīng)用場(chǎng)景中均可以保持比較高的多維QoS度，Qs值大于0.7。FIFO云資源調(diào)度算法根據(jù)CU提交的先后順序，進(jìn)行最簡(jiǎn)單、基本的調(diào)度，沒有進(jìn)行任何優(yōu)化，在測(cè)試時(shí)其多維QoS度低，Qs值小于0.36。M2EC多維能耗虛擬機(jī)調(diào)度算法改進(jìn)了FFD算法，分別對(duì)虛擬機(jī)隊(duì)列和物理機(jī)隊(duì)列進(jìn)行性能的降序排列，對(duì)物理資源的調(diào)度進(jìn)行優(yōu)化，其Qs值在[0.29, 0.80]區(qū)間，相比FIFO云資源調(diào)度算法有提高；但沒有將云任務(wù)指派到虛擬資源進(jìn)行優(yōu)化，相比MQoS云資源調(diào)度算法，其云任務(wù)等待時(shí)間偏高，導(dǎo)致CFT偏高，進(jìn)而影響多維QoS度，降低了 Qs值，在云用戶增加多的情況下，其Qs值下降明顯。從圖3可以看出，MQoS云資源調(diào)度算法的Qs值，比其他調(diào)度算法都要高，位于[0.70,0.91]區(qū)間，遠(yuǎn)遠(yuǎn)高出FIFO云資源調(diào)度算法，總體提升228.99%，和M2EC多維能耗虛擬機(jī)調(diào)度算法相比，總體提升56.93%。

其次，同樣在HR-HT、HR-LT、LR-HT、LR-LT等4種云計(jì)算應(yīng)用場(chǎng)景中，改變CDC的VM規(guī)模，進(jìn)一步評(píng)測(cè)MQoS、FIFO、M2EC這3種調(diào)度算法的多維QoS度。MQoS云資源調(diào)度算法考慮CU和CSP的利益，采用多重 Greedy算法，基于虛擬和物理資源調(diào)度綜合優(yōu)化云資源使用。和在不同云用戶規(guī)模的情況相似，MQoS云資源調(diào)度算法在不同VM規(guī)模情況下，都取得較高的多維QoS度，其Qs值相比其他調(diào)度算法都有明顯優(yōu)勢(shì)。沒有進(jìn)行優(yōu)化的FIFO云資源調(diào)度算法，其多維QoS度始終偏低。M2EC多維能耗虛擬機(jī)調(diào)度算法改進(jìn)了 FFD算法，對(duì)物理資源調(diào)度進(jìn)行優(yōu)化，其Qs值介于FIFO和MQoS之間。如圖4所示，MQoS云資源調(diào)度算法在4種應(yīng)用場(chǎng)景的多維QoS度，其Qs值在[0.66, 0.92]區(qū)間，遠(yuǎn)高于FIFO云資源調(diào)度算法的多維QoS度（Qs值在[0.20, 0.31]區(qū)間），整體提升206.42%；相比M2EC多維能耗虛擬機(jī)調(diào)度算法的多維QoS度（Qs值在[0.28, 0.82]區(qū)間），整體提升34.26%。

5.3.2 云數(shù)據(jù)中心負(fù)載均衡差

圖3 3種調(diào)度算法在4種場(chǎng)景下不同云用戶數(shù)的多維QoS度

圖4 3種調(diào)度算法在4種場(chǎng)景下不同虛擬機(jī)的多維QoS度

在CDC中，不同的虛擬機(jī)處理相同的CU處理請(qǐng)求，由于處理能力不同，其所承受的云計(jì)算負(fù)載程度不同。云資源分配，既要考慮CU的云任務(wù)執(zhí)行工作量，也要考慮虛擬機(jī)執(zhí)行云任務(wù)的處理能力。好的云資源調(diào)度必須考慮各數(shù)據(jù)中心每個(gè)節(jié)點(diǎn)上虛擬機(jī)的負(fù)載均衡情況。衡量云數(shù)據(jù)中心負(fù)載均衡好壞由云數(shù)據(jù)中心負(fù)載均衡差（LBD, cloud data center load balance difference）來度量。云數(shù)據(jù)中心負(fù)載均衡差越小，說明云計(jì)算環(huán)境中各數(shù)據(jù)中心的負(fù)載率越均衡，數(shù)據(jù)中心的相同虛擬機(jī)類型的負(fù)載值（即虛擬機(jī)上執(zhí)行的云任務(wù)工作量與其處理能力比值）越平衡，越能提高云計(jì)算系統(tǒng)的多維QoS度。

云數(shù)據(jù)中心負(fù)載均衡差LBD為各數(shù)據(jù)中心負(fù)載率的標(biāo)準(zhǔn)差，如式(22)所示，DCLk為數(shù)據(jù)中心k的負(fù)載率為CSP的n個(gè)CDC的平均數(shù)據(jù)中心負(fù)載率。

數(shù)據(jù)中心負(fù)載率DCLk，如式(23)所示，具體為云計(jì)算環(huán)境中第k個(gè)CDC，其執(zhí)行云任務(wù)的所有虛擬機(jī)的總計(jì)算能力與 CDC的所有物理機(jī)的總計(jì)算能力的比值，Cvmik為第k個(gè)CDC的第i臺(tái)虛擬機(jī)的計(jì)算能力，Cpmlk為第k個(gè)CDC的第l臺(tái)物理機(jī)的計(jì)算能力。

在實(shí)驗(yàn)中主要考慮大規(guī)模多任務(wù)高并發(fā)高資源差的云計(jì)算應(yīng)用場(chǎng)景。為了更好測(cè)試、比較，分2個(gè)測(cè)試環(huán)境，分別設(shè)置不同的CU規(guī)模和不同的VM規(guī)模，評(píng)估MQoS、FIFO、M2EC這3種調(diào)度算法的LBD。在不同CU規(guī)模下，如圖5所示，F(xiàn)IFO云資源調(diào)度算法沒有進(jìn)行算法調(diào)度優(yōu)化，其數(shù)據(jù)中心負(fù)載均衡差始終偏高，LBD數(shù)值在0.65以上。M2EC多維能耗虛擬機(jī)調(diào)度算法采用改進(jìn) FFD算法在負(fù)載均衡進(jìn)行一定的調(diào)整和完善，其數(shù)值在[0.32,0.59]區(qū)間。MQoS云資源調(diào)度算法面向 CU和 CSP，采用多重 Greedy算法同時(shí)優(yōu)化虛擬和物理資源調(diào)度，LBD處于一個(gè)比較低的水平，數(shù)值在 0.28以下，遠(yuǎn)優(yōu)于FIFO云資源調(diào)度算法，平均總體降低 0.48；相比 M2EC多維能耗虛擬機(jī)調(diào)度算法也有一定優(yōu)勢(shì)，平均總體降低0.20。

在不同VM規(guī)模下，如圖6所示，和在不同CU規(guī)模下相似，F(xiàn)IFO云資源調(diào)度算法的數(shù)據(jù)中心負(fù)載均衡差始終偏高，LBD數(shù)值在0.70以上。采用改進(jìn) FFD算法對(duì)負(fù)載均衡有一定優(yōu)化的M2EC多維能耗虛擬機(jī)調(diào)度算法，其數(shù)值在[0.41,0.67]區(qū)間。MQoS云資源調(diào)度算法從多個(gè)方面優(yōu)化物理和資源調(diào)度，其處于一個(gè)較低的水平，數(shù)值在0.32以下，與FIFO和M2EC調(diào)度算法相比較，平均總體降低 0.49和 0.27，均具有明顯優(yōu)勢(shì)。

圖5 不同云用戶規(guī)模，3種調(diào)度算法的LBD

圖6 不同虛擬機(jī)規(guī)模，3種調(diào)度算法的LBD

6 結(jié)束語

本文在大規(guī)模多任務(wù)高并發(fā)異構(gòu)云環(huán)境下，基于CU和CSP的利益相關(guān)視角，構(gòu)建多維QoS云計(jì)算體系結(jié)構(gòu)，建模多維 QoS云資源調(diào)度模型，基于多重Greedy算法思想設(shè)計(jì)MQoS云資源調(diào)度算法，并進(jìn)行云計(jì)算調(diào)度仿真實(shí)驗(yàn)與結(jié)果分析。實(shí)驗(yàn)結(jié)果表明在4種應(yīng)用場(chǎng)景下MQoS云資源調(diào)度算法的多維 QoS度均好于 FIFO和M2EC調(diào)度算法，特別在高任務(wù)云計(jì)算應(yīng)用場(chǎng)景優(yōu)勢(shì)明顯；同時(shí)在大規(guī)模多任務(wù)高并發(fā)高資源差的應(yīng)用場(chǎng)景中，分別在不同CU規(guī)模和不同虛擬機(jī)規(guī)模情況下，MQoS云資源調(diào)度算法的LBD均優(yōu)于FIFO和M2EC調(diào)度算法，取得很好的云計(jì)算系統(tǒng)效用，充分滿足CU和CSP的利益。在未來的研究中，將深入研究在大規(guī)模多用戶高并發(fā)異構(gòu)云計(jì)算環(huán)境中動(dòng)態(tài)調(diào)整五維性能指標(biāo)權(quán)重，并考慮更細(xì)粒度虛擬機(jī)等情況下的云資源調(diào)度策略與應(yīng)用。