雙層虛擬化云架構(gòu)下任務(wù)調(diào)度能耗優(yōu)化算法

張 馳，王宇新，馮 振，郭 禾

1.大連理工大學(xué) 軟件學(xué)院，遼寧 大連116024

2.大連理工大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，遼寧 大連116024

3.浪潮電子信息產(chǎn)業(yè)股份有限公司 高效能服務(wù)器和存儲技術(shù)國家重點實驗室，濟南250101

近年來，無論是在科學(xué)研究還是商業(yè)領(lǐng)域，為了節(jié)約時間和經(jīng)濟成本，越來越多的工作流任務(wù)被托管到云平臺上運行[1]。隨著云計算基礎(chǔ)設(shè)施需求不斷擴大，云數(shù)據(jù)中心的規(guī)模呈爆炸式增長，能耗過高已經(jīng)成為制約云計算產(chǎn)業(yè)健康發(fā)展的關(guān)鍵性問題。在過去的幾十年中，云數(shù)據(jù)中心中計算資源的能耗已經(jīng)占到其總能耗的45%[2]。為此，研究人員提出了多種節(jié)能策略如動態(tài)電壓和頻率縮放（DVFS）技術(shù)，工作流任務(wù)能耗優(yōu)化調(diào)度策略，以及動態(tài)虛擬機合并策略。

虛擬化技術(shù)是云計算服務(wù)的核心和基礎(chǔ)，是提高云數(shù)據(jù)中心服務(wù)器資源利用率的關(guān)鍵[3]。虛擬機技術(shù)作為傳統(tǒng)的虛擬化技術(shù)會消耗大量的啟動時間和服務(wù)器資源。相對于虛擬機的笨重，容器作為一種輕量化的虛擬化技術(shù)應(yīng)用越來越廣泛[4]。但是，由于容器共享服務(wù)器操作系統(tǒng)造成的隔離性不夠也會導(dǎo)致一些安全隱患[5]。兩者是不同層次的虛擬化技術(shù)，根據(jù)其各自的特性，將它們?nèi)诤鲜褂?，如在虛擬機上部署容器形成雙層虛擬化架構(gòu)，可以使它們優(yōu)勢互補，更好地發(fā)揮作用[5]。一方面既能提供虛擬機帶來的隔離性和安全性，又可以提供容器所擁有的輕便性和靈活性。另一方面，通過在虛擬機上部署多個容器可以使系統(tǒng)中的虛擬機的數(shù)量大大減少，相應(yīng)地減少部署虛擬機的資源浪費和等待時間。大型云服務(wù)提供商，如Amazon Web Services、Microsoft Azure 和Google Container Engine，都已經(jīng)在虛擬機實例上部署了容器；VMware等虛擬化公司也提交了相關(guān)的專利申請[6]。

在傳統(tǒng)的并行工作流任務(wù)能耗調(diào)度算法中，任務(wù)獨占一個計算資源，調(diào)度時考慮的任務(wù)執(zhí)行代價就是它占用計算資源的時長。在雙層虛擬化架構(gòu)的云數(shù)據(jù)中心中，任務(wù)由容器執(zhí)行，任務(wù)的執(zhí)行代價不僅體現(xiàn)在容器的運行時長，也包括其占用計算資源的大小。多個容器的部署也會受到虛擬機有限資源的限制，因此傳統(tǒng)算法并不能適用于雙層虛擬化架構(gòu)。為此，本文提出了一種新的能耗優(yōu)化調(diào)度算法。在滿足用戶給定工作流截止時間約束的條件下，給出合理的調(diào)度方案以降低云數(shù)據(jù)中心的能耗。算法通過兩個階段完成調(diào)度，首先，在滿足用戶截止時間約束的同時，給出使用最少的虛擬機和服務(wù)器完成工作流的調(diào)度方案；然后，最小化上一階段調(diào)度方案中虛擬機和服務(wù)器的工作時間。

1 相關(guān)工作

關(guān)于云數(shù)據(jù)中心的工作流任務(wù)能耗優(yōu)化調(diào)度問題，國內(nèi)外學(xué)者進行了大量的研究。在不使用虛擬化技術(shù)的場景下，Thanavanich[7]提出用處理器上分配任務(wù)的效率比作為性能度量的EHEFT和ECPOP算法，即在經(jīng)典的DAG啟發(fā)式列表調(diào)度算法HEFT和CPOP[8]的一次調(diào)度基礎(chǔ)上，關(guān)閉調(diào)度方案中效率比低的處理器，將其上的任務(wù)重新分配到其余處理器上。王國豪等[9]提出了一種工作流能效調(diào)度算法——CWEES，該算法通過重新分配輕載處理器上的任務(wù)至其他處理器，降低處理器的使用數(shù)量；然后使用DVFS 技術(shù)降低仍有空閑時槽的處理器電壓和時鐘頻率，擴展任務(wù)執(zhí)行時間，最終在不違背任務(wù)順序和截止時間約束前提下降低工作流執(zhí)行總能耗。但是這些算法將任務(wù)直接運行在服務(wù)器的處理器上，無法適用于目前云數(shù)據(jù)中心的虛擬環(huán)境。同時，算法中的處理器不能并行多個任務(wù)，也未考慮任務(wù)需求的計算資源量。

