負(fù)載均衡優(yōu)先的改進(jìn)優(yōu)先級(jí)表調(diào)度算法*

葛維春， 葉 波

(1. 遼寧省電力公司 科技信通部， 沈陽(yáng) 110006； 2. 東北電力大學(xué) 信息工程學(xué)院， 吉林 吉林 132012)

電氣工程

負(fù)載均衡優(yōu)先的改進(jìn)優(yōu)先級(jí)表調(diào)度算法*

葛維春1， 葉 波2

(1. 遼寧省電力公司 科技信通部， 沈陽(yáng) 110006； 2. 東北電力大學(xué) 信息工程學(xué)院， 吉林 吉林 132012)

針對(duì)當(dāng)前云計(jì)算環(huán)境下DAG任務(wù)調(diào)度時(shí)存在的負(fù)載失衡、任務(wù)調(diào)度效率不高的問題，提出了一種負(fù)載均衡優(yōu)先的改進(jìn)優(yōu)先級(jí)表調(diào)度算法(LS-IPLB).算法將云計(jì)算集群中虛擬機(jī)的狀態(tài)參數(shù)變化抽象成空間中的參數(shù)向量變化，給出實(shí)時(shí)衡量云計(jì)算集群的負(fù)載均衡性方法，并作為虛擬機(jī)選擇權(quán)值的重要參數(shù).同時(shí)以任務(wù)執(zhí)行代價(jià)、任務(wù)的出度和任務(wù)間的通信代價(jià)作為參數(shù)計(jì)算任務(wù)優(yōu)先級(jí)，并在任務(wù)調(diào)度時(shí)采用任務(wù)復(fù)制策略進(jìn)一步優(yōu)化調(diào)度過程.結(jié)果表明，LS-IPLB算法能有效縮短DAG任務(wù)圖的完成時(shí)間，并實(shí)現(xiàn)了良好的負(fù)載均衡性.

云計(jì)算； DAG任務(wù)調(diào)度； 負(fù)載均衡； 執(zhí)行代價(jià)； 出度； 通信代價(jià)； 任務(wù)優(yōu)先級(jí)； 任務(wù)復(fù)制

當(dāng)前云計(jì)算集群對(duì)于獨(dú)立任務(wù)的調(diào)度已有成熟的理論與方法，并在實(shí)際中廣泛應(yīng)用.但是關(guān)于DAG任務(wù)的調(diào)度問題仍處于起步研究階段，近年來已引起國(guó)內(nèi)外研究者的廣泛關(guān)注，已有多種關(guān)于DAG任務(wù)調(diào)度方法被提出，并且所采用的調(diào)度策略和解決問題的角度各有不同.其中，優(yōu)先級(jí)表調(diào)度算法因其算法的高效性和易于實(shí)現(xiàn)而得到廣泛應(yīng)用[1-3].

文獻(xiàn)[4]提出的HEFT算法和文獻(xiàn)[5]提出的CPOP算法是當(dāng)前公認(rèn)的調(diào)度效率較高的算法.HEFT算法中任務(wù)優(yōu)先級(jí)別由ranku(從任務(wù)節(jié)點(diǎn)到出口節(jié)點(diǎn)的關(guān)鍵路徑長(zhǎng)度)值確定，任務(wù)調(diào)度時(shí)將任務(wù)分配到具有最小執(zhí)行時(shí)間的虛擬機(jī)上；而CPOP算法將ranku與rankd(從入口節(jié)點(diǎn)到任務(wù)的關(guān)鍵路徑長(zhǎng)度)的和作為權(quán)值來計(jì)算任務(wù)優(yōu)先級(jí).HEFT和CPOP算法分別以任務(wù)的向前和向后關(guān)鍵路徑作為優(yōu)先級(jí)計(jì)算權(quán)值，獲得了較好的全局調(diào)度效果，提升了任務(wù)執(zhí)行效率.單獨(dú)以ranku或者rankd作為權(quán)值計(jì)算任務(wù)優(yōu)先級(jí)容易陷入局部最優(yōu)，并且這兩種算法未采用任務(wù)復(fù)制策略，難以獲得更短調(diào)度時(shí)間的機(jī)會(huì).

