段 菊，于治國

(山東管理學(xué)院 信息化工作辦公室,山東 濟南 250357)

0 引 言

云計算是近年來分布式計算、并行計算、網(wǎng)格存儲和虛擬化等技術(shù)相融合的產(chǎn)物[1]。作為一種新興的商業(yè)模式,其蘊含著巨大的商業(yè)價值[2]。云計算主要是利用虛擬化技術(shù)將數(shù)據(jù)中心的各類資源虛擬化為資源池進行統(tǒng)一的管理和對外服務(wù)，而且云計算是面向普通大眾提供服務(wù)的，其用戶群龐大、種類多樣，要處理的任務(wù)量也是非常巨大的，所以云計算資源的管理和作業(yè)調(diào)度成為了云計算中的關(guān)鍵技術(shù)，在提高資源的使用效率以及為客戶提供優(yōu)質(zhì)的服務(wù)中起著舉足輕重的作用[3]。

云計算利用虛擬技術(shù)等為用戶提供資源，包括計算資源、存儲資源等。用戶雖然免去了購買物理處理機的費用，但是依然需要支付租借云資源的費用，租借費用主要是由租借資源的數(shù)量、類型及時間決定的，因此，如何提高任務(wù)的執(zhí)行效率是降低執(zhí)行費用的關(guān)鍵。

任務(wù)調(diào)度問題是關(guān)于云計算研究課題中的一個重要內(nèi)容，眾多研究學(xué)者也提出了很多算法，如遺傳算法[4]、蟻群算法[5]、粒子群算法[6]等。這些算法都有各自的優(yōu)缺點，后人也在這些算法的基礎(chǔ)上做了相應(yīng)改進，但是目前應(yīng)用最廣泛的是基于啟發(fā)式的調(diào)度算法[7]。其中，由于基于任務(wù)復(fù)制的調(diào)度算法可以消除任務(wù)間的通信開銷，大大降低任務(wù)的等待時間，從而提高任務(wù)的執(zhí)行效率，使得基于任務(wù)復(fù)制的調(diào)度算法得到了廣泛關(guān)注。

目前任務(wù)復(fù)制算法已經(jīng)有很多，例如TDS[8](task duplication based scheduling)考慮join節(jié)點任務(wù)與前驅(qū)的關(guān)系，但是沒有考慮處理機的優(yōu)化問題；TANH[7](task duplication-based scheduling algorithm for network of heterogeneous systems)對TDS算法中的相關(guān)參數(shù)的定義做了改進，使得計算最晚前驅(qū)的方法更合理；OSA[9](optimal task duplication based scheduling algorithm)將盡量多的父節(jié)點與子節(jié)點分配到同一個處理機上，以減少任務(wù)間的通信開銷，但是沒有考慮處理機的負載均衡問題。

隨著研究的不斷深入，任務(wù)復(fù)制算法也得到了很多改進。DCPD[10](dynamic critical path duplication)先對任務(wù)劃分優(yōu)先級然后進行調(diào)度，優(yōu)先級的劃分是根據(jù)任務(wù)的執(zhí)行時間和距離路徑的出口長度來定義的，任務(wù)的優(yōu)先級制約著整個任務(wù)的流程；TDICMA[11](task-duplication and insertion based clustering and merging algorithm)充分考慮了任務(wù)復(fù)制的連鎖反應(yīng)，多次迭代得到合理的任務(wù)復(fù)制策略，該算法更多地關(guān)注靜態(tài)任務(wù)參數(shù)；TDMCP[12](task duplication multi critical path)主要考慮關(guān)鍵路徑上的任務(wù)對整體任務(wù)調(diào)度的影響，該算法只復(fù)制首任務(wù)來影響后續(xù)任務(wù)的執(zhí)行，達到提高整體任務(wù)調(diào)度效率的目的。

