【作者】 邓景文；

【导师】 陆传赉；

【作者基本信息】 北京邮电大学 ， 应用数学， 2008， 硕士

【摘要】 近年来,随着网格、分布式处理技术的不断发展,对集群系统提出了新的要求。网格由大量的异构资源组成,集群管理系统作为网格计算的基础,它的高效实用性就显得十分重要和迫切。作业调度是集群管理系统的核心部分,调度机制决定了作业执行效率,良好的调度机制可以提高整个集群的处理能力,合理有效地在各个用户之间分配资源,加速作业的执行。本文首先对网格、分布式系统和集群等相关问题进行了介绍,然后从现有的调度算法入手,从网格调度中任务的均衡性和算法的性能两方面着重分析了Min-Min,Max-Min算法的一些不足和缺陷。针对网格中多用户的特性,提出了一种公平调度算法。该算法把用户的优先级放在首要位置,充分考虑到每个用户的作业运行情况。主要实现方式是先根据用户的重要性为各个用户分配一个配额值,再将用户的优先级作为一个动态修正量,表现为用户的配额值与用户在集群系统里占用的资源以及系统的配置情况的比值,根据动态优先级来实时调度作业。本文详细阐述了动态优先级的影响因素、变化特性以及对作业调度的影响,针对动态优先级的计算提出了计算公式,同时对公式进行了正确性的证明,并对公平调度算法的复杂度进行了分析。在实验部分利用模拟网格计算技术构造了模拟系统和用户,测试了公平调度算法的实际性能和调度情况,并与其他算法进行了比较。更多还原

【Abstract】 Recently, with the development of network and distributed computing technology, new demands are brought on cluster systems. The grid is composed of many heterogeneous resources. As the infrastructure of grid, to develop an efficient and practical cluster management system is necessary and imperative. Scheduler is the core part of cluster management system. A good scheduler can gather all power of the cluster, allocate resource to users efficiently and enhance the completion of jobs.This paper introduced grid, distributed system and cluster and some related issues. Then based on the existing scheduling algorithms, the paper emphatically analyzed the shortage and limitation of Min-Min and Max-Min algorithms from two aspects regarding task’s equality and algorithms’ performance. Based upon the multi-user situation in grids, it proposed a fair scheduling algorithm. This algorithm puts the user’s priority in the primary location, and sufficiently considered the job status of every user. The primary realization of this algorithm is to dispute a quota value to every user based on the importance of the user. Then we conduct a dynamic rectification considering the user’s priority, which is the ratio of users of the quota system in the cluster and the use of system resources and the allocation, in accordance with priority to real-time dynamic scheduling operations. This paper describes the factors of dynamic priority, as well as the impact of changes in the characteristics of job scheduling, and proposed calculation formula of dynamic priority. We also proofed the correctness of the formula and analyzed the complexity of fair scheduling algorithm. In the simulation, tectonic systems and users is constructed using simulated grid computing technology. We also tested the performance and scheduling of the actual fair scheduling algorithm, and compared with other algorithms.更多还原