申秋慧 牛玲

摘 要：基于啟發(fā)式算法的工作流調(diào)度算法目標(biāo)單一，無法保證用戶滿意度，且多目標(biāo)調(diào)度算法少、性能差。為了改善現(xiàn)狀，提出基于多階段PSO的多目標(biāo)工作流調(diào)度算法MSPSO，分析工作流任務(wù)的層次結(jié)構(gòu)，按層次進(jìn)行多階段PSO調(diào)度，結(jié)合排隊(duì)理論估算每階段調(diào)度需要的虛擬機(jī)數(shù)量，控制PSO搜索空間，使算法能快速找到最優(yōu)解。用4種真實(shí)科學(xué)工作流在CloudSim環(huán)境下進(jìn)行仿真實(shí)驗(yàn)。結(jié)果表明，MSPSO算法資源利用率提高了1.81%，能耗降低了9.16%，任務(wù)違約率低至0.075%。MSPSO調(diào)度算法不僅能動態(tài)增減虛擬機(jī)，降低能耗，還能在保證截止時間的前提下降低任務(wù)違約率，提高資源利用率。

關(guān)鍵詞：工作流調(diào)度;PSO;CPU能耗;云計算

DOI：10. 11907/rjdk. 191474 開放科學(xué)（資源服務(wù)）標(biāo)識碼（OSID）：

中圖分類號：TP312文獻(xiàn)標(biāo)識碼：A 文章編號：1672-7800（2019）009-0081-04

A Multi-objective Workflow Scheduling Algorithm Based on Multi-Stage PSO

SHEN Qiu-hui，NIU Ling

（School of Computer Science and Technology， Zhoukou Normal University， Zhoukou 466000，China）

Abstract： In order to improve the current situation of workflow scheduling algorithm based on heuristic algorithm， which has single goal， can not guarantee user satisfaction， and has few multi-objective scheduling algorithms and poor performance， based on PSO algorithm， a multi-objective workflow scheduling algorithm MSPSO based on multi-stage PSO is proposed. Firstly， the hierarchical structure of workflow tasks is analyzed， and multi-stage PSO scheduling is carried out according to the hierarchical structure. At the same time， the number of virtual machines needed for each stage scheduling is estimated by queuing theory， and the search space of PSO is controlled， so that the algorithm can quickly find the optimal solution. Four kinds of real scientific workflow are used to simulate the experiment in CloudSim environment. The results show that the resource utilization of MSPSO algorithm is increased by 1.81%， the energy consumption is reduced by 9.16%， and the task default rate is reduced to 0.075%. MSPSO scheduling algorithm can not only dynamically increase and decrease the energy consumption of virtual machines， but also reduce the default rate of tasks and improve resource utilization on the premise of guaranteeing deadlines.

Key Words：workflow scheduling; PSO; CPU consumption; cloud computing

0 引言

