（计算机应用技术专业论文）容错orb系统中避免组优先级倒置的研究及原型实现.pdf

y 6 9 4 1 9 6 东南大学学位论文 独创性声明及使用授权说明 一学位论文独创性声明 本人声明所呈交的学位沦文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人 已经发表或撰写过的研究成果，也不包含为获得东南大学或其它教育机构的学位或 证书而使用的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示谢意。 签名! 盛鲨 日期：2 0 0 争l 岁0 二关于学位论文使用授权说明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论 文的复印利电了文档，可以采用影印、缩印或其他复制平段保存论文。本人电了文 档的内容利纸质论文的内容相一致。除在保密朗内的保密论文外，允许论文被查阅 和借阅，可以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权东南大学研究生院办理。 签名二墼导师签名嬲日期窒竺鳓 y v o f 东商大学填士学位论文 容错o r b 系统中避免组优先级倒置的研究及原型实现 摘要 分布式系统的实时和容错理论的研究长期以来是基本独立的。实时问题主要关心调度， 即如何设计满足实对性要求( 主要是可预测性) 的调度算法，并分析任务的可调度性；而主 动式容错的核心问题之一是一致性计算，即保证所有参与进程对给定问题都能得到相同的结 果。实时容错系统的理论和实现进展对那些同时要求高可靠性和可预测性的关键性应用领域 有十分重要的意义。与单机上的本地优先级倒置不同，实时优先级机制在主动式容错应用中 会引起组优先级倒置的特殊问题。对此已有理论上的完善解决方案，但还没有系统实现。在 实时容错c o r b a 系统中实现避免组优先级倒置的功能是很有意义的工作。 本论文以中法合作项目“实时和容错c o r b a ”为背景，在详细分析避免组优先级倒置 算法的基础上，详细论述了g f - j o r b u s 系统的分析设计和实现。该系统是第一个实现避免 组优先级倒置的实时容错c o r b a 原型系统。本文的工作分为理论和实现两个方面。 理论方面，本文在第二章研究了避免组优先级倒置的算法：分析了它可能的运行流程， 对算法满足的理论性质进行了补充说明或证明，并详细探讨了在法国i r i s a 的e d e n 系统 的支持下，算法的运行机理和关键步骤的实现策略和理由。第五章对避免组优先级倒置算法 的系统性能与系统参数的关系进行了定性分析和仿真，考察了包括服务器复本数目与通用一 致性框架( g a f ) 的计算速度优先级分配方式的差异，服务器负载变化，各服务器复本处 理速度和与客户方传输延时等因素对系统性能的影响。 实现方面，论文在第三章使用面向对象的思想对g f - j o r b u s 的服务方主要模块和线程 进行了清晰的划分，采用基于事件的体系结构( e v a ) 设计了避免组优先级倒置的核心部分， 并借助u m l 进行系统的整体分析设计。第四章阐述了计算组执行进度( g e p ) 的具体实现， 提出了可以动态配置的o r b 结构，讨论了不使用截获机制实现容错的方法，并实现了简单 的实时o r b 扩展模块。 【关键词】实时容镨组优先级倒置g a f一致性计算c o r b a 东南大学硕士学位论文窖错o r b 系统中避免组优先级倒置的研究及胤型实现 a b s t r a c t r e a l 。t i m ea n df a u l t - t o l e r a n tt h e o r i e si nd i s t r i b u t e ds y s t e m sh a v eb e e ni n d e p e n d e n tf o rl o n g r e a l t i m er e s e a r c hf o c u s e sm a i n l yo n p r i o r i t y b a s e dt a s ks c h e d u l i n gi n c l u d i n gs c h e d u l i n gm o d e l s ， a l g o r i t h m sa n ds c h e d u l a b i l i t ya n a l y s i s ，w h i l ea c t i v er e p l i c a t e df a u l t - t o l e r a n ts y s t e m sh a v et or e l y o nc o n s e n s u st h a tg u a r a n t e e su n a n i m o u sr e s u l t sa m o n ga l lr e p l i c a s p r a c t i c ea n dt h e o r yi nf a u l t - t o l e r a n tr e a l t i m es y s t e m sa r eo fg r e a ts i g n i f i c a n c ei nc r i t i c a la p p l i c a t i o n st h a tr e q u i r eb o t hh i g i l r e l i a b i l i t ya n dp r e d i c t a b i l i t y ，i ns u c hs y s t e m s ，h o w e v er am u c h - c o m p l i c a t a dn e wp r o b l e mn a m e d g r o u pp r i o r i t yi n v e r s i o n ”( g p i ) a r i s e st h a td i f f e r sf r o m l o c a l p r i o r i t y i n v e r s i o no nas i n g l e m a c h i n e t h ep r o b l e mh a sb e e ns o l v e db yap r o p o s a lb a s e do nt h ec o n c e p to fg r o u pe x e c u t i o n p r o g r e s s ( g e p ) ，b u tp r a c t i c a ls y s t e m si n t e g r a t e dw i t ht h i sp r o p o s a lh a v ey e tt ob ed e v e l o p e d a f f i l i a t e dw i t ht h er e a l - t i m ea n df a u l t - t o l e r a n tc o r b a p r o j e c ti nl a m a ，t h i st h e s i sg i v e s d e t a i l e da n a l y s i so nt h ea l g o r i t h ms o l v i n gt h eg r o u p p r i o r i t yi n v e r s i o np r o b l e mb e f o r ee l a b o r a t i n g t h ed e s i g na n di m p l e m e n t a t i o no fg f j o r b u s - - - t h ef i r s tf a u l t - t o l e r a n tr e a l - t i m ec o r b a s y s t e m t h a te l i m i n a t e sg r o u pp r i o r i v yi n v e r s i o n t h em a i nw o r ko f t h i st h e s i sf a i l si n t ot w op a r t s ： w i t h r e g a r d t ot h e o r e t i c a lw o r k ，c h a p t e r2a n a l y s e st h ea l g o r i t h mb ye n u m e r a t i n gi t s r u n n i n g c a s e s ，c l a d 母i n ga n dp r o v i n gi t sp r o p e r t i e s ，a n dp r o b i n gi n t om e c h a n i s m sa n ds t r a t e g i e sn e e d e dt o d e p l o yt h ea l g o r i t h mo f ft h ee d e ns y s t e mb yi r i s a ，f r a n c e c h a p t e r5a d d r e s s e st h ee f f e c to f t h e a l g o r i t h m sp a r a m e t e r so ni t sp e r f o r m a n c eb yq u a l i t a t i v ea n a l y s i sa n ds i m u l a t i o n t h ep a r a m e t e r s i n c l u d et h es p e e do fg e n e r a la g r e e m e n tf r a m e w o r k ( g a f ) a f f e c t e db yt h en u m b e ro f r e p l i c a s ， d i f f e r e n tw a y st oa s s i g np r i o r i t i e st ot a s k s ，t h ew o r k l o a do fs e r v e rr e p l i c a s ，d i f f e r e n ts p e e do ft h e p r o c e s s o r so n t h e r e p l i c a sa n dt h et r a n s m i s s i o nd e l a ya m o n g t h ec l i e n ta n ds e r v e rr e p l i c a s ， t h er e s to ft h et h e s i si n t r o d u c e st h ed e s i g na n di m p l e m e n t a t i o no fg f j o r b u s c h a p t e r3 p r o p o s e sp a r t i t i o no f m o d u l e s a n dt h r e a d so nt h es e r v e rs i d ea n dd e s i g n st h ec o r eo f t h es y s t e mb y e v e n t - b a s e da r c h i t e c t u r ef e v a ) t oa v o i dg p i t h ec h a p t e ra l s oc a r r i e so u tt h es y s t e ma n a l y s i sa n d d e s i g nb yu m l i nc h a p t e r4 ，s e v e r a la s p e c t so fi m p l e m e n t a t i o na r ed i s c u s s e d ，i n c l u d i n gt h e c o m p u t i n go f g e pi ne d e n c o n f i g u r a b l eo r ba r c h i t e c t u r e a n dc o m b i n a t i o nw i t he d e nn o tb y p o r t a b l ei n t e r c e p t o r sa sw e l la ss i m p l er e a l t i m e0 r be x t e n s i o n s f k e y w o r d s lf a u l t - t o l e r a n t ，r e a l t i m e ，g r o u pp r i o r i t y i n v e r s i o n ( g p i ) ，g e n e r a la g r e e m e n t f r a m e w o r k ( g a f ) ，c o n s e n s u s ，c o r b a 4 东南大学硕上学位论义 容错o r b 系统中避免组优先级倒置的研究及壕型实现 1 。1c o r b a 技术简介 第一章引言 c o r b a ( c o m m o n o b j e c tr e q u e s tb r o k e r a r c h i t e c t u r e ) 技术是当前最具有影响力的分布 对象计算技术。自从o m g ( o b j e c l ：m a n a g e m e n tg r o u p ) 组织于1 9 8 9 年成立以来，就一直致 力于制订、采纳和吸收基于面向对象思想的、异构分布环境下应用的开发和配置的技术和标 准。根据不断发展的用户需求已经发布了c o r b a 规范3 0 2 1 2 1 版本。随着技术和产品的推 广和成熟，c o r b a 已经在制造、电信、金融、电子商务、军事、航空航天、教育和交通运 输等应用领域的软件系统中得到的广泛的运用。单一的o r b 系统结构如图1 1 口1 所示。 c o r b a 技术之所以能够得到如此广泛的应用在于它具有以下的一些特点1 2 0 i ； 操作平台无关性：可以使基于c o r b a 技术开发的应用运行于不同的操作系统和网络环 境下：客户和服务器可以位于不同的平台上。 编程语言无关性：可以方便开发者采用多种编程语言编写应用系统；客户和服务器可以 使用不同的编程语言开发。 基于面向对象思想：c o r b a 技术就秉承了面向对象技术的所有特点，使基于c o r b a 技 术的应用系统具有封装性和继承性。因此，在统一的接口描述语言o m gi d l 的支持下， c o r b a 应用系统的客户端和服务器端可以独立开发：而且系统的扩展和升级是相对方 便和简单的。 t x x x x x 譬m i n t e r f a c ei d e n t i c a lf o ra l lo r bi m p l e m e n t a t i o n s tu p c a i r i t e 咖 露翰2 物t h e r em a yb em u l t i p l eo b j e c ta d a p t e r s 。 ! ! 竺t h e r e e r es t u b sa n d k e n f o r e h o b j e 。t t y p 。n o r m 引l i i n t e 恤。 匕= = = o r b d e p e n d e n t i n t e r f a c e 1 1 ，1 实时c o r b a 图1 1 单o r b 系统的体系结构 在c o r b a 技术不断拓展应用范围的过程中，制造、军事、电信以及航空航天等领域的 某些应用需要c o r b a 系统支持客户服务器交互的严格时间限制需求。这样应用系统一般称 为分布式实时系统。然而大量的研究和实践表明，酱通c o r b a 规范咀及相应的c o r b a 产品 并不适用于支持分布式实时系统的开发和运行。因此，c o r b a 技术本身需要进行拓展或改 进以支持实时的需求 4 1 。 东南大学硕士学位论文窖错o r b 系统中避免组优先级倒置的研究及原型实现 实际上，实时处理和实时系统的研究工作已经具有了相当长的历史。随着实时应用需求 逐步向着大型化动态化以及分布处理方向发展，实时处理和系统己渗透到了社会生活的各 个领域并发挥了重要的作用p l 。穗应的实时任务调度理论、实对操作系统、实时通信协议的 研究不断得到发展，形成了大量有价值的结论、算法和工具。这些成果为c o r b a 技术向实 时领域的发展奠定了坚实的基础。 将时阀因素引入c o r b a 技术后，可以充分发挥c o r b a 在分布软件开发和集成方面的独 特优势，提高分布式实时系统软件的质量，降低开发成本和周期，使实时c o r b a 技术能够 成为开发和运行分枢式实时系统的支撑平台，从而使得异构分布环境下实时软件系统具有可 重用、可移植和可互操作等特性。 对于一般的实时系统来说它具备以下几个重要的特性l o j ： 及时性( t i m e l i n e s s 实对系统所产生的结果在时间上有羲严格的要求，只有符合时 间约柬的结果才是正确的任务必须在这个截止期之内完成。 同时性( s i m u l t a n e i t y ) 一般来说，一个实时系统常常有多个输入源因此，这就要求 系统具有并行缝理的能力，以便能同时处理多个实时任务。 可预测性( p r e d i c t a b i l i t y ) 实时系统的实际行为必须在一定的限度内，而这个限度是可 以从系统的定义而获得的。这意味着系统的处理必须全部是可预测的即使最坏的条件 下也要严格遵守时闻约寒。在出现逶度过载的时候，系统必须以一种可预测的方式来降 级它的性能。实时系统性能的主要评价尺度是系统行为在时间上的可预测性的强弱。 可靠性( r e t i a b i l i t y ) 一方面是指系统的正确性，即系统所产生的结果的值和时间都是 正确的：另一方面是指系统的健壮性，即系统虽然出现了错误或外部环境与定义的不符 合，但系统仍然可以处于可预测状态。 根据o m g 组织会员对实时o r b 系统功能和体系结构的需求意见来看，除了需要支持具 有上述实时任务特性的实时系统的开发和运行之外，实时c o r b a 系统还应该具有较高的性 能，能够有效地控制资源并具有灵活性和可扩展性。实时c o r b a 规范较为著名的实现模型 包括w 缸h i n g c o n 大学的1 i a 0 和东南大学的r t o r b u s 系统 i g t 等等。o m g 组织为了促进实时 c o r b a 技术的发展以及实时c o r b a 规范的制订成立了实时特别兴趣工作组( r t s i g ) 其目的就是为了制订实时c o r b a 规范i 】i ，并最终使所制订的实时c o r b a 规范成为c o r b a 3 0 标准族的一个组成部分。 1 1 2 容错c o r b a o m g 成员和c o f u 3 a 使用者开发的很多不同应用系统都需要采用容错机制。这些系统应 用包括关键性的系统，如航空管制系统、国防预警系统、医疗系统和报警控制系统，还有一 些嵌入式系统如航空仪器、制造控制系统等。此外还包括通讯系统，妇电信和霹络系统，以 及企业级应用，如金融和物品供应链应用。o m g 组织正是看到这些系统的容错需求提出 了解决容错系统的标准化方案。 o m g 在c o r b a2 5 1 ”规范中首次定义了一个容错c o r b a 的规范。这个规范为了不同厂 商提供的容错系统之间能够互操作而提供了容错功能标准的接口和框架。这个规范的只是一 个折中方案，还有很多不完善的地方。其目标是为容错c o r b a 系统提供一个标准，为需要 高可靠性的应用提供统一接口。 规范的核心基于复s u g q 错( r e p l i c a t i o n ) 原理，即利用多个复制对象( o b j e c tr e p l i c a ) 来实现系统的高可靠性。部分复制对象出现错误，其他的则仍然可以正常运行来宠成客户请 求。这个策略保证系统配置有很强的可伸缩性，可以选择复制对象的数量，分配到不同的主 机。c o k b a 的客户端需要能够将调用请求发送剑所有的复制对象而无需知道它”l 的位置。 规范还定义了支持大量的其他容绩技术的接口，包括请求重发，重定向到备用服务器等 ”j 。规范允许用户定义每个复制对象，或者对象绍的容错特性允许容镨底层系统控制应用 6 东南= 学颅士学位论文窖错o r b 系统中避免纰优先级倒置的研究及原型实现 对象的复制，还允许应用直接控制应用对象的复制，为用户提供更大的灵活性。它允许容错 系统底层控制并保证复制对象间的一致性，同时也支持应用程序提供用户所需要的各种层次 上的一致性。这个规范的特性还包括为复制对象提供对错误检测，通知和分析的支持，提供 接口为容错底层系统来提供自动的检测点，登录和错误恢复。总而言之，这个规范的目标是 在对应用系统做最少的修改的隋况下提供透明的复制容错功能。 窖错c o r b a 规范与以往的c o r b a 规范一样，只提供系统的接口定义，并没有规定使用 何种底层机制去实现容错服务功能。 1 1 3 实时和容错c o r b a 的主要机制 实时c o r b a 定义了通用的、独立于具体平台的优先级机制称为“实时c o r b a 优先级”。 此概念的引入是为了克服不同操作系统自身提供的优先级机制之间的不一致性，使得实时 c o r b a 应用可以在不同优先级机制的平台上以统一的方式进行基于优先级的调用。为此， 实时c o r b a 应用总应该使用c o r b a 优先级来表达在系统中的优先级别即使所有参与节点 自身的优先级机制相同或者使用服务器方定义的优先级模型。 实时c o r b a 的目标之一就是限制并尽可能减少调用过程中出现的优先级倒置现象。为 此实时c o r b a 使用一种机制，由客户方定义调用的优先级，将优先级传给服务器方要求 服务器根据此优先级来进行向上的调用。而在有些情况下设定服务器的优先级并让这些服 务器根据被设定的优先级来处理调用就足够了。所以实时c o r b a 支持两种优先级模式，客 户方传播的优先级和服务方宣布的优先级l 】l 。前者是指服务器方兑现客户方所设置的 c o r b a 调用优先级：调用的优先级传播到服务器方并被服务方o r b 映射到系统内部优先级， 非实时c o r b a 客户端发送来的调用则被服务器指定一个优先级再进行处理。后者是指服务 方收到调用后为其分配一个c o r b a 优先级再进行处理，这种模式可以用在以一个c o r b a 调 用开始的新活动上，为新旧活动设置一个分界标志。 很多实时应用系统的执行平台都使用类似实时c o r b a 优先级的机制。在这类系统中， 检测并限制优先级倒置的影响是获得可预测性的关键。所谓优先级倒置，是指服务方正在执 行一个较低优先级的任务，此时已有一个较高优先级的任务已处于待处理状态，如果不进行 任何处理，则高优先级任务被低优先级任务延误。这里的任务可以指进程，线程事务或者 对客户请求的处理过程等。如果低优先级任务的所需执行时间远大于高优先级任务，则优先 级倒置应该尽可能完全避免。这就要求我们能够检测出优先级倒置并加以消除。 关于容错问题，由于一个系统无法有效地对自身出现的错误检查和修复，因此需要一个 或多个冗余的复制系统来代替或者帮助出错的系统进行未完成的工作。容错c o r b a 规范以 复制容错为主要目标来定义的，是利用多个对象，进程或系统提高可靠性。复制容错在应用 中一般有两类不同的方法如图1 2 r q 所示。 被动复制( 冷复制或者温复制) p l 】在没有出错的情况下，对象组中只有一个成员( 主 成员) 执行调用请求。主成员的状态和请求调用序列被周期性地记录在日志中。出现错 误时，某个备份成员被指定为新的主成员，用旧的主成员的在日志中记录状态来恢复新 主成员并将此状态后的请求调用序列发给新主成员。 主动复制对象组的各成员独立地执行每个请求调用它们执行调用的序列相同，保持 完全一致的状态。当一个成员出错时，应用程序可以继续使用其他成员返回的结果，不 必等待错误的检测和恢复。尽管对象组中每个成员都收到每一个请求并发送每一个应 答消息处理机制负责检测并消除重复的请求或应答消息。 主动复制容错比起被动方式有若干优点f 7 】：前者避免了从错误恢复的过程，节省时间； 即使没有出任何错误的时候，客户方仍然可以获得最早返回的应答，以提高系统性能：实现 备份冗余的程度较为有限。因此，在实现容错实时系统中，主动复制方式比被动复制方式常 东南大学烦士学位论史窖错o r b 系统中避免组优先级倒置的研究及原型实现 用”q p “。在这类系统中，服务方应用程序在足够多的处理器上分都有复本而这些处理器 出错是相互独立的事件。各个复本执行全序( t o t a lo r d e r ) 协议来保证客户方发出的请求被 所有工作的服务器复本以相同的顺序处理。假设每个复本的执行行为是确定的( 无随机性因 素) ，则所有工作的服务器复本都会经历相同的状态转换并对任何一个给定的请求都发送相 同的应答给客户方。在客户方需要执行一个验证程序，它负责收集并过滤应答。如果服务器 复本没有恶意行为，则验证程序将第一个返回的应答给客户方：其他情况下可能需要更复杂 的验证程序( 例如多数选举) 以屏蔽出错的服务器复本的应答。 h o t r e p l i c a t i o n w a r m r e p l i c a t i o n c o l dr e p l i c a t i o n 1 。2 问题的提出及研究现状 图1 - 2 复制容锴模式 1 21 实时容错系统的基本问题 主动复制方式的容错系统的核心就是保证各个服务器复本收到相同请求序列的全序协 议。如果还要考虑优先级倒置问题，则全序协议在保证各服务器复本收到一致的请求之外还 必须保证这样的请求序列不会引起优先级倒置。然而由于各服务器复本接收输入请求、准备 等待处理以及实际的处理过程之间没有同步机划，可能有的服务器复本上出现了优先级倒置 而另一些上则没有出现。我们可以直观地认为，如果某个高优先级任务在较多服务器复本上 出现了优先级倒置，这时此任务就处于“组优先级倒景”状态。 实时任务最关心的问题就是可预测性，即任务的完成时间是可以预先估计的。然而组优 先级倒置会使得容错系统中的实时任务的可预测性被破坏。举例来说假设主动式容错系统 中有8 个服务器复本，客户方验证程序需要收集3 个服务器复本的应答并从中选取一个，而 请求任务r 在执行过程中曾经处于组优先级倒置状态，也就是r 在5 个以上( 8 - 3 = 5 ，不包 括5 ) 服务器复本上出现了优先级倒置，使得r 在这些服务器上被延误的时间无法估计。显 然验证程序收集3 个应答中至少有一个来自那些让r 优先级倒置的服务器。由于必须等待 3 个应答都到达后才能从中选择，所以客户方收到的最终应答也被延迟，造成可预测性被破 坏。可见，主动复制式的实时容错系统需要解决组优先级倒置的基本问题才能保证实时任务 的可预测性而可预测性又是实时应用最重要的要求。 本文实现的避免组优先级倒置的实时容错系统基于这样的假设”j ：1 ) 服务器采用主动 复制容错方式；2 ) 客户方发出的请求必须根据优先级被服务器进行处理：3 ) 各服务器复本 的执行没有同步机制，特别是没有任何锁定步进( 1 0 c k - s t e p ) 的操作，各复本的本地时钟之 间也没有紧密的同步。这种系统的典型例子就是实时容错( 主动备份) c o r b a 系统，其中 应用程序通过一组服务对象复本以及客户方传播的优先级方式来实现。 东南人学顺上学位论文 容错o r b 系统中避免组优先级倒置的研究及原型实现 1 2 2 问题的研究现状 人们已经研究设计了若干种全序协议，其中只有三种是考虑请求任务的优先级的，其他 全序协议所关注的问题与【7 】更加不同。换言之，这方面的工作还非常少。 n a k a m u r a 和t a k i z a w a 8 j 设计一种在不出错的环境中运行的基于优先级的全序协议( 参 与协议的进程不会出错) 。他们区分了协议数据单元( p d u ) 的优先级，只是根据p d u 的 优先级以及到达接收者的时间将p d u 进行重新排序井保证排序结果一致。借助为p d u 本身 进行编号，传输机制通过应答和重传来保证各接受者收到相同的p d u 序列。由于没有处理 器执行p d u 这样的概念，该研究中没有出现和优先级倒置相关的问题，和我们关心的通过 避免优先级倒置来保证任务执行时问的可预测性更加无关。 【9 】和 1 0 1 考虑了采用进程复本来容错的情形。 9 的方案是，任何一个服务器复本处理任 何一个请求都是一次性的，各个复本上等待处理的请求集合是不同的。每当服务器复本需要 处理一个请求时所有复本执行一致性协议，协商出相同的等待处理请求集合，然后各复本 从中选取优先级最高的来处理。要确定下一个提交处理的请求，需要再次执行一致性协议。 我们知道，当某个服务器复本上发现了优先级倒置就需要重新调整请求顺序来避免倒置，为 此需要一致性协议来保证各复本请求顺序相同；而【9 】是在任何时候都需要执行一次一致性 协议来得到下一个提交处理的请求。 【l o 】比【9 】有所改进，不需要每次处理请求前执行一致性协议。每当新的请求到达服务器 复本，调度算法比较该请求和本地等待处理请求的优先级：如果前者小于所有的后者就将新 请求放在队列尾部，否则就需要执行一致性协议使得所有复本将新请求插剑队列的相同位置 上。在一致性协议执行中，处理器可以处理优先级高于上述新请求的任务，但是不能处理低 于新请求的任务，以保证新插入的请求不会处于优先级倒置状态。所有服务器复本的执行请 求顺序都和最快的服务器保持一致，不需要卷回。 【9 】和f l o 】都认为，任何服务器复本处理过的请求都无需卷回，一个请求会而且只会被选 中处理一次，在运行期间不能被其他请求抢占。换言之，一个请求一旦被选中处理，则永远 不会被再次调度。这种方式要求服务器复本之间保持高度的同步，为此可能需要阻塞部分服 务器上的处理过程来避免优先级倒置。这两种方案没有考虑避免组优先级倒置，其中【9 】不 适应于通用的客户，服务器模型，单个服务器复本崩溃可能引起客户方收到不一致的应答。 对于标准的客户服务器模型的主动式复制容错实时系统，上述研究都还没有提出保证 基于优先级的实时任务的可预测性的方案。文献【7 首先解决了这个问题。此方案说明，即 使在分部异步环境下只要有足够长的“理想处理时段”，实时容错系统就可以达到可预测 性，并且任何调度的效果也可以预测。如果任务是可预测的，则其结果和响应时间在执行之 前即可知道。在异步系统中。只要避免了组优先级倒置，并且请求任务到达服务器的时间间 隔规律已知，即可保证可预测的运行过程。文献 3 2 】 3 3 论述的实时容错系统是基于同步系 统的，但是同步系统必须依赖于系统内各种时间参数存在上界，并需要知道这些上界值( 例 如消息传输的延迟以及处理任务的速度等等) 。依赖于严格的时间假设是不安全的，特别是 在可能出现处理错误的系统中( 例如网络拥塞) 。这类错误也许并不常见，但是足以使多数 的同步协议不能正常工作。从现实情况出发， 7 假设系统交替处于“好”和“坏”的时段。 在好时段中，系统的行为和同步系统一样：在坏时段中，系统是异步的。当然，好时段的长 度应该大于坏时段，而可预测性分析只是在好时段中有效。 为了保证可预测性，【7 】进一步假设，系统处于“理想处理时段”的时间足够长，在此 期间同定的大多数服务器没有出错，而且相互及时地交互信息：此外，连续的请求调用之间 有最小的时间间隔，这样保证高优先级任务不会过下频繁地到达服务器而无限制地阻塞低优 先级任务。本论文遵循【7 】的术语使j _ = | “请求调度协议”这个术语指代考虑请求的优先级 并能避免组优先级倒管的全序协议。 9 东南大学硕士学位论立：容错o r b 系统中避免组优先级倒置的研究及j 泉型实现 t 3 论文研究主要内容 1 3 1 研究的意义和内容 实时和容错c o r b a 技术和相关理论研究长期以来是两个基本独立的部分。实时问题主 要关心调度，即如何根据待处理任务集的特点和调度约束设计出尽可自e 满足实时性要求( 主 要是可预测性) 的调度算法，并分析任务的可调度性”。而主动式容错的核心问题之一是 一致性计算，即保证所有参与进程对某个问题都能得到相同结果，例如关于参与者集合的构 成或客户方发来的请求序列等。在c o r b a 规范口1 中包含了容错c o r b a ，而实时c o r b a 则成为独立的规范。这两部分规范内容基本上没有涉及共同的内容。 实时和主动式容错结台后，必须首先保证服务器复本间处理请求顺序保持一致性，同时 保证基于优先级的实时任务的满足可预测性。然而由于各复本服务器的处理速度不同，客户 端到复本的不同传输延时等等因素，想要保证不出现组优先级倒置是困难的，但这又是实时 容错系统必须解决的问题。实时容错系统的理论和实现进展对那些同时要求高可靠性和可预 测性的关键性应用领域有十分重要的意义。 在理论上本文分析了 7 】的调度算法的各种执行流程案例，对g e p 满足的性质和算法 不可能停滞等性质进行了证明，重点研究了调度模块和一致性计算模块之间的提交决定原 语在f t - j o r b u s 和e d e n 容错系统中的实现模型。这些内容对算法详细执行过程和正确性 有效性做了补充说明和扩展，并对两个系统相结合的关键技术提出了理论方案。文章还通过 定性分析和仿真相结合的办法分析了算法的系统参数对算法性能的影响，包括服务器复本数 目与通用一致性框架( g a f ) 的计算速度，优先级分配方式的差异，服务器负载变化，备服 务器复本处理速度和与客户方传输延时等因素对系统性能的影响。这部分工作指出了请求响 应时间改变的关键因素，提出在可能的条件下如何改善系统参数以改进性能，对于系统运行 效率有一定指导意义。 本文基于f t j o r b u s 和e d e n 实现了一个实时容错j a v ao r b 原型系统g f - j o r b u s 。 根据现有的信息，g f j o r b u s 是第一个解决组优先级倒置问题的实时容错j a v ao r b 系统。 这个原型系统豹实现为理论方案向实现系统靠近时出现的主要难点和关键工作提出了一套 解决方案，并积累了一定有效经验。例如如何根据g a f 的实现系统e d e n 来实现提交决定 过程，如何确定服务方各层次模块之间的结构和交互，如何利用事件框架设计实时容错系统 核心，如何配置轻量级o r b 并保证服务方多线程高效运行等等。原型系统本身可以在可靠 性和性能要求不太高的简单的容错应用中保证实时任务可预测一| 生。 1 3 2 论文的章节安排 本论文共分六章，本章主要介绍实时和容错c o r b a 的概念和实现机制，实时和容错结 合产生的问题以及问题的研究情况和解决方案简介。 第二章介绍容错理论和e d e n 系统运行机制，对避免组优先级倒置算法进行了介绍和 进一步分析，并研究了算法如何在e d e n 中实现。 第三章提出g f - j o r b u s 系统的设计原则和目标使用e v a 框架和u m l 建模方法对 系统进行详细的分析和设计。 第四章介绍系统实现，包括修改调整e d e n 计算模块，o r b 系统的结构和实时核心。 第五章通过定性分析和仿真结合研究了避免绢优先级算法的系统参数对性能的影响。 第六章总结了论文的主要工作并对今后一r 作做了展望。 o 东南大学硕士学位论文 容错o r b 系统中避免纰优先级倒置的研究及原型实现 第二章避免组优先级倒置算法理论分析 2 1 容错协议和e d e n 系统 2 1 1 一致性问题概述 一致性( c o n s e n s u s ) 是容错分布式系统的基本问题，其定义是【1 4 i ：系统由多个进程参 与，相互之间以远程消息交互，每个进程向其他进程提交一个初始值，尽管有少数进程可能 崩溃，多数永不会崩溃的进程最终必须对结果值达成一致，这个结果值来自于某一个提交值。 一致性问题必须满足中止性( 每个永不会崩溃的进程最终会决定出某个值) 一致性( 任何两 个进程决定值都相同) 和有效性( 如果某个进程决定值是v 则v 必须是某个进程的提交值) 。 在异步分布式系统中。只要有一个进程会崩溃这个问题看似简单的问题就没有办法保 证可以解决，这称为f i s c h e r - l y n c h - p a t e r s o n ( f l p ) 不可能性”“。c h a n d r a 和t o u e g 进一步做出 了开创性的重要研究结果。他们根据检测进程是否崩溃的完整性和准确性，提出了如表2 - 1 所示的8 类错误检测器( f a i l u r ed e t e c t o r ) i 。 表2 1f a i l u r ed e t e c t o r 的分类 c o m p l e t e n e s sa c c u r a q s t r o n g w e a k e v e n t u a l l ys t r o n ge v e n t u a l l yw e a k s t r o n g p e r f e c t s t r o n ge v e n t u a | | yp e r f e c te v e n t u a l l ys t r o n g o pos w e a k d w e a k od e v e n t u a l | yw e a k w ow 强完整性( s t r o n g c o m p l e t e n e s s ) 指：最终每个崩渍的进程都被每个永不崩溃的进程 一直怀疑为崩溃。最终弱准确性( e v e n t u a l l yw e a k a c c u r a c y ) 指：存在某个时刻，此后某些 永不崩溃的进程将一直不会被怀疑为崩溃。这两种特性组合得到的f a i l u r ed e t e c t o r 称为s ， 是可实现的解决c o n s e n s u s 问题的昂弱条件。 c h a n d r a - t o u e g 一致性协议基于“轮流协调者”机制，每个进程异步地参与到连续进展 的各轮工作中每一轮有一个预先确定的进程作为协调者。由于最终弱准确性。必定存在某 一轮，其协调者悬终永远不会被怀疑。每一个进程管理一个本地变量代表其对最终决定值的 当前估计，此估计值开始是本进程上层服务提交的值。假设系统中有多半的进程永远不会崩 溃而消息不会丢失( 但延时不限) 。每轮被分为四个阶段，所有消息来源于而且也发向 协调者，而且每一个进程在任何时刻都只参与某一轮的活动。文献 1 4 】提出了一种基于“滑 动窗口”机制的新思路，将其运用到基于轮次的一致性协议中。滑动窗口目的在于在异步和 消息丢失的情况下仍然可以设计出有效的消息交换。对于基于轮次的协议，这个方法允许每 个进程同时参与到若干连续的轮次中。具体而言，一个正在执行第r 轮的进程，也在同时执 行并管理第r - ( n 1 ) 到第p 1 轮。这种机制使得任何一个进程每n 轮只需要和其他进程紧密同步 一次，其他时候仍然是和其他进程保持异步，独立地参与到若干连续的轮次中。 2 1 2e d e n 系统简介 e d e n l 是法国i r i s a 设计用来在异步分布式环境中进行一致性计算的通用系统，是本 文研究实现的系统所依靠的平台有必要对其f 作机理加以较为详细的介绍。 东南大学硕士学位论文 容错o r b 系统中避免组优先级剧置的研究及原型实现 2 1 2 1g a f 的概念 e d e n 假设参与计算的各个进程没有共享内存或者全局时钟只是通过网络信道交换信 息，消息的延时没有上限，对处理速度也没有任何假设。它提供了很巧妙的通用一致性算法 框架称为g a f ( g e n e r a l a g r e e m e n tf r a m e w o r k ) 1 5 1 对于某个具体的一致性问题，只需要 确定5 个参数，即可使用g a f 加以解决。表2 2 给出了这些参数 表2 2g a f 的5 个可变参数 参数描述 g e t 函数获得进程提交的初始估计值 ，l bs p i f f ( j i u l ，us 。) ( j k ul k us k ) ：于函数定义输出的j 和l 分别是所有 收集到的j 和l 。的并集，而输出的s 是所有收集到的s i 的交集：a c c e p t a b l e ( v ) 铂ei f fv o ；e x e c u s e d ( p i ) - - t r u ei f fp j s 。当协调者已经收集到大多数估计值而且所有未被怀疑 的进程都提交了估计值之后，矿函数被调用。 2 1 2 2e d e n 的组成部分 e d e n 系统没有公开详细文档和源码，本文在这里参考部分文献【”l 川概括地描述 其框架结构和各主要模块的功能。 原子广播服务模块( a t o m i c b r o a d c a s t ) 客户请求发往服务器端，到达某个服务器复本的e d e n 模块。各个复本收到的请求顺序 可能不同，所以需要一致性计算得到全序结果。每个服务器复本维护一个集合，其中保存了 收到但尚未被一致性计算的请求标识。当此集合非空而且上一轮一致性计算结束时，原子广 播服务就启动新一轮计算。计算的结果是请求标识的一个集合，其中包含来自于某些复本进 程提交的值。集合中的请求标识按一定顺序输出到e d e n 外部模块延续了前面各次结果所 得的请求标识序列。外部模块收到新的结果就从未排序的请求集合中将新结果包含的请求标 识删除。如此反复，e d e n 外部模块就可以输出缆一的全序请求序列。 组成员服务模块( g r o u p