基于資源分組的多約束云工作流調(diào)度算法

陳愛國(guó)，王 玲，任金勝，羅光春

(電子科技大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院 成都 611731)

基于資源分組的多約束云工作流調(diào)度算法

陳愛國(guó)，王 玲，任金勝，羅光春

(電子科技大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院 成都 611731)

已有的云工作流調(diào)度算法采用全局搜索方式進(jìn)行資源選取，存在計(jì)算成本高、對(duì)大規(guī)模云系統(tǒng)適應(yīng)性差的問題。該文提出了基于資源分組的多約束云工作流調(diào)度算法，采用有向無環(huán)圖的方法，對(duì)云工作流中的多任務(wù)之間的執(zhí)行順序和數(shù)據(jù)交換等屬性進(jìn)行量化建模；使用模糊聚類方法實(shí)現(xiàn)基于資源多維特征的分組處理，降低工作流任務(wù)到資源匹配過程中的搜索空間；并引入執(zhí)行時(shí)間和成本預(yù)算約束，將工作流的任務(wù)調(diào)度問題轉(zhuǎn)化為有約束條件的極小極大問題進(jìn)行快速求解。仿真測(cè)試表明，該算法顯著降低了任務(wù)執(zhí)行完成時(shí)間和成本。

云計(jì)算; 云工作流; 模糊聚類; 資源分配; 調(diào)度算法

云計(jì)算模式中，云數(shù)據(jù)中心具有大規(guī)模軟硬件資源，通過網(wǎng)絡(luò)服務(wù)的方式向多用戶提供強(qiáng)大的計(jì)算能力。因此，云計(jì)算平臺(tái)中面臨大量動(dòng)態(tài)的計(jì)算任務(wù)請(qǐng)求。這些特點(diǎn)使得云計(jì)算環(huán)境中的任務(wù)調(diào)度比傳統(tǒng)分布式環(huán)境中的任務(wù)調(diào)度要面臨更多更復(fù)雜的問題[1]。特別是隨著網(wǎng)絡(luò)功能虛擬化(network function virtualization, NFV)等技術(shù)的發(fā)展，云環(huán)境中的工作流任務(wù)越來越多，其調(diào)度成為云計(jì)算領(lǐng)域的一個(gè)研究熱點(diǎn)[2-3]。并且，云環(huán)境中用戶按資源使用進(jìn)行付費(fèi)，如何權(quán)衡性能和成本成為一個(gè)普遍問題。越來越多的混合云環(huán)境下存在更復(fù)雜的資源使用成本和性能規(guī)格。這些都給云工作流調(diào)度提出了更多的挑戰(zhàn)[3]。典型的需求場(chǎng)景如公安系統(tǒng)需要對(duì)跨地域分布存儲(chǔ)的多源數(shù)據(jù)進(jìn)行多層關(guān)聯(lián)分析。為了提高計(jì)算效率，完整業(yè)務(wù)被設(shè)計(jì)成多個(gè)計(jì)算步驟，構(gòu)成了工作流任務(wù)。各個(gè)任務(wù)節(jié)點(diǎn)之間有先后關(guān)系和數(shù)據(jù)交換，通常單個(gè)任務(wù)節(jié)點(diǎn)還需要加載存量歷史數(shù)據(jù)。在可以實(shí)現(xiàn)就近資源征用的基礎(chǔ)上，如何從大規(guī)模資源中為完整工作流計(jì)算任務(wù)選擇合適的資源、降低整體計(jì)算成本并提高響應(yīng)時(shí)間具有重要的應(yīng)用價(jià)值。

本文主要針對(duì)云工作流調(diào)度中如何實(shí)現(xiàn)時(shí)間和成本的約束問題開展算法研究。滿足時(shí)間約束是指確保工作流在用戶指定截止時(shí)間前完成，成本約束則要求工作流的執(zhí)行要在一定的成本預(yù)算范圍內(nèi)。造成任務(wù)整體調(diào)度時(shí)間和成本提高的原因多種多樣，包括工作流中多任務(wù)的調(diào)度順序、資源規(guī)模以及算法本身的執(zhí)行效率等。針對(duì)已有的工作流調(diào)度算法存在的搜索成本高等問題，本文提出了基于資源分組的多約束云工作流調(diào)度算法，利用模糊聚類的方法對(duì)云資源進(jìn)行預(yù)處理，并將列表調(diào)度和任務(wù)調(diào)度機(jī)制相結(jié)合，在為任務(wù)搜索合適的資源時(shí)，降低搜索成本。同時(shí)為了實(shí)現(xiàn)任務(wù)調(diào)度過程中最小化完成時(shí)間和最小化執(zhí)行成本這兩個(gè)目標(biāo)，采用有向無環(huán)圖方法求解資源分配策略。該算法在資源聚類的基礎(chǔ)上對(duì)工作流中的任務(wù)進(jìn)行調(diào)度，考慮任務(wù)執(zhí)行的時(shí)間與成本預(yù)算，有效地降低任務(wù)執(zhí)行時(shí)間和執(zhí)行成本，實(shí)現(xiàn)了最小化完成時(shí)間和最小化執(zhí)行成本兩個(gè)目標(biāo)。

