第6章分布式共享存储

第6章分布式共享存储

中国科技大学软件学院丁箐1主要内容6.1共享内存6.2一致性模型6.3基于页面的DSM6.4其它的分布式共享内存2主要内容6.1共享内存6.2一致性模型6.3基于页面的DSM6.4其它的分布式共享内存3多处理机和多计算机回顾对硬件的影响设计一种使多个处理机同时使用同一存储器的机器是非常困难的大的多计算机系统更易于建立对软件的影响用于多处理机编程的技术很多，可以使用临界区（criticalregion），信号量或管程（monitor）提供必要的互斥。对多计算机系统，通信一般使用消息传递，这使输入/输出更为抽象。消息传递带来了许多复杂的问题，4分布式共享存储器(DSM)

Li和Hudak提出让一组由局域网互连的工作站共享一个分页的虚拟地址空间。不共享整个地址空间，而只共享其中所选择的一部分，即那些由多个进程引用的变量和数据结构。在多台计算机上复制共享变量，通过共享复制的变量而不是整个页，模拟处理机的问题可简化为保证一组数据结构的多个拷贝一致性的问题。5DSM的很多研究工作都受到了多处理机结构发展的启发!首先比较几种共享存储器（内存）的多处理机6芯片存储器

CPU与存储器连接模型单片机理想的共享存储器多处理机7PentiumDwith975XChipsetInter-CoreBusInterfaceMemoryControllerHubI/OControllerHubDDR2MemoryPCIExpressx166PCI4SerialATAPorts6PCIExpressx1High-DefinitionAudio2PCIExpressx8orDMI(2GB/s)1066/800MHzFSBCore1L2Cache(forCore1)Core0L2Cache(forCore0)6USB2.0IntelMatrixStorageBIOSSupportIntelPro1000LAN8多处理器结构带缓存的多处理器结构总线仲裁机制：集中式和非集中式基于总线的多处理机CPU内存总线(a)总线(b)缓存CPUCPUCPU内存缓存CPU缓存CPU9通写缓冲(write-though)一致性协议事件对本地CPU操作响应对远程CPU响应读失败（miss）从内存中取得数据并存储到缓存中（MC）（无动作）读命中(hit)从本地缓存中取得数据（无动作）写失败更新内存中的数据并存储到缓存中（C

M

）（无动作）写命中更新存储器和缓存（MCM

）置为无效10缓存拥有权（ownership）协议Cache分成若干个cache块每个Cache块处于三种状态：Invalid－数据无效Clean－与存储器数据一致Dirty－数据被更新，与存储器数据不一致各CPU监听（snoopy）其它CPU在总线的操作11缓存拥有权（ownership）协议多个CPU可有读拥有权只有一个CPU有写拥有权当一个CPU写一个数据取得对该数据的拥有权其它CPU将该数据的缓存块置为“invalid”在本地缓存块中，写数据，并置为“dirty”适当时候，刷新存储区，或提供给其它CPU12缓存拥有权（ownership）协议特点通过各CPU对总线的监听保持缓存一致性该协议实现在存储器管理单元中整个算法在一个存储器周期中完成召回（callback）协议如果用软件实现13缓存拥有权协议操作过程14缓存拥有权协议操作过程15重要属性缓存对总线的监听保证了一致性。协议建立在存储器管理单元中。整个算法在一个存储器周期中完成。16基于环的多处理机没有集中式全局存储器耦合得较松一些(a)Memnet环(b)单一主机(c)块表17交换式多处理机CPU增加到一定数量时，总线或环的带宽达到饱和，再增加额外的CPU也不会提高系统性能减少通信流量采用两种方法解决带宽不足的问题减少通信流量改善缓冲协议，优化块大小，重组程序，以提高存储器访问的本地命中率。增加通信容量改变拓扑结构为系统建立层次结构18(a)三个簇由簇间总线连接组成一个超级簇

(b)由超级簇总线相连的两个超级簇分级层次结构19DASH示例目录每一簇都以目录来记录哪些簇现在拥有哪些块的拷贝缓存（caching）缓存分为两级：第一级缓存和更大的第二级缓存协议（protocul）DASH协议是基于拥有权和置无效的20NUMA多处理机和传统UMA(UniformMemoryAccess)多处理机一样，NUMA机的虚拟地址空间对所有CPU都可见。任何CPU在地址A写入值，接下来别的处理机对A的读操作将读取刚刚写入的值。UMA与NUMA的区别不是在语义上，而是在性能上。在NUMA机上，访问远程存储器要比访问本地存储器慢得多，而硬件缓存并不试图掩盖这个问题。21NUMA示例22NUMA多处理机的属性

