分布式操作系统

第6章分布式共享存储中国科技大学软件学院丁箐2主要内容6.1共享内存6.2一致性模型6.3基于页面的DSM6.4其它的分布式共享内存3主要内容6.1共享内存6.2一致性模型6.3基于页面的DSM6.4其它的分布式共享内存4多处理机和多计算机回顾对硬件的影响–设计一种使多个处理机同时使用同一存储器的机器是非常困难的–大的多计算机系统更易于建立对软件的影响–用于多处理机编程的技术很多，可以使用临界区（criticalregion），信号量或管程（monitor）提供必要的互斥。–对多计算机系统，通信一般使用消息传递，这使输入/输出更为抽象。消息传递带来了许多复杂的问题，5分布式共享存储器(DSM)Li和Hudak提出让一组由局域网互连的工作站共享一个分页的虚拟地址空间。不共享整个地址空间，而只共享其中所选择的一部分，即那些由多个进程引用的变量和数据结构。在多台计算机上复制共享变量，通过共享复制的变量而不是整个页，模拟处理机的问题可简化为保证一组数据结构的多个拷贝一致性的问题。6DSM的很多研究工作都受到了多处理机结构发展的启发!首先比较几种共享存储器（内存）的多处理机7芯片存储器CPU与存储器连接模型单片机理想的共享存储器多处理机8PentiumDwith975XChipsetInter-CoreBusInterfaceMemoryControllerHubI/OControllerHubDDR2MemoryPCIExpressx166PCI4SerialATAPorts6PCIExpressx1High-DefinitionAudio2PCIExpressx8orDMI(2GB/s)1066/800MHzFSBCore1L2Cache(forCore1)Core0L2Cache(forCore0)6USB2.0IntelMatrixStorageBIOSSupportIntelPro1000LAN91.多处理器结构2.带缓存的多处理器结构总线仲裁机制：集中式和非集中式基于总线的多处理机CPU内存总线(a)总线(b)缓存CPUCPUCPU内存缓存CPU缓存CPU10通写缓冲(write-though)一致性协议事件对本地CPU操作响应对远程CPU响应读失败（miss）从内存中取得数据并存储到缓存中（MC）（无动作）读命中(hit)从本地缓存中取得数据（无动作）写失败更新内存中的数据并存储到缓存中（CM）（无动作）写命中更新存储器和缓存（MCM）置为无效11缓存拥有权（ownership）协议Cache分成若干个cache块每个Cache块处于三种状态：1.Invalid－数据无效2.Clean－与存储器数据一致3.Dirty－数据被更新，与存储器数据不一致各CPU监听（snoopy）其它CPU在总线的操作12缓存拥有权（ownership）协议多个CPU可有读拥有权只有一个CPU有写拥有权当一个CPU写一个数据–取得对该数据的拥有权–其它CPU将该数据的缓存块置为“invalid”–在本地缓存块中，写数据，并置为“dirty”–适当时候，刷新存储区，或提供给其它CPU13缓存拥有权（ownership）协议特点1.通过各CPU对总线的监听保持缓存一致性2.该协议实现在存储器管理单元中3.整个算法在一个存储器周期中完成召回（callback）协议•如果用软件实现14缓存拥有权协议操作过程ABCW1W1存储器正确干净ABCW1W1W1存储器正确干净干净(a)(b)含有值的字W在主存中,同时也在B的缓存中W1A读取字W获取W1B不响应读操作而是内存响应初始状态CPU15缓存拥有权协议操作过程ABCW1W1存储器正确无效脏ABCW1W1存储器正确无效脏(c)(d)W2W3ABCW1W1存储器正确无效无效(e)W3A写入值B在总线上监听,一旦发现写操作,就将自己的项置为无效.A的拷贝被标记为脏数据W2A再次写W.A所进行的这些和以后的写操作都在本地执行,没有任何的总线通信C读写W.A通过在总线上监听而发现请求,提供数值,将自己的项置无效.C现在有唯一有效的拷贝.脏W316重要属性缓存对总线的监听保证了一致性。协议建立在存储器管理单元中。整个算法在一个存储器周期中完成。17基于环的多处理机没有集中式全局存储器耦合得较松一些CPUCPUCPUCPUCPUCPU(a)MMU缓存属主存储器CPU私有存储器(b)01234≈≈定位位中断位属主位互斥位有效位(c)块(a)Memnet环(b)单一主机(c)块表18交换式多处理机CPU增加到一定数量时，总线或环的带宽达到饱和，再增加额外的CPU也不会提高系统性能减少通信流量采用两种方法解决带宽不足的问题减少通信流量–改善缓冲协议，优化块大小，重组程序，以提高存储器访问的本地命中率。增加通信容量–改变拓扑结构–为系统建立层次结构19(a)三个簇由簇间总线连接组成一个超级簇(b)由超级簇总线相连的两个超级簇CCCMCCCMCCCMCCCMCCCMCCCMCCCMCCCMCCCM存储器簇CPU簇间总线簇间总线超级簇间总线接口(a)(b)分级层次结构20DASH示例目录–每一簇都以目录来记录哪些簇现在拥有哪些块的拷贝缓存（caching）–缓存分为两级：第一级缓存和更大的第二级缓存协议（protocul）–DASH协议是基于拥有权和置无效的21NUMA多处理机和传统UMA(UniformMemoryAccess)多处理机一样，NUMA机的虚拟地址空间对所有CPU都可见。任何CPU在地址A写入值，接下来别的处理机对A的读操作将读取刚刚写入的值。UMA与NUMA的区别不是在语义上，而是在性能上。在NUMA机上，访问远程存储器要比访问本地存储器慢得多，而硬件缓存并不试图掩盖这个问题。22NUMA示例12131415891011456701238910114567012312131415CPUsCPUs交换器(b)CPUMI/OCPUMI/OCPUMI/O本地总线本地存储器微程序控制存储器管理单元MMU簇间总线(a)簇23NUMA多处理机的属性可以访问远程存储器。访问远程存储器比访问本地存储器慢。没有缓冲机制隐藏访问远程存储器的时间。24分布式共享系统的比较单总线多处理机交换式多处理机NUMA机基于页的DSM基于对象的DSM变量共享的DSM由MMU管理由OS管理由语言运行期管理硬件控制缓存软件控制缓存SequentFireflyDashAlewifeCm*ButterflylvyMirageMuninMidwayLindaOrca缓存块紧耦合松耦合缓存块页页数据结构对象传输单元由硬件实现远程访问由软件实现远程访问25六种共享处理器系统的比较项多处理机DSM单总线交换NUMA基于页式共享变量基于对象线性、共享虚拟地址空间吗？是是是是否否可能的操作读/写读/写读/写读/写读/写常规有封装及方法？否否否否否是是否由硬件执行远程访问？是是是否否否有独立存储器？是是是否否否谁将远程存储器的访问转化为消息？MMUMMUMMU操作系统运行期系统运行期系统传输介质总线总线总线网络网络网络谁执行数据迁移硬件硬件软件软件软件软件传输单元块块页页共享变量对象26主要内容6.1共享内存6.2一致性模型6.3基于页面的DSM6.4其它的分布式共享内存276.2一致性模型只允许有一个拷贝可能会带来严重的性能瓶颈。允许多重拷贝可以就简化性能问题。但这又引起了新的问题：即如何保证所有拷贝的一致性。缓存一致性（coherency）–数据在各个缓存中的值保持一致一致性模型–软件与存储器间的约定（contract）–如果软件遵守约定的规则，存储器就能工作正常。–如果软件违反了这些规定，存储器就不再保证操作的正确性28严格一致性从存储器地址X处读出的值为最近写入X的值非严格一致性P1:W(x)1P2:R(x)1P1:W(x)1P2:R(x)0R(x)129顺序一致性如果所有进程以一定的顺序执行操作，每一进程的操作都以程序规定的顺序出现，则任何操作的结果都是一样的。每一进程的操作都按程序规定的顺序执行。所有进程看到相同的内存访问操作次序运行同一个程序得到的两个可能的结果P1:W(x)1P2:R(x)0R(x)1P1:W(x)1P2:R(x)1R(x)1303个并行执行的进程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)31因果一致性按有无可能的因果联系区分各事件，对于因果相关的写操作，所有进程看到的执行顺序应相同。可能因果相关的写操作应对所有进程可见，且顺序一致。并发写操作在不同机器看来顺序可能是不同的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因果一致性存储器允许的序列,但是顺序一致性存储器和严格一致性存储器不允许32因果一致性举例（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)233管道内存（PRAM）一致性同一个进程的写操作的执行次序，其它进程看到的都相同不同进程的写操作的执行次序，不同进程看到的可以是不同的例：符合PRAM一致性，但不符合因果一致性P1：W(x)1P2：R(x)1W(x)2P3：R(x)1R(x)2P4：R(x)2R(x)134管道内存（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)print(b,c);(a)a=1;print(a,c);(b)b=1;print(a,b);(c)c=1;35处理机一致性与PRAM一致性相似附加条件：–存储相关性：对于任意存储器地址X,对于写入X的顺序是全局一致的。–写入不同地址,对于不同进程来看,不需要相同顺序36弱一致性同步变量：广播导出所有写操作，导入所有写操作对同步变量的访问必须是顺序一致性的。在所有前面的写操作完成之前,不能访问同步变量。在前面所有同步变量的访问完成前,不能访问（读或写）数据。P1：W(x)1W(x)2SP2：R(x)1R(x)2SP3：R(x)2R(x)1SP1:W(x)1W(x)2SP2:SR(x)137释放一致性获取（acquire）访问用于通知存储器系统临界区已就绪释放(release)访问表明临界区刚退出。规则–在访问共享变量前，所有先前的acquire都必须完成。–在进行release前，先前的所有读写操作都必须结束。–acquire和release访问必须满足处理机一致性38释放一致性P1：Acq(L)W(x)1W(x)2Rel(L)P2：Acq(L)R(x)2Rel(L)P3：R(x)1通常，分布式共享存储器在遵守以下规定时就是释放一致的：–在访问共享变量前，进程所有先前的获取访问都必须成功地完成。–在允许释放访问前，进程先前的所有读写操作都必须结束。–获取访问和释放访问必须是处理器一致的。39释放一致性的应用急