1 相關(guān)研究

關(guān)于云調(diào)度算法的研究有很多，包括基于列表的調(diào)度策略的最小完成時(shí)間算法、Sufferage算法、Min-min算法和Max-min算法等算法[4-6]。典型的處理器關(guān)鍵路徑算法(critical path on processor, CPOP)[7]和異構(gòu)最早完成時(shí)間算法(heterogeneous earliest finish time, HEFT)[8]都是基于列表的啟發(fā)式算法，其中HEFT就完成時(shí)間而言優(yōu)于上述所有的算法。HEFT算法對(duì)任務(wù)劃分優(yōu)先級(jí)，對(duì)優(yōu)先級(jí)較高的優(yōu)先為其分配處理資源，在任務(wù)調(diào)度最小化最早完成時(shí)間上取得了良好的效果。但是，HEFT算法在任務(wù)調(diào)度過程中并沒有考慮成本的因素。

文獻(xiàn)[9]詳細(xì)描述了云計(jì)算環(huán)境下任務(wù)調(diào)度中成本和截止時(shí)間約束的重要性，并提出了相應(yīng)的算法。但是，所提出的資源模型和算法僅針對(duì)同類資源。文獻(xiàn)[10]提出了云環(huán)境下分段式工作流調(diào)度算法：一階段算法IC-PCP和兩階段算法IC-PCPD2。這兩個(gè)階段算法在調(diào)度大的工作流時(shí)都有一個(gè)多項(xiàng)式時(shí)間復(fù)雜度，并在最后期限約束下最小化工作流執(zhí)行成本。文獻(xiàn)[11]也提出了一個(gè)算法集來調(diào)度截止時(shí)間約束的任務(wù)以最小化成本執(zhí)行，但是這同樣只最小化了一個(gè)目標(biāo)。所有這些啟發(fā)式算法的主要問題是，他們中大多數(shù)解決的是計(jì)算環(huán)境中的單目標(biāo)優(yōu)化的問題，不能同時(shí)針對(duì)計(jì)算成本和執(zhí)行時(shí)間進(jìn)行優(yōu)化。

文獻(xiàn)[12]提出了BHEFT算法，充分考慮了用戶對(duì)成本預(yù)算和截止時(shí)間的要求。但在進(jìn)行資源分配時(shí)，采用全局資源搜索方法造成了過高的時(shí)間成本和額外計(jì)算成本。特別是當(dāng)云計(jì)算環(huán)境資源規(guī)模較大時(shí)，全局搜索計(jì)算的搜索空間也在攀升。其他研究成果也存在類似問題。

如何在為任務(wù)分配合適資源的同時(shí)，降低資源搜索空間，節(jié)約搜索時(shí)間成本和執(zhí)行成本，是工作流調(diào)度中一個(gè)需要進(jìn)一步研究的問題?；谏鲜龇治?，為了解決在任務(wù)調(diào)度之初由于搜索空間比較大造成的搜索時(shí)間和執(zhí)行成本的問題，本文提出利用模糊聚類的方法對(duì)云資源根據(jù)資源特征屬性進(jìn)行分類的策略。

2 問題模型

云工作流是由一系列關(guān)聯(lián)的任務(wù)構(gòu)成的，將工作流調(diào)度轉(zhuǎn)換成具有依賴關(guān)系的任務(wù)拓?fù)?，而工作流調(diào)度的核心就是計(jì)算任務(wù)到資源的映射策略。調(diào)度目標(biāo)主要關(guān)注兩方面：1) 從任務(wù)提交到任務(wù)執(zhí)行完成所花費(fèi)的時(shí)間最小化，即最小化完成時(shí)間；2) 從任務(wù)提交到任務(wù)執(zhí)行完成所花費(fèi)的成本最小化，即最小化執(zhí)行成本。本文著重討論基于資源預(yù)處理的任務(wù)調(diào)度模型。假設(shè)向云計(jì)算系統(tǒng)提交一個(gè)工作流WF，其包含n個(gè)任務(wù)，系統(tǒng)內(nèi)存在m個(gè)空閑資源。其中，對(duì)于提交的n個(gè)任務(wù)，用戶規(guī)定了成本預(yù)算B和任務(wù)執(zhí)行完成時(shí)間限制D。