文獻(xiàn)[6]提出了關(guān)鍵任務(wù)優(yōu)先調(diào)度算法，算法在每一步都賦予關(guān)鍵路徑節(jié)點(diǎn)最高優(yōu)先級(jí)，但該算法未對(duì)非關(guān)鍵路徑上任務(wù)進(jìn)行有效調(diào)度，一旦非關(guān)鍵任務(wù)調(diào)度失當(dāng)，勢(shì)必會(huì)影響算法調(diào)度性能；文獻(xiàn)[7]提出了改進(jìn)列表任務(wù)調(diào)度算法(HIPLTS)，賦予關(guān)鍵路徑上任務(wù)最高優(yōu)先級(jí)，但是優(yōu)先級(jí)計(jì)算未考慮通信代價(jià)影響，也未考慮系統(tǒng)負(fù)載均衡性.

圖1 LS-IPLB算法原理圖

算法提出了云計(jì)算系統(tǒng)負(fù)載均衡性量度，以兼顧調(diào)度過程中系統(tǒng)的負(fù)載均衡性；在確定任務(wù)優(yōu)先級(jí)時(shí)未單獨(dú)采用ranku或者rankd作為參考量，而是重點(diǎn)考慮了任務(wù)的執(zhí)行代價(jià)、任務(wù)間的通信代價(jià)對(duì)任務(wù)優(yōu)先級(jí)的影響，使計(jì)算出的優(yōu)先級(jí)能夠較準(zhǔn)確地反映出特定DAG任務(wù)圖的內(nèi)在關(guān)系；在處理器選擇階段，提出一種根據(jù)當(dāng)前狀態(tài)計(jì)算權(quán)值、選擇虛擬機(jī)的策略；在任務(wù)分配過程中，運(yùn)用前驅(qū)任務(wù)復(fù)制技術(shù)，達(dá)到減少任務(wù)通信代價(jià)、提高處理器利用率的目的.

1 系統(tǒng)負(fù)載均衡度定義

1.1 計(jì)算節(jié)點(diǎn)數(shù)學(xué)模型

對(duì)于云計(jì)算集群的虛擬機(jī)節(jié)點(diǎn)，其工作狀態(tài)可用一個(gè)參數(shù)向量來表示，如具有k個(gè)狀態(tài)參數(shù)的虛擬機(jī)，其參數(shù)向量可表示為a=(?1，?2，…，?k)，k個(gè)狀態(tài)參數(shù)構(gòu)成k維的參數(shù)向量空間.當(dāng)節(jié)點(diǎn)接收任務(wù)進(jìn)行處理時(shí)，其各個(gè)參數(shù)值將會(huì)發(fā)生變化，此時(shí)參數(shù)變化值即反映了虛擬機(jī)當(dāng)前工作狀態(tài)的變化.假設(shè)云計(jì)算集群中虛擬機(jī)個(gè)數(shù)為M，任務(wù)調(diào)度時(shí)根據(jù)虛擬機(jī)各個(gè)參數(shù)的狀態(tài)進(jìn)行合理任務(wù)分配.假設(shè)各個(gè)參數(shù)在當(dāng)前系統(tǒng)中進(jìn)行調(diào)度時(shí)的權(quán)重分別為a1，a2，…，ak，令a1+a2+…+ak=1，則虛擬機(jī)狀態(tài)參數(shù)集合為

0≤xi2≤a2，…，0≤xik≤ak}

(1)

該平均值G(X1，X2，…，Xk)是各虛擬機(jī)投影到參數(shù)向量空間中的重心位置，它是判斷集群整體負(fù)載情況的重要參數(shù).通過將服務(wù)器節(jié)點(diǎn)映射到參數(shù)向量空間，可以更直觀地研究云計(jì)算集群的負(fù)載狀況.如果節(jié)點(diǎn)聚集于重心的周圍，則集群負(fù)載較為均衡；如果節(jié)點(diǎn)投影點(diǎn)在投影空間中的映射分散，則集群負(fù)載不均衡，負(fù)載均衡狀況比較差.

1.2 負(fù)載均衡度定義

