云计算环境下基于MapReduce模型的任务调度算法研究

发布时间：2018-11-04 09:17

【摘要】：云计算作为一种新的计算模式或者说服务模式，主要通过互联网向用户提供计算、存储、应用平台等各种服务，在国内外各大研究机构及企业的大力推动下，其发展迅速，为处理互联网应用平台日益增长的庞大数据量提供了良好的解决方案。自2004年Google公司提出能并发处理海量数据的MapReduce并行编程模型起，基于MapReduce模型的云平台不断涌现，其中以Hadoop平台应用最为广泛，而基于MapReduce模型的任务调度问题也成为了学者研究的热点问题，高效的任务调度算法能提高云计算系统的整体性能以及更合理地分配和利用云计算中心的资源，，对云计算平台处理海量数据有重要意义。本文首先介绍了云计算的背景及相关技术，重点对MapReduce编程模型进行描述和分析，详细介绍了MapReduce的执行过程；其次，介绍云计算环境下基于MapReduce编程模型的任务调度的新特征，并详细介绍了几种典型的云平台任务调度算法，其主要包括：FIFO算法、MaxCover-Balance算法、公平算法、延迟调度算法、遗传算法。在认真分析和研究云计算相关技术以及各算法的优缺点后，提出了两个改进的任务调度算法。首先，针对已有的延迟调度算法存在的问题进行改进，通过分析数据中心计算节点空闲速率、网络传输速率、节点负载等各动态参数，根据概率模型调整每个作业的等待时间阈值以及空闲计算节点的等待时间，优化算法性能；其次，对原有自适应遗传算法进行改进，在保证用户公平性的前提下，将任务调度到输入数据所在的计算节点以减少网络传输开销，并以缩短总任务的完成时间及提高用户满意度为目标，优化算法性能。最后通过Matlab模拟仿真云计算环境，设置和调整实验参数，对比分析原有算法与改进后的算法。通过反复实验，结果表明改进的延迟调度算法在数据本地性、作业公平性及作业完成时间方面优于已有的延迟调度算法，是云计算环境下有效的任务调度算法；改进的遗传算法在响应时间、公平性和用户满意度方面优于自适应遗传算法，更加适应云计算环境。
[Abstract]:Cloud computing as a new computing model or service model, mainly through the Internet to provide users with computing, storage, application platform and other services, in the domestic and foreign major research institutions and enterprises to promote its rapid development. It provides a good solution to deal with the growing data volume of Internet application platform. Since Google Company put forward the MapReduce parallel programming model which can deal with massive data concurrently in 2004, cloud platforms based on MapReduce model have been emerging, among which Hadoop platform is the most widely used. The task scheduling problem based on MapReduce model has become a hot topic for scholars. Efficient task scheduling algorithm can improve the overall performance of cloud computing system and allocate and utilize the resources of cloud computing center more reasonably. It is important for cloud computing platform to deal with massive data. This paper first introduces the background and related technologies of cloud computing, focuses on the description and analysis of MapReduce programming model, and introduces the execution process of MapReduce in detail. Secondly, it introduces the new characteristics of task scheduling based on MapReduce programming model in cloud computing environment, and introduces several typical cloud platform task scheduling algorithms in detail, including: FIFO algorithm, MaxCover-Balance algorithm, fair algorithm, delay scheduling algorithm. Genetic algorithm. After analyzing and studying cloud computing technologies and the advantages and disadvantages of each algorithm, two improved task scheduling algorithms are proposed. First of all, the existing delay scheduling algorithm is improved, by analyzing the data center to calculate the node idle rate, network transmission rate, node load and other dynamic parameters. According to the probabilistic model, the waiting time threshold of each job and the waiting time of idle computing node are adjusted to optimize the performance of the algorithm. Secondly, the original adaptive genetic algorithm is improved to reduce the network transmission overhead by scheduling the task to the computing node where the input data is located on the premise of ensuring the fairness of the user. In order to shorten the completion time of the total task and improve the user satisfaction, the performance of the algorithm is optimized. Finally, we simulate the cloud computing environment by Matlab, set and adjust the experimental parameters, and compare the original algorithm with the improved algorithm. Through repeated experiments, the results show that the improved delay scheduling algorithm is superior to the existing delay scheduling algorithm in terms of data locality, job fairness and job completion time, and is an effective task scheduling algorithm in cloud computing environment. The improved genetic algorithm is superior to the adaptive genetic algorithm in response time, fairness and user satisfaction, so it is more suitable for cloud computing environment.
【学位授予单位】：新疆大学
【学位级别】：硕士
【学位授予年份】：2013
【分类号】：TP338.6

【相似文献】