在虛擬機云環(huán)境下，謝毅等[10]提出了基于負載的能耗計算方法及相應(yīng)的工作流調(diào)度算法HMEC，算法在進行任務(wù)優(yōu)先級計算和任務(wù)選擇時同時考慮了任務(wù)間的優(yōu)先約束關(guān)系和數(shù)據(jù)傳輸；在進行虛擬機選擇時，采用了能耗消耗最小的任務(wù)分配規(guī)則。張奕等[11]提出了能源和時限可感知的非遷移調(diào)度算法EDA-NMS，通過利用任務(wù)時限的松弛度，延遲寬松時限任務(wù)的開始時間，減少使用的服務(wù)器數(shù)量，避免虛擬機遷移，達到降低能耗的目的。Zhu等[12]研究了具有用戶指定截止時間的獨立任務(wù)的能耗優(yōu)化調(diào)度問題。提出了一種依據(jù)能源效率的任務(wù)排序方法和虛擬機搜索策略。上述研究將虛擬機作為計算資源的最小分配單位來接收和處理工作流任務(wù)，但是在虛擬機模型中沒有考慮任務(wù)的并行處理能力，這種粗粒度的模型有很大的局限性。

在容器云環(huán)境下，Zhang 等[13]為了降低能耗以及容器鏡像和工作負載的網(wǎng)絡(luò)傳輸?shù)某杀?，提出了一種基于整數(shù)線性規(guī)劃的解決方案。李磊[14]使用任務(wù)排隊模型對容器云建模，構(gòu)建基于任務(wù)QoS約束的能耗最小化的目標(biāo)函數(shù)，再利用李雅普諾夫優(yōu)化算法求解，減少容器運行數(shù)量，獲得高資源利用率。Canosa等[15]通過定義容器請求能力模型和完全能力模型來約束不同模型中任務(wù)執(zhí)行的速度上限，并給出分配任務(wù)到容器的調(diào)度策略集。但是，這些研究中容器直接放置在物理機上，同時也沒有考慮到任務(wù)之間的優(yōu)先約束關(guān)系。

對于雙層虛擬化架構(gòu)的云數(shù)據(jù)中心能耗問題，目前還沒有關(guān)于工作流任務(wù)調(diào)度的研究成果，已有工作主要集中在資源調(diào)度上。例如，Hussein等[16]提出了一個雙層放置架構(gòu)，使用基于最優(yōu)擬合的蟻群優(yōu)化算法（ACO-BF）完成容器到虛擬機以及虛擬機到服務(wù)器的放置，算法的適應(yīng)度函數(shù)同時評估虛擬機和服務(wù)器剩余資源量。本課題組之前曾研究[17]針對虛擬機云環(huán)境下有截止時間約束的并行工作流任務(wù)的能耗優(yōu)化調(diào)度，本文在此基礎(chǔ)上進行了擴展和改進，提出了能夠適應(yīng)雙層虛擬化架構(gòu)云數(shù)據(jù)中心的工作流任務(wù)調(diào)度算法。

2 系統(tǒng)模型和相關(guān)定義

2.1 云數(shù)據(jù)中心模型

本文面向的云數(shù)據(jù)中心基于在虛擬機上部署容器的雙層虛擬化云架構(gòu)，如圖1所示。

圖1 雙層虛擬化云架構(gòu)

容器是工作流任務(wù)的處理單元，部署在虛擬機上，虛擬機部署在服務(wù)器上。具體的約束關(guān)系如下：

（1）任務(wù)和容器之間是一一對應(yīng)的關(guān)系，即任務(wù)只能放在一個容器上執(zhí)行，而且在執(zhí)行過程中不能被打斷。容器的大小等于任務(wù)要求的計算能力。任務(wù)執(zhí)行完成后，容器銷毀，釋放占用的計算資源，容器的生命周期等于任務(wù)需要的計算時長。

（2）只要虛擬機上有足夠的計算資源，多個容器可以并行在一個虛擬機上。

