第6章分布式共享存储

《第6章分布式共享存储》由会员分享，可在线阅读，更多相关《第6章分布式共享存储（66页珍藏版）》请在装配图网上搜索。

1、第6章 分布式共享存储分布式共享存储 中国科技大学软件学院丁箐2主要内容主要内容6.1 共享内存6.2 一致性模型6.3 基于页面的DSM6.4 其它的分布式共享内存3主要内容主要内容6.1 共享内存共享内存6.2 一致性模型6.3 基于页面的DSM6.4 其它的分布式共享内存4多处理机和多计算机回顾多处理机和多计算机回顾l对硬件的影响 设计一种使多个处理机同时使用同一存储器的机器是非常困难的 大的多计算机系统更易于建立 l对软件的影响 用于多处理机编程的技术很多，可以使用临界区（critical region），信号量或管程（monitor）提供必要的互斥。对多计算机系统，通信一般使用消息传

2、递，这使输入/输出更为抽象。消息传递带来了许多复杂的问题，5分布式共享存储器分布式共享存储器(DSM)lLi 和Hudak提出让一组由局域网互连的工作站共享一个分页的虚拟地址空间。l不共享整个地址空间，而只共享其中所选择的一部分，即那些由多个进程引用的变量和数据结构。l在多台计算机上复制共享变量，通过共享复制的变量而不是整个页，模拟处理机的问题可简化为保证一组数据结构的多个拷贝一致性的问题。6lDSM的很多研究工作都受到了多处理机结构发展的启发!l首先比较几种共享存储器（内存）的多处理机 7芯片存储器芯片存储器 CPU与存储器连接模型l单片机l理想的共享存储器多处理机8Pentium D wi

3、th 975X ChipsetInter-Core Bus InterfaceMemory ControllerHubI/O Controller HubDDR2 MemoryPCI Express x166 PCI4 Serial ATA Ports6 PCI Express x1High-Definition Audio2 PCI Express x8orDMI(2 GB/s)1066/800 MHz FSBCore 1L2 Cache(for Core 1)Core 0L2 Cache(for Core 0)6 USB 2.0Intel Matrix StorageBIOS Suppor

4、tIntel Pro 1000 LAN91.多处理器结构2.带缓存的多处理器结构总线仲裁机制：集中式和非集中式基于总线的多处理机基于总线的多处理机CPU内存总线(a)总线(b)缓存CPUCPUCPU内存缓存CPU缓存CPU10通写缓冲通写缓冲(write-though)一致性协议一致性协议事件对本地CPU操作响应对远程CPU响应读失败（miss）从内存中取得数据并存储到缓存中（MC）（无动作）读命中(hit)从本地缓存中取得数据（无动作）写失败更新内存中的数据并存储到缓存中（C M）（无动作）写命中更新存储器和缓存（MC M）置为无效11缓存拥有权（缓存拥有权（ownership）协议）协议l

5、Cache分成若干个cache块l每个Cache块处于三种状态：1.Invalid数据无效2.Clean与存储器数据一致3.Dirty数据被更新，与存储器数据不一致l各CPU监听（snoopy）其它CPU在总线的操作12缓存拥有权（缓存拥有权（ownership）协议）协议l多个CPU可有读拥有权l只有一个CPU有写拥有权l当一个CPU写一个数据取得对该数据的拥有权其它CPU将该数据的缓存块置为“invalid”在本地缓存块中，写数据，并置为“dirty”适当时候，刷新存储区，或提供给其它CPU13缓存拥有权（缓存拥有权（ownership）协议）协议l特点1.通过各CPU对总线的监听保持缓存

6、一致性2.该协议实现在存储器管理单元中3.整个算法在一个存储器周期中完成召回（callback）协议如果用软件实现14缓存拥有权协议操作过程缓存拥有权协议操作过程15缓存拥有权协议操作过程缓存拥有权协议操作过程16重要属性重要属性l缓存对总线的监听保证了一致性。l协议建立在存储器管理单元中。l整个算法在一个存储器周期中完成。17基于环的多处理机基于环的多处理机没有集中式全局存储器耦合得较松一些(a)Memnet环 (b)单一主机 (c)块表 18交换式多处理机交换式多处理机lCPU增加到一定数量时，总线或环的带宽达到饱和，再增加额外的CPU也不会提高系统性能减少通信流量l采用两种方法解决带宽不

