云環(huán)境下基于SLA的工作隊列調配算法研究

王啟明，甘 泉

（平頂山學院計算機科學與技術學院河南平頂山 467000）

云環(huán)境下基于SLA的工作隊列調配算法研究

王啟明，甘 泉

（平頂山學院計算機科學與技術學院河南平頂山 467000）

云計算環(huán)境下，工作任務的調度和計算資源的分配受到SLA的約束。不同的工作任務要求不同的QoS，采用具有SLA參數(shù)的約束條件，對任務劃分優(yōu)先級，形成優(yōu)先級隊列。在對該任務分配計算資源時，采用資源等級隊列的方法，分配合理的工作節(jié)點已完成任務。

云計算；SLA；工作隊列；調度算法

1 引 言

在云計算平臺應用的各種技術中，資源調度算法是一個很關鍵的技術。因為它負責把任務分配到工作節(jié)點中運行，云計算平臺性能的好壞主要體現(xiàn)在任務分配的合理程度?，F(xiàn)有資源調度算法很多，一些經(jīng)典的算法如Min－min算法、遺傳算法、WQR算法（WQ的改進算法）和LATE算法等。這些算法有各自的特點，但也存在不足。

有學者提出一個優(yōu)先級工作隊列資源調度算法［1］。該算法是在WQ算法的基礎上，加入工作節(jié)點模糊評級策略。該算法用運行任務的平均完成時間對工作節(jié)點進行評級，避免了根據(jù)硬件信息進行評價的困難。工作節(jié)點選擇算法通過順序查找等級隊列，在找到的等級中隨機選擇工作節(jié)點，然后把任務分配給工作節(jié)點運行。工作節(jié)點等級遷移算法通過同級比較和異級比較的過程，使等級隊列逐漸完成。

資源調度過程中，考慮到云計算的服務質量，云計算服務提供商通過與客戶簽訂SLA（Service－Level Agreement）將非本地的網(wǎng)絡資源以更具有針對性，更高速更廉價的方式提供給用戶，并根據(jù)SLA中所簽訂的內容來保證各自利益。由于云計算環(huán)境下計算中心本身的大規(guī)模性，服務器之間可能存在的異構性，節(jié)點之間可能存在負載不均的現(xiàn)象，這將嚴重威脅到機器性能，從而用戶的服務質量不能得到保證，服務提供商還需根據(jù)SLA內容繳納違約罰金［2］。所以在云計算環(huán)境下如何建立有效的負載均衡機制合理利用網(wǎng)絡資源以保證SLA成為必須考慮的研究內容。

2 經(jīng)典資源調度算法分析

2.1 Min－m in算法

Min－min算法的思路是：優(yōu)先調度長度最小的任務和優(yōu)先分配任務給任務完成時間最小的工作節(jié)點［3］。其目的是優(yōu)化多個任務的總體完成時間，并面向批處理任務的情況下而提出的資源調度算法。算法運行的基礎是先要獲得每個任務在各個工作節(jié)點上運行的時間和任務的長度，因此，每調度一個任務都要遍歷一次所有的工作節(jié)點，這對于規(guī)模大的云計算平臺，效率低，開銷大。同時，由于任務被分配給性能最好的那些工作節(jié)點，沒有被分配到任務的節(jié)點則處于閑置狀態(tài)，該算法還存在負載不均的問題［4］。

2.2 遺傳算法

遺傳算法的思路是：假設有m個任務，n個工作節(jié)點，進行染色體編碼和解碼，表示出任務的總完成時間，適應度函數(shù)設計為：

染色體會通過一定的交叉和變異的操作而變化，經(jīng)過多次迭代運算，可以找出一個使任務的完成時間最短的解［5］。

由于遺傳算法得出最優(yōu)解的過程需要反復迭代多次，時間和空間開銷比較大；再者，這個算法和Min－min算法一樣，需要每個任務在每個工作節(jié)點上的完成時間的ETC矩陣，這個矩陣是很難獲得的。因此，遺傳算法不是一個在實際的云計算平臺中適合的資源調度算法。

2.3 WQ算法和WQR算法