（3）一個工作流的容器可以根據(jù)需要放置在一個或者多個虛擬機上，但是為了工作流之間的隔離性和安全性，虛擬機上只能放置同一個工作流的容器。工作流的所有任務(wù)執(zhí)行完成后，運行該工作流的所有虛擬機會被銷毀，釋放計算資源。

（4）虛擬機的創(chuàng)建以最大化利用服務(wù)器資源為原則，只有當(dāng)已使用服務(wù)器上沒有足夠的計算能力時才會啟動新的服務(wù)器。

（5）由于要考慮使用的服務(wù)器和虛擬機的數(shù)量，為了簡化問題模型，假設(shè)所有的服務(wù)器和虛擬機同構(gòu)，也就是所有的虛擬機的計算能力(vc)都是相同的，每個服務(wù)器上能放置的最大虛擬機數(shù)量(vn)也是相同的。那么，服務(wù)器的計算能力hc=vn×vc。

2.2 工作流模型

通常，云計算中應(yīng)用的工作流包含很多具有依賴關(guān)系的并行任務(wù)，可以用有向無環(huán)圖（Directed Acyclic Graph，DAG）來表示其中，V是DAG中所有節(jié)點的集合，工作流中有n個任務(wù)，每個任務(wù)分別與DAG 中的一個節(jié)點對應(yīng)。節(jié)點的權(quán)值是任務(wù)的計算量，與傳統(tǒng)工作流DAG的最大區(qū)別是，表示為任務(wù)要求的計算能力乘以計算時長。這里假設(shè)是由用戶提前給出的，并且在任務(wù)的執(zhí)行過程中不會改變。E是DAG 中所有邊的集合，如果兩節(jié)點之間存在一條邊，則說明任務(wù)τi是τj的前驅(qū)任務(wù)，相應(yīng)地，τj是τi的后繼任務(wù)。一個任務(wù)只有在它所有的前驅(qū)任務(wù)都完成之后才能開始執(zhí)行?？紤]到可以忽略同部署在一個服務(wù)器的容器之間的通信代價，模型中沒有給出邊的權(quán)值，邊只代表任務(wù)之間的優(yōu)先約束。工作流有給定的釋放時間TR和相對截止時間TD，絕對截止時間可以表示為TR+TD。

規(guī)定一個DAG中只能有一個沒有前驅(qū)的節(jié)點作為入口節(jié)點和一個沒有后繼的節(jié)點作為出口節(jié)點，它們分別對應(yīng)工作流中的入口任務(wù)(τentry)和出口任務(wù)(τexit)。因此，當(dāng)工作流中存在多個沒有前驅(qū)的任務(wù)時，需要為這些任務(wù)增加一個計算量為0的虛擬任務(wù)作為前驅(qū)，同樣，當(dāng)存在多個沒有后繼的任務(wù)時，也會為這些任務(wù)增加一個計算量為0的虛擬任務(wù)作為后繼。

圖2 給出了一個用DAG 表示的工作流實例，圖中給出了每個任務(wù)的計算量，τ0和τ11是虛擬的入口任務(wù)和出口任務(wù)，TR=0，TD=25。

圖2 工作流DAG示例

2.3 能耗模型

Feller等[18]根據(jù)服務(wù)器功率和資源利用率之間的近似線性關(guān)系給出了服務(wù)器功率的計算公式：

其中，PRidle和PRmax分別是服務(wù)器在空閑和滿載時的功率，u是服務(wù)器資源利用率。服務(wù)器資源利用率(u)根據(jù)服務(wù)器上使用的虛擬機數(shù)量(vnused)來計算：

最終，將執(zhí)行工作流所使用的所有物理機的能耗加起來就是云數(shù)據(jù)中心完成這個工作流的總能耗。

2.4 相關(guān)定義

定義1 任務(wù)拓撲層級表示任務(wù)在DAG 中的層級，具體定義如下：

定義2 路徑長度和關(guān)鍵路徑，路徑長度定義為路徑上所有任務(wù)的計算時長的總和。關(guān)鍵路徑是指從τentry到τexit有最長的路徑長度的路徑。一個DAG中可能存在多條關(guān)鍵路徑，但是它們有相同的路徑長度，稱為關(guān)鍵路徑長度(TC)。對于有嚴(yán)格截止時間的工作流，給定的相對截止時間必須不小于關(guān)鍵路徑長度，即TD≥TC。根據(jù)定義，對于圖1的DAG，TC=22。

定義3 任務(wù)最早開始時間和最遲完成時間，主要取決于工作流的TR和TD，以及DAG的結(jié)構(gòu)，它們的計算公式如下：

