房超　黃春梅

摘? 要：隨著云計(jì)算的發(fā)展，越來(lái)越多的人開(kāi)始使用“云”來(lái)處理他們的業(yè)務(wù)，這對(duì)公有云平臺(tái)提出了一些重要挑戰(zhàn)：如何讓公有云平臺(tái)在不斷激增的云業(yè)務(wù)模式下，既能保證云用戶的服務(wù)滿意度，同時(shí)也能穩(wěn)步提高云服務(wù)商（Cloud Service Providers）的收益。首先建立了任務(wù)調(diào)度算法以及QoS需求約束等相關(guān)模型，然后將QoS（Quality of Service）需求約束分別引入到三種傳統(tǒng)任務(wù)調(diào)度算法（FCFS（RR）、MinMin和MaxMin算法）中對(duì)其進(jìn)行改進(jìn)，接著將改進(jìn)后的算法與傳統(tǒng)任務(wù)調(diào)度算法之間進(jìn)行比較，通過(guò)選取在任務(wù)完成度、任務(wù)最終完成時(shí)間（MakeSpan）、任務(wù)平均執(zhí)行時(shí)間（這些影響用戶的服務(wù)滿意度），以及云服務(wù)商總收益等方面的指標(biāo)表現(xiàn)，最后確定了一個(gè)較好的改進(jìn)MinMin任務(wù)調(diào)度算法（I-MinMin算法）。實(shí)驗(yàn)通過(guò)CloudSim進(jìn)行模擬，并采用了現(xiàn)有的阿里云ECS云服務(wù)器中的虛擬機(jī)實(shí)例相關(guān)數(shù)據(jù)。結(jié)果表明：在任務(wù)量不斷增加的情況下，I-MinMin算法在用戶的服務(wù)滿意度各方面，以及云服務(wù)商總收益等指標(biāo)表現(xiàn)上要更優(yōu)于其他算法，更好地實(shí)現(xiàn)了用戶和云服務(wù)商的雙重利益。

關(guān)鍵詞：云計(jì)算;任務(wù)調(diào)度算法;QoS需求;用戶服務(wù)滿意度;云服務(wù)商總收益

中圖分類號(hào)：TP391? ? ?文獻(xiàn)標(biāo)識(shí)碼：A

Abstract：With the development of cloud computing，more and more people begin to use "cloud" to manage their business，which poses some important challenges for public cloud platforms.For example，how to make public cloud platforms，under the ever-growing cloud business model，to ensure the service satisfaction of cloud users and steady improvement of the revenue of cloud service providers （Cloud Service Providers）.Relevant models such as task scheduling algorithms and QoS requirement constraints were established first.Then the QoS （Quality of Service） requirement constraints were introduced into three traditional task scheduling algorithms （FCFS （RR），MinMin，and MaxMin algorithms） for improvement.Then this paper compares the improved algorithm with traditional task scheduling algorithm.The three improved algorithms are compared with the original algorithms in terms of task completion，task final completion time （MakeSpan），average task execution time （these affect user service satisfaction），and the total revenue of cloud service providers' performance.Lastly，a better improved MinMin task scheduling algorithm （I-MinMin algorithm） was determined.The experiment was simulated by CloudSim，and the relevant data of the virtual machine instance in the existing Alibaba Cloud ECS cloud server was used.The results show that the I-MinMin algorithm outperforms other algorithms in terms of user service satisfaction and the total revenue of cloud service providers in the context of increasing tasks，therefore better achieve the dual interest of both users and cloud service providers.

Keywords：cloud computing;task scheduling algorithm;QoS demand;user service satisfaction;total profits of??cloud service providers

1? ?引言（Introduction）

在公有云中，云服務(wù)商利用內(nèi)部IT資源池構(gòu)建成了一個(gè)可以處理各種服務(wù)請(qǐng)求的云數(shù)據(jù)中心，當(dāng)用戶提交服務(wù)請(qǐng)求時(shí)，這些請(qǐng)求首先會(huì)被數(shù)據(jù)中心代理所接收，然后代理會(huì)根據(jù)一些資源調(diào)度算法將請(qǐng)求分發(fā)至數(shù)據(jù)中心的每一臺(tái)虛擬機(jī)中執(zhí)行。通常，用戶的服務(wù)請(qǐng)求會(huì)被解析成各類云任務(wù)（以下簡(jiǎn)稱任務(wù)），用戶服務(wù)請(qǐng)求的處理過(guò)程相當(dāng)于為任務(wù)選擇合適的虛擬機(jī)的過(guò)程，數(shù)據(jù)中心需要制定合適的任務(wù)調(diào)度算法來(lái)處理各種任務(wù)。

