（计算机应用技术专业论文）p2p环境下多目标任务调度策略研究.pdf

大连理- 下大学硕十学位论文 摘要 随着p 2 p 计算模式的兴起、网络带宽的增加和i n t e r n e t 计算能力的迅速增强，如何 充分利用这些资源，在动态的p 2 p 网络环境中构建高可扩展、高可靠、高性能的分布式 计算系统，是近年来研究的热点之一。任务调度是p 2 p 计算中的一项关键技术，直接影 响到整个系统的计算性能。任务调度是指根据一定的调度策略，把一组可并行处理的任 务按规定的时序分配到系统的多个处理机结点上，以期获得较好的系统执行性能。 为了达到任务调度负载均衡和更有效的利用p 2 p 网络资源的目的，提出了基于相似 度的任务调度算法。通过计算现行任务与历史任务之间的相似度，来确定能够直接调度 的结点；通过计算任务需求资源与结点可提供资源的相似度并利用传输时间因素对其进 行修正，来获取满足任务需求的有序结点集合。实验结果表明，基于相似度的任务调度 算法能够有效地减少任务调度过程中的“颠簸”现象，更好达到负载均衡和有效利用资 源的目的。 p 2 p 环境的特点决定了其任务调度是受多个因素制约的。通过考虑任务执行时间、 结点间的通信时间和任务调度费用等因素，提出了多目标约束的并行任务调度策略。首 先提出了多目标任务调度的数学模型，利用任务需求与结点性能之间的关系来定义各目 标的需求关系矩阵，然后利用隶属度函数将各个关系矩阵转化为模糊矩阵，并根据每个 目标对最终目标的不同影响来确定各目标在最终决策中所占的比率，从而将多目标转化 为单目标任务调度模型。实验结果表明，基于多目标约束的任务调度模型较传统的方法 更能优化任务调度的性能。 为了更好满足不同用户对服务质量的要求，提出了任务划分调度模型。首先将任务 分为实时任务与非实时任务，然后根据任务调度的特点以及所存在的任务类型，利用排 队理论分别描述了两种不同的任务调度模型。实验分析了引入本章任务调度模型后对不 同算法的影响，表明了进行任务划分和引入排队机制的有效性。 关键词：p 2 p 网络；任务调度；相似度；模糊矩阵；排队理论 大连理工大学硕士学位论文 t h er e s e a r c ho nm u l t i - o b j e c t i v et a s ks c h e d u l i n gs t r a t e g y i np e e r t o p e e re n v i r o n m e n t a b s t r a c t w i t hp e e r - t o - p e e rc o m p u t i n gm o d e lr i s i n g ，t h es u b s t a n t i a li n c r e a s ei nn e t w o r kb a n d w i d t h a n di n t e r n e tc o m p u t i n gp o w e ri n c r e a s i n gr a p i d l y ，h o wt om a k ef u l lu s eo ft h e s en e t w o r k r e s o u r c e s ，t oc o n s t r u c tal a r g e - s c a l e ，h i g h l ys c a l a b l e ，h i g h l yr e l i a b l e ，h i g h p e r f o r m a n c e d i s t r i b u t e dc o m p u t i n gs y s t e mi nad y n a m i cp e e r t o - p e e rn e t w o r ke n v i r o n m e n t ，w h i c hr e s e a r c h i sah o to n ei nr e c e n ty e a r s t a s ks c h e d u l i n gi sak e yt e c h n o l o g yi np 2 pc o m p u t i n g ，i ti sa d i r e c ti m p a c to nt h ec o m p u t i n gp e r f o r m a n c eo ft h ee n t i r es y s t e m t a s ks c h e d u l i n gp r o b l e mi s t h a ta s s i g n i n gag r o u po fp a r a l l e lp r o c e s s i n gt a s k st on o d e si na c c o r d a n c ew i t ht h et i m i n g r e g u l a t i o n sb yc e r t a i ns c h e d u l i n gs t r a t e g y ，w i t hav i e wt oo b t a i n i n gab e t t e rs y s t e m p e r f o r m a n c e at a s ks c h e d u l i n ga l g o r i t h mb a s e do ns i m i l a r i t yi sp r o p o s e dt oa c h i e v el o a db a l a n c i n g a n dm a k eg o o du s eo ft h en e t w o r kr e s o u r c e s t od e t e r m i n et h en o d e st ob es c h e d u l e d ，t h e w a yo fc o m p u t i n gs i m i l a r i t yb e t w e e nt h ec u r r e n tt a s ka n dt h ep a s tt a s ki sa d o p t e d t og e tt h e n o d e ss e t ，t h em e a s u r eo fc o m p u t i n gt h es i m i l a r i t yb e t w e e nt h es o u r c er e q u i r e m e n t so ft a s k s a n dt h es o u r c e st h a tn o d e ss u p p l yi st a k e n o nt h i sb a s i s ，t h ea l g o r i t h mo ft a s ks c h e d u l i n gi s g i v e n e x p e r i m e n tr e s u l t ss h o wt h a tt h ep r o p o s e da l g o r i t h mc a ne f f i c i e n t l yr e d u c et h e “b u m p ”p h e n o m e n o n ，a c h i e v el o a db a l a n c i n ga n dm a k eu s e o ft h en e t w o r kr e s o u r c e s t h ef e a t u r e so ft h ep 2 pn e t w o r km a k ei t st a s ks c h e d u l i n gp e r f o r m a n c ec o n s t r a i nb y m u l t i f a c t o r c o n s i d e r i n ge x e c u t i o nt i m e ，c o m m u n i c a t i o n t i m e a m o n gn o d e sa n dt a s k s c h e d u l i n gc o s t s ，ap a r a l l e l t a s ks c h e d u l i n ga l g o r i t h mw i t hm u l t i o b j e c t i v ec o n s t r a i n t si s p r e s e n t e d t h em a t h e m a t i c a lm o d e lo ft h em u l t i o b j e c t i v et a s ks c h e d u l i n gi sf i r s tp r o p o s e d w h i c hd e f i n e st h er e q u i r e m e n tr e l a t i o nm a t r i xf o re a c ho b je c t i v eb yu s i n gt h er e l a t i o n s b e t w e e nt h et a s kr e q u i r e m e n ta n dt h en o d e sp e r f o r m a n c e t h e na l lt h er e l a t i o nm a t r i c e sa r e t r a n s f o r m e di n t of u z z ym a t r i xb yu s i n gm e m b e r s h i pf u n c t i o n s t h ep r o p o r t i o n sd e t e r m i n e db y t h e d i f f e r e n te f f e c to nt h ef i n a ld e c i s i o no f e a c ho b j e c t i v ea r ea p p l i e dt oc o n v e r t m u l t i o b j e c t i v et a s ks c h e d u l i n gp r o b l e mt ot h a to ft h es i n g l eo n e ，a n dm e a n w h i l et h es o l u t i o n o fb e s td i s t r i b u t i o no nnt a s k sa n dmn o d e si sc a r r i e do u tb ya d o p t i n gh u n g a r ya l g o r i t h m e x p e r i m e n t a lr e s u l t ss h o wt h a tt h et a s ks c h e d u l i n ga l g o r i t h mw i t l lm u l t i - o b j e c t i v ec o n s t r a i n t s h a sb e t t e rp e r f o r m a n c e st h a nt h et r a d i t i o n a lm e t h o d s t h em o d e lo nt a s ks c h e d u l i n gd i v i s i o ni sp r o p o s e dt os a t i s f yu s e r s q u l i t ys e r v i c en e e d f i r s t l y ，t h et a s k sa r ed i v i d e di n t or e a l - t i m et a s k sa n dn o n r e a lt i m et a s k sa c c o r d i n gt ot h e i i i p 2 p 环境下多目标任务调度策略研究 s t a t u so ft a s kr e q u i r e m e n t s t h e nt w od i f f e r e n tt a s ks c h e d u l i n gm o d e l sb a s e do nt h e s c h e d u l i n gc h a r a c t e r i s t i c sa n de x i s t i n gt a s kt y p e sa r ed e p i c t e db yt a k i n ga d v a n t a g eo fq u e u i n g t h e o r y ，a n da l s ot h er u l e so fq u e u i n ga n dt a s ks c h e d u l i n ga r eg i v e n t h ee x p e r i m e n t sa r eu s e d t oa n a l y z et h ee f f e c to ft h et a s ks c h e d u l i n gm o d e lp r o p o s e dh e r ei nt h ee x i s t i n ga l g o r i t h m s ， a n dw h i c hs h o wt h ev a l i d i t yo fc l a s s i f y i n gt a s k sa n di m p o r t i n gq u e u i n gt h e o r yi nt h et a s k s c h e d u l i n g k e yw o r d s ：p 2 pn e t w o r k ；t a s ks c h e d u l i n g ；s i m i l a r i t y ；f u z z yc l u s t e r i n g ；q u e u i n gt h e o r y i v 大连理工大学学位论文独创性声明 作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究 工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方外， 本论文不包含其他个人或集体已经发表的研究成果，也不包含其他已申请 学位或其他用途使用过的成果。与我一同工作的同志对本研究所做的贡献 均已在论文中做了明确的说明并表示了谢意。 若有不实之处，本人愿意承担相关法律责任。 学位论文题目：! 里巫埴王垒旦拯堡垒迥廑筮喳盟壅 作者签名： 毽亟熊 日期： 2 鲤墨年坚月三l 日 人迮理i ：人学硕十研究生学位论文 大连理工大学学位论文版权使用授权书 本人完全了解学校有关学位论文知识产权的规定，在校攻读学位期间 论文工作的知识产权属于大连理工大学，允许论文被查阅和借阅。学校有 权保留论文并向国家有关部门或机构送交论文的复印件和电子版，可以将 本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印、或扫描等复制手段保存和汇编本学位论文。 学位论文题目：一里2 里巫埴王多旦盘堡釜迥廑筮坠盈究 作者签名： 丞! 毖照 日期：盈! 墨年坠月量l 日 导师签名：垂。蹲 日期：碰年旦月j 也日 人连理f ：人学硕十学位论文 1绪论 1 1p 2 p 网络的研究 1 1 1 p 2 p 网络研究的意义 p 2 p ( p e e r - t o p e e r ) 且p 对等计算或对等网络，简单的定义成通过直接交换来共享计算机 资源和服务的网络。在p 2 p 网络环境中，成千上万台彼此连接的计算机处于对等地位， 整个网络不依赖于专用的集中服务器。网络中每台计算机既能充当网络服务的请求者， 又能对其他计算机的请求做出响应，提供资源和服务。提供的资源和服务可以包括：信 息共享和交换、计算资源( 如c p u 共享) 、存储资源( 如缓存和磁盘空间的使用) 等。 p 2 p 在网络兴起的初期就有应用。随着网络的发展和个人电脑的普及，近年来这种 技术在应用上得到了很快的发展。 人们对p 2 p 的关注，始于2 0 0 1 年关于n a p s t e r 的一场官司，结果虽然以发布p 2 p 软件的n a p s t e r 网站败诉，但是它让整个关注此项技术的人们认识到了p 2 p 技术的威力。 在此以后，各种p 2 p 概念的应用软件和服务不断被推出。其中不但有个人编写的应用软 件，而且还有一些r r 巨头在p 2 p 领域投入大量资源进行研究和开发，微软发布了 w i n d o w sx pp 2 p 软件开发包，s u n 公司投入大量资源开发j x t a 平台，许多厂商也纷纷 推出自己的p 2 p 软件，众多学术团体也在致力于p 2 p 技术的研究。 基于p 2 p 的应用一个重要特点就是使人们更多的、更主动地参与到网络活动中，这 也是它能够在近几年迅速发展的原因之一。它倡导各个实体的主动性，既请求得到服务， 同时又提供服务。每一个结点都处于同等的地位，将传统的“内容位于中心”存储模式 转变为“内容位于边缘模式i l l 。这也使得人们在i n t e r n e t 上的共享行为提高到一个更 高的层次。对于p 2 p 的专门研究虽然近几年才得到重视，但是发展迅速，新技术新应用 不断涌现。 虽然以p 2 p 为指导思想的各类应用软件及各项研究在近年来取得了很多成果，但是 这种网络体系并未像最初人们乐观估计的那样对传统c s ( 客户端服务器) 体系造成重大 冲击，而只是在某些应用领域作为c s 结构的补充存在着。人们接触到最多的是基于 p 2 p 技术的聊天工具、网络游戏和文件共享等一些软件。各大公司纷纷推出自己的p 2 p 体系架构，互不兼容。这罩最主要的原因就在于p 2 p 本身的网络特征、社会应用的需求 以及技术的局限性。p 2 p 强调个体参与，但是由于参与者的层次参差不等，使得应用只 能局限在小范围的结点中，或足特殊的应用中( 如聊天工具和文件下载) 。另外，也可以 看到，p 2 p 的发展是和网络的普及分不丌的，并随着人们需求的r 益多元化，p 2 p 的功 p 2 p 环境卜多目标任务调度策略研究 能也在不断改进和完善。随着p 2 p 技术的不断发展，应用环境的不断丰富，它在各个层 面的应用会逐步完善。 p 2 p 网络技术将成为引领互联网进入下一波发展大潮的主线，由于p 2 p 网络巨大的 日订景，世界上一些主要的国家和主要的公司在p 2 p 网络基础设施的建设和p 2 p 网络平台 的开发和应用上加大了投资力度。p 2 p 网络是未来i n t e m e t 的发展方向，也就是说，p 2 p 网络会成为未来的网络基础设施，其应用领域将是十分宽广的。 1 1 2p 2 p 网络结构 p 2 p 系统的最大特点就是各结点之间直接共享资源，其核心技术就是分布式对象的 定位机制，p 2 p 网络的体系结构直接影响着网络的性能。目f j ，根据p 2 p 网络的发展， 可以将p 2 p 网络划分为：集中式p 2 p 模型、纯分布式p 2 p 模型、混合式p 2 p 模型。 ( 1 ) 集中式p 2 p 网络 在集中式p 2 p 网络中，有中心服务器，但与c s 模式不同。中心服务器只保存共享 资源的目录信息，实际的数据保存在提供这些资源的各个对等结点上。各结点之间可以 直接建立连接，但需要中心服务器提供必要的网络服务，如保存元信息、提供索引或路 由、提供安全检验等，通过集中认证，建立索引机制。服务器在此只起到辅助连接的作 用，一旦连接成功，服务器不再起作用，对等结点之间直接进行通信。与c s 模式中的 服务器相比，也可以认为是弱化了服务器的作用。在集中式p 2 p 模型中，由于服务器只 处理对等结点白j 的搜索请求，实际的数据存储在对等结点上，数据的交换在对等结点之 间直接进行，而不用通过中心服务器，因此大大减轻了服务器的负担，并且使各对等结 点的存储和计算能力得到了充分利用。另外，在这种模型中，由于有中心服务器为用户 提供共享和搜索服务，提高了共享资源的搜索效率。但同时要求基于p 2 p 网络的信任模 型的研究中心服务器能连续工作，能处理大量的用户请求，一旦中心服务器失效，整个 p 2 p 网络即陷于瘫痪。集中式p 2 p 模型的典型代表是n a p s t e r 。模型如图1 1 所示。 ( 2 ) 纯分布式p 2 p 网络 在纯分布式p 2 p 网络中，不存在中心服务器，链状的结点之间构成一分散式网络。 网络中的各结点都是对等的，具有相同的能力。任何一个单独的、任意的终端实体离开 网络，都不会给网络中的服务带来大的损失。通过基于对等网络协议的客户端软件搜索 网络中存在的对等结点，结点之间不必通过服务器，可直接建立连接。搜索时，对等点 向其相邻结点发出请求，若其相邻结点没有所要资源，则转发相应请求，直到发现资源， 再与拥有此资源的结点建立连接并交换数据。纯分布式p 2 p 模型由于没有中心结点，不 存在中心结点失效的问题。但由于其搜索和发现是通过向直接相连的结点查询或广播得 人连理i ：人学硕十学位论文 到，搜索请求在网络中传播范围过大，占用大量的带宽，搜索效率相对较低。纯分布式 p 2 p 型的典型代表是g n u t e l l a 、f r e e n e t 等。模型如图1 2 所示。 图1 1 集中式p 2 p 框架结构 f i g 1 1 c e n t r a l i z e dp 2 pn e t w o r ks t r u c t u r e 图1 2g n u t e l l a 的查询流程 f i g 1 2 g n u t e l l aq u e r yp r o c e s s 夯询流 卜载流 查询流 卜载流 ( 3 ) 混合式p 2 p 网络 在混合式p 2 p 模型中，结合集中式p 2 p 快速查找和纯分布式p 2 p 去中心化的优点， 将用户结点按能力进行分类，分为：普通结点、搜索结点和索引结点，使某些结点担任 搜索和索引等特殊任务。这种模型的关键是引入了索引结点和搜索结点等超级结点。索 引结点用来维护可用的搜索结点信息列表，处理来自其它结点的查询请求。要求索引结 点具有较大的内存以及较快的连接速度。搜索结点管理着大量用户结点以及用户结点共 享的文件列表，功能类似于集中模型中的中心服务器。搜索结点用于处理用户的搜索请 求，并从其子结点( 普通结点) 的共享文件列表中搜索。要求搜索结点具有较大的网络带 p 2 p 环境卜多目标任务凋度策略研究 宽以及较强的处理能力。用户结点通过索引结点获得搜索结点信息，之后用户结点就与 获得的搜索结点相连，每一次查询都通过该搜索结点进行。混合式p 2 p 模型的典型代表 是k a z a a 、b t 等。模型如图1 3 所示。 图1 3 混合式p 2 p 网络结构夯询流程 f i g 1 3 m i x e dp 2 pn e t w o r kq u e r yp r o c e s s 查询流 + 一。卜载流 1 1 3p 2 p 网络技术的应用 ( 1 ) 对等计算 采用p 2 p 技术的对等计算，是把网络中的众多计算机暂时不用的计算能力连接起 来，使用累积的能力执行超级计算机的任务。需要大量数据处理的行业都可以从对等计 算中获利，如天气预报、基因的研究等，有了对等计算后，就不需要价格昂贵的计算机 了。在硅谷现在有很多公司征在投入对等计算的开发，如p o p u l a rp o w e r ，c a n t a t a 等， 并获得了巨大的风险资金。i n t e l 也利用对等计算技术来设计其c p u ，并为其节省极大的 费用，同时对等计算的发展是以p c 机资源的有效利用为根本出发点的，因此也受到了 i n t e l 的极力推崇。从本质而言，对等计算就是网络上的c p u 资源共享。 由于对等计算是网络环境下多个结点参与的计算模式，因此它主要有以下特点i 7 i ： 分布与共享。p 2 p 环境的分稚是指p 2 p 系统是由分和在地理位置互不相同的资 源组成的。共享是指p 2 p 网络上的任何资源都可以提供给网络上的使用者使用。 自相似性。p 2 p 网络的局部和整体之白j 存在着一定的相似性，局部具有全局的 某些特征，全局体现局部的特征。 动态性与多样性。p 2 p 网络的资源不是一成不变的，随着时l h j 的推移，p 2 p 网络 资源会动态增加或动态减少。p 2 p 网络资源是异构和多样的。 人连理i ：人学硕十学位论文 自适应性与管理的多重性。p 2 p 网络允许资源拥有者对他的资源拥有自主的管 理能力，而且资源也受到p 2 p 网络的统一管理，但是资源拥有者的管理权限高于p 2 p 网络管理。 ( 2 ) 协同工作 公司机构的同益分散，使得为员工和客户提供轻松、方便的消息和写作的工具变得 同益重要。网络的出现，使协同工作成为可能。但传统的w e b 实现方式，给服务器带 来了极大的负担，造成了昂贵的成本支出。p 2 p 技术的出现，使得因特网上任意两台p c 都可以建立实时的联系，建立了这样一个安全、共享的虚拟空间，人们可以进行各种各 样的活动，这些活动可以是同时进行的，也可以交互进行。p 2 p 技术可以帮助企业和关 键客户，以及合作伙伴之间建立起一种安全的网上工作联系方式，因此基于p 2 p 技术的 协同工作也受到了极大的重视。l o t u s 公司创始人奥奇获得了6 0 0 0 万美元的风险投资， 来开发其协同工作产品g r o o v e 。 ( 3 ) 搜索引擎 p 2 p 技术的另一个优势是开发出强大的搜索工具。p 2 p 技术使用户能够深度搜索文 档，而且这种搜索无需通过w e b 服务器，也可以不受信息文档格式和宿主设备的限制， 可以达到传统目录式搜索引擎器( 只能搜索到2 0 3 0 的网络资源) 无可比拟的深度( 理 论上将包括网络上所有开放的信息资源) 。以p 2 p 技术发展的另一先锋g n u t e l l a 进行的 搜索为例：一台p c 上的g n u t e l l a 软件可以将用户的搜索请求同时发给网络上另外1 0 台 p c ，如果搜索请求未得到满足，这1 0 台p c 中的每一台都会把该搜索请求转发给另外 的1 0 台p c ，这样搜索的范围将在几秒钟内以几何级数增长，几分钟内就可以搜遍几百 力台p c 上的信息资源。可以说，p 2 p 为因特网的信息搜索提供了全新的解决之道，著 名的搜索引擎公司g o o g l e 也宣称要采用p 2 p 技术来改进其搜索引擎，一家名为 i n f r a s e a r c h 的新建公司也因为开发p 2 p 技术的搜索引擎而获得了一笔巨额风险投资。 ( 4 ) 文件共享 p 2 p 技术使在因特网上的任意两台计算机之间直接共享文档、多媒体和其他文件成 为了可能。利用p 2 p 技术，网上计算机之间可以进行直接交互，而不需要使用任何一台 中央服务器。可以说，对文件交换的需求直接引发了p 2 p 技术热潮。在传统的w e b 方 式中，要实现文件交换需要服务器的大力参与，通过将文件上传到某个特定的网站，用 户再到某个网站搜索需要的文件，然后下载，这种方式对用户而言非常不方便。n a p s t c r 就是抓住了人们对m p 3 的音乐需求，其m p 3 交换直接引发了网络的p 2 p 技术革命。在 p 2 p 网络中，对等机通过不同的查询机制定位含有所需资源的其他对等机后，将直接与 其建立连接，并下载所需文件。 p 2 p 环境卜多目标任务调度策略研究 1 2 研究课题的提出 1 2 1 并行计算 高性能计算在大型科学与工程计算中有广泛的应用l l 2 1 。全球天气预报、分子与原 子核结构模拟、大气污染预测、燃料与燃烧机理、计算生物化学、新兴材料研制、医学 解剖与模拟、新药研制、催化剂设计、天文学数据图象处理、石油勘探开发以及与国家 安全有关的重大问题等等，是2 1 世纪初具有重大挑战意义的主要科学工程计算问题， 直接促使高性能计算研究的飞速发展。 实现高性能计算的途径主要有两种，一是提高单机计算速度，二是利用多个处理机 进行并行计算1 3 j 。尽管高性能并行单机系统的运算速度j 下在以万亿次每秒量级上向前推 进，但对于具有多层并发度需求的复杂计算任务，如图象处理与理解、飞机整机性能模 拟、定性与定量推理等计算任务，根据a m d a h l 加速比定律，仅依靠单一体系结构的高 性能并行机难以提高整个并行计算任务的加速比及并行效率。当前，同构的高性能并行 单机系统还远不能满足科学与工程计算的现实需求，因此网络并行计算应运而生。国际 上自二十世纪八十年代中期就兴起了网络计算的研究热潮1 4 5 l ，其具有高于高性能并行 单机系统的强容错性能，并具有较长的生命周期。 对等网络是近几年兴起的热门网络技术，改变了人们使用网络的方式，也为未来网 络的发展提供了一种新的思路。对等网络中的每个结点的地位都是对等的，每个结点既 充当服务器，为其他结点提供服务，同时也享用其他结点提供的服务。每个结点可以随 时加入或离丌网络系统，系统的拓扑结构随时可能发生变化。 随着i n t e r n e t 的飞速发展、网络带宽的成倍增加以及计算机计算能力的大大提高， 对等网络受到越来越多的关注。但增加的计算能力并未被充分的挖掘，空闲的链路带宽 被白白浪费，对等网络为充分挖掘计算机空闲的计算能力提供了可能。 1 。2 2 课题的提出 分布式计算技术研究的是如何充分利用网络中各种计算单元来共同完成大规模的 计算任务。由于单一计算单元的计算能力总是有限的，因此人们一般采用并行技术、分 稚式技术将多个计算单元结点联合起来共同完成大规模的计算任务，同时目前网络中的 计算机的计算能力一直利用的不是很充分，人们期望能够充分利用网络中的闲散计算能 力来完成大规模的计算任务。p 2 p 计算技术则为普及计算技术的发展提供了新的机遇。 分命式计算可以帮助企业完成大规模的数据处理，参与计算的计算机之间可以直接 共享计算中的中间结果。通过整合这些以日驴尚未使用的闲散计算能力和资源可以将企业 的计算能力得到很大的提升，同时因为利用了多个结点上的计算能力使得计算任务可以 大连理t 大学硕十学位论文 高效廉价的完成。网格计算g r i d l 6 1 是研究分布式计算的典型代表，i b m 公司也启动了 自组织计算计划米研究。 p 2 p 计算技术可以归结为一种特殊的分布式计算技术，从而p 2 p 计算技术所面临的 很多问题都可以利用目前的分布式计算技术的研究成果来解决，如并发控制、事务处理 等基本的分布式系统所面临的问题。但是很多问题在p 2 p 系统中具有了其自身的特点， 目前一般从以下几个角度来研究和解决p 2 p 计算中所面临的问题：任务调度的时机、调 度目标的实现要求、紧迫性任务的响应问题、容错问题和系统的实时性要求。这几个因 素并不是相互独立的，而是互相联系，相互影响的。通常在设计一类分布式系统的任务 分配方案时，要综合考虑几个方面的因素。本文主要考虑纯p 2 p 环境下任务与结点的匹 配策略，针对任务调度的不同目标提出不同的解决方案。 1 3常见任务调度模式及调度算法介绍 1 3 1 经典调度理论 经典调度理论，又称为确定性调度理论，起始于2 0 世纪5 0 年代，是组合优化领域 的一个分支。经典调度理论可以提供构造任务执行顺序的方法，可将任务在确定的时间 上分配给处理机。利用任务的准备时间、释放时间和计算执行时间等时间特性信息，调 度算法可以产生一个精确的调度策略( 但不一定是最优的分配与调度策略) ，调度算法的 输出通常是优化与任务完成时间相关的一个或几个性能指标。 主要的调度策略方法如下所示。 ( 1 ) 基于优先级的方法 基于优先级的任务分配与调度方法中，每个任务被指派一个优先级嘲。调度算法维 护一个任务队列，所有的任务按优先级从高到低的顺序排列到队列中。在任务执行过程 中，一旦出现处理机空闲时，则从任务队列中将准备就绪且具有最高优先级的任务分配 到该空闲处理机上去执行。这种方法中任务优先级的分配策略是关键。分配策略的好坏 直接影响到分配与调度算法的效率。 ( 2 ) l i s t 调度方法 l i s t 调度是一种优先级驱动的非抢先式任务分配与调度技术。当多个任务的执行存 在先后顺序约束关系时，其顺序约束关系一般用不含回路的有向图( d i r e c t e da c y c l i c g r a p h ) 表示。c o f f m a n 7 】已经证明：对于树结构( 可扩充到森林结构) 的u e t 系统，l i s t 调度方法能最小化任务的调度长度。 p 2 p 环境下多目标任务调度策略研究 1 3 2 常见的任务调度模式 常见的任务调度模式有以下三种【8 】： ( 1 ) 集中式调度模式 在集中式调度环境中，一个中央机器扮演着资源管理者的角色，它将任务调度到环 境周围的其它结点。这种调度模型通常在所有资源具有相似特性和使用规则策略的场合 中。在这种调度中，任务首先提交给中央调度者，然后由它将这些任务分配给适当的结 点，那些不能在一个结点上启动的任务通常存放在中心任务队列中，以便随后启动。集 中式调度系统的优势之一是调度者能够给出更好的调度策略，因为它拥有关于可用资源 的所有必要的、最新的信息。然而，集中式调度显然不能与它所管理的不断增长的环境 匹配的很好。调度者本身可能成为一个瓶颈，必须保证其安全和可靠，以防止单点失效， 比如建立双调度器是解决单点失效的有效办法。 ( 2 ) 分布式调度模式 在分布式网络调度模型中，每个网络调度器仅维护本管理域的负载信息，没有中央 调度者负责管理所有的任务。一个调度者和其它调度者之间有两种通信方式：直接通信 和间接通信。分布式调度克服了集中式调度的可扩展性问题，而且它能够提供更好的容 错能力和可靠性。但由于缺乏中央调度者，分布式调度通常导致不够理想的调度决策。 ( 3 ) 分层调度模式 分层调度实际上是分为两个阶段，外部调度和内部调度。外部调度是指，首先通过 网络资源信息服务寻找到当前满足任务需求的资源，然后通过某种策略从这些资源中选 择最佳的资源来执行任务。内部调度是指任务映射到本地服务资源以后，由服务资源本 地管理者予以调度。分级式调度模式就是指在外部调度采用集中式的调度，而在内部调 度中允许资源提供者使用自己的调度策略来进行任务调度。因此，这种模式是一种结合 式的方法。在小型的系统中，采用集中式调度比较好。因为在小型的系统中，资源不是 很庞大，调度中心比较容易掌握所有的资源，对一个任务的请求可以高效地产生调度方 案。而分布式调度其优点是健壮性、可靠性和可用性，但是如果各个调度中心之间没有 高效的吞吐或者通信量比较大时，不易于管理和资源协同分配，所以很难找到全局最优 的资源分配方案。分层调度器易于实现扩展和容错，易于资源的协同分配，但不支持资 源地域自治和多种调度策略。 1 3 3 任务调度算法分类 ( 1 ) 启发式 对于n p 难题的任务调度算法，至今没有找到有效的算法，以求近似最优解的启发 人迮理i ：人学硕+ 学位论文 式算法得到了极大的运用。围绕启发式调度算法，国内外都做了大量的研究，提出了一 些比较成熟的调度算法1 9 j ，如下所示： 模拟退火算法 模拟退火算法是广泛使用的解决组合优化问题的算法之一。它模拟机械工业上的金 属冷却过程，它的最大优点是能避免问题的解落入局部最小。模拟退火算法采用循环搜 索来寻找问题的优化解，循环刚丌始时，算法以一定的可能性接受相对较差的解决方案 以获得有可能更好的问题解搜索空间。随着算法的不断进行，较差的解决方案被接受的 可能性越来越小，最后输出的是较好的解决方案。 禁忌搜索算法 这是一种循环搜索技术，但它在问题的解空间里记录了己经搜索过的空间以避免重 复搜索临近区域。对于每个解决方案s e x ，s 是s 的一个可能的小的改动，例如其中 两个任务相互交换，他们组成了s 的邻居。在这些邻居中，算法求解局部最优问题，然 后这个局部最优问题搜索的映射被加入到一个t a b o o 列表中，t a b o o 列表记录了已经搜 索过的空间。算法重新产生一个映射，如果这个映射和t a b o o 列表中的元素基本相同， 这个映射就被称为是禁忌的，算法将会重新选择映射。 a 掌算法 a 拳算法在许多任务分配问题都有应用。它是一种启发树式搜索算法，根结点是一个 空结点，而中间的结点是部分的解决方案。它在广度有限搜索的基础上增加了一个函数 f ( x ) ；g o ) + o ) ，其中g ( x ) 是达到某个状态时已经花费的丌销，h ( x ) 是一个构造函数， 表示从该状态丌始到达目的状念的丌销的估计值，从而加快了搜索速度。 g a g a ( t h eg e n e t i ca l g o r i t h m ，遗传算法) 是用来寻找比较大的解决方案的一个算法，它 是对己给问题的染色体进行操作，而最初的染色体是随机产生的一个染色体，可以由任 何一个算法产生。 m i n m i n 算法 在m i n m i n 算法中，先要算出每一个作业在每个机器上的最短完成时间。所有作业 中，拥有最小完成时间的作业将被选出来，分配到对应的机器执行，将这个作业删除， 重复上述工作，直至所有作业都被分配。 m a x m i n 算法 m a x m i n 算法与m i n m i n 算法类似，还是要先算出每一个作业在每个机器上的最短 完成时| b j 。在所有作业中，拥有最大最短完成时间的作业将被选出来，分配到对应的机 器执行，将这个作业删除，重复上述工作，直至所有作业都被分配。 p 2 p 环境卜多目标任务调度策略研究 在第4 至第6 个算法中，m i n m i n 算法是最快的算法，g a 算法比m i n m i n 要慢， a 宰是最慢的。对一个1 6 个资源，5 1 2 个作业的网格环境，m i n m i n 算法的执行时间差 不多是1 5 ，g a 算法的执行时间是3 0 5 ，而a 宰算法的执行时| 日j 要1 2 0 0 5 。m i n m i n 算法 是一个简单、快速的算法，并且性能比较好。g a 算法使用m i n m i n 算法来播种染色体， 也是因为它有比较好的性能。m i n m i n 算法的缺点是只考虑到完成时间方面的要求，在 算法目标的其它方面几乎没有考虑，因此这种算法只是在理论情况下是比较好的，对于 执行时间长的大任务就无法保证服务质量。因为大任务通常由于算法的关系被排到最后 完成，这样就不适合在网格的环境下进行任务调度。这种算法只是在理论情况下是比较 好的。在文献 1 0 e p ，考虑到o o s ( 主要指带宽) 的情况下，算法显然不能合理地安排作 业的调度，因此在文献【1 0 】中提出了q o sg u i d e dm i n m i n 算法，在调度过程中，引入了 q o s 这个评判标准，使得在考虑算法m a k e s p a n 的同时，也要兼顾到带宽( o o s 的一个方 面) 的影响。 ( 2 ) 经济模型 随着网格、p 2 p 等分布式网络的发展，网络中的资源不可能无偿的给网络用户提供 服务，将资源的拥有者看成生产者，网络中的用户看成消费者，很自然地，可以将网络 环境下的资源使用看成是一种经济活动。用户如果需要使用某个资源，只需要支付一定 的“钱”，这个“钱可以是网络中的一种特定的可流通的货币，也可以是现实生活中 的货币，在一定条件下，两者可以相互转换。在这种日订提下，经济模型的作业调度随即 产生了。根据经济学理论，目前的网络环境下的经济模型可以包括以下几种：商品市场 模型；标价模型；讨价还价模型；招标合同网模型；拍卖模型；基于投标的资源均衡共 享模型；合作联合交换模型。 1 4 论文的主要工作 论文主要包括以下工作： ( 1 ) 介绍了p 2 p 网络的研究意义，p 2 p 网络结构及应用，并介绍了当f i 常用的任务 调度模式及调度策略等。 ( 2 ) 深入分析了任务调度的特点、目标以及任务调度的研究现状。 ( 3 ) 为了更有效的利用p 2 p 网络资源且达到任务调度负载均衡目标，提出了基于相 似度的任务调度策略。通过计算现行任务与历史任务之间的相似度，来确定能够直接调 度的结点：通过计算任务需求资源与结点可提供资源的相似度并利用距离因素对其进行 修讵，来获取满足任务需求的有序结点集合。在此基础上，利用所提出的基于相似度的 人连理i ：人学硕十学位论文 任务调度算法来完成任务调度过程。采用基于相似度的算法，可以有效的利用网络资源， 有效的消除任务调度过程中的“颠簸”问题和减少网络丌销。 ( 4 ) 在p 2 p 任务调度的多个目标中，经济原则是需要考虑的一个重要方面。以前的 任务调度算法主要考虑最优跨度即时问因素，而p 2 p 环境的特点决定了其任务调度性能 是受多个因素制约的。本章在考虑时间跨度的同时，考虑了执行费用因素。通过考虑任 务执行时间、结点间的通信时间和任务调度费用等因素，提出了多目标约束的并行任务 调度策略。首先提出了多目标任务调度的数学模型，利用任务需求与结点性能之间的关 系来定义各目标的需求关系矩阵，然后利用隶属度函数将各个关系矩阵转化为模糊矩 阵，并根据每个目标对最终目标的不同影响来确定各目标在最终决策中所占的比率，从 而将多目标转化为单目标任务调度模型，在此基础上对一个任务m 个结点的最优分配问 题利用匈牙利算法进行求解。 ( 5 ) 任务服务质量的目标强调不同用户对任务的特殊要求，为了更好满足不同用户 对服务质量的要求并且更好的利用系统资源，将用户的任务根据任务的实时性要求、等 待调度任务队列和执行结点状况等划分为实时任务调度和非实时任务调度两种方式。根 据划分的实时任务和非实时任务，分别描述了其任务调度模型，在任务调度模型中引入 排队机制，可以更有效满足不同用户任务实时性的需求。 1 5 论文的组织结构 在第一章中，主要叙述p 2 p 网络的研究意义，p 2 p 网络结构及应用，并介绍了当前 常用的任务调度模式及调度策略等。 第二章，深入分析了p 2 p 环境下任务调度的特点、目标以及p 2 p 网络任务调度的研 究现状。 第三章，为了实现任务调度负载均衡和充分利用计算资源的目标，提出了基于相似 度的任务调度算法。 第四章，在考虑时间因素的基础上考虑了经济原则，提出了多目标约束的任务调度 策略。 第五章，为了满足不同用户对任务质量的特殊要求，将任务划分为实时