(计算机软件与理论专业论文)集群和网格环境下作业调度系统的研究.pdf_第1页
(计算机软件与理论专业论文)集群和网格环境下作业调度系统的研究.pdf_第2页
(计算机软件与理论专业论文)集群和网格环境下作业调度系统的研究.pdf_第3页
(计算机软件与理论专业论文)集群和网格环境下作业调度系统的研究.pdf_第4页
(计算机软件与理论专业论文)集群和网格环境下作业调度系统的研究.pdf_第5页
已阅读5页,还剩55页未读, 继续免费阅读

(计算机软件与理论专业论文)集群和网格环境下作业调度系统的研究.pdf.pdf 免费下载

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

华中科技大学硕士学位论文 摘要 集群系统由于其卓越的性能价格比、良好的可扩展性、高可用性和好用性,逐渐 成为当今计算机体系结构和并行处理研究的热点和主题。随着计算机和网络通信技术 的迅猛发展,人类的应用需求朝着高性能、多功能、异构和异地计算的方向发展,为 此,又在集群计算的基础之上提出了网格计算,以便更好的利用网络上的各种软硬件 资源来进行多种有效的计算。 无论是在集群环境下还是在网格环境下,作业调度都关系着高性能计算的性能, 是一个相当重要的问题。通过总结前人的工作,系统地研究了集群和网格中作业调度 的关键问题和具有代表性的集群作业管理系统和网格调度系统。多作业扫描算法m s b a c k f i l l i n g 是在综合分析当前流行作业调度算法的基础上,得到的一种改进的 b a c k f i l l i n g 调度算法。实验证明,该调度算法不但能够消除系统中大作业的饥饿现象, 而且也能提高系统的吞吐率,与普通的b a c k f i l l i n g 调度算法相比具有更好的性能。 c j m s 是从需求出发,一种采用m s - b a c k f i l l i n g 算法的集群作业管理系统,它基于b s 结构,为集群中的作业调度提供了一个基础平台。 计算网格是由众多计算站点所组成的,这些计算站点可以是大型主机或集群,在 对由集群系统所组成的计算网格的作业调度问题进行研究后,利用随机p e t r i 网对网 格容错调度进行建模,得出了网格容错调度的随机p e t r i 网模型,并利用这个模型, 对计算网格的性能进行了有效的分析。 关键词:集群,网格,作业管理系统,作业调度,p e t r i 网 华中科技大学硕士学位论文 a b s t r a c t b e c a u s eo fi t s o u t s t a n d i n gp r i c e p e r f o r m a n c er a t i oa n ds c a l a b i l i t y , a v a i l a b i l i t ya n d u s a b i l i t y , c l u s t e rs y s t e mi sb e c o m i n gt h eh o t r i o ta n dt r e n do ft h eh i g hp e r f o r m a n c e c o m p u t e r a r c h i t e c t u r ea n dp a r a l l e l c o m p u t i n gr e s e a r c h h o w e v e r , d u e t o r a p i d d e v e l o p m e n t i n c o m p u t e r a n dn e t w o r kc o m m u n i c a t i o n t e c h n o l o g y , a p p l i c a t i o n r e q u i r e m e n t se v o l v et o w a r d st h et r e n do fh i g hp e r f o r m a n c e ,m u l t i f u n c t i o n ,h e t e r o g e n e i t y a n ds oo n a sac o s t - e f f e c t i v ea n df l e x i b l es o l u t i o n ,g r i dc o m p u t i n gi sp m p o s e dt of i l lt h e n e e do fm a k i n gg o o du s eo fh a r d w a r ea n ds o f t w a r er e s o u r c e st op e r f o r me f f i c i e n t c o m p u t i n go p e m t i o n s i nc l u s t e rc o m p u t i n ga n dg r i dc o m p u t i n ge n v i r o n m e n t ,j o bs c h e d a l ei sr e l a t e dt ot h e p e r f o r m a n c e o f s y s t e m ,a n d i ti sa v e r yi m p o r t a n t i s s u e b a s e do nt h ef o r m e rw o r k sd o n e b y o t h e r s ,t h i sd i s s e r t a t i o nf i r s t l yi n v e s t i g a t e st h ee s s e n t i a li s s u e so f j o bs c h e d u l ei nc l u s t e ra n d g r i de n v i r o n m e n t ,c o m p a r e ss o m er e p r e s e n t a t i v e so fc l u s t e rj o bm a n a g e m e n ts y s t e m s o f t w a r ea n dg r i d s c h e d u l i n gs y s t e m s w ei n v e s t i g a t e s e v e r a lp o p u l a rj o b s c h e d u l i n g a l g o r i t h m s ,d e s i g n a n d i m p l e m e n t e d a b a c k f i l l i n g b a s e dm u l t i - j o bs c a n s c h e d u l i n g a l g o r i t h m 一一m s b a c k f i l l i n g t h ee x p e r i m e n t d e m o n s t r a t e st h a tt h e m s b a c k f i l l i n g s c h e d u l i n ga l g o r i t h mc a n n o to n l ys o l v e st h ep r o b l e mo f s t a r v a t i o n ,b u ta l s oi m p r o v e st h e r a t eo f s y s t e mu t i l i z a t i o n , a n dh a v eb e r e rp e r f o r m a n c ec o m p a r e d 、 ,i t l ln o r m a lb a c k f i l l i n g s c h e d u l i n ga l g o r i t h m t h e n ,w ep r o p o s eac l u s t e rj o bm a n a g e m e n t s o f t w a r ew h i c ha d o p t m s - b a c k f i l l i n gs c h e d u l i n ga l g o r i t h m ,a n dp r e s e n t i t sd e s i g na n d i m p l e m e n t a t i o n c o m p u t a t i o n a lg r i di sc o m p o s e do fm a n yc o m p u t a t i o n a ls i t e s , w h i c ha r ec l u s t e r so r m a i n f r a m e s t h ep r o b l e mo fc o m p u t a t i o n a lg r i ds c h e d u l i n gi sd i s c u s s e da n dt h ef a u l t t o l e r a n tg r i ds p n m o d e l i n g i sp r o p o s e d t h em o d e li su s e dt oh a v ea ne f f i c i e n ta n a l y s i so n t h ep e r f o r m a n c eo f c o m p u m t i o n a lg r i d f i n a l l y , w ec o n c l u d e t h et h e s i sa n dt h ew o r kd o n e b ya u t h o r , a n dg i v es o m ea s p e c t so f j o bs c h e d u l e t h a tw es h o u l dd on e x t k e y w o r d s :c l u s t e r ,g r i d ,j o bm a n a g e m e n ts y s t e m ,j o b s c h e d u l e ,p e t r in e t u 独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知,除文中已经标明引用的内容外,本论文不包含任何其他 个人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集 体,均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承 担。 学位论文作者签名:7 夺目j 日期:加华年f 月8 目 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定,即:学校有 权保留并向国家有关部门或机构送交论文的复印件和电子版,允许论文被查阅和 借阅。本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据 库进行检索,可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 保密口,在年解密后适用本授权书。 本论文属于 不保密阢 ( 请在以上方框内打“4 ”) 学位论文作者签名:7 # - 刚 日期:少。l 】 年f 月g 日 指导教师签名 日期:如¥年r 月歹日 华中科技大学硕士学位论文 1 1 问题的提出 1 绪论 随着社会和科学技术的发展,应用的不断深入,人们对计算机运行速度和处理能 力的要求越来越高,越来越多的应用领域需要高性能计算机,如科学与工程计算、决 策支持和事务处理等商业计算、大型信息服务和网络服务、数字图书馆、生物信息处 理和视频媒体系统。这些系统中,不仅要求计算机具有很强的计算能力,而且要求其 计算能力可以很容易地得到扩展、具有健壮性和很好的性能价格比。传统的并行计算 机可以满足第一个要求;但是并行计算机的部件都是专门生产的,普通用户不太了解 其内部结构,这必然造成并行计算机造价高而且不容易扩展。 随着计算机硬件技术的发展,c p u 的运算能力根据摩尔定律增长。集群系统是将 多台高配置的p c 机( 结点) 通过高速交换机连接而组成的计算机系统,它具有高运 算能力、易扩展、很好的性能价格比。它的计算能力可以和超级计算机相当。集群系 统以其卓越的性能价格比和良好的可扩展性等因素成为当今高性能计算机系统的主 流体系结构。 网格计算技术是科学家针对当今的一些科学难题于2 0 世纪9 0 年代初提出的新 概念。它将分布在不同地理位置的计算资源包括c p u 、存储器、数据库等,通过高速 的互联网组成充分共享的资源集成,从而提供一种高性能计算、管理及服务能力。人 们用这些资源就像用电能一样,不必计较这些资源的来源和负载情况。根据网格功能 的不同,可以将网格系统分为三种类型:计算网格,数据网格,服务网格。其中,计 算网格是将网络上众多的处理器计算资源连接起来,组成一台虚拟的高性能计算机, 使用户可以获得较高性能的计算服务。例如:通过网格计算技术,位于日内瓦的西欧高 能物理研究中心工作人员在网上操作,就可以把任务交给位于法国里昂的计算机集群 上去完成,而不必花许多钱去建立一个巨大的计算机集群。由于网格计算系统高效、 强大的计算能力,使得网格计算被誉为“下一代计算模式”。 无论是在集群环境下还是在网格环境下,作业调度 1 卅都是一个相当重要的问题。 本文针对上述背景,分析了集群作业调度系统的设计内容、关键技术及实现方法,并 对由集群服务器所组成的网格系统的作业调度问题进行了研究。下面先对集群和网格 环境下的作业调度做一个简要的介绍。 华中科技大学硕士学位论文 1 2 国内外研究现状 1 2 1 集群系统 集群( c l u s t e r ) 5 - 9 是用高性能网络或l a n 互相连接的多个独立计算机的集合,这些 计算机可以是单机或多处理器系统( p c 、工作站或s m p ) ,每个结点都有自己的存储器、 1 o 设备和操作系统。集群对用户和应用来说是一个单一的系统,它可以提供低价、 高效的高性能环境和快速可靠的服务。理解集群的概念要把握两点:首先,集群中的计 算机又叫结点,它们是一些完整独立的计算机系统;其次,各结点必须能够在一起协同 工作,形成一个单一的集成系统资源。集群系统的性能取决于结点的规模、结点c p u 的处理速度、结点的内存大小、i o 子系统处理速度以及通信子系统的处理速度,对 于不同的应用背景有所侧重。 集群技术可以使用户以较低的成本来改进他们的计算处理能力,提供了可扩展 性,这是一条用户可以负担得起的升级道路,在保留其现有投资、不增加过多投入的 情况下就可以使他们的计算能力得到提高。由于软件的可扩展性支持,应用程序的性 能也得到了提高。 按照应用背景的不同,可以把集群分为科学计算集群和信息服务集群。 科学计算集群支持作业级并行和程序级并行,具有灵活的体系结构。它可以按照 用户需要搭配不同的集群结点,具有对高计算量、高吞吐量应用的处理能力。它配备 了标准的科学计算编程环境,并装有集群系统管理软件和作业系统管理软件,要求高 的计算速度和低的通信延时,其性能主要由结点的规模、结点的内存大小、结点c p u 和通信子系统的处理速度来决定。科学计算集群可以应用于各种需要大规模、高性能 计算的领域,如基因数据的分析、气象预报、石油勘探等。 信息服务集群是面向信息服务领域的集群系统,具有极好的可扩展性和很高的性 价比。它采用先进的动态负载均衡技术以及高可用技术,消除集群内部的通信瓶颈, 对外则表现出很高的吞吐量和可用性。集群系统内部连接灵活的存储子系统,包括分 布式全局文件系统和高性能的存储网络,可以充分满足信息服务对大容量数据的需 求。信息服务集群可以支持大规模的w e b 、e m a i l 、f t p 、d n s 、p r o x y 、c a c h e 、f i r e w a l l 等多种服务,它要求快速的磁盘i o 处理和网络传输。 按集群中结点归属者的不同,可以把集群分为专用集群和非专用集群【l o 】。在专用集 群中,特定个体并不拥有一个工作站;资源是共享的,所以并行计算可以在整个集群上执 行。而非专用集群是指个人拥有工作站,应用程序是靠窃取空闲c p u 周期来执行的。 2 华中科技大学硕士学位论文 按照核心技术的不同,可以把集群分为两类: 第一类是高可用性集群,运行于两个或多个结点上,目的是在系统出现某些故障 的情况下,仍能继续对外提供服务。而在故障恢复之后,正在运行的服务又会切换倒 原来的服务器,从而保证了业务的不间断性和数据的完整性。高可用性集群的设计思 想就是要最大限度地减少服务中断时间。 第二类是高性能集群,目的是提供和结点个数成正比的负载能力,在这类集群中, 可以根据使用情况随意增加或删除结点,而不会影响整个集群,这种集群很适合提供 大访问量的w e b 服务,或者用于完成通常只有超级计算机才能完成的计算任务。高性 能集群往往也具有一定的高可用性特点【l ”。 本文讨论的是用于集群环境下的作业调度,因此研究的重点是高性能集群。 1 2 2 集群中的作业管理系统 作业管理系统是建立在操作系统之上的一种资源管理软件b 1 6 1 。早期的作业管理 系统是为了强化操作系统的批处理功能。随着计算机技术的不断发展,当前计算机已 经由原来的单机处理模式逐渐转化为集群处理。网络的发展使得操作系统的作业管理 功能已经不能满足时代的要求。在操作系统之上建立一种专门的作业管理软件成为必 须。 目前的几十种集群作业管理系统,在目标、结构、功能和实现上各有差异,从不 同侧面反映了集群作业管理系统所应具备的特性。p b s 、l s f 、l o a d l e v e l e r 是当 今颇具代表性和影响力的几种集群作业管理系统。其中p b s 是研究产品,l s f 、 l o a d l e v e l e r 是商业软件。下面对这几种作业管理系统进行简单介绍和讨论。 1 2 2 1p b s p b s ( p o r t a b l eb a t c hs y s t e m ) 最初由n a s a 的a m e s 研究中心开发,为了提供一 个能满足异构计算网络需要的软件包,特别是满足高性能计算的需要。它力求提供对 批处理的初始化和调度执行的控制,允许作业在不同主机间的路由。p b s 的独立调度 模块允许系统管理员定义资源和每个作业可使用的数量。调度模块有各个可用的排队 作业、运行作业和系统资源使用状况信息。使用它提供的t c l 、b a c l 、c 三种过程 语言,它的调度策略可以很容易被修改,以适应不同的计算需要和目标,即系统管理 员可以方便地实现自己的调度策略。 p b s 的主要特点有:代码开放,免费获取;支持批处理、交互式作业和串行、多 种并行作业,如m p i 、p v m 、h p f 、m p l :提供t c l 、b a c l 、c 三种过程语言,容 华中科技大学硕士学位论文 易实现新的调度策略;提供文件传送功能,f i l es t a g e 。i n 和s t a g e o u t ;满足 p o s i x l 0 0 3 2 d 标准;支持作业依赖;自动的负载平衡;完整的安全认证;提供了完 整的a p i ,方便新的调度器的开发:提供用户影像功能,使p b s 能用于用户不一致的 系统中。 1 2 2 2l s 虽 负载共享软件l s f ( l o a ds h a r i n gf a c i l i t y ) 是由加拿大平台计算公司研制与开发 的,由t o r o n t o 大学开发的u t o p i a 系统发展而来。从强大的功能和广泛使用的角度看, l s f 可谓是一个成熟的集群作业管理系统。在使用范围上,l s f 不仅用于科学计算, 也用于企业的事务处理。用户包括摩托罗拉、美国宇航局( n a s a ) 、休斯敦飞机公司、 通用电气公司、斯坦福大学等著名企业与科研团体。功能上,除了一般的作业管理特 性外,它还在负载平衡、系统容错、检查点操作、进程迁移等方面作了很好的努力, 并力图使之实用化。 l s f 的主要特点是:支持多种操作系统,包括n t 和w 1 n 2 0 0 0 ;支持检查点操作 ( 核心级、用户级及应用程序级) 和进程迁移;具有高可用性,消除单一故障点;提 供了抢占式调度和关键资源保障,保证紧急作业的调度;可通过逻辑表达式创建作业 依赖图,提供对依赖性作业的支持;提供了多神调度策略。包括r e s e r v a t i o n 和b a c k f i l l ; 动态的负载平衡与负载监测,负载指标包括结点状态、运行队列长度、c p u 利用率、 分页速率、登录用户数、空闲时间、可用交换空间、可用存贮器、t m p 目录下的可用 空间;提供了完整的负载麸享库;具有强大的资源管理功能。 1 2 2 3l o a d l e v e l e r l o a d l e v e l e r 是i b m 开发的集群作业管理系统。它成功地运行在i b ms p 2 集 群系统上。l o a d l e v e l e r 允许用户在同构或异构的集群系统中提交交互式批处理 作业。除了i b ma i x 操作系统外,它还支持h p - u x 、s g ii r i x 、s u ns o l a r i s 等主 流u n i x 平台。在教育、研究机构、企业等各行各业,l o a d l e v e l e r 以其灵活高 效的特点得以广泛应用,例如大规模的仿真、资源的优化利用、天气预报、地层模拟、 经济分析等。 l o a d l e v e l e r 的主要特点是:支持并行串行,交互式批处理作业;对工作站 主人的影响小;可定义作业类,优化调度;具有较好的系统可用性;系统中心控制; 完整的文档;分布的用户服务器;提供完整的a p i ;与n q s 兼容。 4 华中科技大学硕士学位论文 1 2 3 网格概述 网格计算是伴随着互联网而迅速发展起来的专门针对复杂科学计算的新型计算 模式。这种计算模式利用互联网把分散在不同地理位置的计算机组织成一个虚拟的 超级计算机,其中每一台参与计算的计算机就是一个结点,这种计算方式叫网格计 算【1 7 2 0 1 。这样组织起来的虚拟超级计算机有三个优势:一个是数据处理能力超强;二 是能充分利用网上的闲置处理能力;三是价格相对于超级计算机低廉。 网格计算是构筑在i n t e m e t 上的新兴技术,它将改变传统的c l i e n t s e r v e r 和 c l i e n t c l u s t e r 结构,形成新的p e r v a s i v e g r i d 体系结构,这种体系结构将使用户把整个 网络视为一个巨大的计算机,并从中享受一体化的、动态变化的、可灵活控制的、智 能的、协作式的信息服务。网格计算系统一般由网格硬件、网格操作系统、网格界面、 网格应用四层基本结构构成,其最突出的特点是资源共享、协同工作和开放性标准。 也正因为如此,网格计算目前研究发展的主要障碍便是标准协议的建立和体系结构的 确定口1 。2 4 1 。 网格技术的产生和发展必须具备以下三个基本条件:计算资源的广域分布、网络技 术以及不断增长的对资源共享的需求。在计算机技术发展的早期阶段,只有很少数量 的大型计算机,它们通常被安装在相互独立的计算中心,多个计算机用户通过使用终 端可以共享一台大型机的资源,但却不能同时共享多台大型机的计算资源。随着网络 技术的发展,多台大型计算机可以在局域网( l 灿田内互连,用户通过网络便可以同时 使用多台计算机的资源;而i n t e r n e t 的飞速发展和普及使得网格计算技术的实现成为可 能。 网格计算环境要求不影响各结点本地的管理和自主性,不改变原有的操作系统、 网络协议和服务,保证用户和远程结点的安全性,允许远程结点选择加入或退出系统, 尽量使用已存在的标准技术,以便与已有的应用兼容,并能提供可靠的容错机制。一 个理想的网格计算类似当前的w e b 服务,可以构建在当前所有硬件和软件平台上,给 用户提供完全透明的计算环境。对用户而言,它把众多同构的、异构的资源变成了同 构的虚拟计算环境。 网格的一个重要特征是实现非平凡的服务质量( q o s ) 瞄】。在服务网格中,用户关 心的服务质量不光是单一的性能因素,还包括很多其他重要因素,如可靠性、安全性 保障、错误的反馈和处理等。而且,不同的应用需要服务保证不同级别的q o s 。例如 生产型应用需要可用性高、响应时间短、安全保密性好、故障率低、容错措施强的服 华中科技大学硕士学位论文 务,而研究型应用需求的服务级别则相对较低。对应不同的服务级别,网格作业管理 系统的行为( 如资源的选择与调度策略) 也需要随之变化。 在网格计算中,首先要查清网格里所有的可用资源,比如哪些结点可供访问、还 空置多少处理能力、数据库里可供使用的数据是什么、共享的应用程序是否已准备好、 共享结点采用何种文件系统等。用户提交的任务要由系统来分配资源并控制其运行, 包括将其分配到哪些结点上运行、调用哪些数据、启动何种应用程序、何时开始运行 等。因此,网格计算至少需要具备三种基本功能:作业管理【2 6 】、作业调度1 2 7 # 8 1 和资源管 理眇3 2 1 。 ( 1 ) 作业管理:用户通过该功能向网格提交作业、为作业指定所需资源、删除 任务并监测任务的运行状态。 ( 2 ) 作业调度;用户提交的作业由该功能按照作业的类型、所需资源、可用资 源等情况安排运行日程和策略。 ( 3 ) 资源管理:确定并监测网格资源状况,收集任务运行时的资源占用数据。 1 2 4 网格环境下的作业调度 网格作业与资源管理系统作为网格系统的重要组成部分,正日益得到广泛而深入 的研究,目前大部分网格作业管理系统,不论是采用面向系统的调度策略( 如 c o n d o r - g 3 3 1 ) ,还是采用面向应用的调度策略( 如n i n l r o d ,g 【3 4 1 ,a p p l e s t 3 5 3 6 ,n e t s o l v e ) , 它们的主要调度对象是面向科学计算任务的处理器、存储器和网络等硬件资源,它们 向用户提供的接口主要是针对批处理作业提交设计的,其调度目标主要是实现计算 结点的负载平衡。他们在具体的资源管理实现和作业调度策略方面不尽相同,下文将 简单介绍其中比较突出的几例: ( 1 ) g l o b u s :由美 a r g o n n e n a t i o n a ll a b o r a t o r y 开发的网格计算工具箱,由一 系列实现基本服务的组件构成,包括:安全、资源定位、资源管理、数据管理、资源 预留和通信等。它的资源管理体系结构采用典型的层次模型,实现了层次模型的大部 分被动组件和主动组件:资源描述与访问采用可扩展模式模型、层次命名空间、软q o s 、 l d a p 网络目录存储、分布式基于查询的发现、周期性推送分发等;在任务调度方面, 提供较低级服务,支持上层资源分配或协同分配( 其中包括资源预留) ,提供高级调 度工具等。 ( 2 ) b o n d ;由美国普渡大学开发的面向对象的网格计算中间件系统。其资源管 理体系结构也是采用层次模型;资源描述与访问采用可扩展对象模型、图式命名空间、 6 华中科技大学硕士学位论文 硬q o s 、基于语言的对蒙存储与通信、基于代理的发现、周期性推送分发等;在任务 调度方面采用分布式调度器、可预测价格模型、在线重调度方法、固定的面向应用的 调度策略等。 ( 3 ) n i m r o d g :由澳大利亚的m o n a s h 大学开发,它是针对参量研究,用来管理 资源和调度应用自动执行的网格资源代理。它的资源管理体系结构采用典型的经济 市场模型;资源描述与访问使用由底层g l o b u s 或l e g i o n q b 间件服务所提供的资源模型、 依赖于计算结点的可用性、提供软和硬q o s 等;在任务调度方面采用由计算经济和截 止期限所驱动的应用级调度策略,遵循层次的、分布式的调度模型等。 ( 4 ) c o n d o r - g :为计算网格提供了一个功能全面的任务代理,用户在提交作业 时要指定该作业对资源的要求,c o n d o r - g 通过对资源的所有者与资源的消费者进行匹 配,提供了强大的资源管理功能。它作为计算网格的前台程序,用来管理运行在各个 分布式计算站点上的作业。c o n d o r - g 提供了作业监控、目志、通知、容错、身份认证 等服务,可以用来处理复杂的相关性作业。c o n d o r - g 灵活丽直观的命令方式方便最终 用户的使用,也适合高级任务代理和网格门户的接口。在c o n d o r - g 中,需要能够控制 运算结点的本地调度策略。 1 3 本文的内容与组织 1 3 1 本文的内容 本文对集群和网格中的作业调度问题进行了综合研究,其主要内容包括: ( 1 ) 提出了一种集群作业调度的改进算法; ( 2 ) 设计并实现了一个采用该调度算法的集群作业管理系统; ( 3 ) 提出集群作业管理系统的性能评价指标,并对算法加以评测: ( 4 ) 针对由集群所组成的计算网格系统,提出了一种网格作业调度的性能评价 模型。 1 , 3 2 本文的组织 下面是本文各章的内容安排: 第一章弓1 言 讨论了国内外集群、网格系统的研究现状,并介绍了其中的作业调度问题。 第二章作业调度算法 华中科技大学硕士学位论文 本章首先介绍作业调度的经典算法,然后对集群中两种性能最好的调度算法加以 分析,最后在综合前人研究的基础上,提出一种改进的调度算法( m s b a c k f i l l i n g 算 法) 。 第三章c j m s 作业管理系统 本章综合借鉴当前集群作业管理系统的实现思想及方法,利用第二章提出的 m s b a c k f i l l i n g 作业调度算法设计了c j m s 系统,并给出了c j m s 系统的实现框架。 第四章性能评测与分析 本章首先给出作业调度策略的性能评测标准,根据该标准对m s - b a c k f i l l i n g 算法 的性能进行了测试,并通过与当前所流行的作业调度算法的比较,对其性能做出了分 析与评估。 第五章计算网格作业调度模型的研究 本章研究了由集群所组成的计算网格的作业调度问题,提出了网格容错调度的随 机p e t r i 网模型,利用这个模型,可以对计算网格的性能进行有效的分析。通过专业 软件包s p n p 测出的结果,反映了故障对网格中不同类别作业的影响。 第六章对全文进行总结并展望了未来的工作。 最后是致谢和参考文献。 8 华中科技大学硕士学位论文 2 作业调度算法 本章首先阐述了作业调度的基本概念,在作业调度系统中,作业调度算法是其关 键,作业调度算法性能的优劣决定了作业调度系统的服务质量,本章综合介绍了常见 的作业调度算法,并重点分析了b a d d r l l i n g 作业调度算法,最后在此基础上提出了 m s b a c k f i l l i n g 算法。 2 1 概述 作业调度是选择作业、给作业分配资源使之得到运行机会的一个活动,作业中包 含了对计算资源要求的信息,作业调度系统的任务就是决定在何时、何处去运行作业。 从技术角度做探讨,只关心影响作业运行的物理因素,如系统的可用资源、作业需求 资源、网络负载等,这种调度称为系统调度,系统调度的主要作用在于协调作业的资 源争用矛盾、平衡系统的负载以及根据优先级关系进行选择。在现实的作业调度系统 中,除了要考虑这些纯技术因素以外,还要处理系统管理方面的一些人为规定。例如 在一个集群系统中,由作业管理系统定制的机器之间的选择关系要人为设定;用户提 交的作业中,某类作业总是优先得到运行,而某类作业只能在特定的时刻才能运行, 这种人为的作业调度称为用户调度。 从调度的机制来分,可以将作业调度分为全局调度和局部调度。全局调度一般是 指作业按某个用户定制的日历规则周期性运行或由系统事件驱动随机运行。对于局部 调度而言,系统要对作业进行动态排队,排队的依据以作业对资源的需求和作业的优 先级等因素而定:其次,系统要掌握网络上所有结点的负载情况,将作业尽可能平均 地分配到各台机器上。 由此可见,影响作业管理系统调度工作的因素主要有:系统结点的负载,作业对 资源的需求、日历规则以及调度算法。其中调度算法可以由系统或用户定制,对一些 实时性、并行性要求较高的系统需要用户定制调度算法的可能性也要大一些。 2 2 传统的作业调度算法 先来先服务口c f s ) :f c f s 是最简单也是最明显的调度策略。所有的作业根据进 入排队的顺序开始执行。当队列中的下一个作业不能得到资源开始执行时,f c f s 不 9 华中科技大学硕士学位论文 会去尝试队列中后面的作业af c f s 最大的优点是易于高效实现,而且能够保证系统 的公平性,作业的执行顺序是可以预见的。但是它牺牲了系统的吞吐率和利用率,特 别是当作业队列的下一个作业需要大数目的结点时,会出现大量空闲的机器时间间 隔,造成系统资源的极大浪费。 短时间作业优先( s p t ) : 可以在短时间内完成执行的作业优先执行,避免了某 个大作业在相当长的时间内独占系统资源,可以提高系统的作业吞吐能力,降低作 业的平均等待时间。这样做的结果会使那些迫切需要计算结果的大作业总是难以立即 执行,另外有些作业虽然计算时间长但所用计算资源类型恰恰是该集群系统最富有的 资源类型,这样的作业需求显然容易被满足,而且它的执行并不会影响其它作业的调 度执行。 f i r s t f i t f i r s t f i t 调度策略根据作业到达作业队列的顺序扫描作业队列中的作业, 执行第一个系统资源能满足其资源需求的作业。与f i f o 相比,它不会由于一个资源 需求大的作业被阻塞而影响其作业队列中后续作业的执行。也就是说,不管系统能否 满足捧在作业队列头的作业的资源需求,只要作业队列中存在作业其资源需求系统能 够满足,系统将不会停止启动执行新的作业。很明显,f i r s t f i t 调度策略能够极大地提 高系统的吞吐率。但是,其缺点也是明显的,那就是资源需求小的作业极大地延迟了 资源需求大的作业,使其可能长时间不能得到执行,从而产生饥饿现象,不能保证公 平性,从而增加系统的平均等待时间。另外,作业的执行顺序具有不可预见性。 随机调度算法( r a n d o m ) :随机调度算法和f i r s t f i t 算法很相似,只是它在从作业 等待队列中挑选下一个执行的作业时是随机进行的。因此,不管作业在等待队列中的 哪个位置,每个作业被调度的概率都是相同的,显然,与f i r s t f i t 算法相比,它更加 难以预测一个作业将在何时被调度执行。 b e s t f i t :b e s t f i t 调度策略扫描整个作业队列,从中选取当前系统能满足的资源要 求最大的作业投入运行。与f i r s t f i t 一样,它不会由于一个资源需求大的作业被阻塞 而影响其作业队列后面的作业得以执行。显然,b e s t f i t 调度策略更能提高系统的吞吐 率,但是,它也不能消除饥饿现象,不能保证公平性,作业的执行顺序也具有不可预 见性。 贪心算法( g r e e d y ) :g r e e d y 调度策略扫描整个作业队列,并将各个作业进行组 合,从中选取当前系统能满足的资源要求最大的作业组投入运行。g r e e d y 与b e s t f i t 一样,它不会由于一个资源需求大的作业被阻塞而影响其作业队列后面的作业得以执 行。而且,它比b e s t f i t 更能提高系统的吞吐率,但是,它仍然不能消除饥饿现象, 1 0 华中科技大学硕士学位论文 不能保证公平性,作业的执行顺序更具有不可预见性。 优先级调度( p f i o f i t y ) :优先级调度策略是一种比较通用的策略。首先,系统根 据各种不同的参数( 用户优先级、作业类型等) 计算出作业的优先级,然后根据优先 级对作业进行排列,生成作业队列,系统根据作业队列来逐一考虑是否运行该作业。 优先级策略的使用最好地体现了系统的公平性。优先级策略还可以和其他策略结合使 用,例如f i r s t f i t ,b a c k f i l l i n g 等等。当优先级策略单独使用时,严格按照作业的优先 级来选取作业,会产生与f i f o 一样的问题,即当高优先级作业的资源要求不能得到 满足时,低优先级作业也都将被阻塞,即使系统能够满足其资源要求。这样,会导致 系统资源空闲,系统不能满负荷运行,降低系统的利用率和吞吐率。而且,低优先级 作业会长时间得不到运行,产生饥饿现象。当优先级策略和其他调度策略结合使用时, 将会具有其他调度策略的一些特征,满足不同系统的调度需要。 资源预留算法( r e s e r v a t i o n ) :为了解决在f i r s t f i t 、b e s t f i t 、g r e e d y 等作业调度 算法中的对资源要求较大的作业长时间不能得到运行的现象,对于长时间不能运行的 作业,可以采取资源预留的策略,即当一个作业在队列中等待的时间超过一定的值, 对它所需要的资源进行预留,即这些资源中的一部分成为可用时,不再分配给其它的 作业,一直到预留的所有资源都已得到满足时,将该作业投入运行。预留策略对于调 度并行作业和串行作业混合的作业队列显得尤其重要。由于并行作业需要较多的c p u 资源,它要等到几个c p u 同时空闲时才能运行。如果系统中有很多串行作业,当有 少数c p u 空闲时,它也不能被执行,而此时空闲的c p u 很容易被其它串行作业或需 要c p u 数目少的并行作业所使用。这样, 就有可能得不到运行。资源通过预留策略, 只要系统一直存在串行作业,该并行作业 就可以解决这个问题。资源预留策略虽然 解决了饥饿现象,但它导致了少量的资源空闲时间,牺牲系统资源的利用率,降低了 系统的吞吐率。 2 3 b a c k f i l l i n g 调度算法 b a c k f i l l i n g 算法即所谓回填算法1 3 7 , 3 8 】,就是充分利用作业管理系统在作业调度时 产生的时间空隙,从作业等待队列中选择合适的作业插入到这段时间段内运行,而不 影响预约作业的按时运行,从而有效利用了系统资源,避免系统资源的浪费,提高了 系统的利用率和吞吐率。在b a c k f i l l i n g 算法中,用户需要在提交作业时指定运行该作 业所需处理机的个数和其预计运行的时间,一般来说作业所需处理机的数目不会在运 华中科技大学硕士学位论文 行过程中发生改变,因而作业可以用一个矩形来表示,其横轴表示其运行时间,纵轴 表示所需要的处理机的个数。 目前,b a c k f i l l i n g 调度策略有多种不同的实现,但是不管怎样,目标都是使尽量 多的小作业得到提前运行,避免饥饿现象,提高系统的吞吐率和降低作业的平均等待 时间。其中有两种比较经典的实现,一种称为保守的( c o n s e n r a t i v e ) b a c k f i l l i n g ,另一 种称为激进的( a g g r e s s i v e ) b a c k f i l l i n g 。 2 3 1 保守的b a c k f i l l i n g 算法 在保守的b a c k f i l l i n g 算法中,每个作业均有两个参数。其中一个是该作业的预期 执行时间,另一个是该作业所需要使用的处理器的个数。当有一个新的作业到来时, 就按照以下的算法来执行: 保守的b a c k f i l l i n g 算法的描述如下: 输入: 等待作业队列( 其中每个作业均有对使用结点个数和预计运行时间的描述) ; 运行作业对列( 其中每个作业均有对使用结点个数和预计完成时间的描述) ; 当前剩余的结点个数。 算法: 1 ) 寻找作业插入点 ( 1 ) 对当前的作业时空分布图进行扫描,找到一个可以满足该作业对结点个数 要求的时间点,这个时间点称为作业插入点; ( 2 ) 从作业插入点开始,继续扫描作业时空分布图,以确保结点在作业结束之 前都是可用的; ( 3 ) 如果不行,返回步骤( 1 ) 继续扫描,直到找到一个合适的作业插入点: 2 ) 当新作业插入之后,更新作业时空分布图,从作业插入点开始执行; 3 ) 如果时间到了作业插入点,则作业立即开始执行。 如图2 1 所示,当系统中没有足够的处理机来运行等待队列中的第一个作业 ( w a i t i n gj o b l ) 的时候,系统为该作业进行资源预留,w a i t i n gj o b 2 本来可以在 r u n n i n gj o b l 作业结束之后马上就开始运行的,但这样做的话就会延误w a i t i n gj o b l 的运行,因而必须继续寻找时间插入点,由此可以看到保守回填算法中作业预留机制 可以确保作业等待队列后面的作业不会延迟前面作业的运行。第三个作业可以通过 b a c k f i l l i n g 的方式马上进行调度。 1 2 华中科技大学硕士学位论文 通过一个链表可以很方便地维护这个时空分布图,对于每一个新作业,只扫描时 空分布图一次,因此该算法的复杂性是和作业的个数成线形关系。 图2 1 b c a k f i l l i n g 调度算法的运行过程 华中科技大学硕士学位论文 以上的算法中还存在着一个问题。在现有的时空分布图的基础上,每个作业在提 交时都指定了一个开始运行时间,系统可以保证它们最迟可以在这个时间点开始运 行。但是,如果前面的作业能够在预期结束时间之前运行完毕的话,这时就会在事先 预计好的调度方案中留下空隙。 针对这种情况,一种解决方案就是去压缩现有的调度,系统将每个作业都从时间 分布图中移去,然后再重新插入。这样的话,作业最迟也可以在和以前相同的时间插 入,因而不会被延迟。 2 3 2 激进的b a c k f i l l i n g 算法 在激进的b a c k f i l l i n g 算法中,将一个小作业插入困资源预留而产生的时间间隔时, 要保证不推迟作业等待队列中在该作业前面的所有作业的运行。因此,所有的作业的 运行时刻是确定的。而在a g g r e s s i v eb a c k f i l l i n g 中,对资源预留形成的空闲时间间隙 的填充只要不影响作业等待队列中第一个作业的运行即可,而不去检查是否影响了其 他的作业。其目的是为了尽可能的提高当前系统的利用率。由于不能够预测作业将会 在队列中延迟多长时间,因此这种算法使得作业的执行无法保证。 a g g r e s s i v eb a c k f i l l i n g 算法的描述如下: 输入; 等待作业队列( 其中每个作业均有对使用结点个数和预计运行时间的播述) ; 运行作业对列( 其中每个作业均有对使用结点个数和预计完成时间的描述) : 当前剩余的结点个数。 算法: 1 ) 找到作业插入点和额外结点数( s p a r e ) ( 1 ) 根据作业的预期截止时间,对正在运行的作业进行排序 ( 2 ) 对当前的作业时空分布图进行扫描,

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论