（计算机软件与理论专业论文）基于离散粒子群优化算法的网格任务调度方法.pdf

基于离散粒子群优化算法的网格任务调度方法 摘要 高速网络的发展使得将分散的、异构的计算资源有机地整合到一起形成 计算网格成为可能。计算网格为解决科学和工程领域一些大规模计算问题 提供了理想的平台。由于网格所具有的广域性、动态性、异构性的特点， 如何对任务进行调度是一个极具挑战性的问题。与此同时，通过模拟自然 生态机制求解复杂优化问题的新型计算智能方法，如遗传算法、免疫算法、 蚁群算法、粒子群算法等具有很好的自适应性。尤其是由e b e r h a r t 和 k e n n e d y 于1 9 9 5 年提出的粒子群优化算法和由d o r i g o 于1 9 9 1 年提出的蚁群 算法，具有n p - h a r d 的组合优化的调度问题成为它们的一个重要研究方向。 我们提出把离散粒子群算法用于网格任务调度问题，即为使粒子群算 法适用于网格任务调度而对粒子群算法进行离散化，对粒子的位置和速度 重新进行定义，并重新设计粒子的位置和速度的变换规则。基于g ri d s i m 包，我们设计了一个网格模拟系统，并在网格模拟系统上对提出的离散粒 子群算法进行仿真实验，实验表明该算法具有较好的性能，但在算法后期 的局部搜索能力差，反馈信息利用不充分。进而我们提出把粒子群算法与 蚁群算法进行融合并应用于连续函数优化问题，利用粒子群算法寻优的结 果来初始化蚁群算法的信息素，为使蚁群算法适用于求解连续函数优化问 题，对蚂蚁寻优思想作了修改和引申，大量在连续空间的典型算例测试结 果表明，融合算法比现存的用于连续函数优化的蚁群算法更快地找到更好 的结果，该融合算法具有良好的效果。我们进一步将融合算法应用于解决 网格任务的调度问题。离散粒子群算法作为融合算法的前期寻优部分，并 把其寻优结果转化为蚁群算法的初始信息素，解决了蚁群算法初始信息素 匮乏的缺陷，蚁群算法部分的信息素更新通过局部更新和全局更新合理结 合来提高蚁群算法的性能，并且用蚁群算法作为融合算法的后期搜索，可 有效克服离散粒子群算法后期的局部搜索能力差的缺陷，又充分利用粒子 群算法的快速收敛性和蚁群算法的正反馈机制的优点。仿真实验表明本文 提出的融合算法在网格调度方面取得较好的效果。 关键词：网格；任务调度：离散粒子群算法；蚁群算法 d i s c r e t ep a r t i c l es w a r ma l g o r i t h i i r b a s e dg r i dt a s ka il o c a t i o n a b s t r a c t i nr e c e n ty e a r s ，t h eh i g h s p e e dn e t w o r k sd e v e l o pv e r yf a s t ，w h i c hm a k e si t p o s s i b l et oi n t e g r a t et h ed i s t r i b u t e da n dh e t e r o g e n e o u sc o m p u t i n gr e s o u r c e s i n t oc o m p u t a t i o n a lg r i d i tp r o v i d e sa ni d e a lp l a t f o r mt os o l v el a r g e s c a l e c o m p u t i n gp r o b l e m si ns c i e n t i f i ca n de n g i n e e r i n ga r e mb e c a u s et h er e s o u r c e s i ng r i da r ed i s t r i b u t e d ，h e t e r o g e n e o u sa n dd y n a m i c ，h o wt os c h e d u l et a s k si n g r i dt om e e tu s e r s r e q u i r e m e n t si sac h a l l e n g i n gp r o b l e 札a tt h es a m et i m e ， t h en e wi n t e l l i g e n tc a l c u l a t i o nm e t h o dw h i c hi su s e dt or e s o l v ec o m p l i c a t e d o p t i m i z a t i o np r o b l e m sb ys i m u l a t i n gn a t u r a le c o l o g i c a lm e c h a n i s m , s u c ha s g e n e t i ca l g o r i t h m , i m m u n i t ya l g o r i t h m , a n tc o l o n ya l g o r i t h ma n dp a r t i c l es w a r m a l g o r i t h a lt h es c h e d u l i n gp r o b l e mw i t hn p _ h a r do p t i m i z a t i o nb e c a m eo n eo ft h e i m p o r t a n td i r e c t i o n si nt h er e s e a r c ho fp a r t i c l es w a r ma l g o r i t h ma n da n tc o l o n y a l g o r i t h m , s i n c ee b e r h a r ta n dk e n n e d yp r e s e n t e dp s oa l g o r i t h mi n1 9 9 5 ，a n dd o r i g o p r e s e n t e da n ta l g o r i t h mi n1 9 9 1 ad i s c r e t ep s oa l g o r i t h mw a sp r o p o s e da n dw e r ea p p l yt ot h ep r o b l e mo fg i r d s c h e d u l i n gi nt h i sp a p e r t h ea l g o r i t h mw a sr e d e f i n e dp a r t i c l e sp o s i t i o na n d v e l o c i t y ，a n dw a sr e d e s i g n e dt h es w i t c hr u l e so fp o s i t i o na n dv e l o c i t yo f p a r t i c l ef o rg r i ds c h e d u l i n g b a s e do ng r i d s i m ，w ed e s i g n e dag r i ds i m u l a t i o n s y s t e m ，a n de x p e r i m e n to nt h es y s t e mf o rt h ea l g o r i t h m s i m u l a t i o ne x p e r i m e n t s h o wt h a ti tc a np r o d u c eg o o dr e s u l t s b u tt h ea l g o r i t h mh a v et h el o c a lo p t i m a i nt h er e a ro ft h ea l g o r i t h ma n dc a n tt a k e f u l lu s eo ft h ef e e d b a c ki n f o r m a t i o n o nc o m b i n a t i o no fp a r t i c l es w a r mo p t i m i z a t i o na l g o r i t h ma n da n tc o l o n ya l g o r i t h m w a sp r o p o s e df o rc o n t i n u o u sf u n c t i o no p t i m i z a t i o n ，t h er e s u l t so fp s ow e r eb e c h a r g ei n t ot h es t a r tp h e r o m o n eo fa n tc o l o n ya l g o r i t h m ，t h ei d e ao fa n ts e a r c h o p t i m i z e w a sr e m o d e lf o rc o n t i n u o u sf u n c t i o n o p t i m i z a t i o nn u m e r i c a l e x p e r i m e n t ss h o w e dt h eg o o dp e r f o r m a n c eo ft h ea l g o r i t h m f o r t h e rm a r e ，t h e c o m b i n a t i o na l g o r i t h mw a sa p p l yt ot h es c h e d u li n gp r o b l e mo fg r i dt a s k t h e d i s c r e t ep s oa l g o r i t h mw e r eb et h ef o r m e ro fc o m b i n a t i o na l g o r i t h m 。a n dt h e r e s u l to f d i s c r e t ep s oa l g o r i t h mw e r eb ec h a r g ei n t os t a r tp h e r o m o n eo fa n tc o l o n y a l g o r i t h a l i ts o l v e dt h eb l i n d n e s ss e a r c hp r o b l e mo fa n tc o l o n ya l g o r i t ht h e p h e r o m o n eu p d a t er u l eo fa n ta l g o r i t h mw a st h er e a s o n a b l ec o m b i n a t i o no nl o c a l a n da l lf o rt h ep e r f o r m a n c eo fa n tc o l o n ya l g o r i t i i 皿a n tc o l o n ya l g o r i t h mw e r e b et h er e a ro fc o m b i n a t i o na l g o r i t h mt h a tc a ne f f e c t i v e l ya v o i dt h el o c a lo p t i m a o fp s oa l g o r i t h m t h ec o m b i n a t i o na l g o r i t h mc a nt a k ef u l lu s eo fp s oa l g o r i t h m t of a s t e rc o n v e r g e n c ea n dt h ep o s i t i v ef e e d b a c km e c h a n i s mo fa n tc o l o n ya l g o r i t h m t og i v et h ep r e c i s i o no ft h es o l u t i o n s i m u l a t i o ne x p e r i m e n t ss h o wt h a ti tc a n p r o d u c eg o o dr e s u l t s k e yw o r d s ：g i r d ；t a s ks c h e d u l i n g ；p s oa l g o r i t h m ：a n tc o l o n ya l g o r i t h m ，西大茸明曩士掌位钝文童i 于离戴粒子毗化算法的用格任务调度方法 1 1 论文的研究背景 第一章绪论 随着计算机网络技术和分布式计算技术的发展，分布式计算环境正向着由i n t e r n e t 连接的异构广域环境网格计算环境发展，网格计算已成为高性能计算领域的一个新 的研究的热点。网格任务调度问题是网格计算的关健问题之一。大量任务请求使用网格 资源时，必须对它们进行合理调度才能达到资源的优化利用。一方面，现有的一些任务 调度方法如b a c k f i l l i n g 、f c f s 等并不能很好的适应网格资源的特点，如调度问题的n p 完全性、调度算法的高效性、资源的异构性及资源分配决策的并行性和分布性。另一方 面，自从8 0 年代以来，尤其是最近几年，受自然隐喻的启发，人们提出各种智能计算 算法，诸如遗传算法、蚁群算法、模拟退火、禁忌搜索、粒子群优化算法( p a r t i c l es w a r m 0 p t i m i z a t i o n ，p s o ) 和人工免疫系统等，吸引了国际上众多专家、学者的关注和兴趣。 他们在解决组合爆炸及n p 类问题卓有成效。在针对各种具体问题本身所带有的特殊性 和复杂性时，各种算法都表现出其自身的优劣性，都会面l | 缶时间性能和优化性能的双重 挑战。其中p s o 算法是由e b e r h a r t 和k e n n e d y 于1 9 9 5 年提出的一类基于群智能的随机 优化算法，是源于对鸟群的捕食等群体行为的模拟。它主要用于连续空间函数的优化问 题，与遗传算法类似，一般地，其它优化算法能够应用较好的领域，p s o 算法亦能成功 应用。如生产调度、多目标优化、组合优化等n p 完全问题，并取得了较好的效果。基 于p s o 算法在连续空间中有较好的效果，许多学者尝试用离散粒子群优化( d i s c r e t e p a r t i c l es w a r mo p t i m i z a t i o n ，d p s o ) 算法去解决组合优化问题，并取得了一些成果。 把离散粒子群算法应用于网格资源调度的原型并不多见，如何把离散粒子群优化算法应 用于网格环境下的计算任务调度并且与蚁群算法融合来提高其性能并应用于网格任务 调度是本文要研究的重点。 1 2 相关研究工作与研究现状 1 2 1 网格的概论及特点 1 2 1 1 网格的概论 在开始阶段，网格计算更多地被称为“元计算”( m e t a c o m p u t i n g ) “，过去对元计算 的研究可以认为是网格计算的初级阶段。直到2 0 世纪9 0 年代中期，网格( g r i d ) 一词才出 现，在1 9 9 5 年的i w a y 项目中明确提出了网格计算的概念盟。 3 , - 西大掣闫| 士掣啦论文| i 于离效粒子群谯耳u 牛诗曲用格任务调度力法 i a nf o s t e r 在1 9 9 8 年出版的文 6 2 一书中这样描述网格：“网格是构筑在互联网 上的一组新兴技术，它将高速互联网、高性能计算机、大型数据库、传感器、远程设备 等融为一体，为科技人员和普通老百姓提供更多的资源、功能和交互性。互联网主要为 人们提供电子邮件、网页浏览等通信功能，而网格功能则更多更强，让人们透明地使用 计算、存储等其他资源。” 2 0 0 0 年，i a nf o s t e r 在文献 1 中把网格进一步描述为“在动态变化的多个虚拟机 构间共享资源和协同解决问题。”至此，人们仍然就什么是网格而争论不休。2 0 0 2 年7 月，i a nf o s t e r 在 6 3 一文中，限定网格必须同时满足三个条件：( 1 ) 在非集中控制的 环境中协同使用资源；( 2 ) 使用标准的、开放的和通用的协议和接口( i a nf o s t e r 认为 目前只有g l o b u s 才算得上标准协议) ；( 3 ) 提供非平凡的服务。这三个条件非常严格， 象p 2 p ( p e e rt op e e r ) 、s u ng r i de n g i n e 、c o n d o r 、m u l t i c l u s t e r 等都被排除在网格之 外。至此，i a nf o s t e r 已经把他头脑中的网格概念描绘清楚了。但并不是所有人都同意 他的观点。例如，有许多人赞同广义的网格概念，它被称作巨大全球网格g g g ( g r e a t g l o b a lg r i d ) ，它不仅包括计算网格、数据网格、信息网格、知识网格、商业网格， 还包括一些已有的网络计算模式，例如对等计算p 2 p 、寄生计算等。可以这样认为，i a n f o s t e r 赞成狭义的“网格观”，而g g g 是一种广义的“网格观” 不管是狭义还是广义的网格，其目的不外乎是利用互联网把分散在不同地理位置的 计算机组织成一台“虚拟的超级计算机”，实现计算资源、存储资源、数据资源、信息 资源、软件资源、通信资源、知识资源、专家资源等的全面共享。其中每一台参与的计 算机就是一个节点，就像摆放在围棋棋盘上的棋子一样，而棋盘上纵横交错的线条对应 于现实世界的网络，所以整个系统就叫做“网格”了。在网格上做计算，就像下围棋一 样，不是单个棋子完成的，而是所有棋子互相配合形成合力完成的。传统互联网实现了 计算机硬件的连通，w e b 实现了网页的连通，而网格试图实现互联网上所有资源的全面 连通。 1 2 1 2 网格的特点 在网格计算环境中，资源是分散在各个不同地域和管理域中，由不同的组织拥有和 操作，并且在使用策略和安全机制上各不相同，即不同站点可能会使用不同的局部资源 管理系统。同时，很多应用需要同时使用多个站点上的资源，站点自治性和分配资源时 可能出现的故障需要一种特殊机制来同时分配位于多个站点上的资源。因此网格资源管 理系统具有如下特点。 1 2 1 2 1 分布与共享共存 分布性是网格的一个最主要的特点，首先网格涉及的资源是分布的，它们一般类型 复杂、规模较大、跨越的地理范围较广；由于这个原因，基于网格的计算也是分布式的， 这就产生了资源与任务的分配和调度、安全传输与通信等一系列需要解决的问题。 虽然网格资源是分布的，但它们是充分共享的，可以提供给网格上的任何使用者。 共享是网格的目的，如何解决分布资源的共享问题，是网格的核心内容。分布是网格硬 件在物理上的特征，而共享是在网格软件支持下实现的逻辑上的特征，这两者在网格系 统中同时存在。 广西大国嘎士掌位制”j 亏叼茸盏粒子阡t 刖臼法的用格任务调度力法 1 2 1 2 2 相似性 网格的局部和整体之间存在着一定的自相似性，局部往往在许多地方具有全局的某 些特征，而全局的特征在局部也有一定的体现。 1 2 1 2 3 动态性和多样性 对于网格来说，决不能假设它是一成不变的，原来拥有的资源或者功能，在下一时 刻可能会出现故障或者不可用；而原来没有的资源，可能随着时间的推移会不断地加入 进来。这就对网格系统的容错性以及可扩展性提出了更高的要求。 网格资源是异构和多样的。在网格系统中可以有不同体系结构的计算机系统和类别 不同的资源，因此网格系统必须能够解决这些不同结构、不同类别资源之间的通信和互 操作问题。 1 2 1 2 4 自治性与管理的多重性 网格上的资源首先是属于某一个组织或者个人，因此网格资源的拥有者对该资源拥 有最高级别的管理权限，网格在统一管理这些资源的同时，也应该允许资源拥有者对他 的资源有自主的管理能力。 因此，网格的管理具有多重性，一方面允许网格资源的拥有者具有自主性的管理， 另一方面又要求网格资源必须接受网格的统一管理。 1 2 2 典型网格项目调度设计思想 本小节对几个主流的网格项目( a p p l e s 、g l o b u s 、c o n d o r - ( ；、n i m r o d - g 和l e g i o n ) 重点分析与调度相关的思想。 1 2 2 1a p p l e s 3 、4 由加州大学圣迭戈分校开发的a p p l e s ( h p p l i c a t i o nl e v e ls c h e d u l i n g ) 系统，主要 用于开发计算网格中单个资源的调度代理。它使用了网络天气服务( n e t w o r kw e a t h e r s e r v i c e ) 提供的服务来监测资源性能的变化。a p p l e s 根据静态的和动态的应用程序及系 统信息来选择可行的资源及资源配置。它与其他的资源管理系统如g l o b u s ，l e g i o n ， n e t s o l v e 交互来完成应用程序。应用程序通过内嵌a p p l e s 代理，从而可以在网格中实 现资源调度。 a p p l e s 项目的另一个贡献是开发了a p p l e s 模板。它类似于n i m r o d g 的体系和资源 代理，但并不支持服务质量q o s 驱动的调度。 由于a p p l e s 的重点是调度，它遵循了底层网格中间件系统提供的资源管理模型。 一个a p p l e s 调度程序对应用程序来说是集中式的，它把任务映射到资源上，但本地的 资源调度程序则类似于n i m r o d - ( ；，执行任务单元。a p p l e s 可以被认为是具有了预测启 发式估计模型，支持在线调度和面向应用程序的调度策略。 1 2 2 2g l o b u s 5 - 8 | i 于离散御卜e 优化算法的用格任务i 度方法 g l o b u s 项目是一个美国多机构研究的成果，追求计算网格的构建。目前g l o b u s 的 研究者们与高能物理和气候模型社区共同努力建设一个数据网格。g l o b u s 系统的一个核 心元素是g l o b u s 工具集，它定义了基本的服务和构建计算网格的能力。该工具由一系 列的组件构成，以实现安全、资源定位、资源管理、数据管理、资源预约和通信等基本 服务。工具箱提供了大量的服务，从可选择的开发专用的工具或应用，以满足他们特殊 的要求。g l o b u s 构建一个分层的结构，高层可以调用底层的服务。 在g l o b u s 的思想中，一个资源管理者提供一个访问界面来把任务提交到特定的物 理资源上，g r a m ( g l o b u sr e s o u r c ea l l o c a t i o n l a n a g e r ) 负责远程应用的资源请求 处理、远程任务调度处理、远程任务管理等工作，是网格计算环境中的任务执行中心。 如果要执行需要分布式资源的服务，则需要一个动态协调分配代理( d u r o c ) 负责各个 资源管理者之间的协同交互，而协同调度器必须提供一个方便的界面来获得资源并在多 个管理者之间执行任务。 g r a m 支持如下调度模型：用户和资源代理( b r o k e r ) 提交一个任务请求，并可指定 初始任务状态为某种任务状态，则g r 删可根据任务请求按理设置任务的状态四种任 务状态包括：p e n d i n g ，表示此任务的资源还没有分配；a c t i v e ，表示任务得到了资源， 且应用程序正在执行；f a i l e d ，表示由于错误和用户取消执行使得任务非正常结束； d o n e ，表示任务成功结束。 1 2 2 3c o n d o r - 6 9 - 1 1 c o n d o r - ( ；是在用于集群环境的支持容错的任务调度工具c o n d o r 的基础上，结合 g l o b u s 工具包实现一个支持网格计算环境的任务调度工具和开发环境。c o n d o r - 6 环境 中与调度相关的部分通常称为c o n d o r - g 计算管理服务，也叫c o n d o r - ga g e n t 。 c o n d o r - ga g e n t 的设计理念其实是g l o b u s 调度思想的一个具体延伸。c o n d o r - g 利 用一个健壮的多功能的计算管理a g e n t 负责资源的发现、任务提交、任务管理和错误 发现。利用g l o b u s 相关网格协议( g r a m 、g a s s 、m d s - 2 、g s i 等) 同网格上计算机进 行交互，利用c o n d o r 提供的机制去维护计算任务的整体信息，这样c o n d o r - ga g e n t 可 以代表客户的需求，在远程资源上进行客户所需要进行的计算任务。允许客户把整个网 格当成一个完整的本地资源，用户可以利用a p i 和命令行工具执行相关操作。 i 2 2 4n i b r o d - o 1 2 、1 3 n i m r o d - 6 是m o n a s h 大学研究的一个网格系统项目。n i m r o d - g 的资源管理b r o k e r 通常被称为一个受计算经济驱动的网格资源b r o k e r 。n i m r o d - 6 是在g l o b u s 、l e g i n 等 网格中间件系统提供服务的基础上建立的，这些中间件系统为安全和统一访问远程资源 提供了一系列底层协议，并且提供了访问资源信息和存储管理的服务。n i m r o d - g 体系 中与调度相关的部分是n i n w o d - gb r o k e r 。 在n i m r o d - g 系统中，对计算网格进行资源管理和任务调度充分考虑了计算经济驱 动的因素，是这一类网格调度的典型代表。n i m r o d - g 系统中的资源b r o k e r 负责决定提 交给网格环境的某个应用的特定的需求，并执行资源发现、资源交易、调度和在网格上 - 4 - j 1 r 大掣嘎士掣啦论文i i 于离散粒子霸艺喇g | 法的用格任务调度方法 部署配置任务，启动和管理任务的执行，收集结果返回给h o m e 结点。n i m r o d - - gt 具 包为表达实验的参数提供了一种简单的说明性参数的模型语言。它用基于经济原则的新 的资源管理和调度算法。对处于大规模分布式系统中的应用，它支持受最终期限和预算 约束的调度算法( 依据资源代价、能力、可用性和用户的服务质量需求调度) 。n i m r o d - g 在调度优化时支持用户自定义的最终期限和预算，用计算经济网格体系结构提供的一套 资源交易服务管理资源的供给和需求。网格银行作为一种基础设施被提出，用来管理资 源拥有者和用户的帐户，并支持电子付款。在价格机制中，它支持多种经济模型，比如 商品市场模型、点市场模型、合同网市场模型。 1 2 2 5l e g i o n 1 4 l e g i o n 是一个由弗吉尼亚大学开发的面向对象的大系统或网格操作系统。l e g i o n 提供了软件架构，使得异构的、地理上分散的、高性能计算机的系统可以互相无缝的操 作。l e g i o n 给应用程序用户提供了一个单一的、连贯的、虚拟的机器。l e g i o n 系统由 类与大类组成。 l e g i o n 中所有的类都是分等级组织起来的，l e g i o n 类在最顶端，v a u l t 类在底部。 它支持一种控制主机负载的机制，还提供了资源预定的能力和给应用级的调度程序执行 周期的或批调度的能力。l e g i o n 资源管理体系是分等级的，有着分散的调度策略。l e g i o n 提供了缺省的面向系统的调度策略，但它也允许资源代理来完成策略扩展。也就是说， 应用级的调度程序如n i m r o d - g 和a p p l e s 可以用以用户为中心的策略来改变l e g i o n 的 缺省调度策略。 1 2 3 网格调度过程 典型的网格调度包括以下的过程皿： 1 2 3 1 作业提交 用户作业的执行通常会涉及到分布式数据、软件、网络资源、存储资源和软件资源。 另外用户可能还对服务的质量有一定要求，如任务必需在什么时间之前完成。这些资源 需求可以通过脚本语言描述( 如r s l ) 提交给网格调度系统。 用户或应用定义需求后被提交给网格调度服务，网格调度服务负责根据这一需求找 到合适的资源。作业需求描述脚本包含了必要的信息足以判断资源是否能够满足这一需 求。作业描述脚本应该包含三方面的信息，一是作业本身的属性，如可以分为几个部分， 相互之间的先序关系，一般被并行化理论抽象为d a g 图的形式；第二是作业的约束条件， 如作业完成的时间限、服务质量等，可能还有在网格经济模型中的“费用”“代价”的 概念；第三是对实际静态资源的需求，如要求程序运行的操作系统、最小的内存要求、 网络带宽等的要求。例如：一个用户提交一个作业需求，声明了需要内存至少1 2 8 m ，操作 系统为r e d h a t 7 o 以上操作系统的任务。 1 2 3 2 收集可用资源静态信息 广西大学硕士掌位说文| i 于离散粒子卅慨硼g t 法的用格任务调度力法 网格调度系统负责为用户提交的“需求清单”找到合适的资源，包括为作业进行资 源调度、资源预约。无论是系统进行资源自动选择还是由用户参与的交换选择，都需要 考虑到用户和资源拥有者两方面的要求，在满足用户需求的条件下节约资源的使用。 这一过程主要是发现潜在资源的静态信息。即为用户的作业需求找到相匹配的资源 组合。调度器收到用户作业的需求报告后将其中的内容解析出来之后，网格调度系统通 过网格信息服务收集网络上可用的网格资源。此时，调度系统仅进行简单匹配，并不判 断这些资源是否处于可用状态。例如：上例中网格调度系统收到用户的需求后，判断用 户需要这些网格资源：一个具有4 8 个结点的计算结点；一个能够进行远程沉浸的设备。 数据输入( 可能已在数据源准备完毕或者需要在作业运行后进行数据传输) 在数据源和 远程沉浸设备之间网络带宽的要求。 1 2 3 3 资源预选 经过资源发现阶段可能会得到针对一个作业的许多合适的网格资源，资源预选的任 务就是进一步筛选，使得只有一部分合适的资源能够进一步的进行匹配。这一过程可以 通过许多启发式原则进行自动筛选或者在用户的干预下进行。例如，用户可能需要在满 足任务运行条件的网格资源中选择费用最小的资源等。 1 2 3 4 资源动态信息查询 作业运行时调度系统需要收集当前的资源信息并依次进行资源使用情况的预测。如 当前资源是否是可用状态，否则预测什么时候可用。如果当前考查的资源不能满足条件， 则需要返回上一步对候选的下一个资源组合进行考查。 1 2 3 5 制订调度计划和资源预约初始化 基于资源可用情况、网络带宽和数据准备情况，调度服务判断哪个资源组合对作业 来说是合适的。这一步骤需要用到一些评价模型用来决定资源组合，制订调度策略和发 出资源预约请求，当某一个资源预约过程失败，那么调度器会选择后备的服务继续这一 预约过程。 1 2 3 6 作业运行时监控 复杂作业运行时间一般比较长，用户应该有权利在任务提交后到执行完毕的时间内 查询任务的运行状态。这是通过作业运行时监控服务来管理的，监控服务负责的另一个 职责是在作业运行满足一定条件时候调用调度其他服务引起作业的下一个流程；在作业 调度服务失败( 如资源不可用) 时重新初始化作业运行。 1 2 4 网格调度算法概述 网格环境下的资源分配和任务调度是网格计算的关键技术之一，也一直是国内外研 究者的研究重点。调度算法可分为动态调度与静态调度。动态启发式调度算法是当任务 已达到调度器就将它调度到机器上。静态启发式调度算法并不是任务到达时映射，而是 先将这些任务放在集合中，在预调度时间由映射事件调用映射。 广西大掣嚷士掌位论文墓于离散粒子翻i 饯耳匕算法的网格任务调矗。螨 经典调度理论，又称为确定性调度理论，起始于2 0 世纪5 0 年代，是组合优化领域 的一个分支，广泛应用于制造、运输和过程控制等领域。经典调度理论可以提供构造任 务执行顺序的方法，可将任务在确定的时间上分配给处理机。利用任务的准备时间、释 放时间和计算执行时间等时间特性信息，调度算法可以产生一个精确的调度策略( 但不 一定是最优的分配与调度策略) ，调度算法的输出通常是优化与任务完成时间相关的一 个或几个性能指标。 假设系统中有n 个任务的集合t = t l ，t 2 ，t n ，其中t 。为第i 个任务。在调度前 已知任务t t 的时间属性有：释放时刻为t ；，时限( d e a d l i n e ) 为d 。优先级或权值为w 。 与任务完成时间有关的任务属性有：完成时刻c 。，响应时间f = c 。一z 。，延迟时间l i = c 。- d 。， 超时时间t ：- m a x ( l j ，o ) ，超时单位代价扰，：t o ：c 。i d i 。于是，任务分配与调度的性能 lj 。o t l , t e 措l z e 指标主要有： 调度长度( 或最大完成时间) ：c - ：m a x c , - 一 平均加权调度长度： a 。：三m 缸啪 甩纠轴 最大延迟时间：厶。：m a x l a 平均响应时间。f ：! 呈， h j = i 7 平均加权响应时间： 三墨e w ， r = 竿 一，i = 1 嵋 平均超时时间：丁：! 兰r ；， 甩= 1 。 韵搬删棚。l ：挚 二_ i ，。 刀i = 1 超时任务数：u = 兰材， ，= l 7 下面是几个经典的调度算法： 1 2 4 1o l b ( o p p o r t u n i s t i cl o a db a l a n c i n g ) 广西大掌硕士掌位论文i 汗蕾h & 粒子吨t 化算法的网格任务调度方法 1 6 o l b 启发式算法将每一个任务分配到下一个准备好可用的机器，而不管这个任 务在这台机器上的执行时间。如果几台机器同时准备好了，则选择任意一台。o l b 启发 式方法的复杂性信赖于执行。在这里所考虑的执行，映射者可能需要考虑检查所有的m 个机器以便去找到接下来变成就绪的机器。 1 2 4 2m i n - k i n 1 7 、1 8 首先分别计算每个任务在所有机器上的最小执行时间，最小执行时间最小 的那个任务被选出来并被分配到相应的机器上，然后这个最近被映射的任务从集合中删 除，重复执行这个过程直到所有的任务都被映射。 在图1 1 - - m i n h i n 算法中，让r j 表示预期的时间即机器m ，在已分配到它上的所有 任务都执行完成后将变成就绪态，在那时及时去执行一个任务的时间。首先用e 。，和r ， 值去计算c 。对每个任务t ，给出最早预期完成时间的机器通过观测c 矩阵( c 矩阵 由c ；。值组成) 的第i 行值所决定。 ( 1 ) ( 2 ) ( 3 ) ( 4 ) ( 5 ) ( 6 ) ( 7 ) ( 8 ) ( 9 ) ( 1 0 ) ( 1 1 ) f o r 对元任务集合m v 中的所有任务t 。( 以任何顺序)开始循环 f o r 所有的机器( 以某一确定的任意顺序)开始循环 c l j - e l j + r j d o 直到m v 中的所有任务映射完毕为止 f o r 对m v 中的每个任务找到最早完成时间及其对应的机器 找到具有最小最早完成时间的任务t 。 将任务t t 分配到能获得最早最小完成时间的机器m 。上 从m v 中删除任务t 。 更新r l 对所有的i 更新c 。 e n d d o 图1 1m i n - m i n 算法 f i 9 1 1m i n - m i na l g o r i t h m 有最小最早预期时间的任务t 。被决定然后被分配到相应的机器。c 矩阵和r 向量 被更新，然后对还没有被分配到一个机器的任务重复上面的过程。 m i n m i n 通过调度这样的任务开始，该任务通过最小的数量改变预计的机器就绪时 间状况。如果任务t 。和t j 竞争一个特定的机器m j ，那么m i n - m i n 方法把这个将较少地 改变机器m j 的等待时间的任务( 如t 1 ) 分配给机器m j 。这增加了任务t 。还会在机器m j 上有它的最早完成时间的可能性并应该被分配到机器m ，上面。因为在t = o ，最早完成 一个任务的机器也是执行该任务最快的一个，并且由于在m i n - m i n 启发式方法通过对每 一个分配的最小数量改变机器就绪时间状态上，被分配到他们的第一个选择( 基于预期 的执行时间) 的任务的百分比在m i n - m i n 中可能比在这部分中所描述的其它批模式启发 式方法更高。如果更大数量的任务被分配到不仅完成他们最早而且执行他们最快的机器 上，该预测是能获得一个较小的跨度。 1 2 4 3m a x - m i n 广曩r 大掌璜士群啦截 二屯| l 于离散誊睁群优喇臼| 皇泊9 网格任务 度力- 囊 1 7 m a x m i n 启发算法与m i n m i n 启发算法相似，它也是从未映射的任务集合u 开 始，计算这些任务的最小完成时间，然后从该集合中选出具有最大执行时间的任务并分 配到相应的机器上，最后，将这个任务从集合u 中删除。重复执行该过程，直到所有的 任务都被映射为止。m a x - m i n 算法的动机是尽量减小由于延迟运行时间长的任务的调度 而导致的惩罚。假设即将被映射的元任务( m e t a - t a s k ) 包含几个执行时间短的任务和几 个执行时间长的任务，那么执行时间长的任务将会首先被调度到最合适的机器上以使它 们同时被执行而后再调度执行时间短的任务。 1 2 4 4 基于优先级和b e s tf i t 机制的c o - r s p b c o - r s b f c o r s b f r 调度算法 文 1 9 首先提出了“联合预留”( c o r e s e r v a t i o n ) 的思想，即当计算请求被提出 时，应用和计算网格系统之间将签订一个资源预留协议，只有当o o s 的要求发生冲突时， 调度者才会检查计算请求。同时，如果在整个计算请求中有一个需要的资源不可得，那 么整个计算请求将被全部抛弃。在此思想上，该算法提出了“基于优先级利益的联合预 留调度算法”( c o 哺s p b ) 、“基于尽力服务的联合预留调度算法”( c o r s b f r ) 和“基 于尽力和优先级的联合预留调度算法”( c o - r s b f r ) 。其中，c o - r s p b 具有较高总体调度 效益，c o r s b f 具有较低的请求拒绝量，而c o r s b f r 则是上述二者的折衷。 1 2 4 5 模拟退火 文 2 0 利用物理退火过程的特性构建一种最优方案的搜索方法。通常这样一个过程 由三个部分组成：a 对初始非最优调度方案做小幅度的随机变动；b 评估新的调度方案； c 继续这一过程直到没有更好的方案产生，也就是说得到了一个局部最优方案。 典型的模拟退火算法框架如下： f i 9 1 2 s aa l g o r i t l m 在t a o 等人的实现中，温度步长l = n * f a c t o r ，其中n 为任务个数，f a c t o r 为必须 调整的参数。另一个为设置初始温度及调整初始接受概率而设的参数为i n i t p r o b ，算法 终止条件为：连续5 次温度调整中，( 1 ) 接受率都小于一个阀值参数m i n p e r c e n t ，( 2 ) 这 期间最好解没有改善提高。对于大部分问题实例，t a o 等人给出上述几个参数经验 广西大学习e 士掌位论文| i 于离散粒子霸许t 喇臼# 法的用柏任务调度方法 值：r = o 9 5 ，f a c t o r = 1 6 ，i n i t p r o b = o 4 ，m i n i p e r c e n t = o 0 2 。另外，t a o 等人还对上述 算法进行了扩充，在算法的内循环中可对当前解的一个邻域进行穷尽搜索。 结合模拟退火的收敛性好和遗传算法的隐并行等优点，c h e n 等人提出了遗传模拟退 火算法( g e n e t i cs i m u l a t e da n n e a l i n g ，g s a ) ，并实现了一个大规模并行s i m d 算法。 在文献 2 2 的基础上，文献 2 4 将g s a 应用于任务间存在数据相关性的异构系统任务调 度。文献 2 1 利用g s a 的思想，提出一个异构系统中统一资源调度的快速遗传模拟退火 算法，这个集中控制式的调度算法能进行任务的动态调度，并试图保持各处理机的负载 平衡。 1 2 4 6 遗传算法 遗传算法( g e n e t i ca l g o r i t h m ，g a ) 瞄明是一种启发式的随机搜索方法，它仿效生 物的进化与遗传，根据“生存竞争”和“优胜劣汰”的原则，使所要解决的问题从初始 解逐渐逼近最优解。它的全局搜索性能，要好于局部搜索算法，而且搜索效率高于随机 搜索。 基于遗传算法的任务分配与调度算法的一般框架如图1 3 ： ( 1 ) 读入d a g 图等相关任务信息，生成初始解群。解群中个体经过解码后( 必 要时还要用辅助算法) 可得到任务系统的一个分配与调度： ( 2 ) 计算解群中个体的适应值： ( 3 ) 如果算法终止条件已满足，转步骤5 ，否则转步骤4 ： ( 4 ) 执行选择、交叉和变异等遗传操作，转步骤2 ： ( 5 ) 输出找到的最好解，算法终止。 图1 3 遗传算法 f i 9 1 3g e n e t