工作流可以表示為一個有向無環(huán)圖，任務(wù)表示節(jié)點(diǎn)，邊表示任務(wù)間的依賴關(guān)系，所以工作流調(diào)度就屬于一類NP（Non-deterministic Polynomial）完全問題。研究者提出了各種基于啟發(fā)式和元啟發(fā)式的算法解決工作流調(diào)度問題[1]。文獻(xiàn)[2]開發(fā)了一個稱為Dyna的調(diào)度系統(tǒng)，在用戶指定的概率期限保證下，將預(yù)期貨幣成本最小化;文獻(xiàn)[3]提出了一種基于任務(wù)序列劃分的兩段式編碼遺傳算法，考慮流式工作特點(diǎn)和地理分布式控制系統(tǒng)的價格差異，以租戶流程租約和虛擬機(jī)實(shí)例負(fù)載為約束，通過兩段式交叉、變異算子進(jìn)行種群迭代進(jìn)化，實(shí)現(xiàn)服務(wù)費(fèi)用與使用成本優(yōu)化;文獻(xiàn)[4]對PSO（Particle Swarm Optimizat）算法進(jìn)行了改進(jìn)，優(yōu)化目標(biāo)是執(zhí)行代價和通信代價最小;文獻(xiàn)[5]考慮工作流中間數(shù)據(jù)存儲，將競價實(shí)例與按需實(shí)例相結(jié)合，提出了一種調(diào)度總費(fèi)用最小化算法;文獻(xiàn)[6]提出了一個復(fù)合迭代局部搜索算法，以成本最小為優(yōu)化目標(biāo);文獻(xiàn)[7]提出了一種離線容錯彈性調(diào)度算法，能夠有效地為云系統(tǒng)中資源利用率較高的工作流提供相應(yīng)容錯調(diào)度策略，任務(wù)違約率低;文獻(xiàn)[8]基于定價模型提出了一種針對特定問題的編碼種群初始化、適應(yīng)度評估和遺傳算子新方案，在大多數(shù)有INS的工作流程中具有更高可靠性;文獻(xiàn)[9]針對數(shù)據(jù)密集型工作流，提出了一種面向負(fù)載均衡的數(shù)據(jù)約減策略，以較少調(diào)度時間為目標(biāo);文獻(xiàn)[10]以截止時間為目標(biāo)，提出了一種滿足期限約束的工作流調(diào)度算法;文獻(xiàn)[11]從云工作流任務(wù)分配、主機(jī)負(fù)載和主機(jī)功耗關(guān)系角度出發(fā)，提出了一種面向能耗的云工作流調(diào)度優(yōu)化方法;文獻(xiàn)[12]提出了一種兩階段調(diào)度算法，第一階段進(jìn)行預(yù)調(diào)度，第二階段進(jìn)行負(fù)載感知動態(tài)調(diào)度，兩階段結(jié)合實(shí)現(xiàn)高資源利用率目的;文獻(xiàn)[13]提出的調(diào)度算法，分析了最小時間增加與最大化資源減少量之間的平衡點(diǎn)，通過合并任務(wù)和資源以提高資源利用率。

上述算法大多只考慮了一個目標(biāo)，比如執(zhí)行成本最低、完成時間最短、能耗低、資源利用率高、系統(tǒng)可靠性高等。而對于一個以上的多目標(biāo)調(diào)度則研究較少，只有文獻(xiàn)[14]針對大數(shù)據(jù)環(huán)境下的科學(xué)工作流調(diào)度提出了一種考慮總完成時間和負(fù)載均衡的最大百分比調(diào)度算法，但調(diào)度算法是靜態(tài)調(diào)度;文獻(xiàn)[15]提出了一種雙目標(biāo)遺傳算法（BOGA），以實(shí)現(xiàn)工作流調(diào)度的低能耗、高系統(tǒng)可靠性;文獻(xiàn)[16]提出的多目標(biāo)差分演化（MODE）算法基于重力搜索算法，以執(zhí)行時間和成本最小化為目標(biāo);文獻(xiàn)[17]提出的多目標(biāo)異類最早完成時間（MOHEFT）算法同時考慮了完成時間和能耗兩個目標(biāo)。

因此，研究多目標(biāo)工作流調(diào)度是一個挑戰(zhàn)，本文基于粒子群算法結(jié)合排隊(duì)理論提出了一種多階段多目標(biāo)的工作流調(diào)度算法，在保證完成時間的前提下，能達(dá)到低能耗、高資源利用率和高可靠性的多目標(biāo)調(diào)度，改善了多目標(biāo)工作流調(diào)度算法數(shù)量少、性能差的現(xiàn)狀。

1 問題描述

云環(huán)境下一個工作流WF可以用兩個集合表示，即WF=（T，E），其中T={t1，t2，t3，…，tn}是WF中所有任務(wù)的集合，任務(wù)個數(shù)為n，E是有向邊的集合，其中元素為eij，表示任務(wù)ti與tj之間存在依賴關(guān)系，ti是tj的父任務(wù)，tj是ti的子任務(wù)，tj必須在ti完成后才能開始執(zhí)行。工作流結(jié)構(gòu)是可以被分析的，當(dāng)工作流到達(dá)時，根據(jù)任務(wù)間的依賴關(guān)系將工作流分成x層，第i層任務(wù)個數(shù)用ni表示，任務(wù)的集合用Ti表示[18]。如圖1所示，第一層任務(wù)個數(shù)n1=2，任務(wù)集合T1={t1，t2};第二層任務(wù)個數(shù)n2=8;第三層任務(wù)個數(shù)n3=9;第4層任務(wù)個數(shù)n4=1。