工作流任務(wù)調(diào)度問題可以描述為：將n個(gè)任務(wù)分配到m個(gè)資源調(diào)度執(zhí)行，并確保在時(shí)間限制D范圍內(nèi)取得任務(wù)的最小完成時(shí)間，在預(yù)算B范圍內(nèi)取得任務(wù)的最小執(zhí)行成本。若預(yù)測(cè)任務(wù)執(zhí)行完成后，最小完成時(shí)間大于時(shí)間限制D或最小執(zhí)行成本大于預(yù)算B，則任務(wù)調(diào)度失敗。如何將任務(wù)分配給恰當(dāng)?shù)馁Y源，以取得執(zhí)行時(shí)間和執(zhí)行成本的最小化，問題定義如下。

定義 1 用戶提交的包含n個(gè)任務(wù)的工作流WF，用有向無環(huán)圖(direct acyclic graph, DAG)描述為：WF=(T, E)，其中T={t1, t2,…,tn}代表任務(wù)集合，集合中有n個(gè)任務(wù)。E={eij}為邊集，代表任務(wù)之間的依賴關(guān)系，若eij=0代表任務(wù)ti和tj之間并不存在執(zhí)行順序的先后關(guān)系；若eij≠0代表任務(wù)ti執(zhí)行完成后，任務(wù)tj才可以執(zhí)行，eij的值代表了任務(wù)ti和tj之間需要傳輸?shù)臄?shù)據(jù)量。典型工作流具有單一的首節(jié)點(diǎn)t1和尾節(jié)點(diǎn)tn，任務(wù)t2～tn?1可泛化為多個(gè)任務(wù)路徑P={p1, p2,…,pL}。

定義 2 云計(jì)算系統(tǒng)中存在的可供調(diào)度的資源用R={r1, r2,…,rm}表示，m為資源的總數(shù)。

定義 3 矩陣W=TR是任務(wù)執(zhí)行時(shí)間代價(jià)矩陣，其中wij代表任務(wù)ti在資源rj上執(zhí)行花費(fèi)的時(shí)間。

定義 4 矩陣C=R2是衡量?jī)蓚€(gè)資源之間的通信能力即數(shù)據(jù)傳輸能力的矩陣，其中cij代表資源ir和資源rj之間的傳輸帶寬，即數(shù)據(jù)傳輸能力。

定義 5 任務(wù)資源分配策略定義為X。對(duì)于給定的任務(wù)集合T和資源集合R，分配策略為：

式中，xij取值為0或1，表示是否將任務(wù)ti分配給資源rj。所有任務(wù)的總執(zhí)行時(shí)間定義為：

式中，xijwij表示任務(wù)ti分配給資源rj的執(zhí)行時(shí)間。所有任務(wù)的總執(zhí)行成本cost為：

式中，pricej表示分配給特定資源rj的單位時(shí)間定價(jià)。

根據(jù)任務(wù)分配策略X，將任務(wù)ti分配給資源rk執(zhí)行，任務(wù)tj分配給資源lr執(zhí)行。對(duì)于所有的任務(wù)，其總數(shù)據(jù)傳輸時(shí)間為：

根據(jù)式(2)和式(4)，可以得出所有任務(wù)執(zhí)行完成時(shí)間為：

式中，S表示資源搜索時(shí)間。

根據(jù)以上分析，任務(wù)資源分配模型以數(shù)學(xué)的形式表示為：對(duì)于給定的任務(wù)集合T和資源集合R，如何找到一個(gè)最優(yōu)的分配策略，使得任務(wù)的完成時(shí)間和執(zhí)行成本最小。根據(jù)式(3)和式(5)，目標(biāo)函數(shù)定義為：

定義式(3)～式(6)的目的是為了準(zhǔn)確刻畫成本，用于最小化求解，其約束條件為：

約束條件表明，在成本最小化、完成時(shí)間最小化的同時(shí)，不能超過預(yù)算限制和時(shí)間限制。根據(jù)式(3)、式(5)和式(6)，影響優(yōu)化目標(biāo)的主要因素是式(5)中的資源搜索時(shí)間S、所有任務(wù)的執(zhí)行完成時(shí)間TET和所有的任務(wù)的總數(shù)據(jù)傳輸時(shí)間DTT受調(diào)度算法本身的影響。因此如何減小S、TET、DTT是調(diào)度算法的首要考慮因素。

3 基于資源分組工作流調(diào)度算法

