（计算机系统结构专业论文）基于sci通信的共享虚拟存储系统.pdf

基于s c i 通信的共享虚拟存储系统：摘要 摘要 本文简单而系统的介绍了共享虚拟存储系统( 又称软件分布式共享存储系 统，简称软件d s m ) ，对其通信行为进行了较深入的分析。在可扩展一致性接口 s c i ( s c a l a b l ec o h e r e n ti n t e r f a c e ) 网络上上重新设计实现了共享虚拟存储 系统j i a j i a ，并进一步进行了性能分析，得到了一些有益的结论。 s c i 标准描述了一个物理互连协议以及应用这个互连协议的通讯媒体，它将 通常的主板总线扩展成为全双工、点到点互连结构，提供低延时、高带宽的通 信和分布共享存储映像。 大部分共享虚拟存储系统的通信模块都是用建立在以太网上的s o c k e t 通信 库，底层采用u d p i p 网络协议，软硬件开销都很大，显然，减少共享虚拟存储 系统底层通信开销需要新的更高性能的通信库支持。基于此，我们把s c i 提供 的高性能通信引入到共享虚拟存储系统j i a j i a 中，利用s c i 的编程接口s i s c i 重新设计和实现了j i a j i a 的通信模块：并对实现的系统进行了性能测试和分 析，结果显示，在s c i 网络上j i a j i a 得到了很好的性能。 在对系统性能的测试分析中，本文提出了网络通信对系统性能影响的评价 指标网络加速比。结合a m d a h l 定律，以网络加速比为衡量指标，本文通过统计 应用程序的通信量及消息规模的分布状况，进一步分析程序的行为特征，深入 的分析网络性能对应用程序性能的影响。 相对于网络通信时间，共享虚拟存储系统在小消息上引入的软件开销比大 消息大得多。相对于百兆位以太网，在s c i 网络中，大消息的性能提高也明显 大于小消息，可以断言，随着网络性能的改善，在j i a j i a 现有的底层通信模式 下，小消息的开销将成为j i a j i a 性能提高的主要制约因素。 关键词：共享虚拟存储系统( s v m ) 软件d s m 系统i a j i a 机群s c i 网 络通信 s h a r e dv i r m a lm c m o ws y s t e m sb a s e do ns c ha b s t r a c t s h a r e dv i r t u a lm e m o r y s y s t e m s b a s e do hs c i x i a n b oc a o ( c o m p u t e r s y s t e m s ) d i r e c t e db y ：w e i w uh u t h i s t h e s i s i n t r o d u c e ss v m s y s t e m s ( a l s o k n o w na ss o f t w a r e d i s t r i b u t e ds h a r e dm e m o r vs y s t e m s ，s o f t w a r ed 跏) b r i e f l y ，a n da n a l y z e s i t sb e h a v i o ro fc o m m u n i c a t i o ni n d e p t h t h r o u g hs c i sa p is i s c i ，t h i s t h e s i s r e d e s i g n sj i a j i a s c o m m u n i c a t i o nm o d u l e ，t e s t sa n da n a l y z e s r e a l i z e ds y s t e m sp e r f o r m a n c e ，d r a w ss o m ec o n c l u s i o n s s c is t a n d a r dd e s c r i b e sap h y s i c a li n t e r l i n k a g ep r o t o c o la n dak i n d o fm e d i ab a s e do nt h ep r o t o c 0 1 s c i ( s c a l a b l ec o h e r e n ti n t e r f a c e ) e x t e n d s u s u a lm a i n b o a r db u si n t o f u l l d u p l e xp o i n t t o p o i n t t r a n s m i s s i o n s i n t e r l i n k a g eo n e s ，a n d i to f f e r sl o w d e l a y a n d h i g h b a n d w i d t h c o m m u n i c a t i o na n dd i s t r i b u t e ds h a r i n gm e m o r y - m a p p e d m o s ts v m sc o m m u n i c a t i o nm o d u l eb a s e do nt c p i pw h i c hu s es o c k e t c o m m u n i c a t i o n1 i b r a r y ，o v e r h e a do fs o f t w a r ea n dh a r d w a r ea r ev e r yh u g e a p p a r e n t l y ，r e d u c i n gs v m sc o m m u n i c a t i o no v e r h e a dn e e d s m o r ep e r f o r m a n c e c o m m u n i c a t i o nl i b r a r y s ot h i st h e s i si n t r o d u c e ss c i sh i g hp e r f o r m a n c e c o m m u n i c a t i o nt os v m j i a j i a t h r o u g h s c i sa p i s i s c i 。t h i s t h e s i s r e d e s i g n sj i a j i a sc o m m u n i c a t i o nm o d u l e ，a n dt e s t sa n da n a l y z e sr e a l i z e d s y s t e m sp e r f o r m a n c e ，a sr e s u l t ss h o w ，j i a j i ab a s e do ns c it h r o wo u tv e r y h i g hp e r f o r m a n c e i n p e r f o r m a n c ea n a l y s i s ，t h i s t h e s i sa d v a n c e sai n d e xn a m e d n e t s p e e d u p u s e d b y e s t i m a t e s y s t e mp e r f o r m a n c e w o r k e do n b y c o m m u n i c a t i o n t h i st h e m sa n a l y z e st h eb e h a v i o ra n dc o m m u n i c a t i o n d i s t r i b u t i n g o fb e n c h m a r k sa n d s y s t e mp e r f o r m a n c e w o r k e do n b y p e r f o r m a n c eo fn e t w o r kt h r o u g ha m d a h l1 a wa n dn e t s p e e d u p c o m p a r e dw i t ht i m es p e n do nn e tc o m m u n i c a t i o n ，o v e r h e a do fs v mo n 1 i t t l em e s s a g ei sm u c hl a r g e rt h a nt h a to nl a r g em e s s a g e a n dc o m p a r e d w i t h e t h e r n e t ，t h e e n h a n c e m e n t p e r f o r m a n c e o f l a r g em e s s a g e i s a p p a r e n t l ym o r et h a nt h a to f1 i t t l em e s s a g ei ns c in e t s ot h i st h e s i s a s s e r t st h a ta l o n gw i t ht h ep e r f o r m a n c ee n h a n c e m e n to fn e t w o r k t h e o v e r h e a do f1 i t t l e m e s s a g ew i l lb er e s t r i c t i o no fj i a j i a sp e r f o r m a n e e e n h a n c e m e n ti nj i a j i a sp r e s e n tc o m m u n i c a t i o np a t t e r n k e y w o r d ：s h a r e dv i r t u a lm a m o r y ( s v m ) ，s o f t w a r ed s m ，j i a j i a ，c l u s t e r , s c i n e t w o r kc o m m u n i c a t i o n 声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得 的研究成果。就我所知，除了文中特别加以标注和致谢的地方外，论文中 不包含其他人已经发表或撰写过的研究成果。与我一同工作的同志对本研 究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 作者签名：絮纪飞曼日期：加弓夕2 一p 关于论文使用授权的说明 中国科学院计算技术研究所有权处理、保留送交论文的复印件，允许 论文被查阅和借阅；并可以公布论文的全部或部分内容，可以采用影印、 缩印或其它复制手段保存该论文。 作者签名：铷段翩签名：嘲( 韦武日期：彦一弓、尸 第一章弓i 言 第一章引言 共享虚拟存储系统又称软件分布式共享存储系统( 通常将软件分布式共享存 储系统简称为软件d s m ) ，可以提供给程序员一个共享存储空间的编程模式，其 可编程性明显优于基于消息传递的编程模式。 本章简要介绍了共享虚拟存储系统和基于更高性能通信库的共享虚拟存储 系统的相关研究工作。最后介绍了本文的贡献及论文的组织。 1 1 共享虚拟存储系统的发展 共享虚拟存储系统在消息传递的硬件上提供了一个共享存储编程的抽象，既 保持了硬件的可扩展性又有较好的性能价格比。与消息传递系统相比，共享虚 拟存储系统具有易于编程的优点，但通常通信量明显增大，性能稍差。出于性 能的考虑，当前共享虚拟存储系统的规模一般限制在几十个或上百个节点，无 法支持更大规模的系统。 自从第一个共享虚拟存储系统i 3 的问世以来，共享虚拟存储系统大致 经历了以下三个发展阶段 4 ： 1 初级阶段：在此期间实现的系统都是在单处理器机群上实现的。其主要 特点是：编程模型支持顺序存储器一致性模型，在c a c h e 一致性协议方 面不允许多写。由于顺序一致性模型过分严格，使得因假共享而导致的 进程问通讯量显著增加，严重影响了性能。因此这一阶段的共享虚拟存 储系统只是验证了这种系统的可实现性。 2 ，发展阶段：放松的存储器一致性模型的提出，特别是懒惰释放一致性模 型( l a z y r e l e a s e c o n s i s t e n c y , l r c ) 5 以及多写协议的提出，极大的减 少了各个进程间的通讯量，增大了各进程访存的并行性，显著提高了共 享虚拟存储系统的性能。同时，各种软件优化措施，如预取( p r e f e t c h i n g ) ， 组播( m u l t i c a s t ) ，以及相应的硬件支持，使得新推出的一些共享虚拟存 储系统达到了实用的程度。 3 当前阶段：减少底层通信开销，增加新的更高性能的通信库支持，成为 共享虚拟存储系统研究的热点。随着s m p 系统的流行，基于s m p 桃群 的层次型共享虚拟存储系统也是一个研究热点。同时，为了提供给程序 员一个更加统一的编程界面，一些共享虚拟存储系统增加了对o p e n m p 的支持。 硕士学位论文：基于s c 通信的共享虚拟存储系统 1 2 基于更高性能通信库的共事虚拟存储系统 虽然对共享虚拟存储系统已经进行了十多年的研究，但它的应用远不如 m p i 、p v m 那样广泛，其中一个主要的原因是它的通信开销比较大，直接影响了 性能 1 。大部分共享虚拟存储系统的通信模块都是用建立在以太网上的s o c k e t 通信库，底层采用u d p i p 网络协议，软硬件开销都很大，显然，减少共享虚拟 存储系统底层通信开销需要新的更高性能的通信库支持。 为提高共享虚拟存储系统的性能，在网络通信方面，前人做了很多工作，采 取了多种措施。 s h r i m p a u r c 3 6 ，利用s h r i m p ( s h r i m p ( s c a l a b l e ，h i g hp e r f o r m a n c e 。 r e a l l yi n e x p e n s i v em u l t i p r o c e s s o r ) 是p r i n c e t o n 大学研制的一个基于p c 或工作站多计算机系统) 提供的a u t ou p d a t e 机制，使得对共享数据副本的修 改能自动的更新其h o m e 中对应的内容；n c p 2 1 2 ，巴西r i o d ej a n e i r o 联邦大 学的一个硬件支持共享虚拟存储的系统，它通过一个基于p c i 的协议控制器来 支持d i f f 的操作和预取，在这两个系统中，在系统的网络通信方面都引入硬件 支持，以提高共享虚拟存储系统的性能。 j i a j i a 系统( 在第五章中将比较系统的介绍j i a j i a 系统) 在改善网络通信 方面也做了很多的工作，以提高系统性能。j i a j i a 在m - v i a 上的实现，引入了 用户层、轻量级通信；j i a j i a 在曙光3 0 0 0 上的实现，利用了其高性能的m y n e t 通信网络上的b c l 通信库，这些措施都有效的提高了j i a j i a 系统的性能。 1 3 本文的贡献与组织 可扩展一致性接口s c i 将通常的主板总线扩展成为全双工、点到点互连结 构。保证可扩展性，提供低延时、高带宽的通信。同时，s c i 协议也提供分布共 享的存储映像，并且保证c a c h e 致性( c a c h e 一致性是可选的) ，基于s c i 技 术可以构建分布式共享存储的并行计算机或机群。基于此，我们把s c i 提供的 高性能通信引入到共享虚拟存储系统j i a j i a ( 这里并没有将s c i 提供的分布共 享的存储映像应用于j i a j i a 的共享存储j i a j i a 系统实现共享存储的方式并没 有改变) ，利用s c i 的编程接口s i s c i ，重新设计和实现了j i a j i a 的通信模块， 以期使共享虚拟存储系统获得更高的性能。 1 3 1 本文的贡献 1 对共享虚拟存储系统的通信行为特点进行了较深入的分析 2 利用s c i 的编程接口s i s c i 重新设计和实现了j i a j i a 的通信模块 3 提出了通信性能对系统性能影响的评价指标网络加速比 第一章引言 4 分析了通信性能对不同类型的应用程序的性能影响。 1 3 2 论文的组织 论文分为五章。第一章简单介绍了共享虚拟存储系统和基于更高性能通信库 的共享虚拟存储系统。第二章介绍了共享虚拟存储系统，结合中科院计算所研 制开发的j i a j i a 共享虚拟存储系统，第三章简单介绍了可扩展一致性接口标准 s c i 的提出、系统拓扑结构和协议。重点对共享虚拟存储系统的通信特点进行了 深入的分析。第四章详细介绍了基于s c i 通信的j i a j i a 的通信模块的实现，包 括s c i 编程接口标准s i s c i 、实现方案选择和系统实现。第五章给出了性能测试 和分析。第六章是是本文的结论和进一步的工作。 第二章共享虚拟存储系统肚其通信特点 第二章共享虚拟存储系统及其通信特点 本章首先对共享虚拟存储系统首先做一简单而系统的介绍，而后对其通信特 点做较为深入的分析。 2 1 共享虚拟存储系统 共享虚拟存储系统提供了一种机制，通过这种机制可以让那些原来独立的计 算机共享一个统一的地址空间，通常也把这个空间叫做虚拟共享存储空担 。在 这样的系统里，任何处理机都可以直接访问整个虚拟共享存储空涮的任何位置 6 。在逻辑上，每个处理机都有一个软件分布式共享存储层，它可以实现在不 同的层次上。这个软件分布式共享存储层负责实现局部存储空间和虚拟共享存 储空间之间的地址转换，更重要的是，它必须负责维护整个虚拟共享存储空间 的一致性，也就是说，任何一个处理机的读操作都应该返回这个共享虚拟存储 系统所支持的存储器一致性模型下的最新写的值，而不管这个写操作是由谁来 执行的。这样，从用户的角度看，他们除了需要做一些计算任务的划分和数据 存取的同步外，就像使用传统的串行机器一样方便。 2 1 1 共享虚拟存储系统中的数据一致性 数据一致性问题是共享虚拟存储系统的核心问题，共享虚拟存储系统中数 据一致性的维护直接决定系统的性能及可伸缩性。共享虚拟存储系统中数据一 致性的维护包括虚存的组织方式、采用何种存储一致性模型以及c a c h e 一致性 协议等方面的内容。 1 存储器组织方式 n u m a ( n o n u n i f o r mm e m o r y a c c e s sa r c h i t e c t u r e ) 和c o m a ( c a c h e o n l y m e m o r ya r c h i t e c t u r e ) 是分布式共享存储系统通常采用的两种存储器组织方式。 在n u m a 结构中，共享存储器静态地分布在所有节点上。每一单元有唯一的地 址以及由该地址确定的h o m e 节点。在c o m a 结构中，数据与地址分离，任一单 元没有固定的地址和相应的h o m e ，本地存储器类似于一个大容量的c a c h e 。通 常，在c o m a 中每一单元都有个o w n e r ，而o w n e r 可以根据访存模式在不同的 处理机之问动态地漂移。因此与n u m a 相比，c o m a 可以减少访问不命中率。c o m a 的缺点是在访问不命中时，需要复杂的操作来确定缺失单元的o w n e r 所在位置： 以及在由于本地存储空间不够进行替换时，必须确保被替换掉的单元在系统中 还有备份。 相应地，共享虚拟存储系统也可以分为两类：采用n u m a 结构的系统又称为 硬卜学位论立：綦于s c i 通信的菇享赢拟存能系统 基于宿主( h o m e b a s e d ) 的系统，而采用c o m a 结构的系统又称为无宿主 ( h o m e l e s s ) 的系统。在实现多写技术以及懒惰传播技术的系统中，上述两种结 构都通过t w i n 和d i f f 来检测处理机修改共享页的内容，但它们保存和传播 d i f t 的方式是不一样的。在基于h o m e 的系统中，每一个共享页都有一个崮定 的h o m e 节点。每个处理机都要根据一致性协议的要求( 如在一个同步区间结束 时) 把对h o m e 不在本地的页面的d i f f 传播到h o m e 节点。在缺页时，缺页的处 理机直接从缺失页的h o m e 节点取数。而在无宿主的协议中，写数的处理机一 商保存着它所做的修改，在处理机缺页时，缺页处理机向当前所有持有缺失贝 司写备份的处理机发出取数请求。写数的处理机在收到取数请求时产生d i f f 并把它送到缺页的处理机。 在共享虚拟存储系统中，基于h o m e 的结构与无h o m e 的结构各有长短。基 于h o m e 的系统的优点是：( 1 ) 缺页时可以直接向缺失页的h o m e 节点取数，只 需一个消息来回；而在无h o m e 的系统中缺页时必须向所有当前持有该页可写备 份的处理机取数。( 2 ) ，对h o m e 在本地的页可以直接访问，没有t w i n 和d i f f 的开销。( 3 ) 由于d i f f 及时地送回到h o m e 节点，没有本地d i f f 的积累问题； 而在无h o m e 的系统中每个处理机必须一直保存它所写的值直到下一个全局同步 或本地内存放不下时的垃圾清理( g a r b a g ec o l l e c t ) 。( 4 ) 当本地物理内存放 不下共享页时，可以把部分c a c h e 中的共享页替换回它们的h o m e 节点，易于实 现大内存：而在无h o m e 的系统中，必须有一种机制保证所替换的页不是咳页在 系统中的最后一个备份。( 5 ) 协议简单。 基于h o m e 的系统的缺点是：( 1 ) 把d i f f 写回到h o m e 需要额外的消息。( 2 ) 在缺页时需要取回整个缺失页；而无h o m e 的系统只需取回缺失页的d i f f 。 一些典型的共享虚拟存储系统如m u n i n 7 ，t r e a d m a r k s 和c v m 8 等都采用 无宿主的结构。而j i a j i a 、c a s h m e r e 等系统则采用基于宿主的结构。 2 存储器一致性模型 存储器一致性模型从本质上说是在应用程序与系统之间关于数据一致性的 一种约定。一方面，它指明了系统为程序员提供的编程规范；另一方面，它也 很大程度上制约了系统的性能。在共享虚拟存储系统中，通信开销很大， 妇大 共享粒度引起的假共享问题也很严重实现对访存事件次序要求严格的一致性 模型难以提高系统性能。最早的i v y 系统就是由于实现t i t n 序一致性使得性能 不够理想。 因此，共享虚拟存储系统一般都实现较弱的一致性模型，尤其以释 放一致性模型较为普遍。有的系统甚至实现更弱的一致性模型。如m u n i n 和 【_ r e a d m a r k s 等实现释放一致性模型，m i d w a y 实现单项一致性模型，j i a j i a 实现 域一致性模型。这些弱存储一致性模型的基本思想是：在顺序一致性模型中， 虽然为了保证程序正确执行而对访存事件次序施加了严格的限制，但在大多数 不会引起访存冲突的情况下，这些限制是多余的：因此可以让程序员承担起部 分执行正确性的责任，即在程序中指出需要维护一致性的访存操作，系统只保 证在用户指出的需要保证一致性的地方维护数据一致性，而对用户未加说明的 部分，可以不考虑处理机之间的数据相关。 第一章拱辜虚拟存储系统及其通信特点 目前常见的弱存储一致性模型包括：弱一致性模型( w e a kc o n s i s t e n c y ) 、 释放一致性模型( r e l e a s ec o n s i s t e n c y ) 、急切更新释放一致性模型( e a g e r r e l e a s ec o n s i s t e n c y ) 、懒惰更新释放一致性模型( l a z yr e l e a s ec o n s i s t e n c y ) 、 域一致性模型( s c o p ec o n s i s t e n c ) 、以及单项一致性模型( e n tr yc o n s i s t e n c y ) 等。这些存储一致性模型对访存事件次序的限制不同，因而对程序员的要求以 及所能得到的性能也不一样。存储一致性模型对访存事件次序施加的限制越弱 越有利于提高性能，但编程越难。 一些常见的存储一致性模型对访存事件次序的限制如下： 顺序一致性模型顺序一致性模型( s e q u e n t i a lc o n s i s t e n c y ，简称s t ) 是程序员最乐于接受的存储一致性模型。对于满足顺序一致性的多处理 机中的任一执行，总可以找到同一程序在单机多进程环境下的一个执行 与之对应，使得二者结果相等。在 9 中，s c h e u r i c h 和d u b o i s 给出了 以下满足顺序一致性的条件：在兴事孝结多处理祝乒，者经处理织帮 严格按照访存指令在进程中出现的次亭执行访存指令置在当裁访存指 令彻底完成之韵不能开始执行下一条访存指令。卿次共享存储系统是颧 序一致的。在上述条件中，一个存数操作“彻底完成”是指它所引起的 值的变化已被所有处理机所接受，一个取数操作“彻底完成”是指它所 取回的值己确定且写此值的存数操作己“彻底完成”。 处理机一致性模型由g o o d m a n i 0 提出的处理机一致性( p r o c e s s o r c o n s i s t e n e y ，简称p c ) 比顺序一致性弱，故对于某些会在顺序一致性 条件下能正确执行的程序，在处理机一致条件下执行时可能会导致错误 结果。处理机一致性对访存事件发生次序的限制是 1 1 ：在伍一取搿操 作l o a d 允许被执行之前，瞬有在网一处理机中先予这一l o a d 的取数操 作都已完成；在任一次数操作s t o r e 允许被执行z 裁所存在同一处理 枫中先f 这一s t o r e 的访存操作t 包括l o a d 秘s t o r e ) 都b 完或， 述条件允许s t o r e 之后的l o a d 越过s t o r e 而执行，放松了顺序一致性 模型对访存次序的限制。 弱一致性模型为了采用单处理机下的各种优化技术，提高d s m 系统性 能，晟大限度提高应用程序并行度。d u b o i s 等人于1 9 8 6 年提出弱一致 牲模型u ：该模型将访存操终区分为同步操作积一般操作芳且只要 求在商步操作鼹存储器是保持一致的，弱一致性模型允许据邻的两个同 步操作之阃钓数据操作以任伺次事执行( 对同一存储草元的操作仍要求 按茬游污锐疗，。它包含三重含义：第一，对同步变量的访问是顺序一 致的：第二，在所有先前的写操作完成之前，不能访问同步变量；第i ， 在先前所有同步变量的访问完成前，不能访问( 读或写) 数据。由于在 两个同步操作之间，冬处理机的访存操作可以以乱序方式进行的，例如 新的写操作可以在前一写操作完成之前开始。因此以前用于单处理机系 统的各种优化技术都可以用来提高性能。但是对于并行程序设计者柬 晚，如果一个共享变量被某一进程修改，并被其它进程访问，程序设计 硕士学位论文：基于s c i 通信的菇享虚拟存储系统 者必须用同步操作对此变量的所有访问进行保护。 释放一致性模型释放一致性模型由g h a r a c h o r l o o 等人于1 9 9 0 年提出 1 2 。该模型进一步将同步访问区分为获取访问和释放访问。这种一致 性模型需要满足三个方面的要求：第一，盛劳问共事变量乳迸茬谚矿万 先前的获取访阃都必须或功完浅：第二在a 许释放访涵酶进程先曲 的昕有读写操作都螫须结束：第三同步操佟遵循处理枫一致性或顿孛 _ 致拦。释放一致性模型从三个方面对访存操作的次序作了放松：第一， 同步操作之间的数据操作可以任何次序完成：第二，在释放操作之后的 数据操作不需要等到该释放操作完成后才可执行；第三，获取操作不需 要等到它前面的数据操作完成后才可执行。虽然释放一致性模型规定了 什么数据在什么时间需要完成一致性维护。但是它可以采用不同方式实 专弛，当执行释放操f c 坑t , 处理机在把2 裁对共享变量帕任惘修改传送翻 其它所有的碰堙柳? 厅，矿释放冀劳问许可。这种方式被称为“急切的释 放一致性( e a g e rr e l e a s ec o n s i s t e n c y ，e r c ) ”；当祟必凰祝执行获取 操作时以。扶i 一个释放其访润许司构处理枫那里获褥其_ j c 哇共享数据的 缪改蔗序。这种方式被称为“懒惰的释放一致性( l a z y r e l e a s e c o n s i s t e n c y ，l r c ) ”。 域一致性模型域一致性是j i a j i ad s m 采用的一致性模型，域一致性 由i f t o d e 等人于1 9 9 6 年提出 1 4 ，它是一种介于释放一致性和数据项 一致性之间的一致性模型。它有两个特色：第一，域一致性比懒惰的释 放一致性更加懒惰，在域一致性下，当处理机p 从处理机q 获取锁l 时， 它不需要获得处理机q 已知的所有数据修改操作，它只获得与锁l 相关 的数据修改即可。因此它需要传递的数据量比懒惰的释放一致性更少。 第二，同数据项一致性模型比较，用户可以使用同步变量划定共享的临 界区域( s c o p e ) ，使得同一个同步变量与一个或多个共享变量相关联。 这样可减轻程序设计负担。为了实现域一致性模型必须满足以下两项要 慕；处理机p 在容许获取锁l 之前所有与锁l 相关联的数据相对于锁 l 的马操终必须相对s 链理枫p 完成，( r 有锁l 被释放后相对于锁l 的写操作才被认为已经完成) ；任饲互斥访存操作必须在获取锓操佧磊 巍抗 单项一致性模型单项一致性模型 1 5 ( e n t r yc o n s i s t e n c y ，简称e c ) 通过同步变量和共享对象的紧密联系来进一步放松对访存事件次序的 限制。它要求每一共享对象都和一个同步变量相关连，对任一共享变量 的访问必须由对与该变量关连的同步变量的同步操作来保护。这样，在 对某一同步变量执行获取访问时，只有那些与该同步变量相关连的共享 数据的修改信息被传送。显然单项一致性模型进一步放松了对访存事件 次序的限制，减少了处理机问的数据传送量，从而有利于性能的提高。 但是要求程序设计者为每一共享对象都指定一个同步变量与之关连，大 大增加了程序设计的复杂性。 第一章共享虚拟存储系统及其通信特点 3 高速缓存一致性协议 高速缓存一致性协议是存储一致性模型的具体实现，同时还涉及到存储器 组织以及实现方式等内容，直接决定共享虚拟存储系统的性能。 同样由于共享虚拟存储系统中通信与共享的粒度较大以及通信开销较大等 原因，共享虚拟存储系统的一致性协议与传统的硬件d s m 的c a c h e 一致性协议 有很大不同。主要特点是利用共享虚拟存储系统允许协议比较复杂的的特点， 以部分c p u 开销以及编程的复杂性为代价减少消息个数和消息量。 c a c h e 一致性协议的实质是将新写的值传播给其它处理机的机制。为了实 现高效的传播，必须考虑以下几个方面。 如何传播新值：写使无效与写更新 “写使无效”和“写更新”协议，顾名思义即是对某一共享单元写操作后，或 者使其它处理机的各份无效，或者以新值替换来维护数据一致性。写使无效协 议适用于顺序共享的程序，即在较长时间内只有一个处理机访问一个变量，而 写更新协议适用于紧密共享的程序，即多个处理机在一段时间内频繁地访问同 一变量。硬件d s m 的传播方式一般比较单一，采用写使无效者较多；而共享虚 拟存储系统的传播方式比较灵活，不少系统同时实现两种传播方式，并根据应 用程序的访存行为自动切换。 准产生新值：多写协议与单写协议 传统的共享存储系统通常采用单写协议，即每次只允许一个处理机写某一 共享单位。在软件共享存储系统中，通信开销很大，而且共享粒度通常为一页， 假共享会严重地影响系统的性能。多写协议可以有效地解决假共享问题，它允 许多个处理机同时读或写分布在同一个共享单位的数据，一个处理机对某一单 元的修改对其它处理机来说可以暂时是不可见的，直到同步操作时才把新值传 播给其它处理机，从而避免了不必要的等待。大多数共享虚拟存储系统如 t r e a d m a r k s ，m u n i n ，c v m ，和j i a j i a 等都支持多写协议。 什么时候传播新值：及时传播与延迟传播 共享虚拟存储系统不同于硬件d s m 系统的一个重要的特征是通讯开销大，所 以减少通信次数是提高系统性能的重要途径。因此，在m u n i n 的急切更新释放 一致性中，对共享单元的修改在释放锁操作时才传播到各个处理机，这样就可 以把多个消息合并成一个消息来传播。t r e a d m a r k s 的懒惰更新释放一致性则更 进一步，它不是在释放锁时由写数的处理机把对共享单元的修改传播给其它处 理机，而是把传播新值的操作延迟到获取锁时，而且只传送给需要此数据的处 理机。j i a j i a 1 4 则介于e r c 和l r c 之间。在j i a j i a 中，新值在释放锁时被 写回它的h o m e 节点，并在下次访问时从h o m e 节点传播到请求节点。 新值将会传播给谁：侦听协议与目录协议 在侦听协议中，写数的处理机把新写的值广播给所有处理机，其它处理机 侦听广播，一旦发现被修改数据处于本地c a c h e 中，将立即接收新值。在目录 硕十学位论文：基于s c i 通信的共享虚拟存储系统 协议中，为每一共享单位维持一目录项用于记录与该共享单位有关的信息，例 如哪些处理机持有该共享单位的备份，该共享单位在主存及在被访问节点中的 状态等。当共享页面被修改后，系统根据目录信息向相应的节点发出“写使无 效”或“写更新”信号。j i a j i a 实现的一致性协议最显著的特点是基于锁的机 制，它不用目录信息，而只是通过附带在锁上的w r i t e n o t i c e 来维护一致性。 2 1 2 共享虚拟存储系统的实现方式 我们从实现层次、共享粒度和通信机制三个方面来说明共享虚拟存储系统的实现方式： 1 实现层次 共享虚拟存储系统的实现方式很灵活。一般说来可以在语言、编译器、运 行库、或操作系统等层次上实现共享虚拟存储系统，有的系统甚至通过一些硬 件支持来提高性能。 最早的共享虚拟存储系统i v y 1 6 是在操作系统内实现的。它通过修改操 作系统中的存储管理模块m m u ( m e m o r ym a n a g e m e n tu n i t ) 来建立共享虚拟存储器 和本地存储器之间的联系并维护数据的一致性。因此，i v y 的一致性粒度是一 个虚存页。当处理机访问一个不在本地内存中的共享页时，系统将产生一个缺 页中断。m m u 会根据中断的地址从其它处理机的内存或本地硬盘中取回缺失的 页。这种实现方法的主要缺点是需要修改操作系统，而这对大多数人来说是不 可能的。在操作系统中实现的其它共享虚拟存储系统还包括m u n i n 1 8 ， s o f t f l a s h 1 7 等。从商业的角度来看，修改操作系统的方案都是没有前途的。 当然，如果能在未来的操作系统核心里加入共享虚拟存储层的功能，那是非常 有用的。正是因为这样，在a c m 每两年召开一次的操作系统设计与实现( 0 s d i ) 的会议上，有很多文章讨论这方面的工作。 用户库的共享虚拟存储系统的实现方式通过操作系统提供的界面来检测缺 页和并进行缺页服务。这种方式通常使用m m a p 0 和m p r o t c t e 0 等系统调用来 建立共享虚存的映射关系并修改共享页的访问权限( 可读、可写、不可读不可 写) 。 处理机对共享虚存进行越权访问时，操作系统会产生s i g s e g v 中断信号， 并调用s i g s e g v 中断处理程序。因此，可以通过修改s i g s e g v 中断处理程序来 进行远程取数以及一致性维护。这种方法不用修改操作系统，也不用过多的用 户或编译器参与，是目前主流的共享虚拟存储系统实现方法。一些著名系统， 如t r e a d m a r k s ， c v m 1 9 ，b r a z o s 2 0 ，以及j i a j i a 等，都采用了上述方法。 在语言级实现共享虚拟存储系统的典型代表是八十年代的l i n d a 2 1 和 o r c a 2 2 系统。 这种系统需要用户显式地调用访问共享虚存的函数。如在 l i n d a 中，共享空间被组织成一个“元组池”，用户通过元组的逻辑名来访问池 中的共享元组。l i n d a 提供了元组操作的一些专用算子，如插入、删除、读 取等。l i n d a 维护一致性的方法也很独特：当处理机想要修改某个共享元组时， 必须先把该元组从共享池中删除，修改完后再重新插入。出于语言级实现的系 统需要将所有已有的程序改写，难以被用户接受。所以，自l i n d a 和0 r c a 后。 0 第二章共享虚拟存储系统放其通信特点 近年来已很少有人在这方面进行研究。 也可以通过编译器来实现共享虚拟存储系统，如m i d w a y 2 3 通过修改可执 行代码，在每一个访存操作后插入一段代码进行远程访问及致性维护等操作。 编译器实现的系统的优点是可以支持细粒度和严格的一致性模型，但由于给每 个普通的访存操作都增加了一些额外的开销，使得整个系统的性能反而可能下 降。另外，这种系统的可移植性也不好。通过编译器实现的系统还包括 w i s c o n s i n 实现的b 1 i z z a r d s 系统。通常，编译器可以作为一种辅助手段对 共享虚拟存储系统进行优化。如通过预编译进行从一种界面到另一种界面的转 换，目前已经实现从o p e n m p 的源程序到t r e a d m a r k s 或j i a j i a 源程序的转换。 也可以通过预编译分析并行程序的访存行为，实现预取等优化策略，减少访问 失效等。 当然，也有一些系统结合了上述几种实现方法，如上述m i d w a y 就采用了编 译器和用户库结合的方法。而m u n i n 修改了操作系统，提供了用户库调用，也 有编译器的支持。 2 共享粒度 共享虚拟存储系统的实现层次直接决定了系统的共享粒度。共享存储系统 的共享粒度是指该系统进行远程访问以及一致性维护的单位。硬件d s m 系统一 般都实现细粒度共享，其共享粒度为c a c h e 行。而在共享虚拟存储系统中，由 于实现方式的限制，共享粒度一般为虚存页。 粗粒度的好处是可以充分利用通信带宽，减少维护一致性所需的目录的容 量，以及预取后面要用到的数据等。但大共享粒度大大增加了软件共享存储系 统中假共享发生的概率。尽管延迟传播技术与多写技术能有效地缓解这个问题， 但假共享问题并没有彻底解决。多写协议以及延迟传播技术只能解决同步区间 ( s y n c h r o n i z a t i o ni n t e r v a l ) 内的假共享问题，不能解决跨同步区间的假共享 问题，如在同步区间内，两个处理机可以同时写同一页的不同部分，但到下一 个b a r r i e r 时两个处理机中的备份都要被清除掉( 由于互相都知道对方已写了) ， 过了b a r r i e r 后两个处理机都得重新取页。粗粒度的另外一个问题是内存碎片 的问题，即共享虚拟存储系统中、空间分配的最小单位是页，即使用户只需要 一个字，系统也会分配一页。 为了进一步缓解粗粒度共享所带来的假共享问题，一些系统通过编译或硬 件支持实现了可变的共享粒度，通常是以页为远程访问的单位，但以较小的块 作为一致性维护的单位。如m i d w a y 通过编译支持，t e m p e s t 2 4 通过硬件支持 实现了细粒度的一致性维护。支持细粒度的系统虽不会有假共享和碎片问题但 是是以增加通信次数为代价的，而且还需要编译器或硬件支持，使得系统的可 移植性降低。 3 通信机制 通信开销是共享虚拟存储系统中主要开销之一。研究表明，在典型的通信 协议如u d p 协议中，通信的起始和结束阶段操作系统和协议的延迟占了整个通 硕士学位论文：基于s c i 通信的共享虚拟存储系统 信延迟的很大部分，而真正由硬件传输引起的延迟相对较小，对于小消息尤其 如此。因此，通过用户级消息传递减少操作系统和协议引起的通信开销成为减 少共享虚拟存储系统通信开销的重要手段。 减少通信开销的另一种方法是通过适当的硬件支持。在这方面目前已有不 少工作 2 4 。他们的结果表明，用很小的额外硬件来加速通信是值得的。在 共享虚拟存储系统中通过硬件支持减少通信开销的一个重要方式是用硬件支持 远程访问，如s h r i m p 的自动更新策略 2 5 ，c a s h e m e r e 一2 1 。 2 6 中采用的存储通 道( m e m o r yc h a n n e l ) 等。这样不仅可以减少通信时间，而且可以减少中断远程 处理机的次数。最新公布的用户级通信标准v i a ( v i r t u a l i n t e r f a c e a r c h i t e c t u r e ) 将这一条写进了标准。 此外，由通信引起的中断开销也不可忽视。在共享虚拟存储系统的典型实 现中，一个处理机向另一个处理机发消息时，通常要中断接收消息的处理机。 一些研究结果表明。通过由接收消息的处理机主动查询来避免中断开销可以总 体上减少通信开销。中断和查询到底哪种方法更好目前尚无定论。 2 1 3 共享虚拟存储系统的编程接口 共享虚拟存储系统的编程界面取决于存储一致性模型与实现方式两个方面。 作为应用程序与系统之间关于数据一致方面的一个约定，存