本文定義按層次對工作流任務(wù)進(jìn)行調(diào)度。用V={v1，v2，v3，…，vm}表示云計算系統(tǒng)中m個活動虛擬機(jī)的集合，m的大小隨著負(fù)載變化而動態(tài)變化。每臺物理機(jī)hi上各虛擬機(jī)的CPU計算能力總和不超過物理機(jī)CPU峰值的70%，因?yàn)槿绻倥渲眯碌奶摂M機(jī)到hi，會導(dǎo)致能耗大幅度提升[19]。每臺虛擬機(jī)vj一個時間只執(zhí)行一個任務(wù)ti，對ni個任務(wù)在m個虛擬機(jī)上調(diào)度就可以轉(zhuǎn)化為一個M/M/n排隊(duì)模型。當(dāng)系統(tǒng)處于平衡狀態(tài)時，由排隊(duì)理論可通過式（1）計算出任務(wù)的平均響應(yīng)時間TRi[5]。

其中，[P0=（k=0mρk1k！+ρn1/1-ρm！）-1]，ρ1=λμ，ρ=λμ/n表示服務(wù)強(qiáng)度，λ表示系統(tǒng)中工作流任務(wù)到達(dá)的速率，μ表示各任務(wù)的平均執(zhí)行時間，m表示虛擬機(jī)個數(shù)，對應(yīng)于排隊(duì)系統(tǒng)中服務(wù)窗口個數(shù)。

用stj表示虛擬機(jī)vj執(zhí)行任務(wù)開始時間，用etj表示執(zhí)行任務(wù)結(jié)束時間，用M表示任務(wù)到虛擬機(jī)的映射集合，由tij=（ti，vj，sti，eti）組成，表示任務(wù)ti在虛擬機(jī)vj上運(yùn)行，運(yùn)行開始時間是sti，結(jié)束時間是eti。工作流任務(wù)第i層的開始時間STi=Minimize sti，結(jié)束時間ETi= Maximize eti，用STWF表示工作流的到達(dá)時間，則工作流的完成時間ETWF可由式（2）計算得到。

綜上所述，工作流調(diào)度問題可以表示成一個四元組S=（T，V，M，ETWF），約束條件為ETWF≤deadline。在滿足截止時間的前提下，可以計算得到每一次調(diào)度最合適的TRi，雖然任務(wù)是動態(tài)變化的，但每一次調(diào)度時都可以統(tǒng)計出需要調(diào)度的任務(wù)個數(shù)，進(jìn)而可以推算出每一次調(diào)度時滿足任務(wù)要求的虛擬機(jī)個數(shù)，虛擬機(jī)個數(shù)m隨負(fù)載動態(tài)變化，任務(wù)多時開啟新的虛擬機(jī)，任務(wù)少時關(guān)閉空閑虛擬機(jī)，不僅提高了虛擬機(jī)資源利用率，還達(dá)到了動態(tài)節(jié)能目的。在可靠性方面，若上一層調(diào)度存在失敗節(jié)點(diǎn)，在下一層調(diào)度時會實(shí)時增加虛擬機(jī)數(shù)量，保證任務(wù)順利完成。每一次調(diào)度都采用種群規(guī)模相對較小的PSO算法，不僅能快速收斂，找到最優(yōu)解，而且還能使調(diào)度策略的魯棒性更好。

2 多階段PSO調(diào)度算法

2.1 PSO模型

用PSO解決問題有兩個關(guān)鍵步驟：一是設(shè)置問題的編碼方式，二是定義適應(yīng)度函數(shù)。為了定義問題的編碼方式，需要先建立粒子的含義和尺寸。對于提出的調(diào)度策略，一個粒子代表工作流的一個層次和子任務(wù)，即第i階段粒子的尺寸是ni。粒子的尺寸決定空間中粒子所在位置的坐標(biāo)個數(shù)。比如，5個粒子的位置用5個坐標(biāo)表示，6個粒子用6個坐標(biāo)表示。系統(tǒng)中每階段可用虛擬機(jī)個數(shù)m決定了粒子移動的范圍。因此，坐標(biāo)值范圍是0-m。粒子位置坐標(biāo)值向下取整，表示該虛擬機(jī)被分配給了粒子所表示的任務(wù)。這樣，粒子的位置就能描述任務(wù)到虛擬機(jī)的映射。比如，系統(tǒng)中有6個虛擬機(jī)，每個粒子的坐標(biāo)值都在0和6之間，坐標(biāo)1表示t1值是1.3，意味著t1被分配給了v1，坐標(biāo)2相當(dāng)于t2值是3.1，表示t2被分配給了v3，以此類推。

