多DAG工作流在云計算環(huán)境下的可靠性調(diào)度方法

景維鵬,吳智博,劉宏偉,舒燕君

(1.哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院,黑龍江哈爾濱 150001; 2.東北林業(yè)大學(xué)信息與計算機(jī)工程學(xué)院,黑龍江哈爾濱 150040)

?

多DAG工作流在云計算環(huán)境下的可靠性調(diào)度方法

景維鵬1,2,吳智博1,劉宏偉1,舒燕君1

(1.哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院,黑龍江哈爾濱 150001; 2.東北林業(yè)大學(xué)信息與計算機(jī)工程學(xué)院,黑龍江哈爾濱 150040)

摘要:針對云計算環(huán)境中多個DAG科學(xué)工作流的可靠性調(diào)度問題,提出一種考慮虛擬機(jī)之間鏈路通信競爭的動態(tài)多DAG分層調(diào)度算法.首先使用通信競爭模型描述虛擬機(jī)之間的通信,然后分別計算主版本及副版本任務(wù)的最早完成時間,并限定任務(wù)所調(diào)度的虛擬機(jī)單元.再對多個同時到達(dá)的DAG工作流任務(wù)使用動態(tài)分層方法,計算每個DAG任務(wù)的不公平程度因子.該算法有效解決了當(dāng)多個DAG中任務(wù)的權(quán)值相差較大時,之前到達(dá)的DAG不會因為剩余任務(wù)遲遲得不到調(diào)度而導(dǎo)致執(zhí)行時間跨度增大的問題.仿真實驗表明,在保證可靠調(diào)度的前提下,該算法不僅能提高多個DAG調(diào)度的公平程度,而且能有效地縮短多個DAG調(diào)度的平均最早完成時間.

關(guān)鍵詞:云計算;多個DAG;可靠性調(diào)度;公平因子

云計算作為一種嶄新的計算模式得到越來越多的關(guān)注.它將各種分布的計算、存儲及應(yīng)用資源進(jìn)行整合并實現(xiàn)多層次的虛擬化與抽象化,有效地將各類資源以服務(wù)的形式提供給用戶.云計算中資源調(diào)度的目的是實現(xiàn)計算資源、存儲資源集合與調(diào)度任務(wù)集合滿足有效空間和時間映射關(guān)系.因此,云計算環(huán)境下設(shè)計有效解決任務(wù)之間依賴關(guān)系的資源調(diào)度策略,是實現(xiàn)云計算科學(xué)工作流高可擴(kuò)展、高可用性的關(guān)鍵.

在云計算科學(xué)工作流的應(yīng)用中,面臨的是海量密集型數(shù)據(jù)的處理,具體表現(xiàn)為:在云計算科學(xué)工作流調(diào)度過程中,存在多個有向無環(huán)圖(Directed Acyclic Graph,DAG)同時提交或在計算過程中動態(tài)提交的情況,因此要求多DAG的科學(xué)工作流的調(diào)度算法必須要滿足環(huán)境的動態(tài)變化和對動態(tài)到達(dá)的工作流進(jìn)行實時處理的需求;企業(yè)級的工作流應(yīng)用中,需要設(shè)置有效的容錯保障機(jī)制以容忍系統(tǒng)運(yùn)行時遇到的故障;合理地調(diào)度機(jī)制應(yīng)該保障用戶提交的科學(xué)計算請求不因數(shù)據(jù)中心的負(fù)載、位置而受到影響.文獻(xiàn)[1]從不同角度證明了調(diào)度算法在科學(xué)工作流應(yīng)用中的重要性.

近年來,針對單個DAG任務(wù)的科學(xué)工作流調(diào)度,無論是調(diào)度模型,或是調(diào)度目標(biāo)的多樣性均取得很大進(jìn)展,然而針對科學(xué)工作流應(yīng)用的多DAG調(diào)度的研究相對較少,文獻(xiàn)[13]提出一種逐個執(zhí)行多DAG任務(wù)的方法,該方法導(dǎo)致虛擬機(jī)會產(chǎn)生大量的空閑等待時間,延長了任務(wù)的執(zhí)行時間.文獻(xiàn)[2,4,13]提出將多個DAG合并成為一個復(fù)合DAG后,再使用調(diào)度整個DAG任務(wù)的方法來調(diào)度負(fù)荷后的DAG任務(wù).這些方法均忽略了存在于各DAG之間調(diào)度的不公平性問題.

