混合云環(huán)境中調(diào)度執(zhí)行多工作流費用優(yōu)化算法

盧莉，李亮亮，黎紅友

（1.四川大學計算機學院，成都610065；2.四川大學網(wǎng)絡空間安全學院，成都610065）

0 引言

隨著計算技術的發(fā)展與變革，不斷有新的劃時代意義的技術涌現(xiàn)出來，例如網(wǎng)格計算、并行計算、效用計算等，近年來興起的云計算又是一次新的變革，但它也不完全是一種全新的技術，而是從之前的那些計算方式不斷演化而來的。美國國家標準與技術研究院（NIST）[1]定義云計算是一種使用便捷，通過網(wǎng)絡按需獲取的可配置的資源共享池，用戶根據(jù)使用量進行付費，并可以在上面快速部署應用。

工作流技術已經(jīng)發(fā)展了數(shù)十年，關于它的定義也多種多樣，工作流管理聯(lián)盟認為工作流就是要實現(xiàn)科學工作任務的自動化執(zhí)行，Buyya 等人則認為科學工作流就是根據(jù)各個任務之間的相互依賴關系或者它們之間的控制邏輯，自動化的完成科學任務[2]，而Bertrem Ludasher 等人認為科學工作流是一個由任務和任務之間的數(shù)據(jù)依賴所構(gòu)成的復雜的流程[3]，綜合上述可以看出工作流有兩個要點，其一是任務和任務之間的依賴關系，其二是自動化執(zhí)行。工作流一般分為傳統(tǒng)的業(yè)務工作流和需要大量計算的科學工作流，它們都具有工作流的一些基本特征，但又各具特點。例如兩種類型的工作流所面對的用戶不相同，傳統(tǒng)的業(yè)務工作流主要面向企業(yè)，他們會將自身的業(yè)務用業(yè)務工作流模型來構(gòu)建，而科學工作流主要面向科研人員；另外兩者所側(cè)重的內(nèi)容也不相同，傳統(tǒng)的業(yè)務工作流更關注控制結(jié)構(gòu)，即比較注重任務實際執(zhí)行時的順序，而科學工作流則偏重于數(shù)據(jù)的處理和傳輸。本文中的任務類型偏向科學工作流，包括需要大量計算的大數(shù)據(jù)和金融領域的工作流，下文簡稱為工作流或者任務。

