（计算机科学与技术专业论文）多线程复制系统的确定性调度框架mdsf的研究与实现.pdf

北京邮电大学硕士研究生学位论文多线程复制系统的确定性调度框架m d s f 的研究与实现 多线程复制系统的确定性调度框架i i d s f 的研究与实现 摘要 复制是分布式系统中容错的一种重要方法。多线程复制能够很 好的利用多核c p u 、多c p u 资源，但也面临着如何保证确定性的问 题。现有的几种多线程调度算法都在一定程度上支持多线程运行， 但都采取了保守的方式来避免多线程所带来的不确定性，从而影响 了多线程同步性的提高。 本文在分析现有几种多线程调度算法之后，基于m a t 算法提出 改进算法一a m a t 算法，该算法需要根据多线程运行期间提供的同 步操作信息来对多线程进行调度。本文提出代码分析、转换的方式 来达到这一目的。同时，代码分析、转换还能够完成对同步语句的 截获，从而透明地完成非复制代码到复制代码的转换。这种方法可 以避免修改底层操作系统、虚拟机所带来的复杂性，也不要求编程 人员手动修改代码。 本文提出一种多线程复制系统的确定性调度框架枷s f ，由两 大部分组成：一个是在预编译阶段的代码分析模块和代码转换模块， 另一个是运行时的线程调度模块。前者能够对多线程程序的源代码 进行分析，并且根据分析结果修改源代码。修改过的源代码在编译 之后部署到运行环境中，并与实现了a m a t 算法的调度模块进行交 互，调度模块会对多线程进行统一调度。经测试证明，该调度框架 支持现有非复制代码的重用，并能实现多线程的高效调度。 关键词：多线程，复制，确定性，静态分析，代码转换，m d s f 北京邮电大学硕士研究生学位论文 多线程复制系统的确定性调度框架m d s f 的研究与实现 r e s e a r c ha n dd 仰l e n 三n t a t i o no f 卫江d s f a d e t e r m d s t i cs c h e d u l i n gf r a m 匝w o r ko f 【i t i t h r e a d i n gr e p l i c a r i o ns y s t e m a b s t r a c t r e p l i c a t i o ni sa ni m p o r t a n ta p p r o a c hi nf a u l t t o l e r a n td i s t r i b u t e d s y s t e m s m u l t i t h r e a d i n gr e p l i c a t i o nm a k e sg o o du s eo f m u l t i c o r ec p u ， m u l t i c p ur e s o u r c e s ，b u ta l s of a c e st h ep r o b l e mo fh o wt oe n s u r e d e t e r m i n i s m a t p r e s e n ts e v e r a lm u l t i t h r e a d i n gs c h e d u l i n ga l g o r i t h m st o s o m ee x t e n ts u p p o r tm u l t i t h r e a d e do p e r a t i o n ，b u tt h e ya l la d o p ta c o n s e r v a t i v em e t h o dt oa v o i dt h en o n d e t e r m i n i s mb r o u g h tf r o m m u l t i t h r e a d i n g ，r e s u l t i n gi nab a de f f e c tu p o nc o n c u r r e n c yo f m u l t i t h r e a d i n g h a v i n ga n a l y z i n gt h ee x i s t i n gm u l t i t h r e a d i n gs c h e d u l i n ga l g o r i t h m s ， t h i sp a p e rp r o p o s e sa na d v a n c e da l g o r i t h mb a s e do nm a ta l g o r i t h m t h ef u t u r ek n o w l e d g eo fs y n c h r o n i z e da c t i o n so ft h em u l t i t h r e a d si nt h e r u nt i m ei sam u s tt ot h ea d v a n c e da l g o r i t h m t h i sp a p e rp r e s e n t sc o d e a n a l y s i sa n dc o d et r a n s f o r m a t i o na san e wm e t h o dt oa c h i e v et h i s p u r p o s e a tt h es a m et i m e ，c o d ea n a l y s i sa n dc o d et r a n s f o r m a t i o ni sa l s o a b l et op e r f o r mt h ei n t e r c e p t i o no ft h es y n c h r o n i z a t i o ns t a t e m e n t s ，t h u s t r a n s p a r e n t l ym o d i f yt h en o n r e p l i c a t e dc o d et or e p l i c a t e dc o d e t h i s m e t h o dc a na v o i dm o d i f i c a t i o no ft h eu n d e r l i n go p e r a t i n gs y s t e m ， v i r t u a lm a c h i n e a n dm a n u a l l ym o d i f i c a t i o no ft h ec o d ei sn o tr e q u i r e d i nt h i sp a p e r , m d s f , ad e t e r m i n i s t i cs c h e d u l i n gf r a m e w o r ki s i n t r o d u c e d i tc o n s i s t so ft w op a n s ，o n ei st h es o u r c ec o d ea n a l y s i sa n d t r a n s f o r m a t i o nm o d u l ew o r k i n gi np r e c o m p i l e dp h a s ea n dt h eo t h e ri s t h em u l t i t h r e a ds c h e d u l i n gm o d u l eo p e r a t i n gi nr u n n i n gt i m e t h e i i 北京邮电大学硕士研究生学位论文多线程复制系统的确定性调度框架m d s f 的研究与实现 f o r m e rp e r f o r m sac o d ea n a l y s i su p o nt h em u l t i t h r e a d e ds o u r c ec o d e ， a n dac o d et r a n s f o r m a t i o nb a s e do nt h ea n a l y s i st h er e s u l t s t h e t r a n s f o r m e dc o d ei sd e p l o y e dt ot h ee n v i r o n m e n tt ow o r kw i t ht h e m u l t i t h r e a ds c h e d u l i n gm o d u l e w h i c hi m p l e m e n t sa m a l g o r i t h ma n d w i l lc a r r yo u tau n i f i e dm u l t i t h r e a ds c h e d u l i n g p r o v e nb yt e s t ，t h e s c h e d u l i n gf r a m e w o r ks u p p o r t st h er e u s eo f t h ee x i s t i n gn o n r e p l i c a t i n g c o d e ，a n dc a nr e a l i z eh i g h p e r f o r m a n c em u l t i t h r e a d e ds c h e d u l i n g k e yw o r d s ：m u l t i t h r e a d ，r e p l i c a t i o n ，d e t e r m i n i s t i c ，s t a t i ca n a l y s i s ， c o d et r a n s f o r m a t i o n ，m d s f i i i 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中 不包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或 其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所 做的任何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处， 本人签名亟垂 本人承担一切相关责任。 日期：竺翌：主：竖 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权 保留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅 和借阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印 或其它复制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在一年解密后适用本授权书。非保密 论文注释：本学位论文不属于保密范围，适用本授权书。 本人签名： 导师签名： 扬雯 日期： 日期： 沙1 。f 3 o 矽| 弓3 北京邮电大学硕士研究生学位论文 多线程复制系统的确定性调度框架m d s f 的研究与实现 1 1 研究背景 第一章概述 随着r r 技术的高速发展，系统的稳定、数据的安全越来越受到重视。如何 提高系统的抗灾容错能力，以确保其连续稳定运行，是当前的一个研究热点。 对数据的完整性、实时性极为敏感的军事、航天、金融、通信、交通等领域， 整个系统的连续稳定运行及数据安全至关重要。一旦整个系统中断运行，将给 各个部门的运行带来极大的混乱；而数据一旦丢失，则带来的损失将是灾难性 的。【1 】 因此，保持系统资源的高可用性是选择计算机系统的重要指标。如何确保 系统资源的高可用性，如何保证整个系统的连续稳定运行，成为人们非常关切 的问题。 1 1 1 复制圆【3 】【4 】【习 分布式系统永远会面临的问题就是节点失败。要解决这一问题，可以通过 基于硬件的机制来减少出错的可能性，或者提供系统出错后的恢复机制，或透 明屏蔽节点失败带来的影响。 使用高特殊的可靠性硬件( 比如冗余存储、冗余电源) 可以提高系统的可依 赖程度。这种方法一般用于对可靠性有很高要求的系统中。可靠性的提高伴随 着硬件成本的增加，基于软件的容错机制可以看作是减少这些成本的好方法。 然而，考虑用基于硬件的方法作为基于软件的容错机制的补充未尝不是容错的 好选择。这两个概念可以同时独立应用到系统中来提高可用性。 恢复一般来说由周期性创建检查点来支持，这些检查点能够用于在系统故 障之后将系统重置到检查点状态。虽然这种方法在无故障时的操作有很小的开 销，但当故障发生时却会丢失最后一次检查点之后的所有状态更新。而且，在 系统恢复时有系统不可用的问题。恢复机制需要精确和及时的故障检测。错误 的识别故障将导致不必要的恢复开销和状态丢失。使用较长的故障检测周期能 够减少错误识别的风险，但也延长了系统故障到可用的时间。 复隹j i j ( r e p l i c a t i o n ) 是分布式系统中容错的另一种方法，指的是在多个节点上 北京邮电大学硬研究学位论文多线程复制系统的确定性调度框架m d s f 的研究与实现 冗余地提供相同的服务功能。互为冗余的对象互成g 本( r e p l i c a ) 。在一个节点 发生故障之后，其它副本能够继续提供服务，从而透明地屏蔽故障带来的影响。 一般而言，复制的实体之间需要保持数据、状态的一致。 在对可靠性要求不高的情况下，可以简单地采用圈1 1 ( a ) 所示的非复制模 式来简单的提供服务，这种模式架构简单，但是一旦服务器发生错误，将使得 服务不可用。如果采用图l ，“b ) 复制的容错模式，则可以避免因为少数服务器 错误而引起的服务中断。在分布计算环境中，窖错一般都通过冗余配置实现。 复制是为确保冗余资源一致性的共享信息过程，分为文件系统复制、数据库复 制，对象复制等。主动复制和被动复制是两个经典的对象复制算法。本文所涉 及的复制指的是对象复制中的主动复制。 客户客户日客户c 1 12 对象复制 p $ m 女i m $ $ i l l8 c $ 1 1 j m 刍 叠 客户客户b客户c ( a ) 非复制模式( b 1 复制模式 图1 - 1 两种服务器模式 在分布式环境中，基于对象的中问件使用对象作为分布单元。这里所说的 对象是一个粗粒度的实体，可以将之看作服务。这里采用了一个与面向对象概 念相似的想法。一个服务就是一个对象，如果为了保证容错性等原因而在多个 服务器上运行某个服务的副本程序则每一个服务器上运行的副本程序相当于 这个服务对象的一个对象实例。一个服务如果在多个服务器上运行相同副本则 称为复制对象：相反，如果只运行在一台服务器上，则是非复制对象。 分布的对象包括多个编程语言层面上的对象，它具有明确定义的向远程调 用提供服务的接口。一个对象复制系统在多个节点提供一个对象( 服务) 的冗余 实例，对象的状态( 数据) 和功能( 代码) 都是复制的。当一个对象在多个节点( 上 拥有副本时，只要其中一个副本可用，则对象( 服务) 可用。被动复$ 1 j ( p a s s i v e p 一 9 北京邮电大学硕士研究生学位论文多线程复制系统的确定性调度框架m d s f 的研究与实现 r e p l i c a t i o n ) 和主动复带l l ( a e t i v er e p l i c a t i o n ) 是保持复制对象一致性的两种重要 方法。 在被动复制( 又叫主从复制) 中，由一个主副本( p r i m a r yr e p l i c a ) 来处理请求， 其还负责更新二级副本( s e c o n d a r yr e p l i c a ) 的状态。一般地，并非在每次主副本 状态改变之后都将状态更新到二级副本，因为这样做的代价太高；而是在一段 较长的时间间隔之后才进行异步更新。如果主副本出现故障，则一个二级副本 将被选为主副本。在这种情况下，新的主副本将重新执行最后一次状态更新之 后的所有请求。为了达到这一目的，一个请求日志会记录所有在上一次状态更 新之后所执行过的客户请求。被动复制节约系统资源，不要求服务的状态是否 确定，但失效恢复时间长，而且还带来了主副本状态一致性问题。尤其是当主 副本在处理请求的过程中突然失效，这时副本的状态一致性很难维护，处理不 当会带来严重后果。【3 】 在主动复制中，所有副本独立执行相同的客户请求。状态机复制便用于这 种方法中。方法的执行需要是确定性的。因此，副本的状态保持一致。最简单 的策略是确保每一个方法行为的确定性，并按照全序( t o t a lo r d e r ) 顺序执行所有 方法。所有副本执行客户调用的方法，只要有一个副本可用，客户就能够没有 延迟的接收到响应。主动复制失效恢复时间短，但耗费系统资源，同时它还要 求各个副本保持确定性( d e t e r m i n i s t i c ) ，而且如果选在顺序执行的方法，还会面 临环形嵌套调用所带来的死锁问题。 一个复制对象a 可以调用复制对象b 的远程方法，这称为嵌套调用。支持 这种调用会给复制框架增加复杂性，这也是只有少数几种系统提供这种支持的 原因。对于嵌套调用，复制框架需要确定一个b 的副本的远程方法虽然被多个 对象a 的副本调用，但仅仅执行一次。另一方面，对象b 的调用结果需要传送 给对象a 的多个副本。 环形嵌套调用可能引起死锁：在执行对象a 某一方法时，经过一连串嵌套 远程调用最终又调用了a 的另一个方法，则a 上的第二个调用不会被处理，从 而导致死锁。相互嵌套调用会导致一个类似的死锁问题：如果对象a 的m a 方 法和对象b 的m b 同时调用彼此的远程方法，则这些嵌套调用在单线程模式下 不能被处理，从而导致死锁。 1 1 3 多线程复制及确定性 6 1 复制框架的任务之一是确保所有的副本在相同的逻辑时间点拥有相同的状 态。对于对象复制来说，一般都分主动复制和被动复制两种。被动复制采用主 从机制，一个主副本执行所有请求，并把状态更新到其他备用副本。在主动复 3 北京邮电大学硕士研究生学位论文多线程复制系统的确定性调度框架m d s f 的研究与实现 制中，所有副本执行所有请求，且执行需要有确定性，从而保证所有副本间的 一致性。 何谓确定性? 主动复制要求不同的服务器上存储相同的数据，运行相同的 代码来提供相同的服务。这对系统提出了一个新的要求，即如何保证不同服务 副本之间的一致性。复制的服务副本之间是平等的，因此并没有哪一个服务副 本来承担协调副本之间一致性的工作，如果服务副本按照相同的运行逻辑来执 行客户请求，那么在保证各个副本接收相同请求的情况下就能够保证副本间数 据和状态的一致性。复制的服务副本按照确定的逻辑进行能够运行，这就是所 谓的确定性。 多数对象复制系统按照全序顺序执行方法。这种策略消除了同步更新对象 状态而因此的不确定性。然而这种方法也不能利用多c p u 或多核c p u ，从而 因非并行而导致没有必要的低效执行。同时，这种执行模式也会引起死锁。比 如，当一个远程对象a 在执行方法m a l 的时候调用了另外一个远程对象，而 后者又调用了a 的方法。 文章 6 】中考察了几种允许并行且保证确定性的编程模型和算法。结论是多 线程复制是最灵活和最有力的方案。然而，多线程有着非确定性的风险，而且 需要复杂的调度策略算法。几种确定性调度算法 7 】 8 【9 】【1 3 】在过去已经被提 出。本文提出的确定性调度框架便是基于多线程复制系统提出的，框架中的线 程调度模块实现了一种基于m a t 算法【9 】改进的调度算法。 1 2 研究现状 为了提高服务的容错性，很多系统往往采用冗余的服务副本( 经常地，不同 的服务副本运行位置独立的多台服务器上) 保证可靠性。主动复制便是提供冗余 服务的一种常见方式，它要求不同的服务副本上存储相同的数据，运行相同的 代码来提供相同的服务。这对服务系统提出了一个新的要求，即如何保证不同 服务副本之间的一致性。副本之间是平等的，因此并没有哪一个副本来承担协 调副本之间一致性的工作。如果每一个服务副本都按照相同的运行逻辑来执行 客户请求，那么在保证各个服务副本接收相同请求的情况下，就能够保证副本 间数据和状态的一致性。每个服务副本按照确定的逻辑进行能够运行，这就是 所谓的确定性。 1 2 1 算法研究现状 单线程程序能够保证确定性，但单线程有着效率低下等问题。多线程程序 4 北京邮电大学硕士研究生学位论文多线程复制系统的确定性调度框架m d s f 的研究与实现 能够很好地利用多核c p u 、多c p u 资源，但也面临多线程情况下如何保证确 定性的问题。现有的几种多线程调度算法都在一定程度上支持多线程运行，但 都采取了保守的方式来避免多线程所带来的不确定性，从而影响了多线程同步 性的提高。 1 2 2 代码截获现状 非复制的服务代码在运行时是由服务器的操作系统或者虚拟机来负责对多 线程进行调度。当对非复制代码进行复制从而使多份相同的代码运行在物理位 置相互独立的服务器上时，需要采取某种策略来确保各个服务程序的确定性。 文章 7 】 8 】 9 】 1 3 】描述了几种保证多线程确定性的调度算法，包括s a t 、p d s 和 m a t 等。在多线程复制系统中的线程调度模块都实现了某种多线程调度算法， 这一模块一般都通过以下方式来获得对同步操作的控制： 1 ) 修改底层操作系统或虚拟机 对底层调度系统的修改，使调度模块成为底层系统的核心模块，从而使其 能够按照调度算法来确定性地控制多线程的运行。这种方式不需要修改原有的 非复制代码，但其缺点也是颇为明显。首先修改底层系统工作量大，难度高， 易出错，对系统开发者提出很高要求。而且当采取新的调度算法时需要重写系 统代码，重新编译和安装，工作量大。【l o 】【l l 】 2 ) 手动修改非复制代码 将所有同步操作手动修改成对调度模块中的特定方法调用，从而使调度模 块能够截获所有互斥锁的获取和释放操作。这要求开发人员基于复制框架进行 编程而不是基于编程语言的同步机制进行编程，并且不容易重用现有的非复制 代码。 3 ) 截获外部线程库 一些编程语言本身没有提供同步机制，因此需要使用外部库来对同步机制 提供支持。如c c + + 语言中，使用的是p o s i x 线程库( p t h r e a d ) 。在这种情况下， 可以修改p t h r e a d 库，将对原p t h r e a d 库的调用截获，并把调用转发给调度模块， 由调度模块来完成对多线程的确定性调度。这种方式没有以上谈及的底层修改 方法的各种缺点，但是这种方式也存在缺陷。在j a v a 语言中，同步机制可以通 过j a v a u t i l c o n c u r r e n t 等工具包中提供的各种机制来实现，也可以利用语言本身 的内嵌同步原语( 比如s y n c h r o n i z e d 关键字) 来实现。则在像j a v a 这种含有内嵌 同步原语的语言中，采取截获多线程库调用的方法不能覆盖语言中所有的同步 机制。 代码转换可以很好地解决以上问题。本文介绍了用以修改j a v a 源代码的代 北京邮电大学硕士研究生学位论文多线程复制系统的确定性调度框架m d s f 的研究与实现 码分析、转换模块。该模块能够将j a v a 语言中所有同步语句转换成与线程调度 模块进行交互的语句，从而实现对同步操作语句的截获。这种方法对多线程程 序开发者完全透明，他们能够自主地使用各种同步机制，包括s y n c h r o n i z e d 关 键字和i a v a u t i l c o n c u r r e n t 等工具包来开发非复制代码，而不需要考虑代码转换 这一过程。在将非复制代码部署到各个副本服务器之前，该代码转换系统对代 码进行相应转换，从而使代码变成复制代码。复制代码经过编译，最后便可部 署到复制系统中去。 1 3 本文工作 本论文的研究目标是针对当前多线程复制系统中的现有问题提出一种新型 的确定性调度框架，在当前现有调度算法的基础上提出改进算法，通过代码分 析、转换这一新颖的方式来完成同步语句的截获及其预测功能，使多线程代码 经过转换之后，具有向调度模块提前汇报同步操作信息的能力，从而使实现了 改进算法的调度模块能够利用这些信息来提高多线程的同步性。 本论文的工作主要包括以下几个部分： 首先介绍复制这样一种提供冗余计算、存储的抗灾容错模式，阐述了对象 复制特别是主动复制，并对当前多线程复制领域的研究现状进行分析。 接下来提出一种确定性的调度框架m d s f ，简述该框架的系统模型以及框 架组成部分：线程调度模块、代码分析模块和代码转换模块。并在接下来的章 节中详细描述各个模块的功能和实现细节。 最后搭建测试环境对m d s f 框架进行了功能测试和性能测试。 需要指出的是，本文的主要研究对象是多线程复制系统中的确定性调度模 型，着重点在于一个副本服务器上如何在确保确定性的情况下提高多线程同步 性能；而不是一个复制体系结构的解决方案，因此不涉及图1 1 ( b ) 中的前端服 务器和副本服务器之间的通信过程、多副本服务器针对同一个客户请求的返回 结果的处理、副本服务器出错处理等。 1 4 论文结构 本文共分为八章。 第一章为概述，主要介绍课题的立题背景、容错系统的基本概念和关键技 术、本课题的研究目标、研究内容及论文的组织情况。 第二章提出一种新的多线程调度框架一m d s f 框架，并提出通过代码分析 来提供锁预测信息这一崭新的思路。该章节介绍这个多线程调度框架的组成、 6 北京邮电大学硕士研究生学位论文 多线程复制系统的确定性调度框架m d s f 的研究与实现 工作流程和优点，并对该框架的系统模型进行了阐述。 第三章介绍了框架中的线程调度模块，介绍了几种确定性调度算法，总结 各自优缺点，并在其中一种算法的基础上提出改进算法一a m a t 算法，m d s f 的线程调度模块便实现了该算法。 第四章讲述了代码分析模块和代码转换模块的工作目标，详细介绍了调度 模块提供的接口，并以一个简单程序代码作为例子来阐述代码分析和代码转换 的具体工作。 第五章详细阐述代码分析模块。首先介绍静态代码分析的基本概念和s o o t 工具包的相应知识，然后介绍了代码分析模块的工作流程，最后讲述了其实现 细节。 第六章详细介绍代码转换模块的工作流程和所用到的技术，并展现部分代 码来讲述如何实现代码转换过程。 第七章对m d s f 框架进行测试，包括功能测试和性能测试两部分。 第八章总结了本文所做的研究工作，并对下一步工作做了展望。 7 北京邮电大学硕士研究生学位论文多线程复制系统的确定性调度框架m d s f 的研究与实现 第二章m d s f 框架 本章将对本文提出的确定性调度框架进行介绍，接着对该框架所基于的多 线程复制模型进行阐述，并在最后一节中详细介绍该框架如何解决多线程代码 中同步操作的截获问题。 2 1 框架简介 本文提出一种新型的调度框架m d s f ( m u l t i t h r e a d i n gd e t e r m i n i s t i c s c h e d u l i n gf r a m e w o r k ) 。m d s f 是一个基于j a v a 语言的同步模型，支持可重入 互斥锁、条件变量以及w a i t 操作上超时设置。这一模型提供了比现有系统更高 的灵活性，因为现有系统大部分仅仅支持二进制互斥锁。m d s f 中的同步模型 能够完全支持j a v a 语言中的原生同步机制( 主要是对s y n c h r o n i z e d 关键字的支 持) 。这样的好处在于允许开发者使用更丰富的同步方法，以及简化现有代码的 重用。 任何一种确定性调度框架需要截获复制对象的同步语句，从而来保证多线 程的确定性。本文提出代码转换这一截获j a v a 同步操作的崭新方法，那些转换 后的语句会与m d s f 中的线程调度模块进行交互，从而使调度模块能够对线程 进行调度。这一方法不像现有的大多数框架一样修改底层操作系统或j v m 。 i 多线程源代码卜叫代码分析模块卜叫代码转换模块卜叫修改后的源代码 上 预编译阶段 j a v a 编译器 j r i 线程调度模块卜 4 应用程序 运行阶段 图2 - 1m d s f 框架图 m d s f 框架由两大部分组成，一个是在预编译阶段的代码分析模块和代码 转换模块，另一个是运行时的线程调度模块。前者能够对多线程程序的源代码 进行分析，并且根据分析结果修改源代码。修改过的源代码在进行正常编译之 后部署到运行环境中，并与实现了a m a t 算法的调度模块进行交互，调度模块 北京邮电大学硕士研究生学位论文 多线程复制系统的确定性调度框架m d s f 的研究与实现 会对多线程进行统一调度。 2 2 系统模型 一个确定性多线程程序至少要满足以下条件才能正确执行：副本中多线程 程序必须正确使用同步机制。如果没有正确的同步机制，程序在非复制的执行 环境中也不能正确工作；一个不能正确使用的程序，再有效的线程调度策略也 不可能确保程序的确定性。 2 2 1 通信模型 一个服务器提供一组服务，客户可以通过提交请求来调用这些服务。服务 器是复制的，也就是说每一个服务器都含有相同的副本服务( 含有相同的数据和 代码) 。为了提高容错性，不同的服务器安置在不同的地理位置。客户使用群组 通信原语( 多播) 1 2 】来与复制服务器进行交互。这些原语可以根据对消息顺序的 保证和提供的容错性来进行分类。全序保证每一条发送的信息都按相同的顺序 到达所有副本服务。至于容错性，可靠的多播可以保证一条信息要么被所有的 副本服务收到，要么都没有收到。消息会按照可靠的全序多播来进行发送。客 户n 务器之间的交互是同步的，比如客户在收到应答之前会一直挂起。 2 2 2 同步模型 m d s f 的目的是为了将非复制的对象实现经过转变，从而成为能够运行在 多个副本服务器上的复制对象实现，并在运行时能够保证确定性。 1 ) 正确使用同步机制 正确将非复制对象经过转换变成复制对象从而部署到系统中去，首先要求 开发非复制对象的开发者正确使用同步机制来编写多线程代码。 如果一个非复制的对象实现是为了单线程执行，那么它肯定不会包含同步 语句，因此它只能使用在单线程的复制对象中。如果使用了多线程，那么就需 要正确协调对共享对象数据的同步访问。对于那些已存在的为多线程执行模型 而设计的对象实现，m d s f 的调度模块支持对这些对象实现的复制，而不要求 开发者修改对象代码中同步机制。这里所说的对象如1 1 2 描述的对象是同一个 概念。 2 ) 使用同步来操作共享数据 j a v a 中一些基本的数据类型( 比如i n t ) 的操作是原子的，对这些原子数据类 型的多线程操作不需要使用显式的同步机制。j a v a 运行环境( j r e ) 能够保证任何 9 北京邮电大学硕士研究生学位论文多线程复制系统的确定性调度框架m d s f 的研究与实现 对这种类型变量的使用是原子的。比如，在没有进行协调的情况下，两个线程 分别向一个i n t 变量写入一个新值，那么这个变量值肯定是这两个新值其中之 一。m d s f 调度模块不支持这种未协调的变量访问，取而代之，对所有共享数 据的访问都需要有显式的同步。 3 ) 所支持的同步机制 j a v a 为线程同步提供了原生( n a t i v e ) 同步机制，包括二进制互斥对象和条件 变量。 j a v a 将每一个对象与一个二进制互斥对象进行绑定。所有互斥对象的锁定 都是可重入的：一个线程可以锁定相同的互斥对象多次。只有当对互斥对象锁 定和释放的操作次数一致时，该互斥对象才会被最终释放。一个s y n c h r o m z e d 关键字便使用互斥对象。比如，当进入一个s y n c h r o n i z e d 代码块时，会获取互 斥对象的锁定；当退出时释放锁定。 条件变量允许一个线程在被互斥对象保护的一段临界区域中等待一个条 件。如果一个线程在等待一个条件变量，它将释放相关的互斥对象并挂起。另 一个线程能够通知( s i 弘a 1 ) 这个线程重启( r e s u m e ) ；这个重启的线程会隐式的重新 申请对这个互斥对象的锁定。 另外，j a v a 允许开发者为那些等待操作指定超时时间。在等待超时后，在 一个等待操作上被挂起的线程将不需要任何通知( n o t i 母) 就能够重启。 以上谈到的j a v a 原生同步机制，包括互斥对象、条件变量以及等待超时操 作都是j a v a 同步机制的重要部分，在m d s f 的同步模型中都是支持的。 在j d k5 0 中对多线程并发编程有了更好的支持。i a v a u t i l c o n c u r r e n t 包提 供了一些在并发编程中很常用的实用工具类。i a v a u t i l c o n c u r r e n t a t o m i c 包是类 的小工具包，支持在单个变量上解除锁的线程安全编程。 j a v a u t i l c o n c u r r e n t 1 0 c k s 为锁和等待条件提供一个框架的接口和类，它不同于内 置同步和监视器。在当前的系统实现中尚不支持j d k 5 0 的新特性，对其支持将 列入m d s f 框架的下一步开发计划之中。 2 2 3 同步机制细节 j a v a 语言提供了s y n c h r o n i z e d 关键字来指定对一个互斥对象的同步操作。 任何一个j a v a 对象实例都能够作为一个互斥对象被使用。s y n c h r o m z e d 关键字 可以作为方法修饰符或者代码块的修饰符。 1 ) 对于一个对象的s y n c h r o n i z e d 实例方法，线程在进入该方法时锁定该对 象，并在离开方法时释放该对象的锁定。 2 ) 对于一个类的s y n c h r o n i z e d 静态方法，线程在进入方法时锁定类的元对 l o 北京邮电大学硕士研究生学位论文多线程复制系统的确定性调度框架m d s f 的研究与实现 象，并在离开时释放。 3 ) 一个以s y n c h r o n i z e d 关键字开头的代码块( 简称s y n c h r o n i z e d 代码块) 显 式指定了一个对象，在进入代码块时该对象会被锁定，离开代码块时释放。 一个s y n c h r o n i z e d 元素隐式指定了一个l o c k 和u n l o c k 操作。这样的结构比 显式的锁定语句更不容易出错；一个互斥对象不会在被锁定之前解锁，也不会 在上锁之后忘记解锁。一个执行线程能够经过多个嵌套的s y n c h r o n i z e d 元素， 这意味着多个互斥对象被连续锁定。隐式锁的获取没有显式的l o c k 和u n l o c k 操 作那么灵活，因为一个线程获得的所有的隐式锁都必须由该线程按照相反的顺 序来u n l o c k 。 除互斥对象外，j a v a 为每一个对象提供了一个条件变量。为此，所有对象 都从j a v a 1 a n g o b j e c t 类中继承了f i n a l 方法w a i t ，n o t i f y 和n o t i f y a u 。当线程获 得一个对象的互斥对象的锁定之后这些方法才能够被调用。w a i t 0 方法释放对象 锁定，并阻塞直到被通知( n o t i f y ) 或被超时( t i m e o u t ) 唤醒。n o t i f y ( ) 唤醒一个在w a i t 操作上阻塞的线程，使其重启。n o t i f y a u 方法解除所有等待线程的阻塞状态。 典型地，w a i t 0 用在一个检查条件的循环中。 多线程j a v a 程序在线程管理上面临着几个不确定性因素： 1 ) 线程并行调度的顺序是不可预测的。如果两个线程同时使用一个相同的 数据，因此需要申请对应的互斥对象，则两个线程之间哪一个先获取这个互斥 对象是不确定的。 2 ) 如果一个线程申请获取另一线程持有的互斥对象，则会挂起直到该互斥 对象可用为止。如果有多个线程被挂起，则当互斥对象被释放时哪一个线程会 被选择从而持有该互斥对象是不确定的。 3 ) 在两种通知操作( n o t i f y 和n o t i f y a l l ) 中，我们不能预测等待线程被唤醒和 执行的顺序，因为j l s 并没有明确这一个顺序。 复制一个使用j a v a 同步机制的对象实现不应该要求开发者重改现有代码。 因此需要调度框架本身必须使用某种手段来去除所有因多线程同步运行而引起 的不确定性，从而在运行时保证锁的获取和等待线程重启的顺序具有确定性。 2 3 同步操作的截获 在复制对象中使用多线程要求复制体系结构能够控制并发操作。这一事实 适用于所有确定性的多线程调度。为此，复制体系结构必须控制同步操作以确 定使用共享数据的顺序。这意味着复制体系结构必须截获复制对象代码中所有 与同步操作有关的语句。 方法调用的截获可以使用底层方法来实现，比如使用特意修改的硬件、操 北京邮电大学硕士研究生学位论文 多线程复制系统的确定性调度框架m d s f 的研究与实现 作系统和j a v a 虚拟机。采取这种方法工作量大，难度高而且容易出错。因此 m d s f 不采用这种修改底层的方法来支持多线程的确定性。在像c + + 一样的语 言中，可以重定向对本地线程库如p t h r e a d 库的调用。比如e t e r n a l 系统便使用 这种方法来实现透明地截获同步调用。在j a v a 语言中，原生同步原语直接嵌入 在编程语言中，因此调用重定向的方法在这种情况下不能使用。 广 r 广 i 非复制代码卜_ 1代码转换卜_ 叫非复制代码卜部署 图2 - 2 透明的代码转换过程 相反，本文提出一种代码转换的方法。m d s f 的代码转换模块能将代码中 的j a v a 同步语句转换成与m d s f 调度模块交互的同步调用。这种方法对于应用 程序开发者来说是透明的，因为应用程序可以直接使用所有的j a v a 同步机制， 而不需要考虑代码转换过程。在应用程序部署之前，代码经过代码转换工具( 如 图2 2 ) 。经过代码转换模块，所有涉及互斥对象和条件变量操作的同步方法都 会被截获。 所有源代码中的s y n c h r o n i z e d 元素都需要被转换成对m d s f 调度模块中的 l o c k u n l o c k 调用。因为遇到异常或者返回语句会使方法提前退出，因此采用一 个t r y f i n a l l y 结构来确保u n l o c k 操作总会被执行。针对2 2 3 所描述的3 种使用 s y n c h r o n i z e d 关键字的情况，对应着3 种不同的代码修改模式。 1 ) 对于一个s y n c h r o n i z e d 实体方法，t h i s 作为l o c k 和u n l o c k 中的m u t e x 参 数。 2 ) 在s y n c h r o n i z e d 静态方法中，一个类的元对象引用( 如c l a s s n a m e c l a s s ) 作为m u t e x 参数。 3 ) 相比之下，对s y n c h r o n i z e d 代码块的操作会更加复制，m u t e x 的值有可 能在代码块中改变。因此必须拷贝m u t e x 引用，从而使u n l o c k 能够正确操作。 1 2 北京邮电大学硕士研究生学位论文多线程复制系统的确定性调度框架m d s f 的研究与实现 图2 3s y n c h r o n i z e d 实例方法的转换 图2 3 的例子阐明了代码转换的效果。图2 - 3 ( a ) 中的加粗斜体字体的是 s y n c h r o n i z e d 关键字和w a i t 、n o t i f y 操作，这些都是转换的目标。在2 - 3 ( b ) 中的 加粗斜体所标示的代码便是转换后的结果。一个s y n c h r o n i z e d 方法转换成一个 l o c k u n l o c k 对，l o c k 处于方法的开始，而u n l o c k 位于方法的末尾，t h i s 作为l o c k 和u n l o c k 的操作对象。 除了互斥对象之外，m d s f 调度模块还提供方法来支持条件变量。对w a i t ( ) ， n o t i f y ( ) 和n o t i f y a l l 0 的方法调用会简单地转换成对m d s f 调度模块相应的方法 调用。因为w a i t o ，n o t i f y ( ) 和n o t i f y a l l 0 已经是j a v a 中任何一个对象的保留方 法名，因此在m d s f 接口中使用了i 作为这些方法的前缀来标识相应方法。 1 3 北京邮电大学硕士研究生学位论文多线程复制系统的确定性调度框架m d s f 的研究与实现 第三章线程调度模块 在本章中，首先回顾一下现有的几种多线程调度算法，然后阐述m a t 算法 细节，然后提出基于m a t 算法的改进算法一a m a t 算法并对该算法进行详细 的介绍。m d s f 框架的调度模块实现的就是a m a t 算法。 3 1 现有的确定性调度算法【6 】 确定性( d e t e r m i n i s t i c ) 行为是大多数对象复制方法的必要条件。为避免多线 程所带来的不确定性，很多对象复制系统仅采用顺序方法调用。 多线程调度框架需要解决不确定性的问题。不确定性包括2 2 3 节论述的多 线程管理上面临的几个不确定性因素，还包括以下几个因素： 1 ) 并行执行的线程在获取互斥对象的顺序是不确定的 2 ) 客户请求到达服务副本的延迟可能不同。 3 ) 嵌套调用到达不同服务副本的时间可能不同。 钔并行执行的线程执行速度是不确定的，不同服务副本之间可能存在很大 差别。 因此，不可能事先得知锁获取的固定顺序。多线程调度算法的目的就在于 在不同的服务副本中唯一确定互斥锁的获取顺序。在本章中，我们将考察已存 在的支持对象方法确定性同步执行的应用层调度算法。 这些算法都有一个共同点，一个线程只有在与其它运行线程没有潜在的非