裴樹軍　孔德凱　苗輝

摘要：云環(huán)境下傳統(tǒng)的任務(wù)調(diào)度算法整體效率較低，為了提高任務(wù)調(diào)度的整體效率，在Map/Reduce基礎(chǔ)上提出了一種基于處理時(shí)間的DMS任務(wù)調(diào)度算法。首先，對(duì)復(fù)雜任務(wù)進(jìn)行預(yù)處理，將復(fù)雜任務(wù)轉(zhuǎn)化為DAG圖，依據(jù)任務(wù)依賴關(guān)系大小產(chǎn)生最佳拓?fù)渑判?，并依?jù)排序結(jié)果將復(fù)雜任務(wù)交給work節(jié)點(diǎn)進(jìn)行處理;其次，通過將節(jié)點(diǎn)處理任務(wù)的預(yù)測(cè)時(shí)間與節(jié)點(diǎn)處理能力的比值作為子任務(wù)在每個(gè)節(jié)點(diǎn)的處理“時(shí)間”進(jìn)行量化建模，建立任務(wù)和處理時(shí)間的度量矩陣，依據(jù)DMS算法進(jìn)行處理，從而獲得任務(wù)分配最佳方案;最后，從任務(wù)調(diào)度效率與資源使用率的角度將DMS算法與公平調(diào)度算法、遺傳算法行對(duì)比驗(yàn)證。實(shí)驗(yàn)結(jié)果表明，DMS算法能明顯提高任務(wù)調(diào)度整體效率，充分利用各節(jié)點(diǎn)的計(jì)算能力提高了Map/Reduce的調(diào)度效率。

關(guān)鍵詞：

云計(jì)算;Map/Reduce;任務(wù)調(diào)度;差值矩陣

DOI：10?15938/j?jhust?2019?01?012

中圖分類號(hào)： TP319

文獻(xiàn)標(biāo)志碼： A

文章編號(hào)： 1007-2683（2019）01-0071-07

DMS Algorithm in the Application of the Map/Reduce Tasks Schedule

PEI Shu?jun，KONG De?kai，MIAO Hui

（School of Computer Science and Technology， Harbin University of Science and Technology， Harbin 150080， China）

Abstract：The whole efficiency of traditional task scheduling algorithms is low under the cloud environment， In order to improve the whole efficiency of the task scheduling， this article based on Map/Reduce presents a Difference Matrix Scheduling tasks schedule algorithm based on processing time?Firstly， pretreatment of complex tasks， the complex tasks is converted to Directed Acyclic Graph figure， the tasks are topological sorted in an optimal manner according to the size of the task dependencies， and the work node is accordance with the sort to processing the complex tasks; Secondly， using the ratio of predictive time that node process tasks to node process capacity as a subtask in each node time quantitative modeling， then establish the task and the metric matrix of process time， according the Difference Matrix Scheduling to processing the matrix， and obtain the optimal scheme of task assignment. Finally， the experiment evaluates the Difference Matrix Scheduling ，fair scheduling algorithm， genetic algorithm in the task scheduling and resource utilization efficiency angles?The results show that the algorithm can significantly improve the overall efficiency of complex task scheduling and make full use of the capacity of the compute nodes to improve the Map / Reduce scheduling efficiency

Keywords：cloud computing; map/reduce; tasks assign; difference matrix

0引言

隨著物聯(lián)網(wǎng)、移動(dòng)互聯(lián)網(wǎng)、社會(huì)化網(wǎng)絡(luò)的快速發(fā)展，數(shù)據(jù)來(lái)源的渠道逐漸增多，半結(jié)構(gòu)化及非結(jié)構(gòu)化數(shù)據(jù)呈幾何倍增長(zhǎng)，從而加速了大數(shù)據(jù)[1-2]處理技術(shù)的快速發(fā)展與變革。云計(jì)算作為一種新興的商業(yè)計(jì)算模式，采用并行的處理方式提高了大數(shù)據(jù)的處理效率。任務(wù)調(diào)度[3-5]問題一直是云計(jì)算系統(tǒng)關(guān)注的核心問題，而影響任務(wù)調(diào)度效率的因素很多，其中任務(wù)調(diào)度模型與算法的好壞能夠直接影響云計(jì)算系統(tǒng)的整體性能?，F(xiàn)在很多學(xué)者都提出了很多有效的方法：國(guó)內(nèi)的Hadoop[6]技術(shù)論壇的總編易劍等學(xué)者提出了Map?Balance?Reduce模型，即在Map節(jié)點(diǎn)處理完任務(wù)形成中間任務(wù)后，使用一個(gè)balance的循環(huán)過程進(jìn)行均衡Reduce的輸入，這樣可以用來(lái)解決輸入不均衡問題;Abhishek Verma提出了一種LATE調(diào)度算法，該算法主要是通過計(jì)算待執(zhí)行和正在執(zhí)行任務(wù)的剩余時(shí)間，將執(zhí)行最慢的任務(wù)進(jìn)行備份從而縮短Map/Reduce作業(yè)執(zhí)行時(shí)間;Tang Zhou等提出了MTSD算法，該算法主要考慮數(shù)據(jù)的本地行與集群異構(gòu)特點(diǎn)，并且以任務(wù)執(zhí)行截止期限作為依據(jù)。依據(jù)節(jié)點(diǎn)計(jì)算能力大小決定數(shù)據(jù)存儲(chǔ)的大小，提高了任務(wù)數(shù)據(jù)本地性。