王啟明，甘 泉

（平頂山學(xué)院計算機科學(xué)與技術(shù)學(xué)院河南平頂山 467000）

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

王啟明，甘 泉

（平頂山學(xué)院計算機科學(xué)與技術(shù)學(xué)院河南平頂山 467000）

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

云計算；SLA；工作隊列；調(diào)度算法

1 引 言

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

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

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

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

2.1 Min－m in算法

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

2.2 遺傳算法

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

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

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

2.3 WQ算法和WQR算法

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

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

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

2.4 LATE算法

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

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

3 基于QoS約束的負(fù)載均衡問題

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

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

4 基于SLA的任務(wù)隊列

4.1 優(yōu)先級任務(wù)隊列設(shè)計

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

表1 SLA服務(wù)權(quán)值表Tab.1 The SLA service weight value table

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

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

4.2 作業(yè)數(shù)據(jù)結(jié)構(gòu)設(shè)計

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

其屬性說明如下：

IDT為任務(wù)的編號；

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

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

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

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

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

5 基于SLA的工作隊列資源調(diào)度算法設(shè)計

5.1 主要實體數(shù)據(jù)結(jié)構(gòu)

5.1.1 工作節(jié)點

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

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

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

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

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

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

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

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

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

5.1.2 等級隊列

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

其屬性說明如下：

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

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

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

5.2 資源調(diào)度算法

5.2.1 工作隊列選擇算法

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

5.2.2 算法流程設(shè)計

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

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

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

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

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

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

5.2.3 算法分析

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

6 結(jié)束語

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

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

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

［2］ 王銳.云計算環(huán)境中基干SLA的負(fù)裁均衡機制研究［D］.云南大學(xué)，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)境下基于改進遺傳算法的任務(wù)調(diào)度算法［J］.計算機應(yīng)用，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］ 張建.云計算服務(wù)等級協(xié)議SLA研究［J］.電信網(wǎng)技術(shù)，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ù)密集型應(yīng)用的數(shù)據(jù)布局策略與方法［J］.計算機學(xué)報，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－），河南魯山縣人，講師，主要研究方向為軟件工程、算法設(shè)計等。

甘 泉 男（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

河南省科技廳攻關(guān)項目（KJT142102210226）