WQ（Workqueue）算法的思路是：對任務是按照FIFO的原則調度，先提交的任務最先調度，而對于工作節(jié)點的選擇則是隨機進行。每當有工作節(jié)點空閑的時候，WQ算法就立即分配一個新任務給它。

WQ算法的過程很簡單，它雖然這種方法在局部的時間內不是最優(yōu)的，但在較長的時間跨度內，由于性能高的工作節(jié)點完成任務速度快，算法分配給性能高的工作節(jié)點的任務數(shù)量總體偏多。因此WQ算法在降低任務的平均完成時間方面有不錯的性能。它避免了Min－min算法和遺傳算法固有的缺點。WQ算法運行過程中，不需要獲取詳細的工作節(jié)點信息和任務信息，沒有復雜的運算過程，在云計算平臺負載較高時，算法有很突出的性能。WQ算法的缺點是，由于算法是隨機選擇工作節(jié)點，當云計算平臺負載較低時，所選擇的工作節(jié)點性能有很大的不確定性。

WQR（Workqueue with Replication）算法是WQ算法的改進型，它在WQ算法原理的基礎上，對每一個調度的任務都同時在多個工作節(jié)點上運行，以獲得更好的任務完成時間。WQR算法在異構的云計算平臺上具有良好的性能。WQR算法過程同樣簡單，它也不需要獲取工作節(jié)點和任務的信息，是一個可行的算法。WQR算法改善了在云計算平臺負載較低的情況下的性能。WQR算法的缺點是對資源的消耗比較大。

2.4 LATE算法

LATE算法的思路是：用任務遷移的方法解決較慢的任務。在Hadoop中，一個工作會被劃分為多個任務，然后把這些任務分配給閑置的工作節(jié)點運行。但有時會把任務分配給性能比較低的工作節(jié)點，由于這個工作節(jié)點完成任務耗時長，因此成為整個工作完成的短板。LATE算法通過把這個任務重新分配給另外一個工作節(jié)點運行的方法來避免這個問題。LATE算法用ProgressScore來評價任務的進度，從而選擇哪一個任務重新運行。

LATE算法的過程簡單，而且改正了Hadoop默認算法的缺點，在異構的云計算平臺上有很好的表現(xiàn)。它通過評估任務的剩余完成時間決定某個任務是否需要重復執(zhí)行，減少了無謂的資源浪費。是一個可行的資源調度算法。這個算法的缺點是，當一個任務被調度到另外一個工作節(jié)點重復執(zhí)行時，該任務需要從原點重新執(zhí)行。這種任務的遷移也沒有考慮到網(wǎng)絡負載的因素，可能造成事倍功半。

3 基于QoS約束的負載均衡問題

服務等級協(xié)議SLA是關于服務供應商與客戶間簽訂的一份合同，其中定義了服務類型、服務質量和客戶付款等方面的內容，同時也包含了關于供應商提供的服務達不到服務等級協(xié)議時，供應商應對用戶進行的賠償?shù)葍热荩?］。服務等級協(xié)議SLA就是服務供應商和用戶之間經(jīng)過協(xié)商達成的一系列的目標，其主要目的是為了達到和維持一定的服務質量（QoS）。

隨著云計算技術的發(fā)展，越來越多的關于云計算的應用將投入使用，所以，如何保證云計算的安全性問題也得到了廣泛關注，而如何保證云計算的服務質量，也將成為云計算繼續(xù)發(fā)展的重要前提。因此，在用戶與云供應商簽訂合同時，也更加關注服務等級協(xié)議SLA。在服務等級協(xié)議SLA中，需要清晰的寫明能夠提供的各項服務參數(shù)指標，以及服務達不到要求時的違約責任，從而更好地保證用戶的權益。SLA中規(guī)定了服務的響應時間，數(shù)據(jù)的安全保障等QoS的內容，以及計費付費模式等等，因此SLA是評判云服務的標準，也是提供商最關注的環(huán)節(jié)之一。所以提高云計算的服務質量盡量降低SLA違約風險是研究的重要內容。但是對于云計算這樣大規(guī)模集群式的服務器模式以及云計算基礎設施的異構性以及服務類型的多樣性，導致系統(tǒng)中有些節(jié)點處于重載，與此同時，另一些節(jié)點處在輕載甚至空閑狀態(tài)，重載節(jié)點響應速度急劇下降，系統(tǒng)無法提供服務，SLA違約。所以，部署一個有效的負載均衡策略對于保障云計算服務SLA來說，是至關重要的。