定義4 任務(wù)松弛時間，指出在工作流的實際完成時間不超過截止時間的條件下，τi可以最長推遲的時間。它可以用來代表一個任務(wù)的緊急程度，越小意味著任務(wù)更加緊迫。如果，那么這個任務(wù)必須在開始執(zhí)行，否則將導(dǎo)致違反截止時間。的計算公式如下：

定義5 任務(wù)開始時間和完成時間是指在調(diào)度算法給出的調(diào)度方案中τi實際的開始時間和完成時間，。而且根據(jù)和的定義，必然存在兩個約束條件，

定義6 調(diào)度中任務(wù)最早開始時間和最遲完成時間是指在任務(wù)調(diào)度過程中，τi可以最早開始執(zhí)行的時間和最遲完成的時間。調(diào)度開始時，和的值分別被初始化為和，在調(diào)度過程中，隨著τi的前驅(qū)和后繼任務(wù)被調(diào)度完成，和會不斷變化。

定義7 虛擬機可用范圍，如果在某一個時間段，虛擬機上的資源沒有完全被容器占用，那么虛擬機在這個時間段內(nèi)的空閑資源被稱為是虛擬機可用范圍。每個虛擬機的是一個集合，集合中的每個元素(ark)有三個屬性，分別是可用時間段開始時間(stk)和結(jié)束時間(ftk)，以及可用資源量(vrk)。每當(dāng)有一個容器被放置在VMj上，將更新。

定義8weightu和weightd，參照Topcuoglu等在文獻[19]中提出的ranku和rankd，提出了weightu和weightd。weightu是從當(dāng)前任務(wù)到τexit的最長路徑上所有任務(wù)的計算量（包含當(dāng)前任務(wù)），計算時從τexit遞歸向上到τentry；weightd是從τentry到當(dāng)前任務(wù)的最長路徑上所有任務(wù)的計算量（不包含當(dāng)前任務(wù)），計算時從τentry遞歸向下到τexit。其中計算量等于要求的計算能力乘以計算時長，具體計算公式如下：

3 算法設(shè)計

本文的目標(biāo)是給出在截止時間內(nèi)完成且能耗最低的工作流調(diào)度方案，調(diào)度算法分兩個階段實現(xiàn)，分別是時間利用率最大化調(diào)度（TUMS）和運行時間壓縮（RTC）。TUMS 階段通過充分使用給定的時間范圍來盡可能減少完成工作流所使用的虛擬機和服務(wù)器數(shù)量，給出初步的調(diào)度方案。RTC 階段找出調(diào)度方案中可以提前運行的容器，在滿足任務(wù)間優(yōu)先約束的同時，通過壓縮虛擬機上前面的空閑時間來提前它們的開始時間，以縮短虛擬機和服務(wù)器的工作時間，最終達到降低能耗的目標(biāo)。

3.1 時間利用率最大化調(diào)度階段

減少完成工作流所需的虛擬機和服務(wù)器數(shù)量的途徑是延長它們的工作時間，在有嚴(yán)格截止時間約束的條件下，只能最大化時間利用率。TUMS是啟發(fā)式列表調(diào)度策略，調(diào)度的第一步是確定每個任務(wù)的優(yōu)先級。對于兩個任務(wù)τi和τj，確定優(yōu)先級的四條規(guī)則具體描述如下：

（3）如果相關(guān)任務(wù)數(shù)量也相同，根據(jù)任務(wù)要求的計算能力；如果，則τi有更高的優(yōu)先級。

（4）對于前三個規(guī)則不能區(qū)分優(yōu)先級的任務(wù)，根據(jù)任務(wù)的拓撲層級；如果，則τi有更高的優(yōu)先級。

如果存在上述規(guī)則不能區(qū)分優(yōu)先級的任務(wù)，則隨機分配。最終，將所有任務(wù)按優(yōu)先級降序排列存儲在一個有序列表。

所有的任務(wù)根據(jù)其weightu和weightd的大小關(guān)系被分為前置任務(wù)和后置任務(wù)兩類。如果，說明當(dāng)前任務(wù)后面有比前面更多的計算量，為了留下更多的運行空間給其后繼任務(wù)的容器，li應(yīng)該盡早開始運行，屬于前置任務(wù)；反之，如果＜，則li應(yīng)該盡量推遲，屬于后置任務(wù)。