為評(píng)估集群的負(fù)載均衡狀況，可用各虛擬機(jī)投影點(diǎn)與重心距離的標(biāo)準(zhǔn)差歸一化值進(jìn)行衡量，定義該值為集群負(fù)載均衡度，用LB表示，即

(2)

負(fù)載均衡度LB表示某時(shí)刻任務(wù)分配到虛擬機(jī)上執(zhí)行時(shí)，系統(tǒng)負(fù)載均衡度的大小，因此，負(fù)載均衡度LB是實(shí)時(shí)衡量云計(jì)算集群負(fù)載均衡性的指標(biāo).顯然，系統(tǒng)負(fù)載均衡度的取值范圍為[0，1]，負(fù)載均衡度越小，表明當(dāng)前系統(tǒng)的負(fù)載均衡狀況越好.它將作為虛擬機(jī)選擇權(quán)值參數(shù)，以兼顧任務(wù)調(diào)度時(shí)集群的負(fù)載均衡性.

2 DAG任務(wù)模型

為描述關(guān)聯(lián)任務(wù)組，本文構(gòu)建了關(guān)聯(lián)任務(wù)的DAG圖.任務(wù)由DAG圖中的節(jié)點(diǎn)表示，執(zhí)行的先后次序由DAG中的邊表示.

G={V，E，W，C}表示一個(gè)具有4個(gè)元組的關(guān)聯(lián)任務(wù)組，各元素表示如下：

3)W為一個(gè)N×M的矩陣，表示N個(gè)任務(wù)在M個(gè)虛擬機(jī)上的執(zhí)行代價(jià)集合，元素w(vi，pm)表示任務(wù)vi在虛擬機(jī)pm上的執(zhí)行代價(jià)，任務(wù)vi的平均執(zhí)行代價(jià)定義為

(3)

4) 集合C表示任務(wù)之間的通信花費(fèi)集合，當(dāng)兩個(gè)具有直接關(guān)聯(lián)關(guān)系的任務(wù)被分配至同一資源執(zhí)行時(shí)，任務(wù)間的通信代價(jià)為0.

為了方便描述任務(wù)調(diào)度問題，還要給出DAG任務(wù)圖中的入口節(jié)點(diǎn)、出口節(jié)點(diǎn)、任務(wù)的前驅(qū)節(jié)點(diǎn)集合、任務(wù)的后繼節(jié)點(diǎn)集合、開始執(zhí)行時(shí)間及最早完成時(shí)間等變量的定義.

定義1 沒有前驅(qū)節(jié)點(diǎn)的任務(wù)為入口節(jié)點(diǎn)，沒有后繼節(jié)點(diǎn)的任務(wù)為出口節(jié)點(diǎn).如果DAG圖中有不止一個(gè)入口節(jié)點(diǎn)，那么添加一個(gè)零計(jì)算代價(jià)的偽入口節(jié)點(diǎn)，并分別用邊權(quán)值為0的邊指向入口節(jié)點(diǎn)，出口節(jié)點(diǎn)同理.

定義2DAG任務(wù)圖中，任務(wù)vi的直接前驅(qū)任務(wù)節(jié)點(diǎn)集合為vi的父節(jié)點(diǎn)集合，記作pred(vi)；任務(wù)節(jié)點(diǎn)vi的直接后繼任務(wù)節(jié)點(diǎn)集合為vi的子節(jié)點(diǎn)集合，記作inhe(vi).

通常任務(wù)vi在虛擬機(jī)pm上的啟動(dòng)時(shí)間受到兩個(gè)因素的制約，其表述如下：

1) 任務(wù)vi在虛擬機(jī)pm上的起始可用時(shí)間.虛擬機(jī)pm上的起始可用時(shí)間是指從任務(wù)vi分配到虛擬機(jī)pm上至要執(zhí)行任務(wù)vi時(shí)的時(shí)間間隔，用usa(pm)表示.若剛完成被分配任務(wù)即執(zhí)行，則有

usa(pm)=ct(vt，pm)

(4)

式中，ct(vt，pm)為任務(wù)vt在pm上的完成時(shí)間.

