基于QoS的云任務(wù)調(diào)度算法研究

房超　黃春梅

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

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

中圖分類號：TP391? ? ?文獻(xiàn)標(biāo)識碼：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)建成了一個可以處理各種服務(wù)請求的云數(shù)據(jù)中心，當(dāng)用戶提交服務(wù)請求時，這些請求首先會被數(shù)據(jù)中心代理所接收，然后代理會根據(jù)一些資源調(diào)度算法將請求分發(fā)至數(shù)據(jù)中心的每一臺虛擬機中執(zhí)行。通常，用戶的服務(wù)請求會被解析成各類云任務(wù)（以下簡稱任務(wù)），用戶服務(wù)請求的處理過程相當(dāng)于為任務(wù)選擇合適的虛擬機的過程，數(shù)據(jù)中心需要制定合適的任務(wù)調(diào)度算法來處理各種任務(wù)。

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

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

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

關(guān)于獨立任務(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算法等，這些算法一般比較簡單且執(zhí)行速度較快。FIFO算法通常與輪轉(zhuǎn)調(diào)度算法相結(jié)合（FIFO（RR）算法）以實現(xiàn)任務(wù)的合理調(diào)度，通過先進(jìn)先出的方式從提交的任務(wù)隊列中選擇任務(wù)，然后按照輪轉(zhuǎn)的方式將任務(wù)分配到每一臺虛擬機中，雖然該算法有一定的負(fù)載均衡性，但它卻忽略了任務(wù)和虛擬機的異構(gòu)特性，并不適合現(xiàn)在的云計算異構(gòu)環(huán)境;MinMin算法屬于批調(diào)度算法，同時它也是一種實現(xiàn)簡單，執(zhí)行時間快的算法，該算法的思想是最先映射任務(wù)長度小的任務(wù)，并且映射到計算最快的虛擬機上，但這種算法容易導(dǎo)致負(fù)載大多集中在能力較強的資源節(jié)點上，使得資源負(fù)載極度不均衡;MaxMin算法與MinMin算法類似，首先都需要計算每一任務(wù)在所有計算節(jié)點上的最早完成時間，不同的是，MaxMin算法優(yōu)先調(diào)度大任務(wù)，任務(wù)到資源的映射是選擇最早完成時間最大的任務(wù)映射到所對應(yīng)的計算節(jié)點上，但會增加任務(wù)的平均完成時間。一些啟發(fā)式的任務(wù)調(diào)度算法，如：粒子群算法（PSO）[4]、蟻群算法（ACO）[5]、遺傳算法GA（Genetic Algorithm）和博弈論算法等[6，7]。這些啟發(fā)式調(diào)度算法雖然在某些方面比傳統(tǒng)任務(wù)調(diào)度算法具有更好的性能[8]，但算法實現(xiàn)起來較復(fù)雜，且實用性不強，有時在某些方面反而不如改進(jìn)的傳統(tǒng)任務(wù)調(diào)度算法更加簡單、有效。因此，這里不做過多闡述，只對一些改進(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需求來進(jìn)行改進(jìn)的，比如，何曉珊等[9]基于QoS修改了MinMin調(diào)度算法，根據(jù)用戶QoS需求對系統(tǒng)吞吐率進(jìn)行優(yōu)化，獲得了一定的性能改進(jìn)。孫大為等[10]根據(jù)用戶應(yīng)用偏好對QoS中的用戶效用進(jìn)行量化，并結(jié)合免疫克隆算法，給出了多維QoS優(yōu)化的適應(yīng)度函數(shù)，改進(jìn)了算法的收斂能力，提高了算法的性能;在增加云服務(wù)商收益方面。Buyya等[11]人提出基于經(jīng)濟(jì)模型資源調(diào)度方法，通過SLA（Service Leveal Aggent）資源分配器來實現(xiàn)資源提供者與資源使用者之間的協(xié)商，實現(xiàn)資源的優(yōu)化分配。Deelman等[12]利用亞馬孫收費標(biāo)準(zhǔn)和一個真實的天文學(xué)應(yīng)用，仿真實驗了不同執(zhí)行方法和資源提供方案下的性價比。Assuncao等[13]人研究了企業(yè)組織利用云服務(wù)提供商基礎(chǔ)設(shè)施擴展企業(yè)本地基礎(chǔ)設(shè)施的收益問題。Deepak等[14]人提出了對于云緩存查詢服務(wù)的一個新穎定價需求方案設(shè)計，實現(xiàn)利潤的最大化。Hamid等[15]人提出一種多QoS利潤感知調(diào)度算法（MQ-PAS），該算法通過考慮每個作業(yè)的可用預(yù)算來定義任務(wù)優(yōu)先級，從而提高供應(yīng)商的利潤。在將用戶服務(wù)滿意度和云服務(wù)商收益相結(jié)合方面，一種比較成熟的解決方案是面向云計算的工作流，簡稱“云工作流”，在這方面，柴學(xué)智等人[16]對云工作流的產(chǎn)生、發(fā)展，以及在云計算中的獨特優(yōu)勢進(jìn)行了詳細(xì)的闡述。武麗芬等[17]人提出滿足截止時間和預(yù)算的雙QoS約束調(diào)度算法（DBWS），該算法將工作流調(diào)度劃分為任務(wù)選擇和資源選擇兩個階段，并設(shè)計了時間質(zhì)量和代價質(zhì)量兩個均衡因素，同類算法在調(diào)度成功率與同步滿足QoS約束上進(jìn)行了比較。方伯芃等[18]人從用戶的QoS和云服務(wù)商的運營成本雙方利益出發(fā)，建立了一個面向QoS與成本感知的云工作流調(diào)度模型，并提出了一種基于任務(wù)序列劃分的兩段式編碼遺傳算法，該算法以租戶流程租約和虛擬機實例負(fù)載為約束，通過兩段式交叉、編譯算子進(jìn)行種群的迭代進(jìn)化，以實現(xiàn)對云工作流服務(wù)費用與云資源使用成本的調(diào)度優(yōu)化。

3? ?問題模型（Problem models）

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

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

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

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

4? ?算法與實驗（Algorithms and experiments）

本文通過在三種傳統(tǒng)任務(wù)調(diào)度算法中嵌入QoS需求約束來對其進(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算法。下面開始對三種改進(jìn)版?zhèn)鹘y(tǒng)任務(wù)調(diào)度算法進(jìn)行說明與實驗。

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

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

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

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

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

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

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

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

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

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

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

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

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

（6）開始模擬;

（7）停止模擬;

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

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

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

在對實驗結(jié)果進(jìn)行分析時，本文選取了影響用戶服務(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ù)最終完成時間（MakeSpan）

（b）Task final completion time

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

（c）Average rask execution time

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

（d）Cloud service provider's total profit

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

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