（计算机系统结构专业论文）可扩展智能分布并行调度模型.pdf

摘要 计算模式正在向三个趋势发展：网络化，智能化和个性化o f 同时，x m l 技术 的出现，使得不同平台的计算资源融合的步伐加快，协同通信计算的发展以及网 格等计算技术的延伸，在计算的多元化的加剧雪勺同时，各个不同平台相互协作的 需求更为突出。g 上述趋势要求分布并行计算环境能够应付急剧变更的需求、具备更好的可扩 展性、能够提供更为安全的计算环境以及能够对更为个性化的计算提供服务这 需要分布并行计算环境能够便捷地根据任务请求分配计算资源，提供给最终用户 和开发人员简洁盼界面，为用户屏蔽多元化计算的复杂性同时提供对多元化计算 的有效支持。因此，需要分布并行计算具备更好自适应和更强的可扩展性，以容 纳不断扩展的计算类型和服务。，勿 解决上述问题的关键是提供一个开放的计算模式来容纳计算的多元化，其中 的一个关键环节就是提供适应能力和可扩展性更好的分布并行调度。 本论文尝试通过改造调度器的软件结构为该问题提供一个尝试性的解决方 法。 本文安排如下：首先，在引入研究问题的基础上，讨论分布并行的调度模型 所需要具备的新的特征以及给出这些特征的一个可计算的解决方法；然后，在此 基础上提出一种新的分布并行调度的设计模型，该模型重点解决分布并行调度的 设计结构对可扩展性，自适应性的制约问题；接着，基于上述讨论结果提出了分 塑羞堡塑廑墨设计和实现上的具体应用实例；最后，通过试验的方法讨论了该实 际模型的性能并对本文进行简要总结。 关键词衔并行调度，软件粕， 步陋应矽 a b s t r a c t w h i l ec o m p u t i n gi sb e c o m i n gm o r ei n t e r c o n n e c t e d ，i n t e l l i g e n t a n d p e r s o n a l i z e d ，t h ef o l l o w i n gc h a r a c t e r w i l lb e c o m em o r ee v i d e n tt h a ne v e r ： t h ei n t e g r a t i o no fc o m p u t i n ga n dc o m n u n i c a t i n g ，t h et r a n s f o r m a t i o no f p c sf u n c t i o nt om o r en o n e p cd e v i c e s ，t h ee m e r g e n c eo fg r i dc o m p u t i n g w i t ht h em a t u r eo fx m lt e c h n o l o g y ，t h ec o m p u t i n gr e s o u r c eo nd i f f e r e n t p l a t f o r mc a nb ee x c h a n g e dm o r ea n dm o r ec o n v e n i e n t l y i tl e a d st om o r e d e m a n d so fs e a m l e s sc o l l a b o r a t i n go fd i f f e r e n tc o m p u t i n gp l a t f o r m t h ea b o v e r e q u i r e m e n t s l e a dt ot h e p r o b l e m ：h o w t oi m p l e m e n ta c o m p u t i n gp l a t f o r mt h a ti sm o r ea d a p t i v ea n de x t e n s i b l e t h i sp a p e rt r i e st or e s o l v et h i sp r o b l e mb yr e d e s i g n i n gt h es o f t w a r e a r c h i t e c t u r eo fd i s t r i b u t i n gp a r a l l e ls c h e d u l em o d e lt o i m p r o v et h e s y s t e m sa d a p t a b i l i t ya n de x t e n s i b i l i t y t h i sp a p e ri sb a l a n c e da sf o l l o w i n g f i r s t l y ，t h i sp a p e rs t u d i e st h e c h a r a c t e r so fd i s t r i b u t e dp a r a l l e ls c h e d u l et h a tr e q u i r e db yt h et r e n d o fd i s t r i b u t e dp a r a l l e lc o m p u t i n ga n dc r i t i c i z e st h ee x i s t i n gs o l u t i o n t ot h e s e p r o b l e m s ：s e c o n d l y ，t h i sp a p e rd e v e l o p sae x t e n s i b l ea n da d a p t i v e d i s t r i b u t i n gp a r a l l e ls c h e d u l et or e s o l v et h e s ep r o b l e m s ：f i n a l l y ，t h i s p a p e ro f f e r st h r e ek e ye x p e r i m e n t st ov e r i f yt h e r a t i o n a l i t yo ft h e s o l u t i o na n dt h e nd r a w sc o n c l u s i o n k e y w o r d s ：d i s t r i b u t i n gp a r a l l e ls c h e d u l i n gm o d e l ，s o f t w a r e a r c h i t e c t u r e ，a d a p t a b i l i t ya n de x t e n s i b i l i t y h 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作 及取得的研究成果据我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为 获得电子科技大学或其它教育机构的学位或证书而使用过的材料。与 我一同工作的同恚对本研究所做的任何贡献均已在论文中作了明确的 说明并表示谢意 签名； 盔血整日期：弋年月日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘， 允许论文被查阅和借阅本人授权电子科技大学可以将学位论文的全 部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：目嗥 导师签名：吟! i 日期：年月h 日 第一章引言 如文献 1 ，2 j 所述，目前的计算模式正在向三个趋势发展：网络化， 智能化和个性化。伴随这些趋势，当前计算模式呈现以下五个特征： 第一，从技术方面来讲，计算和通讯技术融合。现在计算是建立在通 讯技术和计算技术融合的基础上，各种计算模式的融合； 第二，从范围来讲，p c 的功能正被开拓到更多的环境、更多的设备之 上。计算将无处不在的，任何地方都有计算，同时计算的形式会向多元化 发展； 第三，在功能和性能方面，p c 将经历很大的转型。在以后p c 不仅仅是 计算的工具，就是说计算机不仅仅具有计算的功能，同时也是沟通和控制 的平台。以后，计算机可能更多的是用于通讯、控制及娱乐。比如说在家 庭里有许许多多的智能家电，p c 这个时候很重要的功能是把智能家电更好 的连接、管理和控制起来，把信息存储起来，例如控制家里的灯光、音响 等，做各种调配工作； 第四，从架构方面，计算正在走向网格化，就是说计算本身是分布在 一张网格上，像电网一样，无处不在，而且分布是有机的，这也是未来计 算模式中一个很重要的特征； 第五，安全的网络环境成为计算模式发展的重要保障。当计算的功能 或者整个内容或者信息遍布到每一个角落的时候，怎样营造一个安全、可 信的环境就变得十分重要。 另外，x m l 技术的出现，使得不同平台的计算资源整合的步骤加 剧。协同通信计算的发展以及网格等计算技术的延伸，计算的多元化成为 目前的趋势。 分布并行计算适应上述的趋势的关键是具备可扩展性和适应性： 1 计算的可扩展性。可方便的扩展分布并行计算的类型，计算环境 中的硬件和软件资源； 2 计算的适应性。分布计算环境可根据不同类型的服务特征，调整 曼芝曼! 丝坌塑茎笪塑堕苎型 一一 服务策略，以便为不断出现的新的计算分布服务类型提供不断优 化的，已充分利用分布并行系统中的计算潜力a 实现分布并行计算环境的可扩展性和适应性的关键之一是分布并行调 度器具备可扩展性和适应性。 传统的分布并行调度计算的研究集中于算法的研究，然而，现有的分 布并行调度陈旧的的软件结构已经成为制约分布并行系统的可扩展性和适 应性瓶颈。本论文的目的是通过改造分布并行调度器的软件结构提高分布 并行调度器的可扩展性、适应性。 本文的组织如下：首先，阐述本论文研究主题的价值和相关的研究方 法；然后，研究和本论文相关领域的现状；接着，讨论分布并行调度模型 设计相关的核心问题；在此基础上，讨论分布并行调度涉及核心问题的解 决方法，提出可扩展的分布操作系统调度的设计模型( e d s ) ，并通过相关 的试验讨论该模型的设计性能。最后，总结了本论文的要点，并提出进一 步研究的方向。 一亘芏墨! 丝坌变茎堡塑壅苎型一 第二章 相关研究 2 1现有分布并行调度软件结构 本节选取几个主流的分布并行系统( a m o e b a ，j i n i 和a u t o s e c ) ，重 点分析其调度器软件结构；在对其进行评价基础上，为设计新的分布并行 调度提供借鉴。 2 1 1a m o e b a 调度器的设计结构 文献 4 中提到v d j e 大学a n d r e w s t a a e n b a u m 教授及其研究生分布 操作系统a m o e b a 。 a m o e b a 作为分布并行操作系统具有一定代表性，且目 前版本比较成熟 5 3 版本，在学校、政府使用了5 年以上 同时源代码对 研究人员开放，并设立了支持网站 7 可以获取资料丰富教程，便于同原 设计者交流。 本节介绍a r a o e b a 的分布并行调度器r u ns e r v e r 的软件结构及其评价。 2 1 1 1 设计思想 如文献 4 所述，a m o e b a 调度器实现为单独的调度服务器运行服 务器( r u ns e r v e r ) 。 运行服务器的主要功能是在不给系统带来太大额外负载的情形下，采 集处理器池中各个节点的实时的负载信息，并且根据任务对资源的需求， 将新到的任务迁移到最合适的处理节点的上实现负载平衡。 其对任务的行为( 耗用资源的特点) 和处理节点资源的可用程度都还 比较简单( 因为任务的运行特点无法准确的预测) ；因此，a m o e b a 的设计 者为调度器提供了将运行中的任务迁移到其他节点的功能( 进程迁移) 。 因为进程迁移实现的复杂性，同时由于降低了任务执行的可靠性，该调度 器只能对部分类型进程进行迁移，所以a m o e b a 调度器负载平衡主要是依 里芏墨! 堕坌查茎堡塑堡苎型一 靠对新任务迁移实现的。 运行服务器启动后一直处于运行状态( 由启动服务( b o o t s e r v e r ) 器 重新可以启动僵死的运行服务器) 。 2 1 1 2 软件结构 运行服务管理任意数量的处理器池( p r o c e s s o rp o o l s ( m p o o l d i r s * ) ) ， 每个处理器池的予目录包含了多种结构( m u l t i p l ea r c h i t e c t u r e s ) 处理节 点( * a r c h d i r s * ) 。一个节点可能同时成为一个或者多个a r c h d i r 的成 员。每个p o o l d i r 具备不同的处理能力，因此，被定向到某个p o o l d i r 的 服务请求只会被该p o o l d i r 节点集合的节点处理。 运行服务器的对外接口是e x e c _ m u l t i _ f i n d h o s t ，通过该接口向r u n s e r v e r 提供被调度进程( 任务) 的描述字集合，该接口返回一个最适合执 行该进程的处理节点，将该任务迁移到适合的节点上执行。 运行服务器由三组线程组成：处理到达的请求的线程组，( 按一定规 则) 采集处理器的负载信息的线程组，和在服务节点出现故障以后查询监 控其状态是否转为正常的线程组。第三组线程区分节点是否可用( 处于u p 状态) 以避免任务等待已经出现故障的节点。( 后面两组线程由时间管理 器进行管理) 。 系统用一个1 6 - b y t e 的结构保存单个调度任务的信息。运行服务器中 各组线程是并行执行的；这样，当处理一个请求的时候，别的请求不用等 待该请求执行完，可以得到其他请求处理线程的及时处理；另外，当某个 个用户请求任务速度很快，调度的客户端部分可以考虑将多个任务请求分 布到多个节点上从而提高任务的并行处理性能。 2 1 1 3 运行服务器各个策略的实现 口 定位策略的实现 如文献 4 ，一个任务从请求到执行进行如下过程： 1 计算进程描述符合处理器池的交集； 里芝壁塑丝坌变堑塑墨堕型 2 运行服务器检查那些候选机器有足够的内存来运行该任务，排 除掉没有足够内存的节点； 3 对上述节点，计算其运行新的程序后的计算能力，每个节点做 出各自的计算结果，取其中有能力较强服务能力的节点执行该 任务。 1 ：3 负载信息采集策略 如文献 4 ，a m o e b a 分布并行系统中各个节点定期统计自己节点的 c p u ，内存的负载参数；并定期调用获得其他节点的负载值的接口 ( g e t l o a d ) 获得全局的负载信息，以保证其负载相关信息是及时的。 1 3 迁移策略 a m o e b a 的调度器提供如下两种任务迁移方式： 1 新任务迁移一根据现有节点的资源可用性和新任务对资源的需 求量，将新进入的任务迁移到合适的节点，这种迁移代价是较小 的； 2 运行中任务迁移一将运行中的任务迁移到其他节点( 进程迁 移) 。a m o e b a 的设计者认为应该在调度过程中尽可能避免进程迁 移，因为进程迁移带来额外负载，增加了设计和管理的复杂性， 同时降低了系统的可靠性。导致这种迁移的主要原因是对任务对 资源的需求估计不够准确，如果能够学习任务的特性那么就可以 尽量减少进程迁移，提高分布计算的性能。 2 1 1 4 a m o e b a 调度器结构软件评价 口 优点 a m o e b a 的调度器在设计上实现为3 组线程的软件结构的设计方法是值 得借鉴的。这样的设计策略明确的划分了分布并行调度的职责，使得实现 和维护更为方便。 0 缺点 里芏墨! 丝坌查茎堡塑鏖苎型一 a m o e b a 的调度器存在如下缺点： 1 不支持调度器功能的动态扩展。对调度器性能扩展和升级代价 通常很大。 2 由于缺乏对任务特性的学习，导致进程迁移频率无法降低因 为对任务耗用资源的估计是预先设计的，因此，无法准确地估 计新的任务类型资源耗用特性，不能有效地降低任务中途迁移 的比率以优化调度性能； 3 以c p u 和内存指标为基准的负载衡量方式不能准确地反映负载 的真实情形。由于负载衡量方式( a m o e b a 只以可用c p u 资源， 可用内存资源为负载衡量参数) ，该调度器对网络i o 类型服务 分布计算效率不够理想。比如，虽然a m o e b a 服务器虽然提供了 f t p 服务，但按照器负载衡量方式是无法合理地调度该类型服 务的。 2 1 2j i n i 计算平台的动态服务插件技术 2 1 2 1j i n i 概述 如文献 9 所述，j i n i 技术是基于j a v a 语言的分布式的对等基础结 构，j i n i 网络是一个分布式动态网络系统，它允许服务随时加入和离开而 不需要任何人工干预。 当服务连接进入网络时，该服务使用力嘲功议( ，d i s c o v e r y ) 来搜索 查找腰务fl o o k u ps e r v i c e ，) ，获得相应查找服务的龙翟接口；然后使用 加入协议( j o i n ) 将自己崖嬲到查找服务之中，这时该服务就可以为其他 服务所使用。 调用其它服务的设备或应用程序的过程通常如下进行：首先，与其相 邻的查找服务进行连接，这时他可以看到本联合体内所有可用的服务，使 用查找协议( 1 0 0 k u p ) 将所感兴趣的服务的代理接口下载到本地之后就可 以和服务提供者进行直接交互通信。同样，当一个查找服务启动时，它也 使用发现协议向服务进行广播自己的启动，以便服务进行注册登记。 2 。1 1 2j i n i 平台设计结构 j i n i 分布式结构体系包含如下三个部分：基础结构 ( i n f r a s t r u c t u r e ) 、编程模型( p r o g r a m m i n gm o d e l ) 和服务 ( s e r v i c e s ) 。 基础结构。它由构成分布式联合体( f e d e r a t i o n ) 的组件组成，其最 小内核为分布式安全系统，发现、加入协议( d i s c o v e r ya n dj o i n ) 、服 务协议和查找服务( 1 0 0 k u ps e r v i c e ) 。分布式安全模型及其实现定义了 软件实体的认证方式及操作权限；发现、加入协议定义了服务加入j i n i 系 统的方法；查询服务则是供服务进行注册登记的场所，这里提供了可以使 用的服务对象的集合； 编程模型。编程模型由下列接口组成：租借接口，定义了基于事件的 资源分配和释放方法；事件和通知接口，它将j a v a b e a n s 组建所使用的事 件模型扩展为分布式事件模型，来支持j i n i 服务基于事件的通信；事务接 口，它引入了一种面向对象的协议，使用表决”和提交两个阶段来 统一对象之间的相关行为，使得一个事件序列要么全部完成要么全都不发 生。 服务。服务是j i n i 体系的核心，基础结构和编程模型一起来支持服务 的提交注册及服务的发现，服务使用基础结构来完成服务之间的相互调 用，相互发现并向其他服务来发布本服务的出现。服务在j i n i 环境里以对 象的形式出现，它通过接口来定义其提供的可供其他服务使用的操作和特 性。 2 1 2 3j i n i 资源调度特点分析 口优点 提出了服务动态插接的概念，为分布并行计算的研究和设计提供了新 的视角。其服务的发现食查找协议使得分布计算环境的更为灵活。提供了 分布并行计算的安全计算环境的具体实现。 其分层的软件结构方式，便于开发者在现有功能的基础上，方便的扩 展应用服务。 口 缺点 j i n i 技术存在如下不足：局限于j 8 v a 计算平台；因为j i n i 主要针对家 庭网络( 局域网内部的计算分布) ，不用过多考虑资源的优化访问；因 此，对资源可用性讨论存在与否而对资源的优化访问触及不多。 分层的软件结构不便于对分布计算平台的底层进行功能扩展。 2 1 3a u t o s e o 2 1 3 1 设计目的 由u n i v e 鸭时o f c a l i f o r n i a 分布式中间件研究小组开发的a u t o s e c ( a u t o m a t i cs e r v i c ec o m p o s i t i o n ) 1 0 可以根据目前系统的状况和用户的 需求动态的选择信息采集策略和服务资源提供策略。 a u t o s e c 的目的是整合信息采集策略和资源分配策略 1 1 。信息采集 策略对资源分配策略影响可用如下度量标准衡量：客户请求的成功率，维 护系统信息所带来的额外负载开销，以及分布并行调度的整体性能。通过 研究现有的信息采集策略和资源分配策略，a u t o s e c 的研究者总结出一套 动态服务组件组合的原则，在此基础上实现了a u t o s e c 。 2 1 3 2a u t o s e c 调度器设计结构 如文献 1 1 ，a u t o s e c 调度器设计结构的设计结构如下图： - 8 - 图2 - 1a u t o s e c 调度器设计结构 h i 图中各个部分实现功能如下： 1 d i r e c t o r ys e r v i c e 存放系统参数，如网络传输能力参数，节 点服务能力参数及客户端相关参数。d i r e c t o r ys e r v i c e 中的 信息根据当前网络状况和用户需求使用不同的刷新策略； 2 信息采集模块( i n f o r m a t i o nc o l l e c t i o nm o d u l e ) 根据 d i r e c t o r ys e r v i c e 中的客户端，服务节点和网络确定是否根据 当前状态信息刷新d i r e c t o r y ； 3 资源分配模块( r e s o u r c ep r o v i s i o n i n gm o d u l e ) 根据d i r e c t o r y s e r v i c e 为任务分配计算资源； 4 网络监控模块( n e t w o r km o n i t o r i n gm o d u l e s )采集当前的 网络传输能力的信息； 5 动态服务代理( d y n a m i cs e r v i c eb r o k e r ) 根据不同的任务 对资源的需求，采用不同的策略对其进行调度。 2 1 3 3 a u t o s e c 调度器特点分析 口优点 提出了不同调度算法对不同类型的任务效率不同的问题，并在 旦芏曼! 些坌查茎堑塑壅篓翌一 a u t o s e c 调度器结构中实现了混合调度算法解决了该问题。 口缺点 a u t o s e c 的研究还局限于多媒体分布计算，不具备通用的特性。 2 2网格计算对分布并行调度的启发 网格计算反映了分布并行计算发展的方向，同时揭示了推动分布并行 计算发展的动力。 在文献 1 2 ，1 3 中，网格计算被定义为广域范围的无缝的集成和协 同计算环境。网格计算模式已经发展为连接和统一各类不同远程资源的 一种基础结构。传统的因特网实现了计算机硬律的连通，而网格试图实现 互联网上厉方劳掾的全面连通，包括计算资源、存储资源、通信资源、软 件资源、信息资源、知识资源等。 简而言之，网格是把整个网络整合成一台巨大的超级计算机，实现计 算资源、存储资源、数据资源、信息资源、知识资源、专家资源的全面共 享。网格的根本特征是资源共享。 2 2 1网格计算8 三要素” 网格计算至少需要具备三种基本功能：任务管理、任务调度和资源管 理。各个基本功能描述如下： 任务管理。用户通过该功能向网格提交任务、为任务指定所需资源、 删除任务并监测任务的运行状态。 任务调度。用户提交的任务由该功能按照任务的类型、所需资源、可 用资源等情况安排运行日程和策略。 资源管理。确定并监测网格资源状况，收集任务运行时的资源占用数 据。 2 2 2网格多计算平台特性 计算平台向多计算平台和技术过渡。目前的网络计算平台主要由微软 的操作系统、i n t e l 的芯片、思科的网络设备构成。网格的应用会改变计 算平台，带动网络界面发展。平台使用模式改变了，平台也随着改变，分 布计算会出现在更多的计算平台上，并引发新的计算模式包括新的技 术模式和商业模式。 2 2 3基本问题 实现网格计算，必须重点解决三个问题： 1 异构性。由于网格由分布在广域网上不同管理域的各种计算 资源组成，怎样实现异构机器间的合作和转换是首要问题； 2 可扩展性。要在网格资源规模不断扩大、应用不断增长的情 况下，性能不受到影响； 3 动态自适应性。在网格计算中，某资源出现故障或失败的可 能性较高，资源管理必须能动态监视和管理网格资源，从可利 用的资源中选取最佳资源服务。 2 2 4 网格计算对调度发展方向的启发 文献 1 2 ，1 4 】简要的讨论了网格计算中调度器的相关问题，可以发现资 源的调度和传统的分布并行计算的调度功能设计没有本质区别，但更强调 的计算的可扩展性问题和自适应性。同时网格强调不同计算平台的协同计 算模式，对分布并行计算的跨平台特性提出了更广泛的需求。 2 3软件体系结构 2 3 1软件结构 文献 1 4 将软件体系结构定义为两个部分：一个是计算部件，另一个 就是部件之间的交互。部件之间的连接可以被认为是一种连接器，比如过 程调用、事件广播、数据库查询等等。好的的体系结构设计是软件系统成 功的关键。 软件体系结构表示了软件系统的高层结构，主要特点有： 1 软件系统结构是一个高层次上的抽象，它并不涉及具体的系统结 构( 比如b s 还是c s ) 和具体的实现； 2 软件体系结构必须支持系统所要求的功能，在设计软件体系结构 的时候，必须考虑系统的动态行为； 3 在设计软件体系结构的时候，必须考虑有现有系统的兼容性、安 全性和可靠性。同时还要考虑系统以后的扩展性和伸缩性。所以 有时候必须在多个不同方向的目标中进行决策。 当前已经有一些规范化软件体系结构，比如：i s o 的开放系统互联模 型、xw i n d o w 系统等等。 文献 1 4 指出对软件结构进行形式化有利于开发人员更为科学有效地 规划和设计软件地体系结构，同时形式化地描述也可以使软件方便地验证 体系结构并促进软件体系结构的重用。 c m u 软件研究所的研究者在软件结构的形式化描述方面做了相关研 究，设计了如a c m e 6 的软件结构描述语言( a d l ) ，并在此基础上开发 了可用于软件结构的描述或者实现相关的开发工具。另外可以使用o m g 推 荐的统一建模语言( u m l ) 进行描述，越来越多的软件结构采用了u m l 语言 进行描述。 2 3 2软件体系结构设计模式 文献 1 5 j 研究了软件体系结构中一些常用的设计方法，在此基础上总 结了设计中常用软件体系结构的模式。软件体系结构的模式描述了出现在 特定设计语境中的特殊的再现设计问题，并为它的解决方案提供了经过充 分验证的通用图式。解决方案圉式通过描述其组成组件、它们的责任和相 互关系以及它们的协作方式来具体指定。 构成每个模式基础的三部分图式，语境，闯题出现的场景。问题：在 那个语境中出现的再现问题。解决方案：已被证实的问题的解决方案。图 式作为一个整体表示一类规则，用来建立在一个给定语境，这个语境中出 现的一个特定问题以及对这个问题的适当解决方案之间的关系。这个图式 的三个部分是紧密结合的。 模式分为体系结构模式、设计模式和惯用法三类： 1 体系结构模式( a r c h i t e c t u r a l p a t t e r n ) 表示软件系统的基本结构化 组织图式它提供一套预定义的子系统，规定它们的职责，并包 含用于组织它们之间关系的规则和指南。 2 设计模式( d e s i g n p a t t e r n ) 提供一个用于细化软件系统的子系统 或组件，或它们之间关系的图式。它描述通信组件的公共再现结 构，通信组件可以解决特定语境中的一个一般设计问题。 3 惯用法( i d i o m ) 是具体针对一种编程语言的低层模式。惯用法 描述如何使用给定语言的特征来实现组件的特殊方面或它们之间 的关系。 模式之间存在三种关系：细化、变体和组合。这些关系都有助于有效 使用模式。细化支持模式的实现，组合有助于组成复杂的设计结构，变体 有助于在给定设计情形下选择正确模式。 模式为开发具有已定义属性的软件提供了一种有前途的方法。它们把 现有的设计知识文档化，有助于为设计闯题找到适当的解决方案。模式存 在于各种不同的规模和抽象之中，并覆盖软件开发的许多不同的和重要的 里芏墨! 堂坌塑茎堡塑堡垦型一 领域。模式彼此交织一可以用它们来细化其他较大规模的模式，并且可以 将它们组合以解决更复杂的问题。 本论文充分利用了当前设计模式的研究成果对提到的e d s 的结构设计 进行考量和设计。 2 4机器学习对调度适应性的启发 文献 1 6 将机器学习定义为：如果一个计算机程序针对某类任务t 的 用p 衡量的性能根据经验e 来自我完善，那么我们称这个计算机程序在从 经验e 中学刀，针对某类任务t ，他的性能用p 来衡量。例如，对于学习 下西洋跳棋的计算机程序，他可以通过和自己下棋获取经验；他的任务是 参与西洋跳棋对弈；他的性能用他的赢棋能力来衡量。 机器学习这门学科所关注的问题是：计算机程序如何随着经验积累自 动提高性能。近年来，机器学习被成功的应用于很多领域，从检测信用卡 交易欺诈的数据挖掘程序到获取用于阅读兴趣的过滤系统，到能在高速公 路上行驶的汽车。同时，这个学科的基础理论和算法也取得了重大进展。 机器学习从很多学科吸收了成果和概念，包括统计学、人工智能、哲 学、信息论、生物学、认知科学、计算复杂性理论和控制论等。 本论文采用基于实例的学习算法，来对新的类型的任务特性进行学 习。 2 5对本课题的规定 本节根据上述讨论规定本论文的研究课题。 2 5 1 论文解决的问题 分布式计算的发展方向对计算提出了如下的要求： 口 可扩展性需求 里芝墨! 丝塑茎堡塑壅! ! 望 要求能够方便的扩展分布并行系统的性能，同时不对系统的已有功能 和性能造成不良影响。 可扩展性包括如下方面：服务节点的扩展、调度器本身功能的扩展和 被调度服务类型功能的扩展。 口适应性需求 能够根据任务的类型的资源的耗用特性自适应的调整调度策略。 由于现有的调度算法对任务的资源耗用特性学习能力低下，导致基于 任务耗用资源的预测算法调度的性能不够理想，如何通过合适的利用机器 学习算法准确的估计耗用资源的特性是提高分布并行调度算法性能的关 键。比如，视频流或者f t p 服务器的任务特性就比较确定，那么确定了其 任务特性进一步就可以比较准确的预测新任务对资源的需求，从而减少任 务中途迁移的几率。 口 应付急剧增加的调度信息的需求 随计算设备和服务类型的增加，调度信息的类型和数量将出现急剧增 加的趋势。如文献 5 提到，传统的研究仍然以调度算法为主，而对信息 采集的可信度以及采集代价讨论得及其简单，无论多么精致的算法建立在 可信度不高的信息上都是低效率的算法。 这就要求未来的分布并行调度器能够处理这些数量增大和而资源耗用 特性急剧变化的服务类型和不同平台类型的调度信息。 口 安全的计算环境需求 为日益复杂的计算环境提供可扩展的安全机制非常必要。在分布并行 调度的环节提供安全机制，为建立安全的计算环境提供支持。 本文尝试通过改造调度器的软件结构以解决上述问题或者为解决上述 问题提供更好的基础。 可扩展智能分布并行调度模型 2 ，5 2研究方法 本论文尝试从软件体系结构为分布并行调度提高分布并行调度的可扩 展性和白适应提出可行的解决方案。在可扩展分布并行调度器e d s 的过程 中采用现有的软件结构设计模式的研究成果增强调度器的可扩展机制，为 适应性机制和其他特性建立基础。调度器软件体系结构的描述采用o m g 统一建模语言( u m l ) 描述。 第三章调度设计相关问题及解决 3 1分布并行调度功能实现要点 3 1 1对负载衡量方式的改进 分布式并行调度是围绕负载这个核心概念展开的。 负载，即衡量服务节点的负荷，代表了当前节点的繁忙程度。如果以 t 代表节点的最大负载能力，l 代表当前节点的负载。t l 则代表了当前 节点的服务能力。在分布并行系统中，通过将任务从服务能力低的节点迁 移到服务能力较高的节点来提高计算性能。 负载衡量的方式可以从资源可用程度重新考虑，两个方面：其一是任 务对资源的需求，及其特点( 比如快速移动的无线设备) 其二是系统资源 能够提供的资源及其特点。若可用负载( a l ) ，即服务的现有资源( c l ) 和 客户端对资源需求( r l ) ，负载的可用度可如下表示： r = a l 1 0 5 文献 3 ，4 中提到以c p u 的等待队列和内存的使用情况来衡量节点 的负载，即三= f ( c p u ，m e m ) ，该类型负载衡量潜在假设是分布执行的任务 是c p u 集中型的，采用这种策略的分布并行调度有a m o e b a ，而a u t o s e c 的 研究者针对网络服务的分布设计了采用c p u ，内存，磁盘i o 和网络1 0 的综合 衡量方式来衡量节点的负载 1 0 ，从而减小了负载衡量的误差，提高了分 布计算的有效性。 负载信息采集模式，即负载信息采集的具体方法。 不同的采集方法其代价和复杂度是不同的，现有的分布并行系统的负 载信息的采集均采用了调度器主动采集的方式，而提供服务的服务器实际 可以采集到的负载信息被浪费掉了，这部分的信息可以用于描述单个服务 曼芝墨塑丝坌塑茎堑塑堡苎里一 对资源的耗用特性，从而提高对新进入任务资源耗用特性的估计的准确 性。进而提高资源分配的有效性。因此，可以设计两种信息采集模式解决 上述问题： 1 p u s h 模式。由运行的服务器统计其各个任务的资源耗用特性信 息，并将该信息告知调度器：比如，在视频流服务器中加入的任 务流特性的统计功能，即可以准确的估计新的任务对带宽的需 求，从而提高对新的流任务调度的效度； 2 p u l l 模式。由调度器采集系统的宏观的负载信息如c p u 、内存、 磁盘1 0 和网络i o ：这部分采集方式和传统的负载信息采集方式类 似。 利用上述两种方式采集到的负载信息，可以更为准确的估计各个节点 相对于新进入任务的资源需求的特性的负载。根据这个思路，可以对原有 负载估计算法进行改进得到最小可用因子算法。算法的具体实现参考后继 e d s 的实现部分。 3 。1 2调度的基本功能的模块划分 如参考文献 3 ，4 所述，设计分布并行调度器需要实现如下功能： 1 信息采集策略。收集和处理调度相关的信息； 2 迁移策略。确定是否某个节点适合于任务迁移，该策略建立于信 息采集策略采集到的信息的基础上； 3 选择策略。确定被迁移出去的任务：在a m o e b a 的研究者为调度器 设计了两种迁移的任务类型：新到的任务和正在执行的任务，并 指出后一类型的迁移是在对任务耗用资源估计不足的情形下才采 用的迁移方式；如果能够学习新加入任务的耗用资源的特性，就 可以减少后一种迁移的几率； 4 定位策略。确定被迁移的任务需要迁移到那个节点： 从实现角度而言，信息采集策略是分布并行调度器的核心，其他各个 策略是建立在信息采集策略基础上的，同样的负载信息可以为不同的策略 利用来达到平衡各个节点的负载的目的，因此，以信息采集策略为调度器 的核心，其他策略围绕该策略进行扩展可以为调度器的结构的可扩展性提 供坚实的基础。在后面给出对这个问题的更为详细的解决方案的描述。 3 1 3调度可扩展性问题的解决 本文解决的核心问题是通过的分布并行调度的软件结构的提高可扩展 性。典型可扩展性问题分如下几类： 1 可以平滑地扩展分布并行系统的节点( 节点服务能力的扩展，节 点规模的变化) ； 2 可以方便地扩展分布并行系统的服务类型； 3 可以对分布并行调度器本身的功能进行动态升级。 分布并行调度器的软件结构能够容纳上述扩展，使得这些扩展的代价 尽可能的低。 文献 1 5 】提到了两种设计模式可以提高系统设计的灵活性和可扩展 性： 1 微核( m i c r o k e r n e l ) 模式应用于须要能够适应变更系统需求的软件 系统，这种模式把最小功能核心同扩展功能和客户部定制功能分 分离开来独立变化，各个部分通过标准接口交互； 2 代理者( b r o k e r ) 结构模式可以用于构建带有隔离组件的分布式 软件系统，该软件通过远程服务调用进行交互。代理者组件负责 协调通信，诸如转发请求，以及传送结果和异常。 在e d s 的设计中，通过引入代理者( b r o k e r ) 结构模式 1 5 ，可以隔 离分布并行系统中的客户端和服务器，从而使客户端和服务器能够独立的 演化，从而为扩展分布并行调度提供了相当大的灵活性。 而引入微内核( m i c r o k e r n e l ) 模式，可以使调度器本身的可扩展性得到 极大的提高，并为调度器本身功能的动态升级提供了良好的软件结构方面 的支持。e d s 的设计以资源数据库( 参见本章后面叙述) 作为调度器的微 里芏曼! 丝坌塑茎堡：| ! 堡堡翌一 核，将信息采集以及其他部分作为扩展部分，以提高分布并行调度的可扩 展性。 3 2调度器自适应性的实现 自适应性指分布并行调度能够根据计算环境参数以及被调度任务的类 型的变化，自适的调整调度参数，以优化调度的性能。在引入机器学习以 后，调度器可以方便地根据检测的参数的变化自适应的调整调度的参数。 在e d s 调度器设计中，引入了k 邻近算法动态 1 6 地学习新任务的资 源耗用特性，从后面的试验可以发现该算法具备稳定的特性同时能够及时 的反映任务特性的变化，为提高调度器的适应性提供了有效的支持。 3 3对计算安全性的支持 e d s 的解决方法是在调度器中添加授权和认证的安全检验机制，提高 分布计算环境的安全性。 安全性涉及如下方面：服务访问的安全性、功能的扩展安全性： 1 服务访问的安全性，可以通过授权和认证协议实现，在用户请求 服务的报文中加入用户信息用于鉴别用户的合法性； 2 功能的扩展安全性保障，可以通过功能模块中加入开发商的信 息，以鉴别是加入新模块的合法性，从而可以提高恶意破坏的难 度。用户可以根据调度器对外提供的开发接口定制自己的安全检 验机制。 3 4 调度设计的核心概念一资源 3 4 1资源的定义 “资源”即系统中的可参与计算的元素，包含硬件计算资源和软件计 算资源，算法等等。 2 0 - 旦芏墨塑丝坌查茎焦塑墨苎型一 从资源的角度考虑分布并行计算环境中的计算因素，从6 0 年代分布并 行计算研究开始就提出，但引入也对调整设计分布并行调度视角的选择提 供了有益的提示。本文资源含义类似j i n i 中提出的“服务”，但含义更 为广泛。 资源包含如下属性，资源的静态属性，资源的运行时属性和资源的操 作属性： 1 资源的静态属性包含资源名称，资源的最大服务能力，资源的位 置，访问权限等等； 2 资源的运行时属性，包含资源的当前时刻的状态，资源的负载信 息等等； 3 资源的操作属性表示该资源是否可以由调度启动关闭。 资源可以形式化表示如下： 资源= 静态属性，运行时属性，资源的操作属性) 静态属性= 资源编号，资源名称，资源的最大服务能力，资源 的位置，访问权限 运行时属性= ( 状态，负载信息 状态= 启动i 关闭 资源的操作属性= 可操作1 不可操作) 可调度的资源是可以探测其静态和动态属性的资源。在设计和实现的 时候，可以考虑为扩展的资源加入资源属性的提供其资源信息的采集的功 能和接口( 方便的实现负载信息的p u s h 和p u l l 模式) ；在资源进入分布计 算环境后，可以方便的采集资源相关的信息，为调度处理新进入的任务提 供准确的参考。 因此，无论对分布并行系统的扩展( 软件的和硬件的) 都可以考虑为 对计算资源的扩展；这样，可以为开发人员开发可调度的资源和管理人员 对系统的管理统一设计界面和管理界面。 3 4 2 资源数据库 对于如此多的资源相关的信息，用现在的设计中使用的配置文件存储 方式既难于扩展数据的处理方式也不规范；因此，在e d s 的设计引入一个 小型的数据库来存储资源相关的信息：该数据库的设计实现了s q l 9 2 的一 个功能子集数据库本身的处理功能也可以在不影响调度信息的前提下方便 地升级。 同时，引入数据库也可以为系统安全性设计提供了可靠的基层支持， 资源数据库无论从设计策略和软件结构而言都是分布并行调度系统e d s 的 核心。 3 4 3 计算资源的智能管理 在实现了资源的可调度性基础上可以实现资源的智能管理，提高分布 并行系统的可管理性。比如，e d s 的资源管理模块可以根据系统的繁忙程 度启动和关闭相关类型的服务；这样，一方面提高系统的安全性( 当不提 供服务的时候关闭相应的服务和相应端口，提高系统的安全性) ，一方面 减小系统功耗，为系统在某些场合下提供更好的服务。 第四章可扩展调度设计模型e d s 设计 4 0本章组织概述 在上一章的基础上，本章讨论可扩展分布并行调度器e d s ( e x t e n s i b l e d i s t r i b u t e ds c h e d u l e ) 的设计和实现。 本章组织如下： 首先，对分布并行调度e d s 所使用的软件结构模式以及调度器的结构 设计进行简要描述；然后，在上述的基本的设计结构的基础上，设计分布 并行操作系统调度器模型，并给出该设计模型对外提供的开发接口。 本章对e d s 的软件结构的描述采用l m l 统一建模