（计算机软件与理论专业论文）计算网格中的作业调度性能分析.pdf

论文摘要 资源管理区域作为计算网格的主要组成部分，在作业调度和资源分配中起到了 重要作用。本文通过对计算网格管理域中作业调度过程的详细分析，发现管理域中 的作业都是以一种离散的随机概率到达本地调度器，然后等待计算资源的服务，当 计算资源空闲期到来，又以一种随机概率接受计算资源的服务管理域的这种作业 调度过程与排队论中经典捧队模型的任务调度过程极其相似，因此，结合捧队论和 随机过程理论，将计算网格管理域中的作业调度过程与排队论中的经典任务调度过 程进行等效，建立了服务无优先级的计算网格作业调度模型 计算网格中的作业分为网格作业和本地作业，在有些情况下，用户要求网格作 业的响应时间越短越好，有些情况下要求本地作业的响应时间越短越好，根据用户 对计算网格中作业响应时间的不同要求，本文赋予两种作业不同的服务优先级别， 优先级别高的作业具有优先获得计算资源服务的权利。因此，利用捧队论，结合作 业的不同服务优先级别，进而建立了具有服务优先级的计算网格调度模型，并通过 解析以上两个模型，得出系统的平均滞留时闯，作为计算网格作业调度性能分析的 理论依据。 通过数值计算得出多组两种模型下的作业平均滞留时闯，通过它们之间的比 较，分析两种模型下的作业调度性能。 关键词：计算网格；作业调度；捧队模型；性能分析；优先级； a b s t r a c t r e s o u r c ea d m i n i s t r a t i o nd o m a i n sa r c0 1 1 eo ft h em o s ti m p o m n tp a r t s ，a n dt h e yp l a y l l ni m p o r t a n tr o l ei nt h ej o b s e h e d u l i n ga n dn 烙o u i a l l o c a t i o n a 船w ee a r e f u l l y a n a l y z e d t l a c p r e e c s so ft h ej o bs c h e d u l i n g 缸a d m i n i s t r a t i o nd o m a i n so ft h e c o m p u t a t i o n a l 鲥d s ，w cf o u n dt h a tt h ej o b si l lt h ea d m i n i s t r a t i o nd o m a i 璐a l w a y sl 翻l c h t l a el o c a ls e l a e a t u l e ra ta 司【i 掌口矧【er a n d o mp r o b a b i l i t y , t h e nw a i tf o rt h es e r v i c ep r o v i d e db y t l a ee o m l m t a t i o n 蚴u r c c s w h 饥t l a cc o m p u t a t i o n 玎瞄如岫“：嚣a 托v a c a n t , t h ew a i t i n g j o b s 岫t oa 虻x c p tt h es e r v i c eo ft l a ee o m p t l t a t i o n 托舳删懒t l a cp r o e 淄o ft h ej o b s c h e d u l i n g 缸t l a ea a m i i l i s t r a t i o nd o m a i n si sc s l , c e i a n ys i m i l a rt ot h ep r o c e s so ft l a ct a s k s e l a c d u l i t l go ft l a ec l a s s i c a lq u e u i n gm o d e li nt h eq u e u i n gt h e o r y a c c o r d i n gt oc l u c u i n g t h e o r ya n ds t o c l a a s t i ep r o c e s s e st l a c o t y , w el a a n s f o r m e dt h ej o t , s e l a e d u l i n gp r o c e s si nt l a c c o m p u t a t i o n a lg r i d si n t ot h cc l a s s i c a lt a s ks e l a e d u l i n gp r o c e s si nq u 咖t h e o r y , a n d c o n s t r u c t e dt l a cj o t , s e l a e d u l i n gm o d e lo fe o m p u t a t i o n a l 鲥d sw h od o e s l l to w nt l a ep i l l t h ej o b si nt h ec o m p u t a t i o n a l 鲥d s 批d c 血e dt ot h eg r i dj o b sa n dl o c a lj o b s s o m e t i m e s , i i i s c i sh o p et h a tt h ed d a y i n gt i m co ft h eg r i dj o b si ss h o r t e ra n ds l a o r t c r , b u t s o m e t i m e su s c 塔l a o l 弛t h a tt h ea c l a y i n gt i m eo ft h el o c a lj o b si ss h o r t e ra n ds h o r t e r 1 3 e c a l l s ct h ed e l a y i n gt i m eo ft h eg r i dj o b sa n dl o c a lj o b si sd i f f e r e n t b yr e q u e s to fu s e r s , w ed e e m e dt h et o wk i n d so f j o b st ot o wd i f f e r e n ti r if o rs c r v 蚍a n dt h ej o b sw h o o w n r a o r ep r ic 姐a c c e p tt l a cs e r v i c eo fc o m p u t a t i o n a ll r c s o u l c l ea tp r i m a r yr a t e a c c o r d i n gt o t h eq u e u i n gt h e o r ya n dt h ed i f f e r e n tp r ij o b sf o rs e r v i c e , w ec o m u u e t e dt l a cj o b s e l a e d u l i n gm o d e li nt l a ce o m l m t a t i o n a lg r i d sw h oo w nf l u , a n d a f t e ra n a l y z i n gt h ea b o v e t w om o c l c l s , w e 啪w o r ko u tt h ea v c r a g ed d a y i n gt i m eo ft l a ct o ws y s t e m s , w h i e l ai st h e t h e o r y f o u n d a t i o n o f a n a l y z i n g t l a c j o bs e l a e d u l i n g p e r f o r m a n c e o f c o m p u t a t i o n a l g r i d s w bg o tt h ed i f f e r e n ta v e r a g ed e l a y i n gt i m e so ft h et w om o d e l sb yn t t m c r i e a l e o m l m t i n g , a n db yt h ec o m p a r eo ft h e s ed d a y i n gt i m e s , w ca n a l y z e dt h ej o bs e l a e d u l i n g p e r f o r m a n c eo f t h et w om o d e l s k e yw o r d s ：e o l l a l i u t a l t o n s l 鲥d b ；l o bs c h e d u l i n g ；q u 伽i i n gm o d d ；p e r f o r m a n c e a n l y s l s ；p i l l ； 青岛大学硕士学位论文 学位论文独创性声明 本人声明，所呈交的学位论文系本人在导师指导下独立完成的研究成果。文中 依法引用他人的成果，均已做出明确标注或得到许可。论文内容未包含法律意义上 已属于他人的任何形式的研究成果，也不包含本人已用于其他学位申请的论文或成 果。 本人如违反上述声明，愿意承担由此引发的一切责任和后果。 论文作者签名：幽 日期：叶晌l 申 学位论文知识产权权属声明 本人在导师指导下所完成的学位论文及相关的职务作品，知识产权归属学校。 学校享有以任何方式发表，复制、公开阋览、借阅以及申请专利等权利。本人离校 后发表或使用学位论文或与该论文直接相关的学术论文或成果时，署名单位仍然为 青岛大学。 本学位论文属于： 保密口，在年解密后适用于本声明。 不保密6 ( i l l 在以上方框内 论文作者签名： 导师签名： 日期；纠年阳舳 日期：钟朔f 拍 ( 本声明的皈权归青岛大学所有未经许可，任何单位及任何个人不得擅自使用) 第一章绪论 第一章绪论 上世纪舶年代中期，计算机技术与通信技术的充分结合导致了计算机网络的 飞速发展。利用网络上的海量计算资源来解决大规模复杂计算问题，成为科学研究 的必然目标。台理组织与调度网络上多个异构的元计算资源为用户服务是需要解决 的主要任务之一 1 1 研究背景 作为构建于网络环境下的基本计算单元，元计算机的开发包括两个阶段。第一 阶段是用高性能网络将地理上广泛分布的资源连接起来，建立分布式文件系统的阶 段。这一阶段中用络环境与已有的数据传送技术无缝结台，在超级计算中心的支持 下，用户可访问网络上的各种文件信息第二阶段将一个应用展开在多个计算机 上，使异构的一组计算机协调地工作于同一个问题上【l l 。 一些发达国家进彳亍了元计算机的开发与实验。i w a y i 2 m 3 项目用a t m 网络互联 美国北部1 7 个地点的超级计算机、大规模存储系统、高级显示设备等，建立了一 个大规模、多用途的元计算机测试床，有超过个的应用群体在这个测试床上进 行高性能计算、协同设计、远程资源与本地环境的耦合等实验。德国g t b - w c s 柙 项目的目标是建立一个干兆位测试床收集高速广域计算机网络上的实验数据，实 现一些需要巨大数据吞吐率的应用，耦合各种超级计算机( 元计算) 等文献【5 l 介绍了在日本、美国、英国、德国的超级计算机上进行的元计算实验验证了耦合 不同类型计算机的可行性，以及跨计算机运行并行应用的有效性 田l 1 计算两格拓扑结构 1 9 9 8 年的文献【6 】| 昆出建立计算同格。以满足不断增长的计算需求，计算网格 拓扑结构如图1 , 1 所示。计算同格被定义为一种硬件和软件的基础设施它提供对 青岛大学硕士学位论文 高端计算能力的可靠的、一致的、无处不在的、廉价的访问。之所以称计算网格为 基础设施，原因是网格汇聚了计算、数据、传感器等资源，必然有硬件基础设施实 现资源之间的互联，有软件基础设旖监视和控制整个系统。可靠的服务是用户的基 本要求，即从各式各样的网格组件获得可预测的、响应时间能忍受的服务。服务的 一致性是指访问接口的标准性、操作的标准性，就如同电力网格中的标准电压、额 定功率。无处不在的访问是指用户无论在哪里总能获得所需的网格服务只要那里 支持网格接入。廉价的访问是指网格的使用开销是用户普遍可接受的。与元计算机 相比，计算网格除了可进行元计算，更强调多种多样的计算，如临时需要的高性能 计算、协同计算等。 计算网格是对元计算机的进一步扩展，许多原先的元计算项目转变为计算网格 项目。最初的g l o b u s 项目1 7 1 为元计算机开发了一个低层工具包，提供基本机制的实 现，如通信、信息，资源定位与调度、认证和数据访问等，这些机制定义了一个元 计算抽象帆，在抽象机上可容易地构建更高级组件，如并行编程工具、元计算应用 等。9 8 年后g l o b e s 项目成为计算网格项目 8 1 9 1 ，开发的工具包用于实现计算网格中 的基本服务。k g i o n i 驯最初是美国弗吉尼亚州立大学建立的一个校园级元计算机， 远期目标是建立世界范围的虚拟计算机，且也被称作计算网格【“i p 2 1 。 如果计算网格着重数据分析与处理，则又被称作数据网格；如果计算网格着重 信息整理与挖掘，则又被称作信息网格。从用途角度，计算网格又可以是各种各样 的应用网格，如生物网格、流体计算网格和远程教育网格。目前建立或在建的网格 有口o t 埘、a p g r i d 1 4 1 、e u r o g r i d 峙i 、t e r a g r i d l l 6 1 和c h i n a g m l l 订等。 1 1 1 计算网格的作业类型 在网格研究的早期，根据元计算实验曾提出过五种网格运用模式阿，分别是分 布式超级计算，高吞吐率计算、临时需要的高性能计算、数据密集的计算和协同计 算。无论网格采用哪种运用模式，一个网格作业的运行或者局限于一个管理域【i s l ， 或者跨越多个管理域。一个管理域就是一个调度系统负责管理的资源区域，通常是 一个计算系统，如p c 、机群或m p p 系统，如图1 2 所示。因此，网格作业可分为 单系统和多系统两类。 ( i ) 单系统作业 如果用户提交的作业被完整指派到某一个计算系统，即运行局限于一个计算系 统，则该作业称作单系统作业。 m 多系统作业 如果用户提交的作业被划分成若干子作业，子作业分布于多个计算系统，即作 业是在多个计算系统上运行的则该作业称作多系统作业 2 第一章绪论 正如文献【1 9 】介绍的，网格透明地实现了分布资源的共享，实现了两个目的， 一是运行那些计算需求超过本地资源的大规模应用，即多系统作业，二是通过平衡 各计算系统的运转负荷，达到缩短作业响应时问的目的，即改善单系统作业的执行 性能。 圈1 2 管理域的同络拓扑结构 过去的很多并行程序都是在一个高端计算系统上执行的，如果把这些程序提交 到网格，则会被当作单系统作业发送到适合的计算系统。解决一些大规模复杂问题， 如飞行器整体仿真、生物领域的参数研究闭，需要大量的计算资源，这样的大规模 同格应用属于多系统作业 根据多系统作业是否需要计算系统问的数据传输，多系统作业还可分为两个子 关，即蒙特卡洛作业和分布式作业。 蒙特卡洛作业 如果不需要计算系统间的数据传输，或者需要的数据传输开销可以忽略，则多 系统作业的编程一般基于蒙特卡洛方法，这类多系统作业称作蒙特卡洛作业 蒙特卡洛方法是一种通过计算众多采样点处的目标函数以发现分布规律的方 法，因在摩纳哥的蒙特卡洛提出而得名。 ( b ) 分布式作业 如果需要计算系统问频繁的数据传输，则多系统作业的编程方法与传统的分布 式作业类似，这种多系统作业仍称作分布式作业。 在计算网格中。分布式作业可通过动态组合分布的多个单系统作业产生 1 2 1 1 2 2 m 2 1 1 2 计算网格的作业调度 在网格全球论坛f 0 1 0 b 毗g r i df o r u m ) 黼觯案【州中，低级调度实例实现计算 系统的本地调度，高级调度实例实现网格中的协同调度。通常，高级调度实例又称 青岛大学硕士学位论文 网格调度器，低级调度实例又称本地调度器。网格调度器一般不直接控制计算系统 中的资源吲，而是根据网格作业的资源分配请求，为作业选择一个或一组计算系统， 然后将分解后的资源分配请求发送给这些计算系统上的本地调度器，由本地调度器 完成最终的瓷源分配。 可见，网格调度器完成网格层次的调度，本地调度器完成本地层次的调度，网 格层次的调度主要完成作业到资源的映射，本地层次的调度主要完成作业的资源分 配与运行。网格中的作业调度分网格层次调度和本地层次调度两个阶段进行，在逐 层抽象的中问件中，网格层次调度位于聚合层。 在加入网格后，计算系统通常保留自己的本地调度器，只是增加本地调度器与 网格调度器的访问接口。因此，建立计算网格中的作业调度系统，主要是设置( 若 干个) 网格调度器，建立网格调度器之阃、网格调度器与本地调度器之间的联系， 并在网格调度器上实现网格层次的一些调度方法。 网格中的作业是否可模压闭( 即并行度可变) 、是否指定完成期限、是否需要 资源预留，本地调度器是否支持c p u 捧他式分配、是否支持作业动态迁移，这些 因素导致作业调度的多样性。 如果作业的计算系统选择只进行一次，在被发送到计算系统后作业不再迁移到 其他计算系统则这种作业调度称作静态调度。如果在运行前，作业仍可迁移到其 他计算系统，则这种作业调度称作动态调度。 如果在选择计算系统时，不过分考虑作业的详细特征，以提高平均的作业执行 性能为目标，则这种作业调度称作网格系统级调度。经验表明，一种阿格系统级调 度不可能使所有类型作业的调度取得最优性能。如果作业调度是在仔细分析作业和 网格的性能模型基础上完成的。并以优化该类型作业的执行性能为目标则这种作 业调度称作网格应用级调度。 每当网格调度器收到一个用户提交的作业。立即为之选择适合的计算系统并 将作业发送到该计算系统，这种作业调度称作在线调度。每当网格调度器收到一个 作业检查是否凑够一批作业，当凄够一批作业时，才为这些作业确定各自适合的 计算系统，这种作业调度称作批调度。 如果仅在一部分计算系统中优化作业的计算系统选择，则这种作业调度称作网 格局部调度。如果在所有计算系统中优化作业的计算系统选择，则这种作业调度称 作网格全局调度。 不同类型的作业调度适用于不同的场合。网格局部调度、计算系统作业负载的 动态变化等因素会使静态调度的性能不够理想，而动态调度可使作业动态迁移到更 适合的计算系统，削弱这些因素对调度性能的负面影响批调度可取得比在线调度 更好的网格系统性能，如c p u 利用率，但要求用户对作业完成期限的要求不能苛 第一章绪论 刻。如果完成期限临近或要求尽可能短的响应时问则应采用在线调度。单系统作 业一般采用网格系统级调度1 1 咂卅，而多系统作业常采用网格应用级调度i 捌 计算网格中的作业调度系统具有以下几个特点l 明； ( 1 ) 作业调度是面向异构平台的。由于网格系统是由分布在i n t c i n e t 上的各类资 源组成的，包括各类主机、工作站甚至p c 机，它们是异构的，可运行u n i x ， w i n d o w sn t 等各种操作系统下，也可以是上述机型的机群系统、大型存储设备、 数据库或其他设备。因此网格系统中的作业调度必须面向异构平台，并在这些平台 上实现网格作业韵调度。 ( 2 ) 作业调度是大规模的、非集中式的。由于罔格系统是一个大到整个i n t e ：m e t 的分布式系统。要实现一种全局的统一集中的作业调度管理是根本不可能的。因此。 网格的作业调度必须以分布、并行方式进行作业的管理与调度 ( 作业调度不干涉网格节点内部的调度策略。在网格系统中，各网格节点的 内部调度策略是自治的，网格作业调度系统干预其内部的调度策略是没有必要的， 也是不可能的。 ( 町作业调度必须具有可扩展性。网格系统初期的计算规模较小，随着超级计 算机系统的不断加入，系统的计算规模也必将随之扩大。因此，在网格资源规模不 断扩大、应用不断增长的情况下，网格系统的作业调度必须具有可扩展性，不致降 低网格系统的性能。 f 5 ) 作业调度能够动态自适应。网格的资源不但是异构的而且网格的结构总是 不停地改变：有的资源出现了故障。有的新资源要加入到网格中有些资源重耨开 始工作等总之，网格的动态性是明显的，所以作业调度系统必须适应网格的这种 动态性，从可利用的资源中选取最佳资源为用户提供应用服务。 1 1 3 计算网格性能的定义 过去人们常把性能归结为速度但网格性能在不同的角度有不同的解释。比如 说用户只关心应用程序的执行速度和可靠性，而系统管理员则对系统是否易于配 置、管理和维护感兴趣。可见对网格性能的评价决不能只集中在速度上，系统为进 程分配资源的效率和可用性也是要评测的内容。比如说，一台功能强大的超级计算 机它能在几分钟内就解决问题，但明天才能使用；而另一计算机集群，解决同一 问题需十几个小时。但能马上投入使用，以上两者就当前来讲哪一个性能更佳呢? 显然我们会选择后者： 作业在两格系统上执行时，网格计算资源并不是稳定不变的，它的形式和特征 都在不断地变化所以为某次执行发现“最好的”资源，并且检验资源在执行期间 是否能保持其“最好的状态，也是目前性能评价要研究的课题，因为对不同的应 青岛大学硕十学位论文 用程序来说，何谓“最好”很难有统一的标准。另外，获得某种性能所要付出的成 本也要成为评价的要素之一，因此未来的网格实现将包括一种结算机制，通常要在 服务质量和成本问达到一个最佳平衡点i “。 1 1 4 影响计算网格性能的若干因素 实际上，并行系统或分布式系统中存在的性能问题p u 在网格中也都存在。同时， 网格还有一些其特有的影响性能的因素。 ( 1 ) 网格的资源管理系统要在进程的资源请求和实际可得到的物理资源之间建 立有效的映射，因此，分配给进程的资源的适当性或合理性直接影响着此应用程序 的执行性能。 ( 2 ) 网格中的计算资源是动态变化的，这也影响着网格应用程序的性能。 o ) 在网格中，进程对资源的请求不一定在其启动运行时就能全部得以满足， 因此也会造成性能的下降。 1 1 5 计算网格性能分析面临的困难与问题 由于计算网格与常规的分布式系统相比，形成有效资源的方法是不同的，从而 实现的技术也大为不同。因此，对网格进行性能评价还面临如下一些复杂的问题。 ( 1 ) 由于形成网格的计算资源具有多样性、异构性和动态变化性，所以对它们 进行观察、对比和分析十分复杂。 ( 2 ) 网格应用程序在网格计算资源上执行，但性能评价不能只关心应用程序， 还要考虑它与计算资源的相互作用。然而网格的计算资源是不断变化的，无法提前 知道它的确切信息，这也给评价工作带来很大困难。 ( 3 ) 由于网格在抽象和物理资源问建立了映射，并且这个映射是建立在具有动 态性和多样性的实体问，所以这就出现了许多新的性能问题。这些问题必须按其典 型特征进行定义以便在性能分析中发现它们。 ( 4 ) 常规的度量和特征参数在表达网格方面还不足够，甚至不适用。是否资源 特征在虚拟级还有意义仍是个问题。网格及其应用作为新生事物，还需定义一些新 的性能术语。 ( 5 ) 性能评测中，会产生超大量的数据，它们需要被过滤、缩减以及特征提取 和智能表达。因此，开发一种先进的自动分析工具是十分必要的 ( 6 ) 在网格中，执行环境可能在程序运行过程中就会发生变化因此，事后、 离线的分析技术是不适用的需要有在线或半在线的技术来对其进行分析 c 7 ) 由于执行环境是动态变化的，所以每一次执行都无法完全重复或再现，因 此只能用动态在线操作的方法调整或优化性能，但这也是比较困难的。 6 第一章绪论 ( 8 ) 性能是由应用程序本身和计算机系统结构共同决定的。因此，对网格的性 能评测要把应用程序、系统结构以及它们的变化等多方特征考虑进去。正是由于这 种资源交互的复杂性，而且我们尚不能解决资源分配和管理必须随应用程序的变化 而变化、灵活改变资源的需求和可用性等问题，这给性能评价造成了很大的困难。 1 2 计算网格调度性能研究现状 在网格系统中，作业调度系统是其重要的组成部分，它要根据作业信息采用适 当的策略把不同的作业分配到相应的资源节点上去运行。由于网格系统的异构性和 动态性，以及运行于网格系统之中的应用程序对于资源的不同需求，使得作业调度 变得极其复杂不好的作业分配策略，将会增加作业的执行时间，降低整个网格系 统的吞吐量。 网格计算作业调度的目标就是要对用户提交的作业实现最优调度，并设法提包 网格系统的总体吞吐率。具体的目标包括；最优跨度、服务质量、负载均衡、经济 原则等。 f 1 ) 最优跨度。跨度是一个最主要、最常见的目标，指的是调度的长度，也就 是从第一个作业开始运行到最后一个作业运行完毕所经历的时问。跨度越短说明调 度策略越好当用户向网格系统提交作业后，最大的愿望是网格系统尽快完成自己 的作业可见，实现最优跨度是用户和网格系统的共同目标。 ( 2 ) 服务质量。网格系统要为用户提供计算和存储服务时，用户对资源需求情 况是通过服务质量形式反映出来的。作业管理与调度系统在进行分配调度作业时， 保障网格应用的服务质量是完全应当的。 ( 3 ) 负载均衡。在开发并行和分布计算应用时，负载平衡是一个关键匈题。网 格系统更进一步扩展了这个问题。网格作业调度是设计交叉域和大规模应用的。解 决好系统负载均衡是一个非常重要的问题。 ( 4 ) 经济原则。网格环境中的资源在地理上广泛分布的，而且每个资源都归属 于不同的组织，都有各自的资源管理机制和政策。根据现实生活中的市场经济原则， 不同资源的使用费用也应是不相同的。市场经济驱动的资源管理与作业调度必须使 消费双( 资源使用者和资源提供者) 互惠互利，才能使网格系统长久地发展下去。 目前，对两格调度的研究已经开始以上述目标为原则展开。在网格计算中，作 业调度的实质就是将月个相互独立的作业分配到埘个异构可用资源上，使得总任务 的完成时间最小以及资源得到充分利用由此可见，网格计算的作业调度是一个 n p 完全问题目 国际数学界研究n p 问题的历史开始于2 0 世纪7 0 年代。1 9 7 1 年c o o k 找到 了第一个h p 完全问题，寻求标准布尔方程解的问题，开刨了n p 完全问题研究的 青岛大学硕士学位论文 历史。到目前为止，大约有几千个问题已被证明是n p 完全问题，由于大量的n p 完全问题至今没有找到有效算法，而指数型算法对解决规模较大的问题又十分困 难，以求近似最优解为目的的启发性算法自然就受到了极大的重视i 矧。近年来，人 们提出了很多启发性智能化算法，诸如神经网络、模拟退火、禁忌搜索、遗传算法、 蚂蚁算法等，他们毫无争议地成为解决n p 问题及t s p 问题的锐利工具删。 文献 3 5 1 利用遗传算法将作业优先级数与所需计算单元数重复进行匹配，构成 种群，利用适应度函数淘汰部分染色体，通过遗传操作包括选择、交叉和变异。 最终得到优化的作业调度跨度和作业所需计算单元的个数。 文献 3 6 1 设计了一个网格计算的蚂蚁作业调度算法，该算法中还利用蚂蚁算法 的可扩展性，提出了一个简单的资源管理和作业调度的网格仿真结构。 基于a g e n t 的作业调度，其基本设计思想是：将每个网格资源节点均封装成为 一个a g e n t ，把网格系统看成是一种多层次a g e n t 系统的集合。这样，所有分布于 网格系统中不同地方的网格资源节点( 如一个机群) 就构成了底层的a g e n t 系统， 它们为基于网格的应用程序提供高性能计算能力于是，调度问题被简化成如何在 各a g e n t 之间分配计算任务并随时根据a g e n t 的变化情况进行调整以及在各a g e n t 内如何进行子作业的继续分配。文献 3 7 j 提出了一种基于a g e n t 的计算网格 ( a g e n t - b a s e dc o m p u t a t i o n a lg r i d , a c g ) 作业管理方案，给出了网格资源的描述，并 设计了实现网格资源管理的三个网格协议原型；服务登记协议，服务发现协议和服 务访问协议。描述了它们的构成要件及功能作用。该a c g 资源管理方案可为罔格 的计算资源和服务提供一个统一的高层管理框架。 文献 3 8 1 在经济原则的基础上为调度问题引入了成本概念。其核心思想是把诸 如c p u 、存储器、带宽等不同类型资源的使用情况都转变成单一的成本并按照总 成本最小化的目标，对网格系统中的作业进行调度。为此，该文献设计了网格通信 成本函数、c i u 成本函数、存储器成本函数。当一个新的作业到达后，分别计算相 应的成本函数为该作业选择一个成本最低的主机进行调度。 文献 3 9 1 # 0 提出了一个基于a g e n t 的网格管理基础设施它链接着一个性能驱 动的作业调度器，开发该调度器是为了平衡本地网格负载。每个网格调度器都使用 可预测的应用性能数据和选代启发算法，通过多处理节点达到本地负载平衡。在更 高层次上，利用同种a g e n t 的层次结构代表多网格资源。同时，通过使用服务广告 和发现机制a g e n t 之间相互写作，从而平衡全局网格的负载。文中还给出了研究 例子和相关的实验结果表明通过本地调度器和其他的a g e n t 工作写作，可对全局 的 时格负载进行平街，也显著地提高了网格执行性能和资源利用率。 除了上述调度算法之外，人们还提出了很多异构系统的启发调度算法有不少 论文试图把这些算法用于同格环境。文献1 4 0 提出了一个扩展的s u f f e t a g e ，叫 8 第一章绪论 x s u f f e r a g e 可在网格环境中调度参数扫描应用。文献【4 l 】提出了一个期限调度策略， 可使用于多客户多服务器方式，并增加了能够改进算法性能的负载纠错( l o a d c o r r e t i o n ) 和退却( f a l l b a c k ) 机制。文献1 4 7 提出了利用不同站点同时多请求的分布调 度算法。文献【4 3 】提出了主人工人( m a s t e r - w o o e r ) 应用的调度策略，该策略能动态 地检测作业的执行时间，并利用这个信息去动态地调整工人的数量，从而取得一个 理想的工效。 1 3 计算网格性能分析评价的一般方法 计算网格是在目前互联网的基础上构建起来的资源平台，因此过去对计算机 网络性能进行分析、评价的方法同样适用于计算网格。对计算机网络的性能分析与 评价可以简单地分为定性分析、评价与定量分析、评价两种。所谓定性分析，指的 是技术人员根据自己的经验对一个已有或待建的网络进行大致的性能估计，判断网 络配置能否满足用户的需要。这种方法显然是不准确的，常常要在安装或使用过程 中动态地做出一些调整阻满足用户的需求。 定量分析就是运用数学工具或测量方法找出反映网络性能的定量指标间的数 值关系以及某个或某些指标变化时对网络性能的影响。相比定性分析，定量分析更 精确地反映了网络性能的实际情况。为技术人员设计和规划网络提供了更准确、详 细的依据，使决策更科学。 常用的定量分析方法有数学分析法、计算机模拟法和实际测量法三种m 。 1 3 1 测量法 使用软件或专用硬件设备，对已经建立并正常运营的网络进行动态数据的收集 和统计分析。目前流行的大多数网络测试软件及设备均属于这种情况。一般使用一 台笔记本电脑作为网络分析机。 同络测试是保证网络高性能、高可靠性和高可用性的基本手段，最典型、最重 要的是网络协议分析仪，其典型功能是数据包的捕捉、协议的解码、统计分析和数 据流量的产生用它可以捕捉网上的实际流量、提取流量的特征，据此对网络系统 的流量进行模型化和特征化。此外，还可虬主动地产生大量的数据包旌加到网络上， 分析网络的响应或对网络系统进行加重测试。像h p 的l a t c r a e ta d v i s o r , w g 的 d o m i n o 等都属于网络协议分析仪。 比协议分析更高层次的同络性能测试工具，站在应用层的角度，使用一些基准 流量对网络系统的性能进行分析。代表性软件如c , a n y m e d e s o f t w a r c 公司的c h a r i o t 。 用于网络系统规划验证的网络系统模拟环境，价格十分昂贵，也相当复杂，发达国 家也很少使用。 青岛大学硕士学位论文 这种方法的优点是准确性较高，因为网络系统的实际情况比如响应时阃、吞吐 量等都能从使用现场实测得到。测量法对于评价和鉴定一个己经存在并正常使用的 网络是非常合适的。但这种方法局限性很明显，不能在网络建立之前预测网络的性 能。 1 3 2 数学分析法 数学分析法主要运用数学公式反映网络性能指标间的关系。只要得到了每一个 性能的量度与其它量度及影响因素之间的数学表达式，那么整个网络的性能就可以 准确地把握了。这对于网络设计、优化具有重要的意义。 采用数学分析法，需要为网络建立适当的数学模型，把一个实际的网络抽象成 一个理论上的相对简单，但又能反映真实网络情况的模型。建立模型的过程中必须 做些合理的假定，否则是很困难的，而且即便建立了模型，其求解也是非常复杂的， 甚至得不到明确的解析解。 数学分析法主要运用概率论、随机过程和排队论等数学工具，尤其是排队论， 是进行网络性能分析的有力武器。因为一个网络系统往往可以等价为一个排队系 统。 这种方法一般对系统的规模有一定的限制，而且模型的分析需要花费很大的力 气去解决复杂的数学问题，而有些问题本身是无法求出解析解的。分析方法的困难 在于难l 三 求出解析解，但一旦求出，则参数之间的定量关系就一目了然了。但当所 作的假设太多、太牵强时，往往又会使模型失去实际意义。 1 3 3 计算机模拟法 对模拟法而言，就是利用计算机在实际系统的模型上进行模拟试验，系统规模 和复杂性的限制比较小。模拟法比较适合大型系统的性能预测。利用模拟法可以较 快地达到对系统进行预测的目的，而且花费的代价较小，仅为a _ i 编制模拟程序和 上机运行并对结果进行统计分析的时问。 模拟结果和理论值之间，一般是存在误差的。采用模拟方法不是为了获取一个 绝对数值解，而是为了获得一个相对数值解。模拟法具有其他方法无法比拟的优点： 它能迅速对几种方案进行评判，从中选择出最佳方案，而不必去构造实际系统，省 时省力，节省费用，而且灵活性很大 1 3 4 综台评价法 根据用户的需要综合考虑网络的各项性能指标，给出其综合性能指标这是一 种从用户角度考虑的方法，主要用于网络选型等，适用于网络规划与优化决策支持 系统中。 1 d 第一章绪论 1 4 本文的主要工作 目前，计算网格作业调度的研究已经从很多方面展开，其中有计算网格作业的 调度框架问题，作业的调度算法问题以及作业调度的成本问题。但是，到目前为止， 还没有看到有关利用数学的方法来分析、评价计算网格作业调度性能的相关研究。 本论文技术路线就是利用排队论中的经典模型，通过对计算网格中作业本身特点以 及整个作业调度过程的细致分析，考虑被调度作业之间的差异性以及系统对作业响 应时间的要求，对系统的局部作业调度性能做了客观的分析与预测。 本论文的主要工作如下； f 1 ) 通过对计算网格作业调度过程的分析，发现计算网格中的大量网格作业以 及本地作业都是以离散的随机概率到达计算网格某管理域下的本地调度器，当计算 单元正在为作业服务而处于忙期时，这些刚刚到达的作业便在本地调度器的缓冲区 中捧队等待，等待计算单元空闲期的到来计算网格的这一作业调度过程与排队论 中经典排队模型的任务调度过程极其相似，本文的创新点就是结合排队论和随机理 论，将计算网格的作业调度与捧队论中的任务调度进行等效，建立了计算网格的无 优先级调度模型。 f 2 ) 由于计算网格中存在网格作业和本地作业，用户对这两种作业的响应时问 有着不同的要求。为了满足用户的特殊要求，本文赋予网格作业和本地作业不同的 优先服务级别，在计算单元中的作业服务完成后，根据用户的具体要求，以一定的 服务率对排队等待的网格作业或本地作业进行优先服务通过对以上过程的分析， 结合排队理论，对计算网格中的作业调度过程进行数学建模，建立了计算同格的优 先级调度模型，并对以上两种模型进行数学解析，这是本文的又一创新。 o ) 利用排队论理论，推导计算得出网格作业和本地作业在不考虑优先级别与 考虑优先缓别两种情况下的系统平均栉留时闻，并通过数值比较来分析两种情况下 平均滞留时阃的差异性。 l l 青岛大学硕士学位论文 第二章计算网格调度性能参数及其研究工具 2 1 符号表示 作业到达本地调度器的平均到达率 口 作业接受计算单元服务的平均服务率 f c f s 服务规程为先来先服务 ( f )时刻t 到达系统的作业数 x f 在本地调度器中捧队等待的作业数 工系统的作业总教( 包括等待的作业和正在接受计算单元服务的作业) w 作业在本地调度器中的等待时闻 f 作业在系统中的滞留时间( 包括等待时问和服务时间) f 4 第n 个作业的寿命 最第 个作业的更新时刻 f o ) 时刻t 随机变量f 的年龄 e + ( f ) 时刻t 随机变量f 的剩余寿命 m 6 1到达率服从指数分布，服务时间服从一般分布，一个服务员的模型 m m | 1到达率服从指数分布，服务时间服从指数分布，一个服务员的模型 ， 作业到达本地调度器的间隔时同序列 e各个作业的服务时间序列 e ( 矽)作业在本地调度器中的平均等待时间 ( 瓯) 作业在本地调度器中的平均掉队长 e ( 。)系统中作业平均数 e ( )作业在系统中的平均滞留时间( 包括等待时闻和服务时问) p 计算单元的利用宰 第二章计算网倍调度性能参数及其研究工具 x ( o 表示时间r 时系统中的作业数( 包括正在服务的作业数) x t 表示计算单元有k 个作业完成 m i n ( f ，n ) 取i 与n 的最小值 口( 船)血的高阶无穷小 霉。( 血)& 内系统到达一个作业的概率 丑。( 出) 缸时间内系统服务完一个作业的概率 咒( f ) 血时间内系统作业致由f 变为的概率 咒( r ) & 时间内系统作业数不变的概率 地 第i 类优先级作业的平均服务辜 第，类优先级作业的平均到达率 吒 表示系统处于平衡后系统中有七十顾客的概率 一个第一类作业到选时，系统的剩余服务时间 堆 第i 类作业的剩案服务时间 蚱 第i 类作业的剩余服务时同 砰 第f 类作业服务时阃的方差 巩 第一类作业的忙期 k作业占用的计算单元平均数 叫 第一类作业到达时系统中所有第1 类作业的服务时间之和 b ； 第二类作业到达时系统中所有第2 樊作业的服务时间之和 系统作业致由f 变为f + 1 的平均到达率 “ 系统作业数由f 变为f 一1 的平均服务率 青岛大学硕士学位论文 2 2 计算网格调度主要性能参数 在计算网格调度性能研究中，为了能够有效地描述系统在当前环境下的各项性 能指标，通常会根据实际需要，通过常用的系统性能分析方法，得到系统的部分性 能参数值。通过这些性能参数值的变化我们可以了解系统的当前行运状况，并在 以后的运行中根据需要加以适当的改进。以下是计算网格作业调度中的主要性能参 数【蜘。 1 容量 容量常常被不规范地称作速率或速度，它表示单位时间内网格信道上最多可以 传输的比特数，用位，秒( b p s ) 或分组，秒( p a c k e t s s ) 来衡量。对于硬件而言，容量就是 带宽。容量决定了网格的吞吐量上限。 2 吞吐量 目标站点成功接收的信息量。最大吞吐量也就是系统的容量。理想化的吞吐量 等于系统提供的负载。任何情况下吞吐量只能舟于提供的负载和系统的容量之间。 3 利用率 系统处于忙状态的时间百分比。 4 响应时间 用户提交的作业在网格系统中的滞留时间，它包括作业在系统中的传播时间、 在队列中的等待时问和作业接受计算资源服务的服务时问。本文为了突出研究重 点，忽略了作业在系统中的传播时间，只计算作业在队列中的等待时间和接受计算 单元服务的服务时问。 5 队列长度 队列长度是指在系统中的作业数( 包括正在接受服务的作业) ，而等待队长是 指系统缓冲区中排队等待的作业教，它们都是随机变量，是用户和服务机构双方都 十分关心的数量指标。显然，队长等于等待队长加上正在服务的作业数。 6 计算资源的数量 某个计算资源提供的负载一定时，网格的总负载随计算资源数量的增加而增 加。我们希望网格作业在低延迟区域，避免进入高延迟区域特别是无限延迟区域， 所咀有必要确定管理域的性能边界，这与计算资源的数量密切相关。 2 3 常用研究工具 概率论是研究计算网络性能、对模型进行分析的最基本的数学工具，同样，也 能应用于计算网格的性能分析因为概率论的研究对象是大量随机现象的统计与分 布规律，而网格中的信息不论其产生还是到达的时间都是随机的作业的长度也符 第二章计算网格调度性能参数及其研究工具 合一定的概率分布。随机过程论对研究网格性能亦有很大的帮助，但最适合的数学 工具是排队论理论，因为网格中的信息流和排队论中的顾客流非常类似i 删1 7 1 2 3 1 概率论与随机过程 1 指数分布 假设某参数a ) o ，由如下概率分布函数或概率密度函数定义的分布，称为负指 数分布，简称指数分布 荆一k “：或m 一百茗 指数分布具有马尔可夫无后效性，即在相继两次笈生事件的时间间隔工内，选 第一次发生后的某一时问( 用，表示) 为观察点。设距s 点之后的t 时间第二次发生 事件。如果第二次发生的概率与j 无关，只与两事件的时问问隔的分布函数一致， 即存在 e ( x ( ，+ f ) 、工，j ) - e ( x f ) 则称概率变量z 的分布无后效性。 2 泊松分布 概率变量z 取离散值0 ，1 ，2 ，如果对某一常量 ( a ，0 ) 存在概率质量函 数 f ( x j ) - p ( x - d = 冬一，一咀2 j ； 剐工的概