一般，任務(wù)調(diào)度算法需要考慮到每一個(gè)任務(wù)的各項(xiàng)QoS需求[1]，以及每一臺(tái)虛擬機(jī)的資源使用情況，以此來(lái)制定合理的任務(wù)調(diào)度算法，實(shí)現(xiàn)任務(wù)的合理分配以及資源的高效利用。當(dāng)任務(wù)數(shù)較少時(shí)，數(shù)據(jù)中心的資源量足夠滿足任務(wù)的各項(xiàng)QoS需求（比如用戶的價(jià)格需求等），因此，使用一些傳統(tǒng)任務(wù)調(diào)度算法即可實(shí)現(xiàn)這些目標(biāo);但當(dāng)任務(wù)數(shù)不斷增加時(shí)，如果繼續(xù)使用原來(lái)的任務(wù)調(diào)度算法，將有可能導(dǎo)致任務(wù)延遲，數(shù)據(jù)中心資源利用率降低等問(wèn)題，最終使得一些任務(wù)調(diào)度不能滿足他們自身的QoS需求，用戶的服務(wù)滿意度大大降低，同時(shí)也使得云服務(wù)商獲取不到用戶所支付的報(bào)酬。長(zhǎng)此以往，云服務(wù)商將不能獲得足夠的收益以支撐整個(gè)云數(shù)據(jù)中心的持續(xù)運(yùn)行。因此，設(shè)計(jì)一個(gè)可以應(yīng)對(duì)任務(wù)請(qǐng)求不斷增加情況下的高效任務(wù)調(diào)度算法，對(duì)于提高用戶的服務(wù)滿意度以及增加云服務(wù)商的收益至關(guān)重要。

2? ?相關(guān)工作（Related work）

在云計(jì)算中，任務(wù)可以分為獨(dú)立任務(wù)、關(guān)聯(lián)任務(wù)和混合任務(wù)，本文研究的主要是獨(dú)立任務(wù)的調(diào)度算法，因此，只對(duì)獨(dú)立任務(wù)的調(diào)度算法做相關(guān)介紹。

關(guān)于獨(dú)立任務(wù)調(diào)度算法，可以將其分為傳統(tǒng)任務(wù)調(diào)度算法和啟發(fā)式的任務(wù)調(diào)度算法。一些傳統(tǒng)的任務(wù)調(diào)度算法，例如先進(jìn)先出（FIFO）算法[2]、輪轉(zhuǎn)調(diào)度（RR）算法、MinMin算法[3]、MaxMin算法和Sufferage算法等，這些算法一般比較簡(jiǎn)單且執(zhí)行速度較快。FIFO算法通常與輪轉(zhuǎn)調(diào)度算法相結(jié)合（FIFO（RR）算法）以實(shí)現(xiàn)任務(wù)的合理調(diào)度，通過(guò)先進(jìn)先出的方式從提交的任務(wù)隊(duì)列中選擇任務(wù)，然后按照輪轉(zhuǎn)的方式將任務(wù)分配到每一臺(tái)虛擬機(jī)中，雖然該算法有一定的負(fù)載均衡性，但它卻忽略了任務(wù)和虛擬機(jī)的異構(gòu)特性，并不適合現(xiàn)在的云計(jì)算異構(gòu)環(huán)境;MinMin算法屬于批調(diào)度算法，同時(shí)它也是一種實(shí)現(xiàn)簡(jiǎn)單，執(zhí)行時(shí)間快的算法，該算法的思想是最先映射任務(wù)長(zhǎng)度小的任務(wù)，并且映射到計(jì)算最快的虛擬機(jī)上，但這種算法容易導(dǎo)致負(fù)載大多集中在能力較強(qiáng)的資源節(jié)點(diǎn)上，使得資源負(fù)載極度不均衡;MaxMin算法與MinMin算法類似，首先都需要計(jì)算每一任務(wù)在所有計(jì)算節(jié)點(diǎn)上的最早完成時(shí)間，不同的是，MaxMin算法優(yōu)先調(diào)度大任務(wù)，任務(wù)到資源的映射是選擇最早完成時(shí)間最大的任務(wù)映射到所對(duì)應(yīng)的計(jì)算節(jié)點(diǎn)上，但會(huì)增加任務(wù)的平均完成時(shí)間。一些啟發(fā)式的任務(wù)調(diào)度算法，如：粒子群算法（PSO）[4]、蟻群算法（ACO）[5]、遺傳算法GA（Genetic Algorithm）和博弈論算法等[6，7]。這些啟發(fā)式調(diào)度算法雖然在某些方面比傳統(tǒng)任務(wù)調(diào)度算法具有更好的性能[8]，但算法實(shí)現(xiàn)起來(lái)較復(fù)雜，且實(shí)用性不強(qiáng)，有時(shí)在某些方面反而不如改進(jìn)的傳統(tǒng)任務(wù)調(diào)度算法更加簡(jiǎn)單、有效。因此，這里不做過(guò)多闡述，只對(duì)一些改進(jìn)的傳統(tǒng)任務(wù)調(diào)度算法作相關(guān)介紹。