TUMS從L中依次取出任務(wù)li，找到合適的虛擬機來部署它的容器，并確定其ST(li)。先創(chuàng)建個虛擬機，并依次編號。對于li，它的開始時間可以在區(qū)間中選擇。使用li的開始時間范圍以及它要求的計算能力和計算時長，去匹配每個虛擬機的可用范圍，找到能夠容納li容器的所有虛擬機。如果已有的虛擬機中沒有可用的，則要新創(chuàng)建一個。同時要根據(jù)li的類別確定它在這些虛擬機上的最優(yōu)開始時間。最后，根據(jù)li的類別，前置任務(wù)在所有虛擬機中選擇最優(yōu)開始時間最小的，后置任務(wù)選擇最優(yōu)開始時間最大的，虛擬機放置它對應(yīng)容器，同時，最終的ST(li)等于它在該虛擬機上的最優(yōu)開始時間。

一個任務(wù)調(diào)度完成后，TUMS更新該任務(wù)所有前驅(qū)任務(wù)的SLFT和后繼任務(wù)的SEST，同時更新接收容器的虛擬機的AR。重復(fù)執(zhí)行上述步驟，直到工作流中的所有的任務(wù)都調(diào)度完成。TUMS 的時間復(fù)雜度為n為工作流中任務(wù)數(shù)量，m為虛擬機數(shù)量，為任務(wù)的平均計算時長。

3.2 運行時間壓縮階段

TUMS給出調(diào)度方案后，進入RTC階段。RTC的任務(wù)是找到每個虛擬機上可以提前運行的容器，壓縮虛擬機的空閑時間以減少虛擬機和服務(wù)器的工作時間。可以提前運行是指在容器的開始時間之前，虛擬機上有足夠的可用范圍，并且容器提前之后不會違背任務(wù)之間的優(yōu)先關(guān)系。這個階段通過四個步驟實現(xiàn)：

步驟1 建立一個有序列表L′，將所有的任務(wù)按照它們在TUMS 中的優(yōu)先級遞增的順序存儲在L′中，也就是說，L′是L的反向列表。

步驟2 找到L′中的第一個開始時間不等于最早開始時間的任務(wù)，也就是。

步驟3 記錄的容器所在的虛擬機為VMj，如果中存在一個元素k，滿足且vrk≥，而且不是VMj上最早開始運行的容器，那么更新，。

步驟4 更新所有后繼任務(wù)的SEST，以及AR(VMj)。

重復(fù)步驟2 到4，直到檢查完L′中的所有任務(wù)。在步驟3中，不考慮虛擬機上最早運行的容器是因為提前它的開始時間只會拉長它與后續(xù)容器之前的空閑時間，而不會縮短虛擬機的工作時間。RTC 的時間復(fù)雜度為，n為工作流中任務(wù)數(shù)量。

3.3 算例說明

本節(jié)利用圖2 的DAG，說明TUMS-RTC 算法的過程。在TUMS 階段，通過計算所有任務(wù)的優(yōu)先級，有序列表L={τ0,τ11,τ10,τ8,τ2,τ7,τ1,τ6,τ4,τ5,τ9,τ3}，除了τ9、τ10和τ11是后置任務(wù)之外，其余任務(wù)都是前置任務(wù)。TUMS階段的調(diào)度結(jié)果如圖3（a）所示。τ0和τ11是虛擬的入口任務(wù)和出口任務(wù)，權(quán)值為0，在圖中用虛線表示。接著，RTC 階段中找到τ10對應(yīng)的容器C10可以提前運行，將由19提前到16，這樣VM0的工作時間由25縮短到了24。圖3（b）給出了經(jīng)過RTC階段后TUMSRTC算法的最終調(diào)度結(jié)果。

圖3 算法調(diào)度結(jié)果

4 實驗與結(jié)果分析

4.1 實驗配置與性能指標(biāo)

如前文所述，以往的工作流能耗優(yōu)化調(diào)度算法無法直接應(yīng)用于雙層虛擬化云架構(gòu)。為了評估TUMS-RTC算法的性能，使用HEFT和EHEFT算法的調(diào)度思想實現(xiàn)了能夠適用于雙層虛擬化云架構(gòu)的HEFT*算法和EHEFT*算法，將它們作為對比的基準(zhǔn)算法。在EHEFT*算法中，由于虛擬機在任務(wù)執(zhí)行完之后就會銷毀，無法使用EHEFT 算法中的效率比作為評價指標(biāo)，這里選擇關(guān)閉工作時間最短的虛擬機。另外，由于在雙層虛擬化云架構(gòu)下目前還沒有公開的真實工作流數(shù)據(jù)，對比實驗中使用大量參數(shù)可控的隨機DAG作為測試工作流。

本文以能耗優(yōu)化為工作流任務(wù)調(diào)度的目標(biāo)，因此設(shè)計了以下三個性能指標(biāo)量化算法間的性能對比：