由于云環(huán)境中虛擬機(jī)和任務(wù)個數(shù)都是無限的，因此PSO搜索空間會很大，導(dǎo)致算法收斂慢并很難找到合適的解。為了減小搜索空間，提出了分階段調(diào)度方案。第一階段調(diào)度時搜索空間規(guī)模即虛擬機(jī)個數(shù)m設(shè)置為第一層任務(wù)的個數(shù)n1，之后每個階段搜索空間規(guī)模在滿足式（1），即滿足該階段任務(wù)響應(yīng)時間的前提下，計算取最小的m值，也就是說之后每一個階段調(diào)度都是在滿足該階段任務(wù)響應(yīng)時間的前提下取最小虛擬機(jī)個數(shù)，這樣不僅能使PSO收斂速度快，而且找到最優(yōu)解相對容易。同時，系統(tǒng)中運(yùn)行的虛擬機(jī)個數(shù)隨負(fù)載動態(tài)變化，且被充分利用，相比不分階段的PSO，需要的虛擬機(jī)個數(shù)明顯減少且沒有空閑虛擬機(jī)，不僅提高了資源利用率，也降低了系統(tǒng)能耗，實(shí)現(xiàn)了保證完成時間、高資源利用率、低能耗的多目標(biāo)調(diào)度。

2.2 調(diào)度算法

多階段PSO調(diào)度算法思想是當(dāng)一個工作流任務(wù)到達(dá)時，首先分析它的結(jié)構(gòu)，把它分為x層，每一層依次采用PSO進(jìn)行調(diào)度。初始化粒子位置P[i]為一組0-mj的隨機(jī)數(shù)。第一層比較特殊，沒有父節(jié)點(diǎn)，所以初始化虛擬機(jī)個數(shù)就是第一層任務(wù)的個數(shù)n1，后面每一次調(diào)度粒子的規(guī)模根據(jù)式（1）計算得到，若下一階段調(diào)度時粒子規(guī)模大于上一階段粒子規(guī)模，就部署新的虛擬機(jī)，否則關(guān)閉虛擬機(jī)。調(diào)度時用執(zhí)行時間最短作為適應(yīng)度函數(shù)選擇優(yōu)秀粒子的位置，第j階段調(diào)度輸出的是第j層任務(wù)的調(diào)度表。當(dāng)調(diào)度算法在執(zhí)行第j+1層PSO時，第j層的調(diào)度表已經(jīng)輸出，調(diào)度中心就可以展開實(shí)際調(diào)度，調(diào)度算法執(zhí)行和任務(wù)執(zhí)行可以并行，這樣可以減少工作流的完成時間。另外若已調(diào)度任務(wù)中有執(zhí)行失敗的，可以在下一階段重新參與調(diào)度，這樣可以有效降低任務(wù)違約率，提高系統(tǒng)對工作流任務(wù)執(zhí)行的成功率。算法具體描述如下：

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

本文使用CloudSim框架運(yùn)行在實(shí)驗(yàn)室的真實(shí)云環(huán)境中進(jìn)行實(shí)驗(yàn)，選擇來自不同科學(xué)領(lǐng)域具有不同結(jié)構(gòu)、數(shù)據(jù)和計算特點(diǎn)的4個真實(shí)工作流Montage、LIGO、SIPHT和CyberShake作為實(shí)驗(yàn)輸入。用本文多階段PSO調(diào)度（MSPSO）算法與雙目標(biāo)遺傳算法（BOGA）、多目標(biāo)異類最早完成時間（MOHEFT）算法、多目標(biāo)差分演化（MODE），在完成時間、資源利用率、系統(tǒng)能耗和任務(wù)違約率4個方面進(jìn)行比較。

