（计算机系统结构专业论文）基于消息传递系统的多线程并发对象模型.pdf

华中科技大学硕士学位论文 摘要 传统并行并发程序设计采取的是顺序程序设计方式，编程与调试复杂困难，这导 致并行软件开发效率低下。与此同时，用面向对象技术开发软件，能够减小问题域与 解题域之间的语义间隙，使得软件开发过程变得高效。将并行并发同面向对象融合所 产生的对象并行并发系统，既具有面向对象特征，又使并行软件建模变得容易，提高 了并行软件系统的可维护性与可重用性，而在两者结合的过程中需要建立起相应的并 发面向对象模型。 通过对一般的并发面向对象模型特点的分析，总结出构建并发面向对象模型的关 键技术。在此基础上，建立了基于消息传递系统的多线程并发面向对象模型，该模型 采用框架设计，支持异构并行平台，并提供两级粒度的并发。在该模型中，采用并发 对象与并行任务对应起来的对象进程模型，通过运行支撑系统分布并发对象到并行环 境。并发对象间借助高效的消息通信方式进行远程方法请求和计算结果取回。并发对 象内部采用线程对并发成员方法予以封装，由微c s ( c 1 i e n t s e r v e r ，客户月艮务器) 结构集中进行对象方法的并发管理调度。此外，采用“状态方法集”能有效地减弱 继承异常。 模型采用类库方法初步实现。在p v m ( p a r a l l e lv i r t u a lm a c h i n e ，并行虚拟机) 之上设计的r t s ( r u n t i m es u p p o r t ，运行时支撑) 系统包含了预处理框架，为上层并发 对象模型提供了良好的运行支撑。r t s 也引入了许多线程安全机制，用以解决消息传 递库的线程安全问题。 通过测试验证，模型可有效地工作，用实现的并发类库编写测试用例在机群上运 行，显示了较好的加速性能。 关键字：并发面向对象框架，消愚传递系统，多线程，运行支撑，继承异常 华中科技大学硕士学位论文 a b s t r a c t t r a d i t i o n a lp a r a l l e la n dc o n c u r r e n tp r o g r a m m i n gt o o ks e q u e n c ep r o g r a m m i n gt o p r o g r a m ，p r o g r a m m i n ga n dd e b u g g i n g w a s c o m p l e x a n dd i f f i c u l t ，f o rt h i sd e v e l o p i n gt h e p a r a l l e ls o f t w a r ew a s a tl o w e f f i c i e n c y i nt h em e a n t i m e ，a d o p t i n go o t op r o g r a m m i n g c o u l dr e d u c et h es e m a n t i cg a pb e t w e e np r o b l e m sf i e l da n ds o l u t i o n sf i e l d o o pm a k e s t h es o f t w a r ed e v e l o p m e n tm o r ee f f e c t i v e t h eo b j e c tp a r a l l e la n dc o n c u r r e n ts y s t e m sw a s t h eo u t c o m ew h e nc o m b i n i n gt 1 1 ep a r a l l e la n dc o n c u r r e n tm o d e lw i t ho om o d e l t h e s e s y s t e m sn o to n l yh a dt h es u p e r i o r i t yo fo o ，b u ta l s om a d ep a r a l l e l s o f t w a r em o d e l i n g e a s ya n d b e t t e r e dt h em a i n t a i n a b i l i t ya n dr e u s e a b i l i t yo fp a r a l l e ls o f t w a r es y s t e m i nt h e p r o c e d u r eo f c o m b i n a t i o n o f b o t hm o d e l s ，ac o om o d e lm u s tb eb u i l tu p a c c o r d i n gt h ea n a l y s i so fu s u a lc o o m o d e l sc h a r a c t e r i s t i c s ，as u m m a r i z a t i o no f k e yt e c h n o l o g yu s e d t ob u i l dac o om o d e lw a sd r a w n o nb a s i so ft h i s ，am u l t i t h r e a d s c o om o d e lw h i c h d e s i g n e dw i m f r a m e w o r k p a t t e r nw a s b u i l tu pb a s e do nm p s i tc o u l d i u no nh e t e r o g e n e o u sp a r a l l e la r c h i t e c t u r e sa n dh a dt w ol a y e rp a r a l l e lc a p a b i l i t y i n s i d e t h em o d e l ，t h ep r o c e s sm o d e lw a sa d o p t e dt om a pap a r a l l e lo b j e c tt oap a r a l l e lt a s k ， r u n t i m e s u p p o r ts y s t e m w a su s e dt od i s t r i b u t e p a r a l l e lo b j e c t s t od i s t r i b u t e d e n v i r o n m e n t s ，i nf a v o ro ft h em p s y s t e me f f e c t i v em e s s a g ec o r r e s p o n d i n gm a r i n e r ，i t c o u l de a s i l ys e n dr e m o t em e t h o dr e q u e s t sa n dr e c e i v et h er e t u r n e dr e s u l t s t h em e t h o d s i np a r a l l e lo b j e c tw e r ee n c a p s u l a t e dw i t hc o n c u r r e n tt h r e a d s ，t h r e a d sm u s ts a t i s f i e dw i t h v e r t i c a lc o n d i t i o n s m i n ic sf r a m e w o r ka n d b o d y i no b j e c tw a si n t r o d u c e dt oc o n t r o lt h e t h r e a d sc o n c u r r e n te x e c u t i o n f u r t h e r m o r e ，s t a t e s - - m e t h o d ss e tw a su s e dt or e s o l v e i n h e r i t a n c ea b n o r m i t y f i n a l l y , t h ec o o m o d e lw a si m p l e m e n t e db ym e a n so ft h el i b r a r y , ar t s i n c l u d i n g ap r e p r o c e s sf r a m e w o r kw a sd e s i g n e da b o v ep v m ，i tp r o v i d e df i n er u n t i m es u p p o r tf o r t h eu p p e rc o om o d e l i ta l s oi n t r o d u c e dm u c ht h r e a d s a f em e c h a n i s mi n t or t st o s e t t l et h et h r e a d s a f eq u e s t i o n si nm p s y s t e m a c c o r d i n gt e s t ，t h i sm o d e lw o r k e da v a l l a b l y , a n dr u nt h et e s te x a m p l ew r i t t e ni n c o n c u r r e n tc l a s sl i b r a r ya l r e a d yi m p l e m e n t e do nt h eb e o w u l fe n v i r o n m e n t ，i ts h o w e da b e u e rs p e e d u p p e r f o r m a n c e k e y w o r d s ：c o n c u r r e n to b j e c t - o r i e n t e df r a m e w o r k ，m e s s a g e p a s s i n g s y s t e m ， m u l t i t h r e a d s ，r u n t i m es u p p o r ts y s t e m ，i n h e r i t a n c ea b n o r m i t y 1 1 独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除文中已经标明引用的内容外，本论文不包含任何其他 个人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集 体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：试f 善 e t 期：j ! o o 牛年罗月艿日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有 权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和 借阅。本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 保密口，在一年解密后适用本授权书。 本论文属于， 不保密喇。 ( 请在以上方框内打“”) 学位论文作者签名：杏膨 只期：莎呻年f 月8 目 指导教师签名 日期：力口0 年 中 黧 华中科技大学硕士学位论文 1绪论 随着计算机硬件设备及操作系统平台的不断升级，并行计算有了坚实的基础；同 时，随着对象技术的成熟与深入发展，支持并行并发程序设计的对象技术，即并发对 象技术，受到了人们的关注，而并发面向对象程序设计模型及语言是实施并发对象技 术的重要工具，也是发挥并发对象技术之潜能的关键。 1 1 课题背景和意义 并行协同计算由于能提供超级的计算能力，一直是计算机科学发展中最为活跃的 一个分支。特别是近年来一批具有重大挑战意义的科学和工程问题，如：全球大气预 报，石油勘探开发和核聚变模拟等，它们对计算速度的要求达到每秒万亿次以上。这 就使得研究高性能的并行计算技术显得极为重要。这其中不仅要从硬设施着手，研究 并行体系结构，如c p u 流水线并行技术，并行计算机架构s m p ( s y m m e t r i c a lm u l t i p r o c e s s i n g ) 、m p p ( m a s s i v e l yp a r a l l e lp r o c e s s o r ) 、n u m a ( n o n e u n i f o r m m e m o r ya c c e s s ) 等，更要从软技术着手，研究并行软件技术，通过高效的并行软件来充分发挥和挖掘 并行硬件计算的能力。这些研究包括并行程序设计语言、并行编程与调试工具、并行 的操作系统，包括多线程并发处理等技术。 随着计算机集群技术的不断发展，人们利用个人p c 就可方便的搭建廉价的并行 计算环境进行科学计算，因而使并发计算有了更为坚实的基础，所需的只是借助并行 程序设计工具编写并行软件来驱动这些计算资源。 然而，并行程序设计远比顺序程序设计复杂，应用程序必须处理并行任务的划分、 数据在结点的分配、并行进程间的通信以及同步和调度等烦琐细节，对于异构网络， 还必须处理异构结点间的通信协议和数据表示格式的转换。这使得并行程序设计极其 复杂，所开发出来的程序难调试、难维护、难移植。 面向对象程序设计方法是当今最重要软件设计技术之一。面向对象技术用一组对 象模拟现实中的自治实体，对客观世界进行模拟。用面向对象技术开发软件，能够减 小问题域与解题域之间的语义间隙，且其具有的模块、封装、数据抽象及继承等特性， 使得软件开发过程变得更加高效。如果把并行并发技术同面向对象技术融合，将使并 行软件建模变得容易，提高并行软件开发效率，提高并行软件系统的可维护性与可重 用性。 本课题来源于纵向项目“应用软件设计研究”。 华中科技大学硕士学位论文 1 2 国内外发展现状 1 2 1 面向对象技术概况 面向对象技术首先成熟于o o p ( o b j e c t - o r i e n t e dp r o g r a m m i n g ，面向对象程序设 计1 ，然后逐步应用于软件的设计和软件的需求分析，产生了o o d ( o b j e c t o r i e n t e d d e s i g n ，面向对象设计) 和o o a ( o b j e c t o r i e n t e da n a l y s i s ，面向对象分析) 。用面向对 象技术开发的系统由一组交互的软件对象构成，这些软件对象往往对应着实际应用中 一些有形或无形的实体。 面向对象模型由一组互相发送消息的对象构成，其核心概念就是对象和消息。对 象是一个可标识的实体，它由状态和操作两部分构成，对象的状态由对象的局部变量 ( 实例变量) 来表示，对象状态的改变是通过向其发送消息进行的。当对象接收到消息 后，将调用其某个方法( 成员函数) 来对该消息进行处理，方法的执行中有可能改变对 象局部变量的值( 对象的状态) 。对象的方法构成了对象的接口，获取或改变对象的状 态只能通过接口中的方法来进行。对象的这种封装特性可以看作是对模块化和数据抽 象的支持。面向对象模型包含了许多良好的程序设计思想，如：模块、封装、数据抽 象、多态和继承等等，这些对软件的构造、维护及重用是非常有意义的。 1 2 2 并发和面向对象技术 并发( c o n c u r r e n c y ) 的概念由来已久，几乎自从计算机出现起，并发就受到了人们 的重视，它反映了程序潜在的并行执行能力。 传统的并发模型是围绕进程的概念进行设计的，它由一组进程构成，每个进程是 一个顺序执行的过程，各进程间可以并发执行。进程在执行中可以相互通信，交换数 据。进程间通信可以采用两种方式：共享变量和消息传递。信号量、临界区、管程和 路径表达式等被用来对并发进程的操作进行同步。进程是一个实现级的概念，它是对 客观世界活动的一种间接模拟，因此，采用进程模型来解决客观世界中的并发问题就 显得极不自然，并且也使得并发程序难以设计和理解。 面向对象模型以一种更加直接的方式刻画客观世界中的活动，模型中存在着潜在 的并发执行能力。通过简单的观察，不难看出：一个对象向另一个对象发送消息后， 若不需要或不立即需要消息的处理结果，前者不必等待后者处理消息，消息发送者和 消息接受者可以并发执行；对象不都是处于被动的提供服务状态，它们中的一些除了 能通过接收消息向外提供服务外，还可以有自己的事务处理；一个对象往往可以同时 华中科技大学硕士学位论文 处理多个消息，等等。 为了保证面向对象系统的正确运行，必须要给出显式的并发描述与控制，否则将 会出现混乱，例如：当处于某状态下的一个对象不能处理某消息对，强行调用该消息 的处理方法将造成对象内部状态的破坏。另外，对一个对象的多个方法进行并发调用， 也可能造成该对象内部状态的不完整和不一致。目前很多人在研究如何把并发与面向 对象相结合，如何在面向对象模型引进并发描述机制。近年来，有许多并发面向对象 编程方案，可归纳出把并发性引入面向对象系统的三种不同的方法( 如图1 1 所示) ： ( 1 )设计全新的并发面向对象语言。 ( 2 )扩展现有的顺序面向对象语言。 ( 3 )使用现有的顺序面向对象语言，通过外部类库提供并发抽象。 早期的大多数系统都可归于第一种方法。这种方法是设计一种具有内在并发性 的新的并发面向对象语言，如：a b c l 1 2 1 ，p o o l 3 1 、h y b r i d n 、s r 5 1 等。这些新的 语言提供了强大的并发性和一般的编程能力。近年来，国外有许多人以a c t o r 【6 j 模型 为基础，开发出新的并发面向对象语言。如：a b c l 1 ，a c t l ，a c t 2 ，a l b a 等。 第二种方法是随着面向对象方法的成熟和顺序面向对象语言的流行而提出的。 国外在这方面已经做了大量的研究，m e n t a t 7 1 ，p c + + 【8 】c c + + 【9 】，h p c + “1 0 1 和i c + + i 都是从c + + 繁衍出来的显式并行面向对象语言。 类库方法扩充语祛成分 设计新语言 改动多少 图1 1 三种并发面向对象语言实现形式 国内在这方面也做了大量的工作，提出了许多基于某种模型的对c 或c + + 的扩展。 上海交大提出了一种d u a l o b j e c t l l 2 1 面向对象并行程序设计模型，然后给出了基于这种 模型的扩展c + + 并行程序设计。该模型通过引入从语义角度出发的数据一致特性的描 述，在一定程度上解决了实现效率低下的问题。清华大学提出了c c p p 1 3 1 模型及其语 言。c c p p 语言是对c + + 语言的扩充，采用预编译方法实现。c c p p 语言允许并发删顷序 代码重用。吉林大学提出了基于现有模型a c t o r 扩展c + + 并发面向对象语言a c + “14 1 。 华中科技大学硕士学位论文 a c + + 主要探讨如何简单地在语义级上平滑地结合a c t o r 模型和普通面向对象语言，构 成新的并发面向对象语言。在a c + + 中采用了“扩充的行为抽象”和“异步创建”等新方 法，使得a c + + 既支持a c t o r 模型的并发计算能力，又能保持面向对象语言的特性。 类库方法，即第三种方法是最近才提出的，国外在这方面已经做了很多工作，提 出了一些基于c 斗斗语言的并发类库，如p a r c + “”j ，a c t + + l 。 a c t + + 是使用a c t o r 模型的c + + 并发类库，它是c + + 的一种并发扩充，采用了a c t o r 模型的一些并发特色。a c t + + 的显著特点之一就是使用行为集的概念能够处理继承异 常即面向对象语言中继承机制与同步约束规范之间的冲突。 国内也开始了这方面的研究，如吉林大学开发出了基于并发类库的c + + i ”j 。为充 分发挥对象间的并行性，提出了并发对象间的非阻塞的异步方法请求机制。运行在通 用网络操作系统之上的由本地前台管理员和各节点服务员组成的运行支撑系统，便于 移植。清华大学在机群系统中提出了用不同的模型实现c 十+ 并行类库，基于消息传递 的m p c + + 【l ，基于共享对象的s o c + + i ”l ，不过这些模型只是对并行库的c + + 封装， 并没有提供语义上并发控制的机制以及对象内部的并发。 1 2 3 工作站机群软件的发展 伴随着计算机体系结构的发展成熟，微处理器技术的性能不断提高，同时高速 网络技术的进步使得松散耦合系统的通信瓶颈逐步得到缓解。由网络互连的同构和 异构计算机机群系统，以其巨大的计算能力，良好的性能价格比和可扩展性，以及 灵活的体系结构得到广泛应用。 可扩展工作站机群是将一组节点计算机通过高性能网络连接起来，按某种结构连 接起来，在并行程序设计以及可视化人机交互集成开发环境的支持下，统一调度，协 调处理，作为一个单系统向用户提供高性能、高可用性服务的系统。系统的资源管 理及相互协作一般由操作系统之上的并行编程环境完成，系统就可以屏蔽底层硬件 ( 包括工作站和网络) 的异构性，从而具有相当好的跨平台性能和可扩展性。 一个典型的可扩展机群系统的体系结构如图1 2 所示。 如果单单把多个计算机用网络连接起来，而不提供软件支撑，是不能构成高性 能并行计算系统的，因此基于集群架构的并行编程环境并行程序设计语言也应运而 生。这其中主要有两种编程机制：消息传递机制和共享存储机制。共享变量的编程 方式可以方便的处理共享数据，适合大规模并行处理方式，但模型较复杂，需要并 行系统有专门的内存管理硬件环境支持，这就限制了其在分布式系统中的应用潜 力。因此除了少数具有硬件支持的d s m ( d i s t r i b u t e ds h a r e dm e m o r y ) 之外，其余的实 华中科技大学硕士学位论文 现都是利用网络通信机制完成的。相反，消息传递模型具有描述直观、易于理解的 特点，而且适合多种计算模型，因此机群并行编程环境中有一大类是基于消息传递 ( m p ，m e s s a g ep a s s i n g ) 方式的编程环境，例如e x p r e s s 1 9 、p v m 2 0 1 、m p i t 2 ”、p 4 2 2 1 以及现在开始流行的b s p i i b j 2 3 等。 编枵环境和应用程序 s s l ( 单系统映像层) 节点il 节点ll 节点il 节点 硬 件 设 擞佧系统嫠( o s ) ，f 皓 雠 d 黼自m $ 1 m t a g e 辨持握l i 寺 蝴帑互连结构( , n e t w o r ki n t e r c o n n e c t i o n ) 图1 2 工作站机群的软件平台 其中最为流行的m p s ( m e s s a g ep a s s i n gs y s t e m ) 为p v m 和m p i ，两者都可以广 泛的运行在包括m p p 、c l u s t e r s 、n o w e t w o r ko f w o r k s t a t i o n s ) 等分布或并行计算 系统上；二者都对同构和异构性系统提供了充分的支持；都具有丰富的消息传递函 数，以及组操作的功能；随着新的标准的不断完善，m p i 还开始具有任务的动态创 建能力。由于以上的优点，现在大部分的并行机生产商都在其平台上提供了p v m 和m p i ，基于消息传递的程序设计模型也被广泛的采用，而且开发了大量的并行和 分布应用。 1 2 4 p v m 并行虚拟机 p v m 口1 j ”1 ( p a r a l l e lv i s u a lm a c h i n e ) 的开发最早开始于1 9 8 9 年夏天，早前它的 开发队伍包括美国橡树岭国家实验室( o r n l ) 、t e n n e s s e e 大学、e r n o r y 大学以及c m u 等单位，并得到美国能源部、国家科学基金以及田纳西州的资助。p v m 是一套优秀 并行计算工具软件，支持多种体系结构的计算机，像工作站、并行机以及向量机等， 通过网络将它们连起来，形成一台单一的“并行虚拟机”，给用户提供一个功能强大 的分布存储计算机系统。p v m 支持用户采用消息传递方式编写并行程序。p v m 支 持c c + + 和f o r t r a n 语言，由于它是免费的，因此使用范围非常广泛，成为事实上的 消息传递标准。 世导 华中科技大学硕士学位论文 一a图p v 】i 的结构和通信机制 ( 二) x 图1 3p v m 系统结构 p v m 系统( 图1 3 所示) 主要是由两大部分组成。一部分是守护进程，简称p v m d 。 p v m d 始终在后台运行，驻留在的每台结点机上；其中有一个起主导作用称为主 p v m d ，一般位于启动p v m 的结点机上，而其它的称为从p v m d 。p v m d 是消息路由 器和控制器，它提供点到点的连接、任务控制和失败检测服务。每个p v m d 都会在 空闲的时候检测其他p v m d 是否仍在运行。 另一部分是p v m 接口例程库( 1 i b p v m 3 af o rc c + + ，l i b f p v m 3 af o rf o r t r a n ) ，这 个接口库包含应用程序和p v m d 联结的所有函数。接口库函数大致分为四类：虚拟 机控制、任务控制、消息传递和辅助函数。应用程序在作为并行任务执行时，首先 调用库函数并初始化例程库，然后同p v m d 进行通信和系统的协调工作。而t a s k 和 p v m d 之间使用t c p 连接，任务同任务之间默认采用u d p 连接，也可采用t c p 进 行连接。如图1 3 所示为p v m 的结构和通信机制。 p v m 支持多种并行计算模型，包括t r e e 型计算模型、c r o w d 计算模型、m a s t e r s l a v e 模型、基于功能的( f u n c t i o n - b a s e d ) 计算模型。支持多种计算模型大大增强了 p v m 系统的灵活性和功能，特别是当某个模型中的子任务本身可能是用其它模型表 示的并行程序时，可以使用比较灵活的方式进行应用任务的编程。 1 2 5 消息传递语义 在分布式并行计算机系统中，由于各处理机之间通过计算机网络进行连接，处 理机之间没有共享内存供数据传递，因而，分布式并行计算机系统中都通过消息传 华中科技大学硕士学位论文 递的通信机制来完成各处理机之间的数据传递操作。在并行程序设计环境中，依据 处理机间的消息传递机制，必须为程序员提供不同模式的以及多种层次的系统通信 原语，以使用户能方便、灵活地通过此环境进行并行程序设计，完成并行计算任务。 消息传递通信系统是围绕消，亩l , ( m e s s a g e ) 的概念来建立的，在并行程序设计环境 中，一个消息即是由一个发送数据操作w r i t e 所产生的结果，其中数据为一些没有 结构定义的字节流。每个消息由一个读取操作r e a d 来消耗，如果消息字节数大于 读取操作所需要的字节数，则多余字节将被丢掉，反之，则r e a d 读取操作将读取 所有此消息中的字节，同时返回消息字节数不够的指示。 1 2 6 两类通信机制 在并行程序设计环境中提供了多种模式及多种层次的系统通信程序包，其中按 其通信的机制不同，主要分为阻塞( b l o c k i n g ) 通信和非阻塞( n o n b l o c k i n g ) 通信两类。 1 2 6 1 阻塞通信 阻塞通信机制主要指，当调用此通信原语时，用户程序将被挂起，直到相应的 操作完成为止。如果是发送一数据，则数据被从用户程序空间拷贝至系统消息缓冲 区，等待系统根据发送目的结点地址，选择占用相应的通信链路。将数据从系统缓 冲区发送出去之后，用户程序调用才能返回，接着完成后面的操作。 拷 贝 图1 4 阻塞发送机制 拷 贝 如果是接收一数据，则在用户程序调用此系统通信原语之后，直到在本结点系 统消息缓冲区中有相应类型的消息到达之后，该调用函数才能返回，同时，将消息 从系统接收消息缓冲区中拷贝至用户程序空间，其原理如图1 4 所示。 华中科技大学硕士学位论文 12 62 非阻塞通信 对于阻塞通信，接收结点将消息进行缓冲，等待相应的读取操作取走数据消息。 但对于诸如实时处理的系统，这样的通信函数就无法满足实际应用的需要。这些应 用需要在消息到达目标结点之后，立即进行处理。而对于像流水线式地从一结点产 生的数据到另一结点进行的处理，则更需要有消息驱动的通信函数支持。因而，在 并行程序设计环境的消息传递系统中，提供了对于非阻塞通信机制的支持，以满足 消息立即处理的消息驱动需要。 在实时处理系统中，应用程序可以设置一个处理进程用于处理接收到的消息， 而另一部分程序可以继续完成其它的并行计算以及处理其它来源的通信消息，它不 会像阻塞通信那样在调用时被挂起。对于流水线数据的处理，则可以设置处理进程 来接收并处理当前已经到达的通信消息，如果消息未到达，则等待。在这种工作方 式中，不会对结点的正常处理进行挂起，保证了并行计算的流畅进行。 在这种通信模式中，系统接收缓冲区所接收到的消息不会拷贝至用户程序空间 中，而是直接由处理进程进行处理，其原理如图1 5 所示。 非阻塞通信原语为实时处理等追求快速计算的实际应用，在通信系统中提供了 最小的通信延时，满足了快速计算的实际需要。 拷 贝 1 2 7 m p i 消息传递标准 图1 5 非阻塞接收 m p i 2 1 , 2 5 ( m a s s a g ep a s s i n gi m e r f a c e ) 是为了统一不同的m p p 厂家的消息传递的a p i 而制定的工业标准。为了制定消息传递标准，在1 9 9 2 年1 1 月，正式成立了m p j 论坛， 该论坛吸收了大多数并行计算机厂商，许多欧美大学和研究机构以及并行程序开发人 员，大约4 0 个组织的8 0 多人。从1 9 9 3 年3 月，人们开始制定m p i 标准，即对消息传递 接口进行标准化，于1 9 9 4 年颁布了m 口i 一1 。m p i 吸收了当今几乎所有的消息传递系统 指针指向 华中科技大学硕士学位论文 的特色和优点，日益受到并行库丌发人员和广大并行程序设计人员的青睐，成为消息 传递的标准。 m p i 是为了统一和完善消息传递机制开发的一个标准的可移植的并行程序开发 平台。m p i 仅仅只包括一个函数库，这个函数库提供了丰富的点对点通信，集合通信 函数，组，上下文和通信控制器，进程拓扑，允许用户自定义数据类型等众多特征。 l 点对点。m 。缸。l 集i n t 台e r 通f a c 信el 寥p 射脯缸l 集台逦1 8 眵 a d i ( a b s t r a c td e v i c ei a b s t r a c t d e v i c e i 唧圈唧圈 底层通信库 阈 c h - 0 4 l n x b e l 图1 6m p l 分层结构 m p i 库采用分层的结构。最上层是m p i 的a p i ，基本是点到点通信，和在点到点 通信基础上构造的集合通信( c o l l e c t i v ec o m m u n i c a t i o n ) ；中间层是a d i 层( a b s t r a c t d e v i c ei n t e r f a c e ) ，其中d e v i c e 可以简单地理解为某一种底层通信库，a d i 就是对各种 不同的底层通信库的不同接口的统一标准；底层是具体的底层通信库，例如工作站机 群上的p 4 通信库、m p p 等大型机上的n x 库、曙光3 0 0 0 上的b c l 通信库等。分层结构 为m p i 提供了很好的可扩展性。 m p i 的主要目的是提高并行程序的可移植性，m p i 标准的为m p p 开发商提供了一 套定义清楚的接口，因此m p p 提供商可以依托标准开发自己的高效的接口函数，甚至 提供专门的硬件支持。同p v m 日比【2 ，m p i 在动态资源管理方面不如p v m ，p v m 提 供了一系列动态资源管理函数，可以动态地创建进程，而目前m p i 还只能静态的产生 进程，虽然m p l 2 最新规范定义了m p i 可以动态生成进程，但是实现甚少。此外，p v m 在最新的3 4 4 版本中增加了通信上下文，消息信封和带缓冲的事件跟踪机制，使得 p v m 的程序设计更加灵活，因此论文选择p v m 作为并发面向对象模型的支撑实现。 1 3 课题主要研究工作 ( 1 ) 分析和比较现有的各种并发面向对象模型，总结出构建并发面向对象模型 华中科技大学硕士学位论文 常用的关键技术。 ( 2 ) 分析p v m ( m p i ) 结构及其函数库，掌握消息传递编程；并研究多线程模型机 制，研究消息传递库上的安全线程机制，以支持线程级消息传递。 ( 3 ) 建立初步的两级细粒度并发面向对象模型，并在p v m 之上设计简单的对象 分布支撑机制。 ( 4 ) 初步设计和实现所提出的细粒度并发对象模型。 1 4 论文安排 本论文的安排如下： 第二章分析总结并行面向对象模型所具有的关键技术，并分析了几种经典的面 向对象模型及其语言。 第三章根据前面的模型提出了基于消息传递的多线程并发对象模型，描述该模 型的两级并发机制、对象内部线程控制、消息传递库的线程安全问题、运行支持 ( r t s ) 系统、继承异常以及对象间消息通信方式等。 第四章采用类库方法和预处理手段实现前面所提出的模型。阐述了该模型的具 体设计和实现，给出了性能理论分析。 第五章对模型特点分析，总结论文的工作并对今后的研究方向进行了展望。 华中科技大学硕士学位论文 2 并发面向对象关键技术 面向对象模型具有天然的并发性，将并发与面向对象结合起来的并发面向对象模 型，既具有面向对象的特点，又充分发挥并行系统的优点，因此很多人开展此方面的 研究 2 7 - 3 1 】。该章对已有的并发面向对象模型研究的一般问题予以分析总结，主要介绍 并发和面向对象模型结合产生的问题和已有的技术，这包括并发对象间的通信，并发 控制和继承异常等问题，其次，对一些实现的模型系统所用的运行支撑技术进行了总 结，最后介绍一些经典的并发面向对象模型。 2 1 并发与面向对象模型 2 1 1 并发与面向对象的结合途径 设计面向对象并行编程环境，并发与面向对象模型的结合构件并发面向对象模型 是第一步。 目前，并发和面向对象的结合主要有两种途径：在面向对象模型中引进并发机制； 在传统并发模型中引进面向对象思想。 第一种途径设计并发模型是通过构造全新的编译器实现，典型如h y d d 4 1 、p o o l 3 】 等；或扩充现有的顺序面向对象语言，在其中添加描述并行机制来实现。如a c t o r f q 模型、p c + + 【8 】、c c + + 【9 、m e n t a t l 7 1 、c u r r e n t s m a l l t a l k 3 2 等。 采用第二种观点的研究结果一般是基于对象而不是面向对象的并发系统，此类系 统一般通过面向对象的程序设计方法模拟并行模型。典型如p r e s t o 3 3 】以及通过对已有 的并行库进行面向对象扩充，提供类库实现的语言如o o m p i 3 4 1 、p a r a + 十【”1 、d o m e f 3 6 1 等。 第一种途径从对象模型本身出发研究其并发能力。利用面向对象技术刻画客观世 界的良好模型能力和各种重要特性，显式地描述其潜在的并发能力，佼其适合于描述 并发计算。第二种途径则只是采用面向对象技术的某些思想，不是完全的面向对象， 往往舍弃了面向对象的一些重要特性，从而削弱了面向对象的模型能力。 2 1 2 并发面向对象模型分类 通常并发面向对象语言的设计基于正交模型、同构模型、异构模型三种模型。 正交模型中进程对象是相对独立性，易于在顺序面向对象语言基础上进行并发扩 充获得。然而，从并发面向对象程序设计角度看，进程处在对象之外，并发执行位于 华中科技大学硕士学位论文 对象结构之上，因此在进行编程时需要考虑对象和进程的抽象问题，增加了程序员负 担，如基于线程的p r e s t o 等。 同构模型具有简单、易于理解的特点，适于大规模并发处理。支持这种模型的语 言的典型是p o o l t t3 1 。该模型往往是在面向对象构架下考虑并发编程问题，因而可 以克服正交模型的不足，但给予该模型并发面向对象语言设计需要新的编译机制加以 支持。 主动对象和被动对象同时存在的异构模型。如在a c t 十十中，对象分成两类：a c t o r 和被动对象。a c t o r 是一种主动对象，具有并发控制能力，它顺序地接收消息处理；被 动对象就是通常的c + + 对象，它只能作为a c t o r 的局部对象。另一种典型是e i f f e l ” 语言。 异构模型易于与顺序程序设计结合，具有一定的灵活性，从而适合的应用范围较 广。与同构模型类似，它也避免了正交模型之不足，但模型的获得需要设计新的编译 机制加以支持才行。 2 1 3 消息传递方式 在传统的并行程序中，进程间通信通过共享变量或消息传递，而在并发面向对象 语言中，对象间通信只能通过消息传递，因为对象间共享变量破坏了面向对象的封装 特点。并发面向对象语言中，使用三种消息传递方式：同步、异步、f u t u r e 【2 1 方式。 同步方式使用远程过程调用。通信双方必须就消息发送和接收进行同步等待。此 种方式可预测系统计算过程、易于实现和更改，但由于计算和通信过程不能重叠进行， 影响了并发度。p o o l 、h y b r i d 语言就采用这种方式进行对象间的消息传递。 异步方式：发送方发送完消息即可返回继续执行。这样通信和计算过程就重叠起 来，避免了通信双方的等待，提高了并发度。很多模型和语言都采用这种方式。但该 方式使系统不可预测、编程和调试比较困难。 f u t u r e 方式为异步方式的变种，对象a 发送消息给b 后继续执行，但设置一个代 理变量接收b 返回的结果。当对象a 需要结果的时候就访问代理变量。如果有结果 对象a 就返回；否则对象a 阻塞等待返回结果。f u t u r e 方式保留了异步方式较高的 并发度，但是增加了运行时的开销。a b c l l 中的f u t u r e 变量和c o n c u r r e n t s m a l l t a l 妒2 _ 中的c b o x 等就是这种方式。 而实际上很多模型对三种通信方式都有实现，如a c t o r 、c u r r e n ts m a l l t a l k 等。 华中科技大学硕士学位论文 2 1 4 并发控制 在并发面向对象模型中，并发对象需要同步访问，才能保证对象行为的一致性， 保证系统高效有序运作。进行并发控制一般采用两种方法。 一种方法是对象本身不提供并发控制，而是在对象的方法中显式地采用传统的同 步机制f 如信号量、锁机制等) 来控制系统的并发与同步，并发控制可以由不同的对象 完成。此种方法尽管直观却抹煞了对象自治的特点，对象并发控制依赖于其他对象， 而在对象方法中使用锁等机制造成在继承时，子类可能非法进入父类的“临界 区”( c r i t i c a ls e c t i o n ) ，从而对象的并发属性难以继承。 另一种方法把并发与对象结合起来考虑，对象本身对其方法的并发调用进行同步 控制。对象在接收消息时，将根据自身的状态决定是否处理该消息。不同于第一种方 法，该方法从对象模型本身的特点出发考虑对象模型的并发控制，它不仅使得设计的 对象便于使用，而且还有利于对象的重用。 就对象并发控制方式而言可以分为集中式和分散式。 2 1 4 1 集中式控制 集中控制是指把对象的并发控制集中在对象的某一处进行描述。p o o l t 中对象 使用对象体的a n s w e r 方法显式的控制消息接受就属于此种方法。类似的，e i f f e l f ”】 中l i v e ( 即对象体) 并发控制也属于集中式。 另一种集中控制方式是采用一种较抽象的形式( 如：路径表达式) 来描述对象的并 发行为，当对象接收消息时，根据这个抽象的并发描述决定是否处理所接收到的消息， 如c c p p 模型。 另外采用传统的“临界区”同步机制也是属于集中式的。 21 4 2 分散式控制 分散控制方式是把对象的并发控制描述分布到对象的各方法上。 其中一种是在对象各方法的实现中进行同步控制，对象无条件地接受消息，在消 息的处理方法中，根据对象目前的状态决定是等待还是继续执行。例如h y b r i d ，每个 方法都有一个延迟队列和显式代码控制它，只有当延迟队列开放时消息才能执行。 另一种分散控制方式是在对象类中给每个方法定义一个执行条件，当对象接收到 消息时，将根据相应方法的执行条件来决定是否处理该消息，对不满足执行条件的消 息让其等待。如在a c t + + q b ，对象根据当前的行为描述来选择消息。 采用集中还是分散控制方式来实现对象的并发控制其要求不同，前者在设计并发 华中科技大学硕士学位论文 对象类时，必须对对象的并发行为有一个整体的了解并给出完整的描述；而后者不必 掌握对象并发行为的全局知识，而是针对每个被调用方法来考虑对象的并发控制。 2 1 5 对象并发粒度 粒度指的是并发活动中可调度单位的大小以及消息处理的数量。而对象内部是否 允许并发决定了并发的粒度。并发粒度分为三种：细粒度、中粒度、粗粒度。 粗粒度：对象内部不允许并发，对象以f i f o 的结构顺序地从消息队列中选择满 足条件地消息进行处理，对象中只有一个执行线程。p o o l t ，a b c l 1 ，e i 舱l 都属 于这种类型。 中粒度：对象中存在多个执行线程，但在某一时刻只有