4 基于SLA的任務隊列

4.1 優(yōu)先級任務隊列設計

在作業(yè)分類器中設計從用戶服務等級協(xié)議信息到作業(yè)優(yōu)先級的映射機制。提取服務等級協(xié)議中四個主要的服務參數(shù)（可用性、響應時間、資源彈性和違約罰金）的指標值。對參數(shù)的指標值進行等級分類設計，將每個服務參數(shù)分為三個類別，具體的分類設計，如表1所示。

表1 SLA服務權值表Tab.1 The SLA service weight value table

在基于SLA的作業(yè)優(yōu)先級機制中，作業(yè)i的優(yōu)先級設為NICE，其取值為：

其中，NICE值越大，優(yōu)先級越高，反之，優(yōu)先級越低。作業(yè)按照優(yōu)先級NICE值形成優(yōu)先級隊列。一段時間內，若有相同NICE的作業(yè)出現(xiàn)，則按照FIFO的算法排列在相同NICE的作業(yè)后。

4.2 作業(yè)數(shù)據(jù)結構設計

任務隊列是待處理的任務的FIFO隊列，此隊列中的任務是最小不可再分的，是分配給工作節(jié)點處理的最小單位。任務定義為

其屬性說明如下：

IDT為任務的編號；

UT為任務的所有者標識，通過這個所有者標識可以區(qū)分調度的優(yōu)先級；

IDataT為需要處理的數(shù)據(jù)，調度算法可以通過把任務分配給有本地數(shù)據(jù)的工作節(jié)點，避免了網(wǎng)絡傳輸數(shù)據(jù)帶來的開銷，從而優(yōu)化云計算平臺的網(wǎng)絡負載；

ODataT為處理完成后的數(shù)據(jù)；

ST為任務狀態(tài)，云計算中的工作節(jié)點的穩(wěn)定性參差不齊，因而會出現(xiàn)任務不能正常運行，通過標示任務的狀態(tài)，從而為此類任務重新調度時，可以更先調度并賦予更高性能優(yōu)先級的工作節(jié)點，以便迅速完成；

PT為任務費用，由于云平臺中不同的工作節(jié)點需要不同的處理費用，通過表示任務可付的費用，當調度時可以分配一些與之相適應成本的工作節(jié)點，這對于減少云計算平臺運行成本至關重要［1］。

5 基于SLA的工作隊列資源調度算法設計

5.1 主要實體數(shù)據(jù)結構

5.1.1 工作節(jié)點

工作節(jié)點是處理任務的單位，即任務分配的對象，是計算資源和存儲資源的提供者。云計算中，大量采用虛擬化技術，每一臺計算機可以虛擬出一個或多個個工作節(jié)點。因此實際工作節(jié)點的數(shù)量可以大大多于實體機器的數(shù)量。工作節(jié)點定義為其屬性說明如下：

IDW為工作節(jié)點編號；

SW為工作節(jié)點可以提供的存儲資源的大小，作為工作節(jié)點選擇的一個重要依據(jù)；

BW為工作節(jié)點網(wǎng)絡帶寬，工作節(jié)點選擇的一個重要依據(jù)；

MaxTW為工作節(jié)點最大同時運行的任務數(shù)量，不同性能的工作節(jié)點設置不同的最大任務數(shù)量，工作節(jié)點的負載也是通過使用此屬性來標識；

TW是記錄在工作節(jié)點上運行的任務的總時間，此值是通過累加任務運行的時間得出；

NW為在工作節(jié)點上運行的任務的總數(shù)量，此值是通過累加任務的數(shù)量得出，把TW／NW得出的平均運行時間來表示工作節(jié)點的快慢，從而間接地評價了工作節(jié)點的性能；

RW為工作節(jié)點的級別，工作節(jié)點的分級是以在此工作節(jié)點上運行任務的平均完成時間為基礎，平均完成時間越小，級別越高，從而更優(yōu)先調度。此值只能由工作節(jié)點遷移算法更改；