（1）資源利用率，表示執(zhí)行工作流使用的所有虛擬機的總使用資源與總占有資源的比例，占有資源為虛擬機計算能力乘以虛擬機工作時間。資源利用率的計算公式如下：

wt(VMj)為虛擬機VMj的工作時間，也就是虛擬機上第一個容器開始的時間到最后一個容器結(jié)束的時間。

（2）虛擬機數(shù)量減少率，表示使用的虛擬機數(shù)量在虛擬機上限數(shù)量上的減少率。

（3）能耗節(jié)省率，表示完成工作流的能耗在上限能耗上的減少率。

由于不同DAG 之間的差異，后兩個指標(biāo)使用相對于上限的減少率比直接使用虛擬機數(shù)量和能耗的效果更好。為了給出基準(zhǔn)值，提出層次順序調(diào)度策略，把DAG 的節(jié)點按層次順序排序，調(diào)度時將其放在能使它最早完成的虛擬機上。將層次順序調(diào)度中使用的虛擬機數(shù)量作為虛擬機基準(zhǔn)數(shù)量，完成工作流的能耗作為基準(zhǔn)能耗。

4.2 DAG隨機生成程序

為了得到大量有可控特征的隨機工作流DAG，設(shè)計了DAG 隨機生成程序，通過設(shè)置多個輸入?yún)?shù)來控制生成的DAG的特征。

（1）節(jié)點（任務(wù)）數(shù)量，n。

（2）寬度，fat?？刂艱AG 的形狀，每層節(jié)點的個數(shù)最大值為因此fat的最大值為在n確定的情況下，fat越大，工作流的并行度越高，DAG層數(shù)越少。

（3）勻稱度，regularity?？刂聘鲗娱g節(jié)點數(shù)的差異情況，最大值為1。每層節(jié)點的個數(shù)最小值為regularity，因此regularity越大表示每層節(jié)點數(shù)越相似，DAG更勻稱。

（4）邊密度，density?？刂艱AG 相鄰兩層的節(jié)點之間連接的緊密程度，density越大，它們之間的邊越多。最大值為1，說明一個節(jié)點與它下一層的每個節(jié)點之間都有邊。

參數(shù)的值從以下相應(yīng)的集合中選擇：

上述參數(shù)的組合可以生成大量不同的DAG 模型，對每種模型隨機生成100個具體的DAG 作為實驗測試工作流。另外，由于在云數(shù)據(jù)中心中資源的數(shù)量可以看作是無限的，這種情況下，HEFT*和EHEFT*算法都一定會按照DAG 的關(guān)鍵路徑長度完成工作流。因此，為了對比的公平性，實驗中將工作流的截止時間設(shè)置為關(guān)鍵路徑長度，即TD=TC。

4.3 實驗結(jié)果

任務(wù)要求的計算能力wc和計算時長wt對不同調(diào)度算法的性能對比沒有影響。由于任務(wù)不能拆分，其對應(yīng)的容器必須能夠放置到一個虛擬機上，因此wc必須小于等于虛擬機的計算能力vc。實驗中，vc取值為6，wc取值為區(qū)間[1，6]內(nèi)的隨機整數(shù)；wt取值為[1，20]內(nèi)的隨機整數(shù)。針對工作流DAG 的四種參數(shù)，分別進行了四組對比試驗，詳細實驗結(jié)果分析如下。

