云環境下基于相關性的并行任務調度策略

段 菊，于治國

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

0 引 言

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

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

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

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

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

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

1 問題模型分析

1.1 相關定義

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

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

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

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

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

1.2 任務初次劃分

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

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

任務初次劃分的算法如下：

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

else執行步驟2

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

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

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

步驟5：重復步驟1～4，直至結束。

步驟6：輸出任務隊列P。

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

圖1 DAG圖

根據步驟1可知，圖1中t1、t2、t3都沒有前驅，因此它們的初始時間都為0，各自加入隊列為{t1}、{t2}、{t3}。t1的前驅只有t1，所以把t1加入到隊列1{t1}，以此類推，把t7、t11也加入到隊列1{t1，t4，t7，t11}，當出現多個前驅時，則比較fintime(ti)+mij的大小，加入到值最大的前驅所在隊列，例如t12的前驅有兩個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}。

任務初次劃分的詳細過程如表1所示，任務劃分結果如圖2所示。

圖2 任務劃分結果

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

2 基于閾值的任務復制策略

2.1 任務復制算法

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

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

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

結果有以下三種情況：

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

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

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

任務復制算法：

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

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

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

if在一個隊列，執行步驟3；

else

/*計算TSV*/

if(TSV>0)

復制任務；

else不復制；

else執行步驟3

步驟3：j++；//直到隊列任務結束

步驟4：i++；//直到隊列任務結束

步驟5：重復步驟1～4

步驟6：輸出任務隊列

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

圖3 任務復制結果

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

2.2 任務調度算法

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

任務調度算法：

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

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

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

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

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

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

3 實驗與分析

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

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

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

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

圖4 任務的完成時間

圖5 處理機使用數目

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

圖6 處理機利用率

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

4 結束語

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

參考文獻:

[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] 李 強,郝沁汾,肖利民,等.云計算中虛擬機放置的自適應管理與多目標優化[J].計算機學報,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] 潘志舟.基于任務復制和插入的分布式任務調度算法研究[D].武漢:華中科技大學,2015.

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

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

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

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

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