盧莉，李亮亮，黎紅友

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

0 引言

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

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

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

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

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

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

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

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

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

1.1 任務(wù)模型

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

圖1 工作流實(shí)例

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

1.2 資源模型

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

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

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

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

1.3 問(wèn)題描述

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

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

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

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

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

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

其中SCtlvmi表示子任務(wù)tl在虛擬機(jī)vmi上執(zhí)行時(shí)產(chǎn)生的安全服務(wù)時(shí)間開(kāi)銷(xiāo)，當(dāng)子任務(wù)tl在虛擬機(jī)vmi上執(zhí)行時(shí)，V為1，否則為0。

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

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

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

因此這段時(shí)間內(nèi)總的費(fèi)用開(kāi)銷(xiāo)可表示為：

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

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

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

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

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

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

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

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

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

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

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

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

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

表1 rank 排序結(jié)果

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

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

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

OUT(ti)表示ti的直接后繼子任務(wù)的個(gè)數(shù)，λ是一個(gè)參數(shù)因子，它與具體的應(yīng)用類(lèi)型有關(guān)系，后文將對(duì)其進(jìn)行實(shí)驗(yàn)討論。

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

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

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

MIHEFT 算法的偽代碼如下：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 實(shí)驗(yàn)與分析

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

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

表2 私有云實(shí)例類(lèi)型

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

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

表3 公有云實(shí)例類(lèi)型

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

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

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

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

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

實(shí)驗(yàn)分別對(duì)比4 個(gè)算法執(zhí)行所有工作流需要的總時(shí)長(zhǎng)，執(zhí)行完畢后系統(tǒng)總費(fèi)用開(kāi)銷(xiāo)以及私有云資源的利用效率。

3.1 執(zhí)行時(shí)間

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

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

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

使用本文的HCDMW 算法執(zhí)行時(shí)長(zhǎng)較短，因?yàn)樗軌虺浞掷盟接性瀑Y源，減少了私有云中虛擬機(jī)等待的空閑時(shí)間槽，提高了資源利用效率。當(dāng)有工作流在私有云中不能在截止時(shí)間內(nèi)完成時(shí)，HCDMW 算法也并非將整個(gè)工作流完全調(diào)度到公有云中執(zhí)行，而是采用工作流分割的方式，在滿(mǎn)足工作流需求時(shí)將盡可能少的子工作流調(diào)度到公有云中并行執(zhí)行，從而縮短了整體執(zhí)行時(shí)間。

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

3.2 執(zhí)行費(fèi)用

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

圖4 100 個(gè)工作流調(diào)度執(zhí)行費(fèi)用開(kāi)銷(xiāo)

圖5 200個(gè)工作流調(diào)度執(zhí)行費(fèi)用開(kāi)銷(xiāo)

3.3 資源利用率

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

圖6 100個(gè)工作流私有云資源利用率

圖7 200個(gè)工作流私有云資源利用率

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

4 結(jié)語(yǔ)

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

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

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