第一組實驗觀察工作流中任務(wù)數(shù)量n對算法性能的影響，fat、regularity和density的值分別設(shè)置為5、0.6和0.6，實驗結(jié)果如圖4 所示。圖4（a）是資源利用率的情況。隨著n的增加，HEFT*算法的資源利用率持續(xù)降低，由將近75%降低到不到55%；TUMS-RTC 算法的資源利用率穩(wěn)定維持在75%到85%之間，且始終高于EHEFT*算法。圖4（b）是虛擬機數(shù)量減少率的情況。三個算法的虛擬機數(shù)量減少率隨著工作流規(guī)模的增大沒有明顯的變化趨勢，TUMS-RTC 算法與HEFT*和EHEFT*算法的平均差值為38.8%和16.9%。圖4（c）是能耗節(jié)省率的情況。隨著n的增加，HEFT*算法的能耗節(jié)省率持續(xù)下降，HEFT*算法的能耗節(jié)省率維持在15%左右，TUMS-RTC 算法的能耗節(jié)省率持續(xù)增加。當(dāng)n=500 時，TUMS-RTC算法的能耗節(jié)省率達到38.75%，是HEFT*算法的近6 倍。原因分析如下，HEFT*算法在調(diào)度時將容器放在它能最早完成的虛擬機上，當(dāng)n增加時，DAG中同層次的任務(wù)數(shù)量會增加，因此它會使用過多的虛擬機，資源利用率也會下降，同時，由于作為基準(zhǔn)的層次順序調(diào)度同樣會將容器放在它能最早完成的虛擬機上，這樣HEFT*算法的虛擬機數(shù)量減少率不會增加，這樣能耗節(jié)省率就會下降；EHEFT*算法在第二次調(diào)度時會對虛擬機數(shù)量有一定的縮減，因此能夠保持比較高的資源利用率，虛擬機數(shù)量減少率和能耗節(jié)省率；TUMS-RTC 算法在調(diào)度任務(wù)時會盡量為其后續(xù)的任務(wù)留出空間，充分利用已有的虛擬機，因此當(dāng)n增加時，依舊能夠使用較少的虛擬機，保持很高的資源利用率和虛擬機數(shù)量減少率，這樣相較于基準(zhǔn)算法，TUMS-RTC 算法的能耗節(jié)省率會上升。根據(jù)第一組實驗的結(jié)果，TUMS-RTC 算法相較于層次順序調(diào)度算法最高減少了將近45%的虛擬機使用量和40%的能耗，資源利用率維持在80%左右，在調(diào)度任何規(guī)模的工作流時的性能都明顯優(yōu)于兩個對比算法，而且隨著任務(wù)數(shù)量的增加，算法的性能不受影響。

圖4 任務(wù)數(shù)量對算法性能的影響

第二組實驗觀察工作流的寬度fat對算法性能的影響，n、regularity和density的值分別設(shè)置為100、0.6和0.6，fat的最大值為，即10，實驗結(jié)果如圖5 所示。圖5（a）是資源利用率的情況。三個算法的資源利用率都隨著fat的增大而上升，TUMS-RTC與HEFT*和EHEFT*算法的平均差值分別接近15%和3%。虛擬機上的空閑時間是由于虛擬機上順序執(zhí)行的容器之間的時間間隔造成的，當(dāng)n不變時，fat越大，處于同一層級的節(jié)點越多，調(diào)度時會使用更多的虛擬機，每個虛擬機上順序執(zhí)行的容器會變少，導(dǎo)致虛擬機的空閑時間變少，因此資源利用率就會上升。圖5（b）和圖5（c）分別是虛擬機數(shù)量減少率和能耗節(jié)省率的情況。三個算法的虛擬機數(shù)量減少率和能耗節(jié)省率都隨fat增大而增加，因為工作流并行的變高之后，在層次順序調(diào)度中，同一層次的所有任務(wù)依次調(diào)度，為了保證它們的容器都能在最早開始時間開始執(zhí)行，就會用到過多的虛擬機。另外，當(dāng)fat由1增大時TUMS-RTC算法的虛擬機數(shù)量減少率和能耗節(jié)省率都明顯提升，然后分別穩(wěn)定在43%和30%左右。因為當(dāng)fat為1 時，工作流中的任務(wù)趨近于順序執(zhí)行，調(diào)度算法的效果有限，當(dāng)fat增加時，TUMSRTC算法由于同時考慮了任務(wù)的計算能力和計算時長，可以達到很好的性能。根據(jù)第二組實驗的結(jié)果，TUMSRTC 算法在調(diào)度任何寬度的工作流時的性能都明顯優(yōu)于兩個對比算法，而且當(dāng)fat很大，也就是工作流中任務(wù)并行度很高時，算法依然有很好的性能。

圖5 工作流寬度對算法性能的影響

第三組實驗觀察工作流的勻稱度regularity對算法性能的影響，n、fat和density的值分別設(shè)置為100、5和0.6，實驗結(jié)果如圖6 所示。圖6（a）是資源利用率的情況。三個算法的資源利用率都隨著regularity的增大而上升。因為隨著regularity的增大，工作流各層的任務(wù)數(shù)量相差更小，調(diào)度時容器在虛擬機上的分布也會更加均勻，所以資源利用率會上升。圖6（b）和圖6（c）分別是虛擬機數(shù)量減少率和能耗節(jié)省率的情況。三個算法的虛擬機數(shù)量減少率和能耗節(jié)省率隨regularity的變化沒有明顯變化趨勢。因為工作流中每個層次的任務(wù)數(shù)量越平均時，工作流中從入口任務(wù)到出口任務(wù)的各條路徑長度也就越平均，越接近于關(guān)鍵路徑長度，在截止時間等于關(guān)鍵路徑的情況下，算法很難將同一條路徑上的任務(wù)對應(yīng)的容器集中放置在一個虛擬機上，因此雖然資源利用率增加，但是使用了較多虛擬機導(dǎo)致降低的能耗有限。盡管如此，TUMS-RTC 算法相較于HEFT*和EHEFT*算法，在虛擬機數(shù)量減少率上的優(yōu)勢分別有40%和16.5%，在資源利用率上分別提升了將近20%和9%。