7、足的问题l减少通信流量改善缓冲协议，优化块大小，重组程序，以提高存储器访问的本地命中率。l增加通信容量改变拓扑结构 为系统建立层次结构 19(a)三个簇由簇间总线连接组成一个超级簇三个簇由簇间总线连接组成一个超级簇(b)由超级簇总线相连的两个超级簇由超级簇总线相连的两个超级簇分级层次结构分级层次结构20DASH示例示例l目录目录每一簇都以目录来记录哪些簇现在拥有哪些块的拷贝 l缓存（缓存（caching）缓存分为两级：第一级缓存和更大的第二级缓存 l协议（协议（protocul）DASH协议是基于拥有权和置无效的 21NUMA多处理机多处理机l和传统UMA(Uniform Memory Acc

8、ess)多处理机一样，NUMA机的虚拟地址空间对所有CPU都可见。任何CPU在地址A写入值，接下来别的处理机对A的读操作将读取刚刚写入的值。lUMA与NUMA的区别不是在语义上，而是在性能上。在NUMA机上，访问远程存储器要比访问本地存储器慢得多，而硬件缓存并不试图掩盖这个问题。22NUMA示例示例23NUMA多处理机的属性多处理机的属性 l可以访问远程存储器。l访问远程存储器比访问本地存储器慢。l没有缓冲机制隐藏访问远程存储器的时间。24分布式共享系统的比较分布式共享系统的比较 25六种共享处理器系统的比较六种共享处理器系统的比较 项多处理机DSM单总线交换NUMA基于页式共享变量基于对象线

9、性、共享虚拟地址空间吗？是是是是否否可能的操作读/写读/写读/写读/写读/写常规有封装及方法？否否否否否是是否由硬件执行远程访问？是是是否否否有独立存储器？是是是否否否谁将远程存储器的访问转化为消息？MMUMMUMMU操作系统运行期系统运行期系统传输介质总线总线总线网络网络网络谁执行数据迁移硬件硬件软件软件软件软件传输单元块块页页共享变量对象26主要内容主要内容6.1 共享内存6.2 一致性模型一致性模型6.3 基于页面的DSM6.4 其它的分布式共享内存276.2 一致性模型一致性模型 只允许有一个拷贝可能会带来严重的性能瓶颈。允许多重拷贝可以就简化性能问题。但这又引起了新的问题：即如何保证

10、所有拷贝的一致性。l缓存一致性（coherency）数据在各个缓存中的值保持一致l一致性模型软件与存储器间的约定（contract）如果软件遵守约定的规则，存储器就能工作正常。如果软件违反了这些规定，存储器就不再保证操作的正确性 28严格一致性严格一致性l从存储器地址X处读出的值为最近写入X的值 l非严格一致性P1:W(x)1P2:R(x)1P1:W(x)1P2:R(x)0 R(x)129顺序一致性顺序一致性l如果所有进程以一定的顺序执行操作，每一进程的操作都以程序规定的顺序出现，则任何操作的结果都是一样的。l每一进程的操作都按程序规定的顺序执行。l所有进程看到相同的内存访问操作次序l运行同一

11、个程序得到的两个可能的结果P1:W(x)1P2:R(x)0 R(x)1P1:W(x)1P2:R(x)1 R(x)130l3个并行执行的进程l4种正确的执行顺序顺序一致性举例顺序一致性举例print(b,c);(a)a=1;print(a,c);(b)b=1;print(a,b);(c)c=1;a=1;a=1;b=1;b=1;print(b,c);b=1;c=1;a=1;b=1;print(a,c);print(a,b);c=1;print(a,c);print(b,c);print(a,c);print(a,c);c=1;c=1;a=1;print(b,c);print(a,c);print(

12、a,b);print(b,c);print(a,b);(a)(b)(c)(d)31因果一致性因果一致性l按有无可能的因果联系区分各事件，对于因果相关的写操作，所有进程看到的执行顺序应相同。l可能因果相关的写操作应对所有进程可见，且顺序一致。并发写操作在不同机器看来顺序可能是不同的 P1：W(x)1 W(x)3P2：R(x)1 W(x)2P3：R(x)1 R(x)3 R(x)2P4：R(x)1 R(x)2 R(x)3因果一致性存储器允许的序列,但是顺序一致性 存储器和严格一致性存储器不允许 32因果一致性举例因果一致性举例（1）违反因果一致性（2）符合因果一致性P1：W(x)1P2：R(x)1

