基于延遲任務云資源調度方法的研究

花嶸 張友裕

摘? 要： 基于云任務的動態延遲到達，到達時間具有隨機性，進行任務分配到虛擬機執行的仿真模擬。仿真任務是基于排隊論的指數分布到達方式，虛擬機的處理速度存在差異。實驗思路是高優先級盡可能早的執行，同時避免低優先級任務餓死的思路，并定義了一個消費量作為對比點，對比基于一定等待的調度與貪心調度的差異。通過設置動態等待時間的設置來進行實驗，同時測試多組輸入數據減少樣本的偶然性。對比分析各種數據，驗證實驗的有效性。并通過CloudSim進行云仿真實驗模擬。

關鍵詞： 云計算;任務調度;延遲任務

中圖分類號： TP302.1? ? 文獻標識碼： A? ? DOI：10.3969/j.issn.1003-6970.2019.10.031

本文著錄格式：花嶸，張友裕. 基于延遲任務云資源調度方法的研究[J]. 軟件，2019，40（10）：139141+190

Research on Cloud Resource Scheduling Method Based on Delayed Task

HUA Rong， ZHANG You-yu

（College of Computer Science and Engineering， Shandong University of Science and Technology， Qingdao 266510， China）

【Abstract】： Dynamic delay arrival based on cloud tasks， random arrival time， simulation of task assignment to virtual machine execution. The simulation task is based on the arrival of the exponential distribution of the queuing theory， and the processing speed of the virtual machine is different. The experimental idea is to execute the high priority as early as possible， while avoiding the idea of starvation of low priority tasks， and define a consumption as a comparison point， comparing the difference between scheduling based on certain waiting and greedy scheduling. Experiments are performed by setting the dynamic wait time setting， while testing multiple sets of input data reduces the contingency of the sample. Compare and analyze various data to verify the effectiveness of the experiment. And cloud simulation experiment simulation through CloudSim.

【Key words】： Cloud computing; Task scheduling; Delayed task

0? 引言

云計算是通過網絡利用遠程服務器上的資源進行計算，資源量、運算速度可以幾十倍上百倍的大于本地計算機最后把結果收集起來，還可以作為一些網站的載體等作用。云計算在現代社會中占據著越來越重要的地位，各種互聯網大企業也都在發展各種云業務，包括谷歌、亞馬遜、阿里、騰訊等。云資源的使用能減少企業對實體資源投入的花銷，同時，也能減少企業物理機，服務器等的迭代更新，也能減少這部分的花銷。由于云的廣泛使用，關于云上的資源調度，任務調度就成為大家研究的課題之一[10-12]。

云資源調度主要包括兩個方面的研究方向[8]。第一種，是基于云任務與運算單元的負載均衡，即把所有任務均勻的分配給各個運算單元，兼顧各運算單元的能力（快處理器盡可能分配更多的資源），以及任務之前的依賴關系，在每一時間盡可能的把所有可用處理器都調用起來。第二種是基于最小花費的資源調度，通過定義資源的單位價值，資源使用量與單位價值乘積，然后各種資源再求和，得到總的資源消耗量[4]。

1? 問題提出

現實生活中，云計算資源調度不會按照給定的時間，有序的到來，充滿著許多的隨機性。我們需要考慮這些隨機性的存在，設計出適合動態到達的模型[9]。同時，對該問題需要有一定的衡量標準，我們定義一個消耗量作為判斷該算法優劣程度的標準，該算法需要均衡考慮等待時間與執行時間，設計出一個盡可能小的消耗量的算法。

基于此本文的出發點是任務到達后，基于任務優先級等待一定時間，盡可能把執行速度快的處理器分配給優先級更高的任務，讓高優先級任務能更早執行更早完成，以此達到更低的消耗量（基于優先級的一個定義量）[13]。同時，即使是低優先級任務也是能夠執行的，使任務盡可能不至于等待太長時間。本文的工作目標是確保較高優先級任務能夠更快完成，同時兼顧低優先級任務能夠完成，不至于發生“饑餓”[6]。

2? 具體實現

2.1? 參量設置

通過排隊論指數分布進行任務到達的隨機取樣，確保任務的隨機性[7]。不過，進行對比實驗時，會事先把任務的到達時間預先存取到一個文件內，確保兩個對比實驗的數據是相同的[3]。