由于執(zhí)行工作流對計算資源和存儲資源都有較大的需求，所以在傳統(tǒng)的分布式計算環(huán)境中都是將工作流部署到集群或者網(wǎng)格中去執(zhí)行[4]，而云計算的出現(xiàn)給工作流的執(zhí)行帶來了新的機遇，對工作流在云環(huán)境下進行高效的資源配置和制定恰當?shù)恼{(diào)度策略，不僅可以使工作流更加高效的執(zhí)行，也能降低用戶的成本，提高執(zhí)行的可靠性和安全性，同時云服務商也能提高云基礎設施的利用效率，減少能源浪費。

針對云環(huán)境中單個工作流的調(diào)度，Bittencourt 等人[5]使用混合云代價優(yōu)化（Hybrid Cloud Optimized Cost，HCOC）算法，在滿足工作流的期限和預算的前提下降低單個工作流的執(zhí)行費用；文獻[6]將混合云環(huán)境下單個工作流調(diào)度問題轉(zhuǎn)換為整數(shù)線性規(guī)劃問題，提高私有云的資源使用率并降低公有資源使用費用。

針對多工作流的調(diào)度，Kumar 等人[7]提出混合云時間費用優(yōu)化（Time and Cost Optimization for Hybrid Clouds，TCHC）算法，它能降低多個異構(gòu)工作流的執(zhí)行花費。Sharif 等人[8]考慮工作流的截止時間和數(shù)據(jù)安全性，提出基于部分關鍵路徑（Partial Critical Path，PCP）排序的混合云在線安全多端切割（Online Multi-terminal Cut for Privacy in Hybrid Clouds using PCP Ranking，OMPHC-PCPR）算法和基于任務排序的混合云數(shù)據(jù)安全在線調(diào)度（Online scheduling for Privacy in Hybrid Clouds using Task Ranking，OPHC-TR）算法來降低執(zhí)行花費；Lin 等人[9]針對連續(xù)提交的多個同構(gòu)大型工作流調(diào)度算法，提出分層迭代程序劃分（Hierarchical Iterative Application Partition，HIAP）算法來切割工作流成多個子任務，考慮帶寬限制、數(shù)據(jù)傳輸和計算代價，結(jié)合最小負載最長應用優(yōu)先（Minimum Load Longest App First，MLF）隊列排序算法和非直接至公有云（InDirectly to Public）策略，降低執(zhí)行花費，由于該算法所針對的場景與本文類似，因此該算法將作為本文的對比算法之一。

本文研究的場景是在混合云環(huán)境中調(diào)度執(zhí)行由不同的用戶動態(tài)提交的多個工作流，這些工作流具有不同的QoS 需求，而本文主要關注工作流的截止時間和安全需求，因此如何在保證工作流上述QoS 需求的同時優(yōu)化整個混合云系統(tǒng)的總費用支出是本文要解決的問題，本文針對該問題以及現(xiàn)有算法的不足，做了如下工作：

（1）對混合云中多工作流調(diào)度問題，提出了混合云環(huán)境中動態(tài)多工作流調(diào)度算法，優(yōu)先將工作流任務調(diào)度到私有云中執(zhí)行；采用多約束工作流分割機制，對無法在私有云中完成的任務進行分割形成子工作流。

（2）針對在私有云中調(diào)度執(zhí)行的工作流，提出了一種基于表啟發(fā)式算法改進而來的多工作流調(diào)度算法，提高私有云資源的利用率，減少公有云資源的使用量，從而優(yōu)化混合云系統(tǒng)的費用支出。

1 混合云中多工作流調(diào)度模型

1.1 任務模型

本文中的任務類型是工作流（Job），它由一系列子任務（Task）和任務與任務間的數(shù)據(jù)依賴關系構(gòu)成，由于子任務之間有數(shù)據(jù)依賴關系，所以它們的執(zhí)行具有先后順序，一個子任務執(zhí)行完成之后，依賴它的輸出數(shù)據(jù)的下一個子任務才有可能開始執(zhí)行，因為一個子任務可能同時依賴其他多個子任務的數(shù)據(jù)，因此需要具備所有數(shù)據(jù)才能開始執(zhí)行。使用有向無環(huán)圖（Directed Acyclic Graph，DAG）來描述工作流，圖中的結(jié)點（vertice）代表工作流的子任務，邊（edge）代表子任務之間的數(shù)據(jù)依賴關系。圖1 使用DAG 表示的一個簡單工作流示例。工作流中的每個子任務是一個獨立的執(zhí)行單元，即不能再被分割成更小的執(zhí)行單元，具有原子性，且本文規(guī)定一個子任務在執(zhí)行的過程中不能被剝奪資源打斷執(zhí)行。

圖1 工作流實例

在本文的場景中，用戶會持續(xù)不斷的向系統(tǒng)提交工作流執(zhí)行請求，這些工作流使用集合Job={job1,job2,…,jobi,…,jobI}表示，對每個工作流使用一個五維結(jié)構(gòu)來描述WF(T,D,WST,WDT,SN) ，其中T={t1,t2,…,ti,…,tN}表示該工作流的子任務集合，ti表示一個子任務，D={dti,tj|ti,tj∈T,i≠j}表示任務之間的數(shù)據(jù)依賴關系，WST（Workflow Submission Time）表示該工作流的提交時間，WDT（Workflow Deadline Time）表示工作流的截止完成時間約束，SN（Security Needs）表示工作流的安全需求。

1.2 資源模型

本文的混合云環(huán)境由私有云和M個公有云服務商（cloud provider）提供的公有云共同組成，用Cp表示所有公有云服務商，每個Cp對外提供Sm種處理能力不同的虛擬機實例，使用者根據(jù)自己的需求租用相應的虛擬機實例即可。為了保證服務更多用戶，公有云服務商規(guī)定企業(yè)可以租用的虛擬機實例數(shù)量是有限的，用ToNumm表示每個云服務商可提供的虛擬機總數(shù)，Nvmn表示每類虛擬機的數(shù)量，每一種虛擬機實例Vmn能提供的處理能力也各不相同，因為不同的虛擬機具有不同的處理器核心數(shù)Nvcpun，每種vcpu的處理能力也不盡相同，使用SPvcpun表示。

企業(yè)中的私有云使用CR表示，建立該私有云以及后期的運轉(zhuǎn)維護會產(chǎn)生一定的費用，但是本文不考慮這些成本開銷。私有云提供的虛擬機使用Vmq表示。

與私有云中的資源免費使用不同，公有云服務一般是按照一定的周期Tc計費的，本文中將采用不同服務商自定的計費周期時長Tc=h計算相應虛擬機的租賃費用，所以為了降低系統(tǒng)費用支出，需要充分利用好已租用的資源。

除了租用虛擬機帶來的費用開銷，私有云和公有云之間的數(shù)據(jù)傳輸開銷是系統(tǒng)費用支出中的另一大組成部分。本文根據(jù)現(xiàn)在一般商用公有云的實際情況，假設在各個云內(nèi)部傳輸數(shù)據(jù)是免費的，只有在云之間傳輸數(shù)據(jù)才會收取費用，并且該費用Cdata是按照傳輸?shù)臄?shù)據(jù)量大小進行計算的。

1.3 問題描述

本文中的工作流任務是由用戶隨機向系統(tǒng)提交的，因此工作流的到來具有不確定性，在工作流執(zhí)行的過程中隨時可能有其他新的工作流請求到達系統(tǒng)，那么調(diào)度器需要根據(jù)當前實際的資源使用狀況為新到來的任務分配資源，同時還需要考慮對已經(jīng)在資源上執(zhí)行的工作流的影響，避免新的資源分配方式導致已經(jīng)在執(zhí)行的任務不能按時完成。