關(guān)于改進(jìn)的傳統(tǒng)任務(wù)調(diào)度算法，本文主要從用戶服務(wù)滿意度以及云服務(wù)商收益這兩方面進(jìn)行介紹。在用戶服務(wù)滿意度方面，大多數(shù)學(xué)者都是基于QoS需求來(lái)進(jìn)行改進(jìn)的，比如，何曉珊等[9]基于QoS修改了MinMin調(diào)度算法，根據(jù)用戶QoS需求對(duì)系統(tǒng)吞吐率進(jìn)行優(yōu)化，獲得了一定的性能改進(jìn)。孫大為等[10]根據(jù)用戶應(yīng)用偏好對(duì)QoS中的用戶效用進(jìn)行量化，并結(jié)合免疫克隆算法，給出了多維QoS優(yōu)化的適應(yīng)度函數(shù)，改進(jìn)了算法的收斂能力，提高了算法的性能;在增加云服務(wù)商收益方面。Buyya等[11]人提出基于經(jīng)濟(jì)模型資源調(diào)度方法，通過(guò)SLA（Service Leveal Aggent）資源分配器來(lái)實(shí)現(xiàn)資源提供者與資源使用者之間的協(xié)商，實(shí)現(xiàn)資源的優(yōu)化分配。Deelman等[12]利用亞馬孫收費(fèi)標(biāo)準(zhǔn)和一個(gè)真實(shí)的天文學(xué)應(yīng)用，仿真實(shí)驗(yàn)了不同執(zhí)行方法和資源提供方案下的性價(jià)比。Assuncao等[13]人研究了企業(yè)組織利用云服務(wù)提供商基礎(chǔ)設(shè)施擴(kuò)展企業(yè)本地基礎(chǔ)設(shè)施的收益問(wèn)題。Deepak等[14]人提出了對(duì)于云緩存查詢服務(wù)的一個(gè)新穎定價(jià)需求方案設(shè)計(jì)，實(shí)現(xiàn)利潤(rùn)的最大化。Hamid等[15]人提出一種多QoS利潤(rùn)感知調(diào)度算法（MQ-PAS），該算法通過(guò)考慮每個(gè)作業(yè)的可用預(yù)算來(lái)定義任務(wù)優(yōu)先級(jí)，從而提高供應(yīng)商的利潤(rùn)。在將用戶服務(wù)滿意度和云服務(wù)商收益相結(jié)合方面，一種比較成熟的解決方案是面向云計(jì)算的工作流，簡(jiǎn)稱“云工作流”，在這方面，柴學(xué)智等人[16]對(duì)云工作流的產(chǎn)生、發(fā)展，以及在云計(jì)算中的獨(dú)特優(yōu)勢(shì)進(jìn)行了詳細(xì)的闡述。武麗芬等[17]人提出滿足截止時(shí)間和預(yù)算的雙QoS約束調(diào)度算法（DBWS），該算法將工作流調(diào)度劃分為任務(wù)選擇和資源選擇兩個(gè)階段，并設(shè)計(jì)了時(shí)間質(zhì)量和代價(jià)質(zhì)量?jī)蓚€(gè)均衡因素，同類算法在調(diào)度成功率與同步滿足QoS約束上進(jìn)行了比較。方伯芃等[18]人從用戶的QoS和云服務(wù)商的運(yùn)營(yíng)成本雙方利益出發(fā)，建立了一個(gè)面向QoS與成本感知的云工作流調(diào)度模型，并提出了一種基于任務(wù)序列劃分的兩段式編碼遺傳算法，該算法以租戶流程租約和虛擬機(jī)實(shí)例負(fù)載為約束，通過(guò)兩段式交叉、編譯算子進(jìn)行種群的迭代進(jìn)化，以實(shí)現(xiàn)對(duì)云工作流服務(wù)費(fèi)用與云資源使用成本的調(diào)度優(yōu)化。