針對(duì)已有算法的不足，本算法首先進(jìn)行資源分組預(yù)處理，通過選擇最優(yōu)分組解決全局資源搜索成本的問題。并定義了時(shí)間和成本約束量化模型，最小化任務(wù)執(zhí)行時(shí)間和成本。

3.1 資源分組處理

分組處理將大量各種類型的云計(jì)算資源根據(jù)其特征和對(duì)任務(wù)的支持能力劃分為若干小類，以解決資源搜索空間大而帶來的效率低下、資源浪費(fèi)、時(shí)間復(fù)雜度高等問題。

模糊聚類主要是對(duì)資源特征矩陣進(jìn)行處理。完整的模糊聚類過程首先需要采集云計(jì)算資源的特征數(shù)據(jù)，根據(jù)資源特征屬性，建立每個(gè)資源的多重屬性特征初始矩陣。由于每個(gè)資源的特征屬性的數(shù)量級(jí)與量綱存在差異，需要對(duì)初始數(shù)據(jù)矩陣進(jìn)行適當(dāng)?shù)淖儞Q，即數(shù)據(jù)歸一化操作，將標(biāo)準(zhǔn)矩陣中的值限定在0～1之間，方便后續(xù)的聚類劃分。

本文使用S={s1, s2,…,sM}表示需要被聚類的資源集合，其中M表示資源個(gè)數(shù)；使用向量S′(si)={si1,si2,…,siV}(i=1,2,…,M)表示第i個(gè)資源的特征屬性，其中sij表示第i個(gè)資源在第j個(gè)特征屬性上的度量值，V表示特征屬性個(gè)數(shù)。

特征屬性是指面向任務(wù)處理能力的云計(jì)算資源特征或性質(zhì)，主要包括計(jì)算能力、傳輸能力、內(nèi)存大小、存儲(chǔ)能力、網(wǎng)絡(luò)位置、連接數(shù)等特征。確定特征屬性后，再依據(jù)特征屬性對(duì)云計(jì)算資源進(jìn)行聚類，將具有相似特性的資源歸到一起。針對(duì)不同的任務(wù)需求，特征屬性的選擇會(huì)有所不同。結(jié)合混合云場(chǎng)景中的典型業(yè)務(wù)場(chǎng)景，本算法考慮下面4個(gè)特征屬性：

1) c1代表計(jì)算能力屬性，表示資源的平均計(jì)算能力，即資源節(jié)點(diǎn)的計(jì)算性能。性能的高低直接關(guān)系到任務(wù)的執(zhí)行時(shí)間，對(duì)任務(wù)調(diào)度過程中的時(shí)間成本有著至關(guān)重要的影響。

2) c2代表計(jì)算節(jié)點(diǎn)間的數(shù)據(jù)傳輸能力屬性，表示云資源節(jié)點(diǎn)間的聯(lián)通邊權(quán)值的平均值，即連接鏈路的通信能力的平均值，描述了資源與資源間的數(shù)據(jù)傳輸性能，數(shù)據(jù)傳輸性能的高低直接影響數(shù)據(jù)傳輸?shù)臅r(shí)間成本。

3) c3表示計(jì)算節(jié)點(diǎn)與歷史數(shù)據(jù)資源節(jié)點(diǎn)間的數(shù)據(jù)傳輸能力屬性。在跨地域的混合云中，數(shù)據(jù)資源節(jié)點(diǎn)到不同混合云計(jì)算資源節(jié)點(diǎn)間的數(shù)據(jù)傳輸能力差異交大。該能力主要體現(xiàn)為對(duì)歷史數(shù)據(jù)的傳輸加載時(shí)間需求。

4) c4代表連接數(shù)屬性，表示連接到該資源節(jié)點(diǎn)的其他資源的數(shù)目。分派到該資源的任務(wù)可以與其他多個(gè)資源的任務(wù)進(jìn)行數(shù)據(jù)傳輸。

模糊聚類資源分組處理分為3個(gè)步驟：

1) 數(shù)據(jù)標(biāo)準(zhǔn)化處理

此步驟主要是消除數(shù)據(jù)量綱差異。對(duì)于原始數(shù)據(jù)表S′，使用平均值和標(biāo)準(zhǔn)差來處理目標(biāo)系統(tǒng)中的數(shù)據(jù)從而獲得標(biāo)準(zhǔn)化數(shù)據(jù)，每個(gè)數(shù)據(jù)的標(biāo)準(zhǔn)化值為：

式中，ck代表原始數(shù)據(jù)中第k個(gè)特征向量，是ck的平均值；Sck是ck的標(biāo)準(zhǔn)化方差。由于標(biāo)準(zhǔn)化值pik′并非全屬于[0,1]，采用極差標(biāo)準(zhǔn)化方法將pik′轉(zhuǎn)化得到pik′。極差標(biāo)準(zhǔn)化方法定義如下：