本文使用DAG 表示工作流，假設工作流的任意一

假設私有云中各虛擬機之間的帶寬都是已知且固定的，引入一個Q 維的矩陣BW，其中的元素BWi,j表示私有云中的虛擬機Vmi和Vmj之間的通信帶寬，BWi,j=0 表示在虛擬機內(nèi)部傳輸數(shù)據(jù)不產(chǎn)生通信消耗，兩個有數(shù)據(jù)依賴關系的子任務ti和tj被分配到虛擬機Vmm和Vmn上執(zhí)行，則在這兩個結(jié)點之間所產(chǎn)生的數(shù)據(jù)傳輸時間開銷為：

其中Lm表示虛擬機在處理數(shù)據(jù)傳輸之前的準備開銷，dtitj/BWm,n表示傳輸數(shù)據(jù)的真正耗時。如果上述兩個任務被分配到同一個虛擬機上執(zhí)行，則本文忽略該時間開銷，因此兩個有數(shù)據(jù)依賴的子任務之間的平均數(shù)據(jù)通信開銷為：

Lˉm表示所有虛擬機在數(shù)據(jù)傳輸之前的準備耗時的均值，表示私有云內(nèi)部平均傳輸帶寬，即：個子任務ti在任何一個虛擬機中的運行時間都是可以估計得到的，使用wi,q表示每一個子任務ti在私有云中的虛擬機Vmq上的執(zhí)行時間，則子任務ti在私有云中執(zhí)行的平均時間表示為：

當把工作流調(diào)度到公有云中執(zhí)行時，由于工作流具有一定的安全等級需求，因此需要使用到公有云中的相應安全服務，本文使用文獻[10]中的安全模型，產(chǎn)生的額外時間開銷如下所示：

其中SCtlvmi表示子任務tl在虛擬機vmi上執(zhí)行時產(chǎn)生的安全服務時間開銷，當子任務tl在虛擬機vmi上執(zhí)行時，V為1，否則為0。

系統(tǒng)產(chǎn)生的總費用開銷包括虛擬機租賃費用和通信費用。引入向量KVmn表示某個服務商的虛擬機Vmn是否處于使用狀態(tài)，如果被租賃使用則其值為1，否則為0。從時刻timemin到timemax，使用公有云產(chǎn)生的租賃費用為：

數(shù)據(jù)通信產(chǎn)生的費用為：

其中Dataouti表示這段時間內(nèi)公有云Cpi傳輸?shù)剿接性浦械臄?shù)據(jù)量，PriceDatai表示數(shù)據(jù)通信單價。

因此這段時間內(nèi)總的費用開銷可表示為：

綜上，在混合云環(huán)境下調(diào)度執(zhí)行動態(tài)多工作流可用如下目標函數(shù)和限制條件表示：

2 混合云下多工作流調(diào)度策略

為了優(yōu)化整個系統(tǒng)的費用支出，優(yōu)先調(diào)度工作流到私有云中執(zhí)行，因此本節(jié)將首先提出一個私有云中的調(diào)度算法用于工作流在私有云中的調(diào)度執(zhí)行，提高私有云資源利用效率。

2.1 改進的表啟發(fā)式多工作流調(diào)度算法

由于系統(tǒng)中工作流請求和執(zhí)行都是動態(tài)進行著，所以調(diào)度系統(tǒng)具有一定的實時性需求，本文根據(jù)異構(gòu)最早完成時間（Heterogeneous Earliest Finish Time，HEFT）算法[11]提出一種適合本文場景的啟發(fā)式調(diào)度算法。

本文使用經(jīng)典的時間估算模型來計算一個工作流中各子任務的開始時間和完成時間。假設子任務ti在私有云虛擬機Vmq上執(zhí)行的最早開始時間（Earliest Start Time）表示為EST( )ti,Vmq，最早結(jié)束時間（Earliest Finish Time）為EFT( )ti,Vmq，實際結(jié)束時間（Actual Finish Time）為AFT( )ti,Vmq，則子任務ti的EST計算方式如下：