CW為工作節(jié)點的使用費用，與任務中的PT配合使用，為任務的分配提供選擇依據(jù)，從而達到最小使用成本的目的。

5.1.2 等級隊列

等級隊列為多個工作節(jié)點分級隊列，隊列中的工作節(jié)點根據(jù)平均任務完成時間來分級。等級隊列的屬性為

其屬性說明如下：

NRQ為等級隊列中分級數(shù)，分級數(shù)的多少直接影響著優(yōu)先級工作隊列算法的性能，分級數(shù)越多，本算法的性能越好，但算法的運行時間會越長。分級數(shù)由云計算平臺的管理員來設置，平臺中的工作節(jié)點性能差別越大，分級數(shù)應該越多，反之越少，當分級數(shù)為一時，本算法就退化為WQ算法［7］；

MaxWRQ為每一個分級中最多包含的工作節(jié)點數(shù)，這個屬性是由算法自動設置，通常每一級都分配相同數(shù)量的工作節(jié)點，以達到最好的平均性能；

QRQ為保存工作節(jié)點的隊列數(shù)組，數(shù)組的大小為NRQ，每一個數(shù)組項都為工作節(jié)點的列表。本文中，默認設定最高級別為0級，最低級別為NRQ－1級。

5.2 資源調度算法

5.2.1 工作隊列選擇算法

調度算法把在任務隊列中的任務合理地分配給工作節(jié)點，從而優(yōu)化任務的平均完成時間和負載均衡［8］。工作節(jié)點的選擇是指在數(shù)量眾多的工作節(jié)點中選擇特定數(shù)量的工作節(jié)點，為任務分配計算資源和存儲資源。工作節(jié)點選擇算法在待調度任務隊列中選擇一個任務，分配給某一個工作節(jié)點，工作節(jié)點的選擇會根據(jù)工作節(jié)點的分級信息和數(shù)據(jù)的存儲位置等信息為依據(jù)，而工作節(jié)點的分級信息是動態(tài)變化的，因此工作節(jié)點選擇算法在調度每一個任務時都要讀取一次分級信息。

5.2.2 算法流程設計

調度每一個任務前，都運行一次工作節(jié)點選擇算法。時間復雜度為O（NRQ），NRQ為分級數(shù)。算法的流程如下：

（1）從任務隊列中獲取一個任務t，轉到流程（2）；如果隊列為空，則退出算法；

（2）獲取存儲有任務輸入數(shù)據(jù)的工作節(jié)點列表L。如果列表L中有工作節(jié)點w存在于待分配任務的工作節(jié)點分級集合中，并且w為待分配任務的工作節(jié)點中最高級別的，則把任務t分配給工作節(jié)點w，轉到（1）；如果沒有，則轉到（3）；

（3）從i（i初始為0）級別開始獲取當前級別上待分配任務的工作節(jié)點列表La，如果La為空，則設i＝i＋1，轉到（4）；如果La不空，轉到（5）；

（4）如果i大于Nrq－1，則等待直到收到待分配任務的工作節(jié)點信息，設置i＝0，轉到（3）；

（5）從待分配任務的工作節(jié)點列表La中隨機選擇一個工作節(jié)點Wa，把任務t分配給工作節(jié)點Wa，轉到（1）。

5.2.3 算法分析

這種算法優(yōu)先把任務分配給存儲有任務輸入數(shù)據(jù)的工作節(jié)點［9］，可以減少不必要的網(wǎng)絡傳輸［10］。該算法用運行任務的平均完成時間對工作節(jié)點進行評級，避免了根據(jù)硬件信息進行評價的困難。工作節(jié)點選擇算法通過順序查找等級隊列，在找到的等級中隨機選擇工作節(jié)點，然后把任務分配給工作節(jié)點運行。工作節(jié)點等級遷移算法通過同級比較和異級比較的過程，使等級隊列逐漸完成。

6 結束語

