DMS算法在Map/Reduce任务调度中的应用

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

云环境下传统的任务调度算法整体效率较低,为了提高任务调度的整体效率,在Map/Reduce基础上提出了一种基于处理时间的DMS任务调度算法。首先,对复杂任务进行预处理,将复杂任务转化为DAG图,依据任务依赖关系大小产生最佳拓扑排序,并依据排序结果将复杂任务交给work节点进行处理;其次,通过将节点处理任务的预测时间与节点处理能力的比值作为子任务在每个节点的处理"时间"进行量化建模,建立任务和处理时间的度量矩阵,依据DMS算法进行处理,从而获得任务分配最佳方案;最后,从任务调度效率与资源使用率的角度将DMS算法与公平调度算法、遗传算法行对比验证。实验结果表明,DMS算法能明显提高任务调度整体效率,充分利用各节点的计算能力提高了Map/Reduce的调度效率。

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.