2) 任務(wù)vi的直接前驅(qū)任務(wù)執(zhí)行結(jié)果傳遞到虛擬機(jī)pm的時(shí)間.任務(wù)vi開始執(zhí)行的前提是虛擬機(jī)pm接收到其所有直接前驅(qū)任務(wù)的執(zhí)行結(jié)果，由此可計(jì)算任務(wù)vi在虛擬機(jī)pm上開始執(zhí)行時(shí)間，用st(vi，pm)表示，即

C(ei，j))]

(5)

式中，C(ei，j)為執(zhí)行結(jié)果傳遞到虛擬機(jī)的時(shí)間.任務(wù)vi在虛擬機(jī)pm上的完成時(shí)間ct(vi，pm)為任務(wù)vi在虛擬機(jī)pm上開始執(zhí)行時(shí)間與執(zhí)行時(shí)間之和，即

ct(vi，pm)=st(vi，pm)+w(vi，pm)

(6)

圖2為一個(gè)關(guān)聯(lián)任務(wù)組DAG圖，該關(guān)聯(lián)任務(wù)組有8個(gè)任務(wù)組成，v1為入口任務(wù)，v8為出口任務(wù)，任務(wù)間的依賴關(guān)系由圖中有向邊給出；任務(wù)之間的通信花費(fèi)由圖中數(shù)字所示；虛線框中的任務(wù)為同級(jí)任務(wù)，即它們是前級(jí)任務(wù)的直接后繼任務(wù).

圖2 關(guān)聯(lián)任務(wù)DAG圖

3 LS-IPLB算法分析

3.1 任務(wù)優(yōu)先級(jí)計(jì)算

本文提出的LS-IPLB算法流程圖如圖3所示.為任務(wù)設(shè)置優(yōu)先級(jí)能夠?qū)崿F(xiàn)任務(wù)調(diào)度時(shí)的公平和效率，本文修改了表調(diào)度算法HEFT的優(yōu)先級(jí)別計(jì)算公式，增加了任務(wù)的出度值和任務(wù)的出口通信值兩個(gè)關(guān)鍵因子.任務(wù)節(jié)點(diǎn)vi的出度是指該任務(wù)的直接后繼任務(wù)的數(shù)目，用H(vi)表示，分析認(rèn)為任務(wù)出度值越大，對(duì)后續(xù)任務(wù)執(zhí)行的影響越大，該任務(wù)的優(yōu)先執(zhí)行能夠提高后續(xù)任務(wù)的并發(fā)執(zhí)行程度.任務(wù)節(jié)點(diǎn)vi的出口通信值是指該任務(wù)所有出口邊通信時(shí)間之和，用B(vi)表示，即

(7)

圖3 LS-IPLB算法流程圖

分析認(rèn)為任務(wù)的出口通信值B(vi)越大，對(duì)后繼任務(wù)的影響越大，它的優(yōu)先執(zhí)行能夠有效減少后繼任務(wù)等待時(shí)間，從而提前后繼任務(wù)的開始執(zhí)行時(shí)間.綜合考慮以上兩個(gè)重要影響因子，提出了新的優(yōu)先級(jí)計(jì)算方法，即

PR(vi)=(αH(vi)+βB(vi))SL(vi)

(8)

(9)

3.2 虛擬機(jī)選擇

本文采用全職分配原則，以獲得全局最小任務(wù)完成時(shí)間為目標(biāo)，以負(fù)載均衡度與當(dāng)前時(shí)刻任務(wù)vi向后關(guān)鍵路徑的執(zhí)行時(shí)間為權(quán)值，為任務(wù)選擇權(quán)值較小的虛擬機(jī)進(jìn)行調(diào)度.任務(wù)vi的虛擬機(jī)選擇權(quán)值swi，m定義為

INHE_KEY(vi))LB)

(10)

式中：LB為負(fù)載均衡度；INHE_KEY(vi)=HE_KEY(vj)+C(ei，j)+w(vi，pm)；HE_KEY(vi)為vi的關(guān)鍵后繼任務(wù)集合.

3.3 任務(wù)調(diào)度及任務(wù)復(fù)制