為了進一步提高云環(huán)境下任務(wù)的執(zhí)行效率、降低執(zhí)行費用，文中提出一種基于相關(guān)性的并行任務(wù)調(diào)度算法(parallel task scheduling algorithm based on correlation，PTSAC)。該算法在任務(wù)調(diào)度之前根據(jù)任務(wù)間的通信開銷進行隊列劃分，以提高任務(wù)劃分的效率，在此基礎(chǔ)上，根據(jù)相關(guān)性進行任務(wù)復(fù)制，相關(guān)性由任務(wù)間的通信開銷和計算開銷來量化，在該過程中設(shè)置閾值，若相關(guān)性大于閾值則進行任務(wù)復(fù)制，否則不予復(fù)制。

1 問題模型分析

1.1 相關(guān)定義

一般來講，多個任務(wù)協(xié)作完成一個工作流，任務(wù)之間是相互聯(lián)系的，這種制約關(guān)系可以用DAG圖表示，即G={V,E,M,C}，其中：V={ti|ti(i=1,2,…,n)是工作流中的任務(wù)}；E={eij|eij表示ti、tj間的邊，ti是tj的父節(jié)點，表明ti、tj間有通信}；M={mij|mij表示ti與tj間的通信開銷，ti是tj的父節(jié)點}；C={ci|ci表示ti的計算開銷}。

定義1：參數(shù)statime(ti)、fintime(ti)分別表示任務(wù)ti的開始時間和完成時間，并且有：fintime(ti)= statime(ti)+ci。

定義2：tend表示結(jié)束任務(wù)，fintime(tend)表示整個隊列的完成時間，如果結(jié)束任務(wù)不止一個，則maxfintime(tend)=max{fintime(tend)j|j=1,2,…}。

定義3：參數(shù)pred(ti)、maxpred(ti)分別表示任務(wù)ti的前驅(qū)節(jié)點和最晚到達的前驅(qū)節(jié)點，如果任務(wù)ti沒有前驅(qū)節(jié)點，說明其可以作為一個隊列的開始節(jié)點；如果任務(wù)ti有多個前驅(qū)節(jié)點，則maxpred(ti)=max{M(pred(ti))ij+ fintime(pred(ti))|j=1,2,…}。

定義4：參數(shù)statime(ti)、fintime(ti)分別表示任務(wù)ti的開始時間和完成時間，并且有：fintime(ti)= statime(ti)+ci，參數(shù)indegree(ti)表示任務(wù)ti的入度，如果indegree(ti)≥2，說明任務(wù)為關(guān)鍵任務(wù)。

1.2 任務(wù)初次劃分

為了減少不同處理機上任務(wù)之間的通信開銷，在分配任務(wù)時相互間通信開銷大的任務(wù)分配到同一個處理機上以提高任務(wù)執(zhí)行效率。這里因同一處理機上不同任務(wù)間的通信開銷很小，可忽略不計。

任務(wù)劃分的意義在于盡量使相互間通信開銷大的任務(wù)劃分到同一任務(wù)集隊列，然后任務(wù)調(diào)度階段分配合理的處理機，以減少由通信開銷帶來的任務(wù)的等待時間，極大地縮短了整體任務(wù)隊列的執(zhí)行時間，進而減少租借資源的時間，降低執(zhí)行費用。

任務(wù)初次劃分的算法如下：

步驟1：if(pred(ti)==?){初始化statime(ti)=0；fintime(ti)=statime(ti)+ci；單獨成為一個隊列{ti}}。

else執(zhí)行步驟2

步驟2：如果前驅(qū)只有一個tj，直接把任務(wù)ti加入到前驅(qū)tj所在隊列，此時，statime(ti)=fintime(tj)，fintime(ti)=statime(ti)+ci；否則執(zhí)行步驟3。

步驟3：計算pred(ti)的最晚到達時間并排序，找到maxpred(ti)并把任務(wù)加入到maxpred(ti)所在的隊列，此時，statime(ti)=fintime(maxpred(ti))-M(pred(ti))，fintime(ti)=statime(ti)+ci。

步驟4：從總的任務(wù)集中刪除已劃分隊列的任務(wù)。

步驟5：重復(fù)步驟1～4，直至結(jié)束。

步驟6：輸出任務(wù)隊列P。

