计算网格调度系统的探讨

维普资讯 http://www.cqvip.com ５８　福建　电脑　２００７年第１期　计算网格调度系统的探讨　申梅梅，古丽拉－阿东别克，于炯　（新疆大学信息科学与工程学院新疆乌鲁木齐８３００４６）　【摘要】：本文介绍了网格的概念，详细阐述了计算网格调度系统的分类和性能指标，最后介绍了相关研究工作。　【关键词】：网格；计算网格；调度系统；性能指标　０．引言　网格被誉为继Ｉｎｔｅｒｎｅｔ和Ｗｅｂ之后的第三次信息技术浪　潮．实际上网格是利用互联网实现计算资源、存储资源、数据资　源、信息资源、知识资源、专家资源的全面共享和协同。　１．网格的概念　网格一词最早出现在２Ｏ世纪９Ｏ年代中期『ｌ】。网格问题是　以分布为基础的，广泛、方便、灵活，可以支持大规模、大粒度、大　范围的资源共享问题。网格概念是由实际应用中的、具体的网格　问题驱动的．为解决这些网格问题而出现的技术就是网格技术　『２１。网格技术是切实可行的。原因有两个：一是高速通信协议的　快速发展．二是网络带宽的指数级增长。新出现的国际互联网协　议所提供的服务质量保证使得网格技术进一步的发展［３】。然而　网格技术面临挑战的领域有安全、性能调度、可靠性和容错等　等。　而网格计算的概念在１９９５年的Ｉ＿ＷＡＹ项目中被提出ｆ４１。　网格计算是一个抽象概念．也可以被称为是元计算（ｍｅｔａｃｏｍ　ＤｕｔｌｎＥ）。在网格环境下，松散连接的计算机集群（很可能是异构　的）能够被当作一个单一虚拟系统或者一个虚拟组织（ｖｉｒｔｕａｌ　ｏｒ－　Ｅａｎｉｚａｆｉ０ｎ）。简而言之，网格计算的概念扩展了万维网（Ｗｏｒｌｄ　Ｗｉｄｅ　Ｗｅｂ）的功能，从而提供了国际互联网络的分布式超级计　算。　～般而言．网格系统被分类为三个主要的范畴：计算网格　（ｃｏｍｐｕｔａｔｉｏｎａｌ　ｄ）、数据网格（ｄａｔａ　ｄ）和服务网格（ｓｅｒｖｉｃｅ　）。如　图ｌ网格系统的分类　２．计算网格调度系统　网格中的调度有一个相当长的历史．已经产生了众所周知　的超级调度系统比如Ｇｌｏｂｕｓ［５］、Ｌ￣ｇｉｏｎｌ６］、ＢＹＵ／Ｓｉｌｖｅｒ／Ｍａｕｉ［７］　ＰＢＳｆＳ］。其中自适应调度已经得到相当大的关注：Ｂｅｅｋｅｒ等Ａ［９】　描述了一般框架，而Ｃａｓｓａｎｏｖａ等人ｆ１Ｏ］和Ｒｕｓｓ等人【１　１】描述了　具体的面向网格的框架。　在计算网格中的调度可以是　静态的、动态的、自适应的、可替　换的等。若调度是静态的，系统中　每一个可执行的任务都是固定被　分配到一个特定的处理器上：若　调度是动态的．一个程序可能在　运行时问内被再分配到不同的处　理器上：若调度是自适应的，调度　算法本身连同它们的参数一起都　可能被改变；若调度是可替换的。　那么它是为了响应网格负载的变　化。　２．１调度分类　计算网格调度系统有很多种　图２调度系统分类　类型［１２，１３，１４］。笔者从高吞吐量调度系统和高性能调度系统的　视角对计算网格调度系统进行了归纳和分类，如下图２所示。高　吞吐量调度侧重于整个系统的效用（ｕｔｉｌｉｚａｔｉｏｎ）．而高性能调度　则更关注改善交付于一个单独应用的性能　（１）静态与动态　在静态调度过程中．处理器的分配是在程序执行过程开始　以前。关于任务执行时间和资源的信息被假定为在它自己的编　译时间内是知道的。这些方法是没有抢先权的。　相反．动态调度是基于在执行时间内进程的重新分配，其目　的是均衡网格的负载。这些方法提供：信息策略（ｉｎｆｏｒｍａｔｉｏｎ　ｐｏｌｉｃｙ）、转移策略（ｔｒａｎｓｆｅｒ　ｐｏｌｉｃｙ）和安排策略（ｐｌａｃｅｍｅｎｔ　ｐｏｌｉｃｙ）。　（２）参量自适应和算法自适应　自适应调度自动地在运行时间内响应系统状态的变化，其　目的是达到一个接近的最优性能。自适应算法具有算法自适应　或者参量自适应的特征。参量自适应算法集中在改变负载均衡　的参量来响应系统负载的变化。而在算法自适应情况下，整个调　度策略在运行时间内能够被替换来响应网格的负载变化。　（３）最优和局部最优　因为最优调度问题通常是ＮＰ完全问题．所以焦点就集中　在局部最优的解决办法上。这些解决办法依赖近似法和启发式　方法来管理调度过程。被用于最优化度量的典型标准是：最小化　整个过程的完成时间、最大化资源的效用和最大化吞吐量。　２．２性能指标　在异构的计算网格系统中使并行和分布式应用的性能最优　一直是一个有挑战性的研究问题。在这里，笔者介绍一些通常被　用于评价系统性能的性能指标。　通常当并行地安排机器时，时间跨度（ｍａｋｅｓｐａｎ）是一个利　益目标。若最小化一个并行机器上的时间跨度时，调度就能够确　保一个好的性能『ｌ５，ｌ６１。　（１）响应时间。它被定义为使用者请求和系统响应之间的　时间间隔　（２）周转时间。　它指的是一批作业的提交和他们的输出完　成之间的时间问隔。　（３）反应时间。　指的是一个请求的提交和系统执行的开始　之间的时间问隔。　（４）吞吐量。它被定义为请求能够被系统服务的速度。它被　每秒数百万的浮点操作所度量　（５）效用。它度量的是资源忙于服务于请求的时间部分。　（６）并行工作时间。它指的是从一个并行计算开始的瞬间　到最后一个处理器完成执行过程的瞬间所耗费的时间　（７）效率。它度量一个处理器被使用的时间部分。　（８）加速。它指的是在一个处理器上执行问题所花费的时　间与在几个同样机器上完成同样问题所需要时间的比率。　（９）可扩展性。它指在计算机系统的配置发生变化的情况　下．系统的性能对此变化的响应。　３．相关研究工作　到目前为止在网格调度中。还存在着移植性、可扩展性、效　率、可重复性以及网格调度和本地调度的结合等等问题。因此，　该领域的研究还有待于进一步发展和完善。此处简单介绍几种　维普资讯 http://www.cqvip.com ２００７年第１期　福建电脑　５９　在国际上比较著名的网格调度系统：　５．Ｉａｎ．Ｆｏｓｔｅｒ　ａｎｄ　Ｃａｒ１．Ｋｅｓｓｅｌｍａｎ．Ｇｌｏｂｎｓ：Ａ　Ｍｅｔａｃｏｍｐｕｔｉｎｇ　ｌ￣ｃｔｕｔｅ　（１）Ｎｉｍｍｄ／Ｇ：由澳大利亚的Ｍｏｎａｓｈ大学开发的一个网格　Ｔｏｏｌｋｉｔ．Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｊｏｕｒｎａｌ　ｏｆ　Ｓｕｐｅｒｃｏｍｐｕｔｅｒ　Ａｐｐｌｉｃａｉｔｏｎｓ　ａｎｄ　Ｈｉｇｌｌ　Ｐｅｒ－　资源管理和调度系统『１７１。它是针对广域网上对于在地理上分散　ｆｏｒｍａｎｃｅ　Ｃｏｍｐｕｔｉｎｇ，１９９７．　的动态资源的计算管理。它的资源描述与访问使用由底层　［６１Ｔｈｅ　Ｌｅｇｉｏｎ　Ｐｒｏｊｅｃｔ．ｈｔｔｐ：／／ｗｗｗ．ｃｓ＿ｖｉｒｇｉｎｉａ．ｅｄｕＡｅｇｉｏｎ／．　Ｇｌｏｂ１．１８．ｆ５】或Ｌｅｇｉｏｎ［６ｌｑａ问件服务所提供的资源模型。它的调度　７．ＢＹＵ／Ｓｉｌｖｅｒ／Ｍａｕｉ　Ｐ　ｅｃｌ１．ｈｔｔｐ：ｌｌｗｗｗ．ｓｕｐｅｒｄｕｓｔｅｒ．ｏｒｇ／　方面采用由计算经济和截止期限所驱动的应用级调度策略，遵　８．Ｐｏｒｔａｂｌｅ　Ｂａｔｃｈ　Ｓｙｓｅｔｍ（ＰＢＳ），ｈｔｔｐ：／／ｐｂｓ．Ｉｎｌｊ．ｃｏｍ／　９，Ｗｏｌｆｇａｎｇ．Ｂｅｃｋｅｔ　ａｎｄ　Ｇｅｒｌｉｎｄｅ　Ｗａｌｔ，ａｎｎ．Ａｄａｐｔｉｏｎ　ｉｎ　ｎｙｎａｓＩｌｉｃ　Ｌｏａｄ　循层次的、分布式的调度模型。　Ｂａｌａｎｃｉｎｇ：Ｐｏｔｅｎｔｉｌａ　ａｎｄ　Ｔｅｃｈｎｉｑｕｅｓ，Ｔａｇｕｎｇｓｂａｎｄ　３．Ｆａｃｈｔａｇｕｎｇ　Ａｒｂｅｉｔ－　（２）ＡｐｐＬｅＳ：由美国加利福尼亚圣地亚哥大学开发的一个　ｓｐｈ乜一Ｋｅｃｈｅｎｓｙｓｔｅｍｅ（ＡＰＳ　９ｓ）．Ｈａｎｏｖｅｒ　Ｇｅｒｍａｎｙ．　网格应用层调度系统［１８１。它集中在对于并行元计算应用的调度　ＭａＹ，１９９６．　代理的发展上。它使用性能监测和预测来调度网格应用　这个系　１０．Ｈｅｎｒｉ．Ｃａｓａｎｏｖａ。Ｍｙｔｍｇ—ｈｏ．ＫｉｍＪｉｍ．Ｐｌａｎｋ　ｎａｄ　Ｊａｃｋ．Ｄｏｎｇａｒｔａ　Ａｄａｐｔｉｖｅ　统是用来调度广域网上的应用。但是ＡｐｐＬｅＳ调度系统没有提供　Ｓｃｈｅｄｕｌｉｎｇ　ｆｏｒ　Ｔａｓｋ　Ｆａｒｍｉｎｇ　ｗｉｔｈ　Ｇｉｒｄ　Ｍｉｄｄｌｅｗａｒｅ．Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｊｏｕｒｎａｌ　ｏｆ　服务质量（ＱｏＳ）。　Ｓｕｐｅｒｃｏｍｐｕｔｃｒ　Ａｐｐｌｉｃａｔｉｏｎｓ　ａｎｄ　Ｈｉｇｈ　Ｐｅｒｆｏｒｍａｎｃｅ　Ｃｏｍｐｕｔｉｎｇ．１９９９．　（３）ＮｅｔＳｏｌｖｅ：由美国几家公司联合开发的一个客户一代理一　１　１．ｓ．Ｈ．Ｂ．ｕｓｓ．Ｋ．Ｒ．ｅｅｃｅＪ．Ｒ．ｏｂｉｍｏｎ　ａｎｄ　Ｂ．Ｍｅｙｅｒｓ．Ａｎ．￣ｅｎｔ－Ｂａｓｅｄ　Ａｒｃｈｉ－　服务器系统『１９】　它使用户能够远程地解决复杂的科学问题，并　ｔｅｃｔｕｒｅ　ｆｏｒ　Ｄｙｎｇｉ￣ｃ　ｌ￣．ｅｓｏｕｒｃｅ　Ｍａｎａｇｅｍｅｎｔ．ＩＥＥＥ　Ｃｏｎｃｕｒｒｃｎｃｙｄｕｎｅ　ｌ９９９．　且它更关注于调度算法而不是网格基础结构的细节。ＮｅｔＳｏｌｖｅ　１２．Ｋｌａｕｓ．Ｋｒａｕｔｅｒ．Ｒ．ａｊｋｕｍａｒ．Ｂｕｙｙａ　ａｎｄ　Ｍｕｔｈｕｃｔｔｍａｒｕ．Ｍａｈｅｓｗａｔａｎ．Ａ　Ｔａｘ－　代理通过搜索在一个网络上能够提供最优性能的资源来进行调　ｏｎｏｍｙ　ａｎｄ　Ｓｕｒｖｅｙ　ｏｆ　Ｇｒｉｄ　Ｂ．ｅｓｏｕｒｃｅ　Ｍａｎａｇｅｍｅｎｔ　ＳｙｓｔｅｍｓＪｏｕｒｍｌ　Ｓｏｆｔｗａｒｅ　度的　它使用一个负载平衡的策略来提高可用计算资源的使用。　Ｐｒａｃｔｉｃｅ　ａｎｄ　Ｅｘｐｅｒｉｅｎｃｅ，２００２．　ＮｅｔＳｏｌｖｅ还提供了一个简单的接口。　１３．Ｔ．Ｃａｓｅｖａｎｔ　ａｎｄ　Ｊ．ＫｕＭ．Ａ　Ｔａｘｏｎｏｍｙ　ｏｆ　Ｓｃｈｅｄｕｌｉｎｇ　ｉｎ　Ｇｅｎｅｒａｌ　Ｐｕｒｐｏｓｅ　Ｄｉｓｔｒｉｂｕｔｅｄ　Ｃｏｍｐｕｔｉｎｇ　Ｓｙｓｔｅｍｓ．ＩＥＥＥ　Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｆ　Ｓｏｆｔｗａｒｅ　Ｅｎｇｉｎｅｅｒｉｎｇ，　结束语　１９８８．　目前网格的调度问题正日益得到广泛而深人的研究。但是，　１４．Ａｎｔｈｏｎｙ．Ｓｕｌｉｓｔｉｏ．Ｃｈｅｅ．Ｓｈｉｎ．Ｙｅｏ　ｄ　１￣ｊｋｕｍａｒ．Ｂｕｙｙａ．Ｓｉｍｕｌａｔｉｏｎ　ｏｆ　不少调度技术还没有完整的理论依据，一些结论还只是来自仿　Ｐａｒａｌｌｅｌ　ａｎｄ　Ｄｉｓｔｒｉｂｕｔｅｄ　Ｓｙｓｔｅｍｓ：Ａ　Ｔａｘｏｎｏｍｙ　ａｎｄ　Ｓｕｒｖｅｙ　ｏｆ　Ｔｏｏｌｓ．１ｎｔｅｒｎａ－　真结果　因此在这个领域还有大量的开创性工作有待于各方面　ｄｏｎａ１　Ｊｏｕｒｎａｌ　ｏｆ　Ｓｏｆｔｗａｒｅ：Ｐｒａｃｔｉｃｅ　ｎａｄ　Ｅｘｐｅｒｉｅｎｃｅ，Ｗｉｌｅｙ　Ｐｒｅｍ，２００２．　的人员去探索和研究。　１５．Ｐｉｎｅｄｏ．Ｍ．Ｓｃｈｅｄｕｌｉｎｇ：Ｔｈｅｏｒｙ，Ａｌｇｏｒｉｔｈｍｓ　ａｎｄ　Ｓｙｓｔｅｍｓ．Ｐｒｅｎｔｉｃｅ—Ｈａｌｌ，２ｎｄ　ｅｄｉｉｔｏｎ，２００２．　参考文献：　１　６．Ｐｅｔｅｒ．Ｂｒｕｃｋｅｒ．Ｓｃｈｅｄｕｌｉｎｇ　Ａｌｇｏｒｉｔｈｍｓ．Ｓｐｒｉｎｇｅｒ—Ｖｅｒｌａｇ。ｔｈｉｒｄ　ｅｄｉｔｉｏｎ，　１．１ａｎ．Ｆｏｓｔｅｒ　ａｎｄ　Ｃａｄ．Ｋｅｓｓｅｌｍａｎ．Ｔｈｅ　Ｇｒｉｄ：Ｂｌｕｅｐｒｉｎｔ　ｆｏｒ　ａ　Ｎｅｗ　Ｃｏｍｐｕｔｉｎｇ　２００１．　Ｉｎｆｒａｓｔｒｕｃｔｕｒｅ．Ｍｏｒｇａｎ　Ｋａｕｆｉ￣ｎｎ，Ｓａｎ　Ｆｒａｎｓｉｓｃｏ，ＣＡ，１９９９．　１７．Ｒ．Ｂｕｙｙａ，Ｄ．Ａｂｒａｍｓｏｎ　ａｎｄ　Ｊ．Ｇｉｄｄｙ．Ｎｉｍｒｏｄ／Ｇ：Ａｎ　Ａｒｃｈｉｔｅｃｔｕｒｅ　ｆｏｒ　ａ　２．都志辉，陈渝，刘鹏．网格计算．北京：清华大学出版社。２００２．　Ｒｅｓｏｕｒｃｅ　Ｍａｎａｇｅｍｅｎｔ　ａｎｄ　Ｓｃｈｅｄｕｌｉｎｇ　Ｓｙｓｔｅｍ　ｉｎ　ａ　Ｇｌｏｂａｌ　Ｃｏｍｐｕｍｔｉｏｎａｌ　３．Ｄｏｎｇｍｉｎ．Ｋｉｍ　ａｎｄ　Ｓａｌｉｍ　Ｈａｒｉｒｉ．ＶｉｒｔｕＭ　Ｃｏｍｐｕｔｉｎｇ．Ｃｏｎｃｅｐｔ．Ｄｅｓｉｇｎ　ａｎｄ　Ｇｒｉｄ．Ｉｎ：ｐｒｏｃ．ｏｆ　Ｉｎｔ　１　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｈｉｇ量ｌ　Ｐｅｒｆｏｒｍａｎｃｅ　Ｃｏｍｐｕｔｉｎｇ　ｉｎ　Ａｓ－　Ｅｖａｌｕａｔｉｏｎ．Ｔｈｅ　Ｋｌｕｗｃｒ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｓｅｒｉｅｓ　ｉｎ　Ｅｎｇｉｎｅｅｒｉｎｇ　ａｎｄ　Ｃｏｍｐｕｔｅｒ　ａ—Ｐａｃｉｉｆｃ　Ｂ．ｅｇｉｏｎ（ＨＰＣ　Ａｓｉａ　２ｏｏｏ）．Ｍａｙ。２０００．　Ｓｃｉｅｎｃｅ。Ａｕｇｕｓｔ　２００１．　１８．Ｍａｏｚｈｅｎ　Ｌｉ　ａｎｄ　Ｍａｒｋ．Ｂａｋｅｒ．Ｔｈｅ　Ｇｒｉｄ：Ｃｏｒｅ　ＴｅｃｈｎｏｌｏｇｉｅｓＪｏｈｎ　Ｗｉｌｅｙ　４．Ｉ—ｗＡＹ　Ｐｒｏｊｅｃｔ　ｈｔｔｐ：／／ｗｗｗ．ｉｗａｙ．ｏｒｇ／　ｎａｄ　Ｓｏｎｓ，Ｍ　，２００５．　１　９，Ｒ．Ｂｕｙｙａ　ａｎｄ　Ｍ．Ｂａｋｅｒ．Ｇｒｉｄ　Ｃｏｍｐｕｔｉｎｇ一一Ｇｒｉｄ　２Ｏｏ０，Ｓｐｒｉｎｇｅｒ，２００１．　（上接第６５页）　关重要的作用，有助于培养学生的世界观、价值观、人生观，完善　别取得了一、二、三等奖的好成绩。　健全人格。计算机科学与技术专业学生在学习专业知识的同时，　３．利用毕业实习和毕业论文（设计）提高学生的综合能力　也应该多接触人文知识，扩大自己的知识面，对培养情操、开阔　毕业实习和毕业论文（设计）是本科教育的重要环节，是以　视野、锻炼思维都有帮助。　训练学生的综合能力为主要目的，包括分析问题的能力、设计能　４．多方面培养学生兴趣．促进交叉学科的学习　力、实现系统功能的能力和教学能力等的训练，也包括全面掌握　计算机学科综合交叉的发展态势日趋明显．计算机科学与　软件、软件工具、软件开发方法以及硬件知识和应用实践的综合　技术专业的学生应选修机电、管理、财经、新闻等专业的课程，这　训练。作为毕业论文，还包括理论概括能力、抽象集成能力和写　不仅有利于学生拓宽就业渠道．而且也可为社会输送急需的复　作能力的训练。　因此，毕业实习和毕业论文（设计）的内容和指　合型人才。　导形式应多样化，充分挖掘学生的特长，提高学生解决实际问题　４．加强实践环节。培养创新型、实用型人才　的综合能力。　１．课堂教学和实验教学紧密结合．合理安排实验课程内容　６．结束语　统筹安排课堂教学．注重课堂教学和实验教学在内容上的　计算机技术的蓬勃发展．迫使普通高等院校对计算机科学　相互衔接和配合。在实验课教学方面．除完成经典的教学实验　与技术专业的人才培养模式进行改革。作为普通高等院校。办学　外．计算机实验课程的教学内容也必须跟上时代发展的要求．对　要随着经济的发展以及社会需求的变化有针对性地进行调整．　于一些主要课程的教学内容应强调它的实时性．教学的内容应　在实践中不断地探索，寻找适合自身的办学模式和特色。本文提　包括当今的主流技术。如操作系统中包含流行的ＬＩＮＵＸ、数据库　出的构建”多维分流”的人才培养模式。也需要在实践中不断地　课程的重点放在主流的Ｏｒａｃｌｅ上等等　删　完善、提高，以培养出更多适应社会发展的人才。　２．积极开展科技创新活动，培养和挖掘学生的创新意识。　积极组织和吸引学生参加科学研究活动、技术开发项目和　参考文献：　参加全国电子设计、数学建模等各种比赛，把知识信息、科研成　Ｉ．独之秀．计算机就业看起来很蔓［ＤＢ／Ｏ　Ｌ１．ｈｔｔｐ：／／ｗｗｗ．ｃａｒｅｅｒｓｌｉｆｅ．ｃｏｒｎ／　果的创造、加工、传播和应用与教学过程有机整合起来。使学生　ｍａｉｎ／Ａ＿ｒｔｉｃｌｅＳｈｏｗ．ａｓｐ？ＡｒｔＩＤ＝７９７．２００５—６—１　５　超前接触实际研发工作．有效培养了学生独立动手、独立思考、　２．李晓明，陈平．张铭等．关于计算机人才需求的调研报告ｍ．计算机教　进行科学研究和技术开发的能力，充分挖掘学生的创新意识。　育，２００４（８）：１１－１８　渤海大学计算机科学与技术专业为培养学生科技创新能力．成　３，严迪新．时计算机专业学生实践能力培养的ｉｋｉＹ，与对策Ⅱ】．苏州科技学　立了科研小组。科研小组有专门的教师负责指导，通过做实际项　院学报（自然科学版），２００３（３）：６２—６４　目．培养了学生各方面的能力．他们在计算机电子设计大赛中分　４．史志才．蔫斌．韩彦铎等．地方普通高技计算机专业教学的思考Ⅱ】史连　大学学报．２００３（５）：１０７－１０８