（计算机科学与技术专业论文）基于linux环境下的分布式存储系统的研究与实现.pdf

国舫科学技术大学研究生院学位论文 摘要 在过去的二十年里，分布式系统已经成为一种重要的并行计算平台。虚拟共享存储 系统( s v m ) 用软件的方式在物理分布的存储器上实现了一个逻辑上统一的虚拟共享 存储空间。它结合了m p p 和s m p 的优点，具有良好的可扩展性和可编程性。本文就是 在l i n u x 环境下对分布式共享存储系统进行研究。 在s v m 中，存储一致性是关键问题之一。我们在仔细分析各种存储一致性模型的 基础上，提出了种以操作系统为中心的存储一致性模型线程一致性模型( t c ) 。 线程致性模型通过将并行程序执行过程中的同步点和线程状态结合起来，从操作系统 的角度来观察和限制存储访问的正确顺序，从而保证了并行程序的正确执行。线程致 性模型将执行体管理和存储管理这两个方面有机地结合在一起，有利于并行程序数据局 部性的开发。另外，多线程机制的一个显著优势就是能把计算和通信重叠起来，从而有 效地隐藏通信延迟，提高系统性能。 最后，我们提出了基于线程一致性模型的多线内核虚拟共享存储系统m t k 的实现 方案，并对其系统开销进行了分析。系统开销分析表明，线程一致性模型可以有效的提 高虚拟共享存储系统的性能。 j 。， 关键- - t - ：虚拟分布式共享荐磊系统，l i n 线程一蠢衽模型，线程状i 数据局柞往， 多线程机制，m t k ，系统开销。 v 。 第1 页 国防科学技术大学研究生院学位论文 a b s t r a c t d u r i n g t h el a s tt w e n t yy e a r s ，d i s t r i b u t e ds y s t e mh a se v o l v e dt ob eo n eo f t h em o s t u s e f u l p a r a l l e lc o m p u t i n gp a n e l s s h a r e d v i r t u a l m e m o r ys y s t e mb u i l d so n es v ml a y e ro v e r p h y s i c a u yd i s t r i b u t e dm e m o r yt o f o r mo n el o g i c a l l yu n i f o r ms h a r e dv i r t u a l s p a c e s v m c o m b i n e st h e a d v a n t a g e s o fm p pa n d s m p ，p r o v i d e d w i t h g o o ds c a l a b i l i t y a n d p r o g r a m m a b i l i t y t h i sp a p e rd i s c u s s e st h ei n v e s t i g a t i o ni n t os v m u n d e rl i n u xe n v i r o n m e n t m e m o r yc o n s i s t e n c yi s o n eo ft h e p i v o t a lp r o b l e m si ns v m b a s e do nt h ed e t a i l e d a n a l y s i s o fo t h e r m e m o r yc o n s i s t e n c ym o d e l s ，w ep u t f o r t ho n eo s c e n t r i ct h r e a d c o n s i s t e n c ym o d e l ( t c ) b ya s s o c i a t i n gt h es y n c h r o n i z a t i o np o i n to fp r o c e s sw i t ht h r e a d s t a t u s ，t cl o o k si n t oa n dc o n f i n e st h ec o r r e c ts e q u e n c eo f m e m o r y a c c e s se v e n 括f r o mt h eo s a s p e c tt o e n s u r ep r o g r a m sc o r r e c tr u r m i n g t co r g a n i c a l l ya s s o c i a t e sp r o c e s sm a n a g e m e n t m o d u l ew i t hm e m o r y m a n a g e m e n tm o d u l e t h e r e f o r e ，i ti sp r o p i t i o u st oe x p l o i td a t al o c a l i t y o f p a r a l l e ip r o g r a m s i na d d i t i o n ，m u l t i t h r e a d sm e c h a n i s mc a no v e d a pt h ec o m m u n i c a t i o n a n d c o m p u t i n g i t e f f e c t i v e l yw r a p s c o m m u n i c a t i o n l a t e n c y a n d i m p r o v e ss y s t e m p e r f o r m a n c e f i n a l l y ，w ei m p l e m e n t am u l t i t h r e a d sk e r n e ls v m s y s t e mm t k b a s e do nt c m o d e l ，a n d a n a l y z ei t ss y s t e mo v e r h e a d t h ea n a l y s i s e ss h o w t h a tt cc a ne f f i c i e n t l yi m p r o v es v m s p e r f o r m a n c e k e y w o r d ：s v m ，l i n u x ，t c ，t h r e a ds t a t u s ，d a t al o c a l i t y ，m u l t i p l e - t h r e a d sa r c h i t e c t u r e ， m t k ，s y s t e m o v e r h e a d 国防科学技术大学研究生院学位论文 第一章绪论 1 1科学计算和并行计算机的发展 一切技术创造活动，都是适应社会的某种需求( 其中也包 括科学技术自身发展的需求) ，进行的有明确目标指向的 活动。自然辩证法概论 在核物理实验、天气预报、天体研究、基因分析等等科学领域以及商业应用中，存 在着大量的数据计算，它们对并行处理提出越来越高的要求。显然，单纯依靠提高芯片 主频的方法来来设计更快的并行计算机，已远远不能适应这种需要。大规模并行处理机 系统( m a s s i v e l yp a r a l l e lp r o c e s s i n g ，简称m p p ) 应运而生。芯片技术、快速通信技术 以及互连技术，使得m p p 系统获得了长足的发展。 m p p 系统虽具有明显的可扩展性，但是每个处理器都有自己独立的存储地址空间， 处理器之间的通信采用消息传递模型，可编程性差；对称多处理机( s y m m e t r i cm u l t i p l e p r o c e s s i n g ，简称s m p ) 系统采用集中式共享主存结构，具有全局的物理地址空间( 如 图1 1 所示) 。简单的对内存单元的读写即隐含了多个处理器间的通信，这和传统的程 序设计模型基本相同，可编程性好。但s m p 的处理器数目受限于其集中共享主存结构 所带来的访存瓶颈，因而无法达到更高的性能。结合s m p 和m p p 的优点，产生了分布 共享主存结构( d i s t r i b u t e ds h a r e dm e m o r y ，简称d s m ) 的并行计算机系统f 如网 2 所示) 。 图1 1s m p 的基本结构 国防科学技术大学研究生院学位论文 图1 2d s m 的基本结构 和m p p 系统一样，d s m 系统的存储器在物理上也是分布的，但它在逻辑上提供了 一个统一地共享存储空间。d s m 在可扩展性上可以和m p p 相比拟，同时又具有良好的 可编程性。 通常，我们所说的d s m 系统的c a c h e 一致性是由硬件实现的，比如c c - - n u m a ， 它具有统一的物理地址空间。但是，采用硬件实现d s m 系统，性价比比较低，因此， 人们自然想到用软件去实现它。软件实现的方法就是通过软件在物理分布的存储器上构 筑一个逻辑上统一的虚地址空间，这样构成的d s m 系统称为虚共享系统( s h a r e dv i r t u a l m e m o r ys y s t e m ，简称s v m ) ，有时也称作软件实现的d s m 系统。这种方法不仅可以 用来在工作站集群系统上实现虚共享系统，而且也可以用来在分布主存、独立编址的 m p p 上实现虚共享系统。一个典型的s v m 的结构如图1 3 所示。 图1 3s v m 的基本结构 1 2国际国内虚拟分布式共享存储系统的研究概况 1 2 1s v m 的发展历史 自k a il i 博士于1 9 8 6 年在其博士论文“s h a r e dv i r t u a lm e m o r yo nl o o s e l yc o u p l e d 第2 页 国防科学技术大学研究生院学位论文 m u | t i p r o c e s s o r s ”中首次提出虚拟共享存储的概念以来，s v m 发展迅速。至今，s v m 的发展可以划分为三个阶段： 1 1 9 8 6 1 9 9 0 ，历史阶段。在此期间实现的系统都是在基于单c p u 的结点上采用 顺序存储一致性模型，如i v y ，m i r a g e ，e m e r a l d 等。由于顺序一致性模型过于严 格，使得假共享( f a u l s es h a r i n g ) 和碎片( f r a g m e n t a t i o n ) 问题十分突出，从而 严重影响了系统性能，因此这一阶段的系统仅限于在实验室中使用。 2 1 9 9 0 1 9 9 6 ，复兴阶段。随着释放一致性模型的广泛提出，特别是1 9 9 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 ) 的提出，给s v m 的研究 带来了新的曙光。自此许多大学和科研机构分别推出了自己的s v m 系统。如 m u n i n ，t r e a d m a r k s ，m i d w a y ，c v m 和j i a j i a 等。与第一阶段相比，这一时期 的系统也是基于单c p u 结点，但由于采用了释放一致性模型，性能有了明显提 高，不过和消息传递编程模型相比，仍有一定的差距。 3 1 9 9 6 2 0 0 1 ，当今阶段。随着s m p 的流行，以s m p 为结点的层次型虚拟共享存 储系统逐渐成为研究的热点。在超结点s m p 内部，采用总线监听来维护c a c h e 一致性，超结点间则通过目录协议来维护c a c h e 致性。早期有人通过模拟进行 了一些研究，自1 9 9 7 年以来已实现了三个原型系统，分别为d e cw i l l 的s h a s t a 、 r o c h e s t e r 大学的c a s h m e r e 2 l 、和s t a n f o r d 的s o f f l a s h 。 1 2 2 s v m 最近的研究进展 1 编程方法的发展 任何一个系统的优劣最终都要由应用程序来检验，虽然s v m 系统提出的目标是使 得已有的共享存储程序可以不加任何修改地继续运行，但由于以前的共享存储程序都是 为硬件的共享存储( 包括分布式共享存储) 机器而写的，因此没有考虑s v m 系统的许 多特性，结果造成一些以前的程序在s v m 系统中不能取得很好的效果。换句话说，目 前的s v m 系统只对于那些具有粗粒度共享特性的应用程序才会有较好的效果。因此， 很有必要建立一个统一的适合于s v m 系统的编程接口和编程方法，另外，由于缺乏一 个评价s v m 的标准测试程序和方法，许多已发表结论的可靠性很值得怀疑，所以制定 套标准的评价s v m 性能的测试程序和测试方法也是当务之急。 另一方面，由于消息传递程序的编程相当困难，而用并行编译自动生成消息传递程 序也才刚刚起步，所以如果将s v m 系统作为并行编译器的输出目标平台，就可以更好 地推动网络并行计算的发展。 2 细粒度的s v m 传统的s v m 系统基本上采用页面作为维护一致性的单元，这种粗粒度带来了很多 问题，如假共享、碎片等，从某种程度来说，释放一致性模型和多写一致性模型的提出 都是为了解决这类问题；但是却增加了对程序员的要求，因此限制了s v m 系统的推广 和普及。一般认为，顺序一致性模型对程序员的要求最低，非常适合于s v m 系统，但 是它的性能却很不理想：如果能将维护一致性单元的大小减少，这样假共享、碎片等闯 第3 页 国防科学技术大学研究生院学位论文 题都将不复存在，系统的性能也就会相应的提高；另方面，由于将复杂的一致性操作 都集中于同步，使得同步变成了一个瓶颈；因此可以通过编译器在每个访存操作上增加 一些与一致性相关的操作，以分散集中在同步点的操作，这样既支持了细粒度也支持了 顺序一致性，这种思想最早在w i s c o n s i n 的b l i z z a e d - - s 系统上实现：但因系统的性能 不太好而未受到重视，近来，s c a l e s 等人在这方面的工作表明这种方案的性能可以与采 用粗粒度、释放一致性模型的系统相当，甚至更好，并且编程接口简单，因此是一个值 得重视的方向。 3 适当的硬件支持 当共享存储访存不命中时，由于要请求调页且要维护一致性，不可避免要进行一些 操作，因此人们自然想到用适当的硬件来加速某些关键操作，如用协处理器专门负责通 信和协议相关的操作等。当然，究竟硬件适合做哪些工作，目前还没有明确的答案，仍 需要进行研究，巴西的b i a n c h i n i 等人在他们的n c p 2 工程中打算用硬件支持( 1 ) 本地 d i f f 的产生和合并( a p p l y ) ，( 2 ) 远程页的请求与应答，( 3 ) 远程d i f f 的请求与应 答，( 4 ) 消息的发送与接收。 4 基于s m p 的s v m 随着硬件技术的发展，s m p 的机器将越来越普及，在这种机器内部的一致性是由硬 件来维护的，因此以s m p 机器为结点在上层用软件实现s v m 系统，这种层次结构已 成为当前主要潮流之一，也是第三代s v m 系统所依赖的硬件基础，但是，这种新的结 构也为s v m 系统带来了许多新的课题，如结点内和结点间一致性维护的交互问题，一 个结点内多个c p u 的功能划分问题，支持什么样的编程界面( 多线程或单线程) 等。 对于基于s m p 的s v m ，国外已经开展了较多的研究。 1 3 1 课题来源 1 3课题简介 本课题来源于自然科学基金会国家杰出青年基金科研项目单映象并行分布操作 系统( s i n g l es y s t e mi m a g e ，简称s s i ) 。所谓s s i ，简单的说，就是用软件或硬件的方 法，把分布式计算环境映象成一台工作站，把多个计算元素统一成一个单一的计算资源。 用户在使用整个系统时，感觉不到整个c l u s t e r 的存在，而只是觉得自已正在使用一台 独立的p c 或工作站，只不过这台独立的p c 或工作站的功能非常强大。 其中，单地址空间和进程空间是s s i 研究中最重要的部分。这也是本课题的主要研 究内容。 1 3 2 主要研究内容与工作 课题的主要研究内容与工作包括以下四个方面： 提出了线程一致性模型( t h r e a d c o n s i s t e n c y m o d e l ，简称t c ) 。我们在认真分析 第4 页 国防科学技术大学研究生院学位论文 各种一致性模型的基础上，发现现有的一致性模型基本上都是从体系结构相关 的同步原语来考虑存储一致性维护，而对于系统内核来说，这些同步原语是透 明的。内核所见的只是执行体( 线程或进程) 的状态，因此我们从操作系统内 核的角度出发，提出了一种以操作系统为中心的存储一致性模型线程一致 性模型。 认真分析了l i n u x 内核，特别是对l i n u x 的存储管理进行了深入剖析。在此基础 上，提出了遵循线程一致性模型的分布共享存储访问方案。 提出了遵循线程一致性模型的m t k 存储管理系统的实现方案。我们在认真分析 了j i a j i a 、q u a r k s 、t r e a d m a r k s 这几个s v m 系统的基础上，借鉴j i a j i a 的写记 录( w r i t en o t i c er e c o r d ) ，以及q u a r k s 利用p t h r e a d 线程库在库一级的实现，提 出了线程一致性模型的实现机制，以及多线内核存储管理系统m t k 的实现方 案。 最后，我们对m t k 的系统开销进行了分析。重点分析了m t k 系统中的请求调 页开销、一致性维护开销、通信开销以及并行程序加速比。 1 4论文的组织 全文分为5 章，本章概述了课题背景、研究内容、研究环境、以及当前研究状况； 在第二章里，详细讨论了s v m 的基本原理以及实现的关键技术；第三章阐述了线程一 致性模型；第四章详细介绍了m t k 的实现方案与系统开销分析：第五章总结全文。 第5 页 国防科学技术大学研究生院学位论文 第二章虚拟分布式共享存储系统原理 s v m 实现的关键技术主要包括共享存储的组织、存储一致性模型、c a c h e 一致性协 议、一致性粒度以及实现层次等内容，本章从这些方面对s v m 的基本原理进行了详细 论述，并分析了三个s v m 系统实例：j i a j i a ，t r e a d m a r k s ，q u a r k s 。 2 1共享存储的组织( s h a r e d m e m o r yo r g a n i z a t i o n ) 在分布式共享存储系统中，共享存储的组织方式是首先要解决的关键技术问题，它 包含两个内容：共享存储的分布和地址空间结构。 2 1 1 共享存储的分布( d a t al o c a t i o n ) 解决共享存储分布问题最通常的方式是为每个数据项分配一个宿主结点( o w n e r ) 。 宿主结点拥有读写权限，而其他结点仅有只读副本。只有宿主结点可以对数据项进行写 操作。l i 和h u d a k ( 第一个d s m 系统y 的作者) 针对数据分布问题，提出了比较好 的解决方案，概括如下： 固定宿主结点( f i x e do w n e r s h i p ) 在这种方案中，为每块共享数据分配一个固定的宿主结点，对共享数据的地址进行 简单的计算就可以找到其宿主结点。只有宿主结点有直接进行写操作的权限。因为 副本结点执行写操作时，都必须通过宿主结点，因此写开销非常大。共享数据的宿 主结点成了分布式系统的瓶颈。 动态宿主结点( d y n a m i co w n e r s h i p ) 在动态宿主结点方案中，共享数据的宿主在分布式系统中是动态变化的。为了确定 共享数据的宿主结点，需为共享数据建立管理者。管理者并不一定要拥有该共享数 据，它负责跟踪共享数据的宿主结点。对共享存储如何管理，可以分为两类： 集中式管理：选择一个结点作为所有共享存储的管理者。处理结点通过和管 理者通信，从共享数据的宿主结点处获得数据。管理者也跟踪该共享存储在 哪些结点上有r e a d _ o n l y 副本，并维护一个读写请求队列。 分布式管理：集中管理器很容易成为系统的瓶颈。显然，把共享存储的宿主 信息分配到各个结点上，是一种很自然的解决方法。 2 1 2 地址空间结构( a d d r e s s - - s p a c e s t r u c t u r e ) 所谓地址空间结构，就是如何组织分布式存储系统的地址空间。一般可以分为如下 两类地址空间结构： o 共享空间单地址系统( s i n g l es h a r e d a d d r e s s - - s p a c es y s t e m ) 国防科学技术大学研究生院学位论文 在共享空间单地址系统里，共享数据在系统所有结点上都是统一的，也就是说数据 在远程副本结点的c a c h e 中的地址，和它在主结点上的地址是一致的。这样，对于 共享数据的远程访问，无需进行地址转换。 共享空间单独编址( s e p a r a t e s h a r e da d d r e s s s p a c e s ) 在共享空间单独编址的系统中，每个结点把本地存储器划分为多个部分，一部分为 本结点访问的局部存储区，还有一部分为共享存储区，与其他结点共享访问。当结 点访问远程共享数据时，必须进行地址转换。 2 2c a c h e 一致性协议( c a c h e c o n s i s t e n c y p r o t o c 0 1 ) 当存在多个c a c h e 副本时，要求有一个传播新值到被更新单元所有副本的机制，这 种机制通常称为c a c h e 一致性协议。通常根据存储一致性模型来设计c a c h e 一致性协议， 存储一致性模型规定了c a c h e 一致性协议的一致性要求，即c a c h e 一致性协议应提供什 么样的共享存储视图。例如，在r c 中，直到写新值的处理器到达“r e l e a s e ”操作时， 另一处理器才能看见新值：而在s c 中，一个新写的值会尽可能快地传播到所有其它处 理器上。所以，s c 要求的共享存储一致性视图( c o h e r e n tv i e w ) 与r c 的要求是不相 同的，因此，s c 的c a c h e 一致性协议与r c 的c a c h e 一致性协议也是完全不同的。 c a c h e 一致性协议是传播新写值的机制，它使得所有处理器有一个共享存储视图。 目前，已提出了许多传播新值到其它处理器的方法，它们构成了各种c a c h e 一致性协 议，这些协议可从以下四个方面加以区分： o 新写值传播给谁：监听协议或目录协议： 怎样传播新写值：写失效或写更新； 谁能在存储块中写新值：多写协议或单写协议； 什么时候传播新写值：及早传播或延迟传播，这是e h 存储一致性模型来确定的； 根据以上四个方面，可对协议的复杂性和性能进行折衷。一般来说，系统性能的提 高会增加系统的复杂度，而系统的复杂化有可能抵消一部分性能的提高。下面分别对 c a c h e 一致性协议的四个方面进行详细阐述。特别的，我们单独列出了一节来重点分析 存储一致性模型。 2 2 1 写失效( w r i t e - i n v a l i d a t e ) 写更新( w r i t e - u p d a t e ) 根据采用的写传播策略，c a c h e 一致性协议可分成两类：写失效( w r i t e i n v a l i d a t e ) 和写更新( w r i t e u p d a t e ) 。 写失效：如果一个存储块被一处理器更改，该块在其它处理器中的所有副本都要变为 无效。如果其它处理器以后又引用该存储块，该块的最新副本将会重新装入c a c h e 。 o 写更新：如果一个存储块被一处理器更改，该块的新写值将会直接传播到拥有该块副 本的所有处理器。 第7 页 国防科学技术大学研究生院学位论文 与写更新相比，写失效协议的性能受假共享的影响更大，即任何时候，一个存储块 的个数据被一处理器更改，该块的所有副本将变为无效，无论更改的数据项是否被其 它的处理器共享；另一方面，写更新将对某一数据项的更新传播到它的所有副本，包括 不再被使用的副本，因而降低了性能；另外，对同一页面的多次写，写更新协议需要多 次传播更新值，而对于写失效协议，只需一次失效就可以。所以写失效适合于顺序共享 模式的应用，而写更新则适合于紧密共享( t i g h ts h a r i n g ) 的应用。 2 2 2 单写( s i n g l e - w r i t e ) 多写协议( m u l t i p l e w r i t e ) 多写协议主要解决假共享问题。假共享就是共享c a c h e 块，但没有真正地共享数据。 当两个或多个处理器并发地更新同一块的不同共享数据项时，就会发生假共享。 通常，假共享起因于非优化的协议。在写失效协议中，更改存储块中的一个字将引 起块的所有c a c h e 副本变为无效，无论该字是否被其它处理器共享。这样，发送的“写 失效”比并行应用和它的数据共享的要求要多。假共享会导致“乒乓”问题，使存储块 频繁地在不同的处理器间移动。类似地，在写更新协议中，存储块中一个字的更改会引 起存储块在拥有块副本的处理器间来回发送，即使这些处理器再也不访问更改的字。 多写协议允许对同一存储块进行并发写，因而缓解了假共享的影响。但程序员必须 负责保证读和写是针对同一存储块中的相互独立的部分。多写协议缓冲对同一块的并发 写所作的更改，直到同步操作要求传播它们。在松弛一致性模型中，采用多写协议可以 有效地发挥模型本身的优点。 2 2 3 监听协议( s n o o p i n gp r o t o c 0 1 ) & 目录协议( d i r e c t o r y _ b a s e dp r o t o c 0 1 ) 监听协议和目录协议采用不同的方式来确定更新信息的接受者。 监听协议( s n o o p i n gp r o t o c 0 1 ) 在监听协议中，当一结点对共享单元的访问未命中c a c h e 或者可能会引起数据不一 致时，它就把这一事件广播到所有结点，系统中所有结点都监听广播，当c a c h e 中 拥有广播所涉及的共享单元的结点监听到广播后，就采取相应的维护一致性的行动 ( 如：使本高速缓存的副本无效、向总线提供数据等) ，监听协议适合于多个处理结 点通过总线相联的集中式共享存储系统，因为总线是一种方便而快捷的广播媒介。 监听协议对广播机制的依赖极大地限制了这种协议的可伸缩性，主要包括：( 1 ) 总 线是个竞争的资源，任何时刻只能由个结点使用；( 2 ) 所有结点在使用总线前都 必须经过一个仲裁阶段；( 3 ) 总线的时钟周期必须足够大以保证信号能在一个时钟 周期走遍整个总线；( 4 ) 当总线的长度增加后，传播的速度会下降。因此，目前总 线监听协议主要用在小规模的s m p 机器上，在大规模的共享存储机器上，一般都采 用基于目录的协议。 o 目录协议( d i r e c t o r y _ b a s e dp r o t o c 0 1 ) 目录协议的基本思想是：l 为主存中的每一存储行维持一目录项，该目录项记录所确 第8 页 国防科学技术大学研究生院学位论文 当前持有此行副本的结点( 又称共享集，s h a r i n gs e t ) 以及该行的状态信息，当一个 结点向某存储行写数据且可能引起数据不一致时，它就可以根据目录的内容只向持 有此行副本的结点发出一致性维护信息，从而避免了广播。 相对于监听协议，目录协议避免了对硬件的特殊要求和对宽频带的需求，因而得到 了广泛的运用。但目录协议为每一存储行维护目录，从而需要大量的存储空间。 目录协议的目录组织方式可以分为静态和动态两种。静态的目录包括位向量目录和 有限指针目录，动态的目录包括链表和可能宿主两种，下面对它们分别进行介绍： 位向量目录 位向量目录中，每一个目录项都有一个( n 州) 位的向量，其中n 为系统中结 点的数目，第n + i 位是改写位，用来记录该存储行是否被改写过。如果位向量 目录的第i 位被置为“l ”，则表示此存储行在第i 个结点上有一个副本，如果 改写位被置为“l ”，则表示此时正有一个结点在对该行进行写。 有限指针目录： 随着结点数n 的增加，位向量目录所需的目录存储器容量以n 2 的速度增加， 当n 很大时，这种目录的开销甚至超过结点的存储器容量，因而是不切实际的。 通过对大多量的应用观察发现，一个变量一次只被少数几个处理结点所共享， 因此可以限制某个存储行被同时共享的最大结点数n ，然后只需用有限个指针 记录当前有副本的结点。这样，整个目录容量的增长就是线性的。当共享每个 存储行的结点不超过n 时，有限指针目录和位向量是相似的。当共享某个存储 行的结点数多于目录项中的指针数目时，必须有一个机制来解决指针溢出 ( p o i n t e ro v e r f l o w ) 问题。国际上已经提出了许多解决方案，如带广播的有限 指针，带指针替换的有限指针，实现粗向量转换的有限指针，用软件支持的有 限指针，以及动态指针溢出的有限指针等。不同的解决方案主要在性能和复杂 度上进行折中。 链表指针目录 在位向量目录和有限指针目录中，所有的目录都是静态的，为了适应共享结点 数目的动态变化，人们自然想到用动态的链表将它们链在一起。采用动态链表 的好处是可以将对存储空间的需求分布到所有共享数据的结点上，常用的动态 链表法包括链表指针法和可能宿主法。 在链表指针目录法中，主存中每个存储行以及高速缓存中的每一行均有一个( 单 向链表) 或两个( 双向链表) 指针，当某个高速缓存中拥有一个存储行的副本 时，它就被链接到该存储行上，以后当其他结点需要访问这一行时，就从存储 行开始通过单向或双向链表查找相关的信息，并根据一致性的需求对该链表进 行相应的操作，如删除和增加等。 o 可能宿主目录协议 第9 页 国防科学技术大学研究生院学位论文 在所有上面的目录协议中，每个目录都有个固定的主结点，这样虽然查找起 来很方便，但当结点不是所要访问目录的主结点时，就至少要进行一次通信， 在硬件实现的系统中，还可以承受，但在软件实现的系统中就会带来一些额外 的开销。 为了避免耗时的远程目录访问操作，l i 等人提出了将目录组织成可能宿主的形 式，以代替固定宿主结点的目录组织方式，在可能宿主目录协议中，每个存储 页都有一个宿主，它拥有该页的最新副本。但究竟哪个结点是某页的宿主是动 态变化的。因此，每个结点为每页维护一个可能宿主域，通过这个域一定可以 找到该页的宿主。它之所以被称为“可能宿主”是因为它的内容是对宿主的猜 测，而不是精确的指明谁是真正的宿主，这个域可能指向该页的宿主，也可能 只是告诉通过所指向的结点可以找到真正的宿主。当处理机收到写失效的请求， 或放弃宿主权利，或传递一个页错误的请求时，都要对相应的可能宿主的域进 行修改。 从上面的描述可以看出，这种目录的组织形式减少了查找和远程更新目录的开 销，但协议本身比较复杂，因此很适合于软件实现。 2 3 存储一致性模型( m e m o r yc o n s i s t e n c ym o d e l ) 所谓存储一致性模型( m e m o r yc o n s i s t e n c ym o d e l ) ，实际上就是s v m 系统设计者 与应用程序员之间的一种约定，应用程序遵从该规则访问共享存储空间，则可获得正确 的存储访问结果；反之，则存储访问的正确性不受保证。s v m 系统中最重要的问题就 是维护存储一致性，存储一致性模型规定了何时一台处理机能看到另一台处理机更新的 内容。从程序员的角度来看，一致性模型实际上是一种编程模型。越严格的存储一致性 模型对应用程序员的要求越简单，但可供程序优化的程度就越低，甚至会严重影响s v m 系统的性能。本节首先介绍存储一致性模型分类，然后对这些一致性模型进行比较。 对于s v m 系统，只读页面可能在多个结点上均有副本，而可写页面，一般都由一 个宿主( h o m e ) 来维护其一致性。远程访问时，由远程结点向宿主结点发出访问请求 并从宿主结点处取回该可写页面。通常情况下，对一个可写页面，s v m 系统中最多只 能有一个副本，当应用程序的数据相关性比较大时，这种对每一可写页面只维护一个副 本的策略将引发严重的性能瓶颈。维护多个副本的策略能减缓性能的瓶颈效应，但又带 来了一个新问题，即如何在多个副本之间维护数据的一致性。为解决这个问题，提出了 存储一致性模型。大致来说，一致性模型可以分为两大类： 较严格一致性模型：包括严格一致性模型、顺序一致性模型和处理器一致性模型。 松弛一致性模型：弱一致性模型、释放一致性模型、急切释放一致性模型、懒惰释放 一致性模型、域一致性模型、单项一致性模型。 由于使用松弛的一致性模型可以大大提高s v m 系统的效率，因此，在内核实现s v m t ，j ，应该选用松弛的致性模型。本节将详细描述几种典型的松弛一致性模型并从核内 国防科学技术大学研究生院学位论文 实现的角度对它们进行分析。 1 弱一致性模型( w e a kc o n s i s t e n c y ，w c ) w c 通过硬件放松了对可容许事件次序的限制。在弱事件序的系统中，硬件应能够 区别同步访问和普通的共享访问，而程序员则需保证可能引起一致性问题的访问的互斥 性，这是通过使用硬件可识别的同步原语来达到的。显然，w c 需要使用硬件支持 2 释放一致性( r e l e a s ec o n s i s t e n c y ，r c ) 在释放一致性模型中，同步访问进一步被分成“获取( a c q u i r e ) ”操作和“释放 ( r e l e a s e ) ”操作( 如图2 1 ) 。执行“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 ”操作之前，它前面的所有普通的 读写访问都必须已被执行。 图2 1r c ：延迟到q 与p 同步时才传播一致性数据案 释放一致性模型一般用于硬件d s m 系统( 比如d a s h ) 。在d a s h 中，对共享单 l 的写操作会没有延迟地传播到其它处理器：当一个处理器流出写操作时，相关性协议 被启动，并使写入值可见于其它的处理器。显然，r c 的信息交换量是比较大的，所以 在s v m 系统中很少使用r c 模型。 3 立即释放一致性模型( e a g e r r e l e a s ec o n s i s t e n c y ，e r c ) 在s v m 中，减少消息交换的数量也是非常重要的，因此，在s v m 系统m u n i n 中， 实现了e r c 。e r c 缓冲共享存储器的写操作直到“r e l e a s e ”的执行( 如图2 2 ) ，此时， 对同一单元所有的写合并为一条消息。通过合并写操作( 而不是对它们流水) 大大减少 了消息交换。 图2 2e r c ：p 在r e l e a s e 时，将x ，y ”推送( p u s h ) ”到q 4 懒惰释放一致性模型( l a z y r e l e a s ec o n s i s t e n c y ，l r c ) 与r c 不同，l r c 在执行“r e l e a s e ”操作时，并不传播在临界区进行的更改；相反， n 政设加以缓冲，然后在“a c q u i r e ”操作时，仅仅传播给得到释放锁的处理器( 如图 ：3 ) 。这样，l r c 不仅减少了消息交换的数量，而且降低了交换的数据量。在l r c 中， 镐1 l i 国防科学技术大学研究生院学位论文 一个处理器在执行完“a c q u i r e ”操作前，所有已可见于“r e l e a s e 处理器的更改也必 须可见于该“a c q u i r e ”处理器。 q 图2 3l r c ：处理器q 在a c q u i r e 时将x ，y 从p ”拖( p u l l ) ”过来 5 域一致性模型( s c o p ec o n s i s t e n c y ，s c c ) s c c 对存储访问的次序施加了如下的限制： 在处理器p 被允许执行“a c q u i r e ”锁操作之前，p 必须执行完与该锁相 关的写操作； 一个存储访问被允许执行，仅当所有前面的“a c q u i r e ”事件已被执行完。 s c c 比l r c 更加“懒惰”。在s c c 中，当处理器p 从处理器q 获得锁l 时，它并 不需要所有已可见于q 的更改：它仅仅获取处理器q 在由锁l 保护的临界区中所作的 更改( 如图2 4 所示) 。与l r c 相比，s c s 消息交换数量少、数据量小。 p q a r q ( 1 ) r ( x ) r ( y ) r z ) r e l u ) 图2 4s c c 只释放l i 台阶段中的修改 6 单项一致性模型( e n t r yc o n s i s t e n c 3 r ，e c ) e c 将共享数据对象和同步变量相联，进一步松弛了一致性模型。它要求“a c q u i r e ” 操作得到仅仅由同步变量所保护数据的更改，所以减少了不必要的更新传播。在共享存 储系统的一致性模型中，e c 的通信量是最小的，但它要求程序员显示地将数据和同步 变量相联，这就增加了程序员的负担。 2 4 一致性粒度( g r a n u l a r i t y ) 一致性粒度就是一致性单元的大小，通常可以分为两种： 基于对象的一致性粒度( o b j e c tb a s e dg r a n u l a r i t y ) 基于页面的一致性粒度( p a g e b a s e dg r a n u l a r i t y ) 在基于对象的一致性粒度中，一致性单元的大小随着共享数据项的大小变化，协议 的复杂性相对于基于页面的一致性粒度来说，要高出许多，另外，当数据项单元过小时， 维护一致性的通信量很大。基于页面的一致性粒度，符合内核存储管理的虚存分页机制， 同时可以充分的利用通信带宽来维护一致性。在基于页面的致性粒度中，假共享、碎 ”旧溪比较严重，释放致性模型和多写协议可以有效地解决这些问题。 国防科学技术大学研究生院学位论文 2 5 实现层次( i m p l e m e n t a t i o nl a y e r ) 一般说来，可以在语言级、编译级、运行库、操作系统这四个层次上实现s v m ，事 实上，实现的层次与一致性粒度和编程接口关系密切。随着实现层次抽象程度的不断提 高，可支持的一致性粒度就越来越细，对应用程序员的要求也越来越苛刻。特别是在语 言级实现的系统，需要将程序作很大改动，不易被人们接受，所以，自八十年代的l i n d a 和o r c a 系统以后，近年来已很少有人在这方面进行研究，由编译器所实现的系统的优点 是可以支持细粒度和严格的一致性模型，但由于给每个普通的访存操作都增加了一些额 外的开销，使得整个系统的性能反而可能下降，另外，这种系统的可移植性也不好，如 w i s c o n s i n 实现的b l i z z a r d s 系统，当然d e cw r l 的研究人员提出了许多优化技术，给 这种方案又带来了生机。正是因为前两种方案都有较明显的缺点，所以基于运行库的方 案得到了广泛的采用，它具有编程接口简单，易移植，实现方便等特点，因而成为了分 布式共享存储系统的主流，如t r e a d m a r k s 、q u a r k s 、j i a j i a 都属于此类。 库一级实现的s v m ，在一次共享缓存不命中时，进入和退出段违例信号处理程序， 以及多次在用户态核心态间转换，软件开销很大。在操作系统内核实现s v m ，可以消除 这些开销，另外在操作系统级实现s v m ，可以精简通信协议，减少通信开销。在a c m 每两年召开一次的操作系统设计与实现( o s d i ) 会议上，有很多文章讨论这方面的工作。 另外，l i n u x 内核增强了对s m p 的支持。从应用的角度来看，修改操作系统内核的方案 不易为用户接收。 在具体的实现中，许多人将上述的各个层次结合起来，甚至增加一些硬件的支持来 暑高性能，如m u n i n 中采用操作系统改动，运行库支持相结合的方案，m i d w a y 则采用 乏行库支持和编译器相结合的方案。 2 6s v m 系统的典型案例 我们认真地研究了三个典型s v m 系统：t r e a d m a r k s 、j i a j i a 以及q u a r k s 。在实现基 于线程一致性模型的m t k 系统时，我们借鉴了这三个系统的一些特性。本节简略的概 括一下这三个s v m 系统的主要特点。 2 6 1t r e a d m a r k s t r e a d m a r k s 是一个基于标准u n i x 的s v m 系统，以库的形式实现在操作系统上。 t r e a d m a r k s 实现在用户级，没有修改o s 内核，而且也不需要特殊编译器支持。它的主 要特点为： 1 t r e a d m a r k s 采用l r c 作为它的存储一致性模型。l r c 将每个进程的执行分成区 问( i n t c r v a l ) ，每个区间用区间索引( i n t e r v a li n d e