下面通過圖1說明任務(wù)初次劃分算法的過程，系統(tǒng)任務(wù)間的關(guān)系圖可用DAG圖表示。圖中圓圈表示任務(wù)頂點，在圓圈中的1～15表示任務(wù)t1～t15，頂點旁邊的數(shù)字表示任務(wù)的計算開銷，邊上的數(shù)字代表任務(wù)間的通信開銷。

圖1 DAG圖

根據(jù)步驟1可知，圖1中t1、t2、t3都沒有前驅(qū)，因此它們的初始時間都為0，各自加入隊列為{t1}、{t2}、{t3}。t1的前驅(qū)只有t1，所以把t1加入到隊列1{t1}，以此類推，把t7、t11也加入到隊列1{t1，t4，t7，t11}，當(dāng)出現(xiàn)多個前驅(qū)時，則比較fintime(ti)+mij的大小，加入到值最大的前驅(qū)所在隊列，例如t12的前驅(qū)有兩個t7、t8，fintime(t7)+m7,12=7+7=14，fintime(t8)+m8,12=5+6=11，所以t12加入隊列1，最終的三個隊列分別為P(1)={t1，t4，t7，t11，t12，t14}、P(2)={t2，t5，t8}、P(3)={t3,t6,t9,t10,t13,t15}。

任務(wù)初次劃分的詳細過程如表1所示，任務(wù)劃分結(jié)果如圖2所示。

圖2 任務(wù)劃分結(jié)果

任務(wù)maxpred(ti)cistatime(ti)fintime(ti)P(i)t1-202{t1}t2-202{t2}t3-404{t3}t4t1325{t1,t4}t5t2123{t2,t5}t6t3347{t3,t6}t7t4257{t1,t4,t7}t8t5235{t2,t5,t8}t9t6279{t3,t6,t9}t10t63710{t3,t6,t9,t10}t11t73710{t1,t4,t7,t11}t12t7279{t1,t4,t7,t11,t12}t13t92911{t3,t6,t9,t10,t13}t14t1131013{t1,t4,t7,t11,t12,t14}t15t1341115{t3,t6,t9,t10,t13,t15}

由圖1可知，t10，t14，t15是結(jié)束任務(wù)，根據(jù)定義2可知maxfintime(tend)=fintime(t15)=15，即整個任務(wù)隊列完成的時間為15，但實際完成時間為16，這是因為計算過程是按照理論上的最早完成時間計算的，程序運行的過程實際是尋找最長路徑的過程，然后通過隊列的劃分縮短完成時間，在完全并行的情況下得到最早的完成時間，而實際執(zhí)行時是按照次晚路徑計算完成時間，即在圖2中是按照c2+c5+c8+m8,12+c12+c14=16計算完成時間。

2 基于閾值的任務(wù)復(fù)制策略

2.1 任務(wù)復(fù)制算法

這一節(jié)的重點是通過任務(wù)復(fù)制提高任務(wù)的并行性，進一步提前次晚路徑的完成時間。第一節(jié)通過隊列的劃分可以縮短最晚路徑的完成時間，最晚路徑的完成時間被提前之后如果依然大于次晚路徑的完成時間，則這時整個隊列的完成時間就是最后得到的時間maxfintime(tend)，如果最晚路徑的完成時間被提前之后小于次晚路徑的完成時間，則整個隊列的完成時間就要大于最后得到的時間maxfintime(tend)，正如上面的例子就是第二種情況。

針對第二種情況，文中提出基于閾值的任務(wù)復(fù)制算法，解決計算完成時間與實際完成時間不一致的問題。由第一節(jié)可知，計算得到的完成時間是最早完成時間，比文獻[13-14]中的最早完成時間還要早，因此如何使實際完成時間與計算完成時間一致，是提高任務(wù)執(zhí)行效率的關(guān)鍵。

閾值由通信開銷和計算開銷共同決定：

結(jié)果有以下三種情況：

(1)TSV>0說明與tj不在同一隊列中的前驅(qū)任務(wù)的計算開銷總和和通信開銷相加之和大于同一隊列中的任務(wù)計算開銷總和，則可以復(fù)制從隊列的開始到ti所有的任務(wù)到tj所在的處理器上，減少任務(wù)的等待時間；

