（计算机系统结构专业论文）存储一致性模型研究.pdfVIP

存储一致性模型研究 摘要 存储一致性模型( m e m o r yc 0 n s i s t e n c y d e l ) 是共享存储并行计算机中一 个最关键的问题，它不仅影响到并行计算机系统的性能，还影响到并行程序编程 和执行的正确性。现代多线程编程语言中普遍采用虚拟机，类似于共享存储并行 计算机，虚拟机中多个线程闯通过共享对象来进行通信，因此需要一个存储致 性模型来约定多个线程之间通过共享存储器交互的行为规则。随着多线程编程语 言使用越来越广泛和虚拟机技术的不断成熟，存储一致性模型的研究对虚拟杌的 性能提高和正确性保证有重要的理论意义和应用价值。 本文结合仿真器对存储一致性模型进行系统全面的研究。主要研究内容和结 论如下： ( 1 ) 存储一致性模型仿真器的设计与实现：本文通过仿真器来对存储一致 性模型进行量化研究，具体包括：设计并实现了个灵活实用的存储一致性模型 仿真器咖s ；基于该仿真器仿真了不同并行机结构模型下多种存储一致性模型的 行为；针对不同类型的计算问题比较分析了不同的存储一致性模型。 ( 2 ) 面向对象的存储一致性模型的设计与验证：本文结合高级语言的特点 对存储一致性模型进行了研究，具体包括：提出了一种新的面向对象的存储一致 性模型o c ；论述了o c 的主要特性；比较了o c 和其它存储一致性模型； 最后在仿真器m m s 上仿真验证了o c 的行为特点。 ( 3 ) j a v a 存储一致性模型的设计与验证：本文为解决j a v a 语言规范中存储 一致性模型的缺陷对j a v a 存储一致性模型进行了研究，具体包括：将0 c 模型 运用到j a v a 虚拟机中，提出了一种新的j a v a 存储一致性模型l ，j m m ；根据变量 的不同类型分别定义了多线程存储操作之间所应遵循的行为规则；并通过仿真实 验验证了该存储一致性模型的特性。 ( 4 ) 弱一致性模型下的垃圾回收算法的设计与分析：本文为提高弱一致性 模型下虚拟机的执行效率对垃圾回收问题进行了研究，具体包括：充分利用弱一 致性模型的特点提出一种基于跟踪策略的实时分布式垃圾回收算法；描述了单节 点和组节点的垃圾回收策略：分析了该算法的性能和特点；并通过仿真实验验证 了该算法的性能。 本文的主要贡献和创新如下： ( 1 ) 采用了仿真方法系统地对存储一致性模型进行研究，实现了一个存储 一致性模型仿真器m m s ： ( 2 ) 提出了一个新的面向对象的存储一致性模型o c ，该模型具有面向对 象的特色，打破了传统的存储密致性( m e m o f yc o h e 嘣1 c e ) 所要求的全局序的限 制： ( 3 ) 提出了一种新的j a v a 存储一致性模型相对于j a v a 语言规范中的存储 一致性模型该模型不仅保证了j a v a 程序的语义正确性，同时有效提高了j a v a 程 序的运行效率。 关键词：共享存储，存储一致性模型，仿真，j a v a 存储一致性模型，自动内存 管理 ar e s e a r c ho nt h em e m o r y c o n s i s t e n c ym o d e l a b s t r a c t m e m o r yc o n s i s t e n c ym o d e li sam a j o rc o n c e m f o rp a r a l l e lc o r n p u t e rd c s i g na f l d i m p l e m e n t a t i o n t h e 如n c t i o n so fm e m o r yc o n s i s 钯n c ym o d e l so ns h a r e dm e m o r y p a r a l l e lc o m p u t e r sa r em a n i f e s t e di n 柳oa s p e c t s ：p m 酽a m m a b i l i 哆a n dp e r f o n 】m c e v i m l a lm a c h i n e sa r ew i d e l y 璐e di nm o d e mm u l t i 删p r o 萨a m m i n g l a n g u a g e s a s i nas h a r c d m e m o r yp a r a l l e lc o m p u t e r ， v i 咖a lm a c h i n e m u l t i p l e m r e a d s c o m i i i _ u n i c a t i o i l sa r er e a l i 蹈dt h m u g hs h a r c do b j e c t s ，s oam e m o r y c o n s i s t c d n c ym o d e i i sn e c e s s a r yf o rt h ed e f i n i t i o no f 也em l e sf o r 也ei m e r a c t i o nb e t 、w e nt l l et i l r e a d sa n d s h a r c dm e m o r y w i t ht h ew i d ea p p l i c a t i o no fm u l t i t h r e a dp r o f 舢i n g l a n g u a g e s ，s u c h a sj a v a ， t h em e m o wc o n s i s t c n c ym o d e ls h o w sm o r ea f l dn l o r ei m p a c t so n 也ev a l i d i t ya n d p e r f o 姗a n c e o fv i r t i l a lm a c h i n e t h er e s e a r c ha sd e s c d b e di nt h i sp a p e ri so f s i g i l m c 觚c e i nb o t l lt h e 0 陀t i c a la 1 1 da p p l i c 撕o na r e a s t h i sd i s s e n a t i o nf o c l l s e so nt h ed i s c u s s i o no ft h em e m o r yc o n s i s 嘧l c ym o d e l ， a n dt h em a j o ra n a l y s e s 孤df m d 曲g sa r ea sf o l l o w s ： ( 1 ) m 唧o f yc o n s i s t e n c y m o d e ls i m u l a t o r d e s i 印粕di m p l e m e n t a t i o n ：t h e d i s s e r t a t i o n p r o p o s e s an e w 印p r o a c h f o r m e m o r yc o n s i s t e n c y m o d e l r e s e a r c h s i 舢l a t i o n as h a r e dm e m o r ym o d e ls i m u l a t o r i e m m s ，i sd c s i g n e da i l d c o n s t m c t e d t h es i m u l a t o rs i m u l a t e ss e v e r a lm e m o r yc o n s i s t e n c ym o d e l s ，s u c ha s s e q u e n t i a lc o n s i s t e n c y m o d e l ( s c ) ， w e a k c o n s i s t c n c y m o d e l ( w c ) ， r e l e a s e c o n s i s t e n c y m o d e l ( r c ) a n d l a 巧f e l e a s ec o n s i s t e l l c y m o d e l ( l r c ) t h e na c o 唧a r a t i v es f u d yi sc o n d u c t e do nd i f f b r e n tm e m o r yc o n s i s t e n c ym o d e l s ，i n c l u d i n g s c ，w c ，r ca i i dl r c ，i ns u c hp a r a l l e lc o m p u t e ra r c h i t e c t u r e s a ss m pa n dd s m f i n a l l ys i m u l a t i o n sa 心p e r f b r m e do nt h eb e h a v i o r so f d i f i 色r e n tm e m o r yc o n s i s t e n c y m o d e l si ns o l v i n gd i f r e r e n tt y p e so f c o m p u t i n gp m b l e m s ( 2 ) d e s i g na n dv e r i f i c a t i o no fo b j e c t o r i e n t e dm e m o r ym o d c l ：t h i sd i s s e n a t i o n ， c o n s i d e r i n gt h e c h a r a c t e r i s t i c so fh i g h1 e v e l p r o g r a r 眦i n gl a n g u a g e ，c o n d u c t s a c a r c f u l i n v e s t i g a t i o n o ft h em e m o r yc o n s i s t e n c ym o d e l an e wo b j e c t _ o r i e n t e d m e m o r ym o d e l c a l l e do ci s p r e s e n t e d a j l di t ss e m a n t i cn l i ei sd e f i n e d t h e c h a r a c t 喇s t i c so fo ca s c o m p a r c d w i t ho m e rm e m o f yc o n s i s t e n c ym o d e l sa r e d i s c u s s e da n di t sb e h a v i o ri ss i m u l a t e di nt h es i m u l a t o l ( 3 ) d e s i 朗a i l ds i 舢l 撕o no fj a v am e m o r ym o d e l ：t of i xm ep r o b l e mo fj a v a m e m o r ym o d e l i nj a v as p e c 访c a t i o n ，血i sd i s s e r t a t i o ns t u d i e st h ej a v am e m o r ym o d e l a n dp m p o s e san e wj a v am e m o r ym o d e l ，l j m m ，b a s e do nl o c a t i o nc o n s i s t e n c y m o d e la i l do cm o d e l _ t h em l e s0 fj a v am u m t h r e a dm e m o 巧o p e m t i o na r ed e 6 n e d ， i i 忙1 1 l d 证go r 出n a r y v a r i a b i e m l e ，v o l 8 t i l e v a r i a b l e n l l e ，f 试a l v a r ia _ b l er u l ea n d s y n c h r o 芏1 i z em l e t h es i u l a t i o no f t l l i sm c n l o r ym o d e li nt h es i l n u l a t o rm m s v e r i f i e s t l l a tt h en e wm o d e lb o a s t sab e t t e rp e o r m a n c et h a nt h ej a v as p e c i f i c a t i o nm e m o r y m o d e ld o e s ( 4 ) d e s i g n 舡l da n a l y s i so fg 盯b a g ec o l l e c t i o n i nr e l a x e dm e m o r yc o n s i s t e n c y m o d e l ：t bi m p r o v et h ee 衔c i e n c yo f g a r b a g e c o l l e c t i o ni nd i s 砸b u t e ds h a r e dm e m o r y s ”t e m ，t h i sd i s s e 删i o ne x p l o r e st h ed i s 硒b u t e dg a 曲a g cc o l l e c t i o np r o b l e ma 1 1 d p r o p o s e sa 诋c e - b a s e dg a f b a g ec o l l e c t i o na l 卿t h m f o rd s m s y s t c mb a s e d o nr e l a x e d m e m o i ym o d e l _ t h ea l g o r i m mn o t e sm er e f e r e n c e sa m o n ga c t i v eo b j e c t so fe 、，e 叫 n o d ej nd s m s y s 把m ，e n a b l i n gm ea p p j i c a d o np r o c e s sa n dt h ec o l l e c i o np r o c e s st o e x e c u t ec o n c u r r e m l ya n dt h er e l a x e dc o n s i s t e n c ym o d e l sf e a n l r e sa r eu t i l i z e dt o r e d u c ec o m m u n i c a t i o nc o s ta n d r e s p o n s ed e la y f u r t h e m o r e ，t h ee m p l o y m e n to fm o t a b l e s n a ta n dd d t i n s u r e sm ev a l i d i t ya n de 艉c t i v e n e s so f t h ea l g o f i t h mw i t h r e a l 一t i m ea n di n c r e m e n t a lt b a n i i e s t h em a i nc o n t r i b u t i o n so f 也i sp a p e ra r es u m m a f i z e da sf o l l o w s ： ( 1 ) t h ed i s s e r t a t i o np r o p 0 s e san e wa p p r o a c hf o rm e m o r yc o n s i s t e n c ym o d c l r e s e a r c h 啕u a n t i t a t i v es i m u l a t i 彻as h a r e dm e m o r ym o d e ls i m u i a t o r m m s ，i s d e s i g l l e da n dc o n s t n l c t e d ，w h i c hi sad i 腩r e n t 肋mt h et m d i t i o n a lp a r a l l e lc o m p u t e r v i s u n u l a t o l ( 2 ) t h ed i s s e f t a t i o n ，b a s e do nap a n i a lo r d e r p r e s e n t san e wo b j e c t - o r i e n t e d m e m o r y m o d e lc a l j e do c8 n di m p r o v e st h ep e “湘a r i c eo f m u l t i t h r e a d p r o 乎a m ( 3 ) t h ed i s s e r t a t i o np r o p o s e sa n e wj a v am e m o i _ ym o d e l ，l 一丁m m t h i sm o d e l ，b y e x t e n d i n g t h e 0 b j e c tc o n s i s t e n c y t o a d a p t t om ef e a t u r e so fj a v a t e c h n o l o g y g u a r a n t e e st h ev a “d i t yo fj a v am u l t i m r e a dc o d ea 1 1 di m p r o v e sm ep e r f o m l a n c eo f j a v av i r t u a lm a c h i n e k e y w o r d ：s h a r e dm e m o r y ，m e m o r yc o i l s i s t c n c ym o d e l ，s i m u l a t i o n ，j a v a m e m o r ym o d e l ，g a i b a g ec o l l e c t i o n 第1 章绪言 本章摘要 随着处理器性能的不断提高，存储系统已成为计算机系统的性能瓶 颈，因此当代计算机中普遍采用复杂的存储层次结构，共享存储并行计算机中又 进一步扩展了该层次结构。层次结构及复制策略导致了系统中同时存在数据的多 个拷贝，从而产生了复杂的存储一致性问题。为了保证程序的正确性和系统的高 性能，本文从仿真和高级语言应用的角度对存储一致性模型开展了系统的研究。 1 1 并行计算与存储层次 芯片技术的发展为微处理器性能的提高提供了前所未有的动力，为了充分发 挥芯片提供的动力，计算机系统结构也在不断改进优化。在这两者的台力下自 1 9 8 0 年以来微处理器性能基本上维持了每年3 5 至5 5 的提高率，而且在可以 预见的将来微处理器的性能还将按该比率提高1 1 。微处理器性能的提高与并行计 算机的发展两者之间并不是对立的，并行计算和并行计算机都随着微处理器性能 的提高而得到了迅速的发展。 从计算机系统结构的本身发展而言，最关键的因素就是并行f 2 】。所谓“并行” 是指利用时间或空间上的并发性来并行完成计算任务，从而缩短任务的总执行时 间。从系统结构角度来看，“并行”可以体现在不同的层次上。“位”级并行通过 增大数据处理通道宽度来缩短处理时间，如微处理器从4 位、8 位、1 6 位、3 2 位到6 4 位的发展正好体现了“位”级的并行。“指令”级并行通过同时执行多条 指令来缩短程序的执行时间，如流水线技术、超标量技术、动态调度技术等都是 尽可能开发指令间的并发性。但单个线程内的并发性是有限的埘，为了进一步开 发潜在的并发性，必然进入了“系统”级并行。“系统”级并行通过同时执行多 个进程( 或线程) 来开发进程间的并发性，这样的多个进程通常执行在不同的处 理器上，从而进入了并行计算机领域。现代的并行计算机基本上都是采用微处理 器作为其基本构件，处理器之间通过互连网络连接并互相通信协作”。因此并行 第l 页 。中国科学技术大学博士学位论文存储一致性模型研究 计算机系统结构正是在传统的计算机体系结构上增加新的一维，在该维主要解决 节点( 包含微处理器) 间的通信结构问题。对该问题的不同解决方案导致了不同 的并行计算机系统结构，从根本上可以分为共享存储系统和消息传递系统两大 类。 共享存储并行计算机是最基本的一类并行计算机系统，包括对称多处理机系 统( s m p ) 和分布式共享存储系统( d s m ) ，实现了全局共享的单一存储空间， 各处理器通过普通的访存操作完成节点间的通信：而消息传递并行计算机( m p p 和c l u s t e r 等) 则没有可全局访问的存储空间，各处理器通过显示的消息发送 和接收操作完成节点间的通信【5 l 。与消息传递系统相比，共享存储系统由于支持 传统的单地址编程空间，减轻了程序员的编程负担，因此共享存储系统具有较强 的通用性，且可以方便地移植现有的应用软件。正是由于它的易编程性、高吞吐 率等特点在高端和低端应用市场都得到了广泛的应用。然而，在共享存储系统中， 多个处理机对同一地址空问的共享也带来了一些问题，对存储系统提出了更高的 带宽和时延要求，使得存储器系统成为整个系统的瓶颈。下面本文首先以单处理 器的情况为例，说明现代存储系统的结构。 芯片技术的发展在各方面并不都是均衡的，存储芯片( d r a m 芯片) 容量 的发展符合瘴尔定律的描述【6 1 ，基本上每1 8 个月容量翻番，但d i 弧m 访问延迟 的改进则远远滞后，基本上每年的改进比率只有7 左右。从而导致处理器和存 储器之间存在了一个巨大的性能鸿沟【j 】。 1 0 o 蠹 1 1 0 1 lgli 女lsg gg lg ig 时问( 年) 圈1 1 处理器和存储器性能比较 第2 页 第l 章绪言 图1l 显示了存储器和处理器性能的发展曲线。可见两者之间的性能差距越 来越大。为了弥补两者之间的差距并尽可能提供容量大、延迟小的存储系统，现 代计算机系统中都采取了复杂的存储层次结构7 8 ，”。在当代计算机中，存储系统 都按图1 2 所示的那样按层次组织：层次离处理器越近则访问延迟小，容量也较 小；层次离处理器越远则访问延迟大，容量也较大；上层保存的内容是下层保存 内容的子集。 磬i 厘l 茁l 盛l 谁l 足l l 袖l l 层4 b | _ 一容量一 圈1 2 存储器的层次结构 存储层次结构的设计中利用了提高计算机性能的一个关键技术：访问的局部 性【1 ”。因为程序中固有的特性，通常处理器对数据和指令的访问模式都体现出局 部性，包含两个方面：空间局部性和时间局部性。空间局部性是指处理器对指令 或数据的访问在空间上有聚集的特性，也就是说最近访问过的数据的相邻数据在 不久的将来很有可能会被再次访问。时间局部性是指处理器对指令或数据的访问 在时间上有聚集的特性，也就是说最近访问过的数据在不久的将来很有可能会被 再次访问。利用时间局部性在存储层次的上层中保存最近用到的数据，从而在下 次访问时能够快速向处理器提供数据：利用空间局部性将最近用到的数据的相邻 数据也保存到上层。 在共享存储并行计算机系统中，同样也采用了存储层次结构。从处理器的角 度来说，存储层次进一步细化了，c a c h c 层可分为本地c a c h e 和远程c a c h e ，主 存可分为本地主存和全局主存。从数据的角度来说，局部性原理仍然适用，导致 第3 页 中国科学技术大学撙士学位论文存储一致性模型研究 了复制策略的采用。这样同一个数据在存储层次系统中就会有多个拷贝，它们分 别位于不同层次上；本地c a c h e 、主存、多个远程c a c h e ，处理器访问时可以从 离它最近的地方获取数据，从而缩短了访问延迟，同时也减少对互连网络带宽的 争用。图1 3 显示了s t a i l d f b r dd a s h 的存储器逻辑层次结构【1 ”。 田1 3s t a n d f b r dd a s h 的存储层次 1 2 存储一致性模型简介及研究现状 目前共享存储系统都采用高速缓存来缓和由共享引起的冲突以及由存储器 分布引起的长延迟对性能的影响，此外，在规模较大的共享存储系统中，都把共 享存储器分成许多模块并分布于各处理机之中【l ”。存储器的分布会引起非一致的 访存m a ( n 衄u n i f 0 肌m e m o r ya c c e s s ) 问题【1 4 j ，即不同处理器访问同一存储 单元可能有不同的延迟。而高速缓存的使用又带来了高速缓存一致性问题，即如 何保证同一单元在不同高速缓存中的备份数据的一致。访存时间的不一致以及同 一单元的多个备份也破坏了存储访问的不可分割性( a t o m i c i t y ) ，使得同一单元内 容的变化在不同的时刻被不同的处理器所认识，从而影响系统的正确性。为了保 证正确性，需要对访存操作的发生次序进行严格的限制，许多在单处理机中行之 有效的提高性能的技术，如流水、多发射、预取、缓存等，不能在共享存储系统 中盲目使用，这不利于提高性能。因此为了保证系统的正确性，同时能够提高共 享存储系统的性能，对访存操作的次序限制就需要进行深入的研究，这正是存储 一致性模型所要解决的根本问题【l t ”】。 第4 页 第l 章绪言 一个存储一致性模型描述了对共享存储系统中访存事件次序的限制，这些限 制通常体现为要求一个处理器发出的访存操作在什么时刻相对于其他处理器执 行完( 或被其他处理器所接受) 。如顺序一致性模型、弱一致性模型、放松一致件 模型等。存储一致性模型作为程序设计者和系统设计者之间的一个关键界面，当 程序员写程序时，他可以根据存储一致性模型的要求知道程序中每一个访存操作 所产生的行为，从而知道如何设计满足存储一致性模型的正确程序。另一方面， 存储一致性模型应该为系统设计者进行优化留有余地。 对访存操作执行次序的限制只是实现存储一致性模型的手段，丽不是一个存 储一致性模型的本质特征。真正体现存储一致性模型本质的是决定程序执行结果 以及正确程序的编程界面的某种机制，而处理器问的同步方式就是这样一种机 制。同步在共享存储并行程序中起着重要作用。共享存储系统中的多个处理器在 执行并行程序时，虽然可以通过共享存储器进行通信，但还需要进行必要的同步， 以得到确定的结果。各种弱一致性模型正是利用了这一特点，使用专门的同步操 作并在同步点维护一致性，以放松对访存事件次序的限制，并且在大多数情况下 不用专门为了数据一致性而增加同步操作。存储一致性模型通过进程间同步来确 定进程间冲突访问的执行次序。进程间同步规定一个处理器所写的值在何时通过 何种方式传播到其它处理器。不同的存储一致性模型有着各自的用以确定处理器 问访存事件次序的同步机制。 近年来，国内有不少学术机构开展了关于存储一致性模型的研究( 如计算所 f 1 7 】、国防科大、南京航空航天大学1 9 】等) ，他们的研究主要集中在共享存储环 境下存储一致性模型的设计方面，并取得了一些成果， 如文献 1 7 1 中从程序设 计的角度出发提出了一种新的存储一致性模型框架，文献 1 8 】中提出了一种以操 作系统为中心的线程一致性模型，文献1 1 9 中对l c 一致性模型进行了分析。从 本文作者收集的资料来看，目前国内学术界对存储一致性模型的评价及形式化描 述方面的研究不多。 国际上关于存储一致性模型的研究主要是从性能优化和可编程性方面提出 了一些新的存储一致性模型l l ”，包括九十年代提出的释放一致性模型、弱一致性 模型、懒惰释放一致性模型等，同时还有些研究者对不同的存储致性模型进行 了性能评价 2 0 2 ”。近年来有些研究者提出了一些可以应用到多线程程序语义上的 第5 页 中国科学技术大学博士学位论文存储一致性模型研究 存储一致性模型，包括c r f 一致性模型2 2 1 和l o c a t i o n 一致性模型( l o c a t i o n c o f l s i s t e n c v ) 等，这些模型与传统的系统结构级的模型不同，它们主要是从编 译实现的角度出发考虑存储一致性的。 九十年代末期以来结合j a v a 虚拟机的研究，国际上开展了很多对j a v a 存储 一致性模型的研究，包括将其中定义的j a v a 存储一致性模型形式化 2 4 】，将j a v a 存储一致性模型与其他模型进行比较【2 5 1 ，对j a v a 程序的正确性验证研究，以 及提出新的j a v a 存储一致性模型【2 7 】等。近年来，国内有不少学术机构开展了关 于j a v a 虚拟机的研究( 如清华大学0 2 8 1 、软件所、国防科大【3 0 l 、哈工大川等) ， 他们的研究主要是在现有的j a v a 语义下实现高效安全的j a v a 虚拟机，并为此提 出了一些新的实现技术。在国内期刊或会议上还未看到关于j a v a 多线程存储语 义方面的研究结果。 1 。3论文的选题和基本构思 存储一致性模型是共享存储并行计算机中一个最关键的问题，它不仅影响到 并行计算机系统的性能，还影响到并行程序编程和执行的正确性。从1 9 7 9 年 l a m 口o r 提出顺序一致性模型以来，研究人员在2 0 多年的研究过程中提出了很 多存储一致性模型，包括处理器一致性、弱一致性、释放一致性和懒惰释放一致 性等。每种模型都有自己的特点和行为规则，但是到目前为止还没有一种方法能 够对这些存储一致性模型作出全面系统的评价，造成了并行计算机机设计者对存 储一致性模型选择的无所适从。 存储一致性模型的研究己不能仅仅局限于提出新的一致性模型，而应该同时 从存储一致性模型的描述和评价等方面开展理论研究，因此本文作者试图结合仿 真器对存储一致性模型进行系统全面的研究。本文作者一直在存储一致性模型方 面开展研究，主要的研究工作包括通过仿真的手段对存储一致性模型进行评价分 析，设计了一个存储一致性模型仿真器，该仿真器作为本文研究的基础和平台； 随着共享存储系统的发展，多线程编程语言也得到了广泛使用，如j a 、，a 语言， 类似于面向硬件的存储一致性模型，对于这些软件编程语言同样需要存储一致性 模型来约束编译系统( 虚拟机或编译器) 和程序员之间的行为，本文结合应用的 需求提出了一些新的语言级的存储一致性模型，解决了程序语言级存储一致性模 第6 页 第1 章绪言 型中的一些问题：在共享存储系统中的自动垃圾回收是一个非常困难的问题，尤 其是在分布式系统中，而存储一致性模型更增加了该问题的复杂度，本文作者对 陔问题开展了研究，试图为弱一致性模型下自动垃圾回收提供解决方案。 本文下面将用六章来论述关于存储一致性模型的研究。第二章简单介绍了并 行计算机的访存模型及存储一致性模型，描述了典型的存储一致性模型：顺序一 致性模型、弱一致性模型、释放一致性模型、懒惰释放一致性模型；第三章详细 论述了存储一致性模型仿真器m m s 的设计与实现，并对存储一致性模型进行了 性能测试和比较：第四章结合现代程序设计中面向对象的特色，在较高的软件层 次上提出了面向对象的存储一致性模型，该模型可广泛应用到共享存储的编程语 言中：第五章结合j a v a 语言特色，将面向对象的存储一致性模型应用到j a v a 存 储一致性模型中：第六章研究了弱存储一致性模型下共享存储器中的自动内存管 理问题，提出了一种实时分布式垃圾回收算法；第七章对全文进行了总结。 第7 页 第2 章存储一致性模型概述 本章摘要根据通信结构的不同可将并行计算机分为共享存储并行计算机和消 息传递并行计算机，本章描述了共享存储并行计算机中的关键问题，作为后续章 节讨论的基础。其中详细讨论了并行计算机的结构，并行计算机的主要访存模型； 描述了存储一致性模型在共享存储并行计算机中的地位及作用，并介绍了典型存 储一致性模型，包括顺序一致性模型、弱一致性模型、释放一致性横型、懒惰释 放一致性模型等：并就存储一致性与高速缓存一致性的关系进行了论述。 2 1 共享存储并行计算机简介 本节首先简要介绍并行计算机系统结构，随后从并行计算机访问存储器的角 度对并行机进行分类，最后介绍了存储器层次结构的引入所导致的存储一致性问 题。 2 1 1 并行计算机结构 简单地讲，并行计算机就是由多个处理单元( 也称为处理器，或简称为c p u ) 组成的计算机系统，这些处理单元棚互通信和协作能抉速、高效的求解大型复杂 问题【。 并行计算机是相对串行计算机而言的，所谓串行计算机就是只有单个处理单 元顺序执行计算程序的计算机，所以也称为顺序计算机。顺序计算机最早是从位 串行操作到字并行操作、从定点运算到浮点运算改进过来的；然后它逐步演变出 各种并行计算机系统：从顺序标量处理计算机开始，首先用先行技术预取指令， 达到重叠操作实现功能并行；支持功能并行可使用多功能部件和流水线两种方 法：而流水线技术对处理向量数据元素的重复相同的操作表现出强大的威力，从 而产生了向量流水线计算机( 包括存储器到存储器和寄存器到寄存器两种结构) ； 不同于时间上并行的流水线计算机，另分支的并行机是空间上并行的s i m d ( 单 第9 页 中国科学技术大学博士学位论文存储一致性模型研究 指令流多数据流) 并行机，它用同一控制器同步地控制所有处理器阵列执行相同 操作来开发空间上的并行性：如果用不同的控制器异步地控制相应的处理单元执 行各自的操作，则就派生出另一类非常主要的m i m d ( 多指令流多数据流) 并行 机：其中，如果各处理单元通过公用存储器中的共享变量实现相互通信，则就称 为多处理机( m u l t i 口m s s o r s ) ；如果处理单元之间使用消息传递的方式来实现相互 通信，则就称为多计算机( m u l t i c o m p u t e r s ) 。 并行计算机从系统结构上一般可分为6 类 3 2 】：单指令多数据流机s i m d ( s i n g l e - i n s 缸1 l c t i o nm u l t i p l e d a f a ) ： 并行向量处理机p v p ( p a m i l e lv e c t o r p r o c e s s o r ) ；对称多处理机s m p ( s ”吼e 仃i cm u l t i p r o c e s s o r ) ；大规模并行处理机 m p p ( m 嬲s i v c l y p a r a l l e lp r o c e s s o r ) ；工作站机群c o w ( c l l l s t e r o f w b 出诅t i o n ) 和分 布式共享存储d s m ( d i g b u t e ds h 盯e dm e m o r y ) 多处理机。s m i d 计算机多为专 用，其余的5 种均属于多指令多数据流m i m d ( m u l 邱l c i 璐衄l c t i o nm u l t i p l e d a t a ) 计算机。5 种m i m d 并行机的结构模型示于图2 1 【3 3 l 。其中b ( b r i 幢e ) 是存储总 线和i 0 总线间的接口，d i r ( c a c h ed i r e c t o r y ) 是高速缓存目录，i o b ( i ob u s ) 是 i o 总线，l d ( l o c a ld i s k ) 是本地磁盘，m b ( m e m o r yb u s ) 是存储器总线， 小c ( n e t w o r ki n t e r f a c ec i r c i l i n y ) 是网络接口电路，p c ( m i c r o p m c e s s o ra i l dc a c h e ) 是微处理器和高速缓存，s m ( s h a r e dm e m o r y ) 是共享存储器。 “1 m p p 一一一一一一一一一一一1 田2 1 典型并行机结构 其中对称多处理机和分布共享存储多处理机属于共享存储机器范畴，下面将 第1 0 页 第2 章存储一致性模型概述 会分别描述，其它的机器不在本文的描述范围。 ( 1 ) 对称多处理机( s m p ) 对称多处理机的结构示于图2 1 ( b ) 。s g ip o w e rc h a l l e n g e 【”j 和d e ca l p h a 服务器8 4 0 0 f 3 5 】都是这种类型的机器。s m p 系统使用商品微处理器( 具有片上或 外置高速缓存) ，它们经由高速总线( 或交叉开关) 连向共享存储器。这种机器 主要应用于商务，例如数据库、在线事务处理系统和数据仓库等。重要的是系统 是对称的，每个处理器可等同的访问共享存储器、l o 设备和操作系统服务。正 是对称，才能开拓较高的并行度：也正是共享存储，也限制了系统中的处理器不 能太多( 一般少于6 4 个) ，同时总线和交叉开关互连一旦作成也难于扩展。 2 ) 分布共享存储多处理机( d s m ) 分布式共享存储多处理机的结构示于图2 1 ( d ) 。s t a n f o r dd a s h 【1 2 】、c r a y t 3 d 和s g i ，g r a y o r i g i n 2 0 0 0 【3 7 1 等属于此类结构。高速缓存目录d m 用以支持 分布高速缓存的一致性。d s m 和s m p 的主要差别是，d s m 在物理上有分布在 各节点中的局部存储器从而形成了一个共享的存储器。对用户而言，系统硬件和 软件提供了一个单地址的编程空间。d s m 相对于m p p 的优越性是编程较容易。 2 1 2 并行计算机的访存模型 由于本文主要讨论并行计算机的存储问题，下面从系统访问存储器的模式讨 论各种并行计算机系统，它实际揭示了并行计算机的关键系统结构。 ( 1 ) 均匀存储访问模型( u m a ) u m a ( u n i f o mm e m o r ya c c e s s ) 模型是均匀存储访问模型的简称。图2 2 示出了u m a 多处理机模型，其特点是：物理存储器被所有处理器均匀共享； 所有处理器访问任何存储字取相同的时间( 此即均匀存储访问名称的由来) ； 每台处理器可带私有高速缓存；外围设备也可以一定形式共享。这种系统由于 高度共享资源而称为紧耦合系统( t i 曲t l yc o u p l e ds y s t e m ) 。当所有的处理器都 能等同地访问所有i o 设备、能同样地运行执行程序( 如操作系统内核和i o 服 务程序等) 时称为对称多处理机s m p ( s y m m e m cm u l t i p m c e s s o r ) ：如果只有一 台或一组处理器( 称为主处理器) ，它能执行操作系统并能操纵i o ，而其余的处 第l l 页 中国科学技术大学博士学位论文存储一致性模型研究 理器无能力( 称为从处理器) ，只在主处理器的监控之下执行用户代码，这 时称为非对称多处理机。一般而言，u m a 结构适于通用或分时应用。 处理器 系统互连 【( 甚臻，交叉开关，多缎m 络 图2 2 u m a 多处理机模型 ( 2 ) 非均匀存储访问模型( n u m a ) m m a ( n o n u n i f o m lm 锄o r ya c c e s s ) 模型是非均匀存储访问模型的简称 ”o 驯。图2 3 示出了n i n 江a 多处理机模型，其中( a ) 为共享本地存储器的n u m a ； ( b ) 为层次式机群m 7 m a 。m 琢a 的特点是：被共享的存储器在物理上是分 布在所有的处理器中的，其所有本地存储器的集合就组成了全局地址空间；处 理器访问存储器的时间是不一样的；访问本地存储器l m 或群内共享存储器c s m 较快，而访问外地的存储器或全局共享存储器g s m 较幔f 此即非均匀存储访问名 称的由来) ；每台处理器照例可带私有高速缓存，且外设也可以某种形式共享。 全局互连网络 匝 _一1 圊旺圹恒 匝 矗 ；悍 臣) 1 厂芒哥n 1 nj in 旺h ! 塑l口r j 一c s m 群l群 ( a ) 共享本地存储模型( b ) 层次式机群模型 图2 t 3 m m a 多处理机模型 ( 3 ) 全高速缓存访问模型( c o m a ) c 0 m a ( c a c h e o n l ym e m o r ya c c e s s ) 模型是全高速缓存存储访问的简称 m ，4 1 ，矧。图2 4 示出了c o m a 多处理机模型，它是m m a 的一种特例。其特点 第1 2 页 第2 章存储一致性模型概述 是：各处理器节点中没有存储层次结构，全部高速缓存组成了全局地址空间； 利用分布的高速缓存目录d 进行远程高速缓存的访问；c o m a 中的高速缓 存容量一般都大于2 级高速缓存容量：使用c o m a 时，数据开始时可任意分 配，因为在运行时它最终会被迁移到要用到它们的地方。这种结构的机器实例有 瑞舆计算机科学研究所的d d m 和k e n d a hs q u a r cr e s e a r c h 公司的k s r 一1