第6章分布式共享存储.ppt
第6章 分布式共享存储,中国科技大学软件学院丁箐,2,主要内容,6.1 共享内存6.2 一致性模型6.3 基于页面的DSM6.4 其它的分布式共享内存,3,主要内容,6.1 共享内存6.2 一致性模型6.3 基于页面的DSM6.4 其它的分布式共享内存,4,多处理机和多计算机回顾,对硬件的影响 设计一种使多个处理机同时使用同一存储器的机器是非常困难的 大的多计算机系统更易于建立 对软件的影响 用于多处理机编程的技术很多，可以使用临界区（critical region），信号量或管程（monitor）提供必要的互斥。对多计算机系统，通信一般使用消息传递，这使输入/输出更为抽象。消息传递带来了许多复杂的问题，,5,分布式共享存储器(DSM),Li 和Hudak提出让一组由局域网互连的工作站共享一个分页的虚拟地址空间。不共享整个地址空间，而只共享其中所选择的一部分，即那些由多个进程引用的变量和数据结构。在多台计算机上复制共享变量，通过共享复制的变量而不是整个页，模拟处理机的问题可简化为保证一组数据结构的多个拷贝一致性的问题。,6,DSM的很多研究工作都受到了多处理机结构发展的启发!首先比较几种共享存储器（内存）的多处理机,7,芯片存储器,CPU与存储器连接模型单片机理想的共享存储器多处理机,8,Pentium D with 975X Chipset,9,多处理器结构带缓存的多处理器结构总线仲裁机制：集中式和非集中式,基于总线的多处理机,CPU,内存,总线,(a),总线,(b),CPU,CPU,内存,10,通写缓冲(write-though)一致性协议,11,缓存拥有权（ownership）协议,Cache分成若干个cache块每个Cache块处于三种状态：Invalid数据无效Clean与存储器数据一致Dirty数据被更新，与存储器数据不一致各CPU监听（snoopy）其它CPU在总线的操作,12,缓存拥有权（ownership）协议,多个CPU可有读拥有权只有一个CPU有写拥有权当一个CPU写一个数据取得对该数据的拥有权其它CPU将该数据的缓存块置为“invalid”在本地缓存块中，写数据，并置为“dirty”适当时候，刷新存储区，或提供给其它CPU,13,缓存拥有权（ownership）协议,特点通过各CPU对总线的监听保持缓存一致性该协议实现在存储器管理单元中整个算法在一个存储器周期中完成召回（callback）协议如果用软件实现,14,缓存拥有权协议操作过程,15,缓存拥有权协议操作过程,16,重要属性,缓存对总线的监听保证了一致性。协议建立在存储器管理单元中。整个算法在一个存储器周期中完成。,17,基于环的多处理机,没有集中式全局存储器耦合得较松一些,(a)Memnet环(b)单一主机(c)块表,18,交换式多处理机,CPU增加到一定数量时，总线或环的带宽达到饱和，再增加额外的CPU也不会提高系统性能减少通信流量采用两种方法解决带宽不足的问题减少通信流量改善缓冲协议，优化块大小，重组程序，以提高存储器访问的本地命中率。增加通信容量改变拓扑结构 为系统建立层次结构,19,(a)三个簇由簇间总线连接组成一个超级簇(b)由超级簇总线相连的两个超级簇,分级层次结构,20,DASH示例,目录每一簇都以目录来记录哪些簇现在拥有哪些块的拷贝 缓存（caching）缓存分为两级：第一级缓存和更大的第二级缓存 协议（protocul）DASH协议是基于拥有权和置无效的,21,NUMA多处理机,和传统UMA(Uniform Memory Access)多处理机一样，NUMA机的虚拟地址空间对所有CPU都可见。任何CPU在地址A写入值，接下来别的处理机对A的读操作将读取刚刚写入的值。UMA与NUMA的区别不是在语义上，而是在性能上。在NUMA机上，访问远程存储器要比访问本地存储器慢得多，而硬件缓存并不试图掩盖这个问题。,22,NUMA示例,23,NUMA多处理机的属性,可以访问远程存储器。访问远程存储器比访问本地存储器慢。没有缓冲机制隐藏访问远程存储器的时间。,24,分布式共享系统的比较,25,六种共享处理器系统的比较,26,主要内容,6.1 共享内存6.2 一致性模型6.3 基于页面的DSM6.4 其它的分布式共享内存,27,6.2 一致性模型,只允许有一个拷贝可能会带来严重的性能瓶颈。允许多重拷贝可以就简化性能问题。但这又引起了新的问题：即如何保证所有拷贝的一致性。缓存一致性（coherency）数据在各个缓存中的值保持一致一致性模型软件与存储器间的约定（contract）如果软件遵守约定的规则，存储器就能工作正常。如果软件违反了这些规定，存储器就不再保证操作的正确性,28,严格一致性,从存储器地址X处读出的值为最近写入X的值 非严格一致性,29,顺序一致性,如果所有进程以一定的顺序执行操作，每一进程的操作都以程序规定的顺序出现，则任何操作的结果都是一样的。每一进程的操作都按程序规定的顺序执行。所有进程看到相同的内存访问操作次序运行同一个程序得到的两个可能的结果,30,3个并行执行的进程4种正确的执行顺序,顺序一致性举例,31,因果一致性,按有无可能的因果联系区分各事件，对于因果相关的写操作，所有进程看到的执行顺序应相同。可能因果相关的写操作应对所有进程可见，且顺序一致。并发写操作在不同机器看来顺序可能是不同的,因果一致性存储器允许的序列,但是顺序一致性 存储器和严格一致性存储器不允许,32,因果一致性举例,（1）违反因果一致性（2）符合因果一致性,33,管道内存（PRAM）一致性,同一个进程的写操作的执行次序，其它进程看到的都相同不同进程的写操作的执行次序，不同进程看到的可以是不同的例：符合PRAM一致性，但不符合因果一致性,34,管道内存（PRAM）一致性示例,a=1;a=1;b=1;*print(b,c)b=1;print(a,c)b=1;*print(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),35,处理机一致性,与PRAM一致性相似附加条件：存储相关性：对于任意存储器地址X,对于写入X的顺序是全局一致的。写入不同地址,对于不同进程来看,不需要相同顺序,36,弱一致性,同步变量：广播导出所有写操作，导入所有写操作 对同步变量的访问必须是顺序一致性的。在所有前面的写操作完成之前,不能访问同步变量。在前面所有同步变量的访问完成前,不能访问（读或写）数据。,37,释放一致性,获取（acquire）访问用于通知存储器系统临界区已就绪 释放(release)访问表明临界区刚退出。规则在访问共享变量前，所有先前的acquire都必须完成。在进行release前，先前的所有读写操作都必须结束。acquire和release访问必须满足处理机一致性,38,释放一致性,通常，分布式共享存储器在遵守以下规定时就是释放一致的：在访问共享变量前，进程所有先前的获取访问都必须成功地完成。在允许释放访问前，进程先前的所有读写操作都必须结束。获取访问和释放访问必须是处理器一致的。,39,释放一致性的应用,急性释放一致性(EAGER release consistency)当执行了释放操作，执行此操作的处理机将所有修改的数据传给所有那些已经有其缓冲拷贝且可能需要它的处理机 惰性释放一致性（LAZY release consistency）在执行释放时，不发送任何数据。在执行获取操作时，处理机试图从拥有这些变量的机器上取得它们的最新值,40,入口一致性,当存储器满足下列所有条件时，就成为入口一致性存储器：（1）只有某一进程的保护共享变量全部被更新以后，该进程才允许执行同步变量的获取访问；（2）在一进程以互斥模式访问该进程的同步变量之前，不允许其他进程持有此同步变量，即使在非互斥模式下；（3）在结束互斥模式下对一个同步变量的访问后，任意其他进程必须与该变量的拥有者核查，才能试图以非互斥模式访问该同步变量。,41,一致性模型总结,不用同步操作的一致性模型,42,一致性模型总结,使用同步操作的一致性模型,43,主要内容,6.1 共享内存6.2 一致性模型6.3 基于页面的DSM6.4 其它的分布式共享内存,44,6.3 基于页面的DSM,局域网上的工作站从根本上不同于多处理机。处理机只能访问本地存储器。不像在NUMA或UMA多处理机系统中，这里没有全局共享变量的概念。然而，DSM的目的就是在系统中增加软件，以允许多计算机系统运行多处理机上的程序。,45,基本设计,页块：地址空间管理的基本单位,46,实现技术,虚拟地址空间内存映射（memory mapping）缺页中断（pagefault）,47,存储映射技术,两个进程共享同一个文件,48,存储映射技术,s is an error code addr are memory addresseslen is a length prot controls protectionflags are miscellaneous bitsfd is a file descriptor offset is a file offset,49,复制复制只读块 复制所有页块 粒度（Guanularity）页块的大小应是多大：字、块（少量字）、页或段（多个页）。,包含两个无关变量的页的错误共享,50,实现顺序一致性（Sequential Consistency）,多处理机一般有两种处理方法：更新置无效 基于分页的DSM系统通常使用置无效协议而不是更新协议,51,处理机读页举例,P,W,拥有者,1.读,P,R,拥有者,1.读,P,R,拥有者,1.读,页面,处理器1,处理器2,R,P,R,1.读,P,1.请求复制,2.将页标志为R,3.读,P,R,拥有者,R,拥有者,W,拥有者,1.请求降级,2.请求复制,3.将页标志为R,4.读,(a),52,处理机写页举例,53,寻找拥有者（Finding The Owner）,通过广播 拥有者定位协议(ownership location pretocol)让每个进程（更可能的是每个处理机）跟踪每一页的可能拥有者,54,拥有者定位协议,四消息协议三消息协议,P,拥有者,页面管理器,1.请求,2.响应,3.请求,4.响应,P,拥有者,页面管理器,1.请求,3.响应,2.移交请求,(a),(b),55,寻找拷贝,.每个页面的拥有者通过拷贝集得知哪个其它CPU正共享该页面,每个页面的拥有者通过拷贝集得知哪个其它CPU正共享该页面.页拥有劝用双线框表示,56,页面置换（Page Replacement）,类似于最近最少使用（LRU）的算法 置换进程拥有的那些复制页,57,同步,在多处理机系统中，经常使用TEST-AND-SET-LOCK(TSL)指令完成互斥操作。在DSM系统中，同步通常需要一附加机制。一种可能的方法是让同步管理器接受进入和离开临界区的消息，锁或解锁变量，如果工作正常则发送应答。当不能进入临界区或不能加锁变量时，不立即发送应答并阻塞发送消息的进程。当临界区可用或变量可以加锁时消息才被送回。,58,主要内容,6.1 共享内存6.2 一致性模型6.3 基于页面的DSM6.4 其它的分布式共享内存,59,共享变量的分布式共享存储器,提高性能？仅仅共享那些被多个进程使用的变量和数据结构。这样，问题由如何在网络中分页变为如何维护包含所需变量且可被复制的分布式数据库。,60,释放 一致性,基于软件实现（eager）释放一致性 Munin区分三种变量：普通变量共享数据变量同步变量,61,多重协议,允许编程者在定义共享变量时加以注释，将它们分为以下四种情况之一：只读(read-only)迁移（Migratory）写共享(Write-shared)常规(Conventional),62,目录,Munin使用目录定位包含共享变量的页。当访问共享变量出错时，Munin用哈希算法排列导致出错的虚拟地址以找到共享变量目录中变量项。,63,同步,Munin为同步变量维护了第二个目录。同步变量的定位方法和普通共享变量的定位方法差不多。,64,基于对象的分布共享内存,以对像而不是页为单元在网上传送数据是有意义的 更为结构化的方法组织内存！,65,对象,比其它技术更为模块化。由于访问受到控制，实现方法更为灵活。同步和访问可以清晰地结合起来。,66,执行对象上的操作,
