采用面向对象方法实现任务调度算法仿真.doc

采用面向对象方法实现任务调度算法仿真 　　摘要:对网格计算中的任务调度及调度算法进行了介绍;对GridSim工具包的工作原理、体系结构进行了介绍;对如何开发基于GridSim的调度仿真系统进行了阐述;并采用面向对象思想对调度仿真系统进行了改进,使得对调度算法的仿真变得更便捷。 　　关键词:任务调度;GridSim;面向对象;仿真 　　中图分类号:TP311文献标识码:A文章编号:1009-3044(2010)19-5309-03 　　Using Object-oriented Method to Realize Task Scheduling Algorithm Simulation 　　ZHAO Jian 　　(The 631 Institute, Aviation Industry Corporation of China, Xian 710068, China) 　　Abstract: This paper has an introduction on task scheduling and scheduling algorithms in grid computing;and has an introduction on the working principles,architecture on the GridSim simulator; Explained how to develop scheduling simulation system based on GridSim;The scheduling simulation system has been improved by using object-oriented thinking and makes the algorithm becomes more convenient. 　　Key words: task scheduling; gridSim; object oriented; simulation 　　1 网格任务调度与调度算法 　　网格是“构筑在互联网上的一组新兴技术。它将高速互联网、高性能计算机、大型数据库、传感器、远程设备等融为一体,提供可靠的、协调的、无处不在的和低廉的高端计算能力”[1]。其思想从根本上改变了人们对“计算”的看法,它突破了以往强加于计算资源上的关于计算能力大小、地理位置、共享及协作方面的限制,将世界各个角落的计算资源整合在一起进行协同计算。由于其思想的先进性,使其逐渐成为下一代分布并行计算的规范。 　　网格中的计算资源是分布且异构的,并具有动态性和多样性等特征[2],这使得网格系统变得异常庞大和复杂。资源描述与发现、资源管理、任务调度、性能评价、通信规范、安全体系和容错机制都是网格系统有待解决的重大课题。 　　任务调度是网格系统中的关键技术,其目的是:在众多的分布且异构的计算资源中,同时考虑各计算节点的计算性能、节点之间的通讯性能等参数,把不同的任务以最合理的方式分配到相应的节点去完成[3]。任务调度的基本模型如图1所示。 　　典型的网格任务调度流程通常包括以下几步: 　　1) 用户将包含有多个子任务的应用程序提交给与其相绑定的网格资源代理。该用户应用程序可能对服务质量(QoS)有一定的要求,如应用程序必须在什么时间之前完成,或完成应用程序的最高开销是多少,等等。 　　2) 代理收到用户应用程序及QoS请求后,通过网格信息服务(GIS)收集网格环境中可用资源的静态信息,并按用户的需求清单筛选出适合处理用户作业的若干资源。 　　3) 代理根据相应的调度算法将用户应用中的多个子任务映射到相应的资源上,即哪个子任务应该被指派到哪个资源上进行处理。此时,子任务并没有真正到达相应的资源; 　　4) 完成映射后,代理将各个子任务指派到与其对应的资源上。 　　5) 完成指派后,代理将对各个子任务的执行情况进行实时监控,并接收执行完毕后的返回结果。 　　6) 所有子任务均执行完毕后,代理将应用程序的执行结果返回给用户。 　　任务调度的目标是要对用户需求实现最优调度,并设法提高网格系统的吞吐率。其具体目标有:跨度(Makespan)指从第一个任务开始运行到最后一个任务运行完毕所经历的时间,用户向网格系统提交需求后,最大的愿望是网格系统尽快完成自己的需求,所以实现最优跨度是用户和网格系统的共同目标;网格系统在进行任务调度时,保障应用的服务质量也是理所应当的;另外,任务调度的目标还包括负载均衡、经济原则等[4]。 　　从任务调度的流程与目标可以看出,调度系统采用什么样的调度算法直接决定着网格系统性能的优劣。调度算法通过一个用户子任务集合和一个网格资源集合得出一张子任务到资源的映射表。目前研究的调