葛維春， 葉 波

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

電氣工程

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

葛維春1， 葉 波2

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

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

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

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

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

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

圖1 LS-IPLB算法原理圖

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

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

1.1 計算節(jié)點數(shù)學(xué)模型

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

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

(1)

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

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

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

(2)

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

2 DAG任務(wù)模型

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

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

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

(3)

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

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

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

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

通常任務(wù)vi在虛擬機pm上的啟動時間受到兩個因素的制約，其表述如下：

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

usa(pm)=ct(vt，pm)

(4)

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

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

C(ei，j))]

(5)

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

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

(6)

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

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

3 LS-IPLB算法分析

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

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

(7)

圖3 LS-IPLB算法流程圖

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

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

(8)

(9)

3.2 虛擬機選擇

本文采用全職分配原則，以獲得全局最小任務(wù)完成時間為目標(biāo)，以負(fù)載均衡度與當(dāng)前時刻任務(wù)vi向后關(guān)鍵路徑的執(zhí)行時間為權(quán)值，為任務(wù)選擇權(quán)值較小的虛擬機進(jìn)行調(diào)度.任務(wù)vi的虛擬機選擇權(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)度開始時，深度遍歷DAG任務(wù)圖，得到任務(wù)圖的關(guān)鍵路徑，任務(wù)調(diào)度時賦予同級任務(wù)中關(guān)鍵路徑上任務(wù)最高優(yōu)先級，對于非關(guān)鍵任務(wù)按照PR(vi)值進(jìn)行降序排列，對于PR(vi)值相同的任務(wù)，則選擇后繼任務(wù)數(shù)多的優(yōu)先調(diào)度.

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

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

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)虛擬機pm上，可以提前任務(wù)的最早執(zhí)行時間.定義約束條件為任務(wù)vi，1復(fù)制到虛擬機pm上的執(zhí)行時間小于任務(wù)vi，1分配到虛擬機px上的執(zhí)行時間與執(zhí)行結(jié)果傳遞到虛擬機pm上的時間C(ei，1，i)之和，即

ct(vi，1，pm)

(12)

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

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

(13)

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

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ù)制約束條件為止，此時虛擬機空閑時間槽小于任何一個待調(diào)度前驅(qū)任務(wù)的執(zhí)行時間，終止復(fù)制約束條件為

(2≤r≤n)

(16)

4 仿真實驗結(jié)果與分析

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

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

表1 虛擬機屬性

表2 任務(wù)屬性

實驗1 負(fù)載均衡性測試

(17)

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

圖4 期望處理時間方差

圖5 負(fù)載均衡度

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

實驗2 不同類型任務(wù)對算法的影響測試

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

(18)

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

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

(19)

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

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

圖7 CER=10時算法調(diào)度長度比率

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

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

5 結(jié) 論

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

[1]林偉偉，齊德昱.云計算資源調(diào)度研究綜述 [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]郭力爭，趙曙光，姜長遠(yuǎn).云計算環(huán)境下基于關(guān)聯(lián)量的數(shù)據(jù)部署與任務(wù)調(diào)度 [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]張曉磊.云計算獨立任務(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)先級列表任務(wù)調(diào)度算法 [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]王鵬，黃焱，李坤，等.云計算系統(tǒng)相空間分析模型及仿真研究 [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].計算機輔助設(shè)計與圖形學(xué)學(xué)報，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]宮華，張彪，許可.并行機生產(chǎn)與成批配送協(xié)調(diào)調(diào)度問題的近似策略 [J].沈陽工業(yè)大學(xué)學(xué)報，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.

國家電網(wǎng)公司電力云計算服務(wù)試點平臺建設(shè)項目(0711-140TL21112001).

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

10.7688/j.issn.1000-1646.2017.03.01

TP 391.9

A

1000-1646(2017)03-0241-07

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