（计算机软件与理论专业论文）基于ect的优先权约束的作业调度模型及算法研究与实现.pdf

山东大学硕士学位论文 摘要 随着科学技术的发展，h 廊m e t 迅速蔓延到世界各地，成为人们沟通信息和 协同工作的有效工具。其中，通过h 鹏m e t 连接的成千上万的计算资源、存贮资 源、软件资源、信息资源等各种数字化设备共同构成了生产、传播和使用知识的 重要载体。而网格作为一种新兴的计算基础设旅，将这些物理上互连的众多资源 汇聚起来，实现了资源共享、协同工作和联合计算的功能，并为广大用户提供了 科学、工程、金融、军事等各种综合性服务。 由于h i t 唧e t 所提供的计算资源在地理上分布广泛，隶属于不同社区，而且 这些资源从硬件架构到软件部署都不尽相同，因此，在采用网格计算为广大用户 解决各种领域( 比如：高能物理生物信息学、化学分子模拟以及数值天气预报等) 中的超大规模、超级复杂的问题时，需要合理地将这些具有超级计算能力的分布 式异构资源，分配给具有不同应用需求的用户，使得用户的问题既能够及时得到 处理，同时也要确保资源使用过程中，各类资源能够平衡使用。因此需要一种可 靠、高效率的调度算法来解决资源共享中作业调度、资源分配的问题。而根据解 决问题的目的不同，调度算法有着不同的目标函数：面向资源和面向应用。例如 目前一些流行的、基于应用q o s 的网格调度管理算法就是以面向用户为主要目 的，在调度过程中考虑用户对作业管理、资源分配的影响。对用户来说，他最关 心的莫过于自己作业的执行效率( m a k es p 锄) 和使用资源的总耗费( c o s t ) 。具 体体现：要求作业必须要在特定时间内完成，或者完成作业的总费用不能超过预 算上限等。还有一些更复杂的、结合资源的别的约束条件，如：容错性能不可低 于某一下限，资源安全性能要高等。目前，网格环境中资源共享时，用户提交的 作业，大都要根据实际目标附加各式各样的需求约束。 本文提出的基于e c t 的优先权约束的作业调度模型和相关的调度算法，以 网格中的异构资源为研究背景，采用随机p e 缸网( s p n ) 技术，借鉴现有的容错 性网格作业调度模型，建模时，既考虑调度过程中用户优先权对作业调度、资源 分配的影响，同时兼顾用户提出的期望完成时间( e c t ) 和作业实际完成时间二 者的协调统一，既希望高优先权用户的作业得到高质量的服务( 作业提早完成) ， 又保证绝大多数作业都能在各自用户期望的完成时间内完成，从而协调不同用户 之间无冲突共享资源的矛盾。 山东大学硕士学位论文 本文以大规模科学与工程计算为背景，网格为基础环境，着力研究了网格过 程中作业调度、资源分配、资源共享等相关问题，分别给出了满足实际需求的作 业调度模型和相应的调度算法。前者诠释了调度过程中资源、用户以及作业之间 的相互依赖关系和约束：后者则详细描述了调度过程中作业调度、资源分配的具 体策略。最后给出与m 砸矗u n 、m a x 衄n 、x s u 所a g e 等多种经典调度算法的性能 比较。结果表明，采用本文算法调度作业，可使得绝大部分用户所提交的作业都 能在用户指定的期望完成时间内完成，尤其保证高优先权用户的作业远旱于其期 望完成时闻完成，从而保障了高优先权用户的权益，也使用户总体上满意程度比 较好，实现了多用户合理共享异构资源的目标。 关键词：网格：网格计算；作业调度；资源分配；优先权 i i 山东大学硕士学位论文 a b s t r a c t 晰曲n l ed e 、，e l o p m 即to f 鲥印c ea 1 1 dt e c h n o l o g y ，n l eb t e l m e ts p r e a dr a p 讪y a r o u n dn l ew o r l di th a sb e c o m ea ne 丘e c d v et o l o lf o ri r i f o m l a 在o nc o m m 嘶c 撕o na n d e o o p e 枷0 n 锄o n gp e o p l et h r o u g h 砌l i c h ，t l o 邺锄d so fc o m p u 恤gr e s o u r c 嚣， s t o r a g er e s o u r c ，s o f 胁r er e s o l l r c 嚣，i l l f o 皿a 舡o nr e s o u r c e s ，舔w e l l 勰o n l e fd i 西t a l e q m p m e n tt o g e t h e rc o n 碰t i l t e 丑1 em 句o rc a n j e 培f o rp 州u c 石o l l 仃锄s m 蛔m 锄d 山e 晒eo fh l o w l e 电e 玉o w e v e r ：渐dj u s tl i k ean e wc o m p 叻n gi i l 丹枷c t i l r e ，i th 勰 c o v e r e da 1 1m 舒er e s o u r c 嚣g e o 掣a p h i c a i i y c o 皿e m da 1 1 dh 罄i i n p l e r n e n t e dt l e f u n c t i o no fr e s o l | r c es h a r i n 吕c o o p e r a t i o na i l dc o m b i n e dc o m p u 血吕锄di th 嬲 p r o v i d e dv a r i o 璐o f 嘲s 谢出a l lk i n 出o fs e r v i c 器i ns c i e l l c e ，鲕e 耐n 吕f ，m 锄c e ， f 吐l i t a r ye 1 b e c a u s e 血ec o n l p 仰n gr e s o l l r c 豁p r o v i d e db ym eh 衄n e ta r e 丽d e l yd i s m b u t e d g e o 印a p l l i c a 王1 y 锄db e l o n g t od i 珏b r e n t u s e 巧，t l l es t m c t u r eo fh a r d 、v a r e ，血e d 印l o y m e n to fs o 讯哪e 越df 缸1 1 m e s a r en o t q l l i t et 1 1 es a m e ，t i l 既w h e ng f i d c 0 1 p 劬gi si | s e d 船s o l u d o n sf o rl a r g e - s c a i ep r o b l e m sr e q u i 打n gs u p e r c o m p 砸n g p o w e ri n v a r i o l l sf i e l d s ( s u c h 勰h i g h e r i 盯g yp b y s i c s ，b i o i l l f o 眦a d c s ，c h e m i c a l m o l e c l l l es i m u l 撕o n 粕dd i 百诅1w e 柚e rp r e d i c t i o n ) ，w en e e d 协a l l o c a t e 血嚣e 击s 研b m e dh 蹴r o g e n e 。u sf 器o u r c 嚣w i t hs u p e r m p u t 血gp o w e rt ou s e r so fd i 丘毫r 铋t a p p i i c a t i o i l sr e a s o n a b l yt om a l 【ep r o b l e m sd e a l t 谢t he 篮c i 衄t l y ，m e a n w i l i l ew ea l s o s h o l l i de n s u i et 量l er e s o u r c e 砸l i 撕o nr 翻诚b a l a l l c e t h e r e f o 阳w en e e dar e l i a b l e 阻de 蚯c i e n ts c l l e d u l i l l ga l g o f i 协mt 0h e l pt os o l v em ep r o b l e mf o rj o bs c h e d 讪h ga 1 1 d 懈o l l r c ea l l o c a n o n n l e r ea r ed i 丘h e n to b j e c t i v ef 血血。璐f o rs c h e d u l i n ga l g o r i t h l n s a c c o r d i i l gt od i s 血c to b j 硎v e si np r o b l e ms o l u 五o n ，s u c h 蠲r 器o l l r c e c e l l m c 锄d a p p l i c 撕o nc 曲缸c f o ri n s 锄c e ，s o m e 面ds c h e d l d i i l gm a n a g e m e n ta l g o r i t l m s b a s e d o n ( 2 0 sf o c u so n 印p l i c a l i o nd e m a i l d i n a l l dd 血n gt i l es c h e d u h n gp r o c e 辎，t l l e 如c t so fl l s e r sa r et 吐既n oc o n s i d e 咖i i lj o bs c h e d l l i i n g 锄dr e s o u r c ea 1 1 0 c 砒i o n f o rl l s e r s ，n l en l o s ti r i 】p o 栅tm i i l g st h e yc o n c e ma r e 协ee 伍c i e n c yo f j o b 既e c 埘o n 姐dm et o t a lc o s ti nr e s o u r c es h 痂g s u c h 笛j o b sm u s tb ec o m p l 鼬e d 谢t h i nd e a d l i n e ， o rt i l et o 锄c h a r g ei i lr e 1 1 r c es h 撕n gc 锄t 懿c ds o n l e 叩p e r - l i i i l i t e t c w h 砒s r n o r e ，t i l e f ea r eo t i l e rc o n s 咖i n t sf o r l | r c ed e m 强d i i l & l i k ef a u l t 协l e r 觚c e 扰d s e c 嘶够 a n dn o wm o s tj o b ss u b r n i t t e d b yl l s e r s 村e1 0 d g e dw 油d i 髓r e i l t r e q 试r 锄e n t sb a s e do na c t u a 王o b j e c t i v e si n 蕊dr e s o u r c es h a r i n g ， t 1 1 i sp a p e p r e s 朗t sp r i o n t yc o n s t r a i l l e ds c h e 山d i n gm o d e lb a s e do ne c t 笛w e n i 山东大学硕士学位论文 鹪吐l ec o n e s p o n d 抽ga i g o r i t h m t h em o d e lr e g a r d s 血eh e 咖g e n e o l l sr e s o u r c e si n g r i d 罄也em a i ne n v i r o f 埘e n t ，a d o p t ss t o c h a s t i cp 啦in e 雠o r k s ( s p n ) t e c h n o l o g y ，a n d t a k e st h ef a m t 一幻l e r 锄c e 鲥d j o bs c h e d 山i n gm o d e lf o rr e f e r e l l c e a n di i lr n o d e l i l l w e c o n s i d e rm ee 髓c 协o fp n o r i t i 舒o fd i 胁e n tu s e r s ，a sw e l la sm ec o o r d i n a n o no ft h e e ) 【p e c t e dc o m p l e t i 帆石m e 伍c da n dm ea m l a lc o r n p l “o nt l m eo f j o b s ，t og u a r a i l t e e m ej o b so fa j l 璐e r st db ec o m p i e t e d 、v i m i i le c t ( e 印e c c e dc o m p l e t i o nt i m e ) ， 器p e c i a l l y t 0e n s u r e 血e j o b so fu s e r s 、】l ，i t i l i l i g hp r i o r i 6 韶t ob ed e “t 、i ma ss o o na s p o s s i b l e ，n l a l 【i n gm e s el l s e r sg e ts e i c e so fg o o dq l i a i i 瓢i no r d e rt oc o o r d i n a t em e c o n n i c to ff e s o u r c es h 蕊gb e 啪钮d 主蠢毫r e n tu s e r s b a s e do n 吐1 eb a c k 笋。吼do fl 盯g e - s c a l es c i e i l t i f i c 越d 印g i n r i n gc o m p u d n 岛w e t a k e “d 罄b 鹊i c 朗v i r o n m 朗i ，孤df o c l l so nt h ef 嚣e a r c ho f 筋ds c h e d u l i n 舀 r e s o l l r c ea n o c 撕o n 矾dr e s o l | r c es h 丽n ge t c w bh a v e 西v as c h e d u l i n gm o d e l m e e d n gt i l ea c t u a ln e e d s 肌dt l ec o r r e s p o n d i n gs c h e d u l i n ga l g o r i m m t h ef o n l l e r i n t e r p r g t s 也er e l a t i o n s h i pb 咖e e l lr 鼯o u r c e s t a s k s 锄dl l s e r 鲴w e 王l 嬲s o m e c o n s 仃a i l l 坞锄o n gm e m i l ls c h e d u l i l l gp r o c e s s ；m el 甜e rd e s c b e s 血es c h e d u l i n g a l g 砸t h mi nd e t a i l f i n a 呈l y w ec o n l p a r eo u ra l g o 也mm t hk 妇一硼n ，m a ) 【一m i i la n d x s 喵a g ea l g o r i 血r 璐i np e r f o r n l a n c e ，i i lo u ra l g o r i 缸l i 玛c 勰w ee n s u r e 吐1 em 匆o r i t yo f m ej o b s ，i np a m c u l a w h o s eu s e f sh a ：v i n g1 1 i g hp r i o 开d e s ，t 0b ec o m p l e t e d 、撕t l i i le c t ， s o 鹪t 0m a i 【ei l s e r sg e n e r a l l ys 撕s f i e d ，t h l l sa c l l i e v m gt h eg o a lo fm u l d u s e r ss h a r i n g h e t e m g e i l e o 啪r e s o u r c e sr e a s o n a b l y 锄dv v i 廿l o u tc o n n i c t k e y w o r d s ：g r i d ；g r i dc o m p u 6 n g ；j o bs c h e d u l i n g ；r e s o u r c ea i l o c a d o n ；p r i o t y 原创性声明和关于论文使用授权的说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本 论文不包含任何其他个人或集体已经发表或撰写过的科研成果。 对本文的研究做出重要贡献的个人和集体，均已在文中以明确方 式标明。本声明的法律责任由本人承担。 论文作者签名：盔盘 日期：2 型! ：墨竺 关于学位论文使用授权的声明 本人同意学校保留或向国家有关部门或机构送交论文的印刷件 和电子版，允许论文被查阅和借阅；本人授权山东大学可以将本学位 论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩 印或其他复制手段保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：叠查垫导师签名：篁至日期：! 竺! ：! 丝 山东大学硕士学位论文 第1 章绪论 本章详细介绍了课题背景和研究目标，重点阐述了本文所要研究和解决的工 作，最后给出了全文的组织结构。 1 1 研究背景 随着社会的不断发展，科学技术更以日新月异的速度向前推进，近年来，高 性能计算在诸如预测模型的构造和模拟、工程设计和自动化、能源勘探、医学、 军事以及基础研究等领域都起着重要作用。一些推动人类文明的挑战，如外科手 术的磁共振成像和药物设计、大气模型的建立和中长期天气预报、卫星遥感数据 及地震数据的分析等，如果没有速度极快、内存容量极大高性能计算机，就很难 成为现实。高性能计算方法的基本原理就是将问题分为若干部分，然后通过网络 相连的每台计算机资源( 称为节点) ，同时参与问题的解决，从而显著缩短了解 决整个问题所需的计算时间。因此，如何能够以一种有效的方式把互联网上分布 于不同地理位置的、异构资源通过高速互联网络连接起来，为外界提供大规模的， 无限延展的计算能力是我们研究工作的重点。而网格技术恰恰可以满足这种需 求。它作为二- 种新兴技术，汇集分散在不同地理位置的各种资源( 计算资源、存 储资源、数据资源、信息资源、软件资源、通信资源、知识资源等) ，屏蔽资源 的异构性以及资源设备之间的复杂关联，为外界用户提供一个方便、透明的资源 使用平台。通过采用网格的关键技术，我们可以实现多用户无冲突、安全、灵活 地共享各种异构、动态资源的功能，这在科学技术的发展史上无疑是一个革命性 的变化。 目前有很多国家和机构积极参与了网格的研究与开发工作。例如：美国国家 航空和宇宙航行局( n a s a ) 的i p g ( i n f o m a t i o np o w e r 网格) 项目，目的是让 人们使用计算资源和信息资源就像使用电力网提供的电力资源样方便快捷。欧 洲共同体的e u r o 网格和d a t a 网格，主要用于包括高能物理、生物计算、气候 模拟等多个领域的应用。我国8 6 3 计划支持的“中国网格( c h i n a g r i d ) ”建设， “上海教育科研网格”，“仿真网格”( 由航天二院和清华大学共同开展) ，“织女 星网格”( 由中科院计算所领衔开发) 。 山东大学硕士学位论文 计算网格的出现使得隶属不同用户、跨越多个地理位置的分布式异构资源的 共享成为可能。为此，网格的体系架构中每一层应该部署不同的协议来支持不同 的服务：安全、统一访问、资源管理、任务调度、资源监控等。其中，资源管理、 任务调度是现在研究的热点也是难点，由于网格环境的灵活多变性，为用户合理 分配资源，保证资源的有效利用，满足用户共享资源的需求，则要依靠作业调度 过程中所采取的调度算法，它决定着资源的使用效率和用户的满意程度。 本论文研究课题来源于山东省重大项目：科学与工程计算应用网格。 1 2 研究目标 网格环境中分布着各种异构分布式计算资源，它们来源广泛，可为外界提供 多种领域的服务( 比如：高能物理生物信息学、化学分子模拟以及数值天气预报 等) 。同时，共享资源的用户也是千变万化，不同类别的用户对资源的需求也不 尽相同( 例如：有的类别的用户希望自己的作业能够尽早得到处理) 。因此在多 用户共享资源的过程中，如果不采取相应的调度策略，不同类别用户之间很可能 会产生冲突，争夺资源的使用权、优先权，造成资源利用率失衡，从而导致资源 浪费，也使得用户对网格资源共享的满意程度大打折扣。 本文旨在研究一种异构环境下，基于e c t 的用户优先权约束的作业调度模型 和相应的调度算法，必须适用于目前我们的实际环境，可以解决为网格资源下不 同类别的用户无冲突共享资源的问题。e c t ( 期望完成时间，由用户指定) ，作业 要尽量保证在该期望完成时间之内完成，体现了用户对作业的限制条件；用户优 先权约束，是指在调度过程中，还要充分考虑不同的用户对资源分配和作业执行 产生的影响，通过为不同级别的用户分配不同的优先级，保证高优先级用户的作 业可以优先执行，最大限度地保障高优先权用户的权益( 在本文算法中，要将用 户优先权和期望完成时间这两方面因素结合考虑) ，平衡系统利用率，使得绝大 多数用户满意程度高，实现网格环境中合理共享资源的目标。 1 3 主要工作 主要的研究工作如下所示： ( 1 ) 基于异构环境下，实现多用户无冲突共享网格资源的目标，本文提出 山东大学硕士学位论文 了一种基于e c t 的优先权约束的作业调度模型。建模过程中，创建了系统模型、 用户模型、任务模型，并详细描述了它们之间的相互依赖和约束关系，最后本文 参考了著名的基于随机p e t r i 网s p n 技术和容错性网格作业调度模型，结合上述 已有的三种基本模型，根据实际需求，以用户优先权和期望完成时间( e c t ) 为 主要影响因素，建立满足应用需要的作业调度模型。该模型充分考虑了调度过程 中优先权和e c t 对作业提交、处理、执行的影响，对调度过程进行建模求解，并 加以性能分析。 ( 2 ) 基于创建好的调度模型，本文进而提出了基于e c t 的优先权约束的作 业调度算法，该算法属于静态调度算法，主要侧重于面向应用( 用户) 的目标函 数。算法解决的主要问题：调度过程中，保证绝大多数作业都能在期望完成时间 ( e c t ) 之内完成，尤其要保障高优先权用户的作业优先处理，使得用户满意程 度高。 ( 4 ) 最后把本文调度算法与其它三种经典的静态启发式作业调度算法进行 性能比较，根据设定的目标函数( 保证用户的满意程度) ，评估它们的适用性以 及执行效率。通过多次试验比较，发现本文的调度算法重点考察了用户对作业调 度的影响，在不过多牺牲系统效率、平衡资源利用率的前提下，更能满足实际网 格环境的需求，充分保证了用户所提交作业基本都能在期望完成时间内完成，而 且高优先权用户的作业可远远先于其期望完成时间完成，用户的满意程度最好。 1 4 论文的组织结构 全文分为六章。 第一章为绪论，主要介绍论文的课题背景和研究目标，主要工作和组织结构。 第二章介绍相关的基础知识。其中包括网格知识的简要介绍：网格调度的详 细概述；网格调度算法的定义、分类，介绍各种经典静态调度算法和评价算法的 重要依据：目标函数；最后给出甘特图的概念，它是后面模拟、评测调度算法的 重要工具。 第三章介绍了基于e c t 的优先权约束的作业调度模型的设计。 第四章详细给出了基于e c t 的优先权约束的作业调度算法描述。 第五章介绍了本文算法与其它静态调度算法的性能比较和评估。 山东大学硕士学位论文 第六章总结全文，并提出下一步工作。 山东大学硕士学位论文 第2 章相关基础知识 本章首先简单介绍了网格的基本知识；然后给出了调度在网格环境中的重要 地位；最后介绍了调度算法的重要性，并给出一些经典的调度算法以及评测算法 的目标函数。 2 1 网格概述 什么是网格( g r i d ) o ”? 网格就是一个集成的计算与资源环境，或者说 个计算资源池，网格能够充分吸纳各种计算资源，并能将它们转化成种随处可 得的、可靠的、标准的同时还有经济的计算能力。除了各种类型的计算机，这里 的计算资源还包括网络通信能力、数据资料、仪器设备、甚至是人等各种相关资 源。其中，基于网格问题的求解就是网格计算。 网格是借鉴电力网“1 ( e l e c t r i cp o w e rg r i d ) 的概念提出来的，网格的最终 目的，是希望用户在使用时，如同使用电力一样方便。总而言之，网格是一个硬 件和软件的基础设施，此基础设施提供对高端计算能力可靠的、一致的、普遍的 和不昂贵访问。1 ，它通过标注开放的通用协议和借口来协调分布式资源已提供最 好的服务质量1 “。网格作为一种新兴的重要的基础设施，和其他系统相比，有 以下几个重要特点： 分布与共享 分布是网格一个最重要特点。网格的分布性主要是指网格资源是分布的，组 成网格计算能力不同的计算机、各种类型的数据库以及其他各种设备与资源，都 是分布于地理位置各不相同的多个地方，而不是集中在起。分布的网格一般涉 及的资源类型复杂，规模较大，跨越的地理范围较广。网格资源虽然是分布的， 但他们却是可以共享的，即网格上的任何资源都可以提供给任何使用者，共享是 网格的目的，没有共享便没有网格。解决分布式资源的共享问题是网格的核心内 容， 动态与多样性 网格是动态的，允许所有资源自由加入和离开计算环境，而且由于通信带宽 是共享的，因此通信延迟显得更为动态而不确定；同时，网格又是多样的，而且 山东大学硕士学位论文 在硬件和软件两个层次上都存在着异构性，导致了资源之间通信和互操作问题。 自治与管理的多重性 网格上的资源首先是属于某一个组织或个人的，因此网格资源的拥有者对该 资源具有最高级别的管理权限，网格应该允许资源拥有者对他的资源有自主的管 理能力，这就是网格的自治性。但是网格资源也必须接受网格的统一管理，否则 不同的资源就无法建立相互之间的联系，无法实现共享和互操作，无法作为一个 整体为更多的用户提供方便的服务。 2 2 网格调度概述 2 2 1 网格调度的含义 由上所述，计算网格是硬件和软件基础设施的统一体，它可以为外界提供可 靠、一致、持久、低廉的高端计算能力。1 。网格是个共享环境，部署持久、基 于一定标准的服务设旌，并且支持分布广泛、不同的社区来创建、共享资源。这 些共享资源通常是指：一切由i n t e r n e t 相连的计算机、存储空间、设备设施、 软件应用以及数据等。它们隶属于各个不同的管理组织，基于相应的策略被使用。 例如：这些资源都提供什么服务，允许哪些用户使用，以及在什么样的条件下才 可被使用等 6 。因此，如何在动态多变、复杂的多虚拟组织环境下，解决协调 资源的共享问题是网格领域的重点，从而引发出调度问题 7 的讨论与研究。 简单说，网格调度可以看作一个软件框架 8 】，而位于框架之上、具有调度 功能的调度系统则充当着资源和外界用户之间的接口。它承上启下，负责对地理 上广泛分布的、自主的异构资源进行管理，动态地根据这些资源的可用性、所提 供计算的能力、性能效率、使用成本以及用户提出的质量服务的需求 9 ，集中 所有分布式资源，以供外界任务选择、匹配、共享。下面简要介绍网格调度的特 点。 2 2 2 两格调度的特征 和以往传统的并行或分布式系统不同，网格环境中不断有资源加入、退出， 这种自主灵活性造成网格环境的复杂、多变和不稳定；而且资源的归属性不一致 山东大学硕士学位论文 也导致了资源在共享过程中的诸多不便。然而正由于这些困难，也给我们深入研 究网格调度带来了新的挑战。我们总结网格调度的主要特点： 资源异构：网格特点的重要体现 节点自治：资源属于不同社区，因此资源使用者具有使用资源的最高控 制权限，这加重网格调度的复杂性 资源非专用：也是网格特点的一个重要体现，即资源共享 应用多样性：多样化需求导致多样化服务 动态性：网格特点复杂性的突出表现，资源的动态变化造成网格环境的 不稳定性，更导致调度工作的困难 网格环境中，要想通过调度过程，以达到多用户之间能够合理使用这些网格 资源的目的，我们必须充分理解上述特点。在具体调度过程中，必要时还需要对 某些特点加以简化( 如：暂且忽略动态因素) 以降低复杂性，实现主要的、满足 实际需求的调度功能。下面是网格调度的主要架构模型和功能组件。 2 2 3 网格调度模型 网格调度模型可由以下四部分组成： 应用模型：描述了将要被调度处理的应用( 作业或任务) 。任务：指的 是调度过程中分配给单一资源的原子单元；作业( 任务或应用) ：由一 系列原子任务组成，通常在一组资源上执行。作业可以是递归的结构， 即作业会被分解成子作业或一系列任务，而子作业又可以被分成原子任 务。 资源模型：通常用于执行任务操作。例如具有运算能力的处理机、用 来数据存储的设备以及用于数据转移的网络连接。 性能模型：指的是调度过程中需要对潜在的性能进行预测，该性能指标 通常指应用需求和资源状态。 调度策略：根据何种标准为应用分配最合适的资源，同时决定一系列应 用的执行序列。 上面的模型给出了网格调度框架的具体构造，囊括了网格调度涉及的所有因 素。但是在。“中，z h u 提出了一个更为通用的网格调度框架，该框架相对来说 山东大学硕士学位论文 更简洁明了。正如他所说：我们可以把调度过程划分成三个部分“。： 资源发现和过滤 根据一定的调度策略选择资源并对作业进行调度 分配资源并提交作业 总的来说，调度实现了两部分功能：1 ) o r d e r i n g ，2 ) m a p p i n g 。o r d e r i n g 指的是为同时提交的一系列作业确定最终的执行序列( 当调度过程需要考虑优先 权和完成期限时，o r d e r i n g 显得尤其重要) ：m a p p i n g 指得是为每个作业挑选分 配最合适的资源，在每次m a p p i n g 中，需要预测潜在的性能保证调度最优。这里 的性能指标主要是指；系统吞吐量最大、资源利用率最高1 、平均周转时间最 小以及兼顾必要的经济因素“”。图2 。2 1 是通用网格调度框架。从中，我们可 以看出在网格调度流程中关键组件的功能作用。 m n d n 2 2 4 调度功能组件 图2 2 3 通用的网格调度框架 g s ( g r i ds c h e d u l e r ) ：网格调度器。接受网格用户所提交的作业，然 后从网格信息服务模块中获取这些用户的对资源的需求，根据定的目 标函数和可预测的资源性能，产生最终的应用一资源映射对。网格调度 器，不能直接对资源进行控制，但是它可以通过一些代理“，或者和应 用联系更紧密的应用层调度机制“8 。”1 对资源进行管理。这些代理或应用 山东大学硕士学位论文 层的调度机制是不能和资源位于同一社区层次上的，相反，它们单独位 于网格应用层，而且由于资源的性能和规模不同，它们的架构也多有不 同：中心架构、阶层架构、离散架构“”。目前，我们把这些网格层次上 的代理称作元调度器“”。 g i s ：网格信息服务模块。收集和预测相应的资源信息。例如：。c p u 性能、 内存大小、网络带宽、软件的可用性以及一段时间内总的资源性能。 g l o b u s 中的如s 就是g i s 的一个例子。除了资源信息之外，用户需求在 调度过程中也必不可少，例如：指令数量，内存需求以及作业中子任务 之间的依赖性和通信量等。根据资源状态和应用需求这两方面的影响， 我们可以生成一个性能模型，通过该模型来调度作业，可以保证调度 性能最优。 l m ( l a u n c h i n ga n d n i t o r i n g ) ：执行和监控模块。它根据调度结果， 将作业提交到已经选好的资源上，导入输入数据和执行程序，同时监控 作业的执行状态。g l o b u s 中的g r 埘是的一个很好的例子1 。 l r m ( l o c a lr e s o u r c em a n a g e r ) ：局部的资源管理器。主要负责资源域 内的作业调度。它所处理的作业不仅来自资源域内的用户，也来自资源 域以外的其它网格用户，l r m 还要把作业执行的状态信息报告给g i s 。 在同一个资源域中，多个局部资源管理器需要根据局部统一的资源管理 策略来使用。例如p b s “1 、c o n d o r 等都可以看作是一种l r m 。 由上我们已经了解网格调度是网格中最重要的组成部分，那么，要实现网格 调度的具体功能绝非易事。调度，简而化之，就是根据相应的策略管理资源，处 理提交作业，以实现多用户资源共享的目的。因此，要深入研究网格调度，我们 就需要根据实际需求，设计合理、可用的网格调度模型，该模型可以抽象描述网 格环境中的调度过程，通过它，我们可以模拟实现作业提交、资源共享的流程。 有了调度模型，我们才可以制定出相应的调度算法( 策略) ，从而实现调度功能， 这就是调度的完整过程。因此调度算法也是调度中必不可少的部分，没有算法， 调度作用无法体现，下面我们将给出调度算法的详细介绍。 山东大学硕士学位论文 2 3 网格调度算法 2 3 1 网格调度算法的含义 调度算法作为一个基本问题，长期以来一直在传统分布式或并行系统上被深 入研究，例如：对称多处理机系统( s 肝) 、大规模并行处理机( 船p ) 、集群工作站 ( c o w ) 。而如今，这些传统的调度算法在网格调度中效果却很差。这是由于对传 统的系统来说：所有的资源都隶属于同一社区，调度系统控制管理所有的资源， 资源池一成不变，需要导入的数据常驻在固定的场所等。然而这一切都不满足网 格调度的特点。 在网格调度环境中，资源通常是自治的，属于不同社区，服从于当前局部调 度策略。而网格调度系统想采用单一的策略来管理、控制所有社区的资源，显然 是比较困难的。自治性导致了局部资源管理和远程访问控制之间的分歧，例如： 局部调度系统可能会为本地提交的作业设置高优先权，必要时采取资源预留方案 以保证本地作业可以优先享用资源。因此，网格调度系统必须要协调不同社区的 约束，根据用户、资源各自的需求，制定合理有效的调度策略( 算法) 。例如， 现在流行的计算经济网格模型中，网格系统、网格资源调度、资源拥有者和用户 等等都有新的需求，我们根据资源拥有者和终端用户需要：描述他们的要求、估 价和目标函数( 价值表达式) 的方法；把它们转化为资源分配( 价值传送) 的调 度策略；增强对不同服务、运行时期可能出现的变化和动态适应的选择与分配机 制。文献提出了完整的适用于网格环境的分布式计算市场模型。 一个有效的网格调度算法必须能够随时对资源状态做出准确的预测，动态分 配资源。但是由于网格环境中资源可自由加入、退出，导致网格调度的灵活多变 以及不稳定性；而且调度过程中还需协调各个衽区的自治性，缓解社区用户之间 抢夺资源之间的矛盾，保证用户都能够满意地共享资源，这些因素都影响着调度 算法的有效性和可用性。目前，国内也有很多基于应用的网格调度算法的研究。 例如：。1 中提出了当系统负载过大，难以保障应用的服务质量( q o s ) 时所采 用的q o s 获益的资源规划算法；“7 1 针对网格计算中的多q 0 s 约束网格作业调度 问题，以独立作业为研究对象，将其规约为多目标组合最优化问题，通过深入剖 析多目标最优化理论及其演化算法，结合网格作业调度自然特征，提出了一种解 山东大学硕士学位论文 决多q o s 约束网格作业调度问题的多目标演化算法，该算法求解多个q 0 s 维度效 用函数指标的非劣解集，尝试解决多管理域间网格用户、资源管理者等网格实体 的多目标协同问题；则从应用需求的性能出发，提出应用敏感的w e b 服务请 求调度策略，使用应用获益来评估服务期为应用提供的性能保障效果，按照应用 效益最大化为目标来分配资源；还有基于优先权的端到端的实时任务调度算法卿 等。这些算法大都根据实际需求，建立了完善、侧重用户某一特定需求的调度模 型，并在此模型的基础上提出合理的调度算法，解决了领域中的相关问题，并且 很好地协助我们深入研究网格调度算法。 2 3 2 网格调度算法的类别 众所周知，调度算法本身就是一个n p c 问题。”3 ，尤其在网格这种特殊的环 境中，更显得富有挑战性。而目前，网格调度算法从功能性质上可以主要划分以 下两大类： 局部调度算法和全局调度算法 局部调度策略指的是如何对单一c p u 进行分配与执行：全局调度策略通过采 用系统信息将任务分配给多个处理器以优化系统方面的性能。很显然网格调度属 于全局调度。 静态调度算法和动态调度算法 静态调度中，所有的资源和任务在本次调度中全部可用。而且在每次调度过 程中，每个任务只可进行一次资源分配。因此，每次执行任务之前i 需要对每个 任务的计算成本作一个严格的估计。静态调度的最大的优点：从应用角度来看易 于实现、系统开销小和过载时更好的可预测性等，在单处理器实时嵌入式系统中 广泛应用“】。 但是基于静态信息的成本估算并非完全符合动态变化的环境。即如果被选中 的一系列资源节点中某一节点执行失败，那么整组的节点可能会由于网络系统故 障而被隔绝。而且资源长时间处于高负载，会使作业的反应时间比预期更长。为 缓解这一问题，一些辅助机制，例如重调度( r e s c h e d u l i n g ) 被引入。1 ，它以牺 牲任务迁移耗费为代价，使得静态调度与动态调度之间的差距变小。关于静 态调度算法下面会详细介绍。 动态调度：当作业的耗费估计变得困难，或者作业不断地动态在线提交， 山东大学硕士学位论文 申请资源。常见的动态调度的例子：c o n d o r 、l e g i o n “等。 动态任务调度两大主要功能：系统状态估计( 不是静态调度中的成本佶算) 和决策。系统状态信息主要来自于网格，基于预先估计，按照一定方式把任务分 配给所选资源。由于对一个任务来说，它的耗费估计不可知，因此，最常用的估 计方法就是以保证资源的高利用率和负载平衡为准则。 负载平衡在动态调度中得以很好的实现，这是由于我们无需在任务执行之前 确定任务的运行状态和行为。尤其当评测系统运行效率的主要目标是最大化资源 利用率，而不是降低平均周转时间。如果一个资源同时被指定分配给多个作业， 这就需要采取一种平衡策略来决定是否要把该资源分配给某个作业，或者将正在 使用该资源的某个作业迁移到别的资源上去继续执行。 关于动态调度算法有很多种，例如“，它们都考虑了资源预留。它作为 获得资源性能率的一种手段，在网格计算中广泛运用。 上面介绍了网格调度算法的两个大类别，各有千秋。我们还可获知，调度算 法根据采用不同的应用策略还可看作下述4 类：无条件的先来先服务策略 ( f c f s ) ，平衡约束的相关技术手段，成本约束的相关技术手段，动态调度与静 态调度相结合的方法。 下面我们具体介绍这四种方法： 无条件的先来先服务策略( f c f s ) 在该方法中，从所有可提供服务的资源中，具有最小( 最短) 等待执行的作 业队列的资源将优先使用，并且，所有提交的作业根据其提交顺序被执行。该方 法最大的优点：简单，但是实验表明：它的效果远远低于最优。 平衡约束的相关技术手段 该方法试图通过周期性的转移等待队列中的提交作业以达到平衡资源之间的 利用率。但是，在大型系统中，例如网格中，作业转移中的通信延迟问题是一个 相当大的损耗。因此需要我们采取一些适应性的局部启发式调度算法以应用于网 格环境。例如：所有的作业分配给各个资源，不考虑全局平衡，只考虑局部中的 平衡效应( 局域网中的通信延迟相对会小一些) 该方法有很多的优点：1 ) 所有 作业同时分配给网格中所有资源，并且开始执行；2 ) 平衡过程式分布的而且可 以计算的：3 ) 平衡过程的通信延迟可以降低，由于任务迁移发生在局域网中。 成本约束的相关技术手段 山东大学硕士学位论文 调度过程中，平衡约束的一个改进就是成本约束。该方法不仅考虑了资源之 间的平衡，也考虑了任务之间相互通信的成本问题。我们并不是要周期性的迁移 作业，作业在迁移之前将会被检查。如果作业迁移的成本比降低作业执行时间还 要大，该作业就不会被迁移。 动态调度和静态调度相结合的混合调度方法 该方法集成了静态调度和动态调度的特点，它采用了静态调度的所有优点， 同时也能获取用户和资源的不确定因素，比如说，有些作业具有不确定的行为状 态( 完成时间期限提前对资源性能要求改变) 。静态调度则适用于稳定不变的执 行过程；在执行过程中，当需要统计分析，得出每个作业的运算估计，并降低运 行延迟时，则需要动态调度。 为了进一步加深对调度算法的理解，我们把静态和动态调度算法继续细化为 以下分类： 最优算法和次优算法 我们根据资源和作业的状态信息，根据一定的标准，找出一种最优的资源一 作业匹配解。例如：最小化m a k es p a i l ，最大化资源利用率等等。但是由于调度 本身就是n p c 问题，因此网格环境中需要采取合理的假设条件来求得一定限制范 围内的最优解。因此目前的研究主要致力于找寻次优解，而次优解又可以被划分 为如下两个类别： 近似算法和启发式算法 近似算法采用正规的计算模型，它并不从所有的解空间中寻找一个最优解， 而是找一个“足够好”的解，我们采用相应的标准来评价一个解的优劣，该标准 必须能够降