13、W(x)2P3：R(x)2 R(x)1P4：R(x)1 R(x)2P1：W(x)1P2：W(x)2P3：R(x)2 R(x)1P4：R(x)1 R(x)233管道内存（管道内存（PRAM）一致性）一致性l同一个进程的写操作的执行次序，其它进程看到的都相同l不同进程的写操作的执行次序，不同进程看到的可以是不同的l例：符合PRAM一致性，但不符合因果一致性P1：W(x)1P2：R(x)1 W(x)2P3：R(x)1 R(x)2P4：R(x)2 R(x)134管道内存（管道内存（PRAM）一致性示例）一致性示例a=1;a=1;b=1;*print(b,c)b=1;print(a,c)b=1;*pri

14、nt(a,c)c=1;print(a,c)print(b,c)*print(a,b)c=1;c=1;a=1;print(a,b)print(a,b)print(b,c)Prints:00Prints:10Prints:01 (a)(b)(c)print(b,c);(a)a=1;print(a,c);(b)b=1;print(a,b);(c)c=1;35处理机一致性处理机一致性l与PRAM一致性相似l附加条件：存储相关性：对于任意存储器地址X,对于写入X的顺序是全局一致的。写入不同地址,对于不同进程来看,不需要相同顺序 36弱一致性弱一致性l同步变量：广播导出所有写操作，导入所有写操作 l对同步

15、变量的访问必须是顺序一致性的。l在所有前面的写操作完成之前,不能访问同步变量。l在前面所有同步变量的访问完成前,不能访问（读或写）数据。P1：W(x)1 W(x)2 SP2：R(x)1 R(x)2 SP3：R(x)2 R(x)1 SP1:W(x)1 W(x)2 SP2:S R(x)137释放一致性释放一致性l获取（acquire）访问用于通知存储器系统临界区已就绪 l释放(release)访问表明临界区刚退出。l规则在访问共享变量前，所有先前的acquire都必须完成。在进行release前，先前的所有读写操作都必须结束。acquire和release访问必须满足处理机一致性38释放一致性释放

16、一致性P1：Acq(L)W(x)1 W(x)2 Rel(L)P2：Acq(L)R(x)2 Rel(L)P3：R(x)1l通常，分布式共享存储器在遵守以下规定时就是释放一致的：在访问共享变量前，进程所有先前的获取访问都必须成功地完成。在允许释放访问前，进程先前的所有读写操作都必须结束。获取访问和释放访问必须是处理器一致的。39释放一致性的应用释放一致性的应用 l急性释放一致性(EAGER release consistency)当执行了释放操作，执行此操作的处理机将所有修改的数据传给所有那些已经有其缓冲拷贝且可能需要它的处理机 l惰性释放一致性（LAZY release consistency）

17、在执行释放时，不发送任何数据。在执行获取操作时，处理机试图从拥有这些变量的机器上取得它们的最新值 40入口一致性入口一致性当存储器满足下列所有条件时，就成为入口一致性存储器：（1）只有某一进程的保护共享变量全部被更新以后，该进程才允许执行同步变量的获取访问；（2）在一进程以互斥模式访问该进程的同步变量之前，不允许其他进程持有此同步变量，即使在非互斥模式下；（3）在结束互斥模式下对一个同步变量的访问后，任意其他进程必须与该变量的拥有者核查，才能试图以非互斥模式访问该同步变量。41一致性模型总结一致性模型总结不用同步操作的一致性模型不用同步操作的一致性模型 一致性说明严格所有的共享访问事件都有绝对

18、时间顺序顺序所有进程都以相同的顺序检测到所有的共享访问事件因果所有进程都以相同的顺序检测到所有因果联系的事件PRAM所有的进程按照预定的顺序检测到来自一个处理器的写操作,来自其它处理器的写操作不必以相同的顺序看见处理器PRAM一致性+存储器相关性42一致性模型总结一致性模型总结使用同步操作的一致性模型使用同步操作的一致性模型 一致性说明弱同步完成后,共享数据才可能保持一致释放当离开临界区时,共享数据就保持一致入口当进入临界区时,和该临界区相关的共享数据保持一致43主要内容主要内容6.1 共享内存6.2 一致性模型6.3 基于页面的基于页面的DSM6.4 其它的分布式共享内存446.3 基于页面

19、的基于页面的DSM 局域网上的工作站从根本上不同于多处理机。处理机只能访问本地存储器。不像在NUMA或UMA多处理机系统中，这里没有全局共享变量的概念。然而，DSM的目的就是在系统中增加软件，以允许多计算机系统运行多处理机上的程序。45基本设计基本设计 l页块：地址空间管理的基本单位0 1 2 3 4 5 6 7 8 9CPU 10259CPU 21368CPU 347CPU 4存储器(a)全局共享地址空间10 111512 1314111012 1413 15(b)CPU 10259CPU 21368CPU 347CPU 41112 1413 1510(c)CPU 10259CPU 2136

