（计算机应用技术专业论文）“上海高校网格e网格计算应用平台”任务调度策略的优化.pdf

上海人学硕十学位论文 t h ep o s t g r a d u a t et h e s i so fs h a n g h a iu n i v e r s i t y 摘要 网格技术源于2 0 世纪9 0 年代的美国政府的分布式超级计算项目i - w a y 。i 。网 格把分卸在不同地点的、不同单位的、不同计算节点的各种计算和信息服务资源， 例如计算能力、存储能力和信息服务能力，整合为一个单一的( 虚拟的) 系统。 “上海高校网格e 一网格计算应用平台”是基于o g s a 架构的网格计算环境。 主要包括四个计算资源结点和一个网格任务管理平台。这四个计算资源节点分别是： 上海大学自强3 0 0 0 集群计算机系统、上海超级计算中心曙光4 0 0 0 a 集群计算机系 统、华东理工大学s i m f a r m 集群计算机系统和上海大学自强2 0 0 0 集群计算机系统。 于2 0 0 5 年1 2 月通过了上海市级鉴定。专家对于“e 平台”的鉴定结论是“该平台 达到了国际先进水平”。本人参加了该平台所使用的基于优先级的抢先式任务调度系 统的丌发工作，认为该任务调度系统在吞吐率，资源利用率和调度环境适应性三方 面还可以改进。在论文中提出了三个任务调度优化的方案： 时间片轮转任务调度。借鉴了单机操作系统中所使用的时间片轮转算法，将 其应用到网格平台中，通过对相同任务级别的用户任务进行时间片轮转调度束达到 提高平台整体吞吐率的作用。根据网格平台的特点，将工作重点放在资源匹配的实 现上，提出了交叉匹配的思想。并且在乎台中实现了时间片轮转任务调度。 特殊缴任务调度。特殊级任务是指具有资源需求可变和任务优先级低的特点 的计算任务。在其它用户任务调度完成后，通过对特殊级任务的调度来最大限度地 把平台中的空闲资源利用起来。根据平台的实际情况，提出了特殊级任务规范，改 进了特殊级任务进行中间运行结果保存的方式。最后在平台中设计和实现了特殊级 任务调度机制。 遗传算法任务调度。为了使调度程序能够应对随着平台的发展而可能变得更 加复杂的调度环境，提出了在平台中使用遗传算法进行任务调度的想法，并且根抛 平台的实际情况，提出了遗传算法任务调度对资源优先级和任务优先级的处理方法。 最后在平台中设计和部分实现了遗传算法任务调度。 关键词：网格，上海高校网格，任务调度，优化。 上海大学硕士学位论文 t h ep o s t g r a d u a t et h e s i so f s h a n g h a iu n i v e r s i t y a b s t r a c t g r i dt e c h n o l o g yr o o t si nt h ed i s t r i b u t e d s u p e r c o m p u t i n gi - w a yp r o j e c tt h a t w a s s p o n s o r e db yu s g o v e r n m e n ti nt h e9 0 so f2 0 “c e n t u r y ag r i di n t e g r a t e sm a n y c o m p u t i n ga n di n f o r m a t i o ns e r v i c er e s o u r c e sl o c a t e di nd i f f e r e n tp l a c e s ，d i f f e r e n t c o m p a n i e sa n dd i f f e r e n tn o d e si n t oo n es i n g l e ( v i r t u a l ) s y s t e m t h er e s o u r c e si n c l u d ef o r i n s t a n c e ，c o m p u t i n gc a p a b i l i t y , s t o r a g ec a p a c i t ya n di n f o r m a t i o ns e r v i c ea b i l i t y p l a t f o r mo fe g r i d c o m p u t i n ga p p l i c a t i o ni ns h a n g h a ih i g he d u c a t i o n g r i d f a b b r e v i a t e dt oe p l a t f o r m ) ”i sag r i d c o m p u t i n ge n v i r o n m e n tb a s e do no g s a s p e c i f i c a t i o n t h ep l a t f o r m i n c l u d e s f o u r c o m p u t i n g r e s o u r c en o d e sa n daj o b m a n a g e m e n ts y s t e m f o u rc o m p u t i n gr e s o u r c en o d e sa r es h a n g h a iu n i v e r s i t yz i q i a n g 3 0 0 0c l u s t e rs y s t e m ，s h a n g h a is u p e rc o m p u t i n gc e n t e rs h u g u a n g4 0 0 0 ac l u s t e rs y s t e m ， e a s tc h i n au n i v e r s i t yo fs c i e n c ea n dt e c h n o l o g ys i m f a r mc l u s t e rs y s t e ma n ds h a n g h a i u n i v e r s i t yz i q i a n g2 0 0 0c l u s t e rs y s t e m p r o j e c t e p l a t f o r m w a se v a l u a t e db ya s p e c i a l i s tg r o u po fs h a n g h a ie d u c a t i o nc o m m i t t e eo nd e c 2 0 0 5a n dt h e ya c k n o w l e d g e d t h ep r o j e c tr e a c h e da na d v a n c e di n t e r n a t i o n a ll e v e l t h ea u t h o rj o i n e dt h eg r o u po n d e v e l o p p i n go ft h ej o bs c h e d u l e rs u b s y s t e mt h a ta d o p t e ds c h e d u l i n gp o l i c yb a s e do n p r i o r i t y i nt h i sp a p e r , t h ej o bs c h e d u l e rc o u l db ei m p r o v e dt or a i s et h r o u g h p u tr a t e ， r e s o u r c eu s i n ge f f i c i e n c ya n ds c h e d u l i n gc o n d i t i o na d a p t a b i l i t yi sf i g u r eo u ta n dt h r e e n e ws c h e d u l i n gp o l i c i e sa l ei m p l e m e n t e d t h e s en e ws c h e d u l i n gp o l i c i e sa r ea sf o l l o w s ： t i m e s h a r i n gj o bs c h e d u l i n g t i m e s h a r i n ga l g o r i t h mi sw i d e l yu s e di ns t a n d - a l o n e o s at i m e s h a r i n gj o bs c h e d u l i n go n “e p l a t f o r m ”i sd e s i g n e da n dr e a l i z e dt or a i s et h e s y s t e m st h r o u g h p u tr a t e d u et ot h ed i f f e r e n ta r c h i t e c t u r e ，t oi m p l e m e n tt i m e s h a r i n gj o b s c h e d u l i n go n “e - p l a t f o r m ”i sm u c hm o r ec o m p l i c a t e dt h a no ns t a n d a l o n eo s a na c r o s s m a t c h i n ga l g o r i t h mi sp r e s e n t e di nt h ep a p e rt or e a l i z et h er e s o u r c e sm a t c h i n gi nt h e “e - p l a t f o r m ” s p e c i a l l e v e lj o bs c h e d u l i n g aj o bh a sc h a n g e a b l er e s o u c er e q u i r e m e n ta n dt h e l o w e s tu s e rp r i o r i t yi sc a l l e das p e c i a l l e v e lj o b a f t e ra l lj o b st h a th a v eg o te n o u g h r e s o u r c e sh a v i n ga l l o c a t e d ，s p e c i a l - l e v e lj o b sw i l lb es c h e d u l e di no r d e rt ou s et h e f r a g e m e n tr e s o u r c e sa sm o r e a sp o s s i b l e as p e c i f i c a t i o no fs p e c i a l l e v e lj o b si sp r o p o s e d a n da ni m p r o v e dm e t h o do ni n t e r m e d i a t er e s u l ts a v i n go fs p e c i a l - l e v e lj o bi sp r e s e n t e d f i n a l l y ，as p e c i a l l e v e lj o bs c h e d u l i n gm e c h a n i s m h a sb e e nr e a l i z e d g e n e t i ca l g o r i t h mj o bs c h e d u l i n g i no r d e rt om a k et h ej o bs c h e d u l e rm o r e e f f e c t i v et od e a lw i t ht h em u c hm o r ec o m p l i c a t e ds c h e d u l i n gc o n d i t i o nb yt h ee x t e n s i o n i i 上海大学硕十学位论文 t h ep o s t g r a d u a t et h e s i so f s h a n g h a iu n i v e r s i t y o f “e - p l a t f o r m ”i nt h ef u t u r e ，w ep r o p o s e dg e n e t i ca l g o r i t h mj o bs c h e d u l i n g a c c o r d i n g t ot h ep l a t f o r m sc h a r a c t e r i s t i c ，am e t h o dh o wt od e a lw i t hu s e rp r i o r i t ya n dr e s o u r c e p r i o r i t yh a sb e e np r o p o s e d f i n a l l y , ag e n e t i ca l g o r i t h mj o bs c h e d u l i n gm e c h a n i s mh a s b e e np a r t l yr e a l i z e d k e y w o r d s ：g r i d ，s h a n g h a ih i g he d u c a t i o ng r i d ，j o bs c h e d u l i n g ，i m p r o v i n g i i i 上海大学硕士学位论文 t h ep o s t g r a d u a t et h e s i so f s h a n g h a iu n i v e r s i t y i 璺| 2 - 1 “上海高校网格e 一网格计算廊_ f j 平台”布局图一6 幽2 2 “上海高校网格e 一网格计算麻用平台”平台体系结构6 幽2 - 3 “上海高校网格e 一网格计算应刚平台”调度结构幽7 幽2 - 4 全局队列调度池模型结构图8 图3 - 1 时间片轮转算法流程图1 2 图3 - 2 优先中l t 运行时间最长的可轮转运行任务的资源匹配流程图1 9 图3 - 3 优先提交等待时间最长的可轮转等待任务的资源匹配流程图2 l 幽3 - 4 测试环境2 5 幽3 - 5 平台初始状态2 6 图3 - 6 四次任务提交后的平台状态。2 7 图3 7 第无个c m i n g 用户任务提交完成后的系统状态，2 8 图3 8 第一次时问片轮转任务调度完成厉的平台状态2 8 幽3 - 9 第一二次时问片轮转任务调度完成后的平台状态2 9 幽3 1 0 第二次时间片轮转任务调度完成后的平台状态2 9 图4 1 网格任务的远行时间图3 3 幽4 - 2 交互式用户级中间结果保存机制原理| 墨j 3 4 幽4 3 特殊级任务运行流程图3 6 幽4 - 4 特殊级任务调度监控示例图4 i 幽4 5 平台初始状态4 2 l 墨l4 - 6s p e 蹦户提交一个特殊级任务4 2 图4 7 特殊级任务调度完成后的平台状态4 3 图4 8c m i n g 用户任务提交完成后的平台状态4 3 | 墨| 4 - 9 特殊级任务调度完成后的平台状态一4 4 幽4 1 0 t r u i n g 埘户任务提交完成后的平台状态r 4 4 幽4 i lc m i n g 川户任务运行完成后的平台状态4 5 | 玺i5 - 1 遗传算法的基本过程4 7 图5 2 染色体编码图一5 0 v i 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工作。除了 文中特别加以标注和致谢的地方外，论文中不包含其他人已发表或撰写 过的研究成果。参与同一工作的其他同志对本研究所做的任何贡献均已 在论文中作了明确的说明并表示了谢意。 签名：勉呜日期丑三! 三 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定，即：学校有 权保留论文及送交论文复印件，允许论文被查阅和借阅；学校可以公布 论文的全部或部分内容。 ( 保密的论文在解密后应遵守此规定) 签名：盟翌一导师签名 日期： p 1 ，2 己 上海大学硕士学位论文 t h ep o s t g r a d u a t et h e s i so f s h a n g h a iu n i v e r s i t y 1 1 课题研究背景及意义 第一章绪论 “网格( g r i d ) ”是借鉴电力网( p o w e r g r i d ) 的概念提出来的”i ，网格的最终 目的是希望用户在使用它提供的计算能力的同时，就如同使用电力一样方便。网格 计算( g r i dc o m p u t i n g ) ”4 i 已经成为针对复杂科学计算的新型计算模式。它使用标准、 开放、通用的协议和界面，通过高速网络连接将地理上分散的、异构的各种资源按 需动念地集成为一体，构成一个单一映像的“虚拟组织( v o ) ”，充分发挥和利 用系统中各种资源的计算和服务能力，实现资源共享和协同解决复杂的科学与工程 计算问题。 上海高校网格建设是上海市教委首批启动的六个e 研究院项目之一。上海高校 网格以应用为驱动，建成兼顾专用性和通用性的信息资源平台，在占领网格技术研 发制高点的同时，为其他e 研究院提供资源支撑。“上海高校网格e 研究院”是一 个以信息网络为平台的虚拟研究机构，“上海高校网格e 一网格计算应用平台”是上 海市教委e 研究院上海高校网格的重要部分，它是由“上海高校网格e 研究院”研 发的基于网格o g s a 规范和网格核心中间件的网格计算环境，主要为从事大规模并 行计算的人员提供计算资源和结果共享的平台。 网格任务调度属于网格中间件层，它是网格任务管理系统中一个重要的功能组 成部分，调度策略的好坏将直接影响到网格资源的有效使用程度和用户任务的响应 速度。如何通过有效的任务调度束提高网格系统中资源的利用率一直以来都是网格 研究的重要课题之一。本文将通过对“上海高校网格e 一网格计算应用平台+ ( 以下简称为“e 平台”) 中的任务调度策略的分析，指出其中所存在的不足之处并 相应地提出调度优化的方案，通过使用优化后的调度策略可以使“e 平台”的调度 性能得到整体上的提高，这是一件非常重要和有意义的事情。 1 2 网格的特点及研究现状 1 2 1 网格的主要特性 虽然网格系统具有分布式的一些特征，但是作为一种新的计算基础设施，网格 具有一些重要的特点l “，这些特点对于网格构建、网格研究和网格应用有重要的影 响。一个典型的网格应该具有以下基本特征： 1 - 上海大学硕士学位论文 t h ep o s t g r a d u a t et h e s i so fs h a n g h a iu n i v e r s i t y 虚拟组织：虚拟组织是由遵循资源共享规则的一组个体、机构组成。一。如 果将互联网理解为通信网络，那么网格计算就是计算的网络：工具和协议用束协调 资源，所有资源集中在一起，彼此分享，共同解决问题。 异构性：组成网格的资源是异构的，对于计算资源，有不同的类型的计算机， 不同的计算方式，不同的计算接口，不同的系统架构；同样对于存储资源和其它资源 也面临这样的问题。因此网格要具有利用资源的异构特点进行处理的能力，同时也 要具有提供一致资源管理的能力。 资源协同：网格上的资源协同主要包括资源共享的协同与问题解决协同。资 源共享的协同以资源互连为基础，不仅包括在资源使用时不同用户因为时自j 、空问、 权限等差异引起的协商，还包括资源的组合| s i ；问题解决的协同是指虚拟组织之间 通过协作共同解决某一问题，以满足网格用户的需求。 动态性：由于网格中的资源具有自治性，因此网格资源可能动态的加入或者 退出网格，也可能出现故障导致不可用，另外资源的性能情况也可能发生较大的变 化，使得供网格使用的资源也会发生相应的变化。由于网格没有集中控制能力，i 捌 此对于这种动态性需要有一种机制来保障网格应用的运行不会遭受比较大的影响。 1 - 2 2 网格技术研究现状 在网格技术的研究上总体来说还处于探索与实践阶段，还没有大型的成熟的网 格应用。但从研究进展上来讲已经处于快速发展阶段，很多国家与研究机构都已经 投入到了网格的研究中，在计算网格、数据网格以及信息网格等方面都已经有了一 些突破和成绩。 美国对网格的研究起步较早，处于领先地位。起先，研究者主要来自一些研究 机构，后来一些大公司也参与进来。美国国家科学基金n s f 支持的t e r a g r i d p “连接 位于五个不同地方的超级计算机，达到每秒2 0 万亿次的计算能力，并能存储和处 理近l 千万亿字节的数据，其最大特色是连接网格的专用网络带宽将达到惊人的 4 0 g b p s 。美国物理网格g r i p h y n ( g r i dp h y s i c s n e t w o r k ) i ”“计划建立每秒千万亿次级 别的计算平台，用于数据密集型计算。i b m 在2 0 0 1 年8 月宣布，将投入4 0 多亿 美元进行“网格计算创新计划”，全面支持网格计算。i b m 的这一举措已经见效， 它不仅成为g l o b u s 的首席合作伙伴，还成为o g s a ( o p e ng r i ds e r v i c ea r c h i t e c t u r e ) 。1 和w s r f ( w e bs e r v i c er e s o u r c ef r a m e w o r k ) 【i 引标准的制定者之一。英国政府宣布 投资l 亿英镑，用以研发“英国国家网格”( u kn a t i o n a lg r i d ) i | ”。此外，在欧 洲还有欧洲数据网格等网格研究项目正在开展。 我国对网格技术的研究工作起步相对较晚，但发展速度很快。教育部在“十五” 2 1 1 工程公共服务体系建设中设立了“中国教育科研网格c h i n a g r i d ”重大专项，使 用网格技术将c e r n e t 上分散、异构、局部自治的巨大资源整合起来，通过有序管理 一2 - 上海大学硕士学位论文 t h ep o s t g r a d u a t et h e s i so fs h a n g h a iu n i v e r s i t y 和协同计算，发挥综合效能，实现资源的广泛、有效聚合，提供计算服务，数掘服 务和信息服务等，形成中国最大、最先进、最实用的网格系统。其节点覆盖2 1 1 建 设的1 0 0 所高等院校。 国家高性能计算环境( 亦称国家计算网格) 是国家级高性能计算和信息服务的 战略性基础设施，它将在全国范围内为各行业提供各种一体化的高性能的计算环境 和信息服务。其网格系统软件将充分发挥各网格节点的高性能计算系统和大容最数 据信息处理系统的功能，使之成为网络上的可共享的国家高性能基础设施，为各行 业用户提供具有统一管理、易于远程使用、安全的高性能计算和大容量数据处理的 环境。 2 0 0 2 年底，上海市宣布投入两个多亿建设e i n s t i t u t e ( e 研究院) ，其中上海高 校网格建设是重点。“上海高校网格e 一网格计算应用平台”是基于o g s a 架构的网 格计算环境。主要包括四个计算资源节点和一个网格任务管理平台。这四个计算资 源节点分别是：上海大学自强3 0 0 0 集群计算机系统、上海超级计算中心曙光4 0 0 0 a 集群计算机系统、华东理工大学s i m f a r m 集群计算机系统和上海大学自强2 0 0 0 集 群计算机系统。于2 0 0 5 年1 2 月通过了上海市级鉴定。专家对于“e 平台”的鉴定 结论是“该平台达到了国际先进水平”，并且获得了2 0 0 6 年度上海市科技进步二等 奖。 1 3 本文主要研究内容 本人参加了该平台所使用的基于优先级的抢先式任务调度系统的开发工作，认 为该任务调度系统在吞吐率，资源利用率和调度环境适应性三方面还可以改进。对 此在论文中提出了三个任务调度优化的方案： 提高调度程序的吞吐率：通过借鉴单机操作系统中所使用的时间片轮转算 法，提出并在“e 平台”中实现了“时间片轮转任务调度”，提高了系统的吞吐率。 提高调度程序的资源利用率：优先级抢先任务调度很容易造成“资源碎片” 的出现，对此提出“特殊级任务调度”的概念，通过利用“特殊级任务”可分割和 资源需求可变的特点来提高“e 平台”中的资源利用率。 提高调度程序对调度环境的适应性：优先级抢先任务调度无法作出全局最优 调度，在“e 平台”今后的规模得到大幅扩充后，这一不足会降低网格系统的调度 性能，对此提出使用“遗传算法任务调度”来代替优先级调度以应对更加复杂的调 度环境。 本文将主要围绕上述几个方面进行阐述。 3 上海大学硕+ 学位论文 t h ep o s t g r a d u a t et h e s i so f s h a n g h a iu n i v e r s i t y 1 4 本文的组织结构 本文其它章节的内容如下： 第二章是“e 平台”及其任务调度模型的描述。首先介绍了“e 平台”的相关情 况和平台中一直在使用的任务调度模型，然后对这调度模型进行了深入地分析和 研究，指出了它所存在的三个可改进之处并相应地提出了三个优化的方案。 第三章是时间片轮转任务调度的设计和实现。针对“e 平台”任务调度吞吐率 较低的缺陷，提出了使用时间片轮转任务调度束优化，并给出具体设计，实现和测 试。 第四章是特殊级任务调度的设计和实现。针对“e 平台”任务调度资源利用率 较低的缺陷，提出了使用特殊级任务调度来优化，并给出具体设计、实现和测试。 第五章是遗传算法任务调度的设计和实现。针对“e 平台”任务调度对调度环 境适应性较差的缺陷，提出了使用遗传算法任务调度来优化，并给出具体设计和模 拟结果。 第六章总结全文并提出对此项目进一步研究的展望。 - 4 - 上海大学硕士学位论文 t h ep o s t g r a d u a t et h e s i so f s h a n g h a iu n i v e r s i t y 第二章“e 平台”及其任务调度模型 “上海高校网格平台”是由上海大学计算机学院院长、首席研究员李三立院士 主持开发建设的新一代信息基础设施，“e 一网格计算应用平台”( 又称“密集计算网 格”，本文中简称为“e 平台”) 是该平台的一个组成部分。本章对“e 平台”和平台 中的任务调度模型将进行详细地论述和分析。本章组织如下：第2 1 节介绍“e 平台” 的基本情况，第2 2 节介绍并分析“e 平台”中的任务调度模型，第2 3 节是本章小 结。 2 1 “e 平台”平台简介 “上海高校网格e 一网格计算应用平台”( p l a t f o r n lo fe - g r i dc o m p u t i n g a p p l i c a t i o ni ns h a n g h a ih i g he d u c a t i o ng r i d ) 由上海大学“上海高校网格技术e 研究 院”负责研究开发，在经过了上海市计算机软件评测重点实验室的软件测试和上海 市情报所的软件查新工作后，于2 0 0 5 年1 2 月通过了上海市级鉴定。专家对于“e 平台”的鉴定结论是“该平台达到了国际先进水平，在平台的调度系统中的调度软 件和基于o g s a 川”的g l o b u st o o l k i t s i ”m i l 2 i 与o p c n p b s i 二4 i 连接的资源管理软件 上有刨新。” 本人从2 0 0 5 年7 月开始参与到“e 平台”的研发工作中，并陆续参加了部分的 研讨和开发，工作的重点主要集中在协助开发任务调度程序上。这一套调度程序于 2 0 0 6 年1 月获得了由中华人民共和国国家版权局颁发的软件著作权，软件编号为“软 著登字第0 4 8 2 5 0 号”，登记号为“2 0 0 6 s r 0 0 5 8 4 ”。 “e 平台”建立在o g s a 的基础上，采用了g l o b u st o o l k i t3 2 网格软件开发包。 “e 平台”的布局如图2 1 所示： 一5 上海人学硕士学位论文 t h ep o s t g r a d u a t et h e s i so f s h a n g h a iu n i v e r s i t y 图2 1 “上海高校网格e 一网格计算应用平台”布局图 图中主要包括四个计算资源节点和一个网格任务管理平台。这四个计算资源节 点分别是：上海大学自强3 0 0 0 集群计算机系统、上海超级计算中心曙光4 0 0 0 a 集 群计算机系统、华东理工大学s i m f a r m 集群计算机系统和上海大学自强2 0 0 0 集群 计算机系统。任务管理平台主要由网格门户、调度决策和信息服务器组成。 “e 平台”平台的体系结构如图2 2 所示，它主要由三层结构组成，包括用户 接口层( u s e ri n t e r f a c el a y e r ) 、网格中间件层( o d dm i d d l e w a r el a y e r ) 和网格资源层 ( g r i dr e s o u r c el a y e r ) 等。 i l l s e r i n t e r f ac e l a v e t - g d m i d d i e w a r e l a y e r g d r e s o u r o e l a y e r 图2 2 “上海高校网格e 一网格计算应用平台”平台体系结构 6 上海大学硕士学位论文 t h ep o s t g r a d u a t et h e s i so fs h a n g h a iu n i v e r s i t y 网格用户接口层：用户接口层是网格资源和服务与网格用户之间的桥梁，它 主要包括网格用户管理和用户任务提交服务。 网格中间件层：网格中间件层负责用户接口层与网格资源层之间的信息转换 和交互，是平台的核心组件集合层。网格中间件层分为两个子层：作业调度子层和 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 e a l l o c a t i o nm a n a g e r ) “j 和网格信息与资源服务( i n f oa n dr e s o u r c es e r v i c e ) 两种服务。 网格资源层：网格资源层是网格系统中任务执行的真正环境，它主要由本地 资源管理系统和具体的资源节点组成。 2 2 “e 平台”的任务调度模型 任务调度模型位于“e 平台”的网格中间件层，它采用了分级的调度结构和基 于优先级的抢先式任务调度策略。 2 2 1 任务调度结构 针对“e 平台”的体系结构，任务调度采用了分级调度结构1 2 引，如图2 3 所示。 调度结构主要由两级调度组成：即本地级任务调度( l o c a lj o bs c h e d u l e r ) 和全局级任 务调度( g l o b a lj o bs c h e d u l e 0 。 ； i全局级任务调度本地级任务调度 i；，ll 竺竺竺兰! ! t 叫竺翌竺墨! ! l ； ： i _ ii ：= = = 三：= = lj 兰! ：! 三：i ： 。一一： 医蛩霹i 垂薰匣l l 、i 一， i| j 叵垂垂，咂囹i ii ：一。 ； ! ： i 图2 - 3 “上海高校网格e 一网格计算应用平台”调度结构图 本地级任务调度主要负责接收全局级任务调度分派来的用户任务，实现该用户 任务在本地资源中的调度和分配，通常本地级任务调度都拥有自己的调度策略和资 源使用约束。“e 平台”中，四个主要的资源节点上都配置了本地集群任务管理系统， 其中在上海超级计算中心使用了l s f | 1 3j ( l o a ds h y i n gf a c i l i t y ) 集群任务管理调度 系统作为本地任务调度系统，其它；个集群使用了o p e n p b s 2 4 1 ( p o r t a b l eb a t c hs y s t e m ，7 上海大学硕士学位论文 t h ep o s t g r a d u a t et h e s i so f s h a n g h a iu n i v e r s i t y 的一种丌源系统) 集群任务管理调度系统作为本地任务调度系统。 全局级任务调度，使用中央调度器( c e n t r a ls c h e d u l e r ) ，是网格任务调度的核心 组件。它负责为用户任务进行全局范围内的宏观资源决策和分配，然后根据不同用 户任务所映射的网格资源，将其重定向分派到对应的本地级任务调度系统中：同时 根据用户任务的控制命令实现有效的监控。“e 平台”中采用了一个全局队列调度池 模型，负责实现全局级任务调度的功能。全局队列调度池模型结构如图2 - 4 所示， 主要由队列和中央调度器组成： 图2 - 4 全局队列调度池模型结构图 图2 - 4 中的各部分说明如下： 中央调度器( c e n t r a ls c h e d u l e r ) ：负责响应各类系统事件的触发和用户任务控 制信息的处理，接受用户提出的资源请求并进行相应的操作，维护当前系统有效的 网格资源信息，调度当前就绪任务，为其实现资源的映射和分配并分派到实际资 源节点上运行； 用户提交任务队列( u s e 州e w j o b q u e u e ) ：主要用于保存网格用户新提交到网格 调度器的用户任务信息。用户把任务提交给网格任务调度模块之后，这些任务按照 用户任务优先级为主序以及提交时间的先后为次主序，依次进入用户提交任务队列 并等待中央调度器的处理； 等待任务队列( j o b w a i t i n g q u e u e ) ：用于保存所有因为当前网格资源不足而 暂时不能进行调度的用户任务，该队列根据用户的优先级以及任务生成的时日j 进行 排序； 正在运行任务队歹l j ( j o b r u n n i n g q u e u e ) ：用于保存当前正在运行的所有任务信 息列表，以便实现对它们的有效监控： 任务完成队列( j o b f i n i s h e d q u e u e ) ：用于保存在网格中已经运行完成的任务 节点( j o b n o d e s ) 的信息； 资源信息队y 1 1 ( r e s l n f o q u e u e ) ：用于保存当前系统全部可用的网格资源信息， 为调度程序提供最新的资源状况。 8 上海大学硕士学位论文 t h ep o s t g r a d u a t et h e s i so f s h a n g h a iu n i v e r s i t y 2 2 2 任务调度策略 “e 平台”中目前所使用的任务调度策略是基于用户优先级和资源优先级的抢先 式任务调度策略。 ( 1 ) 调度规则。抢先式任务调度主要基于用户优先级与资源优先级的总体原则迸 行设计和实现。在“e 平台”的调度中，采用了以下规则与机制： 对于不同的用户优先级的任务之间采用高优先级任务、高优先级资源调度规 则( h i g h e 卜p r i o r i t yj o bh a sh i g h e rp r i o r i t yt ou s et h eh i g h e s t p e r f o r m a n c er e s o u r c e ) 。 对于同等用户优先级别的任务之间采用先来先服务的调度规则( f i r s t c o m e f i r s t s e r v e ，f c f s ) 。 进行任务抢先遵循最后提交时间和最低优先级别抢先原, l j ( l a t e s ts u b m i t t i m ea n dl o w e s tp r i o r i t yj o bp r e e m p t i v e ，l s t & l p j p ) 。 ( 2 ) 用户任务中间结果的存储规则。使用抢先式任务调度策略的一大前提是平台 能够保存每个正在运行的用户任务的中间运行结果。在“e 平台”中实际使用了用 户缎上的中白j 结果保存机制，即保存中间结果的工作由用户任务自行完成。由于在 高性能计算中，一般都需要比较长的计算时间，所以用户的程序中都会有保留中问 计算结果的功能，以便在系统出现故障时，可以返回到保存的中间结果，继续计算。 ( 3 ) 优先级别的设置。根据用户任务的紧迫程度和网格资源不同的计算性能，在 “e 平台”中分别设置了不同的任务优先级和资源优先级。 任务优先级：根据网格用户的不同角色和对网格资源的拥有情况，设置了三 类不i - j 等级的任务优先级，它们是： u s e r - l e v e l ：低优先级网格任务，即网格普通用户任务，即一般的网格用户所提 交的网格任务： r e s e r v e 1 e v e l ：中优先级网格任务，即网格重要用户任务，主要包括那些资源 预约用户任务和u s e r - l e v e l 任务由于调度约束而提升优先级的任务； o w n e r l e v e l ：高优先级网格任务，即资源所有者级别的网格任务，主要包括为 网格提供共享资源的资源所有者所提交的网格任务。 资源优先级：根据组成网格的资源节点的计算性能的不同，“e 平台”将网格 资源分成了不同的优先级别，给每个资源节点一个数字编号，作为资源的优先权值。 数值越小，表示其优先级也越高。在该网格平台中，上海大学的自强3 0 0 0 集群是计 算网格平台的主运算节点，因此它的优先级最高，其次是上海超算中心的曙光 4 0 0 0 a ，后面依次为华东理工的s i m f a r m 集群和上海大学自强2 0 0 0 集群。 ( 4 ) 调度算法描述。调度遵循基于“二最”| 6 i 的最佳任务抢先调度原则：即在任 务的资源决策过程中，始终保持队列中最高优先级任务运行在满足其资源需求的最 高优先级资源结点上。 在具体的实现中，用户任务提交完成后，调度程序会从u s e r n e w j o b q u e u e 中获 o 上海大学硕士学位论文 t h ep o s t g r a d u a t et h e s i so f s h a n g h a iu n i v e r s i t y 取当前提交用户任务l i e w j o b 的资源需求，根据该需求去查看“e 平台”中每一个资 源结点的资源情况，从中寻找提交n e w j o b 的可用资源，这个过程称为资源匹配。资 源匹配的步骤如下： 从具有最高资源优先级的资源结点开始到最低资源优先级的资源结点，逐一扫 描每一个资源结点的资源情况。判断当前扫描到的资源结点上， 有没有足够多的空闲资源可以满足n e w j o b 的运行要求。如果有的话表示资源 匹配成功，调度程序会将r 。c w j o b 提交至该资源结点上；没有的话进行下一多。 在当前资源结点上运行的所有任务中有没有比n e w j o b 的任务优先级低，而其 所占用的资源加上该资源结点上的空闲资源可以满足n e w i o b 的运行要求的任务。有 的话表示资源匹配成功，调度程序会暂停这个任务的运行并释放其所占用的资源供 n e w i o b 提交用；没有的话进行下一步。 在当前资源结点上运行的所有任务中有没有这样一串任务：它们中每一个的 任务优先级都比n e w i o b 的任务优先级低，而且它们所占用的资源总和加上该资源结 点上的空闲资源后可以满足n e w j o b 的运行要求，有的话表示资源匹配成功，调度程 序会暂停这一串任务的运行并释放它们的资源供n e w j o b 提交用；没有的话调度程序 的扫描移至下一个资源结点，回到重新开始。 如果在所有的资源结点上都找不到可以满足要求的资源时，对n e w j o b 的资源 匹配就视为失败。 资源匹配成功时，调度程序会向要提交n e w j o b 的资源结点上的l s f ( 或 o p e n p b s ) 发出指令，中止被选中的正在运行任务的运行，然后提交n c w j o b 至该资 源结点上。 资源匹配失败时，调度程序会将n e w j o b 放入j o b w a i t i n g q u e u e 中，等待任务 的再调度( 当发生正在