3? ?問(wèn)題模型（Problem models）

為便于分析，本文規(guī)定每臺(tái)虛擬機(jī)每次只能執(zhí)行一個(gè)任務(wù)，多臺(tái)虛擬機(jī)可以同時(shí)執(zhí)行，且任務(wù)一旦被執(zhí)行將不能被搶占，直到任務(wù)執(zhí)行完成，虛擬機(jī)才可執(zhí)行下一個(gè)任務(wù)。本文首先建立了云任務(wù)、虛擬機(jī)以及主機(jī)等基本模型（或公式）;然后建立了調(diào)度算法相關(guān)模型（或公式）;最后是調(diào)度目標(biāo)模型（或公式）。此外，本文模型中所用到的變量i、j和k分別表示任務(wù)標(biāo)號(hào)、虛擬機(jī)標(biāo)號(hào)和主機(jī)標(biāo)號(hào)，它們均滿足0≤i≤m-1、0≤j≤n-1及0≤k≤s，其中m、n和s分別表示任務(wù)總數(shù)、虛擬機(jī)總數(shù)和主機(jī)總數(shù)，由于模型（或公式）較多，本文以列表的形式展示，如表1—表3所示。

QoSconst表示QoS需求約束，包括虛擬機(jī)vj執(zhí)行任務(wù)ti所產(chǎn)生的預(yù)計(jì)執(zhí)行收益不能超過(guò)該任務(wù)的最高可接受價(jià)格，以及任務(wù)ti在虛擬機(jī)vj上的預(yù)計(jì)完成時(shí)間不能超過(guò)該任務(wù)的截止時(shí)間 （16）

所有任務(wù)在執(zhí)行完成后，未違反QoS需求約束（QoSconst）的任務(wù)將會(huì)產(chǎn)生云服務(wù)商收益，因此，記錄這些未違約任務(wù)的數(shù)量可以很好地反應(yīng)出云服務(wù)商總收益的變化。

為了提高用戶的服務(wù)滿意度，算法應(yīng)該在任務(wù)量不斷增加的過(guò)程中，始終保持較高的任務(wù)完成度TCR（Task Completion Rate）、較低的任務(wù)最終完成時(shí)間（MakeSpan）以及任務(wù)平均執(zhí)行時(shí)間ATET（Average Task Execution Time）;服務(wù)商方面，主要選擇的是保持云服務(wù)商的總收益Profitcsp持續(xù)增加，另外，TDR（Task Default Rate）用于分析算法的QoS違約率變化。

4? ?算法與實(shí)驗(yàn)（Algorithms and experiments）

本文通過(guò)在三種傳統(tǒng)任務(wù)調(diào)度算法中嵌入QoS需求約束來(lái)對(duì)其進(jìn)行改進(jìn)，目的是為了尋找一種具有較好的用戶服務(wù)滿意度，以及云服務(wù)商總收益的改進(jìn)算法。三種傳統(tǒng)任務(wù)調(diào)度算法分別是FCFS（RR）算法、MinMin算法及MaxMin算法，改進(jìn)后的算法分別稱為I-FCFS（RR）算法、I-MinMin算法及I-MaxMin算法。下面開(kāi)始對(duì)三種改進(jìn)版?zhèn)鹘y(tǒng)任務(wù)調(diào)度算法進(jìn)行說(shuō)明與實(shí)驗(yàn)。