(2)TSV=0說明兩種開銷和一樣大，則不需要復(fù)制任務(wù)，此時若復(fù)制任務(wù)，不但不能減小時間開銷，而且會增加空間開銷；

(3)TSV<0說明與tj不在同一隊列中的前驅(qū)任務(wù)的計算開銷總和和通信開銷相加之和小于同一隊列中的任務(wù)計算開銷總和，則不需要復(fù)制任務(wù)，此時若復(fù)制任務(wù)，不但不能減小時間開銷，反而會增加時間開銷和空間開銷。

任務(wù)復(fù)制算法：

步驟1：計算P(i)中任務(wù)的入度indegree(tj)

步驟2：if(indegree(tj)≥2)

/*檢查tj的所有前驅(qū)是否在同一隊列*/

if在一個隊列，執(zhí)行步驟3；

else

/*計算TSV*/

if(TSV>0)

復(fù)制任務(wù)；

else不復(fù)制；

else執(zhí)行步驟3

步驟3：j++；//直到隊列任務(wù)結(jié)束

步驟4：i++；//直到隊列任務(wù)結(jié)束

步驟5：重復(fù)步驟1～4

步驟6：輸出任務(wù)隊列

根據(jù)任務(wù)復(fù)制算法對上一小節(jié)中得到的任務(wù)隊列進行處理。首先從隊列P(1)開始，任務(wù)t12的入度為2，存在前驅(qū)任務(wù)t8不與其在同一隊列，根據(jù)定義5計算閾值TSV=c2+c5+c8+m8,12-(c1+c3+c7)=2+1+2+6-(2+3+2)=4>0，即復(fù)制任務(wù)隊列P(2)={t2，t5，t8}到隊列P(1)，t14的前驅(qū)都在同一隊列；查看隊列P(3)，任務(wù)t13的入度為2，同t12的方法，TSV=10-9=1>0，復(fù)制任務(wù)隊列P(2)={t2，t5，t8}到隊列P(3)；經(jīng)過任務(wù)復(fù)制后的隊列如圖3所示。

圖3 任務(wù)復(fù)制結(jié)果

經(jīng)過任務(wù)復(fù)制目前上述例子中的完成時間為15，達到了理想中的最早完成時間，任務(wù)復(fù)制算法降低了任務(wù)的等待時間，提高了任務(wù)的并行性。經(jīng)過任務(wù)復(fù)制，每個處理機上的任務(wù)隊列基本都是相互獨立的，還有少數(shù)的有關(guān)聯(lián)但對多個處理機進行并行處理沒有太大影響。這樣就可以在每個處理機上獨立應(yīng)用任務(wù)調(diào)度算法，只有在遇到個別任務(wù)時才需要與其他處理機進行通信，大大降低了通信開銷，提高了任務(wù)執(zhí)行效率。文中提到的處理機為處理機集群。

2.2 任務(wù)調(diào)度算法

通過任務(wù)初次劃分及任務(wù)復(fù)制，對任務(wù)隊列進行了合理的劃分，得到了一個一個的任務(wù)集，任務(wù)集間的相關(guān)性大大降低，有的可以完全并行運行，為此，需要把任務(wù)集調(diào)度到合理的處理機上執(zhí)行。任務(wù)集的數(shù)目決定了租借處理機的數(shù)目，通過對任務(wù)的復(fù)制，可以有效地減少任務(wù)集的數(shù)目，進而減少租借處理機的數(shù)目；另一方面，處理機數(shù)目的減少意味著處理機利用率的提高，合理利用處理機的空閑時間是提高處理機利用率的最佳途徑，因此，任務(wù)調(diào)度算法的主要目的是為任務(wù)集查找合理的空閑時間，然后進行任務(wù)調(diào)度。

任務(wù)調(diào)度算法：

步驟1：初始化隊列L，用于存放有空閑時間段的處理機，初始化變量count=0，用于記錄處理機的數(shù)目；

步驟2：計算處理機空閑時間段的大小，并設(shè)置標(biāo)記flag=0,按照空閑時間段升序排列，放入隊列L；