文獻(xiàn)[3]提出了一種Planner-guided的調(diào)度策略,算法使用動態(tài)RANK-HYBD方法對多DAG任務(wù)分配優(yōu)先級,但該算法未考慮DAG任務(wù)在不同時間到達(dá)的情況.另外,由文獻(xiàn)[3]分析表明,簡單的DAG任務(wù)合并,并不能顯著提升算法的性能.文獻(xiàn)[14]提出了一種面向數(shù)據(jù)密集型應(yīng)用的離線時間開銷多DAG任務(wù)調(diào)度算法,但該算法沒有解決之前到達(dá)的DAG任務(wù)不會因為剩余任務(wù)遲遲得不到調(diào)度而導(dǎo)致執(zhí)行時間跨度增大的問題.綜上,如何有效地解決多DAG任務(wù)調(diào)度的公平性,滿足多個DAG任意時間提交的可靠性調(diào)度技術(shù)是云計算環(huán)境下多DAG調(diào)度問題的關(guān)鍵.

由于云計算是建立在大規(guī)模廉價服務(wù)集群上的一種新的服務(wù)模式,加上計算任務(wù)的復(fù)雜性和動態(tài)性,導(dǎo)致計算節(jié)點極易出現(xiàn)故障,因此,調(diào)度算法必須在探求整體任務(wù)的最短完成時間的情況下進(jìn)行,提高任務(wù)調(diào)度的可靠性.文獻(xiàn)[5-8]中論述使用主副版本的調(diào)度機(jī)制是有效提高調(diào)度算法可靠性的主要方法.文獻(xiàn)[5]提出使用完全復(fù)制方法對任務(wù)進(jìn)行復(fù)制,并定義執(zhí)行副本的具體時間;文獻(xiàn)[6]提出一種能夠滿足最佳最早完成時間(Makespan)和可靠性的實時調(diào)度算法;文獻(xiàn)[7]在文獻(xiàn)[6]算法的基礎(chǔ)上使用Map Reduce編程框架,實現(xiàn)可靠性和性能最優(yōu);文獻(xiàn)[8]提出優(yōu)先級約束、可靠性代價驅(qū)動的容錯調(diào)度方法,該算法強(qiáng)調(diào)“強(qiáng)主版本復(fù)制”,要求任務(wù)必須收到它所有前驅(qū)節(jié)點的結(jié)果,使該算法只考慮任務(wù)的前驅(qū)節(jié)點,而沒有考慮所有節(jié)點任務(wù)的完成問題.文獻(xiàn)[5,7-8]使用復(fù)制的方法在可靠性和系統(tǒng)性能之間取得折衷.但這些方法僅僅對復(fù)制任務(wù)本身進(jìn)行判斷,沒有算法對副版本任務(wù)開始時間進(jìn)行準(zhǔn)確的計算,這樣使得算法性能受到極大影響.

另外,上述調(diào)度算法均假設(shè)任意網(wǎng)絡(luò)的虛擬機(jī)是全互連結(jié)構(gòu),同時也假設(shè)調(diào)度器與虛擬機(jī)之間及虛擬機(jī)之間是可以隨時獲取相關(guān)調(diào)度信息,而在實際應(yīng)用中,在云計算復(fù)雜環(huán)境中這種假設(shè)是不成立的.文獻(xiàn)[11]的研究表明,考慮通信鏈路通信競爭的調(diào)度算法能有效提高算法的精度.文獻(xiàn)[9]在異構(gòu)計算環(huán)境下的通信競爭模型,利用該模型證明了調(diào)度算法的有效性,但該模型是考慮任意網(wǎng)絡(luò)互連情況;文獻(xiàn)[10]在通信競爭模型下,使用最短路徑的搜索算法實現(xiàn)了任意互連網(wǎng)絡(luò)中虛擬機(jī)的查找問題及調(diào)度問題.

綜上,筆者提出一種面向科學(xué)工作流應(yīng)用的動態(tài)多DAG分層調(diào)度算法(CCRH).該算法首先使用通信競爭模型描述虛擬機(jī)之間的通信競爭,使用主副版本技術(shù)提高調(diào)度算法的可靠性,針對多DAG使用公平因子的分層調(diào)度策略;仿真實驗表明了算法的有效性.

1 任務(wù)調(diào)度模型

典型的云計算科學(xué)工作流的應(yīng)用,在不同時刻動態(tài)提交的任務(wù)用DAG來表示,進(jìn)行形式化定義如下.