式中， pk′min是最小值； pk′max是p1′k,p2′k,…,p′Nk的最大值。

2) 模糊矩陣實(shí)現(xiàn)

此步驟的主要目的是便于后續(xù)根據(jù)云計(jì)算資源特征屬性的相似性對(duì)資源進(jìn)行聚類。利用指數(shù)相似系數(shù)法可以計(jì)算處理單元S={s1, s2,…,sN}的模糊相似關(guān)系Rs。經(jīng)過測(cè)試，指數(shù)相似系數(shù)法具有更好的效果，計(jì)算方法如下：

3) 聚類信息評(píng)估

采用基于割集的聚類方法，可以得到一組聚類結(jié)果，用CLUSTER={CL1,CL2,…,CLK}表示，CLj表示第j個(gè)資源群組。每個(gè)群組的整體性能表示為：

式中，w代表群組中處理單元的個(gè)數(shù)；iα代表處理單元第i個(gè)特征向量的權(quán)重，它的值一般可以通過歷史數(shù)據(jù)或經(jīng)驗(yàn)獲得。通過對(duì)每個(gè)群組的整體性能的計(jì)算，根據(jù)性能高低重新排序。任務(wù)調(diào)度時(shí)，優(yōu)選排序靠前的資源群組。

3.2 時(shí)間成本約束定義

在問題模型描述和資源屬性建模的基礎(chǔ)上，進(jìn)一步引入工作流的任務(wù)時(shí)間約束和成本預(yù)算約束量化方法，并通過算法模型實(shí)現(xiàn)完成時(shí)間和執(zhí)行成本這兩個(gè)目標(biāo)的權(quán)衡優(yōu)化。

3.2.1 執(zhí)行時(shí)間約束

用戶提交工作流給云平臺(tái)執(zhí)行，并指定期望的總體執(zhí)行完成時(shí)間D。在調(diào)度過程中，調(diào)度粒度落到工作流中的任務(wù)層面，需要將執(zhí)行時(shí)間約束加入到任務(wù)調(diào)度選擇條件中。為此，定義以下3個(gè)變量：

1) 工作流剩余執(zhí)行時(shí)間要求SWD：描述工作流中尚未執(zhí)行任務(wù)的執(zhí)行時(shí)間要求。

2) 執(zhí)行時(shí)間適應(yīng)因子DAF：用于調(diào)整當(dāng)前任務(wù)的執(zhí)行時(shí)間限制。

3) 當(dāng)前任務(wù)執(zhí)行時(shí)間CTD：描述當(dāng)前任務(wù)的執(zhí)行時(shí)間限制。

對(duì)于任務(wù)ti，其剩余截止時(shí)間為：

任務(wù)的執(zhí)行時(shí)間ET(tk)根據(jù)資源分配策略X計(jì)算如下：

根據(jù)式(13)，任務(wù)ti的截止時(shí)間適應(yīng)因子為：

任務(wù)tk的平均執(zhí)行時(shí)間為任務(wù)tk在所有資源上的執(zhí)行時(shí)間的平均值：

根據(jù)式(12)～式(15)，ti的當(dāng)前任務(wù)執(zhí)行時(shí)間為：

3.2.2 執(zhí)行成本約束

前面問題模型描述中約定工作流規(guī)定的成本預(yù)算為B。根據(jù)對(duì)工作流執(zhí)行總成本的要求，需要將成本約束加入到任務(wù)選擇條件中。為此，引入以下3個(gè)變量。

1) 剩余成本預(yù)算SWB：描述未執(zhí)行的任務(wù)的成本限制。

2) 成本預(yù)算適應(yīng)因子BAF：用于調(diào)整當(dāng)前任務(wù)的預(yù)算限制。

3) 當(dāng)前任務(wù)成本預(yù)算CTB：描述當(dāng)前任務(wù)的執(zhí)行成本限制。

對(duì)于任務(wù)ti，其剩余成本預(yù)算為：

執(zhí)行成本EC(tk)為：

任務(wù)ti的成本預(yù)算適應(yīng)因子為：

任務(wù)tk的平均執(zhí)行成本為任務(wù)tk在所有資源上的執(zhí)行成本的平均值：

根據(jù)式(17)～式(20)，任務(wù)ti的當(dāng)前任務(wù)預(yù)算為：

3.2.3 約束條件引入