連續的兩個任務到達時間間隔為

interval=，x為[0，1]內的隨機數

（1）

一般設置為0.05，0.1，0.15等值（值越小間隔越大）。仿真時，先產生一組完整的值，數量為任務的個數，存入一個文本文件內。

定義若干個虛擬機vm（執行單元，用于執行任務），虛擬機的數量為。確保這若干個虛擬機是異構的，要求處理速度要不同，同時執行速度相差不要特別小。

本文定義的cost考慮兩部分來源，等待時長與執行時長，假設等待時長的權重為A，執行時長的權重為B，則A+B=1。則cost為

（2）

其中，N為總的任務個數，為任務完成時間，為任務開始執行時，為任務到達時間，P為任務優先級，取值為1-10的整數，cost為這若干個任務的單獨花費的總和，三個時間存在如下的關系，

， （3）

執行l為當前任務的長度，v為該任務選擇的虛擬機的執行速度（v的可能取值個數為虛擬機的? ?數量）。

等待時間B*P后的分數因子為（0，1]的值，為了與等待時間相差不大，執行時間A*P后的因子也為該取值范圍的值，在定義cost時最后乘上1%這個值，是為了盡可能使兩者的值在一個數量級。以此確保計算的cost能相對合理的衡量任務分配的花銷問題。也就是說，該值的設置應該是與整體的任務長度以及運算單元的執行速度是相關的。

2.2? 調度設計

本文的調度算法是動態延遲等待再分配，通過設定一個含m個元素的隊列用來暫存數據，由于分配時是把隊列內的所有任務立刻進行分配，所以要確保隊列的大小需要小于虛擬機的數量（）。設置一個閾值時間來防止等待時間過長[5]。

（1）記錄第一個到達隊列內的時間（該值大小為此任務的，同一批次分配內的任務都以此時間作為判斷），隊列內的任務最大等待時間為。對之后到來的任務會進行一次判斷，當任務的優先級高于某值，且空閑虛擬機內有執行速度較快的虛擬機時，進行直接分配，不加入待執行任務隊列，當不滿足這種情況時，把任務加入待執行隊列。應當與到達第一個任務的優先級相關，任務優先級越低等待時間偏向于越長，則此次隊列內任務的最晚執行時間為，該執行時間發生的情況為，在閾值時間內，到達的任務個數是小于m的，在規定時間內沒有達到足夠的任務，直接進行了分配，定義當前到達的任務數量為a個，我們假定所有的任務不會分在同一虛擬機上，即為把a個任務分配給個虛擬機，第一個任務有種選擇，第二個任務選擇少一，以此類推，則對當前隊列內任務可行的分配方案為種，計算所有的cost，并把消費最低的cost作為分配執行方案。

（2）還有一種情形是在截止時間前，已經到達了m個任務。則會在第m個任務到達時，立即開始分配執行任務，則此時的時間是小于的，開始執行的時間即為第m個任務的到達時間。則在這種情況下可能的分配方案個數共為，同樣計算所有cost，并從中選擇最小值作為最終的執行方案。

（3）當把隊列內的任務清空分配之后，會把下一次到達的任務的再次作為新的，并重復上述過程，直到所有任務執行完成。

3? 實驗仿真

設置虛擬機的個數為5個，5個虛擬機的執行速度分別為100，125，150，175，200，任務的總個數N為30，任務的大小為5000到15000內的隨機數，另外，本文假定A=0.7，B=0.3，強調執行時間重于等待時間的量。

仿真實驗的是在CloudSim上面測試的[1-2]，該應用是基于Java語言的。我們做的對比實驗是，在任務到達的時刻就進行基于貪心分配的計算，高優先級任務分給快一些的虛擬機，低優先級的任務分配較慢的虛擬機，并用相同的輸入數據計算兩組實驗的值，進行對比大小。為保證兩組輸入是完全一樣的，我們先采用要求的隨機數的方法產生一組值，具體的數據包括任務的優先級，任務的長度，任務的到達時間，基于3個進行實驗，值分別為0.05，0.1，0.15，以此來設置任務到達的時間間隔進行對比實驗，每次計算涉及到3個量，30組數，共90個數據，并把該值存入一個文本文件內，執行時先從文本文件內讀入數據。在實驗之前，先進行簡單的計算，我們以最后一個任務的到達時間作為對比量，以此來刪除誤差較大的量，盡量把到達的時間控制在一定的范圍，消除偶然性，同時進行多組實驗，排除特殊樣本可能存在不合理性的可能。