其中pre(ti)表示子任務ti的直接前驅(qū)任務集合，avail(Vmq)表示虛擬機Vmq完成上一個任務后可以開始執(zhí)行任務ti的時間，內(nèi)層max 表示任務ti所有的前驅(qū)任務全部運行完后依賴數(shù)據(jù)送達Vmq的時刻。任務ti的EST 通過遞歸定義，因此任務ti的最早開始執(zhí)行時間是其所有前驅(qū)節(jié)點已經(jīng)把依賴數(shù)據(jù)送達虛擬機Vmq的時刻和該虛擬機資源可用時刻中的較大者，即外層max 的含義。EST(tentry,Vmq)=0，則Makespan(job1)為job1中所有的出口子任務中AFT(texit)的最大者。對其他時刻提交的任務請求，Makespan(jobi）則是出口子任務中AFT(texit)最大者與任務最早開始調(diào)度執(zhí)行的時間之差。

由于工作流中的子任務執(zhí)行具有先后順序，因此需要為它們制定合理的調(diào)度順序。首先對一個工作流中的子任務進行排序，優(yōu)先級高的任務先分配資源調(diào)度執(zhí)行。算法HEFT 中給出了任務優(yōu)先級的計算方式，該優(yōu)先級順序是從出口子任務texit遞歸向上定義，直到該工作流的入口子任務tentry為止，計算方式如（14）所示：

子任務ti在虛擬機Vmq上的最早結(jié)束時間則是最早開始時間與該任務在虛擬機上的實際執(zhí)行時間之和，如（13）所示。

如果一個工作流中有多個入口任務或者多個出口任務，則為其添加一個虛擬的入口任務或者一個虛擬的出口任務，它們的計算量和數(shù)據(jù)傳輸量全為0。對于一個工作流，從該工作流的第一個子任務被調(diào)度執(zhí)行到最后一個子任務執(zhí)行完畢，中間的歷時長度稱為一個工作流的調(diào)度長度，用Makespan 表示。假設提交到系統(tǒng)中的第一個工作流job1的入口任務tentry的tj∈succ(ti)表示tj是ti的直接后繼任務之一，對于texit，其rank(texit)定義為它的平均執(zhí)行時間wexit，而其他子任務的rank(ti)為ti的平均執(zhí)行時間加上它的直接后繼任務中rank 值與平均數(shù)據(jù)傳輸時延之和最大者，通過這種遞歸向上的方式計算出一個工作流中每個子任務的rank 值，然后進行內(nèi)部的優(yōu)先級排序，所以這種方式稱為向上排序方式（upward rank）。

從上述優(yōu)先級計算方式可知，子任務的rank 值表明該任務在整個工作流中的優(yōu)先級，值越大則優(yōu)先級越高，說明該任務在整個工作流中的位置越靠前，應該被盡早調(diào)度執(zhí)行。

但是，HEFT 中的rank(ti) 計算方式比較簡單，對于復雜的工作流，不能完全反映出各子任務在整個工作流中的重要程度。如圖1 中的工作流實例，該工作流由9 個子任務構(gòu)成，圓圈旁邊的粗字體數(shù)字代表任務的平均執(zhí)行時長，箭頭旁的數(shù)字表示子任務之間數(shù)據(jù)傳輸耗時。

假設使用rank(ti) 方法計算得到各子任務的排序值，結(jié)果如表1 所示。

表1 rank 排序結(jié)果

根據(jù)HEFT 調(diào)度算法，圖1 中的工作流子任務調(diào)度 順 序為t1→t3→t4→t2→t5→t6→t8→t7→t9。 從DAG 圖中可以看出，t5的直接后繼任務有3 個(t6,t7,t8)，且t8只和t5有數(shù)據(jù)依賴，所以為了使t8更早被調(diào)度執(zhí)行，t5應該比同一層次中的其他任務(t2,t3,t4)更早的被調(diào)度，但是根據(jù)rank(ti)方法所得的優(yōu)先級順序，t5需要在t2，t3，t4調(diào)度之后才可能被分配資源執(zhí)行，所以這種優(yōu)先級計算方式需要加以改進更好的提高工作流執(zhí)行，從而更好的刻畫出工作流內(nèi)部的結(jié)構(gòu)特性，尤其對于子任務眾多、結(jié)構(gòu)復雜的工作流，合理的安排子任務的調(diào)度順序可以的并行度，降低工作流的Makespan。因此本文將對原來的rank(ti) 計算方式做出改進，以更好的反映出一個工作流內(nèi)部子任務之間的優(yōu)先順序。

從圖1 可以看出，子任務t5較同一層次中的其他子任務更加重要，因為它的直接后繼子任務（t6，t7，t8）都與它有數(shù)據(jù)依賴關系，而t2，t3，t4都只有一個或者兩個直接后繼子任務，因此如果t5沒有執(zhí)行完畢，即使t2，t3，t4已經(jīng)執(zhí)行完畢，后繼子任務也無法開始執(zhí)行，這將很大程度降低整個工作流的并行執(zhí)行效率，延長Makespan，所以t5相對于其他幾個同層的子任務應該需要更高的優(yōu)先級以盡早被調(diào)度執(zhí)行。

從上述分析可知，t5的重要性表現(xiàn)在它有更多的直接后繼子任務，DAG 圖中則表示節(jié)點t5的出度相較于同層中其他節(jié)點更多，所以在調(diào)度前期計算各子任務的rank(ti)時我們將其直接后繼子任務的數(shù)量納入考慮，得到如下新的衡量子任務調(diào)度順序的指標Nrank(ti)，其計算方式如下：

OUT(ti)表示ti的直接后繼子任務的個數(shù)，λ是一個參數(shù)因子，它與具體的應用類型有關系，后文將對其進行實驗討論。

由于工作流執(zhí)行請求是由不同用戶動態(tài)隨機提交至系統(tǒng)的，因此任務調(diào)度器會周期性的對系統(tǒng)中還未調(diào)度的任務進行資源分配并調(diào)度執(zhí)行，所以在一個調(diào)度周期Cycle內(nèi)，可能有很多新的工作流請求進入系統(tǒng)，當系統(tǒng)中資源不充足時，如何決定在該時間段內(nèi)到達的所有工作流的調(diào)度順序就顯得很重要。一些算法按照工作流的截止時間（WDT）安排調(diào)度順序，選擇截止時間靠前的工作流優(yōu)先分配資源，該方式稱為EDF（Earliest Deadline First），這種簡單的方式很容易導致一些工作流不能在其WDT之前執(zhí)行完成。于是其他人又提出了一種衡量任務緊急程度的指標，叫任務寬松度，該指標定義為某時刻一個工作流執(zhí)行結(jié)束到它的WDT之間的時間區(qū)間，Ljobi=Djobi-Ejobi，其中Djobi表示工作流的截止時間，Ejobi表示工作流執(zhí)行結(jié)束時間，Ljobi越小表示工作流jobi越急迫，越應該盡早調(diào)度，當工作流類型差異很大時，這種度量方式就不能很好的工作，可能存在某個工作流的執(zhí)行時長為lenjoba，它遠大于另一個的執(zhí)行時長lenjobb，但是它們距離各自的截止時間Ljoba＞Ljobb，如果按照上述方式則認為jobb更加緊急，從而在資源不充足時優(yōu)先調(diào)度了jobb，這很可能導致joba不能在它的截止時間之前完成，因為它的執(zhí)行時間較長導致不確定性更多。因此本文提出一種相對緊急程度來度量各工作流之間的調(diào)度順序，

其中WETjobi是根據(jù)當前時刻的實際資源狀態(tài)估計得到的，Urgentjobi是(0,1) 之間的一個小數(shù)，它通過工作流最早結(jié)束時間到指定截止時間的這段空余時間段，除以工作流提交的時間到截止時間的這段時間長度（即工作流的最長容忍時間）所得的，數(shù)值越小表示距離工作流的截止時間越近，說明該任務越急迫。

本文借鑒HEFT 算法中的核心思想提出了調(diào)度動態(tài)多工作流的MIHEFT（Move and Insert based Heterogeneous Earliest Finish Time）算法，對不同時刻動態(tài)到達的任務請求，根據(jù)它們的相對緊急程度Urgentjobi制定工作流之間的調(diào)度順序，對工作流內(nèi)部的子任務，則采用改進的Nrank(ti)計算他們的優(yōu)先級，然后制定相應調(diào)度策略。

MIHEFT 算法的偽代碼如下：

Algorithm 1 分別計算出每個工作流子任務的EST和EFT，然后再估計出整個工作流的WET，接著計算出待調(diào)度工作流的Urgent。然后對各工作流分別進行資源預分配和調(diào)度執(zhí)行，如偽代碼11～20 所示。該過程需要先對工作流中的所有子任務計算Nrank 值，然后在內(nèi)部做出優(yōu)先級排序。然后將排序后的子任務預分配到合適的計算資源上，當資源可用時任務將獲得資源執(zhí)行，通過調(diào)用Algorithm 2 為每個子任務尋找合適的資源。

對每個需要分配資源的子任務，首先需要計算該任務在每類虛擬機上的計算時間，然后從最快的虛擬機開始檢查。對于空閑出來的虛擬機，首先檢查該空閑時間槽的長度（Free Time Slot length），如果該空閑時間槽長度大于等于該任務在此虛擬機上的執(zhí)行時長leni，則可以直接將該任務“插入”到此虛擬機任務隊列相應的位置上，如果當前的空閑時間槽長度有限，不足以執(zhí)行完此任務，則需要檢查是否能夠“移動”后續(xù)的子任務加長時間槽。如12～18 行所示，首先對虛擬機任務隊列中該空閑時間槽后面的任務所屬的工作流進行檢查，因為在工作流中，一個子任務延遲length 時長執(zhí)行，也會影響到該子任務的所有后續(xù)子任務，使它們也延后length 執(zhí)行，進而可能使整個工作流的執(zhí)行時長延后length，所以需要檢查延后length 時長后是否會影響到其他工作流在deadline 之前完成，如果對后續(xù)所有子任務所屬的工作流都沒有影響，則可將該任務插入任務隊列的相應位置上，如果檢查后發(fā)現(xiàn)“移動”后續(xù)的子任務會使其他工作流超出截止時間，則該虛擬機空閑時間槽不能滿足此任務的執(zhí)行，繼續(xù)換其他虛擬機執(zhí)行上述相同的操作，直到為此子任務尋找到合適的資源，或者是搜索了整個系統(tǒng)資源后沒有找到合適的資源能夠使該工作流在截止時間內(nèi)完成。

2.2 混合云下多工作流調(diào)度

為了減小系統(tǒng)費用支出，任務調(diào)度器優(yōu)先為工作流在私有云中尋找空閑資源，私有云中使用2.1 小節(jié)中的MIHEFT 算法為工作流分配虛擬機資源。MIHEFT算法首先需要使用Nrank 計算一個工作流中各子任務的優(yōu)先級，計算該優(yōu)先級時需要為子任務在虛擬機上的執(zhí)行時間進行估計。

假設ti在虛擬機Vmn上執(zhí)行，則執(zhí)行時間可以使用式（17）計算：

MIti表示ti的計算量，一般為指令數(shù)，SPvcpun和Nvcpun分別代表所在虛擬機Vmn的虛擬CPU 的計算能力和核心數(shù)。工作流之間如果存在數(shù)據(jù)依賴，即如果tj的執(zhí)行依賴ti給它傳遞數(shù)據(jù)，用dtitj表示兩個任務之間需要傳遞的數(shù)據(jù)量，則數(shù)據(jù)傳輸耗時可以通過（18）計算得到：

ti和tj兩個任務分別在虛擬機Vmn和Vmm上執(zhí)行，虛擬機Vmn和Vmm分別屬于云系統(tǒng)Cpn和Cpm。可以看出兩個子任務之間的數(shù)據(jù)傳輸時間分為3 種情況：當兩個虛擬機分別屬于不同的云環(huán)境中時，數(shù)據(jù)傳輸需要跨越不同的云，因為本文假設云數(shù)據(jù)中心之間的鏈路帶寬相比云內(nèi)部的帶寬要小，所以在云之間傳輸數(shù)據(jù)時瓶頸在云之間的鏈路帶寬，因此大概傳輸時間由需要傳輸?shù)臄?shù)據(jù)量大小與云間可用鏈路帶寬以及虛擬機Vmn在處理數(shù)據(jù)傳輸之前的準備時間開銷LVmn確定；當Vmn和Vmm屬于同一個云環(huán)境下時，此時數(shù)據(jù)鏈路帶寬由虛擬機本身的帶寬所決定，因此數(shù)據(jù)傳輸時間由數(shù)據(jù)量大小和兩個虛擬機帶寬中的較小者決定；當兩個虛擬機處于同一個物理機中時，數(shù)據(jù)可直接在物理機內(nèi)共享，此情況下本文忽略數(shù)據(jù)傳輸時延。

