（计算机应用技术专业论文）基于蚁群算法的网格资源分配与调度研究.pdf

基于蚁群算法的网格资源分配与调度研究 摘要 新世纪以来，越来越多的科学和工程计算需要高性能计算，于是在 传统的分布式计算技术上发展了元计算、正统的网格计算和对等计算等 相关领域技术。网格环境下的资源分配与调度是一个n p 难问题，由于网 格具有的异构性、分布性和动态性，传统的资源管理方法在网格环境中 并不适用。与此同时，通过模拟自然生态机制求解复杂优化问题的新型 计算智能方法，如遗传算法，蚁群算法，免疫算法等具有很好的自适应 性。尤其是从意大利学者d o r i g o ，m a n i e z z o & c o l o m i ( 1 9 9 1 ) 提出的蚂蚁 算法( a n ta l g o r i t h m ) 开始，具有n p h a r d 性的组合优化的调度问题成为 蚁群算法的一个重要研究方向。 蚂蚁算法是解决这类问题的有效算法。在本文中，阐述了网格资源 分配与调度的相关研究。介绍了蚁群算法原理。在许智宏，孙济洲等人 的工作基础上，设计了一个网格系统模型，改进了信息素策略，将蚁群 算法引用到网格环境下的资源分配与任务调度。该算法采用伪随机比例 规则，采用最优路径蚂蚁的信息素整体更新规则与预分配时的信息素局 部更新规则恰当结合在一起的信息素策略。进而提出了具有动态信息素 局部更新规则动态蚁群算法。在此基础上，基于g r i d s i m 软件包，使用 j a v a 编程语言设计了信息索模型测试方案，对本文提出的机制进行了测 试。模拟实验表明该算法是一种快速，有效，负载更均衡的算法 关键词：网格：任务调度：资源分配：蚁群算法 i a n tc o l o n ya l g o r i t h mb a s e dr e s o u r c ea l l o c a t i o n a n dt a s ks c h e d u l i n go fg r i d a b s t r a c t f r o mt h eb e g i n n i n go ft h i sc e n t u r y , b e c a u s eo ft h eh i g h - p e r f o r m a n c e c a l c u l a t i o np e r f o r m e di nm o r ea n dm o r es c i e n t i f i ca n de n g i n e e r i n g c a l c u l a t i o n ，m e t ac a l c u l a t i o n ，鲥dc a l c u l a t i o na n dp 2 pb a s e do nt h e t r a d i t i o n a ld i s t r i b u t i n gc a l c u l a t i o nh a sb e e nd e v e l o p e d b e c a u s et h eg r i di s h e t e r o g e n e o u s ，d i s t r i b u t e da n dd y n a m i c ，t r a d i t i o n a lm e t h o d so fr e s o u r c e m a n a g e m e n t w i l ln o tf u n c t i o nw e l li ng r i de n v i r o n m e n t r e s o u r c e a l l o c a t i o na n dt a s ks c h e d u l i n go fg r i di sa l ln p h a r dp r o b l e r m a tt h e s 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 e c o m p l i c a t e do 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 g n a t u r a l e c o l o g i c a l m e c h a n i s m ，s u c ha sg e n e t i ca 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 di m m u n i t y a l g o r i t h m i sw e l ls e l f - a d a p t i v e t h es c h e d u l i n gp r o b l e mw i t hn p h a r d o p t i m i z a t i o nb e c a m eo n eo ft h ei 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 f a c o a l g o r i t h m ，s i n c ed o r i g o ，m a n i e z z o & c o l o m ip r e s e n t e da n ta l g o r i t h m i n1 9 9 1 a n ta l g o r i t h mh a sp r o v e dt ob eak i n do fe f f e c t i v ea l g o r i t h mt os o l v e t h i sk i n do f p r o b l e m s i nt h i sa r t i c l e ，r e l a t i v er e s e a r c ho f r e s o u r c ea l l o c a t i o n a n dt a s ks c h e d u l i n go fg r i dw i l lb el i s t e d ，a n dt h ea n tc o l o n ya l g o r i t h m w i l lb ei n t r o d u c e d b a s e do np r e v i o u sr e s e a r c h , t h em a j o rr e s e a r c hw o r k si n t h i sa r t i c l ea r e ：g r i ds y s t e mm o d e lw a sd e s i g n e d ，p h e r o m o n er u l ew a s e l u c i d a t e da n da l li m p r o v e da n tc o l o n ya l g o r i t h mw a sp r e s e n t e d i ta d o p t e d t h ep s e u d o r a n d o mp r o p o r t i o n a lr u l e ，a n dt h ep h e r o m o n er e n e w a lr u l e f e l i c i t o u s l yc o m b i n e dg l o b a lp h e r o m o n er e n e w a lr u l eo no p t i m u mp a t hw i t h l o c a lp h e r o m o n er e n e w a lr u l ea tp r e a s s i g n m e n t i tw a s p r o v e db y s i m u l a t i o ne x p e r i m e n tt ob eas p e e d y ，e f f i c i e n ta n d p e r f e c ta l g o r i t h mo n l o a db a l a n c e m o r e o v e r ，d y n a m i ca n tc o l o n ya l g o r i t h mw i t hd y n a m i cl o c a l p h e r o m o n e r e n e w a lw a sp r e s e n t e d f o u n d e do nt h i s ，ag r i dp h e r o m o n e m o d e ls i m u l a t i o nw i l lb ef o u n d e du p o ng r i d s i mt o o l k i t s ，u s i n gj a v at oc o d e ， r e f e r r i n gt or e l a t i v er e s e a r c h e s i tw a sp r o v e db ys i m u l a t i o ne x p e r i m e n tt ob e as p e e d y ，e f f i c i e n ta n dp e r f e c ta l g o r i t h mo nl o a db a l a n c e k e yw o r d s ：g r i d ；t a s ks c h e d u l i n g ；r e s o u r c ea l l o c a t i o n ；a n tc o l o n y a l g o r i t h m 亡西盔堂亟迨塞基王塑蕴篡鎏趁圈搔童遂筮醒量词魔班壅 第一章绪论 1 1 论文的研究背景 进入新世纪，越来越多的科学和工程计算需要高性能计算，于是在传统的分 布计算技术上发展了元计算、正统的网格计算和对等计算等相关领域技术。调度 问题在网格中仍然是一个非常重要的问题。尽管调度技术一直成为计算机学者们 研究的焦点，但传统的调度方法大多不能适应网格环境下的灵活性，动态性和自 治性。网格计算的本质是在动态变化的、拥有多个部门或团体的复杂虚拟组织中， 进行安全灵活的协同资源共享与问题求解，目前的众多网格系统在底层通信、异 构资源整合、在线控制等方面已经进行了大量的研究，并开发了各种相应的的平 台和组件。但是这些系统对于网格环境中的资源管理和调度这个复杂的问题的关 注存在不足。另一方面，自从8 0 年代以来，尤其是最近几年，试图通过模拟自然 生态机制求解复杂优化问题的新型计算智能方法，如遗传算法，蚁群算法，免疫 算法等相继出现，大大地丰富了最优化技术。拟生态方法具有很好的自适应性， 其中从意大利学者d o r i g o ，m a n i e z z o c o l o r n i ( 1 9 9 1 ) 提出的蚂蚁算法( a n t a l g o r i t h m ) 开始，具有n p h a r d 性的组合优化的调度问题成为蚁群系统的一个 重要研究方向。如何将蚁群算法引用到网格环境下的资源分配与任务调度是本文 要研究的重点。 1 2 相关研究工作 1 2 1 网格的概念及特点 网格是从电力网格中借鉴过来的一个概念，原本是希望计算力和计算资源能 够象电力一样，“打开电源开关就可以使用”，不用去关心是谁、如何提供的这些 服务【1 0 】。 网格的目标是抽象并量化计算资源，随时随地能够通过网络“定额”完成“定 量”的计算相关的工作。 网格的本质特征是分卅1 】与资源共享。分御是网格最本源的特征，网格是通过 集中分散的资源来完成计算的，资源的共享是一种集中资源的手段。 网格具有动态性和多样性。这是由于用户的需求是变化的，所以动态性是网 格需要考虑的一个基本问题。 网格具有自治性与管理的多重性。网格节点内部的自治和外部的受控整合是 网格的一个特征，分层的资源需要层次化的管理，而分层来自于网格节点的归属 亡珏太堂亟途塞 基王鞑蕴簋洼殴旦搔童涯筮配当坷廑班究 问题和性能方面的考虑。 随着互联网的不断发展，将地理上广泛分布的大量计算资源( 包括超级计算 机、集群、工作站、个人p c 等) 集合起来进行大规模的问题求解变得日益普遍， 由此产生了我们所称的“网格计算”【1 2 1 1 2 5 2 3 。 全球网格研究的领军人物、美国阿岗( 如g o 衄e ) 国家实验室的资深科学家、美 国g l o b u s 项目的领导人i a n f o s t e r 曾在1 9 9 8 年出版的网格：2 1 世纪信息技术 基础设施的蓝图一书中这样描述网格：“网格是构筑在互联网上的一组新兴技 术，它将高速互联网、高性能计算机、大型数据库、传感器、远程设备等融为一 体，为科技人员和普通老百姓提供更多的资源、功能和交互性。互联网主要为人 们提供电子邮件、网页测览等通信功能，而网格功能则更多更强，让人们透明地 使用计算、存储等其他资源。” 2 0 0 0 年，i a nf o s t e r 在文献 2 】中把网格进一步描述为“在动态变化的多个虚 拟机构间共享资源和协同解决问题。”至此，人们仍然就什么是网格而争论不休。 2 0 0 2 年7 月，i a n f o s t e r 在什么是网格? 判断是否网格的三个标准一文中， 限定网格必须同时满足三个条件：( 1 ) 在非集中控制的环境中协同使用资源；( 2 ) 使用标准的、开放的和通用的协议和接口( j a n f o s t e r 认为目前只有g l o b u s 才算 得上标准协议) ；( 3 ) 提供非平凡的服务。这三个条件非常严格，象p 2 p ( p e e rt o p e 砷、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 n f o s t e r 已经把他头脑中的网格概念描绘清楚了。但并不是所有人都 同意他的观点，例如，有许多人赞同广义的网格概念，它称作巨大全球网格g g g ( g r e a tg l o b a lg r i d ) ，它不仅包括计算网格、数据网格、 信息网格、知识网格、商业网格，还包括一些已有的网络计算模式，例如对等计 算p 2 p ，寄生计算等。可以这样认为，i a nf o s t e r 赞成狭义的“网格观”，而g g g 是一种广义的“网格观”。 不管是狭义还是广义的网格，其目的不外乎是利用互联网把分散在不同地理 位置的计算机组织成一台“虚拟的超级计算机”，实现计算资源、存储资源、数 据资源、信息资源、软件资源、存储资源、通信资源、知识资源、专家资源等的 全面共享。其中每一台参与的计算机就是一个节点，就像摆放在围棋棋盘上的棋 子一样，而棋盘上纵横交错的线条对应于现实世界的网络，所以整个系统就叫做 “网格”了。在删格上做计算，就像下围棋一样，不是单个棋子完成的，而是所 有棋子互相配合形成合力完成的。传统互联网实现了计算机硬件的连通，w c b 实 现了网页的连通，而网格试图实现互联网上所有资源的全面连通。 清华大学李三立院士将网格与信息高速公路作了比较，他说：“将先进计算 基础设施( 网格) 与信息高速公路相比较，可以说，信息高速公路是信息传输和 获取的信息基础设施；而先进计算基础设施则是信息处理的信息基础设施。虽然， 2 国内外都有不断把信息高速公路扩充频带宽度、改进路由器性能的计划；但是， 国外科学家认为：真正的下一代信息基础设施是先进计算基础设施。它将使以计 算机为主体的信息处理发生根本性的变化。” 中科院计算所李国杰院士认为：“网格不同于国外正在搞的i n t e m e t2 或下一 代i n t e m e t ( n g i ) ，网格可以称作是第三代i n t e m e t ，其主要特点是不仅仅包括计算 机和网页，而且包括各种信息资源，例如数据库、软件以及各种信息获取设备等， 它们都连接成一个整体，整个网络如同一台巨大无比的计算机，向每个用户提供 一体化的服务。” 1 2 2 网格资源管理系统 1 2 2 1 网格资源管理系统的特点 在网格计算环境中，资源是分散在各个不同地域和管理域中，由不同的组织 拥有和操作，并且在使用策略和安全机制上各不相同，即不同站点可能会使用不 同的局部资源管理系统。同时，很多应用需要同时使用多个站点上的资源，站点 自治性和分配资源时可能出现的故障需要一种特殊机制来同时分配位于多个站点 上的资源。因此网格资源管理系统具有如下特点；资源管理者的自治性；资源分 配决策的分布性；资源本身的异构性；资源的动态变化性；资源使用者的异构性 【2 6 。 资源管理是网格计算的核心问题之一，它包括资源的组织、定位、发现、调 度、分配、确认、进程创建以及准备所需资源的其它活动。资源管理提供了管理 的功能和概念，使集群能够被当作单一资源，系统管理员根据预先定义好的标准 通过资源管理软件确保资源的合理分配和使用，以最终达到资源共享的目的。在 资源管理中，面临的有唯一验证、授权、资源访问、资源发现以及资源调度等挑 战。如何对网格计算环境中的资源进行管理是实现商性能联合计算，共同完成重 大应用问题的关键 3 0 。网格中常用的资源包括：处理能力、存储系统、目录、网 格资源、分布式文件系统、分布式计算机池、计算机集群等 3 1 。 1 2 - 2 - 2 网格资源管理的分类 由于网格在逻辑上连接了属于不同的所有者或组织的多重资源，因而选择合 适的资源管理体系结构模型在最终网格( 在商业上) 是否成功上起着重要的作用。 最主要的三种网格中的资源管理体系结构模型是：分层模型、抽象所有者模型以 及计算经济模型 3 2 】。 分层模型是g l o b u s 、l e g i o n 、n i n f 等网格计算系统所使用的资源管理模型。 它较好地解决了网格计算环境给资源管理所带来的一些挑战性问题，如：站点的 自治性、底层的异构性、以及联合分配问题等。 抽象所有者模型在资源共享过程中遵循类似于快餐店的订购与交货模式，由 资源经纪人( 抽象所有者) 代表资源所有者与用户进行交互和协商。 计算经济模型将经济的概念引入网格资源管理中，它应用了市场经济中的供 求原则束对资源的所有者和使用者进行调节以保证双方均获取最大利益，建立以 用户为中心，而不是系统为中心的调度政策，提供了资源分配和管理的有效机制。 1 2 2 3 较成熟的嘲格资源管理系统 资源管理是网格研究的一个核心问题。针对网格资源管理的特点，国外一些 网格研究项目根据自己的目标设计了不同的系统 3 3 】。大体上可以分为基于g l o b u s 的和基于j a v a 的两大类。分述如下。 网格项目中首先要提到的就是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 项目中，资源和状态信息有一个基于l d a p ( 轻量级目录访问协议) 的m d s ( 元目录服务) 组成。m d s 由g i i s ( 网格检索服务) 和g r i s ( 网格信息服务) 两个组件组成。g r i s 实现了一个为了查询网格中资源提供者的当前状态、能力和 配置的统一接口。g i i s 从多个g r i s 中提取信息并集成一个单一的一致的资源信 息数据库。资源信息提供者使用一个p u s h 协议更新g r i s 。 在g l o b u s 项目中，m d s ( 源目录服务) 在资源发现方面同时使用p u s h 和p u l l 协 议。高层工具如资源代理通过查询m d s 执行资源发现。m d s 名字空间以树结构 分层组织。g l o b u s 以资源预约方式提供q o s 。g l o b u s 提供调度组件，但不提供相 应的调度策略。g l o b u s 被用于开发许多全局调度器，包括n i m r o d g a p p l e s 和 c o n d o r g 。 下面来看基于g l o b u s 的网格项目。 n i m r o d g 是一个允许在计算网格中管理和操纵任务池应用的网格资源代理。 它在资源管理上遵从分层和计算市场模型。它支持资源预约和通过计算经济学提 供q o s 。用户使用一个声明参数建模语言或g u i 设置自己的参数。用户描述q o s 请求，例如最终期限、经费预算和愿意的优化策略等。网格资源的能力通过启发 式或历史负载数据进行估计并通过周期性的重调度实现负载平衡。 4 a p p l e s ( a p p l i c a t i o nl e v e ls c h e d u l e r ) 项目是由加利福尼亚大学圣迭戈分校 ( u n i v e r s i t yo f c a l i f o r n i a ，s a nd i e g o ) 开发的，主要用于在生产网格的个人应用的调 度代理。它使用网际气象服务n w s ( n e t w o r kw e a t h e rs e r v i c e ) 的服务动态监视资源 性能的变化。a p p l e s 项目遵从由底层网格中间件系统提供资源管理模型的框架。 是一个有预测性的启发式的状念估计模型，可在线重调度和面向应用的调度策略。 c o n d o r 是由威斯康星麦迪逊大学开发的一个高吞吐量计算环境，可以管理大 量的象由不同个体拥有的p c s 、工作站和集群计算集。尽管c o n d o r 被普遍认为是 利用周期窃取窃取方式，但它可以被配置成资源共享模式。c o n d o r 环境同样遵循 分层的体系结构，为并行和顺序应用提供强大和灵活的资源管理服务。c o n d e r 系 统特别关注计算机主人对资源的控制和分配给c o n d o r 池的控制能力。但它不提供 q o s 支持。 下面来看基于j a v a 的网格项目。 j a v e l i n 是一个基于j a v a 的框架，用于内部网的并行计算的网格项目，是一个高 吞吐量的网格计算系统。j a v e l i n 系统的三个关键组件是客户或应用、主机和代理。 c l i e n t 是一个执行搜索计算资源的进程。h o s t 是提供计算资源的进程。b r o k e 是一 个协调分配资源的进程。j a v e l i n 支持计算的计件和分支跳跃模型。j a v e l i n 使用的 一个分布调度方法可实现负载平衡。j a v e l i n 使用层次型体系结构，每个代理组织 一个主机树。资源被简单的固定在一个树状名字空间的对象上。信息存储是一个 由j a v e l i n b n s 实现的网络目录。作为调度结果，主机和代理相互更新。因此，j a v e l i n 使用需求资源分发。资源发现使用基于路径的分布查询。 l e g i o n 是由维吉尼亚大学( v i r g i n i a ) 开发的一个面向对象的元系统或网格操 作系统。l e m o n 提供了一个能使异构的、地理上分布的、高性能的机器可以实现 无缝的互操作的软件框架。它给应用用户提供一个单一的、一致的、虚拟的机器。 它的对象代表了所有的网格组件。它的体系结构时遵从分层模型。能控制主机的 负载并为应用级调度提供资源预约以执行周期和批调度。l e g i o n 的资源管理体系 是分层的而调度策略是分布的。 1 2 3 任务调度算法概述 按不同的分类标准，能用于网格环境下的资源管理与任务调度算法可以划分 为不同的种类。为了叙述方便，在本文中将现有的调度方法分为一般的启发式调 度方法和其他调度方法两大类，并在第二章详细阐述本文引用的蚁群算法的原理。 5 1 2 3 1 启发式( h e u r i s t i c s ) 调度方法 1 2 3 1 1 启发式方法概述 启发式方法 2 1 是在一个合理的计算成本上寻找好的解决方法的技术，该技 术没有能力去保证可行性或最优性或者甚至在许多情况下没有能力去规定一个特 定可行的方法是多么接近最优性 1 1 】。调度规则( d i s p a t c h i n gr u l e s ) 是启发式的 例子；他们被用于选择下一个作业到在资源上去处理无论资源什么时候变成空闲。 调度规则包括e d d ( e a r l i e s td u ed a t e ) 最早预定日期和f c f s ( f i r s tc o m ef i r s t s e r v e d ) 先来先服务 3 。 由于网格环境的动态性和复杂性，因此本文所述的启发式方法都是动态的， 同时考虑到一般异构机群系统或网格环境常假定： ( 1 ) 任务是独立的( 如在文献 2 0 】中) ，即在任务之间没有通信要求。这个假 定是很常见的，例如，当许多独立的使用者提交他们的工作到一个共享计算资源 的集合时； ( 2 ) 调度是一个动态的模式。这是因为任务到达的时间可以是随机的并且在 所考虑的异构机群系统或网格环境中的一些机器或网格计算资源可能断线和新的 机器可能在线； ( 3 ) 任务没有最终期限或优先权与他们相连。 本文所引用的蚁群算法和提出的动态蚁群算法也遵循以上假定。 映射能被分类成两个范畴，即时模式启发式方法和批模式启发式方法。即时 模式启发式方法和批模式启发式方法之间的比较评定是用试验的方法研究。在批 模式中，当任务到达时，任务没有被映射到机器上；而是他们被收集到一个集合 中，这个集合是因为映射而被检测的，即预先调度了几次被称为映射事件。在映 射事件中因为映射而考虑的不受约束的任务的集合被称为一个元任任务 ( m e t a - t a s k ) 。一个元任务包括最近到达的任务( 例如，在最后一个映射事件到达 后的任务) 和在较早的映射事件被映射但没有开始执行的任务。而即时模式启发 式方法考虑仅为了映射一次的任务，批模式启发式方法考虑在每个映射事件中直 到任务开始执行前为了映射的任务。 在即时模式启发式方法中，每个任务对匹配和调度仅被考虑一次，例如：一 旦映射被计算出后就不会改变。当到达率足够低时，一个任务一到达映射者，机 器就可以被准备好去执行该任务。因此，在即时模式中使用映射者可能是有益的， 所以一个任务直到下一个映射事件开始它的执行时才需要等待。 在即时模式中，只要一个任务到达映射者，映射者就把该任务分配给机器； 在批模式中，在一个映射事件中需要被映射的无约束的任务的集合被叫作元任务 m e t a - t a s k 。( 在一些系统中，术语m e t a - t a s k 被定义在允许交互任务依存关系的一 6 个方面。) 在批模式中，对于第i 个映射事件，元任务m ，在时刻f 被映射，其中i 0 。 初始的元任务m o 由所有先于时刻f 。到达的任务组成m 。= t , l a j 0 ，由在最后的映射事件以后的任务和已经被映射但没有开始执行的任务 组成m i = 以k i q “ u 和，l a “) 。 在批模式中，映射者为了匹配和调度，考虑在每个映射事件上的一个元任务。 这能确保批模式启发式方法比即时模式启发式方法作出更好的决定成为可能的。 这是因为批模式启发式方法对一个整体的元任务有资源需求信息并且知道大量任 务的实际的执行时1 日j ( 由于更多的任务当等待映射事件时可能会完成) 。当任务到 达率很高时，将有足够多的任务去保持机器繁忙于在映射任务事件和当一个映射 正被计算时之间。( 但是，在这假定每个映射启发式方法的运行时间当比较平均任 务执行时间时是可以忽略的那样小。) 即时模式和批模式启发式方法都假定，在异构机群或网格中每个机器上的每 个机器的预期的任务执行时间估计是知道的。这些估计能在一个任务被提交执行 以前或在提交时被提供。本文引用的蚁群算法和动态蚁群算法就是在预调度时先 计算出预计执行时间后再进行调度的。 下面描述五个批模式启发式方法和三个即时模式启发式方法。 1 2 3 1 2 即时模式映射启发式方法( o n - l i n em o d em a p p i n gh e u r i s t i c s ) 这里介绍五种即时模式启发式方法：( 1 ) 最小化完成时间( m i n i m u mc o m p l e t i o n t i m e ) ，( 2 ) 最小化执行时间( m i n i m u me x e c u t i o nt i m e ) ，( 3 ) 交换( 开关) 算法 ( s w i t c h i n ga l g o r i t h m ) ，( 4 ) 百分之k 最佳( k p e r c e n tb e s t ) ，和( 5 ) 机会主义的负载配 平( o p p o r t u n i s t i cl o a db a l a n c i n g ) 。 最小完成时间( m c t ) 启发式把每个任务分配给任务完成时间最早的机器。这 使得一些任务被分配给对他们而言没有最小达到最小执行时间的机器上。最小完 成时间( m c t ) 启发式方法是来自s m a r t n e t 1 3 的快速贪婪探索式方法的一个变种。 即时模式把最小完成时间( m c t ) 启发式方法用作一项基准，例如，在性能上与其 他的启发式方法比较。当任务到达时，在h c 套件中的所有机器被检查以决定为 任务给出最早完成时间的机器。因此，映射一个给定的任务要花费0 ( m ) 时间。 最小执行时间( m e t ) 启发式把每个任务分配给执行时间的总和最小的机 器执行改任务的计算。这个启发式方法与m c t ( 最小完成时间启发式方法) 相 比，没有考虑机器的就绪时间。这种方法能在跨越机器间的负载中促成一个严峻 的不平衡。这种方法的益处是它把每个任务分给这样的机器，该机器执行该任务 的执行时间的总和最小。 7 交换( 开关) 算法( s a ) 由下面的观察激发而来。通过分配更多的任务给一 些机器而不是给其他的机器，最小执行时间( m e t ) 启发式方法能潜在地创造出 跨越机器间的不平衡，因此最小完成时间( m c t ) 探索式方法尽力去平衡负载， 通过的是对最早完成时间分配任务。如果任务的到达是随机的混合状态，在给定 的阈值以静以负载平衡为代价使用m e t 是可行的，然后使用m c t 去消除跨越 机器的负载。( s a ) 启发式方法在一个依赖跨越机器的负载分布状态的循环方式 中使用m e c 和m e t 启发式方法。目的是为了有一个具有m c t 和m e t 都理想的 属性的启发式方法。 让组件中所有机器最大的就绪时间是r m a ；最小的就绪时间是r m l 。然后，跨越 机器的负载平衡检索由石= r m 给定。参数厅是区间 o ，1 】内的任何值。如果石是 1 0 ，那么跨越机器间的负载是均匀地平衡的。如果石是0 ，那么至少一个机器还 没有被分配一个任务。，选择在区间【o ，l 】中的比值厅的两个阈值，码( 1 即l o w ) 和死( h 即h i g h ) ，因为确 。最初，石的值被设定为0 0 。s a 启发式方法开始 映射任务，在负载平衡检索的值增加到至少死之前使用m c t 启发式方法。在那 个时刻以后，s a 启发式方法开始使用m e t 启发式方法去执行任务匹配，这促使 了负载平衡检索减少。当它减少到万，或更少时，s a 启发式方法转换回来使用m c t 启发式方法去映射任务并且循环继续。 百分之k 最佳k p e r c e n tb e s t ( k p b ) 启发式当映射一个任务时考虑仅机器们的 子集。该子集由挑选出的m f k 1 0 0 ) 个基于对任务执行时问的最好的机器组成， 其中，1 0 0 m k 1 0 0 。把任务分配给予集中提供最早完成时间的机器。如果 k = 1 0 0 ，那么k p b 启发式方法退回到m c t 启发式方法。如果k = 1 0 0 m ，那么k p b 启发式方法退回到m e t 启发式方法。映射一个任务到一个机器的一个好的k 值仅 在一个由计算性优良的机器组成的子集中。目的不是如此多的把当前的任务匹配 到一个计算上比较好的机器上因它可以避免把当前的任务放在可能更适合一些一 到达的任务的机器上。关于任务异构性的“预见”在m c t 中j 下在消失，m c t 可 能把一个任务分配给一个比较差的机器，因为在完成时l 、日j 中一个直接的微小的改 善，可能剥夺一些随后到达的更好的机器的匹配任务，并最终导致一个较k p b 更 大的跨度( m a k e s p a n ) 。应该注意到当k p b 和s a 在他们的操作中都装配m c t 和 m e t 的任务时，仅在k p b 中每个任务分配试图去同时地最优化m c t 和m e t 的 目标。但是，在一个固定的对任何任务而言不在k 个最好的机器中的子集和的 情况下，k p b 较m c t 会促成更多的空闲时间并导致更差的性能。因此k p b 和 m c t 的相关性能机器的h c 套件和将被执行的任务的特征。 对每个任务而言，花费0 ( m l o g m ) 时间去归类机器以决定检测决定机器的子 集。一旦决定了机器的子集，将花费0 ( m k 1 0 0 ) 时间，例如，o ( m ) 时间去 决定机器的分配。全部k p b 探索花费o ( m l o g m ) 时间。 机会负载平衡( o l m 启发式把一个任务分配给这样的机器，该机器接下来变 成了就绪，没有考虑在该机器上的执行时问。如果多机器在同时变成了就绪，那 么就任选一个机器。o l b 启发式方法的复杂性依赖于执行。在这里所考虑的执行， 映射者可能需要考虑检查所有的m 个机器以便去找到变成接下来就绪的机器。因 此，花费o ( m ) 去找到分配。 1 2 313 批模式映射启发式方法( b a t c hm o d em a p p i n gh e u r i s t i c s ) 在这儿描述了三种批模式启发式方法：( 1 ) 最小对最小启发式方法( t h e m i n - m i nh e u r i s t i c ) ，( 2 ) 最大对最小启发式方法( t h em a x - r a i nh e u r i s t i c ) ，和( 3 ) 容 忍启发式方法( t h es u f f e r a g eh e u r i s t i c ) 。 在批模式启发式方法中，元任务在先前定义的时间间隔后被映射。这些时间 间隔在这被定义为使用了两个下面建议的策略中之一。 第一个策略称为正规的时间间隔策略，该策略在正规的时间间隔内映射元任 务( 例如，每十秒) 。一个映射将是冗余的的情况即( 1 ) 自从最后的映射后没有 新的任务已经到达的时候( 2 ) 自从最后的映射后没有任务完成执行的时候( 因此， 机器就绪时间是不可变的) 。为能被避免如此冗余的映射事件发生应去检查这些条 件。 另一策略称为固定数量策略，当满足下面两个相互排斥的条件之一，固定数 量策略就映射一个元任务m ，( a ) 一个正到达的任务使得i m i l 大于或等于一个先前决 定的随机数k ，或( b ) 在集合陬l 中所有的任务已经到达，和一个任务完成而还必 须开始的任务的数量是大于或等于k 。在这个策略中，映射时间间隔将依赖于到达 率和完成率。当等待下一个映射事件时机器空闲的可能性将依赖到达率，完成率， m 和k 。在一个真实的系统中将被映射的任务可能需要一个最大等待时间。 下面讨论在此所考虑的批模式启发式方法。 在图1 1 中出示的最小对最小启发式方法是在s m a r t n e t 1 3 d 0 被实现的启发式 方法之一。 在图1 1 中，让b 表示预期的时间即机器m 1 在已分配到它上的所有任务都 执行完成后将变成就绪态，在那时及时去执行一个任务的时间。首先用和r j 值 去计算。对每个任务，给出最早预期完成时间的机器通过观测c 矩阵( c 矩阵 由值组成) 的第i 行值所决定。 9 ( 1 ) 6 ”对元任务集合m 。中的所有任务t ( 以任何顺序) 开始循环 ( 2 ) r ) r 所有的机器( 以某一确定的任意顺序) 开始循环 ( 3 ) c - 】= e lj 乜 ( 4 )d o 直到m 。中的所有任务映射完毕为止 ( 5 ) 6 w 对m ，中的每个任务找到最早完成时间及其对应的机器 ( 6 )找到具有最小最早完成时间的任务t k ( 7 )将任务“分配到能获得最早最小完成时间的机器m 1 上 ( 8 )从m y 中删除任务t k ( 9 ) 更新r l ( 1 0 )对所有的i 更新c 。l ( 1 1 ) e n d d o 图1 1 最小对最小启发式算法 f i 9 1 1t h em i n - m i nh e u r i s t i c 有最小最早预期时间的任务t k 被决定然后被分配到相应的机器。c 矩阵和r 向量被更新，然后对还没有被分配到一个机器的任务重复上面的过程。 最小对最小通过调度这样的任务开始，该任务通过最小的数量改变预计的机 器就绪时间状况。如果任务t i 和b 竞争一个特定的机器m j ，那么最小对最小方法 把这个将较少地改变机器m ，的等待时间的任务( 说它是t 吧) 分配给机器m 】。这 增加了任务t k 还会在机器m 上有它的最早完成时间的可能性并应该被分配到机器 m l 上面。因为在t = o ，最早完成一个任务的机器也是执行该任务最快的一个，并 且由于在最小对最小启发式方法通过对每一个分配的最小数量改变机器就绪时间 状态上，被分配到他们的第一个选择( 基于预期的执行时间) 的任务的百分比在 最小对最小中可能比在这部分中所描述的其它批模式启发式方法更高。如果更大 数量的任务被分配到不仅完成他们最早而且执行他们最快的机器上，该预测是能 获得一个较小的跨度。 在图1 1 中的第( 1 ) 到第( 3 ) 行c 矩阵的初始化花费0 ( s m ) 时间。最小 对最小启发式方法的d o 循环重复s 次并且每次遍历花费0 ( s m ) 时间。因此， 该探索花费0 ( s 2 m ) 时间。 在图1 2 中出示的最大对最小启发式方法与最小对最小启发式方法的思想相 似，是在s m a r t n e t 1 3 0 0 被实现的启发式方法之一。但它不同于最小对最小启发式 方法，因为对每个任务而言，一旦发现了提供最小完成时间的机器，有最大最小完 成时间的的任务t k 被决定然后被分配到相应的机器。即在图1 1 的第六行中，“最 小”被改变成“最大”。最大对最小启发式方法与最小对最小启发式方法同样的复 杂性。 i o ( 1 ) ”对元任务集合m ，中的所有任务l ( 以任何顺序) 开始循环 ( 2 )f o r 所有的机器( 以某一确定的任意顺序) 开始循环 ( 3 )c i j = 岛 r 4 1d o 直到m 。中的所有任务映射完毕为止 ( 5 )f o r 对m ，中的每个任务找到最小完成时问及其对应的机器 ( 6 )找到具有最大最小完成时间的任务t k ( 刀将任务t k 分配到能获得最大最小完成时间的机器m l 上 ( 8 )从m ，中删除任务t k r 哪更新r l ( 1 0 ) 对所有的i 更新 ( 1 1 ) e n d d o 图1 2 最大对最小启发式算法 f i 9 1 2t h em a x - r a i nh e u r i s t i c 在图1 3 中所示的容忍启发式方法是基于以下思想：通过把一个任务分配给一 个机器可能产生一个较好的映射，该任务是指如果特定的机器没有被分配到，根据 与其完成时间会容忍大多数。让一个任务t i 的容忍值是不同于它的第二最早完成 时间( 在一些机器m ，上) 和它的最早完成时间( 在一些机器m x 上) 。换句话说， 对任务b 使用m 。将导致最好的完成时间，使用n l v 将导致第二好的。 在图1 3 中，第( 1 ) 到第( 3 ) 行是初始化阶段，这与在最小度最小和最大对 最小启发式方法的是相似的。初始时所有机器都被标记为没有被分配。在第( 6 ) 行到第( 1 4 ) 行f o r 循环的每个遍历中，从元任务晕任意地挑一个任务k 。找到对 任务t k 给出最早完成时j 日j 的机器m 1 ，如果m 1 没有被分配就试探性地将任务t k 分配 给机器m 。标记m 1 已被分配了，然后从元任务中移走任务t k 。然而，如果机器 m 】以前已经被分配了任务h ，从任务和自中选择有较高容忍值的任务，把选定 的任务分配机器m 1 ，并从元任务中移出选定的任务。未被选择的任务将不会再被 考虑为该f o r 语句的执行，而是在第( 4 ) 行开始作d o 循环的下一个遍历时将会被 考虑。当f o r 循环的所有遍历被完成时( 例如，当f o r 语句的一个执行被完成时) ， 更新每个被分配一个新任务的机器的机器就绪时间。执行丌始于第( 4 ) 行的下一 个d o 循环的遍历直到所有的任务已被映射完。 让w 是一个数字，该数字用来度量对不同机器的任务问的争用程度。那么， 容忍启发式方法的复杂性为：o ( w s m ) ，其中1 巧s s 。可见，在最差情况下口 是等于s 的，并且在最好情况下是1 ；在数字上，布的这些值分别地等于对最差和 最好情况下，在第( 4 ) 行上d o 循环的遍历的数目。 ( 1 ) ( 2 ) ( 3 ) r 4 ) f o r 对元任务集合m ，中的所有任务( 以任何顺序) 开始循环 f o r 所有的机器( 以某一确定的任意顺序) 开始循环 c i j 2 电j q d o 直到m 。中的所有任务映射完毕为止 标记所有未破分配的机器 f o r 对m ，中的每个任务( 以某一确定的任意顺序) 严对于一个给定的f o