基于QoS的云任務調度算法研究

房超　黃春梅

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

關鍵詞：云計算;任務調度算法;QoS需求;用戶服務滿意度;云服務商總收益

中圖分類號：TP391? ? ?文獻標識碼：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）

在公有云中，云服務商利用內部IT資源池構建成了一個可以處理各種服務請求的云數據中心，當用戶提交服務請求時，這些請求首先會被數據中心代理所接收，然后代理會根據一些資源調度算法將請求分發至數據中心的每一臺虛擬機中執行。通常，用戶的服務請求會被解析成各類云任務（以下簡稱任務），用戶服務請求的處理過程相當于為任務選擇合適的虛擬機的過程，數據中心需要制定合適的任務調度算法來處理各種任務。

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

2? ?相關工作（Related work）

在云計算中，任務可以分為獨立任務、關聯任務和混合任務，本文研究的主要是獨立任務的調度算法，因此，只對獨立任務的調度算法做相關介紹。

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

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

3? ?問題模型（Problem models）

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

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

所有任務在執行完成后，未違反QoS需求約束（QoSconst）的任務將會產生云服務商收益，因此，記錄這些未違約任務的數量可以很好地反應出云服務商總收益的變化。

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

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

本文通過在三種傳統任務調度算法中嵌入QoS需求約束來對其進行改進，目的是為了尋找一種具有較好的用戶服務滿意度，以及云服務商總收益的改進算法。三種傳統任務調度算法分別是FCFS（RR）算法、MinMin算法及MaxMin算法，改進后的算法分別稱為I-FCFS（RR）算法、I-MinMin算法及I-MaxMin算法。下面開始對三種改進版傳統任務調度算法進行說明與實驗。

4.1? ?對傳統任務調度算法的改進

本文對傳統任務調度算法不做過多介紹，只對改進版的傳統任務調度算法進行相關分析，它們都是通過在原有算法中嵌入QoS需求約束進行的，如表4—表6所示。

上述三種改進版傳統任務調度算法在為任務選擇合適的虛擬機過程中，每一步都要經過QoS需求的層層約束。在滿足QoS需求約束的情況下，任務會被放置到合適的虛擬機中;在不滿足QoS需求約束的情況下，任務會被取消。

4.2? ?實驗相關參數

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

表7中虛擬機的數據采用的是阿里云云服務器ECS中共享型實例的標準數據。在阿里云服務器ECS定價界面中選擇華東2地域，實例價格信息選擇入門級用戶、經典網絡、非Windows系統，以及優化的I/O即可找到這些虛擬機實例的相關數據信息，如圖1所示。

依照阿里云幫助文檔中關于云服務器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。因此本文假設這五種不同類型虛擬機的主頻分別擁有0.5GHz、1GHz、1.5GHz、2GHz和2.5GHz這五種主頻，且所有Cpu的每個機器周期都等于四個時鐘周期，每條指令等于三個機器周期，則該Cpu的時鐘周期數（每條指令執行的時鐘周期個數）為3*4=12個，最終由公式：Cpu的運算能力=主頻/時鐘周期數，可以得到了表7中五種類型虛擬機的Cpu運算能力。

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

（1）初始化CloudSim，創建CloudinformationSerVice服務;

（2）創建數據中心（包含創建主機的過程）;

（3）創建數據中心代理;

（4）創建虛擬機，并提交給數據中心代理;

（5）創建任務，并提交到數據中心代理;

（6）開始模擬;

（7）停止模擬;

（8）輸出模擬結果。

下面將對實驗的結果進行分析。

4.3? ?改進版傳統任務調度算法實驗結果與分析

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

（a）任務完成度（TCR）

（a）Task completion rate

（b）任務最終完成時間（MakeSpan）

（b）Task final completion time

（c）任務平均執行時間（ATET）

（c）Average rask execution time

（d）云服務商總收益（Profitcsp）

（d）Cloud service provider's total profit

算法的QoS違約率和未違約任務數統計如圖3和圖4所示。

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