圖6 工作流勻稱度對算法性能的影響

第四組實驗觀察工作流的邊密度density對算法性能的影響。n、fat和regularity的值分別設(shè)置為100、5和0.6，實驗結(jié)果如圖7所示。三個算法的性能基本不受density變化的影響。因為如前文模型定義中所述，本文的工作流中，不計任務(wù)之間數(shù)據(jù)傳輸?shù)韧ㄐ砰_銷，因此DAG中的邊只代表任務(wù)之間的優(yōu)先關(guān)系，沒有權(quán)值，因此對調(diào)度幾乎沒有影響。在資源利用率、虛擬機數(shù)量減少率和能耗節(jié)省率上，TUMS-RTC算法與HEFT*算法的差值平均值分別接近17%、37%和20%；與EHEFT*的差值平均值分別接近5%、14%和9%。

圖7 工作流邊密度對算法性能的影響

在實驗中，三種算法的資源利用率都很高，因為資源利用率的計算以虛擬機為單位，虛擬機在它上面所有的容器銷毀之后也會被關(guān)閉。服務(wù)器上的空余資源可以被其余用戶的虛擬機使用，這也是虛擬化技術(shù)的優(yōu)勢，因此不以服務(wù)器為單位計算資源利用率。根據(jù)上述實驗結(jié)果分析，TUMS-RTC算法的性能在各項對比指標(biāo)上都明顯優(yōu)于HEFT*算法和EHEFT*算法。通過統(tǒng)計所有工作流模型的調(diào)度結(jié)果數(shù)據(jù)，TUMS-RTC算法有80%左右的資源利用率，相較于層次順序調(diào)度有40%左右的虛擬機數(shù)量減少率和30%左右的能耗節(jié)省率，達到了優(yōu)化能耗的調(diào)度目標(biāo)。另外，在工作流中任務(wù)數(shù)量和并行度增加時，該算法依舊可以保持很好的性能，說明它能夠很好地應(yīng)用于云數(shù)據(jù)中心中大型高并行度工作流的任務(wù)調(diào)度。

4.4 算法分析

云數(shù)據(jù)中心計算設(shè)備的能耗主要由啟動的服務(wù)器數(shù)量和它們的工作時間兩個因素決定，TUMS-RTC算法在兩個階段中分別針對兩個因素給出優(yōu)化策略，根據(jù)實驗結(jié)果可以看出取得了預(yù)期的效果。算法在初始調(diào)度之后增加RTC階段會在一定程度上增加實現(xiàn)成本，但這部分增加的成本是可接受的。首先，RTC階段對初始調(diào)度結(jié)果的調(diào)整需要完整的虛擬機的可用范圍數(shù)據(jù)，會使用額外的存儲空間，但算法的整體空間復(fù)雜度依舊是，而且對當(dāng)前計算機的內(nèi)存容量不會構(gòu)成瓶頸。另外，TUMS階段的時間復(fù)雜度與任務(wù)的平均計算時長相關(guān)，當(dāng)任務(wù)的計算時間過長時會對算法的性能有一定的影響，但相較于任務(wù)計算的時間，調(diào)度時長可基本忽略不計。

5 結(jié)語

云數(shù)據(jù)中心中，在虛擬機上部署容器的成為一種趨勢，為了解決該架構(gòu)下云數(shù)據(jù)中心的能耗問題，本文提出了一種針對有截止時間約束的工作流的能效優(yōu)化調(diào)度算法TUMS-RTC。算法通過時間利用率最大化調(diào)度和運行時間壓縮兩個階段，在保證截止時間約束的條件下，提高了資源利用率，最小化了完成工作流所需的虛擬機和服務(wù)器數(shù)量，從而達到了降低云數(shù)據(jù)中心能耗的目標(biāo)。使用大規(guī)模隨機工作流進行對比實驗，結(jié)果證明算法對云數(shù)據(jù)中心中大型工作流的能耗優(yōu)化調(diào)度是有效的。在下一步的研究中，將考慮工作流任務(wù)間的通信開銷和云數(shù)據(jù)中心服務(wù)器和虛擬機的異構(gòu)，使問題模型更加貼近真實場景，并設(shè)法使用真實的云數(shù)據(jù)中心數(shù)據(jù)和環(huán)境進行實驗。