本文研究了在SLA約束下的云計算平臺中，云計算任務基于約束條件的優(yōu)先級隊列設計，和資源調度算法。在任務優(yōu)先級隊列設計中，對某些文獻中的優(yōu)先級隊列設計進行了改進，文獻中，SLA服務參數(shù)采用等級值｛A，B，C｝的方法設計，筆者經(jīng)過演算認為，在用戶服務等級協(xié)議與作業(yè)等級的映射表Mapping Table中，會出現(xiàn)Job Level重疊的情況，因此改為采用二進制權值的方法來標記參數(shù)。在資源調度算法中，考慮到云計算平臺的計算負荷，采用復雜度適中的算法設計，更能夠符合云計算平臺的實際情況。當任務執(zhí)行過程中，面臨SLA違約的危險時，就要才用任務遷移的方法，任務遷移算法將作為后續(xù)研究內容。

［1］ 葉毅峰.云環(huán)境下優(yōu)先級工作隊列資源調度算法研究［D］.暨南大學，2013.

YE Yifeng.The Priority Workqueue Resource Scheduling Algorithm for Cloud Environment［D］.Jinan University，2013.

［2］ 王銳.云計算環(huán)境中基干SLA的負裁均衡機制研究［D］.云南大學，2012.

WANG Rui.Research on Load－Balancing Mechanism Based on SLA in Cloud Environment［D］.Yunnan University，2012.

［3］ Armstrong R，Hensgen D，Kidd T.The relative performance of various mapping algorithms is independent of sizable variances in runtime predictions［J］.In 7th IEEE Heterogeneous Computing Workshop，（HCW 98），1998，10（2）：79－87.

［4］ Freund R F，Gherrity M，Ambrosius S.Scheduling resources in multi－user，heterogeneous，computing environments with SmartNet［J］.In 7th IEEE Heterogeneous ComputingWorkshop，（HCW 98），1998，10（2）：184－199.

［5］ 李建鋒，彭艦.云計算環(huán)境下基于改進遺傳算法的任務調度算法［J］.計算機應用，2011，31（1）：184－186.

LI Jianfeng，PENG Jian.Task scheduling algorithm based on improved genetic algorithm in cloud computing environment［J］.Journal of computer applications［J］，2011，31（1）：184－186.

［6］ 張建.云計算服務等級協(xié)議SLA研究［J］.電信網(wǎng)技術，2012，2（2）：7－10.

ZHANG Jian.Research on cloud computing service level agreements［J］.Telecommunications network technology，2012，2（2）：7－10.

［7］ Jing Lu，Meifang Shao.Relaxing Data Integrity in Cloud Computing Environment［J］.International Journal of Digital Content Technology and its Applications，2012，6（13）：241－249.

［8］ 鄭湃，崔立真，王海洋.云計算環(huán)境下面向數(shù)據(jù)密集型應用的數(shù)據(jù)布局策略與方法［J］.計算機學報，2010，33（8）：1472－1480.

ZHENG Pai，CUI Lizhen，WANG Haiyang A Data Placement Strategy for Data—Intensive Applications in Cloud［J］.CHINESE JOURNAL OF COMPUTERS，2010，33（8）：1472－1480.

［9］ Alain Tchana，Laurent Broto，Daniel Hagimont.Approaches to Cloud Computing Fault Tolerance［R］.IEEE CITS 2012－2012 International Conference on Computer，Information and Telecommunication Systems.2012：25－27.

［10］ CloudSim.A Framework For Modeling And Simulation Of Cloud Computing Infrastructures And Services［EB／OL］.2011.http：／／www.cloudbus.org／cloudsim／

王啟明 男（1980－），河南魯山縣人，講師，主要研究方向為軟件工程、算法設計等。

甘 泉 男（1980－），安徽靈璧縣人，講師，主要研究方向為操作系統(tǒng)、算法分析等。

A Work Queue Scheduling Algorithm Based on SLA Under Cloud Environment

WANG Qiming，GAN Quan
（College of computer science and technology，Pingdingshan University，Pingdingshan 467000，China）

Under cloud computing environment，task scheduling and computing resources allocation is constrained by the SLA.Different tasks require different QoS，so the work queue is classified w ith constraints of the SLA parameter.Task is allocated on the computing resources by reasonable assignment of work node in the resource level queue.

cloud computing；SLA；work queue；scheduling algorithm

TP 312

A

河南省科技廳攻關項目（KJT142102210226）