步驟3：從隊列L中查找合適的最小處理機空閑時間，若存在則把任務(wù)集調(diào)度至此處理機上執(zhí)行，從任務(wù)隊列中把此任務(wù)集刪除，若flag=0，則count=count+1,并修改flag=1;

步驟4：重新計算flag=1的處理機的空閑時間段，如果還有空閑時間段，則根據(jù)時間段的大小插入到隊列中；

步驟5：若不存在合適的空閑時間段則把任務(wù)集拆分，然后查找空閑時間段；

步驟6：輸出count及flag=1的處理機的空閑時間。

3 實驗與分析

為了驗證文中提出的基于相關(guān)性的并行任務(wù)調(diào)度算法的有效性，對TDMCP算法、EOSWCA算法和文中算法從任務(wù)的完成時間、處理機的使用數(shù)目及利用率三個方面進行對比分析。

為了體現(xiàn)算法的公平性和有效性，采用前期實驗仿真平臺CloudSim[15]和參數(shù)設(shè)置，編程工具采用Myeclipse8.0[16]，任務(wù)數(shù)分別設(shè)為10、20、30、40、50、60、70、80、90、100等10種類型的任務(wù)隊列，每種類型的任務(wù)隊列產(chǎn)生10個，計算它們的完成時間maxfintime、處理機數(shù)目、處理機利用率。任務(wù)的計算時間ci和通信時間mij是在[1,20]中隨機產(chǎn)生的。

由圖4可以看出，TDMCP算法的完成時間要遠遠高于PTSAC算法，隨著任務(wù)數(shù)的增加差距也越來越明顯，TDMCP算法僅僅復(fù)制首任務(wù)而沒有對后面的任務(wù)進行處理，在任務(wù)并行性方面明顯處于劣勢。EOSWCA算法也是采用任務(wù)復(fù)制的方法，縮短關(guān)鍵路徑上任務(wù)的完成時間，其最早完成時間為次關(guān)鍵路徑的完成時間。而PTSAC算法不僅縮短了關(guān)鍵路徑上任務(wù)的等待時間，而且有效減少了次關(guān)鍵路徑的完成時間。隨著任務(wù)數(shù)的增加，PTSAC算法的優(yōu)勢越發(fā)明顯。

從圖5可以看出，在處理機使用數(shù)目方面，EOSWCA算法和PTSAC算法要絕對優(yōu)于TDMCP算法。EOSWCA算法和PTSAC算法在任務(wù)劃分之后，都進行了相當(dāng)于任務(wù)聚簇的操作，也就是合并任務(wù)隊列的過程，在任務(wù)調(diào)度階段任務(wù)集的個數(shù)，決定了處理機的數(shù)目，因此，有效減少任務(wù)集的數(shù)目對降低租借處理機個數(shù)顯得尤為重要。TDMCP算法沒有進行此類操作，由圖也可以看出，EOSWCA算法和PTSAC算法在處理機使用數(shù)目方面變化趨勢相似，但PTSAC算法仍有優(yōu)勢，尤其是在任務(wù)數(shù)增長到60以后，優(yōu)勢明顯。

圖4 任務(wù)的完成時間

圖5 處理機使用數(shù)目

處理機利用率的對比采用比值的方式，TDMCP算法的處理機總空閑時間作為基數(shù)，即TDMCP算法的處理機利用率作為單位“1”，EOSWCA算法和PTSAC算法的處理機總空閑時間分別與TDMCP算法的處理機總空閑時間作比，比值作為處理機利用率。由圖6可以看出，隨著任務(wù)數(shù)的增加，比值在減小，說明隨著任務(wù)數(shù)的增加，EOSWCA算法和PTSAC算法的處理機利用率不斷提高。任務(wù)數(shù)增加到60之后，PTSAC算法的處理機利用率明顯高于EOSWCA算法。

圖6 處理機利用率

綜合以上三個方面，PTSAC算法整體要優(yōu)于TDMCP算法和EOSWCA算法。

4 結(jié)束語