混合云中動態(tài)多工作流調(diào)度算法HCDMW（Hybrid Cloud Dynamic Multiple Workflows Scheduling）偽代碼如下：

調(diào)度器使用Algorithm 3 不斷檢查系統(tǒng)中的任務池，如果任務池中還有工作流未得到調(diào)度，則將未調(diào)度的工作流取出進行調(diào)度，使用Algorithm 1 為這些任務在私有云中預分配資源，如果成功為任務找到合適的資源，則繼續(xù)等待新任務的到來，如果工作流在私有云中不能在截至時間內(nèi)完成，則把該工作流分割為多個子工作流，然后調(diào)度部分子工作流到公有云中執(zhí)行。

一個子任務如果它的直接前驅(qū)任務和直接后繼任務都少于一個，定義這種子任務為簡單子任務（simple task），非簡單子任務則定義為復雜子任務（complex task）。在對工作流分割的時候，從入口子任務開始，采用一種類似深度優(yōu)先搜索的方式，將更多簡單子任務分割開，并調(diào)度至公有云中并行執(zhí)行。

2.3 公有云中調(diào)度

分割后的部分子工作流需要調(diào)度到公有云中執(zhí)行，本文的優(yōu)化目標是費用開銷，任務在公有云中執(zhí)行的費用開銷主要包括計算資源的成本和數(shù)據(jù)傳輸產(chǎn)生的費用，總費用表示如下：