基于任務(wù)ti對(duì)執(zhí)行時(shí)間和成本預(yù)算的要求，構(gòu)建可為任務(wù)ti分配的資源集合BSi。通過預(yù)測(cè)任務(wù)ti在資源rp所需要的執(zhí)行成本與執(zhí)行時(shí)間是否滿足條件EC(i, p)≤CTBi和ET(i, p)≤CTDi，將滿足條件的資源保留下來，構(gòu)成可為任務(wù)ti分配的資源集合CLj,i，表示為：

集合BSi表示所有CLj,i中的資源所構(gòu)成的可分配資源集合：

在進(jìn)行任務(wù)調(diào)度時(shí)，從BSi中選擇合適的資源分配給任務(wù)。

3.3 調(diào)度過程

3.3.1 調(diào)度準(zhǔn)備

調(diào)度準(zhǔn)備階段的工作主要是為任務(wù)級(jí)調(diào)度做準(zhǔn)備。包含根據(jù)優(yōu)先級(jí)構(gòu)造任務(wù)列表、資源聚類、依據(jù)工作流總體時(shí)間和成本約束量化任務(wù)粒度的時(shí)間和成本約束、構(gòu)造可分配資源集合等操作。這些操作節(jié)省了搜索資源空間所花費(fèi)的時(shí)間，同時(shí)也降低了后續(xù)任務(wù)調(diào)度執(zhí)行的時(shí)間成本和預(yù)算成本。

3.3.2 任務(wù)-資源求解與分配

基于3.1和3.2節(jié)描述的算法模型，優(yōu)化求解任務(wù)-資源分配策略。引入時(shí)間成本平衡因子，以平衡用戶對(duì)時(shí)間和成本的要求定義如下分配規(guī)則。

1) 如果BSi≠?，使得最小的資源優(yōu)先被選擇，即優(yōu)化函數(shù)：式中，α是時(shí)間成本平衡因子，取值范圍為[0,1]，代表了用戶偏好的執(zhí)行時(shí)間和執(zhí)行成本敏感度。如果對(duì)于任務(wù)ti的多個(gè)備選資源節(jié)點(diǎn)，度量值iF相等，則優(yōu)選任務(wù)ti前序任務(wù)所在的資源節(jié)點(diǎn)。

2) 如果BSi=?且SWB≥0，所有的可用資源只要滿足式(24)，均可以被選擇。因?yàn)榧词咕植抗?jié)點(diǎn)的可用資源不滿足約束條件，但完整工作流的約束也有可能是滿足的。

3) 如果BSi=?且SWB＜0，SWD＜0，則選擇可用資源中價(jià)格最小整體性能最高的資源。

完整工作流中多個(gè)任務(wù)路徑P可以并行化執(zhí)行，各個(gè)路徑的執(zhí)行時(shí)間和執(zhí)行成本分別用ET(pi)和EC(pi)表示，用路徑上各個(gè)任務(wù)的執(zhí)行時(shí)間和執(zhí)行成本求和得到?？紤]到路徑是可以并行執(zhí)行的，因此最優(yōu)化函數(shù)為：

則工作流WF的優(yōu)化求解目標(biāo)為：

通過將問題建立成數(shù)學(xué)模型，將工作流的任務(wù)調(diào)度問題轉(zhuǎn)化為有約束條件的極小極大問題的求解。該目標(biāo)函數(shù)的最優(yōu)化結(jié)果是由多個(gè)任務(wù)構(gòu)成的調(diào)度策略，通過求解該目標(biāo)函數(shù)的最優(yōu)值，可得到相應(yīng)的最優(yōu)化的資源分配策略，也就是滿足用戶提交的工作流任務(wù)的最優(yōu)化調(diào)度策略。

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

基于云計(jì)算仿真軟件CloudSim開發(fā)了實(shí)驗(yàn)系統(tǒng)，核心擴(kuò)展了工作流調(diào)度模塊。通過實(shí)驗(yàn)對(duì)比分析了本文提出的算法與HEFT算法[8]、BHEFT算法[12]在運(yùn)行時(shí)間和成本方面的性能。設(shè)置任務(wù)節(jié)點(diǎn)數(shù)分別為10、20、50、100、150、200、250、300的情況下，分別運(yùn)行20次的模擬實(shí)驗(yàn)，并取得實(shí)驗(yàn)結(jié)果的平均值進(jìn)行對(duì)比分析。

4.1 執(zhí)行時(shí)間對(duì)比

根據(jù)文獻(xiàn)[13]，選擇正常調(diào)度長(zhǎng)度(normalized schedule length, NSL)作為評(píng)價(jià)算法在調(diào)度任務(wù)時(shí)的時(shí)間性能指標(biāo)，正常調(diào)度長(zhǎng)度NSL計(jì)算如下：