定義1 四元組G=(V,E,w,c),表示節(jié)點和邊的DAG圖,其中,V={v1,v2,v3,…,vN},表示任務(wù)集合,N表示任務(wù)數(shù),任務(wù)之間具有的依賴關(guān)系用E={eij|vi,vj∈V}表示,w(vi)表示任務(wù)vi的計算代價,c(eij)表示任務(wù)vi和vj之間的通信代價.

定義2 集合{vx∈V:exi∈E}表示任務(wù)vi前驅(qū)節(jié)點集合,記為pred(vi).集合{vx∈V:eix∈E}表示任務(wù)vi后繼節(jié)點集合,記為succ(vi).如果pred(vi)=?,則任務(wù)節(jié)點vi是入口節(jié)點,記為ven try.如果succ(vi)=?,則任務(wù)節(jié)點vi是出口節(jié)點,記為vexit.

定義3 云計算的計算資源由于進(jìn)行虛擬化,這里將虛擬化后異構(gòu)的虛擬機(jī)集合描述為P={P1,P2…,PM},其中M表示虛擬機(jī)個數(shù),調(diào)度到虛擬機(jī)Pk上的任務(wù)vi的主版本開始時間表示為tps(vi,pk),完成時間分別表示為tpf(vi,pk);任務(wù)vj副版本開始時間和完成時間分別表示為tBs(vj,pk),tBf(vj,pk),任務(wù)vi的主、副版本任務(wù)被調(diào)度的虛擬機(jī)表示為Pp(vi)和PB(vi).

定義4 云計算系統(tǒng)是任意互聯(lián)的網(wǎng)絡(luò)結(jié)構(gòu).虛擬機(jī)之間的網(wǎng)絡(luò)連接包括計算節(jié)點內(nèi)部、同一機(jī)柜內(nèi)部以及不同機(jī)柜,這里用lhk表示Ph與Pk之間的通信代價.

2 多DAG調(diào)度算法CCRH

2.1 任務(wù)優(yōu)先級

單個DAG任務(wù)優(yōu)先級使用靜態(tài)調(diào)度方法計算,受HEFT[12]算法啟發(fā),假設(shè)任務(wù)vi和vj具有依賴關(guān)系,且vj的運(yùn)行直接依賴于vi的運(yùn)行結(jié)果.考慮計算與通信總體消耗的任務(wù)優(yōu)先級表示為