（1）按上面要求設置的第一組實驗，任務到達較快，系數為0.15，取最晚到達任務的時間在170-230的范圍內，在貪心情況下，除了每個虛擬機分配的第一個任務，均需要等待一定時間才能執行，也就是說大概25個任務需要進行等待操作，實驗結果是，該組實驗下優化效果尤為明顯。cost值的差值一般能達到7到10左右。

（2）在第一組的基礎上，修改指數分布的系數為0.1，取最晚到達任務的時間在250-350的范圍內，使任務的到達時間間隔變大，需要等待的任務稍微變少，同時，兩組實驗cost的差值也變小了，大概平均只能在2到3的水平。

（3）在上兩組的基礎上，修改指數分布的系數為0.05，取最晚到達任務的時間在520-680的范圍內，繼續增大任務到達的時間間隔，使任務幾乎都能在到達時，都能有空閑的虛擬機，在該組實驗下，不僅無優化，反而比基于貪心的對比實驗還要差4-6的水平。

（4）在基于（1），（2）的實驗結果基礎上，加做一組指數分布系數為0.125，取最晚到達任務的時間在200-280的范圍內，該組實驗結果在（1），（2）的中間水平，有優化效果，cost差值大概為4-6，效果在（1）與（2）的中間水平。

4? 結果分析

由于樣本的差異性，可能存在一些效果更好，和一些效果一般的情況。但總的來說，效果較為理想。在任務到達的速度快過任務執行的速度時，比較極端的情況是除了第一組值，其他任務的執行均需等待，在趨向于這種情況時，優化效果較好，并隨著任務到達速度的減慢（指數分布系數變小，間隔變大），優化效果逐漸變差，甚至當任務到達特別慢時，反而不如另一組實驗。原因是在這種情況下，每個任務到達時，都有空閑虛擬機，任務都能直接執行，進行一定的等待，反而是不明智的。

參考文獻

[1]Rodrigo N. Calheiros， Rajiv Ranjan， Anton Beloglazov， Cesar A. F. De Rose， and Rajkumar Buyya. CloudSim： A Toolkit for Modeling and Simulation of Cloud Computing Environments and Evaluation of Resource Provisioning Algorithms. Software： Practice and Experience （SPE）[J]， 2011， 41： 23-50.

[2]周婉， 王移芝. 基于卡爾曼預測器的云計算資源調度研究[J]. 軟件， 2015， 36（9）： 12-15.

[3]趙琴. 排隊論在車間調度中的研究與應用[D]. 蘭州： 蘭州理工大學. 2013： 9-28.

[4]馮田. 基于sufferage的動態出租車拼車調度算法. 電腦知識與技術[J]. 2011（7）： 7019-7023.

[5]周平， 殷波， 邱雪松， 等. 面向服務可靠性的云資源調度方法. 電子學報[J]. 2019（5）： 1036-1043.

[6]黃坤， 吳俊. Gang調度在云計算任務遷移和饑餓處理中的性能和成本評估[J]. 華中師范大學學報（自然科學版）， 2013（5）： 621-625+631.

[7]姜海燕. 基于指數分布參數的滾動軸承故障特征提取方法. 自動化技術與應用[J]， 2019（3）： 27-30+42.

[8]武凱， 勾學榮， 朱永剛. 云計算資源管理淺析[J]. 軟件， 2015， 36（2）： 97-101.

[9]熊舸， 張煜， 楊勇. 基于服務量的異構車載網絡資源調度算法[J]. 軟件， 2015， 36（5）： 54-60.

[10]劉鵬. 云計算[M]. 第三版. 北京： 電子工業出版社， 2016： 1-12.

[11]姜福成. 云計算的基礎結構設計和云應用服務[J]. 軟件， 2014， 35（7）： 97-102.

[12]王曉艷. 基于云計算的數據中心建設探討[J]. 軟件， 2014， 35（2）： 129-130.

[13]詹文濤， 艾中良， 劉忠麟， 等. 一種基于YARN的高優先級作業調度實現方案[J]. 軟件， 2016（3）： 84-88.