混合云環境中調度執行多工作流費用優化算法

盧莉，李亮亮，黎紅友

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

0 引言

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

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

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

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

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

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

（1）對混合云中多工作流調度問題，提出了混合云環境中動態多工作流調度算法，優先將工作流任務調度到私有云中執行；采用多約束工作流分割機制，對無法在私有云中完成的任務進行分割形成子工作流。

（2）針對在私有云中調度執行的工作流，提出了一種基于表啟發式算法改進而來的多工作流調度算法，提高私有云資源的利用率，減少公有云資源的使用量，從而優化混合云系統的費用支出。

1 混合云中多工作流調度模型

1.1 任務模型

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

圖1 工作流實例

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

1.2 資源模型

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

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

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

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

1.3 問題描述

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

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

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

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

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

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

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

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

數據通信產生的費用為：

其中Dataouti表示這段時間內公有云Cpi傳輸到私有云中的數據量，PriceDatai表示數據通信單價。

因此這段時間內總的費用開銷可表示為：

綜上，在混合云環境下調度執行動態多工作流可用如下目標函數和限制條件表示：

2 混合云下多工作流調度策略

為了優化整個系統的費用支出，優先調度工作流到私有云中執行，因此本節將首先提出一個私有云中的調度算法用于工作流在私有云中的調度執行，提高私有云資源利用效率。

2.1 改進的表啟發式多工作流調度算法

由于系統中工作流請求和執行都是動態進行著，所以調度系統具有一定的實時性需求，本文根據異構最早完成時間（Heterogeneous Earliest Finish Time，HEFT）算法[11]提出一種適合本文場景的啟發式調度算法。

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

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

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

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

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

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

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

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

表1 rank 排序結果

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

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

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

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

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

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

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

MIHEFT 算法的偽代碼如下：

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

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

2.2 混合云下多工作流調度

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

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

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

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

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

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

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

2.3 公有云中調度

分割后的部分子工作流需要調度到公有云中執行，本文的優化目標是費用開銷，任務在公有云中執行的費用開銷主要包括計算資源的成本和數據傳輸產生的費用，總費用表示如下：

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

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

3 實驗與分析

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

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

表2 私有云實例類型

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

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

表3 公有云實例類型

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

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

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

表5 數據傳輸費用

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

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

3.1 執行時間

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

圖2 100個工作流調度執行總時長

由于在公有云中執行前需要將大量基礎數據傳輸到公有云，所以會使整體時長增加不少。

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

圖3 200個工作流調度執行總時長

3.2 執行費用

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

圖4 100 個工作流調度執行費用開銷

圖5 200個工作流調度執行費用開銷

3.3 資源利用率

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

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

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

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

4 結語

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

（1）慮資源失效的可能性，當資源失效后能夠調度任務到其他資源上執行避免整個工作流執行失敗，增強調度系統的魯棒性，使其能夠更加貼近真實的云環境；

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