其中，Tc表示該虛擬機計費周期時長，priceVmn表示周期單價，k 表示該虛擬機在之前所產(chǎn)生的計費周期數(shù)量，如果該任務能在已租用過的計費周期內(nèi)完成，則不會產(chǎn)生新的費用，否則需要計算新產(chǎn)生的費用。

在公有云中為子任務分配資源時，為了提高公有云資源利用率，首先在已經(jīng)租用了的虛擬機集合中為任務尋找合適的資源，因為本文公有云計費方式都是按照時間段計費，所以可能存在很多租用了的虛擬機處于空閑狀態(tài)而浪費掉，因此當任務調(diào)度至公有云中時，先在已租用的虛擬機集合中尋找能使子任務在截止時間內(nèi)完成的資源，當無法找到時再租用使該任務能夠按時完成且費用最小的新虛擬機，這樣能減少虛擬機的租用數(shù)量并提高已租用資源的利用率，降低整體成本開銷。

3 實驗與分析

為了驗證HCDMW 算法在混合云環(huán)境下對動態(tài)提交的多工作流調(diào)度執(zhí)行的有效性以及對系統(tǒng)整體費用開銷優(yōu)化的效率，使用WorkflowSim 模擬器[12]，它是基于CloudSim[13]開發(fā)而來的云工作流模擬器，它彌補了CloudSim 不支持工作流調(diào)度的特點，并提供容錯調(diào)度的特性，提供工作流級別的任務聚簇、資源配置和任務調(diào)度等功能。將該算法與Greedy、MLF_ID[9]和HCOC[5]三個算法進行對比。