可以访问远程存储器。访问远程存储器比访问本地存储器慢。没有缓冲机制隐藏访问远程存储器的时间。23分布式共享系统的比较

24六种共享处理器系统的比较

项多处理机DSM单总线交换NUMA基于页式共享变量基于对象线性、共享虚拟地址空间吗？是是是是否否可能的操作读/写读/写读/写读/写读/写常规有封装及方法？否否否否否是是否由硬件执行远程访问？是是是否否否有独立存储器？是是是否否否谁将远程存储器的访问转化为消息？MMUMMUMMU操作系统运行期系统运行期系统传输介质总线总线总线网络网络网络谁执行数据迁移硬件硬件软件软件软件软件传输单元块块页页共享变量对象25主要内容6.1共享内存6.2一致性模型6.3基于页面的DSM6.4其它的分布式共享内存266.2一致性模型

只允许有一个拷贝可能会带来严重的性能瓶颈。允许多重拷贝可以就简化性能问题。但这又引起了新的问题：即如何保证所有拷贝的一致性。

缓存一致性（coherency）数据在各个缓存中的值保持一致一致性模型软件与存储器间的约定（contract）如果软件遵守约定的规则，存储器就能工作正常。如果软件违反了这些规定，存储器就不再保证操作的正确性

27严格一致性从存储器地址X处读出的值为最近写入X的值

非严格一致性P1:W(x)1P2:R(x)1P1:W(x)1P2:R(x)0R(x)128顺序一致性如果所有进程以一定的顺序执行操作，每一进程的操作都以程序规定的顺序出现，则任何操作的结果都是一样的。每一进程的操作都按程序规定的顺序执行。所有进程看到相同的内存访问操作次序运行同一个程序得到的两个可能的结果P1:W(x)1P2:R(x)0R(x)1P1:W(x)1P2:R(x)1R(x)1293个并行执行的进程4种正确的执行顺序顺序一致性举例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(a,b);print(b,c);print(a,b);

(a)

(b)

(c)

(d)30因果一致性按有无可能的因果联系区分各事件，对于因果相关的写操作，所有进程看到的执行顺序应相同。可能因果相关的写操作应对所有进程可见，且顺序一致。并发写操作在不同机器看来顺序可能是不同的

P1：W(x)1W(x)3P2：R(x)1W(x)2P3：R(x)1R(x)3R(x)2P4：R(x)1R(x)2R(x)3因果一致性存储器允许的序列,但是顺序一致性存储器和严格一致性存储器不允许31因果一致性举例（1）违反因果一致性（2）符合因果一致性P1：W(x)1P2：R(x)1W(x)2P3：R(x)2R(x)1P4：R(x)1R(x)2P1：W(x)1P2：W(x)2P3：R(x)2R(x)1P4：R(x)1R(x)232管道内存（PRAM）一致性同一个进程的写操作的执行次序，其它进程看到的都相同不同进程的写操作的执行次序，不同进程看到的可以是不同的例：符合PRAM一致性，但不符合因果一致性P1：W(x)1P2：R(x)1W(x)2P3：R(x)1R(x)2P4：R(x)2R(x)133管道内存（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:00 Prints:10 Prints:01

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

对同步变量的访问必须是顺序一致性的。在所有前面的写操作完成之前,不能访问同步变量。在前面所有同步变量的访问完成前,不能访问（读或写）数据。

P1：W(x)1W(x)2SP2：R(x)1R(x)2SP3：R(x)2R(x)1SP1:W(x)1W(x)2SP2:S

R(x)136释放一致性获取（acquire）访问用于通知存储器系统临界区已就绪释放(release)访问表明临界区刚退出。

规则在访问共享变量前，所有先前的acquire都必须完成。在进行release前，先前的所有读写操作都必须结束。acquire和release访问必须满足处理机一致性37释放一致性P1：Acq(L)W(x)1W(x)2Rel(L)P2：