調(diào)度開始時(shí)，深度遍歷DAG任務(wù)圖，得到任務(wù)圖的關(guān)鍵路徑，任務(wù)調(diào)度時(shí)賦予同級(jí)任務(wù)中關(guān)鍵路徑上任務(wù)最高優(yōu)先級(jí)，對(duì)于非關(guān)鍵任務(wù)按照PR(vi)值進(jìn)行降序排列，對(duì)于PR(vi)值相同的任務(wù)，則選擇后繼任務(wù)數(shù)多的優(yōu)先調(diào)度.

從任務(wù)隊(duì)列中選擇優(yōu)先級(jí)最高的，將其調(diào)度到swi，m最大的虛擬機(jī)上，此時(shí)，若存在多個(gè)相同swi，m值虛擬機(jī)，則選擇負(fù)載均衡度值較小的虛擬機(jī)進(jìn)行任務(wù)調(diào)度.

為進(jìn)一步縮短任務(wù)執(zhí)行時(shí)間，提高處理器運(yùn)行效率，算法采用任務(wù)復(fù)制技術(shù)對(duì)調(diào)度過程進(jìn)行優(yōu)化.任務(wù)vi的直接前驅(qū)任務(wù)按優(yōu)先級(jí)排列的集合為

pred(vi)={vi，1，vi，2，…，vi，n}

(11)

若任務(wù)vi，1滿足

C(ei，i，y))

則稱vi，1為任務(wù)vi的關(guān)鍵前驅(qū)節(jié)任務(wù).將當(dāng)前任務(wù)vi的關(guān)鍵前驅(qū)節(jié)任務(wù)vi，1復(fù)制到目標(biāo)虛擬機(jī)pm上，可以提前任務(wù)的最早執(zhí)行時(shí)間.定義約束條件為任務(wù)vi，1復(fù)制到虛擬機(jī)pm上的執(zhí)行時(shí)間小于任務(wù)vi，1分配到虛擬機(jī)px上的執(zhí)行時(shí)間與執(zhí)行結(jié)果傳遞到虛擬機(jī)pm上的時(shí)間C(ei，1，i)之和，即

ct(vi，1，pm)

(12)

若約束條件式(12)不滿足，則考察任務(wù)vi的直接前驅(qū)任務(wù)層中優(yōu)先級(jí)次大的前驅(qū)任務(wù)vi，2，可將其調(diào)度到任務(wù)vi所在虛擬機(jī)的空閑時(shí)間槽fts(vi，pm)上執(zhí)行，縮短DAG任務(wù)圖的完成時(shí)間.定義約束條件為任務(wù)vi，2在虛擬機(jī)pm上的執(zhí)行代價(jià)w(vi，2，pm)小于空閑時(shí)間槽fts(vi，pm)的長(zhǎng)度，即

fts(vi，pm)>w(vi，2，pm)

(13)

若任務(wù)vi有兩個(gè)以上的前驅(qū)任務(wù)，則繼續(xù)考察任務(wù)vi，3，此時(shí)空閑時(shí)間槽更新為

f=fts(vi，pm)-w(vi，2，pm)

(14)

其約束條件為

fts(vi，pm)-w(vi，2，pm)≥w(vi，3，pm)

(15)

繼續(xù)考察剩下的前驅(qū)任務(wù)，直到不再滿足終止復(fù)制約束條件為止，此時(shí)虛擬機(jī)空閑時(shí)間槽小于任何一個(gè)待調(diào)度前驅(qū)任務(wù)的執(zhí)行時(shí)間，終止復(fù)制約束條件為

(2≤r≤n)

(16)

4 仿真實(shí)驗(yàn)結(jié)果與分析

