陳俊宇

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

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

1引言

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

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

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

2.1工作流定義

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

定義1 （W）.W=

W為工作流。

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

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

2.2服務(wù)商定義

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

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

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

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

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

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

5結(jié)束語(yǔ)

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