3.1 實(shí)驗(yàn)設(shè)置

實(shí)驗(yàn)運(yùn)行在一臺IBM高性能服務(wù)器上，假設(shè)采用同一類型虛擬機(jī)，參數(shù)是：CPU計算能力為4 400MIPS，存儲容量50GB，帶寬2G。虛擬機(jī)每次運(yùn)行一個任務(wù)，每種算法執(zhí)行20次，求平均值作為最終實(shí)驗(yàn)結(jié)果。初始虛擬機(jī)個數(shù)取工作流第一層任務(wù)個數(shù)。根據(jù)文獻(xiàn)[20]研究成果PSO算法中的參數(shù)c1、c2和ω，取值為c1=c2=2，ω=0.5。

3.2 結(jié)果分析

仿真實(shí)驗(yàn)時，分別設(shè)置工作流規(guī)模為50、100、1 000個任務(wù)，結(jié)果表明，雖然任務(wù)規(guī)模與完成時間、能耗、資源利用率有直接關(guān)系，但是在證明算法性能上50、100和1 000個任務(wù)結(jié)果是相同的，因此結(jié)果分析以100個任務(wù)為代表。任務(wù)完成時間如圖2所示，BOGA算法完成時間最小，表現(xiàn)最好，MSPSO算法次之，比其高了8.39%，原因在于BOGA算法以完成時間最短為目標(biāo)，而MSPSO算法是多目標(biāo)的，在保證截止時間的前提下首先優(yōu)化的是系統(tǒng)能耗和資源利用率，然后才是完成時間。如圖3、圖4所示，在系統(tǒng)能耗和資源利用率方面，MSPSO算法表現(xiàn)最好，能耗降低了9.16%，資源利用率提高了1.81%，原因是MSPSO算法調(diào)度時虛擬機(jī)是隨著每一階段任務(wù)個數(shù)動態(tài)增減的，能及時關(guān)閉空閑虛擬機(jī)降低系統(tǒng)能耗，且系統(tǒng)中每一個活動虛擬機(jī)都被充分利用，而虛擬機(jī)部署時也是在保證物理機(jī)性能的情況下裝載盡可能多虛擬機(jī)。另外，MSPSO還有一個好處就是上一階段執(zhí)行失敗的任務(wù)將在下一階段重新被調(diào)度，降低任務(wù)違約率。如圖5所示，MSPSO算法任務(wù)違約率最低，為0.075%。

4 結(jié)語

本文分析了現(xiàn)有工作流調(diào)度算法，發(fā)現(xiàn)多目標(biāo)工作流調(diào)度算法較少，因此提出一種結(jié)合排隊(duì)理論、基于多階段PSO的多目標(biāo)調(diào)度算法MSPSO，該算法在保證截止時間的前提下，對工作流進(jìn)行多階段PSO調(diào)度，不僅能夠動態(tài)增減虛擬機(jī)以降低能耗，還能提高資源利用率并降低任務(wù)違約率。實(shí)驗(yàn)驗(yàn)證了MSPSO算法的優(yōu)越性，雖然完成時間略高于以最小完成時間為目標(biāo)的BOGA算法，但在系統(tǒng)能耗、資源利用率、任務(wù)違約率方面表現(xiàn)最好。

MSPSO算法雖然能動態(tài)增減虛擬機(jī)，但是沒有考慮虛擬機(jī)關(guān)閉和開啟的能耗代價，因此未來會考慮把開關(guān)虛擬機(jī)能耗開銷引入MSPSO，對MSPSO作進(jìn)一步優(yōu)化和驗(yàn)證。

參考文獻(xiàn)：

[1] 馬俊濤，陳業(yè)恩，胡國杰，等. 云計算環(huán)境下基于遺傳算法的任務(wù)調(diào)度技術(shù)研究[J]. 軟件導(dǎo)刊， 2016， 15（1）：51-53.

[2] ZHOU A C，HE B，LIU C. Monetary cost optimizations for hosting workflow-as-a-service in IaaS clouds[J]. IEEE Transactions on Cloud Computing， 2013， 4（1）：34-48.

