云環境下基于SLA的工作隊列調配算法研究

王啟明，甘 泉

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

云環境下基于SLA的工作隊列調配算法研究

王啟明，甘 泉

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

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

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

1 引 言

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

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

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

2 經典資源調度算法分析

2.1 Min－m in算法

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

2.2 遺傳算法

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

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

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

2.3 WQ算法和WQR算法

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

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

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

2.4 LATE算法

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

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

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

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

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

4 基于SLA的任務隊列

4.1 優先級任務隊列設計

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

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

在基于SLA的作業優先級機制中，作業i的優先級設為NICE，其取值為：

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

4.2 作業數據結構設計

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

其屬性說明如下：

IDT為任務的編號；

UT為任務的所有者標識，通過這個所有者標識可以區分調度的優先級；

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

ODataT為處理完成后的數據；

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

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

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

5.1 主要實體數據結構

5.1.1 工作節點

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

IDW為工作節點編號；

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

BW為工作節點網絡帶寬，工作節點選擇的一個重要依據；

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

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

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

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

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

5.1.2 等級隊列

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

其屬性說明如下：

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

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

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

5.2 資源調度算法

5.2.1 工作隊列選擇算法

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

5.2.2 算法流程設計

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

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

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

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

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

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

5.2.3 算法分析

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

6 結束語

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

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

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

［2］ 王銳.云計算環境中基干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］ 李建鋒，彭艦.云計算環境下基于改進遺傳算法的任務調度算法［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］ 張建.云計算服務等級協議SLA研究［J］.電信網技術，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］ 鄭湃，崔立真，王海洋.云計算環境下面向數據密集型應用的數據布局策略與方法［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－），安徽靈璧縣人，講師，主要研究方向為操作系統、算法分析等。

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）