（计算机应用技术专业论文）用软件实现局域网中的内存共享.pdfVIP

m i ! 航空航火人学顺士学位论文 捅要 f 1 征局域网- 用软件实耽内存共事是近年来研究的一个热门课题，实现的系 统其有良好的可扩展性和简单的用户编程接口，并能实现在p c 机组成的局域 网中模拟高性能计算机运行并行科学计算程序。 实现这样的系统关键涉及到三个方面的问题：内存的组织、数据的同步和 节点间通信。内存的组织主要分成共享页面是有宿主节点还是没有宿主节点两 种；数据的同步关键是要保证数据的正确性、完整性和访存的先后顺序，为此 提出的多种存储器一致性模型和高速缓存一致性协议保证了系统中的各节点 按照一定的方式和顺序访问分散在不同机器上的数据：节点间通信是影响系统 性能的一个非常关键的因素，如果通信的性能不好会导致系统的设计目标不能 实现，所以要设计能高效运行的共享内存系统就要设计高效的通信模块。厂 在本文所阐述的系统中，主要采用了基于主节点的内存管理方式，也就是 所有的共享页面都有一个固定的主节点，当页面被修改过后就要把修改的值传 回主节点中，并保证其它机器读取的数据总是最新的；数据同步方面系统采用 了域一致性模型、多写协议，和基于锁的同步方式；在通信方面，本文提出了 一种新的通信模块框架，采用用户级通信的概念，在操作系统和应用程序之间 插桩一个守护进程模块，这个模块专门给应用程序提供通信服务，从最底层的 协议栈中直接为应用程序收发数据，从而大大减少了原来由网络系统软件传递 数据带来的通信开销。 本文先讨论了用软件实现局域网中的共享内存系统要涉及到的相关理论 问题，然后提出了一个具体的实现方案，最后描述了这个系统的实际运行结果 和得出的结论。 、l，t i 关键词共享内存系统，主节点，存储器一致性模型，高速缓存一致性协 议，用户级通信 、7 ：十、， ! ! 墼业茎型塑婪旦! 塑生堑苎皇 a b s t r a c t i m p l e m e n t i n gs o f t w a r es h a r e dm e m o r ys y s t e mi nl a nh a sb e c o m eah o t s u b j e c t i nr e c e n t y e a r s ，t h es y s t e m s h o u l da c h i e v e s c a l a b i l i t y ，s i m p l e p r o g r a m m i n gi n t e r f a c ea n ds h o u l de m u l a t ep a r a l l e lp r o g r a m m i n ge n v i r o n m e n t t h e r ea r et h r e e k e ya s p e c t s i n i m p l e m e n t i n g s u c ha s y s t e m ：m e m o r y o r g a n i z a t io n ，d a t as y n c h r o n i z a t i o na n dc o m m u n i c a t i o n i nt h ef i r s t a s p e c t ，t h e s y s t e mw ec a r r i e do u tt a k e so i lt h eh o m e b a s e dm e m o r yo r g a n i z a t i o ns c h e m e t h i s m e a n st h ed a t am o d i f i e d b y t h en o d eo t h e rt h a nh o m es h o u l d d e l l v e tt h e m o d i f i c a t i o nt ot h eh o m en o d e i nd a t a s y n c h r o n i z a t i o na s p e c t ，w em u s td e f i n e t h e m e m o r ya c c e s ss t y l e ， w h i c hi n c l u d e sm e m o r yc o n s i s t e n c ym o d e la n dc a c h ec o h e r e n c e p r o t o c 0 1 t h e s y s t e mo f t h i st h e s i se m p l o y ss c o p ec o n s i s t e n c ym o d e l ，m u l t i w r i t ea n dl o c k b a s e d c a c h ep r o t o c o l ， i nc o m m u n i c a t i o nm o d u l e ，w ep r o p o s ean e wf r a m e w o r k t h i sf r a m e w o r k e m p l o y st h eu s e rl e v e ln e t w o r k i n gc o n c e p t t h em o d u l eh a sad a e m o na td a t a l i n k l a y e r t oc a t c ht h e p a c k e t sa n dd e l i v e r i tt ot h e a p p l i c a t i o np r o c e s s t h i s m e t h o dw i l lr e d u c et h ec o p yn u m b e ro ft i m e so ft h em e s s a g ea n dt h u si m p r o v et h e c o m m u n i c a t i o n e f f i c i e n c y t h i st h e s i sd e t a i l st h ei m p l e m e n t a t i o no fo u rs o f t w a r es h a r e dm e m o r ys y s t e m a n dt h er e l a t e dt h e o r y a tt h ee n do ft h et h e s i sw ed e s c r i b et h ee v a l u a t i o nr e s u l t s o ft h es y s t e m k e yw o r d s ：s h a r e dm e m o r ys y s t e m s ，h o m en o d e ，m e m o r yc o n s i s t e n c y m o d e l ，c a c h ec o h e r e n c ep r o t o c o l ，u s e rl e v e ln e t w o r k i n g 一一 i 鬣蕊聂蕊匾蕊暑t _ _ 1 丁 两虿一 南i 航空航犬人学顺十。学伉论文 第一章引言 1 1 用软件实现局域网中共享内存系统的基本思想 在局域网环境中t 每台计算机都具有本地的处理器、内存和操作系统，但 每台机器的处理能力和内存都是有限的，如果把这些资源充分的统一利用起 来，就可能实现在局域网中模拟运行以前只有在高性能计算机中才能运行的并 行科学计算程序。 实现内存的共享有很多方法，总共可以分成硬件和软件两大类。其中用硬 件实现的方法主要是用硬件自动维护高速缓存行的数据一致性，而本文重点是 介绍用软件的方法来实现内存共享，所以这里就不介绍硬件实现的方法了。 用软件实现内存共享是从并行处理中发展出来的一项技术，其主要思想是 寻找一种高效的方案，使得原来独立的计算机共享一个逻辑上统一的地址空 间，这个空间通常叫做全局虚拟共享内存空间，系统中的任何一台计算机都可 以访问这个虚拟共享内存空间中的任一地址，而无须考虑该地址实际是哪台机 器中内存的映射。 用软件实现共享内存系统主要的设计原则是：隐藏远程通信机制，保持共 享内存系统的可移植性和应用程序设计的简单性。 在这样的系统中，共享内存就好象是本地共享存储器的扩充，用一个软件 层来提供共享存储器的抽象，由于屏蔽掉了系统中的通信等机制由系统来维 护数据的一致性和完整性，给用户的感觉就好象在访问本地存储器，虽然实际 的数据是分散在局域网中的各个节点上的。 系统实现后还要求对用户有简单的编程接口，即用户只要对现有系统上的 应用程序做简单的修改就可以在新的共享内存系统环境下运行，从而实现方便 的程序移植。 图一是共享内存系统的思想示意图。 从图中可以看出用软件实现的内存共享系统实质上就是把局域网中各节 点的本地内存取出一部分映射到全局共享内存中进行统一管理，节点之间通过 局域网相连，使得共享内存中的数据好象是在同一个内存地址空间中一样。 i j 软什实现埘域硎中晌山存兆卓 恩marem e r n o 吖景m a i n m e m o r y 片n m 删 、心瀑醴心戳 l 全局虚拟共享内存 图一：用软件实现共享内存系统的思想示意图 1 2 课题的研究历史和现状 地内存 用软件实现内存共享系统的概念最早是由k l i 在1 9 8 6 年提出的【1 1 ，在多 年的研究中，出现了一些比较著名的共享存储系统下面就介绍一下其中比较 有代表性的几个： 在早期的共享存储系统中，使用的大多是顺序一致性协议，其中有代表性 的是i v y 、m i r a g e 等。i v y i 】是第一个正式的虚拟共享存储系统。它通过修改操 作系统中的存储管理模块在分布的存储器上建立统一的共享虚拟存储空间，并 实现顺序一致性的一致。隍模型。但正因为采用的是过于严格的顺序一致性模 型，从而严重影响了性能，同时系统也没有很好地解决系统中大粒度( 通常是 存储页) 共享导致的假共享( f a l s es h a r i n g ) 及碎片( f r a g m a t i o n ) 等问题( 这 些问题将在下面的章节中详细讨论) ，导致这些系统只能在实验室使用。 后来的研究学者提出了一些比较放松的一致性模型，这些模型使得共享存 储系统的性能有了很大的提高。这一阶段有代表性的系统主要有m u n i n 2 1 l 4 i 、 t r e a d m a r k s 3 1 、j i a j i a 等。 m u n i n 是基于共享变量的共享存储系统它实现的是释放一致性模型，可 以将每一变量放置在分散的页面上，共享变量用关键宇“s h a r e d “来标记，编 2 ，jt 南京航。e 航大人。、顾十学位论文 汗时缺省的将每个共享变量放在一页上，大的共享变量可以占多页，多个变量 也可以由程序指定放于一页中。由于系统使用的基本上是多处州机模式每一 处理机有一分贝线形地址空洲，以前的多线程程序仅做少量的改动就可以在该 系统中运行。 t r e a d m a r k s 系统是r i c e 大学开发的一个运行库系统，它提供了工作站机 群上的分布共享存储器，实现的是单一存储空间。它运行于u n i x 的用户层， 不需要对内核进行任何修改，使用标准的u n i x 接口、编译器和连接器，在标 准的u d p p 接口上实现机间通信，不需要特定的硬件支持就可以在u n i x 工 作站机群上运行。 j i a j i a 系统是中科院近年来开发的一个可以运行于s u n o s4 1 、s u n o s 5 4 、a i x4 1 、l i n u x 和n t 等操作系统下的虚拟共享内存系统。它采用一种基 于锁的高速缓存一致性协议来实现域存储一致性模型基于锁的协议的设计本 着简单实用的原则，只支持一种存储一致性模型和一种写传播策略，同时采用 多写协议来避免假共享。 近年来随着对称多处理s m p 技术的成熟，基于s m p 的共享存储系统也逐 渐成为热点课题，一些更进一步的优化协议、多线程支持和应用程序的研究也 取得了长足的进展。这些系统采用的实现方式主要是在s m p 系统内部利用硬 件存储共享，而s m p 系统之间利用软件实现存储共享，这样一方面可以利用 s m p 硬件共享的特点提高效率，另一方面可给用户提供统一的共享存储编程 界面。其中有代表性的系统是s h a s t a 、s o f f f l a s h 和s i r o c o o 等。 1 3 本文的结构 本文的主要结构如下： 第一章中主要介绍了用软件实现的共享内存系统的基本思想和课题的研 究状况： 第二章主要阐述了实现共享内存系统中要涉及到的一些关键性的问题： 第三章主要对实现系统中要解决的数据一致性问题做详细分析，主要探讨 了存储一致性模型和高速缓存一致性协议； 第四章介绍了内存共享系统对通信的要求和用户级通信的概念： 在第五章中介绍实现的共享内存系统的整体框架。而第六章则详细阐述了 这个共享内存系统的实现细节； 壤后一章是结论及今后的改进方向。 j j 允忭实现川城刊中的内存j “! 第二章实现共享内存系统要解决的关键问题 在用软件实现共享内存系统的过程中，重点要考虑解决数据一致性、内存 组织方式、高效的通信机制以及用户编程接口等几个问题，本章就主要对这些 问题做详细的讨沦。 2 1 数据一致性问题 数据一致性问题是共享内存系统的核心问题，因为系统中的所有数据是分 散在局域网中各个节点上的，不能象传统的系统管理软件那样来统一管理，从 而可能造成数据访问的不同步，进而使应用程序的运行得到不正确的结果，所 以系统中数据一致性直接决定了系统的正确性、可扩展性及性能。从本质上说， 共享内存系统可以用一下公式表示： 共享内存系统= 数据一致性+ 请求调页机制 数据一致性的维护包括采用何种存储一致性模型、高速缓存一致性协议以 及内存的组织方式等方面的内容。 2 1 1 存储器一致性模型 存储器一致性模型本质上是应用程序与系统之间关于数据一致性的一种 约定，一方面它指明了系统为程序员提供的编程规范，另一方面它也很大程度 上制约了系统的性能。越严格的存储器一致性模型对应用程序员的要求越简 单，但可提供优化的机会就越少，甚至会严重影响性能。为了提高性能，近年 来用软件实现的共享内存系统中普遍采用放松的一致性模型，将普通的访存操 作与同步操作分开处理，甚至将同步操作的不同阶段( 如获取操作和释放操作) 也区分开，这样系统就只要在同步点处维护一致性，而对于普通的访存操作则 无须或很少需要维护一致性，进而有更多的优化机会。 在共享内存系统中普遍采用的一致性模型主要有：顺序一致性模型 ( s e q u e n t i a l l yc o n s i s t e n c y ) 、急切释放一致性模型( e a g e rr e l e a s ec o n s i s t e n c y ， e r c ) 、懒惰释放一致性模型( l a z yr e l e a s ec o n s i s t e n c y ，l r c ) 、域一致性模 型( s c o p ec o n s i s t e n c y ，s c ) 、数据项一致性模型( e n t r yc o n s i s t e n c y ，e c ) 等。 i 瑟蕊嚣函函嚣夏酉丁 甄焉： 4 渤球虮。l 舨犬。学坝 ：学位论文 2 1 2 高速缓存一致性协议 高速缓存一致性协议是保证在系统多个节点中，同一数据的多个副本如何 一致的协议( 要注意的是这晕的高速缓存的含义应浚是从整个系统的角度出发 的，电就是浇系统的高速缓存可能对应某个处理机的本地主存，以下晓到系统 的高速缓存时不注明都是表示这个含义) ，它是存储器一致性模型的具体实现， 同时还涉及到存储器组织以及实现方式等内容系统采用何种协议直接决定了 系统的性能。 高速缓存一致性协议的实质是如何将节点中产生的新值传播给其它处理 机的一种机制。为了实现高效的数据传播，必须考虑以下几对协议： 1 多写协议和单写协议：这一对协议处理的是新值由几个处理机产生的 问题。传统的共享内存系统通常采用单写协议，即每次只允许一个处理机产生 新值。在软件实现的共享内存系统中，共享粒度通常为一页，这将会带来假共 享( 假共享的概念在后面章节解释) 的问题，从而会严重地影响系统的性能。 而多写协议可以有效地解决这个问题，它允许多个处理机同时读或写分布在同 个共享单位而不同单元的数据，一个处理机对某一单元的修改对其它处理机 来说暂时可以是不可见的，直到同步操作时才把新值传播到其它处理机，从而 避免了不必要的等待。如今大多数共享内存系统都支持多写协议。 2 写使无效和写更新协议：这对协议主要是解决新值如何传播的问题。 写使无效和写更新协议，顾名思义即是对某一共享单元写操作后，或者使其它 处理机的备份无效，或者用新值替换旧的数据，以此来维护数据一致性。写使 无效协议适用于顺序共享的程序，即在较长时间内只有一个处理机访问一个共 享单位：而写更新协议适用于紧密共享的程序，即多个处理机在一段时间内频 繁地访问同一共享单位。 3 急切更新和懒惰更新协议：这对协议解决的是新值应该在什么时候传 播的问题。用软件实现的共享内存系统不同于用硬件实现的系统的一个重要的 特征是它的节点间通信开销大，所以减少通信次数是提高系统性能的重要途 径。因此，在急切释放一致性模型( e r c ) 的系统中对共享单元的修改是在 释放锁时才传播到各个处理机，这样就可以把多条消息合并成一条来传播；而 在懒惰释放一致性模型( l r c ) 的系统中则更进一步，它不是在释放锁时传播 新值给其它处理机，而是把传播操作延迟到获取锁时而且只传送给需要此数 据的处理机；基于主节点的系统则介于e r c 和l r c 之间，系统中新值是在释 放锁时被写回它的宿主节点，并在下一次访问时从宿主节点传播到请求节点。 4 侦听协议和目录协议：这对协议解决的是把新值传播给谁的问题。在 侦听协议中，产生新值的节点把新值广擂给所有处理机，其它处理机在侦听中 川i 软州：实l 见肘j 蚓碉中的内仃共卓 旦发现被修改的数据处于本地高速缓存中，就立即接收新值：在目录m 议中， 每共享单位郝有一个目录项记录与浚共享单位有关的信息，当北享页面被修 改后，系统根掘曰录信息向相应的节点发出写使无效或写更新信号：还有一种 是基于锁的一致性机制，它不用目录信息，而只是通过附带在锁上的相应写记 录来维护一致性。 存储器一致性模型和高速缓存一致性协议问题将在下一章中详细讨论。 2 1 3 内存组织方式 共享内存系统的内存组织通常有两种方式：非均匀存储访问结构n u m a ( n o n u n i f o r m m e m o r ya c c e s s ) 和只读高速缓存结构c o m a ( c a c h e 一0 n l v m e m o r ya r c h i t e c t u r e ) 。在n u m a 结构中，共享存储器静态地分布在所有节点 上，每一单元有唯一的地址以及由该地址确定的宿主节点：在c o m a 结构中， 数据与地址分离，任一单元没有固定的地址和对应的宿主，本地存储器类似于 一个大容量的高速缓存。而对于用软件实现的共享内存系统来说也根搌存储 单元有无宿主分成基于宿主( h o m e b a s e d ) 的系统和无宿主( h o m e l e s s ) 的 系统，它们分别相似的对应于c c n u m a ( c a c h e c o h e r e n tn u m a 高速缓存 一致性的n u m a ) 结构和c o m a 结构。 在基于宿主的共享内存系统中，共享内存空间分布在所有节点上，每一个 共享页面都有一个固定且唯一的宿主节点。在访存不命中时，系统将根据访存 单元的地址计算出该单元所在的宿主节点，并向宿主节点发出调页请求，在一 个同步区间结束时，每个处理机都要根据一致性协议的要求把对宿主不在本地 的页面的修改传播到宿主节点。 在无宿主的共享内存系统中，虽然共享内存空间也分布在所有节点中，但 每个共享页并没有一个固定的宿主节点，因此在访问某页发生不命中时，缺页 节点向当前所有持有该页可写备份的节点发出调页请求，产生新值的节点在收 到调页请求时把最新的页面送到缺页的节点中。 由于在c o m a 结构的系统中数据的宿主节点不固定，就要求每个节点记 录整个共享内存空间的信息，从而造成浪费；而在n u m a 结构的系统中每个 节点只要维护与本机有关的页面信息就可以了，所以最近的研究表明，在用软 件实现的共享内存系统中基于宿主的系统性能要优于无宿主的系统。 2 2 内存的共享粒度 共事粒度就是指系统进行远程访问和进行一致性维护时采用的单位。通常 6 南京航空虮凡、# 坝l 一节何沦义 共享粒度分粗粒度和细粒度两种。用硬件实现的共享内存系统中一般 | f 用细粒 度共享，其拭享粒度为硬件的高速缓存行；而用软件实现的系统中由于实现方 式的限制，共享粒度一般为虚存页。 在这里先解释一个假共享( f a l s es h a r i n g ) 的概念，所谓的假共享就是当 两个处理机同时访问逻辑上不相关但即处于一页中的两个变量时，如果至少有 一个操作是写操作，这两个处理机不共享这两个变量，但却共享一页这将有 可能导致该页在两个处理机之l 司乒乓传递的现象。 粗粒度的好处是可以充分利用通信带宽，减少维护一致性所需目录的容 量，以及预取后面要用到的数据等。但系统中的假共享和碎片问题却很严重， 尽管放松的一致性模型与多写技术能有效地缓解这个问题，但假共享问题并没 有彻底解决，而且多写协议本身也带来了其它的开销，如页差和页副本的产生 和保存，垃圾处理等；而相应地如果采用细粒度则不会产生假共享和碎片问题， 但同时是以增加通信次数为代价的，而且还需要编译器或硬件支持，使得系统 的可移植性降低，所以有人提出采用支持可变粒度的系统来折衷，但这种方案 由于自动分析识别技术的不成熟，还不能很方便的被应用，所以目前关于究竟 采用什么粒度最好还没有定论。 2 3 系统的实现层次 在用软件实现的共享内存系统中，实现的层次有四个：语言级、编译器级、 运行库级或操作系统级。实现层次和一致性粒度及编程接口是密切相关的，随 着实现层次抽象程度的提高，可支持的一致性粒度越来越细对应用程序员的 要求也越来越苛刻。 在语言级实现的共享内存系统需要用户显式地调用访问共享内存的函数， 典型代表是八十年代的l i n d a 和o r c a 系统。但由于系统需要将所有已有的程 序改写，难以被用户接受。所以自l i n d a 和o r c a 后近年来已很少有人在这 方面进行研究。 在编译器级实现的共享内存系统种，要在每一个访存操作之后插入一段代 码进行远程访问及一致性维护等操作，所以它可以支持细粒度和严格的一致性 模型，这种系统的典型代表是m i d w a y 和w i s c o n s i n 实现的b l i z z a r d s 系统。 但由于给每个普通的访存操作都增加了一些额外的开销使得整个系统的性能 反而可能下降，而且这种系统的可移植性也不好。当然由于最近提出了一些对 这种系统的优化方案，使得这种方法又重现出生机。 在早期的一些共享内存系统( 如i v y 、m u n i n 、m i r a g e 等) 中，实现是通 软什1 史l 处埘域州q 内存，0 享 过修改操作系统来完成的，主要思想是通过修改操作系统中的存储管理模块来 完成全局虚拟存储器和本地存储器之问f 内一致性。但由于这利t 方法主要缺点是 需要修改操作系统，所以这对大多数人来说是不太容易接受的不过在未来的 操作系统核心驻加入共享虚拟存储层的功能却是前景非常好的一种研究方向。 用运行库来实现共享内存系统是目前被广泛采用的一种方法，它的实现主 要通过操作系统提供的接口来检测缺页并进行调页服务。这种方式通过一些系 统调用( 如m m a p ( ) 等) 来建立全局共享虚存和本地内存的映射关系和修改 共享页的访问权限( 可读，可写等) ，当处理机对共事虚存进行越权访问时， 硬件会产生页违例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 、j i a j i a 、q u a r k 等。 当然在实现中，有很多的系统是把以上几种实现方案结合起来使用的，如 而m u n i n 采用修改操作系统和运行库调用的方法，而m i d w a y 的实现就主要是 编译器和运行库结合的方法等。 2 4 通信机制 在用软件实现的共享内存系统中，通信是系统的主要开销之一。在以前大 部分的系统中，节点间通信主要是采用u d p i p 协议来实现的，但研究表明， 在u d p 协议中，通信的起始和结束阶段操作系统和协议的延迟占了整个通信 延迟的很大部分，而真正由硬件传输引起的延迟相对较小，对于小消息尤其如 此，而且这种通信是不可靠的服务方式，上层的软件必须自己负责处理流量控 制，消息包顺序和错误控制等，这也浪费了大量不必要的时间。所以如何有效 的减少通信的开销是决定共享内存系统性能的一个关键因素。 在过去几年中，人们提出了很多的优化方法来减少共享内存系统的通信开 销，如用多写协议减少通信次数等，但这方面的研究随着存储器一致性协议的 成熟已经很难再大幅度的减少开销了，所以人们就开始考虑从通信技术本身着 手来提高通信性能，于是就提出了用户级通信( u s e rl e v e l n e t w o r k i n g ，u l n ) 的概念，所谓用户级通信就是让用户绕过操作系统，直接通过网络接口进行通 信，从而避免由操作系统的介入带来的软件开销。为此c o m p a q 、i n t e i 和 m i c r o s o h 公司还共同制定了一个用户级通信的标准v i a ( v i r t u a li n t e r f a c e 8 柯求航空航犬人。学硕一i - 学何沦文 a r c h i t e c t m e ) ，这个标准的制定标志蓿用户级通信的研究丌始走向成熟。如何 把用户缎迎信干共享内存系统的很好的结合起来是e 【前研究的一个方向，通过 用户缎通信l j 以把应用枉! 序和底层的通信缓冲区管理结合起来，从而减少在消 息传递时数据在用户空间和操作系统内核空间中的来回拷贝，并减少由此带来 的系统调用等丌销。 关于用户级通信的问题，将在第四章中做详细的阐述。 2 5 用户编程接口 共享内存系统与基于消息传递模型的并行系统比较起来对应用程序编制 的要求要简单的多如它不需要考虑底层数据是如何分布的，也不需要显式地 由用户调用相应的通信函数来院明数据是如何传递的等等，所以共享内存系统 近年来得到了很广泛的研究。 一般说来系统提供的编程界面主要取决于系统采用的存储器致陛模型 与系统的共享粒度、实现层次等几个方面。 由于存储器一致性模型规定了程序员为维护共享数据的一致性所应遵循 的编程规范，所以越严格的存储器一致性模型对程序员的要求越低。顺序一致 性是程序员最欢迎的，它对程序员没有额外的维护数据一致性的要求，而相比 之下，单项一致性则是程序员所一般所难以接受的，释放一致性与域一致性是 比较好的兼顾程序设计与系统性能的存储器一致性模型因为它们所利用的同 步机制是共享存储并行程序本来就需要的。 共享内存系统的编程界面同时也取决于系统的一些具体的实现方式，如在 语言级实现的系统中，用户需要通过显式的函数调用来访问共享存储器，相当 于学习新的语言，比较麻烦；而在编译器级实现的系统中，编译器自动插入有 关语句，对用户的要求较少；在目前普遍采用的运行库实现方式中，系统给用 户分配共享空间以及提供同步的函数调用，一旦共享空间被分配后，用户可以 像访问普通变量那样访问共享变量。 系统的实现方式确定以后，还要考虑并行系统的编程模式，其中主要包括 s p m d ( s i n g l ep r o g r a mm u l t i p l ed a t a ) 以及s m p ( s y m m e t r i cm u l t i p l ep r o c e s s ) 两种。s p m d 就是单程序多数据流模式，其中多个处理机同时执行同一程序， 但操作不同的数据，它是从消息传递编程模式演化过来的；s m p 模式就是对 称多处理机上的编程模式，与这种模式相对应的自动编译技术相对来说比较成 熟一些。最近提出的o p e n m p 标准有统一这些编程接口的趋势。 从以上可以看出，个好的共享内存系统应该提供易于理解的简单编程界 9 软什实现脚域剐中的山打共事 而，小成咳让程序员过多的改变传统的编程方式，以降低编程| j 难度并易于程 序的移植。 蠹翻瓯翮函磊爵r 露一 o 南j 肌空航 人? 顺o 位论文 第三章数据一致性协议 从上一章中可以看出，数据一致性是实现共享内存系统时要解决的核心问 题，所以在这一章中，将重点对这个问题做展开的讨论，其中主要包括存储器 一致性模型和高速缓存一致性协议这两方面内容。 3 1 存储器一致性模型 由于在用软件实现的共享内存系统中，处理机和存储器在空间上的分散性 将会引起访存时间的不一致，而在多个节点中保存的对同一存储单元的多个备 份破坏了传统的访存的不可分割性，使得在同一时刻同一存储单元对不同的处 理机会显示出不同的值，这些都会影响系统的正确性。正是为了保证系统的正 确性和数据的一致性，研究人员提出了多种存储器一致性模型。 由于本文主要是阐述共享内存系统的实现，所以只介绍一下和文章中实现 部分相关的，并且有代表性的几种存储器一致性模型： 3 1 1 顺序一致性模型 顺序一致性模型s c ( s e q u e n t i a l c o n s i s t e n c y ) 是由l a m p o r t 4 】提出的，它的 定义是：若所有的执行结果与所有处理机按某一顺序执行的结果相同，并且各 处理器在此顺序序列中的程序次序与原有程序的次序一致则称该系统为顺序 一致的。 这个一致性模型是最严格的也是程序员最乐于接受的存储器一致性模型， 对于满足顺序一致性模型的多处理机中的任一次执行，总可以找到同一程序在 单机多进程环境下的一次执行与之对应，并且两者的结果一样。 顺序一致性可以表述成两个条件：1 ) 所有的访存操作应该好象是以某种 全序的顺序执行，并且这些执行都是不可分割的；2 ) 每个处理机内的所有访 存操作应该好象是由程序员在程序中指定的顺序来执行。 在顺序一致性模型中，每个处理机内部的访存次序，如w r ，w w ，r r ，r w 都必须保持，其中符号“a b ”表示访存操作b 必须在访存操作a 完成以 后才能执行，w 表示存数操作，r 表示取数操作。 顺序一致性模型是到目前为止被研究得最多的一致性模型，国际上已经提 出大量的优化和改进技术，如软件或硬件预取技术，猜测执行技术乱序执行 技术等，其中的一些技术已经被处理机厂商采用。 i l 曩蓊蓊豳蕊繇匿百厂蕊j ；_ 一 j 戟仆实现局域明中的内存共享 3 1 2 释放一致性模型 在解释释放一致性模型前先给出两个相关的一致性模型旧定义：处理器一 致性( p r o c e s s o rc o n s i s t e n c y p c ) 模型和弱一致性( w e a k c o n s i s t e n c y ，w c ) 模型： 处理机一致性模型要求满足：1 ) 在进行菜读操作之前，必须完成所有以 l 河在同一处理机中的读操作：2 ) 在进行某写操作之前，必须完成所有以前在 同一处理机中读和写操作。 弱一致性模型有三个要求：1 ) 在允许其它任何处理器的读写访问之前， 必须先完成所有的同步访问：2 ) 在允许其它任何处理器的同步访问之前，必 须先完成所有的读写访问；3 ) 各同步访问间满足顺序一致性。 在弱一致性模型的基础上，o h a r a c h o r l o o 等又进一步提出了释放一致性模 型r c ( r e l e a s ec o n s i s t e n c y ) p j 。它把同步操作进一步划分为获取操作a c q u i r e 和释放操作r e l e a s e 。a c q u i r e 用于获取对某些共享存储单元的独占访问权，而 r e l e a s e j 用于释放这种访问权。释放一致性模型对访存事件的发生次序作如 下限制：1 ) 在任一普通访存操作允许被执行之前，所有在同一处理机中先于 这一访存操作的获取操作a c q u i r e 都己完成：2 ) 在任一释放操作r e l e a s e 允许被 执行之前，所有在同一处理机中先于这- - r e l e a s e 的普通访存操作都已完成；3 ) 同步操作的执行满足顺序一致性条件。 在释放一致性模型中，不仅在同步操作之间的普通访存操作可以以任何次 序执行，而且在获取操作之前的普通访存操作和获取操作之间，以及释放操作 之后的普通访存操作与该释放操作之间也没有限制，可以以任何次序执行，而 更进一步，在r c p c 一致性模型( p c 表示同步操作的执行要满足处理机一致性) 下，不同的r e l e a s e 和a c q u i r e 对之间也没有限制，这是因为r e l e a s e 操作相当于 存数操作，而a c q u i r e 操作相当于取数操作，而在处理机一致性模型下，w r 访存次序时可以违反的，这些条件的放松会使系统的性能提高很多。 而在用软件实现的共享内存系统中，为了减少通信和数据交换的开销，人 们又在释放一致性模型的基础上提出了急切释放一致性模型e r c ( e a g e r r e l e a s ec o n s i s t e n c y ) 和懒惰释放一致性模型l r c ( l a z yr e l e a s ec o n s i s t e n c y ) 。 急切释放一致性是一个基于页的，采用多写，写更新的一致性模型。在这 个模型中，临界区内的多个存数操作在执行r e l e a s e 操作之前( 即退出临界区 之前) 进行。采用急切释放一致性模型的典型系统是m u n i n 系统。 懒惰释放一致性是一个基于页的，采用多写，写使无效的一致性模型。在 此模型中，由一个处理机对某单元的存数操作并不是由此处理机主动地传播到 所有共享该单元的其它处理机中，而是在其它处理机要用到此处理机所写的数 1 2 晰京航空航犬人学坝十学似论文 据时( 即其它处理帆执行a c q u i r e 操作时) 再向此处理机索取恢单元的最新备 份，这样可以进一步减少逊信量。采用懒惰释放一致性模型的典型系统是 t r e a d m a r k s 系统。 3 1 3 域一致性模型 域一致性模型( s c o p ec o n s i s t e n c y ，s c c ) 1 6 】对访存事件次序的要求比懒惰 释放一致性更松。在l r c 中，当处理机p 从处理机q 获得锁l 时，处理机q 所看到的修改都被传给处理机p ；但在s c c 中，只有在用锁l 保护起来的区域 中所做的修改才会传送给p 。总的来浇这个模型的基本思想就是用一个叫一致 性范围( c o n s i s t e n c ys c o p e ) 的概念来隐式地在共享数据和同步对象之间建立 一种联系，使得一个同步对象能保护多个共享数据，一个数据可以由多个同步 对象来保护，从而很大程度上减少了通信的次数提高了性能。 s c c 对事件次序作如下限制：1 ) 处理机p 上一个一致性范围的新的会话 被允许打开之前，所有以前相对于这个一致性范围已经执行的写操作都必须相 对于处理机p 执行完；2 ) 处理机p 发出的一个访存操作在被允许执行之前， 所有以前处理机p 企图打开的会话都必须已经成功的打开。 实现这种模型的典型例子是p r i n c e t o n 大学的s h r i m p 系统。本文下面要 介绍的系统中就是采用的这个模型，模型的具体实现将在后面章节详细介绍。 3 2 高速缓存一致性协议 高速缓存的使用可以减少由处理机和存储器的空间分布而引起的访存延 迟，减少多个处理机在访问共享存储器时的冲突，而由此产生的多个处理机中 数据的一致性问题也影响到了系统的正确性，所以保证数据正确性的高速缓存 一致性协议的实现是实现系统的一个关键问题。 高速缓存一致性协议是存储一致性模型的具体实现，协议的实质是如何把 一个处理机产生的新值传播给其它处理机，并确保所有处理机看到的共享数据 是一致的这样一种机制。下面就来介绍其中的多写协议、写使无效和写更新协 议、协议的延迟传播、以及侦听和基于目录的协议： 3 2 1 多写协议 为了解决假菇享产生的严重影响系统性能的问题，人们提出了多写协泌r 协议允许多个处理机同时读写分布在同一共享单位的不同单元，一个处理机对 某个单元的修改对其它处理机是暂时不可见的，直到同步操作时才把新值传给 1 3 4 kp l ：实现局城州。l ，的内存共! # 其它处理机。 多写m 议自从提出以柬得到了广泛的应用，它的主要优点有：由于允许多 个处耻射l 并发剥同一个一致性单位进行读写，从而减少了由“写一写”假共享 和“写一读”假共享所引起的通信开销，通信粒度通常是修改过的页差，而页 差一般比一页要小很多，所以即使在假共享很少发生的应用中也会极大的减少 通信量。由于允许多个处理机并发写，不需要等所有权获得后才写，就更进一 步放松了处理机内部的访存次序。采用这个协议的系统主要有t r e a d m a r k s ， c v m ，q u a r k s ，j i a j i a 等。 3 2 2 写使无效与写更新协议 根据新值是如何传播的，可以把高速缓存一致性协议分成写使无效( w r i t e i n v a l i d a t e ) 协议和写更新( w r i t eu p d a t e ) 协议，在写使无效协议中一个处理 机修改数据后把其它处理机上的各份置为无效，下次有访问该数据的操作发生 时就重新加载该页面：而写更新协议中被修改的最新协议会立即传播到所有拥 有该数据备份的处理机中。 这两种协议各有利弊，适用的范围也不同。写更新协议中假共享问题比较 严重，因为不管共享数据是否真的被其它处理机共享，数据所在的一致性单元 都可能被置为无效，所以它更适用于顺序共享的程序，即在较长时间内只有一 个处理机访问一个变量的情况；而写更新协议要不断地把新值传给其它所有拥 有备份的处理机，对那些虽然有备份但不再会用到的处理机来说将是一种浪 费，所以它适用于紧密共享的程序，即多个处理机在一段时间内频繁地访问同 一变量的情况。所以有时候可以把两种协议结合起来，根据数据的访问频率来 调整是用写使无效还是用写更新协议可以使系统达到比较好的性能。 3 2 3 一致性协议的延迟传播 为了在采用急切释放和懒惰释放协议之间找到一种折衷方案，当系统用写 使无效协议时，在处理机收到使无效的消息后不是立即执行相应的无效操作， 而是将它们存储并等到自己执行下一个同步获取操作时才执行这个同步获取 操作并不一定与前面发出使无效消息的释放操作相对应。为了让发出使无效消 息的处理机能继续执行，收到使无效消息的处理机应该立即送回应答消息。这 种将使无效消息缓存一段时间的方法，可以在某种程度上避免可能发生的收到 无效消息和执行下一个同步获取操作之间的假共享。 1 4 一h 京航空航火人。顷十学位论文 3 2 4 同步机构的几种组织方法 1 侦听协议：当某个处理机对兆享堆元的访问不命中而引起数据不一致 时，就向其它所有处理机发出广播请求，系统中所有处理机都在侦听广播当 听到广播中涉及到的共享单元在本地的高速缓存中有备份时，就执行相应的同 步操作。 由于协议采用广播机制，所以它适用于总线连接的系统并且每个处理机 只需要维护局部的高速缓存状态信息，对存储空间的要求很小。但同时由于是 依赖于广播和总线，所以对总线系统的依赖也很大，如总线竞争使得同一时刻 只有一个处理机可以使用总线，所有处理机要经过总线的仲裁才能得到总线， 总线加长后传播速度会下降等。所以这种方式只能适用于规模较小的系统，而 用网络连接的一些较大的系统将使用以下两种机制。 2 基于目录的协议：在这种协议中，每个存储单位都有一个目录项与之 对应，目录项记录了存储单位在整个系统的各个高速缓存中的状态，包括哪些 处理机中含有存储单位的备份，存储单位是否处于“脏”状态等等。当某个处 理机发生缺页时就可以根据目录中的内容向拥有该存储单位备份的处理机发 出写使无效或写更新的信号，从而避免广播。 为了提高搜索目录的效率，人们提出了多种目录结构，这些结构可以是静 态的也可以是动态的，可以是集中的也可以是分布的。下面是其中一些有代表 性的目录结构： 位向量目录：在这种目录结构中，每个目录项都有一个n + l 位的向量， 其中n 为系统中处理机的个数，第n + l 位是修改位，记录该存储单位是否被 写过。如果目录的第i 位被置为“1 ”，则表示此存储单位在第i 个处理机上有 备份，如果改写位被置为“1 ”，则表示此时只有一个处理机正在修改此存储单 位。但是这种目录所需要的目录存储器容量随着处理机数n 的增加将以n 2 的 速度增加，所以不适合于n 很大的情况； 有限目录：这种协议主要是考虑到系统中的处理机具有局部性，即在任何 给定的时间间隔内，只有一小部分处理机访问某些给定的存储单元，所以有限 目录已经足以应付这个小的工作处理机组了，于是就限定某个存储单位只能同 时最多被n 个处理机共享，然后只要用有限个指针记录当前有备份的处理机 这样目录容量的增长就是线性的了。当共享某个存储单位的处理机不超过n 时，这种方法和位向量目录是相似的但当共享某个存储单位的处理机超过n 时就会相应用某种机制来限制指针溢出的问题。 链式目录：链式目录不但有有限目录的可扩展性而且因为它是通过维护 一个指针链来跟踪共享数据拷贝的所以也不限制共享数据块拷贝的数目。在 is 4