式中，Tfast是工作流在最快的資源上執(zhí)行所有任務(wù)的執(zhí)行時(shí)間。NSL的值越大，表示任務(wù)執(zhí)行的時(shí)間越長(zhǎng)。本算法與BHEFT算法、HEFT算法在運(yùn)行時(shí)間方面的性能對(duì)比結(jié)果如圖1所示。

可以看出，隨著任務(wù)數(shù)量的增加，3個(gè)算法的NSL值均呈上升趨勢(shì)。但是，相比于BHEFT算法和HEFT算法，本算法仍然具有相對(duì)較小的NSL值；并且隨著任務(wù)數(shù)量的增加，在資源夠用的情況下本算法的NSL值上升趨勢(shì)并不明顯。這是由于本算法根據(jù)工作流任務(wù)屬性，首先進(jìn)行了資源分組處理策略，有效減少了資源搜索空間，從而降低了資源搜索時(shí)間；其次，將工作流全局資源調(diào)度問題轉(zhuǎn)化成了極小極大問題，可以通過數(shù)學(xué)公式求解得到優(yōu)化的資源分配策略。

圖1 不同算法在不同任務(wù)數(shù)量下的NSL值

4.2 執(zhí)行成本對(duì)比

根據(jù)文獻(xiàn)[14]，選擇正常調(diào)度成本(normalized schedule cost, NSC)作為評(píng)價(jià)算法在調(diào)度任務(wù)時(shí)的成本性能指標(biāo)，計(jì)算如下：

式中，ConCheap是所有任務(wù)在最廉價(jià)資源上的執(zhí)行成本。NSC的值越大，表示耗費(fèi)的成本越大。本算法與BHEFT算法和HEFT算法在運(yùn)行成本方面的性能對(duì)比結(jié)果圖2所示。

圖2 不同算法在不同任務(wù)數(shù)量下的NSC值

可以看出，在對(duì)工作流任務(wù)進(jìn)行調(diào)度時(shí)，本算法在成本方面的調(diào)度性能明顯優(yōu)于HEFT算法，略優(yōu)于BHEFT算法。這是由于本算法引入了成本約束的限制條件，有效降低了任務(wù)調(diào)度的成本。

通過上面兩個(gè)實(shí)驗(yàn)，可以得出在相同的截止時(shí)間和預(yù)算的約束下，使用相同的定價(jià)模型，在降低執(zhí)行成本和完成時(shí)間上，本算法比其他兩個(gè)算法優(yōu)越。

4.3 加速比對(duì)比

算法執(zhí)行加速比Speedup[15]表示所有任務(wù)的最小順序執(zhí)行時(shí)間之和與實(shí)際完工時(shí)間的比值，Speedup計(jì)算如下：

它是衡量算法性能的一個(gè)指標(biāo)，值越大，表示算法性能越好。本算法與BHEFT算法和HEFT算法在加速比方面的性能對(duì)比結(jié)果如圖3所示。

由圖可知，在不同的任務(wù)數(shù)量下，本算法比其他兩個(gè)算法具有更好的加速性能，運(yùn)行執(zhí)行效率更快。因?yàn)楸舅惴ú捎萌植呗砸淮涡郧蠼夥椒ǎ⑶冶舅惴?gòu)建的策略求解模型計(jì)算簡(jiǎn)單。

圖3 不同的任務(wù)數(shù)量下算法的Speedup性能

5 結(jié) 束 語

本文分析了現(xiàn)有云工作流調(diào)度模型存在的搜索資源占用時(shí)間長(zhǎng)，造成算法執(zhí)行時(shí)間與執(zhí)行成本增加的問題。提出了基于資源分組的多約束云任務(wù)調(diào)度算法，該算法將調(diào)度過程分解為資源劃分和任務(wù)調(diào)度策略求解兩方面，首先提出基于模糊聚類的資源分組處理方法；然后考慮到任務(wù)的成本和執(zhí)行時(shí)間約束，提出了有約束條件的極小極大策略求解算法，并根據(jù)資源分配規(guī)則對(duì)任務(wù)進(jìn)行調(diào)度。未來研究中，將考慮加入可靠性約束條件，并以運(yùn)營(yíng)的云平臺(tái)為對(duì)象進(jìn)行驗(yàn)證。

[1] FANG Y, WANG F, GE J. A task scheduling algorithm based on load balancing in cloud computing[C]//Web Information Systems and Mining. Sanya, China: Springer, 2010: 271-277.

[2] VILALTA R, MAYORAL A, MU?OZ R, et al. The SDN/NFV cloud computing platform and transport network of the ADRENALINE testbed[C]//2015 1st IEEE Conference on Network Softwarization (NetSoft). [S.l.]: IEEE, 2015: 1-5.