針對云環(huán)境下任務(wù)調(diào)度的問題，在前期研究的基礎(chǔ)上，從執(zhí)行時間、處理機數(shù)目及利用率方面作了進一步的研究，提出一種基于閾值的任務(wù)復(fù)制策略。該策略對復(fù)制任務(wù)的方法做了優(yōu)化，通過設(shè)置閾值的方式，判斷是否需要進行任務(wù)復(fù)制以減少任務(wù)的等待時間；然后對得到的任務(wù)集進行合理調(diào)度。實驗結(jié)果表明，該算法在提前任務(wù)的完成時間、降低處理機的使用數(shù)目及提高處理機利用率等方面有很大的改善。下一步將對云環(huán)境下科學(xué)工作流的數(shù)據(jù)復(fù)制策略進行研究。

參考文獻:

[1] CHEN Wanghu,ALTINTAS I,WANG Jianwu,et al.Enhancing smart re-run of kepler scientific workflows based on near optimum provenance caching in cloud[C]//IEEE world congress on services.Anchorage,AK,USA:IEEE,2014:378-384.

[2] 李 強,郝沁汾,肖利民,等.云計算中虛擬機放置的自適應(yīng)管理與多目標(biāo)優(yōu)化[J].計算機學(xué)報,2011,34(12):2253-2264.

[3] ALI M,KHAN S U,VASILAKOS A V.Security in cloud computing:opportunities and challenges[J].Information Sciences,2015,305:357-383.

[4] ZHU Nuo,SHAO Chunfu.Vehicle routing problem with simultaneous delivery and pick-up based on the improved genetic algorithm[C]//Fourth international conference on genetic and evolutionary computing.Shenzhen,China:IEEE,2010:312-316.

[5] CHAHARSOOGHI S K,KERMANI A H M.An effective ant colony optimization algorithm (ACO) for multi-objective resource allocation problem (MORAP)[J].Applied Mathematics & Computation,2008,200(1):167-177.

[6] TAGHIYEH S,XU Jie.A new particle swarm optimization algorithm for noisy optimization problems[J].Swarm Intelligence,2016,10(3):161-192.

[7] BAJAJ R,AGRAWAL D P.Improving scheduling of tasks in a heterogeneous environment[J].IEEE Transactions on Parallel & Distributed Systems,2004,15(2):107-118.

[8] RANAWEERA A,AGRAWAL D P.Task duplication based scheduling algorithm for heterogeneous systems[C]//Proceedings of 14th international parallel and distributed processing symposium.Cancun,Mexico:IEEE,2000:445-450.

[9] PARK C I,CHOE T Y.An optimal scheduling algorithm based on task duplication[C]//Eighth international conference on parallel and distributed systems.[s.l.]:IEEE,2001:9-14.

[10] LIU Chun-Hsien,LI Chia-Feng,LAI Kuanchou,et al.A dynamic critical path duplication task scheduling algorithm for distributed heterogeneous computing systems[C]//Proceedings of the 12th international conference on parallel and distributed systems.Washington,DC,USA:IEEE,2006:365-374.

[11] 潘志舟.基于任務(wù)復(fù)制和插入的分布式任務(wù)調(diào)度算法研究[D].武漢:華中科技大學(xué),2015.

[12] 李靜梅,尤曉非,韓啟龍.基于任務(wù)復(fù)制的多關(guān)鍵路徑任務(wù)調(diào)度算法[J].計算機工程與設(shè)計,2014,35(5):1639-1645.

[13] 段 菊,陳旺虎,王潤平,等.云環(huán)境下基于聚簇的科學(xué)工作流執(zhí)行優(yōu)化策略[J].計算機應(yīng)用,2015,35(6):1580-1584.

[14] 陳旺虎,段 菊,俞茂義.允許違反局部時間約束的科學(xué)工作流調(diào)度策略[J].計算機工程與科學(xué),2016,38(11):2165-2171.

[15] 何婧媛.云計算仿真工具CloudSim的研究與應(yīng)用[J].科技資訊,2016,14(2):32-33.

[16] 劉彥君,金飛虎.JavaEE開發(fā)技術(shù)與案例教程[M].北京：人民郵電出版社，2014.