[3] 方伯芃，孫林夫. 面向QoS與成本感知的云工作流調(diào)度優(yōu)化[J]. 計算機(jī)集成制造系統(tǒng)，2018，24（2）：331-348.

[4] 郭文濤，盧少武. 基于代價優(yōu)化的云工作流調(diào)度改進(jìn)PSO算法[J]. 計算機(jī)測量與控制，2017，25（6）：162-166.

[5] 馬子泰，曹健，姚艷. 云環(huán)境下使用競價實(shí)例并考慮中間數(shù)據(jù)存儲策略的工作流調(diào)度方法[J]. 計算機(jī)集成制造系統(tǒng)， 2017， 23（5）：983-992.

[6] 王宏欣，張躍. 帶截止期約束的多模態(tài)云服務(wù)工作流調(diào)度[J]. 小型微型計算機(jī)系統(tǒng)， 2016， 37（11）：2437-2442.

[7] DING Y，YAO G，HAO K. Fault-tolerant elastic scheduling algorithm for workflow in Cloud systems[M]. Elsevier Science Inc，2017， 393：47-65.

[8] ZHU Z，ZHANG G，MEMBER S，et al. Evolutionary multi-objective workflow scheduling in cloud[J]. IEEE Transactions on Parallel and Distributed Systems， 2016， 27（5）：1344-1357.

[9] 胡志剛，李佳，鄭美光. 云環(huán)境下面向負(fù)載均衡的數(shù)據(jù)密集型工作流的數(shù)據(jù)約簡策略[J/OL]. 計算機(jī)應(yīng)用研究：2018-05-24 21：09：29. http：//kns.cnki.net/KCMS/detail/51.1196.TP.20180524.2109.020.html.

[10] 張秋霞，張來順. 云環(huán)境中滿足期限約束的工作流任務(wù)調(diào)度[J]. ?計算機(jī)工程與設(shè)計， 2019， 40（2）：425-432.

[11] 謝毅，賀田塔，倪倩蕓，等. 面向能耗的云工作流調(diào)度優(yōu)化[J]. ?系統(tǒng)工程理論與實(shí)踐， 2017，37（4）：1056-1071.

[12] 王巖，汪晉寬，韓英華. 面向云工作流的兩階段資源調(diào)度方法[J]. 華南理工大學(xué)學(xué)報：自然科學(xué)版， 2017， 45（1）：80-87.

[13] 劉曉天，朱耀琴，顧大明. 有效資源減少量最大化的云計算工作流調(diào)度[J]. 計算機(jī)工程與設(shè)計， 2017， 38（11）：82-88.

[14] LI X， SONG J，HUANG B. A scientific workflow management system architecture and its scheduling based on cloud service platform for manufacturing big data analytics[J]. ?The International Journal of Advanced Manufacturing Technology， 2016， 84（1-4）：119-131.

[15] ZHANG L，LI K，LI C，et al. Bi-objective workflow scheduling of the energy consumption and reliability in heterogeneous computing systems[J]. ?Information Sciences， 2017， 379：241-256.

[16] ARSUAGA-RíOS，MARíA，VEGA-RODRíGUEZ，et al.Meta-schedulers for grid computing based on multi-objective swarm algorithms[J]. ?Applied Soft Computing， 2013， 13（4）：1567-1582.

[17] DURILLO J J，NAE V，PRODAN R. ?Multi-objective energy-efficient workflow scheduling using list-based heuristics[J]. ?Future Generation Computer Systems， 2014， 36：221-236.

[18] RODRIGUEZ M A，BUYYA R. ?Deadline based resource provisioning and scheduling algorithm for scientific workflows on clouds[J]. ?IEEE Transactions on Cloud Computing， 2014， 2（2）：222-235.

[19] HSU C H，SLAGTER K D，CHEN S C，et al. Optimizing energy consumption with task consolidation in clouds[J]. Information Sciences， 2014， 258：452-462.

[20] 冀云，高世澤. 輸入率和服務(wù)率可變且窗口能力不等的M/M/n排隊(duì)模型研究[J]. 重慶師范大學(xué)學(xué)報：自然科學(xué)版，2014，31（3）：65-67.

（責(zé)任編輯：何 麗）