云计算下计算能力调度算法的研究与改进

发布时间：2019-04-27 00:58

【摘要】：近年来,云计算作为一种新的高性能计算模式成为广大研究学者的研究热点,各大公司也纷纷推出自己的云平台,如加利福尼亚大学研究的Eucalyptus, Apache基金会的Hadoop平台、以及10gen的MongoDB等。其中Hadoop平台是开源的,现在已被广泛使用,它具有分布性、效率高、成本低、可靠性强等优点,而其中它的一项重要技术作业调度是影响到平台整体性能与资源利用率的一个关键。作业调度技术是要将进入系统的作业进行合理的分配与处理,它的目标既要使整个系统能够有序的运行,又要充分有效的利用资源,还要使用户满意度尽可能高。但是随着用户需求的不断增多和作业种类、作业规模的不断增大,目前的调度算法越来越难满足用户的需求,因此研究一种新的作业调度算法,既能满足上述要求,又能结合实际应用具有重大的意义。目前应用广泛的作业调度算法有先进先出(FIFO)算法,这种算法简单明了,成本低,只适合满足单作业或少量作业的需求；公平调度算法(Fair Scheduling algorithm),它支持多用户公平地享用资源,能够满足大量作业进入系统,但这样极易造成资源的浪费；计算能力调度算法(Capacity Scheduling algorithm),它吸取了公平算法的不足,根据作业的性能分配资源,但这种分配策略过于简单,容易陷入局部最优；国内一些学者分别从系统资源、系统配置、作业等方面下手深入地研究,试图提出一些改进算法。本文针对系统的配置,从作业的总运行时间、平均运行时间与等待时间着手,利用模拟退火算法在组合优化问题上能够避免局部最优的优势,结合计算能力调度算法,提出了一种基于模拟退火的计算能力调度算法,构建了模拟退火调度算法的数学模型,选择计算能力调度算法的默认搜索策略作为初始解,提出一个新的目标函数,计算出作业的解空间,并选择对数函数作为退火策略。该目标函数综合考虑了作业的总运行时间和作业等待时间,旨在提高作业运行效率的同时减少作业的等待时间。为了提高学习速度对模拟退火作业调度算法进行了改进,在算法中加入了记忆功能,可以大大减少迭代次数,提高搜索速度和算法的收敛速度。本文在最后详细描述了如何在Hadoop平台下实现该算法,其中包括平台的内部配置已经四种调度算法的配置。将改进的算法与前三种算法分别放入平台中运行,得出了作业的总运行时间与等待时间。最后对实验结果进行比较与分析,证明了改进算法的有效性。
[Abstract]:In recent years, cloud computing as a new high-performance computing model has become the research focus of many researchers, and many companies have launched their own cloud platforms, such as the Hadoop platform of the Eucalyptus, Apache Foundation, which is researched by the University of California. And 10gen's MongoDB and so on. Hadoop platform is open source, it has been widely used, it has the advantages of distribution, high efficiency, low cost, strong reliability and so on. And one of its important technology job scheduling is a key to the overall performance of the platform and resource utilization. Job scheduling technology is to allocate and deal with the jobs entered into the system reasonably. Its goal is not only to make the whole system run in an orderly manner, but also to make full and effective use of resources, and also to make the user satisfaction as high as possible. However, with the increasing demands of users, the types of jobs and the scale of jobs, the current scheduling algorithms are more and more difficult to meet the needs of users. Therefore, a new job scheduling algorithm is studied, which can not only meet the above requirements, but also can meet the requirements mentioned above. It is of great significance to combine practical application. At present, the most widely used job scheduling algorithms are first-in-first-out (FIFO) algorithm, which is simple and simple, low cost, and is only suitable for single job or a small number of jobs. Fair scheduling algorithm (Fair Scheduling algorithm), which supports multi-users to enjoy resources fairly, can satisfy a large number of jobs into the system, but it is easy to waste resources. Computing ability scheduling algorithm (Capacity Scheduling algorithm),) absorbs the deficiency of fair algorithm and allocates resources according to job performance, but this allocation strategy is too simple and easy to fall into local optimization. Some domestic scholars studied the system resource, system configuration, homework and so on, and tried to put forward some improved algorithms. Aiming at the configuration of the system, this paper starts with the total run time of the job, the average run time and the waiting time, utilizes the simulated annealing algorithm to avoid the local optimal advantage on the combinatorial optimization problem, and combines the computing ability scheduling algorithm. A computational capability scheduling algorithm based on simulated annealing is proposed. The mathematical model of simulated annealing scheduling algorithm is constructed. The default search strategy of computational capability scheduling algorithm is selected as the initial solution, and a new objective function is proposed. The solution space of the operation is calculated and the logarithmic function is chosen as the annealing strategy. The objective function takes into account the total running time and the waiting time of the job, in order to improve the running efficiency of the job and reduce the waiting time of the job at the same time. In order to improve the learning speed, the simulated annealing scheduling algorithm is improved. The memory function is added to the algorithm, which can greatly reduce the number of iterations, improve the search speed and the convergence speed of the algorithm. In the end, this paper describes in detail how to implement the algorithm under the Hadoop platform, including the configuration of four scheduling algorithms for the internal configuration of the platform. The improved algorithm and the first three algorithms are put into the platform respectively, and the total running time and waiting time of the job are obtained. Finally, the experimental results are compared and analyzed, and the effectiveness of the improved algorithm is proved.
【学位授予单位】：太原理工大学
【学位级别】：硕士
【学位授予年份】：2012
【分类号】：TP338

【参考文献】