集群系统下面向用户的作业公平调度算法
摘要
近年来,随着网格、分布式处理技术的不断发展,对集群系统提出了新的要求。网格由大量的异构资源组成,集群管理系统作为网格计算的基础,它的高效实用性就显得十分重要和迫切。作业调度是集群管理系统的核心部分,调度机制决定了作业执行效率,良好的调度机制可以提高整个集群的处理能力,合理有效地在各个用户之间分配资源,加速作业的执行。
本文首先对网格、分布式系统和集群等相关问题进行了介绍,然后从现有的调度算法入手,从网格调度中任务的均衡性和算法的性能两方面着重分析了Min-Min,Max-Min算法的一些不足和缺陷。针对网格中多用户的特性,提出了一种公平调度算法。该算法把用户的优先级放在首要位置,充分考虑到每个用户的作业运行情况。主要实现方式是先根据用户的重要性为各个用户分配一个配额值,再将用户的优先级作为一个动态修正量,表现为用户的配额值与用户在集群系统里占用的资源以及系统的配置情况的比值,根据动态优先级来实时调度作业。本文详细阐述了动态优先级的影响因素、变化特性以及对作业调度的影响,针对动态优先级的计算提出了计算公式,同时对公式进行了正确性的证明,并对公平调度算法的复杂度进行了分析。在实验部分利用模拟网格计算技术构造了模拟系统和用户,测试了公平调度算法的实际性能和调度情况,并与其他算法进行了比较。
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.
本文首先对网格、分布式系统和集群等相关问题进行了介绍,然后从现有的调度算法入手,从网格调度中任务的均衡性和算法的性能两方面着重分析了Min-Min,Max-Min算法的一些不足和缺陷。针对网格中多用户的特性,提出了一种公平调度算法。该算法把用户的优先级放在首要位置,充分考虑到每个用户的作业运行情况。主要实现方式是先根据用户的重要性为各个用户分配一个配额值,再将用户的优先级作为一个动态修正量,表现为用户的配额值与用户在集群系统里占用的资源以及系统的配置情况的比值,根据动态优先级来实时调度作业。本文详细阐述了动态优先级的影响因素、变化特性以及对作业调度的影响,针对动态优先级的计算提出了计算公式,同时对公式进行了正确性的证明,并对公平调度算法的复杂度进行了分析。在实验部分利用模拟网格计算技术构造了模拟系统和用户,测试了公平调度算法的实际性能和调度情况,并与其他算法进行了比较。
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.
引文
[1]TOP500 Supercomputer Site.http://www.top500.org.
[2]都志辉,陈渝,刘鹏编著,网格计算,清华大学出版社,2002.
[3]徐洪智 独立任务的网格调度算法研究[硕士学位论文]长沙:湖南大学2007:16-18
[4]Rajkumar Buyya.High Performance Cluster Computing,Volumel - Architectures and Systems Prentice Hall,1999.
[5]H.EI-Rewini,TG;Lewis,and H.H.Ali.Task Scheduling in Parallel and Distributed Systems.PrenticeH all,1994.
[6]M.R.Garey and D.S.Johnson,Computers and Intractability:A Guide to the Theory of NP-Completeness,Freeman,San Francisco,1979.
[7]黄金贵 网络并行计算环境中基于多处理机任务的调度研究[博士学位论文]长沙:中南大学2003
[8]李显宁 异构机群系统的可分负载调度算法研究[硕士毕业学位论文]南宁:广西大学2006 18-23
[9]Freund R,Gherrity M,Ambrosius Set al.Scheduling Resources in Multi-user,Heterogeneous,Computing Environments with SmartNet.Proc of 7~(th)Heterogeneous Computing Workshop,(HCW'98).Los Alamitos:IEEE Computer Society Press,1998-03:184-199
[10]Min-You Wu,Wei Shu,Hong Zhang.Segmented Min-Min:A Static Mapping Algorithm for Meta-Tasks on Heterogeneous Computing Systems.Proceedings of the 9th Heterogeneous Computing Workshop,2000,375-385
[11]桂小林,钱德沛.元计算系统的批模式启发式任务调度算法研究.计算机工程.2001,27(12):30-32
[12]张丽晓 基于计算网格的集群系统资源管理与作业调度的研究与实现[硕士学位论文]上海:上海大学2004
[13]张静,沈兵计算网格中独立任务批模式调度映射算法研究 计算机与信息技术
[14]Ian Foster,Carl Kesselman.网格计算(第二版).电子工业出版社.2004-9-1
[15]BU GY,XU ZW.A Grid System TheoreticalModel[A].Proc of HPCAsia 2001[C],2001.
[16]A.A.Khokhar,V.K.Prasanna,M.E.Shaaban,et.al.Heterogeneous Computing:Challengs and Opportunities.Proceeding IEEE Heterogeneous Computing Workshop, 18-27,1993.
[17]H.EI-Rewini,TG.Lewis,and H.H.Ali.Task Scheduling in Parallel and Distributed Systems.P renticeH all,1994.
[18]陈华平,黄刘生,安虹,陈国良等.并行分布计算中的任务调度及其分类明.计算机科学,2001,28(1):45-48.
[19]Platform Computing Corporation.LSF Administrator's Guild.2004
[20]Olf Amdt,Bemd Freisleben,Thilo Kielmann,et al.A comparative study of online scheduling algorithms for networks of workstations[J].Cluster Computing,2000,3(2):95-112.
[21]Braun TD,Siegel HJ,Beck N,et al.A Comparison of Eleven Static Heuristics forMapping a Class of IndependentTasks onto Heterogeneous Distributed Computing Systems[J].Journal of Parallel and Distributed Computing,2001,6(6):810 - 837.
[2]都志辉,陈渝,刘鹏编著,网格计算,清华大学出版社,2002.
[3]徐洪智 独立任务的网格调度算法研究[硕士学位论文]长沙:湖南大学2007:16-18
[4]Rajkumar Buyya.High Performance Cluster Computing,Volumel - Architectures and Systems Prentice Hall,1999.
[5]H.EI-Rewini,TG;Lewis,and H.H.Ali.Task Scheduling in Parallel and Distributed Systems.PrenticeH all,1994.
[6]M.R.Garey and D.S.Johnson,Computers and Intractability:A Guide to the Theory of NP-Completeness,Freeman,San Francisco,1979.
[7]黄金贵 网络并行计算环境中基于多处理机任务的调度研究[博士学位论文]长沙:中南大学2003
[8]李显宁 异构机群系统的可分负载调度算法研究[硕士毕业学位论文]南宁:广西大学2006 18-23
[9]Freund R,Gherrity M,Ambrosius Set al.Scheduling Resources in Multi-user,Heterogeneous,Computing Environments with SmartNet.Proc of 7~(th)Heterogeneous Computing Workshop,(HCW'98).Los Alamitos:IEEE Computer Society Press,1998-03:184-199
[10]Min-You Wu,Wei Shu,Hong Zhang.Segmented Min-Min:A Static Mapping Algorithm for Meta-Tasks on Heterogeneous Computing Systems.Proceedings of the 9th Heterogeneous Computing Workshop,2000,375-385
[11]桂小林,钱德沛.元计算系统的批模式启发式任务调度算法研究.计算机工程.2001,27(12):30-32
[12]张丽晓 基于计算网格的集群系统资源管理与作业调度的研究与实现[硕士学位论文]上海:上海大学2004
[13]张静,沈兵计算网格中独立任务批模式调度映射算法研究 计算机与信息技术
[14]Ian Foster,Carl Kesselman.网格计算(第二版).电子工业出版社.2004-9-1
[15]BU GY,XU ZW.A Grid System TheoreticalModel[A].Proc of HPCAsia 2001[C],2001.
[16]A.A.Khokhar,V.K.Prasanna,M.E.Shaaban,et.al.Heterogeneous Computing:Challengs and Opportunities.Proceeding IEEE Heterogeneous Computing Workshop, 18-27,1993.
[17]H.EI-Rewini,TG.Lewis,and H.H.Ali.Task Scheduling in Parallel and Distributed Systems.P renticeH all,1994.
[18]陈华平,黄刘生,安虹,陈国良等.并行分布计算中的任务调度及其分类明.计算机科学,2001,28(1):45-48.
[19]Platform Computing Corporation.LSF Administrator's Guild.2004
[20]Olf Amdt,Bemd Freisleben,Thilo Kielmann,et al.A comparative study of online scheduling algorithms for networks of workstations[J].Cluster Computing,2000,3(2):95-112.
[21]Braun TD,Siegel HJ,Beck N,et al.A Comparison of Eleven Static Heuristics forMapping a Class of IndependentTasks onto Heterogeneous Distributed Computing Systems[J].Journal of Parallel and Distributed Computing,2001,6(6):810 - 837.