[3] 陳超. 改進(jìn)CS算法結(jié)合決策樹的云工作流調(diào)度[J]. 電子科技大學(xué)學(xué)報(bào), 2016, 45(6): 974-980.

CHEN Chao. Workflow task scheduling in cloud computing based on hybrid improved CS algorithm and decision tree[J]. Journal of University of Electronic Science and Technology of China, 2016, 45(6): 974-980.

[4] MATHEW T, SEKARAN K C, JOSE J. Study and analysis of various task scheduling algorithms in the cloud computing environment[C]//2014 International Conference on Advances in Computing, Communications and Informatics. [S.l.]: IEEE, 2014: 658-664.

[5] GUO L, ZHAO S, SHEN S, et al. Task scheduling optimization in cloud computing based on heuristic algorithm[J]. Journal of Networks, 2012, 7(3): 547-553.

[6] VARALAKSHMI P, RAMASWAMY A, BALASUBRAMANIAN A, et al. An optimal workflow based scheduling and resource allocation in cloud[C]// Advances in Computing and Communications. [S.l.]: Springer, 2011: 411-420.

[7] TOPCUOGLU H, HARIRI S, WU M. Performanceeffective and low-complexity task scheduling for heterogeneous computing[J]. IEEE Transactions on Parallel and Distributed Systems, 2002, 13(3): 260-274.

[8] ARABNEJAD H, BARBOSA J G. List scheduling algorithm for heterogeneous systems by an optimistic cost table[J]. IEEE Transactions on Parallel and Distributed Systems, 2014, 25(3): 682-694.

[9] MALAWSKI M, JUVE G, DEELMAN E, et al. Cost-and deadline-constrained provisioning for scientific workflow ensembles in iaas clouds[C]//Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis. [S.l.]: IEEE Computer Society, 2012.

[10] ABRISHAMI S, NAGHIBZADEH M, EPEMA D H J. Deadline-constrained workflow scheduling algorithms for infrastructure as a service clouds[J]. Future Generation Computer Systems, 2013, 29(1): 158-169.

[11] VAN D B R, VANMECHELEN K, BROECKHOVE J. Online cost-efficient scheduling of deadline-constrained workloads on hybrid clouds[J]. Future Generation Computer Systems, 2013, 29(4): 973-985.

[12] ZHENG W, SAKELLARIOU R. Budget-deadline constrained workflow planning for admission control[J]. Journal of Grid Computing, 2013, 11(4): 633-651.

[13] SHIN K S, CHA M J, JANG M S, et al. Task scheduling algorithm using minimized duplications in homogeneous systems[J]. Journal of Parallel and Distributed Computing, 2008, 68(8): 1146-1156.

[14] VERMA A, KAUSHAL S. Cost minimized pso based workflow scheduling plan for cloud computing[J]. International Journal of Information Technology and Computer Science (IJITCS), 2015, 7(8): 37.

[15] CAO H, JIN H, WU X, et al. DAGMap: Efficient and dependable scheduling of DAG workflow job in Grid[J]. The Journal of Supercomputing, 2010, 51(2): 201-223.

編 輯 葉 芳

Multi-Constrained Scheduling Algorithm of Cloud Workflow Based on Resource Grouping

CHEN Ai-guo, WANG Ling, REN Jin-sheng, and LUO Guang-chun

(School of Computer Science and Engineering, University of Electronic Science and Technology of China Chengdu 611731)

The existing cloud workflow scheduling algorithms, using the global search for resource selection, exist a high computational cost and poor adaptability for large-scale cloud systems. Aimed at solving these problem, a multi-constrained cloud workflow scheduling algorithm based on resource grouping is proposed in this paper. It uses the direct acyclic graph to model the multi-task in cloud workflow and characterize the execution sequences and data transfer requirement between tasks with the DAG’s node and edge’s attributes. Then, fuzzy clustering method is employed to classify resources based on multidimensional features and reduce the computational load from workflow tasks to resource selection. By introducing execution time and cost budget constraints, the proposed algorithm transforms the scheduling problem into a minimax problem. Simulation results show that our algorithm significantly reduces the task execution time and cost.

cloud computing; cloud workflow; scheduling algorithms; resource allocation; fuzzy clustering

TP311

A

10.3969/j.issn.1001-0548.2017.03.014

2016 ? 12 ? 26；

2017 ? 03 ? 21

四川省科技支撐計(jì)劃(2016GZ0075, 2016GZ0077)；四川省技技廳國(guó)際合作項(xiàng)目(2017HH0075)

陳愛國(guó)(1981 ? )，男，博士，副教授，主要從事云計(jì)算、信息物理融合系統(tǒng)方面的研究.