為評(píng)價(jià)LS-IPLB算法的性能，本文在CloudSimToolkit環(huán)境中進(jìn)行模擬實(shí)驗(yàn)，通過改寫DatacenterBroker類中的bindCloudletToVm方法，添加本文的LS-IPLB調(diào)度算法，并且使用Ant工具對(duì)平臺(tái)進(jìn)行重新編譯，將LS-IPLB調(diào)度算法加入到模擬平臺(tái)的任務(wù)調(diào)度單元中進(jìn)行實(shí)驗(yàn).在相同的環(huán)境配置下，實(shí)驗(yàn)選取與本文算法在各方面性能具有可比性的經(jīng)典表調(diào)度算法HEFT、文獻(xiàn)[7]改進(jìn)優(yōu)先級(jí)調(diào)度算法(HIPLTS)、文獻(xiàn)[9]基于任務(wù)復(fù)制的調(diào)度算法(HNDP)進(jìn)行比較.實(shí)驗(yàn)考查算法的3個(gè)影響因素：負(fù)載均衡度、DAG任務(wù)圖中任務(wù)個(gè)數(shù)N及不同任務(wù)類型對(duì)調(diào)度算法的影響，因此設(shè)置了2組對(duì)比試驗(yàn)，分別測(cè)試4種算法的負(fù)載均衡性以及不同通信計(jì)算比的任務(wù)調(diào)度長(zhǎng)度.

本仿真實(shí)驗(yàn)在戴爾Xeon E5-2609 v3服務(wù)器上創(chuàng)建了40個(gè)虛擬機(jī)作為計(jì)算節(jié)點(diǎn)，用于50～450個(gè)獨(dú)立任務(wù)的調(diào)度.虛擬機(jī)VM到主機(jī)的映射分配由Cloudsim自帶的Time-Shared算法實(shí)現(xiàn)，虛擬機(jī)的屬性如表1所示，任務(wù)的屬性表如表2所示.

表1 虛擬機(jī)屬性

表2 任務(wù)屬性

實(shí)驗(yàn)1 負(fù)載均衡性測(cè)試

(17)

顯然，系統(tǒng)方差值越小，系統(tǒng)負(fù)載均衡性越好.根據(jù)式(17)與式(2)得出的實(shí)驗(yàn)結(jié)果分別如圖4、5所示.

圖4 期望處理時(shí)間方差

圖5 負(fù)載均衡度

從圖4中可以看出，隨著任務(wù)數(shù)的增大，HIPLTS算法、HNDP算法和HEFT算法都出現(xiàn)了較為明顯的負(fù)載失衡，而本文LS-IPLB算法引入負(fù)載均衡度后，算法呈現(xiàn)出良好的負(fù)載均衡性，δ值小于其他3種算法；從圖5可以看出，其實(shí)驗(yàn)結(jié)果與圖4的結(jié)果一致，LS-IPLB算法的負(fù)載均衡LB值從開始就小于其余3個(gè)算法，且隨著任務(wù)數(shù)的增大，LB值趨于穩(wěn)定.實(shí)驗(yàn)結(jié)果表明，LS-IPLB算法具有很好的負(fù)載均衡特性，并且適用于當(dāng)前較大規(guī)模云計(jì)算集群的任務(wù)調(diào)度.

實(shí)驗(yàn)2 不同類型任務(wù)對(duì)算法的影響測(cè)試

衡量一個(gè)任務(wù)調(diào)度算法的基本評(píng)判標(biāo)準(zhǔn)是DAG任務(wù)圖中全部任務(wù)的完成時(shí)間，本文采用文獻(xiàn)[3]中的調(diào)度長(zhǎng)度比率作為對(duì)調(diào)度策略性能的評(píng)價(jià)指標(biāo)，其定義為

(18)

式中：max(ct(vk，pm))為DAG任務(wù)圖的最多完成時(shí)間；CPCC為關(guān)鍵路徑上的任務(wù)計(jì)算代價(jià)之和.顯然，SLR≥1，且SLR越小，說明當(dāng)前調(diào)度策略下DAG任務(wù)圖完成時(shí)間越短，算法性能越好.

實(shí)驗(yàn)設(shè)置10個(gè)性能相異的虛擬機(jī)，測(cè)試30個(gè)不同的DAG任務(wù)圖.定義DAG任務(wù)圖中全部任務(wù)節(jié)點(diǎn)通信代價(jià)總和與全部任務(wù)節(jié)點(diǎn)計(jì)算代價(jià)總和之比為通信計(jì)算比，即

(19)

顯然，CER能夠反映DAG任務(wù)是計(jì)算密集型任務(wù)還是通信密集型任務(wù).

試驗(yàn)分別設(shè)置CER=0.5和CER=10來模擬計(jì)算密集型任務(wù)與通信密集型任務(wù)，圖6、7為通過多次重復(fù)實(shí)驗(yàn)得出的調(diào)度長(zhǎng)度比率的平均結(jié)果.

