（计算机应用技术专业论文）基于蚁群算法的网格多qos任务调度研究.pdf

大连理工大学硕士学位论又 摘要 任务调度是网格研究的一个热点问题，任务调度本身是个n p 难解问题，又加之网 格的动态性、分布性、异构性和自治性，使得网格下的任务调度更加复杂。蚁群算法固 有的并发性和可扩充性等特性，使它适合用于解决网格计算的任务调度问题。服务质量 也是衡量网格性能的一个重要指标，在网格的任务调度过程中应该在调度目标函数中综 合考虑用户的q o s 需求。 本文给出了一个网格多q o s 约束任务调度模型，以带有q o s 约束的任务为研究对 象，结合蚁群算法，提出了2 个基于蚁群算法的网格任务调度算法( q a c o 和q i a c o ) 。 q a c o 是将蚂蚁系统应用到网格多q o s 任务调度中。由于对于更大一些规模的计算， 蚂蚁系统的求解能力有限，算法的性能会下降。很多学者又提出了一些改进的蚁群算法， 其中蚁群系统是效果比较好的一种算法。本文结合随机交换局部搜索来改进蚁群系统， 再将其应用到网格任务调度中，再提出了一个基于改进蚁群系统的网格多q o s 任务调度 算法( q i a c o ) 。本文重点考虑了5 种q o s 约束：时间、可靠性、版本、安全性、优 先级，并将q o s 约束转换成效用，调度目标是最大化总效用即用户满意度。 本文进行了仿真模拟实验，将本文提出的2 个基于蚁群算法的网格多q o s 任务调度 算法( q a c 0 与q i a c o ) 与改进的m i n m i n 算法、q o s m a n m i n 进行比较。仿真实验 表明q i a c 0 比q a c o 有了很大的改进，q i a c o 无论是m a k e s p a n 还是总效用相比同类 算法都有很大的优势。本文还详细说明了q i a c o 如何在网格中应用实现，由于时间有 限，还没有实现，还有一些问题有待解决，下一步会将q i a c 0 实现，应用到真实的网 格环境来检测其可行性及性能。 关键词：网格任务调度；蚁群算法；多q o s 约束；效用 基于蚁群算法的网格多q o s 任务调度研究 r e s e a r c ho ng r i dm u l t i p l eq o sc o n s t r a i n e ds c h e d u l i n gb a s e do na n t c o l o n yo p t i m i z a t i o n a b s t r a c t t h es c h e d u l i n gp r o b l e mi ng d dp r o v e dt ob en p - h a r di sah o tt o p i c f u r t h e r m o r e ，t h eg r i d h a st h ec h a r a c t e r so fd y n a m i c i t y ，d i s t r i b u t i v e n e s s ，h e t e r o g e n e i t y ，a n da u t o n o m y ，w h i c hm a k e t h eg r i ds c h e d u l i n gm o r ec o m p l e x b e c a u s ea n tc o l o n yo p t i m i z a t i o nh a st h ec h a r a c t e r so f c o n c u r r e n c y ，e x p a n s i b i l i t ya n ds oo n , i ti ss u i tt os o l v et h eg r i ds c h e d u l i n g t h eq u a l i t yo f s e r v i c e ( q o s ) i sa l s oa ni m p o r t a n tm e a s u r eo f t h eg r i d ，t h u s ，w es h o u l dc o n s i d e rt h eu s e r s r e q u i r e m e n to fq o s i ns c h e d u l i n g i nt h i st h e s i s ，w ep r e s e n tam o d e lo fm u l t i p l eq o sc o n s t r a i ni ng r i d f o c u s i n go nt h e m e t a - t a s k 、加mm u l t i p l eq o sd i m e n s i o n sa n dc o m b i n i n gt h ea n tc o l o n yo p t i m i z a t i o n , t w o a n tc o l o n yo p t i m i z a t i o nf o rg r i dt a s ks c h e d u l i n go f m u l t i p l eq o s c o n s t r a i ni sp r o p o s e d ( q a c o a n dq i a c o ) q a c oa p p l yt h ea n ts y s t e mt ot h e 鲥do fm u l t i p l eq o sc o n s t m i n e d s c h e d u l i n g b e c a u s et h ea b i l i t yo f a n ts y s t e mi sl i m i t e da n d t h ep e r f o r m a n c ew i i id e c l i n ea s t os o m el a r g e rs c a l ec o m p u t a t i o n , m a n yi m p r o v e da n tc o l o n yo p t i m i z a t i o nw e r ep r o v e d a n t c o l o n ys y s t e m si so n eo ft h ei m p r o v e da n tc o l o n yo p t i m i z a t i o nw h i c hh a sg o o d p e r f o r m a n c e c o m b i n i n gr a n d o mc h a n g el o c a ls e a r c ht oi m p r o v e a n tc o l o n ys y s t e m s ，ag r i d m u l t i p l eq o sc o n s t r a i n e ds c h e d u l i n gb a s e do ni m p r o v e da n tc o l o m ys y s t e m s ( q t a c o ) h a s b e e np r o p o s e d t h ep r o p o s e dc o n s i d e r i n gf i v ek i n d so fq o sd i m e n s i o n s ：t i m e ，r e l i a b i l i t y , v e r s i o n ，s e c u r i t ya n dp r i o r i t yw h i c ha r et r a n s f o r m e dt ou t i l i t ya st h eh e u r i s t i ci n f o r m a t i o no f t h ea l g o r i t h m w eh a v ed o n et h es i m u l a t i o ne x p e r i m e n t sa n dc o m p a r e dq a c o ，q i a c 0 ，i m p r o v e d m i n m i l la n dq o s m i l l - m i n t h er e s u l t sh a v es h o w nt h a tq i a c op e r f o r m sb e t t e rt h a no t h e r s i i lb o n lm a k e s p a na n dt o t a lu t i l i t y w eh a v ed e s c r i b e dt h ed e t a i l so fh o w p u tt h ea l g o r i t h m q i a c o i n t og r i de n v i r o n m e n t b e c a u s eo ft h el i m i to ft i m et h e r ea r es t i l ls o m ep r o b l e m sm u s t b es o l v e d w ew i l li m p l e m e n tq i a c oa n da p p l yi ti n t ot h er e a lg d de n v i r o n m e n tt op r o v ei t s v a l i d i t yi nt h ef u t u r e k e yw o r d s ：g r i ds c h e d u l i n g ；a n tc o l o n yo p t i m i z a t i o n ；m u l t i p l eq o sc o n s t r a i n ； u t i l i t y i i 大连理工大学学位论文独创性声明 作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究 工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方外， 本论文不包含其他个人或集体已经发表的研究成果，也不包含其他已申请 学位或其他用途使用过的成果。与我一同工作的同志对本研究所做的贡献 均已在论文中做了明确的说明并表示了谢意。 若有不实之处，本人愿意承担相关法律责任。 学位论文题目： 基王数叠箕洼鲍圆整垒q q 曼堡盔调度珏究一 作者签名：立乱晶一日期：j 壁牛年乒月二冱日 大连理工大学专业学位硕士学位论文 大连理工大学学位论文版权使用授权书 本人完全了解学校有关学位论文知识产权的规定，在校攻读学位期间 论文工作的知识产权属于大连理工大学，允许论文被查阅和借阅。学校有 权保留论文并向国家有关部门或机构送交论文的复印件和电子版，可以将 本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印、或扫描等复制手段保存和汇编本学位论文。 学位论文题目： 作者签名： 导师签名： 日期：型旦年芝月j 鱼日 日期：函年! 三月生日 大连理工大学硕士学位论文 1 绪论 1 。1选题背景 i n t e m e t 的出现使得人们能够大范围地共享各种信息，也使得人们比以往任何时候 都更加渴望能够更广泛地共享各种资源。使用i n t e m e t 作为底层，研究人员可以将很大 范围上地理分布的异构计算机系统集合在一起形成一个大规模的计算平台。该领域的研 究产生了个新的软件体系结构，我们称之为网格。基于网格的问题求解就是网格计算。 近年来世界各地开展了许多相关的研究项目，研究结果表明网格计算确实是一个可行的 高性能广域分布式计算模型。而网格计算就是将分布的计算机组织起来协同解决复杂的 科学与工程计算问题。狭义的网格一般被称为计算网格( c o m p u t a t i o n a lg r i d ) ，即主要 用于解决科学和工程计算问题的网格。 网格资源管理系统是网格计算的核心中间件与用户级中间件的重要组成部分，是连 接各类远程资源和进行任务协同调度的核心基础设施。在网格资源管理系统的设计与实 现中，对任务调度策略的研究是其核心内容。高效的调度策略可以充分利用网格系统的 处理能力，从而提高应用程序的性能。人们对网格任务调度的研究从未间断过，大量的 研究成果对网格的进一步发展做出了十分巨大的贡献。从网格的定义可知，“提供非凡 的服务质量”是判断网格的三个准则之一，服务质量q o s 成为网格系统的一个重要的性 能指标l l 】，所以网格的资源调度策略应该考虑用户的q o s 需求。将网格的这两个问题综 合起来就是要求网格系统要在拥有最好最合理的资源分配方式和资源调度策略的同时 还要保证服务质量。因此，如何提高网格系统中的调度算法的性能，如何保证网格任务 调度过程中的服务质量都是网格发展道路上需要解决的关键问题。本文就是将这两个问 题结合起来，研究网格环境下带有多个q o s 约束的任务调度算法。 1 2 课题研究的目的及意义 在网格系统中，它的一块核心部分就是网格任务调度，调度本身是个n p 难问题， 又加之网格的动态性、分布性、异构性和自治性，使得网格下的任务调度更加复杂。人 们对网格任务调度的研究从未间断过，关于这个问题的大量的研究成果对网格的进一步 发展做出了十分臣大的贡献。网格系统一般具有动态、分布、跨域、异构、虚拟化和智 能型等特点，网格在提供服务时涉及到的因素非常多，因此网格应用中的服务质量( 即 q o s ) 的协商和保证变成一项非常复杂和具有挑战性的工作。服务质量的好坏、效率的 高低直接关系到网格系统的性能，因此基于网格应用的需求，必须具有非凡的服务质量， 即网格应用系统和用户希望、也迫切需要有q o s 的协商和保证。非凡的服务质量已经成 基于蚁群算法的网格多q o s 任务调度研究 为检验网格性能好坏的标准之一，因为不同的用户，甚至同一用户对服务的功能、性能、 成本等都有不同考虑。事实上目前的网格系统大多只能提供部分q o s 功能。 因此，如何提高网格系统中的调度算法的性能，如何保证网格任务调度过程中的服 务质量都是网格发展道路上需要解决的关键问题。本文的目的在于从网格q o s 特性、网 格q o s 保证机制等方面研究基于q o s 的任务调度算法来满足用户的需求。本文对网格 环境下的多q o s 任务调度的研究，文中所得出仿真结果、实验分析及引入的数学理论知 识，都可作为以后网格的继续研究的参考依据和理论基础，具有十分重要的意义。 1 3 本文主要内容和工作 本文的章节组织如下： 第一章：绪论，介绍了课题的选择背景，研究目的和意义，以及论文的主要内容与 组织结构。 第二章：对本文的相关背景进行了介绍，包括网格的概念，网格中间件g l o b u s ，网 格任务调度及国内外网格任务调度算法研究现状。 第三章：介绍了网格下的q o s 相关概念，定义了一个多。q o s 网格任务调度模型， 并且详细介绍了本文使用的算法评价模型和性能预测机制。 第四章：首先介绍了基本蚁群算法的原理，详细阐述了基于蚂蚁系统的网格多q o s 任务调度( q a c o ) 的基本思想、算法结构等。介绍了蚂蚁系统的缺陷及其他改进的蚁 群算法，然后详细阐述了基于改进蚁群系统的网格多q o s 任务调度( q i a c o ) 的基本 思想、算法结构等。 第五章：对本文提出的算法进行了仿真模拟，并详细分析了仿真结果。 第六章：主要讲解了q i a c o 如何在真实网格下实现。 结论：对本文的工作进行了总结，并指出了下一步的工作。 1 4 本章小结 本章首先介绍了本文的选题背景，然后说明了课题研究的目的和意义。最后说明了 本文的主要内容和工作。 大连理工大学硕士学位论文 2 相关背景介绍 2 1 网格概念 网格的概念源于电力网格 2 ( e l e c t r i cp o w e r ：g d d ) 的思想，电力网格是我们比较熟悉 的一种“网络 ，用户只需将用电器连上电网，就能使用到电网提供的电，根本就不用 管这个电是水力发的电，火力发的电，还是核能发的电，也不用管这些电站位于何处。 网格技术的最终目标是让网格用户在使用网络资源的时候就如同现在使用电力一样方 便，希望给最终的使用者提供的是与地理位置无关、与具体计算设施无关的通用计算能 力。网格词在2 0 世纪9 0 年代中期首次被使用，用来描述用于科学和工程分布式计算 的基础设施，这种基础设施把计算资源、数据存储设施、广域网络、仪器设备等连成有 机的整体，方便用户使用这个基础设施中的任何资源。在此之后，网格的概念逐渐被发 展和扩大，最终作为一个专门的领域来研究。 网格整合网络中的异构资源，在动态、多制度的虚拟组织中协调资源共享，解决大 规模挑战性问题【3 j 。它的目标是实现网络虚拟环境下的高性能资源共享和协同工作，消 除信息孤岛和资源孤岛。网格的作用是将分散在网络上的信息及信息存储、处理能力以 合理的方式“粘合”起来，形成有机的整体，以提供比任何单台高性能计算机都强大得 多的处理能力，实现信息的高度融合和共享。传统的因特网技术实现了计算机硬件之间 的连通，w e b 技术实现了网页之间连通，而网格技术则试图实现互联网上所有资源的全 面连通，包括计算资源、存储资源、通信资源、软件资源、信息资源、知识资源等。 与其它的分布式系统相比较，网格计算有如下的重要特点1 2 】： ( 1 ) 分布与共享：分布性是网格计算的一个最主要的特点。网格计算的分布性， 首先是指网格的资源是分布的，即不同计算能力的计算资源、各种类型的数据库、各种 仪器设备等分散在地理位置不同的地方。网格资源虽然是分布的，但是它们却是可以充 分共享的，即网格上的任何资源都可以提供给网格上的任何使用者，共享是网格的目的。 分布是网格硬件在物理上的特征，而共享是在网格软件支持下实现的逻辑上的特征，这 两者对于网格来说都是十分重要的。 ( 2 ) 自相似性：网格的局部和整体之间存在着一定的相似性，局部往往在许多地 方具有全局的某些特征，而全局的特征在局部也有一定的体现。网格的自相似性在网格 的建造和研究过程中有重要的意义。 ( 3 ) 动态性与多样性：对于网格系统来说，它所拥有的资源和服务不是一成不变 的。例如原来拥有的资源，在下一时刻可能就会出现故障或者不可用；而原来没有的资 基于蚁群算法的网格多q o s 任务调度研究 源，可能会不断地加入系统。网格资源的这种动态变化特点要求网格管理必须充分考虑 并解决好这一问题。网格资源是异构和多样的。在网格环境中可以有不同体系结构的计 算机系统和类别不同的资源，因此网格系统必须能够解决这些不同结构、不同类别资源 之间的通信和互操作问题。 ( 4 ) 自治性与管理的多重性：网格上的资源，首先是属于某一个组织或者个人的， 资源拥有者有对他的资源自主的管理能力，这就是网格的自治性。但是网格资源也必须 接受网格的统一管理，这样才能实现网格资源的共享和共操作。因此网格的管理具有多 重性，一方面它允许网格资源的拥有者对网格资源具有自主性的管理，另一方面又要求 网格资源必须接受网格的统一管理。 网格之父i a n f o s t e r 限定网格必须同时满足三个条件f l j ： ( 1 ) 在非集中控制的环境中协同使用资源。网格整合各种资源，协调各种使用者， 这些资源和使用者在不同控制域中，比如，个人电脑和中心计算机，相同或不同公司的 不同管理单元。网格还解决在这种分布式环境中出现的安全、策略、使用费用、成员权 限等问题。 ( 2 ) 使用标准的、开放的和通用的协议与接口。这些协议与接口解决认证、授权、 资源发现和资源存取等基本问题。 ( 3 ) 提供非平凡的服务质量。网格允许它的资源被协调使用，以得到多种服务质 量，满足不同使用者的需求。 2 2 网格中间件g io b u s g l o b u s 项目是目前国际上最有影响的网格计算项目之一。它发起于九十年代中期， 其前身是i - w a y 试验环境项目，它的最初目的是希望把美国境内的各个高性能计算中 心通过高性能网络连接起来，方便美国的大学和研究机构使用，提高高性能计算机的使 用效率。随着对g l o b u s 项目的深入研究，针对它的目标也进一步扩展，希望通过g l o b u s 项目可方便对地理上分布的研究人员建立虚拟组织，进行跨学科的虚拟合作。目前， g l o b u s 项目把在商业计算领域中w e bs e r v i c e 技术融合在一起，希望不仅仅局限于科学 计算领域，而且能够对各种商业应用进行广泛的、基础性的网格环境支持，实现更方便 的信息共享和互操作，从而对商业模式、工作方式和生活方式产生深远的影响。一些重 要的公司，包括m m 和微软等都曾公开宣布支持g l o b u st o o l k i t 。目前大多数网格项目 都是采用基于g l o b u st o o l k i t 所提供的协议及服务建设的，已经被应用于全球数百个站 点和几十个主要的网格汁算项目：n a s a 网格( n a s ai p g ) 、欧洲数据网格( d a t a 嘶d ) 和 大连理工大学硕士学位论文 美国国家技术网格f n t g ) 等。 g l o b u s 对信息安全、资源管理、信息服务、数据管理以及应用开发环境等网格计算 的关键理论和技术进行了广泛的研究，开发出能在多种平台上运行的网格计算工具包软 件( g l o b u st o o l k i t ) ，能够用来帮助规划和组建大型的网格试验和应用平台，开发适合 大型网格系统运行的大型应用程序。g l o b u si 具包是g l o b u s 最重要的实践成果，目前 最新版本是g t 4 e 4 1 。g t 4 的架构图如图2 1 。 e 习e 司亘互臣 图2 1 g l o b u st o o l l ( i 14 架构图 f i g 2 1 t h ef r a m e w o r ko fg l o b u st o o l k i t 如图2 1 所示g t 4 主要包括5 个部分：s e c u r i t y ( g s i ，安全) ，为网格通信提供保 密性、完整性和回放保护( 为了防止监听和中间人攻击) ，并为网格用户提供单点登录 和权限委托的能力；d a t am g m t ( 数据管理) ，提供网格下的存储管理，副本管理、数 据传输等功能；e x e c u t i o nm g m t ( 任务管理) ，提供了一个可靠的执行环境，帮助实现 信任证书的管理，从而提交作业，监视作业的进展状况，控制作业的执行情况，并分阶 段地处理相关的数据；i n f os e r v i c e ( 信息服务) ，提供对网格计算环境中信息的发现、 注册、查询、修改等功能，动态反应一个真实、实时的网格计算环境；c o m m o nr u n t i m e ( 公共运行库) ，支持各个组件的运行。 基于蚁群算法的网格多q o s 任务调度研究 2 3 网格任务调度问题 网格资源管理通常由三个部分组成【5 】，分别是资源发现、资源匹配和任务执行。其 中资源发现部分是在所有可用的资源中找出满足任务要求的资源；资源匹配部分是从发 现的资源中找到一个最合适的资源分配给任务，是资源和任务的匹配；任务执行部分是 把任务传送到资源匹配部分找到的资源上去执行。资源如何匹配是网格资源管理需要解 决的核心问题，对网格的性能起着决定性的作用。网格的主要目的就是当用户提交任务 时，网格可以综合分析和评价所有共享资源，将任务分配到最合适的资源上执行，由于 网格中的用户数量巨大，提交任务种类和数目千差万别，使得网格的任务调度策略显得 尤其重要。 由于网格系统具有动态、异构、广域的特点，在网格计算系统下，任务调度需要考 虑任务特性、机器特性，为不同任务匹配不同的资源，从而提高系统资源的利用率和任 务的执行效率。由于网格计算中任务调度是一个n p 完全问题，它引起了众多学者的关 注，成为目前网格计算研究领域的一个焦点。 网格调度和传统分布式系统的调度系统的主要区别6 j ： ( 1 ) 有效范围不同 网格调度器的有效范围是i n t e m e t ，网格环境下资源全局状态对调度系统而言是不 确定的，对一般分布式系统而言，资源调度器是可见的。 ( 2 ) 操作对象不同 传统调度系统面对的是组织内部的，执行实际任务的计算单元、存储单元。而网格 调度面对的是不同系统之间的调度实例，本身不涉及具体的资源。因此，网格调度器又 被称为是元调度器，它是建立在现有的调度系统之上的一层中间层，任务是为不同系统 之间的调度实例的协同工作提供标准的系统服务和协议。 ( 3 ) 标准的开放性不同 由于不同的系统需要通过网格调度系统来通信，所以势必要求通信协议的标准性和 开放性，如w s r f 、w e bs e r v i c e s 、x m l 等。而对于系统内部的调度器，可以根据自身 的需要，综合考虑性能等方面的因素，定制自己的通信协议。对网格资源的访问通常需 要遵循资源管理者定义的访问权限、记帐、优先级和安全机制，这些机制是由资源所在 的不同系统来自主管理的。因此，支持自主系统之间交互的高层调度服务( s c h e d u l i n g s e r v i c e ) 是进行网格调度的技术关键。同时，调度系统也需要根据作业的实际情况( 批 处理作业或实时作业) 定义不同的调度策略以满足q o s ，这些将是网格调度系统设计的 基本原则。 大连理工大学硕士学位论文 简单地说，网格计算任务调度的目标就是要对用户提交的任务实现最优调度，并设 法提高网格系统的总体吞吐率。具体的目标包括：最优跨度( m a k e s p a n ) 、服务质量 q o s ( q u a l i t yo fs e r v i c e ) 、负载均衡( l o a db a l a n c i n g ) 、经济原则( e c o n o m i cp r i n c i p l e s ) 等。 ( 1 ) 最优跨度( 最短完成时间) 跨度是一个最主要、最常见的目标，指的是调度的长度，也就是从第一个任务开始 运行到最后一个任务运行完毕所经历的时间。跨度越短说明调度策略越好。当用户向网 格系统提交任务后，最大的愿望是网格系统尽快完成自己的任务。可见，实现最优跨度 是用户和网格系统的共同目标。 ( 2 ) 服务质量q o s 网格系统要为用户提供计算和存储服务时，用户对资源的要求是通过q o s 形式反映 出来的。任务管理与调度系统在进行分配调度任务时，保障网格应用的q o s 是完全应当 的。本文研究的目的是在网格任务调度的同时尽可能地满足用户的q o s 需求。 ( 3 ) 负载均衡 在开发并行和分布计算应用时，负载平衡是一个关键问题。网格系统更进一步扩展 了这个问题。网格任务调度是涉及交叉域和大规模应用的调度。解决好系统的负载均衡 是一个非常重要的问题。 ( 4 ) 经济原则 网格环境中的资源在地理上是广泛分布的，而且每个资源都归属于不同的组织，都 有各自的资源管理机制和政策。根据现实生活中的市场经济原则，不同资源的使用费用 也应是不相同的。市场经济驱动的资源管理与任务调度必须使消费双方( 资源使用者和 资源提供者) 互惠互利，才能使网格系统长久地发展下去。 2 4 网格任务调度算法研究现状 目前，国内外已经有很多学者针对网格下的任务调度算法进行研究，其中 m i n m i n l 7 1 ，m a x m i n 7 1 ，s u f f e r a g e 蜘等是比较简单有效的启发式算法。 m i n m i n 算法计算每个任务在各个资源上的期望完成时间，获得每个任务的最早完 成时间及其资源机器，再将具有最小最早完成时间的任务指派给获得它的资源，指派完 成后就更新资源就绪时间，并将已分配的任务从任务集合中删除。如此重复，直到全部 任务分配完毕。 m a x m i n 算法与m i n m i n 算法的思想基本相同，区别是m a x m i i l 算法首先考虑长 任务，当获得每个任务的最早完成时间及其资源时，不是将具有最小最早完成时间的任 基于蚁群算法的网格多q o s 任务调度研究 务进行分配，而是对具有最大最早完成时间的任务进行分配。但是以上的算法都没有考 虑用户的q o s 需求，之后有学者提出了以q o s 为指导的任务调度算法。 h e 等人【9 】第一次将q o s 约束加入任务调度算法中，通过改进经典的任务调度算法 m i n m i t t 算法，提出了一个自适应、以性能q o s 为向导的m i n - m i n 启发式算法。该算 法它只考虑了网络带宽约束，网络带宽会影响任务完成时间，因此在某种情况下性能较 好，但是不适合多维q o s 约束的情况。 w e n g 等人【1 0 】对s u f f e r a g e 算法进行改进，以平均响应时间作为q o s 约束提出了 q o s s u t t e m g e 算法，在计算s u f f e r a g e 值时乘以响应率的平方，将响应时间也作为影响 任务调度的因素。该算法也只是考虑了平均响应时间一维q o s 情况，同样也不适用多 q o s 约束。 陈晶等人【l l 】在任务完成期限和网络带宽的双重属性约束下结合预测机制，提出了网 格资源调度算法s e n i o r 。根据网格任务的预测执行时间，调整任务的发送顺序和改变分 配的目标资源，该算法有比较好的任务完成率，但是没有提出具体的预测机制。 伍之昂等人【1 2 】提出了网格q o s 的层次结构模型，并对其中承上启下的虚拟组织层 q o s 参数进行了新的分类和测量；然后，利用s n a p ( s e r v i c en e g o t i a t i o na n da c q u i s i t i o n p r o t o c 0 1 ) 协议对基于网格q o s 层次结构模型的网格q o s 参数的映射转换过程进行了 分析，并运用相关的网格q o s 的研究改进了现有的m i n m i n 算法，与原始m i n m i n 等 算法进行比较获得较好的结果。 张伟哲等人【1 3 通过对多q o s 约束的网格作业调度问题分析，提出多q o s 约束的网 格作业调度问题可规约为多目标组合最优化问题，在此基础上，通过引入多目标最优化 理论及其演化算法，提出了一种解决多q o s 约束的网格作业调度多目标演化( 多目标遗 传) 算法q o s - n s g a - i i 1 。 在异构计算方面，也有很多学者提出了结合服务质量q o s 的任务调度算法，并且考 虑了多维q o s 需求。 t r a e yd b r a u n 等人【1 4 】提出了异构计算环境下关于独立性、优先级、时间期限和多 个版本的静态任务调度算法，针对带有多个q o s 约束的任务调度模型，将遗传算法， g e n i t o r 算法，基于m i n - m i n 的两阶段贪婪算法应用于该模型。经过仿真实验结果表 明，g e n i t o r 算法相比其他算法有最好的结果，基于m i n m i n 的两阶段贪婪算法也有 较好的性能，而且运行时间更短。 g o l c o n d ak 等人1 1 5 】采用具有安全性、优先级、最迟完成时间等q o s 约束的任务调 度模型，对q s m t s i p 、m i n - m i n 、g e n e t i ca l g o r i t h m 、l e a s ts l a c kf i r s t 和s u f f e r a g e 5 种 大连理工大学硕士学位论文 启发式任务调度算法进行了比较，在这些算法里添加上q o s 属性要求来进行改进，分别 以用户满意数，m a k e s p a n 和任务总效用作为指标进行比较，实验结果表明g a 和m i n m i n 都可以获得比较好的结果。 因为网格环境下的任务调度是n p 难解问题，适合用遗传算法、粒子种群算法等智 能优化算法来解决，蚁群算法亦是其中一种。蚁群算法的优点包括：鲁棒性强，具有正 反馈机制，避免早熟现象等。而且蚁群算法具有很好的扩展性即在一个规模r l 的问题上 求出最优解后，再增加m 个节点，可在原有基础上快速找到该问题的最优解。蚁群算法 的这个优点可以很好的解决网格的动态特性，因此蚁群算法很适合解决网格计算中的调 度问题。一些基于蚁群算法【1 7 j 的网格调度算法已被提出，并且获得了较好的结果。 z h i h o n g x 等人【l6 j 首次将蚁群算法应用到网格任务调度中，提出了基于蚁群算法的 网格任务调度算法，使用的是基本蚁群算法( 蚂蚁系统) 。r u a y s h i u n g 等人1 1 7 】以负载 平衡为目标提出了基于平衡蚁群优化网格任务调度算法，并将该算法应用于真实的网格 环境下，取得了较好的结果。但是它们没有考虑q o s 因素。 综上所述，虽然已经有很多学者在研究网格任务调度问题时考虑了q o s 约束，但是 部分算法只考虑了单一的q o s 约束，而考虑了多个q o s 约束的算法性能并没有获得很大 的提升，与m i n - m i n 算法相比，m i n - m i n 算法仍然占优势。研究表明蚁群算法可以很好 的解决网格调度问题，但是还没有学者在应用蚁群算法时考虑q o s 约束。本文进一步将 蚁群算法应用多q o s 约束网格任务调度问题中，从而提出了基于蚂蚁系统的网格多q o s 任务调度算法( q a c 0 ) 。由于蚂蚁系统的缺陷，出现很多改进的蚁群算法，其中蚁群系 统对调度问题具有很好的效果。大量关于元启发式算法的文献告诉我们，把局部搜索算 法和生成初始解的机制相结合是一条获得高质量解的有效途径。因此本文再结合局部搜 索改进蚁群系统提出了q i a c 0 算法，并对改进的m i n - m i n 和q o s - m i n m i n 进行仿真实验 对比。 2 5 本章小结 本章首先简单介绍了网格的基本概念、网格中间件g l o b u s 。然后介绍了网格任务调 度问题，说明了任务调度问题是网格研究的一个重要问题，是现在研究的热点。最后分 析了国内外网格任务调度算法的研究状况，并分析了他们的缺陷和不足之处，从而提出 了将蚁群算法和多q o s 约束应用到网格任务调度问题。 基于蚁群算法的网格多o o s 任务调度研究 3网格多q o s 任务调度模型 服务质量q o s ( q u a l i t yo f s e r v i c e ) 是网格系统的一个重要的性能指标l l j ，所以网格 的资源调度策略应该考虑用户的q o s 需求。近年来，这个问题已成为国内外研究的热点， 即在网格的任务调度过程中为了更好的满足用户需求而在调度目标函数中综合考虑用 户q o s 需求的参数。然而，现在已有的一些任务调度算法过于简单，不能满足对q o s 的多样化需求，有些调度算法中只支持一维的q o s 需求，对于真正的网格应用，用户与 系统之间的交互应该加强，用户应能对提交的工作提出更多样的q o s 需求。 本文针对网格环境下的任务调度问题进行研究，网格环境下的任务调度模式分为即 时模式和批模式。即时模式是每当有任务到来时就立刻对该任务进行调度，而批模式采 用了周期性和任务数量限制相结合的方式，即在调度周期到达或者本次调度任务量达到 规定数量时进行调度算法的执行，大部分网格系统都采用批调度模式进行调度。本文也 采用批模式的调度方式，批模式调度中的任务也称为元任务，。元任务之间是相互独立的 【1 8 】。本文设定每个任务都带有多个q o s 需求。使用效用函数将q o s 约束转换成效用， 用于表示用户的满意度。虽然从用户角度来看，每个用户都希望最大化自己的效用，作 为调度者应该最大化所有用户的效用而不仅仅是单个用户的，因此本文的目标是从整个 系统角度考虑，最大化所有用户的总效用。 3 1 相关概念定义 网格用户可能会对资源的有一些特殊要求，比如安全性、c p u 速度、网速等，他们 希望能得到尽可能好的服务。这些要求可以以o o s 的形式包含在用户提交的任务中。在 任务调度的过程中，元调度器将根据任务中的o o s 需求，选择合适的资源与任务映射， 以满足用户的需求。 在大规模计算中，q o s 分为可度量的( m e t r i c s ) 和策略性的( p o l i c i e s ) 1 9 o 可度 量的q o s 包括服务期限等与时间相关的参数和精度等与准确性相关的参数，主要用来定 义性能参数，安全需求和任务之间的相关性等。策略性的o o s 规定了一些应用的行为来 控制资源管理器如何处理应用。本文主要考虑了可度量的o o s ，定义了网格下的o o s 模 型，参考n 蚰n 5 3 提出的q o s 模型，使之应用于网格环境下，重点考虑以下5 种o o s 约束： 时间( t i m e l i n e s s ) ：定义了某个任务相关的时间，可以是任务的完成时间、开始 时间、时间期限、执行时间。本文只考虑时间期限( d e a d l i n e ) ，每个任务都有一个可 以接受的执行时间期限。 大连理工大学硕士学位论文 可靠性( r e l i a b i l i t y ) ：网格中的机器如果长时间运行，可能会失效( 比如死机、 重启等) 。当机器失效时，在该机器上运行的任务就要重启，由此可能导致资源的浪费 或降低网格的性能。因此给每台机器设定一个失败率，来考察任务成功的概率。 版本( v e r s i o n s ) ：网格中可用的资源因为不是专用于网格，他们的属性经常改变， 因此将资源的属性分为多个版本，任务可以在不同版本下运行。本文主要考虑不同的版 本会影响任务的执行时间和用户的偏好，用户的偏好是指用户可能会更乐意在某个版本 下运行，因此每个任务针对每个机器的不同版本设定一个偏好度。 安全性( s e c u r i t y ) ：每个用户可能对他们的任务和数据都有一个安全等级要求。 安全要求包括机密性、一致性、真实性等。比如对于数据来说，一致性和真实性很重要。 为了符合用户的不同需求，给机器设定安全等级来表示任务在该机器上可以获得的安全 性的高低。 优先级( p r i o r i t y ) ：网格中的资源有限，当多个任务竞争稀有资源时，调度者应 该优先满足更重要的任务的o o s 需求。为了评价任务之间的重要性，给每个任务设定优 先级，来表示任务的重要性。在实际应用中，用户可以和调度者协商设定优先级。 虽然本文只提供了这几种典型的q o s 指标，但是本文的参数定义和解决方案可以应 用于更多的q o s 类型。 本文给出了如下的一些参数定义，方便描述算法并对算法进行仿真模拟： 定义1 ：集合r - ，l ，厂2 ，朋) 表示网格环境下的m 个异构的计算资源( 可以是一般 的p c 机或者集群等) 。 定义2 ：集合t = “，t ：，f 。) 表示一个任务集中的n 个元任务集合。本文假设元任 务之间是相互独立的，在执行过程中不会被打断。 f e t l l e t l h l 定义3 ：矩阵e t = ji；l 表示任务预期执行时间。本文假设每个任务的执 【酣。，甜。j 行时间已经预测得出，其中，甜，表示任务t ，在资源，上的预期执行时间。 定义4 ：m ( z ) ，1 i 刀，表示任务f ，被分配的资源。 定义5 ：s j = s ) l1 f 玎，1 m ) ，用户记录每个资源上的任务调度顺序，s ， 为一个调度函数，表示f ，在厂，上的执行顺序。 定义6 ：y 表示为一个版本函数，矿( f ) ，1 f ，7 是任务t ，执行时的版本。 定义7 ：每个任务t ，有巧个q o s 约束。q 。是r ，的第j 个q o s 约束的有限或无限集， 其中1 d r 。q ，为q 7 中f ，的j 维q o s 约束的具体值。q = q f l ，q 2 ，q ，4 ) 为任务， 基于蚁群算法的网格多q o s 任务调度研究 的q o s 的z 维空间，q j = q ，1 ，q ，2 ，q ，西) 为空间上的一点。在本文中d i = 5 ，分别代表 时间、可靠性、版本、安全性、优先级。 任务调度的目标是将，z 个任务分配到m 个资源上，并能达到最大的效益。 3 2 评价模型 国内外已经提出的许多网格任务调度算法中使用了多种性能指标。这些性能指标大 致可以分为两类：基于系统的目标和基于用户的目标。由于单个性能指标往往不能满足 实际应用的需要，因此人们提出多q o s t 2 眦1 1 的性能模型。 主要有以下几种指标类型： ( 1 ) 基于系统的指标 基于系统的性能模型关注整个系统资源的有效利用，通常的指标包括系统吞吐量、 资源利用率、效率和公平性等。 系统资源的利用率表明资源的忙闲程度。因为网格的目标就在于资源的有效共享和 最大利用，多数实际的调度器以此作为最主要的性能目标。然而，系统利用率与应用本 身和调度算法密切相关：对于计算密集型的任务，系统( c p u ) 利用率自然比存在上下文 切换的几个任务资源利用率高。 系统吞吐量定义为单位时间内完成的任务个数。系统执行的任务数越多，吞吐量就 越大。然而，系统吞吐量很多时候需要让位于其它指标。例如，简单的最短任务优先算 法具有最大的吞吐量，然而它对大任务是不公平的。 效率定义为最佳完成任务的程度。该指标和资源的类型异构关系密切，例如，向量 计算机用于计算关于向量的问题，具有浮点计算能力的处理机执行浮点运算被认为是有 效的。效率指标通常和提前预留( a d v a n c er e s e r v a t i o n s ) 机制相结合，主要用于资源类型 异构的计算平台。 公平性是很难度量的，然而公平性是很多调度系统追求的目标之一，例如操作系统 的多优先级队列观点常用于调度器的实现。公平性指标和任务分布情况及用户期望相 关，在具体实现时需要和某种基于市场经济的策略相结合。 ( 2 ) 基于用户的指标 基于用户的性能指标包括应用的最短完成时间( m a k e s p a n ) 、周转时间、平均延迟和 有限降级( b o u n d e ds l o w d o w n ) 、带权完成时间和( t o t a lw e i g h t e dc o m p l e t i o nt i m e ) 等。 最短完成时间是绝大多数任务调度算法所追求的唯一目标，最短完成时间定义为一 个给定应用或应用集合中最后一个任务的结束时间。