基于遗传算法的分布式任务调度系统的分析
|
摘要
任务调度是分布式计算系统研究的核心内容之一。如何合理的将作业分配给不同的资源,以使整个系统达到最佳的性能,这就是任务调度要解决的问题。由于分布式计算系统的异构性和动态性,以及运行于系统之中的应用程序对于资源的不同需求,使得任务调度变得极其复杂,不好的任务分配策略,将会增加任务的执行时间、降低整个系统的吞吐量。
本论文首先介绍了分布式系统的概况,分析了分布式环境下任务调度的问题,并且设计了分布式计算任务调度系统中针对机器资源特性的收集模块,针对任务调度的NP完全问题,遗传算法具有很好的处理能力,但是传统的遗传算法有着过早收敛等缺陷,本文针对传统遗传算法的缺点,结合遗传算法操作过程中对各项参数的要求提出了一种对分布式异构计算系统进行任务分配与调度的改进的遗传算法,根据分布式计算系统各服务节点的计算能力、负载及网络状态进行动态调度,从而能够向用户提供最优性能,提高任务完成的效率。本论文的改进遗传算法,在传统遗传算法的基础上,针对分布式计算任务调度的动态特性,首先对任务分配调度问题做出定义,然后提出了新的编码机制和适应度函数,根据新的编码机制,重新设计了选择算子、交叉算子和变异算子。最后给出算法的仿真实验结果分析与结论等。
任务调度问题是一个典型的NP问题,将遗传算法应用于任务调度中,利用遗传算法所具有的并行性和全局解空间搜索的特点,可以有效地缩短任务的完成时间,提高分布式系统资源的使用效率。
Task Scheduling is one core of the Distributed Computing System Research. In order to make the system have the best performance, it imports to distribute the reasonable resource to execute the task, this is the problem which the task scheduling will solve. The Task Scheduling is very complex, because the Heterogeneity and dynamic of the Grid System and the different need of the resources of the application program. Bad Task Scheduling will increase the Running time and reduce the throughput of the whole Distributed System.
In this paper it introduces the current development state of the Distributed Computing System first, then it analyzes the basic functions of the Task Scheduling and designs the resource collection model in the System. Genetic Algorithm has good performance when it is used to solve the NP Complete Problem of the Task Scheduling, but the traditional Genetic Algorithms have precocious defect. This paper provides an improved Genetic Algorithm according the defect of the traditional Genetic Algorithm. It can provide the user the best performance and increase the efficiency of the task to schedule dynamically according the computing capacity load and network state of the node. In this paper, first it defines the Task Scheduling Problem, then re-designs the selection, crossover and mutation operator according the dynamic characteristic of the Distributed Computing Task Scheduling System in the basis of the basic Genetic Algorithm. At last, it provides the simulation results and the conclusions.
The Task Scheduling Problem is NP-Complete Problem,it can shorten the complete time and improve the efficiency of the Distributed System with the characteristics of parallelism and global solution space of the Genetic Algorithm when using the Genetic Algorithm to solve the Task Scheduling Problem.
本论文首先介绍了分布式系统的概况,分析了分布式环境下任务调度的问题,并且设计了分布式计算任务调度系统中针对机器资源特性的收集模块,针对任务调度的NP完全问题,遗传算法具有很好的处理能力,但是传统的遗传算法有着过早收敛等缺陷,本文针对传统遗传算法的缺点,结合遗传算法操作过程中对各项参数的要求提出了一种对分布式异构计算系统进行任务分配与调度的改进的遗传算法,根据分布式计算系统各服务节点的计算能力、负载及网络状态进行动态调度,从而能够向用户提供最优性能,提高任务完成的效率。本论文的改进遗传算法,在传统遗传算法的基础上,针对分布式计算任务调度的动态特性,首先对任务分配调度问题做出定义,然后提出了新的编码机制和适应度函数,根据新的编码机制,重新设计了选择算子、交叉算子和变异算子。最后给出算法的仿真实验结果分析与结论等。
任务调度问题是一个典型的NP问题,将遗传算法应用于任务调度中,利用遗传算法所具有的并行性和全局解空间搜索的特点,可以有效地缩短任务的完成时间,提高分布式系统资源的使用效率。
Task Scheduling is one core of the Distributed Computing System Research. In order to make the system have the best performance, it imports to distribute the reasonable resource to execute the task, this is the problem which the task scheduling will solve. The Task Scheduling is very complex, because the Heterogeneity and dynamic of the Grid System and the different need of the resources of the application program. Bad Task Scheduling will increase the Running time and reduce the throughput of the whole Distributed System.
In this paper it introduces the current development state of the Distributed Computing System first, then it analyzes the basic functions of the Task Scheduling and designs the resource collection model in the System. Genetic Algorithm has good performance when it is used to solve the NP Complete Problem of the Task Scheduling, but the traditional Genetic Algorithms have precocious defect. This paper provides an improved Genetic Algorithm according the defect of the traditional Genetic Algorithm. It can provide the user the best performance and increase the efficiency of the task to schedule dynamically according the computing capacity load and network state of the node. In this paper, first it defines the Task Scheduling Problem, then re-designs the selection, crossover and mutation operator according the dynamic characteristic of the Distributed Computing Task Scheduling System in the basis of the basic Genetic Algorithm. At last, it provides the simulation results and the conclusions.
The Task Scheduling Problem is NP-Complete Problem,it can shorten the complete time and improve the efficiency of the Distributed System with the characteristics of parallelism and global solution space of the Genetic Algorithm when using the Genetic Algorithm to solve the Task Scheduling Problem.
引文
[1]Tanenbaun A S.Distributed Operating Systems.陆丽娜译.北京:电子工业出版社,1999.
[2]陈国良,吴俊敏,章锋等.并行计算机体系结构.北京:高等教育出版社,2002.
[3]曲绍云.分布式异构系统中任务调度问题的研究:(硕士学位论文).青岛:青岛大学,2005.
[4]Freund R,Siegel H.Heterogeneous Processing.IEEE Computer,1993,11(26):13-17.
[5]Stone H S.Multiprocessor scheduling with the aid of network flow algorithms.IEEE Trans on Software Eng,1978,4(3):254-258.
[6]罗红,慕德俊,邓智群等.网格计算中任务调度研究综述.计算机应用研究,2005,4(5):16-19.
[7]Shin K,Cha M,Jang M et al.Task scheduling algorithm using minimized duplications in homogeneous systems.Journal of Parallel and Distributed Computing,2008,4(1):1146-1156.
[8]Shivle H,Sameer T,Siegel R et al.Dynamically mapping tasks with priorities and multiple deadlines in a heterogeneous environment.Journal of Parallel and Distributed Computing,2007,2(7):154-169.
[9]王翠平.分布式系统中的任务调度问题:(硕士学位论文).青岛:青岛大学,2002.
[10]Korkhov W,Moscicki J,Krzhizhanovskaya W.Dynamic workload balancing of parallel applications with user-level scheduling on the Grid.Future Generation Computer System-The International Journal of Grid Computing Theory Methods and Applications,2008,25(1):28-34.
[11]桂小林.网格技术导论.北京:北京邮电大学出版社,2005.
[12]Marcin P.WMI Essentials for Automating Windows Management.America:Sams,2001.
[13]都志辉.高性能计算并行编程技术:MPI并行程序设计.北京:清华大学出版社,2001.
[14]易昭华.大规模机群监控系统监控信息采集与储存技术研究:(硕士学位论文).北京:清华大学,2004.
[15]陈国良.遗传算法及其应用.北京:人民邮电出版社,1996.
[16]苑希民,李鸿雁,刘树坤等.神经网络和遗传算法在水科学领域的应用.北京:中国水利水电出版社,2002.
[17]周明,孙树栋.遗传算法原理及应用.北京:国防工业出版社,1999.
[18]Lu Yu jun,Li Ren Wang,Han Jin.Adaptive genetic algorithms for the job-shop scheduling problems.Proceedings of the 7th World Congress on Intelligent Control and Automation,WCICA'08,2008.
[19]周琛琛.基于遗传算法的网格任务调度算法研究:(硕士学位论文).安徽:安徽大学,2007.
[20]Mitchell M.An Introduction to Genetic Algorithms.Cambrige.MA:The MIT Press,1996.
[21]Whitley D.The Genetic Algorithm and Selection Pressure:Why rank-based allocation reproduction trials is best.Proceedings of the 3rd International Conference on Genetic Algorithm,Los Altos,1989.
[22]田绍亮,左明,吴绍伟.一种改进的基于动态反馈的负载均衡算法.计算机工程与设计,2007,28(3).
[23]黄众,蒋培.基于可调变异算子求解遗传算法的欺骗问题.软件学报,1999,10(2):216-219.
[24]王健,王建华.标准遗传算法的研究进展.华东船舶工业学院学报,2000,12(3):28-29.
[25]Bester J,Foster I,Kesselman C,et al.GASS:A Data Movement and Access Service for Wide Area Computing Systems.Sixth Workshop on I/O Parallel and Distributed Systems,1999,42(3):141-147.
[26]张涛,须文波.基于遗传算法的网格计算资源调度策略.江南大学.微计算机信息,2006,42(6):115-117.
[27]耿汝年,须文波.基于自适应选择遗传算法的任务调度与分配.计算机工程,2008,34(3):43-45.
[28]Sivas M,Patnaik L M.Adaptive probabilities of crossover and mutation in genetic algorithms.IEEE Trans Sys Man and Cybern,1994,24(4):656-667.
[29]钟求喜,谢涛,陈火旺.遗传算法中解个体的生存策略.计算机工程与科学,2000,22(1):14-17.
[30]潘凤萍,巩敦卫,孙晓燕等.一种自适应遗传算法研究.中国矿业大学学报,2003,32(1):68-70.
[31]Chiu H P,Hsieh K L,TangY T et al.A knowledge-based genetic algorithm for the job shop scheduling problem.Proceedings of the 6th Conference WSEAS Int.Conf.on Artificial Intelligence,Knowledge Engineering and Data Bases,Antibes-Juan les pins,2007.
[2]陈国良,吴俊敏,章锋等.并行计算机体系结构.北京:高等教育出版社,2002.
[3]曲绍云.分布式异构系统中任务调度问题的研究:(硕士学位论文).青岛:青岛大学,2005.
[4]Freund R,Siegel H.Heterogeneous Processing.IEEE Computer,1993,11(26):13-17.
[5]Stone H S.Multiprocessor scheduling with the aid of network flow algorithms.IEEE Trans on Software Eng,1978,4(3):254-258.
[6]罗红,慕德俊,邓智群等.网格计算中任务调度研究综述.计算机应用研究,2005,4(5):16-19.
[7]Shin K,Cha M,Jang M et al.Task scheduling algorithm using minimized duplications in homogeneous systems.Journal of Parallel and Distributed Computing,2008,4(1):1146-1156.
[8]Shivle H,Sameer T,Siegel R et al.Dynamically mapping tasks with priorities and multiple deadlines in a heterogeneous environment.Journal of Parallel and Distributed Computing,2007,2(7):154-169.
[9]王翠平.分布式系统中的任务调度问题:(硕士学位论文).青岛:青岛大学,2002.
[10]Korkhov W,Moscicki J,Krzhizhanovskaya W.Dynamic workload balancing of parallel applications with user-level scheduling on the Grid.Future Generation Computer System-The International Journal of Grid Computing Theory Methods and Applications,2008,25(1):28-34.
[11]桂小林.网格技术导论.北京:北京邮电大学出版社,2005.
[12]Marcin P.WMI Essentials for Automating Windows Management.America:Sams,2001.
[13]都志辉.高性能计算并行编程技术:MPI并行程序设计.北京:清华大学出版社,2001.
[14]易昭华.大规模机群监控系统监控信息采集与储存技术研究:(硕士学位论文).北京:清华大学,2004.
[15]陈国良.遗传算法及其应用.北京:人民邮电出版社,1996.
[16]苑希民,李鸿雁,刘树坤等.神经网络和遗传算法在水科学领域的应用.北京:中国水利水电出版社,2002.
[17]周明,孙树栋.遗传算法原理及应用.北京:国防工业出版社,1999.
[18]Lu Yu jun,Li Ren Wang,Han Jin.Adaptive genetic algorithms for the job-shop scheduling problems.Proceedings of the 7th World Congress on Intelligent Control and Automation,WCICA'08,2008.
[19]周琛琛.基于遗传算法的网格任务调度算法研究:(硕士学位论文).安徽:安徽大学,2007.
[20]Mitchell M.An Introduction to Genetic Algorithms.Cambrige.MA:The MIT Press,1996.
[21]Whitley D.The Genetic Algorithm and Selection Pressure:Why rank-based allocation reproduction trials is best.Proceedings of the 3rd International Conference on Genetic Algorithm,Los Altos,1989.
[22]田绍亮,左明,吴绍伟.一种改进的基于动态反馈的负载均衡算法.计算机工程与设计,2007,28(3).
[23]黄众,蒋培.基于可调变异算子求解遗传算法的欺骗问题.软件学报,1999,10(2):216-219.
[24]王健,王建华.标准遗传算法的研究进展.华东船舶工业学院学报,2000,12(3):28-29.
[25]Bester J,Foster I,Kesselman C,et al.GASS:A Data Movement and Access Service for Wide Area Computing Systems.Sixth Workshop on I/O Parallel and Distributed Systems,1999,42(3):141-147.
[26]张涛,须文波.基于遗传算法的网格计算资源调度策略.江南大学.微计算机信息,2006,42(6):115-117.
[27]耿汝年,须文波.基于自适应选择遗传算法的任务调度与分配.计算机工程,2008,34(3):43-45.
[28]Sivas M,Patnaik L M.Adaptive probabilities of crossover and mutation in genetic algorithms.IEEE Trans Sys Man and Cybern,1994,24(4):656-667.
[29]钟求喜,谢涛,陈火旺.遗传算法中解个体的生存策略.计算机工程与科学,2000,22(1):14-17.
[30]潘凤萍,巩敦卫,孙晓燕等.一种自适应遗传算法研究.中国矿业大学学报,2003,32(1):68-70.
[31]Chiu H P,Hsieh K L,TangY T et al.A knowledge-based genetic algorithm for the job shop scheduling problem.Proceedings of the 6th Conference WSEAS Int.Conf.on Artificial Intelligence,Knowledge Engineering and Data Bases,Antibes-Juan les pins,2007.