云計算環(huán)境下的通信存在于處理機(jī)內(nèi)、機(jī)柜內(nèi)、機(jī)柜之間,因此必須將通信邊調(diào)度考慮進(jìn)來,以此實現(xiàn)更加嚴(yán)謹(jǐn)?shù)恼{(diào)度模型.文中使用文獻(xiàn)[11]提出的基于插入策略的最短路徑搜索算法,實現(xiàn)云計算環(huán)境下任意網(wǎng)絡(luò)互連異構(gòu)計算系統(tǒng)的通信路徑查找.這里,定義LST(eij,l),LFT(eij,l)為eij在通信鏈路l的通信開始時間和完成時間,且LFT(eij,l)≥LST(eij,l)+c(eij).

2.2 主副版本任務(wù)調(diào)度

為了提高云計算系統(tǒng)的可靠性,文中使用主副版本的調(diào)度方法,即通過在備份虛擬機(jī)上執(zhí)行冗余任務(wù)來實現(xiàn)容錯,同時保證任務(wù)的實時性.通過準(zhǔn)確分析主、副版本任務(wù)的開始時間及滿足所調(diào)度的虛擬機(jī)(虛擬計算節(jié)點)的約束,在滿足系統(tǒng)可靠性的前提下,獲得較好的Makespan.

2.2.1 主版本任務(wù)調(diào)度

調(diào)度方法首先解決主版本任務(wù)調(diào)度,依據(jù)前驅(qū)節(jié)點集合pred(vj)中任務(wù)的副版本完成時間,任務(wù)vj的主版本的開始時間tps(vj,p)有以下3種狀態(tài):

(1)任務(wù)vj的主版本的完成時間小于集合pred(vj)中任務(wù)的副版本最遲完成時間與通信鏈路完成時間的最大值.

(2)任務(wù)vj的主版本開始時間大于集合pred(vj)中的任務(wù)的副版本最遲完成時間與通信鏈路完成數(shù)據(jù)傳輸時間的最大值.

(3)任務(wù)vj的主版本開始時間介于pred(vj)中任務(wù)主、副兩個版本最遲完成時間與通信鏈路完成時間的最大值之間,且其完成時間在其最大副版本完成時間之后.

由以上3種情況可知,算法CCRH中不同DAG任務(wù)的主版本調(diào)度約束,在滿足其自身優(yōu)先級任務(wù)約束的情況下,可以對其進(jìn)行獨立調(diào)度,只需依據(jù)調(diào)度虛擬機(jī)隊列尋找最早開始的完成任務(wù)的虛擬機(jī)即可,其調(diào)度的虛擬機(jī)也沒有嚴(yán)格的限制.

2.2.2 副版本任務(wù)調(diào)度

下面分析任務(wù)vj的副版本任務(wù)執(zhí)行的最早開始時間.首先定義副版本調(diào)度滿足的約束條件,當(dāng)任務(wù)vj的主版本調(diào)度滿足狀態(tài)(2)或(3)時,它的副版本任務(wù)的開始時間必須滿足

當(dāng)任務(wù)vj的主版本調(diào)度滿足狀態(tài)(1)時,副版本任務(wù)的最遲開始時間必須滿足

任務(wù)vj的主版本調(diào)度滿足狀態(tài)(2)時,它的副版本任務(wù)的所能調(diào)度虛擬機(jī)滿足

任務(wù)vj的主版本調(diào)度滿足狀態(tài)(1)或(3)時,pred(vj)2表示集合pred(vj)中滿足狀態(tài)(1)或(3)的任務(wù)集合,pd(vj)為vj所有任務(wù)中與vj存在間接與直接依賴關(guān)系滿足狀態(tài)(1)或(3)的任務(wù)集合.由于

云計算環(huán)境下科學(xué)工作流任務(wù)調(diào)度的一個重要目標(biāo)是獲取任務(wù)的最早完成時間(Makespan).多DAG任務(wù)的最早完成時間可以用出口節(jié)點副版本的完成時間表示,CCRH尋求的副版本的最早開始時間,即完成了對整個任務(wù)調(diào)度策略的出口任務(wù)的副版本最早完成時間即可,即

2.3 多DAG分層調(diào)度

在云計算系統(tǒng)的多DAG調(diào)度模型中,由于一個DAG工作流a要與其他的DAG工作流爭用同一組計算資源,所以工作流a的Makespan(從提交DAG a開始到DAG a的最后一個任務(wù)執(zhí)行完畢所用的時間)很可能比a單獨使用該云計算環(huán)境的Makespan要長,這兩個Makespan可分別被表示為Mmulti(a)和Mown(a),文獻(xiàn)[12]定義Slowdown描述這一比值:SSlowdown=Mmulti(a)Mown(a),因此某個調(diào)度算法S的不公平程度因子UUn faines(s)定義為

3 實驗結(jié)果與分析

仿真實驗將算法與HEFT[12]、BMCT[13]分別采用公平因子調(diào)度后的公平性、調(diào)度時長、虛擬機(jī)利用率、任務(wù)運(yùn)行時間這4個方面性能進(jìn)行比較(HEFT的多DAG任務(wù)采用與文獻(xiàn)[13]相同的分層方法).為了更好體現(xiàn)算法在科學(xué)工作流調(diào)度中的優(yōu)勢,使用兩種類型的DAG任務(wù):隨機(jī)DAG任務(wù)、快速傅里葉變換(Fast Fourier Transform,FFT),其中每種類型的DAG包括2～10個DAG任務(wù),每個DAG包含10～50個任務(wù).使用CCR描述DAG任務(wù)圖中通信與計算比率,CCR的值選擇0.1～1的隨機(jī)數(shù).

實驗環(huán)境為Inter(R)Xeon E7420 2.13 GHz,RAM 4GB,硬盤1 TB的10臺服務(wù)器搭建具有30個虛擬計算平臺,為了模擬云計算平臺,在每個計算節(jié)點上使用虛擬化Xen創(chuàng)建了虛擬集群,以模擬數(shù)據(jù)中心的云計算環(huán)境,

3.1 公平性

算法的公平性能夠有效反應(yīng)調(diào)度算法在處理多個DAG任務(wù)時,能夠公平的對待不同優(yōu)先級以及不同時間提交的問題,實驗通過不同的科學(xué)工作流的DAG任務(wù),對CCRH、HEFT、BMCT算法的公平性進(jìn)行比較.圖1表示3種算法在隨機(jī)DAG任務(wù)、FFT下的DAG任務(wù)的公平性.由圖1可以看出,由于HEFT與BMCT采用相同的分層的方法,其公平性沒有太大的差異,而CCRH由于采用動態(tài)分層的方法,其公平性有了較大的提高,而且沒有出現(xiàn)較大的跳變現(xiàn)象.

3.2 算法Makespan

算法Makespan性能可以有效反應(yīng)不同調(diào)度算法的調(diào)度時長,實驗通過不同的科學(xué)工作流的DAG任務(wù),對CCRH、HEFT、BMCT算法的Makespan進(jìn)行比較.圖2表示3種算法在隨機(jī)DAG任務(wù)、FFT圖中的Makespan.由圖2可以看出,3種算法的Makespan性能均在可接受的范圍之內(nèi).其主要原因是,3種算法選擇相似的優(yōu)先級比較算法.BMCT優(yōu)于HEFT的原因是BMCT考慮任務(wù)之間的通信約束,而CCRH由于采用主副版本技術(shù),提高系統(tǒng)可靠性,但其副版本任務(wù)的執(zhí)行增加了算法的Makespan.可以看到,在提高系統(tǒng)可靠性的前提下,系統(tǒng)增加的Makespan在可接受的范圍內(nèi).

圖1 算法公平性比較

圖2 算法平均Makespan比較

3.3 大規(guī)模數(shù)據(jù)運(yùn)算時間

為了更好測試算法的在大規(guī)模數(shù)據(jù)運(yùn)算時的Makespan性能,驗證主副版本技術(shù)在提高系統(tǒng)可靠性同時,對計算性能的犧牲.實驗分別對比3種算法在隨機(jī)產(chǎn)生的100個DAG圖任務(wù)的運(yùn)行時間(Makespan)進(jìn)行比較,由圖3可以看出,HEFT在3種算法在40個任務(wù)時,其Makespan基本相同,隨后BMCT表現(xiàn)出較差的Makespan,在DAG任務(wù)達(dá)到80時,CCRH的Makespan性能下降較為明顯,在100個DAG任務(wù)時調(diào)度算法獲得的Makespan為原來的2倍,其犧牲的系統(tǒng)運(yùn)行時間在可接受范圍之內(nèi).

圖3 大規(guī)模數(shù)據(jù)運(yùn)行時間比較　

圖4 資源利用率比較

3.4 資源利用率

為了更好體現(xiàn)算法對云環(huán)境資源的利用,考查不同的科學(xué)工作流負(fù)載中,虛擬計算節(jié)點的平均使用情況.從圖4中可以看出,CCRH擁有較高的虛擬機(jī)利用率,因而在資源使用計費的云環(huán)境中,CCRH擁有較好的效益,并且能提高系統(tǒng)的負(fù)載均衡性.

4 結(jié)束語

筆者針對云計算系統(tǒng)中科學(xué)工作流的可靠調(diào)度問題,通過使用主副版本技術(shù),利用動態(tài)分層調(diào)度的方法,有效解決了多DAG調(diào)度的不公平性問題.仿真實驗表明,該算法在滿足可靠性要求的前提下,其公平性、Makespan、資源利用率、系統(tǒng)運(yùn)行時間均表現(xiàn)出較好的性能.

參考文獻(xiàn):

[1]WIECZOREK M,PRODAN R,FAHRINGER T.Scheduling of Scientific Workflows in the Askalon Grid Environment [J].SIGMOD Record,2005,3(34):56-62.

[2]MANDAL A.Scheduling Strategies for Mapping Application Workflows onto the Grid[C]//Proceedings of the 14th International Symposium on High Performance Distributed Computing.New York:ACM,2005:125-134.

[3]田國忠,肖創(chuàng)柏,徐竹勝,等.異構(gòu)分布式環(huán)境下多DAG工作流的混合調(diào)度策略[J].軟件學(xué)報,2012,23(10):2720-2734.TIAN Guozhong,XIAO Chuangbai,XU Zhusheng,et al.Hybrid Scheduling Strategy for Multiple DAGs Workflow in Heterogeneous System[J].Journal of Sofware,2012,23(10):2720-2734.

[4]ZHAO H,SAKELLARIOU R.Scheduling Multiple DAGs onto Heterogeneous Systems[C]//Proceedings of the 20th International Parallel and Distributed Processing Symposium.Piscataway:IEEE,2006:1639387.

[5]ZHANG J,SHA E H M,ZHUGE Q,et al.Efficient Fault-tolerant Scheduling on Multiprocessor Systems via Replication and Deallocation[J].International Journal of Embedded Systems,2014,6(2/3):216-224.

[6]BARUAH S,BONIFACI V,MARCHETTI-SPACCAMELA A,et al.A Generalized Parallel Task Model for Recurrent Real-time Processes[C]//Proceedings of the 33th Real-time Systems Symposium.Piscataway:IEEE,2012:63-72.

[7]RAJU R,AMUDHAVEL J,PAVITHRA M,et al.A Heuristic Fault Tolerant Mapreduce Framework for Minimizing Makespan in Hybrid Cloud Environment[C]//Proceedings of the IEEE International Conference on Green Computing,Communication and Electrical Engineering.Piscataway:IEEE,2014:6922462.

[8]XIE G Q,LI R F,LIU L,et al.DAG Reliability Model and Fault-tolerant Algorithm for Heterogeneous Distributed Systems[J].Information Processing Letters,2009,109(11):539-542.

[9]QIN X,JIANG H.A Novel Fault-tolerant Scheduling Algorithm for Precedence Constrained Tasks in Real-time Heterogeneous Systems[J].Parallel Computing,2006,32(5):331-356.

[10]SINNEN O,SOUSA L A.Toward a Realistic Task Scheduling Model[J].IEEE Transactions on Parallel and Distributed Systems,2006,17(3):263-275.

[11]景維鵬,吳智博,劉宏偉,等.支持優(yōu)先級約束任務(wù)的容錯調(diào)度算法[J].清華大學(xué)學(xué)報,2011,51(S1):1440-1444.JING WEIPENG,WU ZHIBO,LIU HONGWEI,et al.Fault-tolerant Scheduling Algorithm for Precedence Constrained Tasks[J].Tsinghua Science and Technology,2011,51(S1):1440-1444.

[12]MACEY B S,ZOMAYA A Y.A Performance Evaluation of CP List Scheduling Heuristics for Communication Intensive Task Graphs[C]//Proceedings of the International Parallel Processing Symposium.Los Alamitos:IEEE Computer Society,1998:538-541.

[13]TOPCUOGLU H,HARIRI S,WU M.Performance Effective and Low-complexity Task Scheduling for Heterogeneous Computing[J].IEEE Transactions on Parallel and Distributed Systems,2002,13(3):260-274.

[14]謝國琪,李仁發(fā),楊帆,等.異構(gòu)網(wǎng)絡(luò)化汽車電子系統(tǒng)中多DAG離線任務(wù)調(diào)度[J].通信學(xué)報,2013,34(12):20-32.XIE Guoqi,LI Renfa,YANG Fan,et al.Multiple DAG Off-line Task Scheduling for Heterogeneous Networked Automobile Electronic Systems[J].Journal on Communications,2013,34(12):20-32.

(編輯:王 瑞)

Multiple DAGs dynamic workflow reliability scheduling algorithm in a cloud computing system

JING Weipeng1,2,WU Zhibo1,LIU Hongwei1,SHU Yanjun1
(1.School of Computer Science and Technology,Harbin Institute of Technology,Harbin 150001,China; 2.The College of Information and Computer Engineering,Northeast Forestry Univ.,Harbin 150040,China)

Abstract:In order to solve the reliable scientific workflow scheduling problem for cloud computing,a dynamic of the RANK-Hierarchical algorithm is put forward which takes account of communication contention as well as supports task dependencies(CCRH).A communication contention model is first defined,as soon as the earliest completion of the primary and backup task is deduced.Besides,the executived processor is limited.We use the dynamic hierarchical method and calculate each DAG unfair degree factor for multiple DAGs scientific workflow.It can deal with the situation that multiple DAGs workflow comes at different times and there are various kinds of structure.Both the theory and experiments have proved that the algorithm can not only improve the scheduling fairness of multiple DAGs workflow but also shorten the average execution Makespan.

Key Words:cloud computing;multiple DAGs;reliability scheduling;degree factor

作者簡介:景維鵬(1979-),副教授,博士,E-mail:nefujwp@gmail.com.

基金項目:國家自然科學(xué)基金資助項目(61202091);國家863重大科技專項資助項目(2013AA01A215);哈爾濱市科技局科技創(chuàng)新人才基金資助項目(2014RFQXJ132)

收稿日期:2014-11-03 網(wǎng)絡(luò)出版時間:2015-05-21

doi:10.3969/j.issn.1001-2400.2016.02.015

中圖分類號:TP306

文獻(xiàn)標(biāo)識碼:A

文章編號:1001-2400(2016)02-0083-06

網(wǎng)絡(luò)出版地址:http://www.cnki.net/kcms/detail/61.1076.TN.20150521.0902.012.html