本實驗將構(gòu)建一個混合云環(huán)境，它由一個小型的私有云和3 個公有云服務構(gòu)成，私有云提供的虛擬機配置如表2 所示，包括三種類型，每一種虛擬機實例提供10 個，由于這些資源是私有的，所以安全級別最高并且可免費使用。

表2 私有云實例類型

3 個公有云中的虛擬機實例類型分別按照Amazon EC2- Asia Pacific（Tokyo）、Amazon EC2-Asia Pacific（Singapore）[14]和Microsoft Azure[15]中的部分實例進行配置。Amazon EC2 在東京（Tokyo）和新加坡（Singapore）區(qū)域以及Microsoft Azure 在上海的實例配置和價格如表3 所示。由于公有云服務商對每個用戶所能使用的虛擬機實例數(shù)量有限制，因此本節(jié)實驗假設兩個使用Amazon EC2 配置的公有云能夠提供的虛擬機實例數(shù)量均為20 個，使用Microsoft Azure 配置的能提供30 個實例。

如表3，Amazon EC2 中的實例，本實驗只選取了計算優(yōu)化型（C3.）實例和存儲優(yōu)化型（i2.）實例，Microsoft Azure 中的實例只選擇了優(yōu)化計算實例類型。按照Amazon EC2 中實例類型配置的虛擬機設置為按小時收費，不足一小時的部分也按一小時計費，Microsoft Azure 實例類型的計費方式則精確到分鐘數(shù)[16]，不足一小時的部分四舍五入到最接近的分鐘數(shù)，實驗環(huán)境中的幾個公有云計費方式本文都按照這些真實的情況設置。

表3 公有云實例類型

假設各公有云和私有云內(nèi)部的實例之間的網(wǎng)絡拓撲結(jié)構(gòu)均是全連接的，即同一個云內(nèi)部的任意兩個虛擬機實例之間都可以直接連通而不用經(jīng)過外部網(wǎng)絡。為了實驗環(huán)境的網(wǎng)絡設置與真實情況相近，現(xiàn)假設將私有云部署在四川大學校園內(nèi)，使用網(wǎng)絡測速工具SpeedTest 測量校內(nèi)與上述各公有云服務商之間的網(wǎng)絡帶寬，為了獲得穩(wěn)定可靠的數(shù)據(jù)，本測量實驗在校內(nèi)多個地點進行且分不同時間段，測量多天后取平均值，測量結(jié)果如表4 所示。然后使用這些真實數(shù)據(jù)設置實驗平臺中私有云和3 個公有云之間的鏈路帶寬。

表4 私有云和公有云之間的鏈路帶寬

除了租用虛擬機實例需要收費，使用公有云另一項大的費用支出是數(shù)據(jù)傳輸產(chǎn)生的開銷。Amazon EC2規(guī)定數(shù)據(jù)傳入和在同一個數(shù)據(jù)中心內(nèi)部的數(shù)據(jù)傳輸是免費的，但是數(shù)據(jù)傳出至互聯(lián)網(wǎng)以及在不同區(qū)域（region）之間的數(shù)據(jù)傳輸是需要付費的，其付費方式如表5 所示。

表5 數(shù)據(jù)傳輸費用

本小節(jié)實驗將使用工作流生成器分別合成100 和200 個工作流，估計各工作流在上述各種虛擬機實例下的執(zhí)行時長，然后取平均值作為對應工作流的標準執(zhí)行時長。設置每個工作流的截止時間時，取其標準執(zhí)行時長與截止時間因子θ的乘積，其中θ服從一個方差為0.2 的高斯分布，該分布的均值μ將作為實驗的變量參數(shù)。對每一個生成的工作流，根據(jù)文獻[10]為其所有子任務分別設置安全需求等級，該安全等級是滿足條件的隨機值，同時也需要為實驗模擬器中的所有虛擬機實例賦予安全級別。最后將生成的工作流動態(tài)提交到實驗模擬器中，這些工作流的提交過程也符合泊松分布。

實驗分別對比4 個算法執(zhí)行所有工作流需要的總時長，執(zhí)行完畢后系統(tǒng)總費用開銷以及私有云資源的利用效率。

3.1 執(zhí)行時間

圖2 和3 分別描述了提交100 和200 個工作流后，使用4 種不同的調(diào)度算法最終的執(zhí)行總時長。從兩圖中可以看出，隨著參數(shù)μ變大，使用不同調(diào)度算法的執(zhí)行總時長均呈現(xiàn)變大的趨勢，因為參數(shù)μ變大意味著工作流整體截止時間變長，因此有更多工作流能夠在本地私有云中執(zhí)行，但私有云中的資源相對有限且性能沒有公有云實例強大，所以任務的總體執(zhí)行時長會增加。使用Greedy 算法和HCOC 算法時，工作流執(zhí)行時間比其他兩者長，因為它們沒有充分利用私有云中的資源，相比其他兩種算法，它們將更多工作流調(diào)度到公有云中執(zhí)行。