20、8CPU 347CPU 4111012 1413 151046实现技术实现技术l虚拟地址空间l内存映射（memory mapping）l缺页中断（pagefault）47存储映射技术存储映射技术l两个进程共享同一个文件48存储映射技术存储映射技术ls is an error code addr are memory addressesllen is a length prot controls protectionlflags are miscellaneous bitslfd is a file descriptor offset is a file offset49l复制复制只读块 复制所

21、有页块 l 粒度（Guanularity）页块的大小应是多大：字、块（少量字）、页或段（多个页）。包含两个无关变量的页的错误共享50实现顺序一致性（实现顺序一致性（Sequential Consistency）l多处理机一般有两种处理方法：更新置无效 l基于分页的DSM系统通常使用置无效协议而不是更新协议 51处理机读页举例处理机读页举例 PW拥有者1.读PR拥有者1.读PR拥有者1.读页面处理器1处理器2RPR1.读P1.请求复制2.将页标志为R3.读PR拥有者R拥有者W拥有者1.请求降级2.请求复制3.将页标志为R4.读(a)52处理机写页举例处理机写页举例 PW拥有者1.写PR拥有者1.

22、将页标志为W2.写入PR拥有者1.无效的拷贝2.将页标志为W3.写入RPR1.请求置无效2.请求拥有者3.将页标志为W4.写入P1.请求置无效2.请求拥有者3.请求页面4.将页标志为W5.写入PR拥有者R拥有者W拥有者1.请求置无效2.请求拥有者3.请求页面4.将页标志为W5.写入(b)53寻找拥有者（寻找拥有者（Finding The Owner）l通过广播 l拥有者定位协议(ownership location pretocol)l让每个进程（更可能的是每个处理机）跟踪每一页的可能拥有者 54拥有者定位协议拥有者定位协议 l四消息协议l三消息协议P拥有者页面管理器1.请求2.响应3.请求4

23、.响应P拥有者页面管理器1.请求3.响应2.移交请求(a)(b)55寻找拷贝寻找拷贝.l每个页面的拥有者通过拷贝集得知哪个其它CPU正共享该页面每个页面的拥有者通过拷贝集得知哪个其它CPU正共享该页面.页拥有劝用双线框表示56页面置换（页面置换（Page Replacement）l类似于最近最少使用（LRU）的算法 l置换进程拥有的那些复制页 57同步同步 l在多处理机系统中，经常使用TEST-AND-SET-LOCK(TSL)指令完成互斥操作。l在DSM系统中，同步通常需要一附加机制。一种可能的方法是让同步管理器接受进入和离开临界区的消息，锁或解锁变量，如果工作正常则发送应答。当不能进入临界

24、区或不能加锁变量时，不立即发送应答并阻塞发送消息的进程。当临界区可用或变量可以加锁时消息才被送回。58主要内容主要内容6.1 共享内存6.2 一致性模型6.3 基于页面的DSM6.4 其它的分布式共享内存其它的分布式共享内存59共享变量的分布式共享存储器共享变量的分布式共享存储器 l提高性能？l仅仅共享那些被多个进程使用的变量和数据结构。这样，问题由如何在网络中分页变为如何维护包含所需变量且可被复制的分布式数据库。60释放释放 一致性一致性 l基于软件实现（eager）释放一致性 lMunin区分三种变量：普通变量共享数据变量同步变量61多重协议多重协议 l允许编程者在定义共享变量时加以注释，

25、将它们分为以下四种情况之一：只读(read-only)迁移（Migratory）写共享(Write-shared)常规(Conventional)62目录目录 lMunin使用目录定位包含共享变量的页。当访问共享变量出错时，Munin用哈希算法排列导致出错的虚拟地址以找到共享变量目录中变量项。63同步同步 lMunin为同步变量维护了第二个目录。同步变量的定位方法和普通共享变量的定位方法差不多。64基于对象的分布共享内存基于对象的分布共享内存 l以对像而不是页为单元在网上传送数据是有意义的 l更为结构化的方法组织内存！65对象对象 对象对象空间进程l比其它技术更为模块化。l由于访问受到控制，实现方法更为灵活。l同步和访问可以清晰地结合起来。66执行对象上的操作执行对象上的操作