4.1? ?對(duì)傳統(tǒng)任務(wù)調(diào)度算法的改進(jìn)

本文對(duì)傳統(tǒng)任務(wù)調(diào)度算法不做過(guò)多介紹，只對(duì)改進(jìn)版的傳統(tǒng)任務(wù)調(diào)度算法進(jìn)行相關(guān)分析，它們都是通過(guò)在原有算法中嵌入QoS需求約束進(jìn)行的，如表4—表6所示。

上述三種改進(jìn)版?zhèn)鹘y(tǒng)任務(wù)調(diào)度算法在為任務(wù)選擇合適的虛擬機(jī)過(guò)程中，每一步都要經(jīng)過(guò)QoS需求的層層約束。在滿足QoS需求約束的情況下，任務(wù)會(huì)被放置到合適的虛擬機(jī)中;在不滿足QoS需求約束的情況下，任務(wù)會(huì)被取消。

4.2? ?實(shí)驗(yàn)相關(guān)參數(shù)

本文試驗(yàn)采用CloudSim進(jìn)行模擬，總共創(chuàng)建了五臺(tái)主機(jī)、20臺(tái)虛擬機(jī)。虛擬機(jī)的屬性數(shù)據(jù)采用的是阿里云服務(wù)器ECS中真實(shí)實(shí)例的數(shù)據(jù)。另外，本文將0—3600個(gè)任務(wù)以300個(gè)為單位平均分成了12組，作為不同任務(wù)量的任務(wù)集。實(shí)驗(yàn)過(guò)程中的相關(guān)參數(shù)如表7所示。

表7中虛擬機(jī)的數(shù)據(jù)采用的是阿里云云服務(wù)器ECS中共享型實(shí)例的標(biāo)準(zhǔn)數(shù)據(jù)。在阿里云服務(wù)器ECS定價(jià)界面中選擇華東2地域，實(shí)例價(jià)格信息選擇入門(mén)級(jí)用戶、經(jīng)典網(wǎng)絡(luò)、非Windows系統(tǒng)，以及優(yōu)化的I/O即可找到這些虛擬機(jī)實(shí)例的相關(guān)數(shù)據(jù)信息，如圖1所示。

依照阿里云幫助文檔中關(guān)于云服務(wù)器ECS的共享型實(shí)例說(shuō)明，本文共選取了ecs.xn4.small、ecs.n4.small、ecs.xn4.large、ecs.mn4.small及ecs.mn4.large四種不同類型的實(shí)例（虛擬機(jī)），這些實(shí)例使用的都是2.5GHz主頻的Intel?Xeon?E5-2682 v4（Broadwell）處理器，帶寬都為0.5Gbit/s（512Mb/s），由此可以得到這些實(shí)例在正常情況下的Cpu最高主頻為2.5GHz。因此本文假設(shè)這五種不同類型虛擬機(jī)的主頻分別擁有0.5GHz、1GHz、1.5GHz、2GHz和2.5GHz這五種主頻，且所有Cpu的每個(gè)機(jī)器周期都等于四個(gè)時(shí)鐘周期，每條指令等于三個(gè)機(jī)器周期，則該Cpu的時(shí)鐘周期數(shù)（每條指令執(zhí)行的時(shí)鐘周期個(gè)數(shù)）為3*4=12個(gè)，最終由公式：Cpu的運(yùn)算能力=主頻/時(shí)鐘周期數(shù)，可以得到了表7中五種類型虛擬機(jī)的Cpu運(yùn)算能力。

本文將0—3600個(gè)任務(wù)按照每300個(gè)為遞增的順序來(lái)模擬不斷增加的云任務(wù)集，總共分成12份;將任務(wù)的長(zhǎng)度（指令數(shù)）以10000百萬(wàn)為單位平均分成了10份;將截止時(shí)間以1小時(shí)為單位平均分成了10份;將最高可接受價(jià)格以0.01元為單位平均分成了10份。使用CloudSim進(jìn)行模擬的過(guò)程大體如下：

（1）初始化CloudSim，創(chuàng)建CloudinformationSerVice服務(wù);

（2）創(chuàng)建數(shù)據(jù)中心（包含創(chuàng)建主機(jī)的過(guò)程）;

（3）創(chuàng)建數(shù)據(jù)中心代理;