圖2 100個工作流調(diào)度執(zhí)行總時長

由于在公有云中執(zhí)行前需要將大量基礎數(shù)據(jù)傳輸?shù)焦性?，所以會使整體時長增加不少。

使用本文的HCDMW 算法執(zhí)行時長較短，因為它能夠充分利用私有云資源，減少了私有云中虛擬機等待的空閑時間槽，提高了資源利用效率。當有工作流在私有云中不能在截止時間內(nèi)完成時，HCDMW 算法也并非將整個工作流完全調(diào)度到公有云中執(zhí)行，而是采用工作流分割的方式，在滿足工作流需求時將盡可能少的子工作流調(diào)度到公有云中并行執(zhí)行，從而縮短了整體執(zhí)行時間。

圖3 200個工作流調(diào)度執(zhí)行總時長

3.2 執(zhí)行費用

圖4 和圖5 分別描述了使用4 種算法調(diào)度時，執(zhí)行完100 個工作流和200 個工作流后系統(tǒng)產(chǎn)生的總費用開銷?？梢钥吹诫S著μ變大，系統(tǒng)總費用支出均在減小，因為隨著μ變大工作流整體的可容忍時長（提交時間到截止時間）增加，更少的工作流被調(diào)度到公有云執(zhí)行，因此系統(tǒng)費用都會變小。其中Greedy 算法始終高于其他算法，因為Greedy 算法優(yōu)先為工作流選擇性能最高的虛擬機實例，這些虛擬機的價格也相對較高，因而執(zhí)行費用最高。本文的HCDMW 算法相比其他3 個算法要少很多，因為當工作流需要調(diào)度到公有云中執(zhí)行時，HCDMW 算法會考慮多個成本因素，將工作流合理分割為多個子工作流，然后將部分子工作流調(diào)度到公有云中執(zhí)行，且在公有云中執(zhí)行時，也是優(yōu)先使用已租賃過的虛擬機實例，其次選擇滿足要求且便宜的實例，這些措施都進一步提高了已租用公有云資源的利用效率，從而使系統(tǒng)總費用開銷大大降低。

圖4 100 個工作流調(diào)度執(zhí)行費用開銷

圖5 200個工作流調(diào)度執(zhí)行費用開銷

3.3 資源利用率

圖6 和圖7 分別描述了使用4 種不同算法調(diào)度執(zhí)行100 和200 個工作流時，混合云系統(tǒng)中私有云資源的利用率。當μ變大后，即工作流整體的截止時長變大，意味著工作流提交到系統(tǒng)后預留了更長的執(zhí)行時間，容忍時長增加，更多的工作流可以在本地私有云中執(zhí)行而無需調(diào)度到公有云中，所以從圖中可以看出，隨μ變大私有云資源利用率總體呈現(xiàn)變大趨勢。

圖6 100個工作流私有云資源利用率

圖7 200個工作流私有云資源利用率

從圖6-圖7 可以看出，當參數(shù)μ取2 時，使用4 種不同算法的私有云資源利用率都不高，因為任務的截止時間都比較緊迫，因此需要調(diào)度很多任務到公有云中執(zhí)行，導致私有云資源利用率較低。使用HCOC 算法時，大部分時間的利用率都比其他算法低，因為該算法會將整個工作流調(diào)度到公有云中并且尋找最經(jīng)濟的資源，導致任務的執(zhí)行時間變得很長，從而讓私有云資源被浪費更多。本文的HCDMW 算法相比MLF_ID 算法在資源利用率上要好一些，因為HCDMW 算法將不能在截止時間內(nèi)完成的工作流進行分割，然后只調(diào)度部分任務到公有云中，保證私有云不會因此而閑置等待，并且私有云中的MIHEFT 調(diào)度算法能夠充分利用資源的空閑時間槽，進一步減少了私有云資源的浪費，提高了利用率。該實驗結(jié)果也印證了執(zhí)行費用的實驗結(jié)果，因為HCDMW 算法能夠充分利用免費的私有云資源，所以才使系統(tǒng)整體費用開銷得到優(yōu)化。

4 結(jié)語

本文以混合云環(huán)境下動態(tài)多工作流調(diào)度執(zhí)行問題為研究背景，為了既減小系統(tǒng)整體費用支出，又能滿足工作流的截止時間約束、安全隱私需求等，提出了針對混合云中動態(tài)多工作流調(diào)度執(zhí)行的HCDMW 算法，有效減少了系統(tǒng)的費用開銷。但本文算法還存在一些問題需要進行更深入的研究和改進，在后續(xù)工作中從以下幾個方面進行：

（1）慮資源失效的可能性，當資源失效后能夠調(diào)度任務到其他資源上執(zhí)行避免整個工作流執(zhí)行失敗，增強調(diào)度系統(tǒng)的魯棒性，使其能夠更加貼近真實的云環(huán)境；

（2）公有云中還具有一類資源具有競價模型，即價格是動態(tài)變化的，本文后續(xù)工作將考慮加入該類資源模型，以更有效地優(yōu)化系統(tǒng)的費用。