圖7 CER=10時(shí)算法調(diào)度長(zhǎng)度比率

從圖6可以看出，隨著任務(wù)數(shù)增加，LS-IPLB算法和HIPLTS算法優(yōu)于其他2個(gè)算法，這是由于CER=0.5時(shí)，DAG任務(wù)屬于計(jì)算密集型任務(wù)，任務(wù)間的通信代價(jià)占比較低，冗余復(fù)制并不能明顯減少任務(wù)間的通信代價(jià).但本文改進(jìn)的任務(wù)優(yōu)先級(jí)計(jì)算和虛擬機(jī)選擇策略能更有效地把任務(wù)分配到合適的虛擬機(jī)上.本文算法在虛擬機(jī)選擇時(shí)加入了負(fù)載均衡度參數(shù)，使系統(tǒng)中的虛擬機(jī)始終處于較好的負(fù)載均衡狀況，虛擬機(jī)計(jì)算資源得到了更充分的利用，隨著任務(wù)數(shù)量的增加，優(yōu)勢(shì)逐漸顯現(xiàn).

從圖7可以看出，當(dāng)CER=10時(shí)，DAG圖中任務(wù)屬于通信密集型任務(wù)，LS-IPLB算法和HNDP算法優(yōu)于其他兩種算法，利用冗余復(fù)制機(jī)制能有效減少任務(wù)間通信代價(jià).本文算法在調(diào)度時(shí)賦予同一級(jí)上關(guān)鍵路徑任務(wù)為最高優(yōu)先級(jí)，并優(yōu)先復(fù)制關(guān)鍵前驅(qū)任務(wù)，使得算法取得了明顯的調(diào)度性能.

5 結(jié) 論

本文提出了負(fù)載均衡優(yōu)先的改進(jìn)優(yōu)先級(jí)表調(diào)度算法(LS-IPLB)，在改進(jìn)表調(diào)度算法任務(wù)調(diào)度策略的同時(shí)，加入任務(wù)負(fù)載均衡度理論，得到了較理想的任務(wù)調(diào)度結(jié)果.實(shí)驗(yàn)表明，該算法實(shí)現(xiàn)了良好的負(fù)載均衡特性，尤其適用于較大規(guī)模云計(jì)算集群的任務(wù)調(diào)度.算法是在虛擬機(jī)之間全互聯(lián)情況下提出的，沒有考慮更復(fù)雜的非全互聯(lián)環(huán)境，本文算法的DAG任務(wù)與實(shí)際關(guān)聯(lián)任務(wù)有差別，今后可考慮更為復(fù)雜的接近實(shí)際云任務(wù)的DAG模型，設(shè)計(jì)更合理的調(diào)度算法.

[1]林偉偉，齊德昱.云計(jì)算資源調(diào)度研究綜述 [J].計(jì)算機(jī)科學(xué)，2012，39(10)：1-6.

(LIN Wei-wei，QI De-yu.Survey of resource in cloud computing [J].Computer Science，2012，39(10)：1-6.)

[2]郭力爭(zhēng)，趙曙光，姜長(zhǎng)遠(yuǎn).云計(jì)算環(huán)境下基于關(guān)聯(lián)量的數(shù)據(jù)部署與任務(wù)調(diào)度 [J].計(jì)算機(jī)工程與科學(xué)，2013，35(8)：1-7.

(GUO Li-zheng，ZHAO Shu-guang，JIANG Chang-yuan.Data placement and task scheduling based on associated amount in cloud computing [J].Computer Engineering and Science，2013，35(8)：1-7.)

[3]張曉磊.云計(jì)算獨(dú)立任務(wù)及關(guān)聯(lián)任務(wù)調(diào)度算法研究 [D].重慶：重慶大學(xué)，2014.

(ZHANG Xiao-lei.Study on scheduling slgorithm of the independent and associated for cloud computing [D].Chongqing：Chongqing University，2014.)

[4]Topcuoglu H，Hariri S，Wu M Y.Performance-effective and low-complexity task scheduling for heterogeneous computing [J].IEEE Transactions on Parallel and Distributed Systems，2002，13(3)：260-274.

