陳俊宇

關(guān)鍵詞：云環(huán)境；數(shù)據(jù)密集型；分層調(diào)度；最大傳輸路徑

中圖法分類號：TP393 文獻(xiàn)標(biāo)識碼：A

1引言

云平臺一直以來為眾多工作流應(yīng)用程序的調(diào)度提供高效的執(zhí)行環(huán)境，大量研究者對云環(huán)境下數(shù)據(jù)密集型工作流調(diào)度問題展開相關(guān)工作和研究。秦生輝提出了基于流程分割的數(shù)據(jù)密集型工作流調(diào)度方法，滿足了執(zhí)行中跨節(jié)點跨數(shù)據(jù)傳輸?shù)膬?yōu)化需求。杜清華等提出了一種高效的跨平臺工作流優(yōu)化方法，基于GGFN的成本模型和延遲貪婪剪枝方法縮短運行時間。李敬偉等提出了一種基于局部數(shù)據(jù)位置感知資源管理的調(diào)度方法，在提高資源利用率的同時，大幅度提高工作流的調(diào)度效率。

本文提出了一種基于最大數(shù)據(jù)傳輸路徑的數(shù)據(jù)密集型工作流調(diào)度方法，先對工作流中所有任務(wù)進(jìn)行分層排列，并尋找工作流中的最大數(shù)據(jù)傳輸量路徑，分配完最大數(shù)據(jù)傳輸量路徑上的任務(wù)后開始逐層調(diào)度，對其余任務(wù)進(jìn)行調(diào)度。

2數(shù)據(jù)密集型工作流調(diào)度流程

2.1工作流定義

本文調(diào)度的工作流通過有向無環(huán)圖表示。具體如定義1所示。

定義1 （W）.W=

W為工作流。

T={t｜i=1…n}，T表示W(wǎng)中的任務(wù)集合，t表示工作流W的第i個任務(wù)。

D={d，j=1…n}，D表示W(wǎng)中任務(wù)之間傳輸數(shù)據(jù)量的集合，其中d表示t向t傳輸?shù)臄?shù)據(jù)量。

2.2服務(wù)商定義

若干個云服務(wù)商參與工作流的調(diào)度，不同服務(wù)商調(diào)度任務(wù)會產(chǎn)生一定的執(zhí)行時間，對于有直接數(shù)據(jù)依賴的2個任務(wù)，若同時分配至相同的服務(wù)商，則傳輸時間可忽略不計。

4實驗分析

本文對比算法選擇HEFT算法[5]和Min-Min算法，并隨機(jī)生成工作流作為實驗輸入。

（1）驗證數(shù)據(jù)傳輸量對工作流完成時間的影響，任務(wù)傳輸量設(shè)置[200，400]、[400，600]、[600，800]、[800，1000]4個區(qū)間，任務(wù)數(shù)量為50，服務(wù)商數(shù)量為10，服務(wù)商執(zhí)行任務(wù)時間設(shè)置為[ 400，500]，從實驗數(shù)據(jù)得出，任務(wù)之間的傳輸量在[10，200]內(nèi)，優(yōu)化力度較小，當(dāng)任務(wù)之間的傳輸量在[ 800，1000]內(nèi)，分層調(diào)度法在完成時間上，相比于HEFT算法降低了14%，相比于Min-Min降低了23.5%。

（2）按照任務(wù)數(shù)量來比較，工作流任務(wù)的數(shù)量設(shè)置為[20，30，40，50]，每種任務(wù)數(shù)量將對應(yīng)隨機(jī)生成依賴關(guān)系不同的工作流，任務(wù)之間的傳輸量設(shè)置為[400，600]，服務(wù)商個數(shù)為10，服務(wù)商執(zhí)行任務(wù)時間設(shè)置為[100，200]，從實驗數(shù)據(jù)得出，當(dāng)傳輸量比重大于執(zhí)行時間時，任務(wù)數(shù)量越多，分層調(diào)度法在完成時間上，優(yōu)化力度越大，相比于HEFT最高降低了15%，相比于Min-Min最高降低了19%。

（3）按照執(zhí)行時間來進(jìn)行比較，執(zhí)行時間范圍設(shè)置為[ 100，200]、[200，300].[300，400]、[400，500]4個區(qū)間，傳輸量設(shè)置為[200，300]，任務(wù)個數(shù)為20，服務(wù)商個數(shù)為10，生成結(jié)果取平均值，從實驗數(shù)據(jù)得出，當(dāng)傳輸量比重大于執(zhí)行時間時，任務(wù)數(shù)量越多，分層調(diào)度法在完成時間上，優(yōu)化力度越大，相反，當(dāng)傳輸量比重小于執(zhí)行時間時，分層調(diào)度法不具有優(yōu)勢。

5結(jié)束語

本文提出了一種基于最大數(shù)據(jù)傳輸路徑的數(shù)據(jù)密集型工作流調(diào)度方法，首先對工作流進(jìn)行分層，找出工作流中最大數(shù)據(jù)傳輸量路徑并對該路徑進(jìn)行分配工作。然后對其余任務(wù)分配服務(wù)商，以此縮短工作流的完成時間。最后通過具體實驗證實了本文方法的可行性，并通過算法對比驗證了本文方法的有效性。在今后的工作中，我們將考慮對預(yù)算受限的工作流進(jìn)行更深入的研究。