（4）創(chuàng)建虛擬機(jī)，并提交給數(shù)據(jù)中心代理;

（5）創(chuàng)建任務(wù)，并提交到數(shù)據(jù)中心代理;

（6）開(kāi)始模擬;

（7）停止模擬;

（8）輸出模擬結(jié)果。

下面將對(duì)實(shí)驗(yàn)的結(jié)果進(jìn)行分析。

4.3? ?改進(jìn)版?zhèn)鹘y(tǒng)任務(wù)調(diào)度算法實(shí)驗(yàn)結(jié)果與分析

在對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行分析時(shí)，本文選取了影響用戶服務(wù)滿意度和云服務(wù)商收益的四種指標(biāo)，以及QoS違約率、未違約任務(wù)數(shù)等，并使用折線圖的方式比較了六種任務(wù)調(diào)度算法在12種不同任務(wù)集中的表現(xiàn)及變化，如圖2、圖3和圖4所示。

（a）任務(wù)完成度（TCR）

（a）Task completion rate

（b）任務(wù)最終完成時(shí)間（MakeSpan）

（b）Task final completion time

（c）任務(wù)平均執(zhí)行時(shí)間（ATET）

（c）Average rask execution time

（d）云服務(wù)商總收益（Profitcsp）

（d）Cloud service provider's total profit

算法的QoS違約率和未違約任務(wù)數(shù)統(tǒng)計(jì)如圖3和圖4所示。

從以上各圖可以看出：在任務(wù)量不斷增加的過(guò)程中，三種傳統(tǒng)任務(wù)調(diào)度算法（FCFS（RR）、MinMin和MaxMin算法）始終保持100%的任務(wù)完成度。這是由于傳統(tǒng)任務(wù)調(diào)度算法在任務(wù)調(diào)度時(shí)，沒(méi)有考慮到用戶提交的任務(wù)中所要求的各項(xiàng)QoS需求，只是籠統(tǒng)的將任務(wù)全部分配到虛擬機(jī)當(dāng)中。因此，這種方法雖然可以將所有任務(wù)都執(zhí)行完成，但卻造成了大量任務(wù)違約，從圖3中也可以看出它們的QoS違約率基本處于增加的狀態(tài)，用戶將不會(huì)為這些違約的任務(wù)支付任何費(fèi)用，這種情況會(huì)在任務(wù)不斷增多的情況下愈發(fā)明顯。除FCFS（RR）算法外，MinMin和MaxMin算法的任務(wù)最終完成時(shí)間（MakeSpan）一直處于穩(wěn)步上升的趨勢(shì)，但又由于任務(wù)的最終完成數(shù)也是一直增加的，故任務(wù)平均完成時(shí)間取決于他們各自的增加幅度。而這三種算法的服務(wù)商總收益前期一直處于上升的趨勢(shì)，后期則趨于平穩(wěn)。這是由于此時(shí)的數(shù)據(jù)中心已經(jīng)達(dá)到了任務(wù)處理的“飽和”上限，系統(tǒng)已經(jīng)無(wú)法處理更多的任務(wù)，從圖2（b）中也可看出此點(diǎn)。而隨著可以處理的任務(wù)達(dá)到頂峰，服務(wù)商總收益也將獲得最高值（圖4中未違約任務(wù)趨于平衡）。相對(duì)于傳統(tǒng)任務(wù)調(diào)度算法，三種改進(jìn)的任務(wù)調(diào)度算法（I-FCFS（RR）、I-MinMin和I-MaxMin算法）由于考慮了用戶的QoS需求，即對(duì)任務(wù)進(jìn)行了篩選，避免了用戶QoS需求違約（如圖3它們的QoS違約率始終為0），因此它們的任務(wù)完成度取決于任務(wù)的最終完成數(shù)與所有提交的任務(wù)數(shù)比值，從圖2（a）可以看出它們的任務(wù)完成度一直處于下降的趨勢(shì)。在前一小段，他們的任務(wù)最終完成時(shí)間（MakeSpan）處于小步上升的狀態(tài)，云服務(wù)商的總收益不斷增加（從圖4中可以看出），后期大半段，它們依舊會(huì)出現(xiàn)“飽和”的現(xiàn)象，其任務(wù)最終完成時(shí)間與云服務(wù)商總收益基本保持平衡狀態(tài)。