Acq(L)R(x)2Rel(L)P3：R(x)1通常，分布式共享存储器在遵守以下规定时就是释放一致的：在访问共享变量前，进程所有先前的获取访问都必须成功地完成。在允许释放访问前，进程先前的所有读写操作都必须结束。获取访问和释放访问必须是处理器一致的。

38释放一致性的应用

急性释放一致性(EAGERreleaseconsistency)当执行了释放操作，执行此操作的处理机将所有修改的数据传给所有那些已经有其缓冲拷贝且可能需要它的处理机惰性释放一致性（LAZYreleaseconsistency）在执行释放时，不发送任何数据。在执行获取操作时，处理机试图从拥有这些变量的机器上取得它们的最新值39入口一致性当存储器满足下列所有条件时，就成为入口一致性存储器：（1）只有某一进程的保护共享变量全部被更新以后，该进程才允许执行同步变量的获取访问；（2）在一进程以互斥模式访问该进程的同步变量之前，不允许其他进程持有此同步变量，即使在非互斥模式下；（3）在结束互斥模式下对一个同步变量的访问后，任意其他进程必须与该变量的拥有者核查，才能试图以非互斥模式访问该同步变量。40一致性模型总结不用同步操作的一致性模型

一致性说明严格所有的共享访问事件都有绝对时间顺序顺序所有进程都以相同的顺序检测到所有的共享访问事件因果所有进程都以相同的顺序检测到所有因果联系的事件PRAM所有的进程按照预定的顺序检测到来自一个处理器的写操作,来自其它处理器的写操作不必以相同的顺序看见处理器PRAM一致性+存储器相关性41一致性模型总结使用同步操作的一致性模型

一致性说明弱同步完成后,共享数据才可能保持一致释放当离开临界区时,共享数据就保持一致入口当进入临界区时,和该临界区相关的共享数据保持一致42主要内容6.1共享内存6.2一致性模型6.3基于页面的DSM6.4其它的分布式共享内存436.3基于页面的DSM局域网上的工作站从根本上不同于多处理机。处理机只能访问本地存储器。不像在NUMA或UMA多处理机系统中，这里没有全局共享变量的概念。然而，DSM的目的就是在系统中增加软件，以允许多计算机系统运行多处理机上的程序。44基本设计

页块：地址空间管理的基本单位0123456789CPU10259CPU21368CPU347CPU4存储器(a)全局共享地址空间101115121314111012141315(b)CPU10259CPU21368CPU347CPU4111214131510(c)CPU10259CPU21368CPU347CPU41110121413151045实现技术虚拟地址空间内存映射（memorymapping）缺页中断（pagefault）46存储映射技术两个进程共享同一个文件47存储映射技术sisanerrorcodeaddrarememoryaddresseslenisalengthprotcontrolsprotectionflagsaremiscellaneousbitsfdisafiledescriptoroffsetisafileoffset48复制复制只读块复制所有页块粒度（Guanularity）页块的大小应是多大：字、块（少量字）、页或段（多个页）。包含两个无关变量的页的错误共享49实现顺序一致性（SequentialConsistency）

多处理机一般有两种处理方法：更新置无效基于分页的DSM系统通常使用置无效协议而不是更新协议50处理机读页举例

PW拥有者1.读PR拥有者1.读PR拥有者1.读页面处理器1处理器2RPR1.读P1.请求复制2.将页标志为R3.读PR拥有者R拥有者W拥有者1.请求降级2.请求复制3.将页标志为R4.读(a)51处理机写页举例

PW拥有者1.写PR拥有者1.将页标志为W2.写入PR拥有者1.无效的拷贝2.将页标志为W3.写入RPR1.请求置无效2.请求拥有者3.将页标志为W4.写入P1.请求置无效2.请求拥有者3.请求页面4.将页标志为W5.写入PR拥有者R拥有者W拥有者1.请求置无效2.请求拥有者3.请求页面4.将页标志为W5.写入(b)52寻找拥有者（FindingTheOwner）

通过广播拥有者定位协议(ownershiplocationpretocol)让每个进程（更可能的是每个处理机）跟踪每一页的可能拥有者53拥有者定位协议

四消息协议三消息协议P拥有者页面管理器1.请求2.响应3.请求4.响应P拥有者页面管理器1.请求3.响应2.移交请求(a)(b)54寻找拷贝.