[5]Buyya R，Yeo C S，Venugopal S，et al.Cloud computing and emerging IT platforms：vision，hype and reality for delivering computing as the 5th utility [J].Future Generation Computer Systems，2009，25(6)：599-616.

[6]Jane?ek T J.A high performance，low complexity algorithm for compile-time task scheduling in heterogeneous systems [J].Parallel Computing，2015，31(7)：653-670.

[7]李靜梅，王雪，吳艷霞.一種改進(jìn)的優(yōu)先級(jí)列表任務(wù)調(diào)度算法 [J].計(jì)算機(jī)科學(xué)，2014，41(5)：20-23.

(LI Jing-mei，WANG Xue，WU Yan-xia.Improved priority task scheduling algorithm [J].Computer Science，2014，41(5)：20-23.)

[8]王鵬，黃焱，李坤，等.云計(jì)算系統(tǒng)相空間分析模型及仿真研究 [J].計(jì)算機(jī)研究與發(fā)展，2013，36(2)：286-296.

(WANG Peng，HUANG Yan，LI Kun，et al.Load ba-lancing degree first algorithm on phase space for cloud computing cluster [J].Journal of Computer Research and Development，2013，36(2)：286-296.)

[9]孟憲福，劉偉偉.基于選擇性復(fù)制前驅(qū)任務(wù)的DAG調(diào)度算法 [J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2010，22(6)：1056-1062.

(MENG Xian-fu，LIU Wei-wei.A DAG scheduling algorithm based on selected duplication of precedent tasks [J].Journal of Computer-Aided Design and Computer Graphics，2010，22(6)：1056-1062.)

[10]宮華，張彪，許可.并行機(jī)生產(chǎn)與成批配送協(xié)調(diào)調(diào)度問題的近似策略 [J].沈陽(yáng)工業(yè)大學(xué)學(xué)報(bào)，2015，37(3)：324-328.

(GONG Hua，ZHANG Biao，XU Ke.Approximation strategy for coordinated Scheduling problem in production and batch delivery of parallel machines [J].Journal of Shenyang University of Technology，2015，37(3)：324-328.)

(責(zé)任編輯：景 勇 英文審校：尹淑英)

List scheduling algorithm of improved priority with considering load balance

GE Wei-chun1, YE Bo2

(1. Science and Technology Communication Department, Liaoning Province Electric Power Company, Shenyang 110006, China; 2. College of Information Engineering, Northeast Dianli University, Jilin 132012, China)

Aiming at such problems as the load imbalance and low efficiency of DAG task scheduling in the current cloud computing environment, a list scheduling algorithm of improved priority with considering load balance (LS-IPLB) was proposed. In the algorithm, the state parameter change of virtual machine in the cloud computing cluster was abstracted into the parameter vector variation in the space, and the real-time measurement method for the load balance of cloud computing cluster was given, which was taken as an important parameter to select the weight of virtual machine. At the same time, the task priority was calculated through taking the task execution cost, task output value and communication cost between the tasks as the parameters. In addition, the task duplication strategy was used in the task scheduling to further optimize the scheduling process. The results show that the LS-IPLB algorithm can effectively shorten the completion time of DAG task graph, and can achieve good load balance.

cloud computing; DAG task scheduling; load balance; execution cost; output value; communication cost; task priority; task duplication

2017-03-28.

國(guó)家電網(wǎng)公司電力云計(jì)算服務(wù)試點(diǎn)平臺(tái)建設(shè)項(xiàng)目(0711-140TL21112001).

葛維春(1961-)，男，遼寧沈陽(yáng)人，教授級(jí)高級(jí)工程師，博士，主要從事電力系統(tǒng)分析計(jì)算及科技管理等方面的研究.

10.7688/j.issn.1000-1646.2017.03.01

TP 391.9

A

1000-1646(2017)03-0241-07

*本文已于2017-05-08 20∶25在中國(guó)知網(wǎng)優(yōu)先數(shù)字出版. 網(wǎng)絡(luò)出版地址： http：∥www.cnki.net/kcms/detail/21.1189.T.20170508.2025.016.html