分布式共享存储器

分布式共享存储器第1页/共73页6.1简介并行及分布式计算机系统分类

并行分布式计算机多处理机（共享存储器）多计算机（私有存储器）总线型总线型交换型交换型MIMD松耦合紧耦合SequentEncore超级计算机RP3LAN工作站

超立方体Transputer第2页/共73页6.1简介

基于总线的多处理机

基于总线的多处理机由若干个CPU组成，它们都连接到一个公共的总线上，并且共享一个存储器模块。为了避免总线过载，需要高速缓存，但带来了不一致问题。连接的CPU数量有限。CacheCPUBusCacheCPUCacheCPUMemory第3页/共73页6.1简介交换型多处理机将存储器分成许多存储器模块，用十字交叉开关将它们与CPU相连。MMMMCCCC优点：多个CPU能够同时访问存储器。缺点：n个CPU和n个存储器模块，需要n2个交叉开关。第4页/共73页6.1简介交换型多处理机Omega网络结论

需要的交叉开关数量多，需要解决交换延迟，价格昂贵。建立一个大的、紧密偶合的、共享存储器的多处理机系统是困难的。CCCCMMMM2x2开关第5页/共73页6.1简介基于总线的多计算机每个CPU都与它自身的存储器直接相连。由于仅是CPU和CPU之间的通信，通信量比当互连网络用于CPU和存储器之间的通信量低几个数量级。CPULocalmemory网络CPULocalmemoryCPULocalmemory图1-4局域网上由多台工作站组成的计算机系统工作站工作站工作站第6页/共73页6.1简介交换型多计算机

两种流行的拓扑结构：网格和超立方体第7页/共73页6.1

简介多处理机和多计算机的比较从硬件角度

设计一种使多个处理机同时使用同一存储器的机器是非常困难的。由于总线会成为一种瓶颈，基于总线的多处理机总数最多只能有几个。交换式多处理机可应用于大系统，但相比之下过于昂贵、缓慢、复杂以及难以维护。大的多计算机系统易于建立，单主板计算机（包含一个CPU、一个存储器、一个网络接口）可以相互连接在一起，不受数量的限制。

结论：从硬件设计者的角度看，多计算机系统比多处理机系统更优越。第8页/共73页6.1

简介多处理机和多计算机的比较从软件角度

用于多处理机编程的技术很多。大量的理论和实践知识可用于多处理机编程。对于多计算机系统，通信一般使用消息传递。复杂。

结论：从软件设计者的角度看，多处理机系统比多计算机系统更优越。

多计算机系统易于建立但难于编程，多处理机系统易于编程但难于建立！第9页/共73页6.1简介分布式共享存储器设计思想一组由局域网互联的工作站共享一个分页的虚拟地址空间。设置每页刚好在一台机器上。对本地页的访问由硬件实现。试图访问其他机器上的页时，由操作系统处理。既易于编程，又易于建立！与虚拟存储器系统比较相同点：当一进程访问一未驻留存储器的页时，激活陷阱，操作系统获取相应页并将其调入。不同点：操作系统不是从磁盘而是通过网络从另一个处理机中获取页。

第10页/共73页6.1简介分布式共享存储器不足之处页在网上频繁的调入调出。改进不共享整个地址空间，而只共享那些由多个进程引用的变量和数据结构。在多台计算机上复制共享变量，通过共享复制的变量而不是整个页。读操作可以可以在本地进行而不引起任何的网络通信，写则可以通过多拷贝更新协议完成。

第11页/共73页6.2共享存储器6.2.1芯片存储器芯片包含CPU和存储器。CPU和存储器通过地址线和数据线直接相连。广泛用于汽车、电气用具、玩具等。将芯片扩展，使多个CPU可以共享同一存储器。不仅复杂，而且非常昂贵和不实用。第12页/共73页6.2共享存储器6.2.2基于总线的多处理机基于总线的多处理机：当任一CPU要从存储器中读取数据时，它将数据的地址放在总线上，并在控制总线上加上“读”信号。存储器读出需要的数据，将其放在总线上，在控制总线上加“准备好”信号，CPU可读到相应的数据。为防止多个CPU同时访问存储器，需要总线仲裁机制。CPU总线CPUCPU存储器第13页/共73页6.2共享存储器6.2.2基于总线的多处理机基于总线的多处理机容易超载。为了降低总线负载，将每个CPU提供一个监听高速缓存。缓存一致性协议总线存储器CPU缓存CPU缓存CPU缓存第14页/共73页6.2

共享存储器6.2.2基于总线的多处理机通写缓存一致性协议

事件缓存响应本地CPU操作时执行的动作缓存响应远程CPU操作时执行的动作读失败从存储器中取得数据并存储到缓存中无动作读命中从本地缓存中取得数据无动作写失败更新存储器中的数据并存储到缓存中无动作写命中更新存储器和缓存使缓存项无效易于理解和使用。缺点：所有写操作必须通过总线。第15页/共73页6.2

共享存储器6.2.2基于总线的多处理机Writeonce协议

思想：允许正被多个CPU读取的字出现在它们所有的缓存中。而仅被一个CPU经常写的字将只保存在它的缓存中，为减少总线流量，不必每次都写回存储器。该协议管理缓存块，每个块处于以下三种状态之一：无效——本缓存块无有效数据干净——存储器被更新，该块可能在别的缓存中脏——存储器错误，该数据块不在其他缓存中第16页/共73页Writeonce协议初始状态含有值W1的字W在主存中，同时也在B的缓存中。ABCW1W1CPU干净存储器正确图6-3（a）第17页/共73页Writeonce协议A读取字W获取W1，B不响应读操作，只是内存响应。ABCW1W1W1CPU干净存储器正确干净图6-3（b）第18页/共73页Writeonce协议A写入值W2，B在总线上监听，一旦发现写操作，将自己的缓存项置无效。A的拷贝标记为脏数据。ABCW1W2W1CPU无效存储器错误脏图6-3（c）第19页/共73页Writeonce协议A再次写W，A所进行的这些和以后的写操作都在本地执行，没有任何的总线通信。ABCW1W3W1CPU无效存储器错误脏图6-3（d）第20页/共73页Writeonce协议C读写W，A通过在总线上监听而发现请求，则发信号禁止存储器响应。然后A提供C所需要的字，并将自己的缓存项置无效。C发现该字来自其他的缓存而不是存储器，并且其状态为Dirty，则响应的标示为dirty。C现在有唯一的有效的拷贝。ABCW1W3W1W3CPU无效存储器错误无效图6-3（e）脏第21页/共73页Writeonce协议存储器何时更新？当缓存缺乏空间而必须清除某一字时，如果该字的状态为dirty。那时，该字从所有的缓存中消失，写回到存储器。缓存一致性协议具有三个重要的属性缓存对总线的监听保证了一致性。协议建立在存储器管理单元中整个算法在一个存储器周期中完成第22页/共73页6.2

共享存储器6.2.3基于环的多处理机一个独立的地址空间被分成一个私有区和一个共享区。私有区被分成段，使得每个机器都有一个段用来存放堆栈和其他非共享的数据和代码。共享区对所有的机器都是一样的。共享存储器被分成32字节的块，是机器间传输的单元。Memnet环第23页/共73页6.2

共享存储器6.2.3基于环的多处理机环接口、MMU（存储器管理单元）、缓存和一部分存储器集成在一个称为Memnet设备的器件中。Memnet中没有集中式的全局存储器。共享地址空间中的每个32字节数据块都有一个属主机器。属主机器在其属主存储器域中为32字节数据块保留物理存储器。数据块可被置于除属主机器以外的任何机器的缓存中。单一主机第24页/共73页6.2

共享存储器6.2.3基于环的多处理机每个机器的Memnet设备上有一个块表，包括每个块在共享地址空间的入口，以块序号为索引。块表有效位：判断块是否在缓存中且已被更新互斥位：确定本地拷贝是否唯一属主位：只有当本机是该块的属主机器时才置位。中断位：用于强制中断定位位：表明若块存在并有效，它定位在缓存中何处。第25页/共73页6.2

共享存储器6.2.3基于环的多处理机读操作当CPU要从共享存储器中读一个字时，该存储器地址传送给Memnet设备，Memnet设备检查表项以确定该块是否存在。若存在，读请求立即的到满足。否则，Memnet设备捕获令牌，将请求信包送入环中。请求信包包含目标地址和32字节的哑域。信包在环中传递，每个Memnet设备检查自己是否有所需的块，若有则将块置于哑域。第26页/共73页6.2

共享存储器6.2.3基于环的多处理机写操作若包含要写字的块存在于本地并且是系统中的唯一拷贝，字就在本地写入。若所需块在本地存在，但不是系统中的唯一拷贝

CPU将在环中发出置无效信包，强制其它机器抛弃此块的拷贝。

置无效信包返回时，将该块的互斥位置位，字在本地写入。第27页/共73页6.2

共享存储器6.2.3基于环的多处理机写操作若本地不存在所需块，CPU发出包含读请求和置无效请求的信包。第一个有此数据块的机器将该块拷入信包，同时抛弃自己的拷贝。其余机器仅从自己的缓存中抛弃该数据块。当信包返回到发送者时，本地存储该数据块并执行写操作。第28页/共73页6.2

共享存储器6.2.3基于环的多处理机Memnet和基于总线的多处理机比较相似之处：读操作返回的都是最近写入的值。读操作时，数据块可能在一个缓存中，也可能在多个缓存中。写操作时，数据块只能在一个缓存中。区别：基于总线的多处理机是紧耦合的，基于环的多处理机是耦合的较松一些。基于环的多处理机没有集中式全局存储器。第29页/共73页6.2

共享存储器6.2.4交换式多处理机基于总线和基于环的多处理机当CPU增加到一定数量时，总线或环的带宽达到饱和。两种方法解决带宽不足问题：减少通信流量增加通信容量增加总线带宽改变互联网络的拓扑结构，增加通信容量。建立层次结构第30页/共73页6.2

共享存储器6.2.4交换式多处理机建立层次结构仍在一根总线上挂一些CPU，当将整个单元看作一个簇。系统中有多个簇，用簇间总线相连。簇内总线簇间总线超级簇间总线第31页/共73页6.2

共享存储器6.2.4交换式多处理机基于网状簇的分层设计16个簇、每簇有一条总线，4个CPU，16M全局存储器和一些I/O设备总共地址空间256M，分为16块，每块16M存储器以16字节的块为单位，因此1簇有1M存储器块。第32页/共73页6.2

共享存储器6.2.4交换式多处理机目录记录哪些簇拥有哪些块的拷贝。因为每簇有1M存储块，目录中有1M个项。每一簇的每个表项保留一个一位的位图，以判定簇是否将该块放入缓冲区。簇0是否拥有存储器中的块3的拷贝第33页/共73页6.2

共享存储器6.2.4交换式多处理机缓存每个缓存块有以下三个状态之一：未缓存——存储器中有此块的唯一拷贝干净——存储器已更新，块可能在若干缓存中脏——存储器错误，块仅在一个缓存中每个缓存块的状态存于其目录项的状态域中第34页/共73页6.2

共享存储器6.2.4交换式多处理机协议（读操作）块状态R的缓存邻近者缓存属主所在簇的存储器簇缓存未缓存发送块到R；标记为干净，仅在R簇的缓存中干净使用块复制块到R的缓存中从存储器到R拷贝块；标记表明仍然在R簇的缓存中脏使用块发送块到R和属主所在簇，通知属主所在簇将其标记为干净，并存储在R所在簇发送块到R和属主所在簇（如果在其他地方缓存过），通知属主所在簇将其标记为干净且它在R簇的缓存中第35页/共73页6.2

共享存储器6.2.4交换式多处理机协议（写操作）块状态R的缓存邻近者缓存属主所在簇的存储器簇缓存未缓存发送块到R；标记为脏，只有在R簇中才缓存干净发送信息给属主所载簇，请求脏状态的唯一拥有权如果被允许，使用块复制块并使其无效，发送信息给属主所在簇，请求脏状态的唯一拥有权发送块给R，将所有的缓存置无效；将它标记为脏并存在于R簇的缓存中脏使用块缓存到缓存地传送到R中，将邻近的拷贝置无效发送块到R和属主所在簇（如果在其他地方缓存过），通知属主所在簇将其标记为脏并只存在于R簇的缓存中第36页/共73页6.2

共享存储器6.2.5NUMA多处理机特点在大型多处理机上实现硬件缓存并不简单。硬件必须维护复杂的数据结构。缓存机制不复杂。NUMA机的虚拟地址空间对所有CPU都可见。任何CPU在地址a写入值，接下来别的处理机对a的读操作将读取刚刚写入的值。第37页/共73页6.2

共享存储器6.2.5NUMA多处理机例子（Cm*）CPU访问存储器时，请求到达CPU的MMU，MMU检查高位地址以确定需要哪块存储器。若为本地地址，MMU仅在本地总线发出请求。若为远程存储器，MMU建立一个包括地址的请求信包，通过簇间总线发送到目的簇。第38页/共73页6.2

共享存储器6.2.5NUMA多处理机例子（BBN碟形）每个CPU和一块存储器直接相连。右边CPU和存储器对和左边的相同。通过8个交换器相连。每个交换器4个入口，4个出口。本地访问的请求直接完成如果访问远程存储器，发送请求信包，通过交换网络将信包发送入相应存储器。第39页/共73页6.2

共享存储器6.2.5NUMA多处理机NUMA机器的三个主要属性可以访问远程存储器访问远程存储器比访问本地存储器慢没有缓冲机制隐藏访问远程存储器的时间NUMA软件设计的一个重要问题是决定每页放在何处以寻求最好的性能第40页/共73页6.2

共享存储器6.2.6分布式共享系统的比较第41页/共73页6.3

一致性模型6.3.1严格一致性严格一致性模型由下述条件定义：从存储器地址X处读出的值为最近写入X的值假定绝对全局时间存在举例：

设X是存储在B机器上的变量，A机器上的进程在T1时刻读X，即发送信包到B以读取X。稍后，在T2时刻，B机器上的进程写X。答：按照严格一致性模型，A应该读取原来的值。

如果T2-T1=1nsA机器与B机器距离3米那么，信号传输的速度应为3*109第42页/共73页6.3

一致性模型6.3.1严格一致性符号表示

P1，P2，….代表不同的进程，直线分割进程，时间轴向右增加

W(X)a:在x处写aR(Y)b：在y处读出值赋给b

变量的初值均为0P1:P2:W(x)1R(x)1P1:P2:W(x)1R(x)0R(x)1

严格一致性模型：读操作所返回的值必须总是反映最近更新的结果。第43页/共73页6.3

一致性模型6.3.2顺序一致性顺序一致性模型由下述条件定义：如果所有进程以一定的顺序执行操作，每一进程的操作都以程序规定的顺序出现，则任何操作的结果都是一样的。要求分布式系统中的所有成员和它们的进程共享一个通用视图，此视图记录了对于共享内存访问操作的顺序。

运行同一个程序得到的两个可能的结果：P1:P2:W(x)1R(x)0R(x)1P1:P2:W(x)1R(x)1R(x)1第44页/共73页6.3

一致性模型6.3.2顺序一致性举例三个并行运行的进程，共享相同的顺序一致分布式共享存储器，都访问变量a，b，c。从存储器访问的角度看，赋值看作是写操作，打印被看作是读操作。

a=1；print(b,c);

b=1；print(a,c);

c=1；print(a,b);第45页/共73页6.3

一致性模型6.3.2顺序一致性举例

4种有效执行的顺序（4/90种）

a=1；print(b,c);

b=1；print(a,c);

c=1；print(a,b);

a=1；b=1；

print(a,c)；print(b,c);

c=1；print(a,b);

b=1；c=1;

print(a,b)；print(a,c);

a=1；print(b,c);

b=1；a=1;

c=1；print(a,c);

print(b,c)；print(a,b);

Prints:001011Signature:001011

Prints:101011Signature:101011

Prints:010111Signature:110101

Prints:111111Signature:111111标记项：顺序输出P1，P2，P3的结果，得到6位字串。<64种第46页/共73页6.3

一致性模型6.3.2顺序一致性Ahamad系统进程i的读写操作顺序由Hi确定，下图显示两种次序H1和H2，分别对应于P1和P2；这种次序的集合称为H。合并H中的操作串为一个单独串S，以得到操作执行的相对顺序。S的合法值须遵守两个限制：（1）维持程序次序（2）保证存储相关性

H1=W(x)1H2=R(x)0R(x)1P1:P2:W(x)1R(x)0R(x)1第47页/共73页6.3

一致性模型6.3.2顺序一致性Ahamad系统维持程序次序：如果在H的一个字串中，读或写访问A出现在另一访问B之前，那么S中的A也应出现在B之前。保证存储相关性：在地址x处读出的值必须是最新写入的x。

H1=W(x)1H2=R(x)0R(x)1P1:P2:W(x)1R(x)0R(x)1根据两个限制，S只有一个合法值：

S=R(x)0W(x)1R(x)1第48页/共73页6.3

一致性模型6.3.3因果一致性因果一致的存储器遵循以下条件：

如果事件是因果相关的，那么它们必须以相同而且是正确的顺序出现在所有成员面前。P1:W(x)1W(x)3P2:R(x)1W(x)2P3:R(x)1R(x)3P4:R(x)1R(x)2R(x)2R(x)3W(x)2和W(x)3是并发的第49页/共73页6.3

一致性模型6.3.3因果一致性因果一致的存储器遵循以下条件：两个写操作存在因果关系：W(x)2可能决定于W(x)1不正确P1:W(x)1P2:R(x)1W(x)2P3:R(x)2P4:R(x)1R(x)1R(x)2P1:W(x)1P2:W(x)2P3:R(x)2P4:R(x)1R(x)1R(x)2正确第50页/共73页6.3

一致性模型6.3.4PRAM一致性和处理器一致性PRAM一致性遵循以下条件：

一个进程的写操作可以被其他进程以指定的顺序接收到，但不同的进程的写操作在不同进程看来次序可以是不同的。

PRAM代表管道RAM。由不同进程产生的写操作是并发的。P1:W(x)1P2:R(x)1W(x)2P3:R(x)1P4:R(x)2R(x)2R(x)1PRAM一致性的有效事件序第51页/共73页6.3

一致性模型6.3.4PRAM一致性和处理器一致性PRAM一致性举例：三个不同进程看到的语句执行顺序

a=1；*print(b,c);

b=1；print(a,c);

c=1；print(a,b);

a=1；b=1；*print(a,c)；print(b,c);

c=1；print(a,b);

b=1；print(a,c);

c=1；*print(a,b);

a=1；print(b,c);

Prints:00

Prints:10

Prints:01

将三个进程输出顺序相接，得到：001001。在顺序一致性下是不可能的。第52页/共73页6.3

一致性模型6.3.4PRAM一致性和处理器一致性处理器一致性举例

a=1;if(b==0)kill(P2);

两个并行的进程P1和P2处理器一致性模型：若P1在看到P2的b赋值之前读取b，P2在看到P1中的a赋值之前读取a，那么两个进程都被kill。顺序一致性模型：6种顺序。但不可能导致两个进程都被kill。

b=1;if(a==0)kill(P1);第53页/共73页6.3

一致性模型6.3.5弱一致性同步变量：用于向其它机器传播写操作，对于全局数据在其它地方出现的修改作本地更新。弱一致性的三个属性：

对同步变量的访问是顺序一致的。

在所有的先前的写操作完成之前，不能访问同步变量。在先前所有同步变量的访问完成前，不能访问（读或写）数据。P1:W(x)1P2:SW(x)2P3:R(x)2R(x)1R(x)1R(x)2P1:W(x)1P2:SW(x)2SR(x)1弱一致性事件有效序列弱一致性事件无效序列第54页/共73页6.3

一致性模型6.3.6释放一致性获得访问权：通知系统进程正准备进入临界区，所有其它成员所做的修改结果都要加以传播，并由本地的处理器来更新。释放访问权：通知系统，进程准备退出临界区，对共享内存所作的本地修改将传播到其它的各个成员。分布式共享存储器在遵守以下规定时是释放一致的在访问共享变量前，进程所有先前的获取访问都必须成功地完成；在允许释放访问前，进程先前的所有读写操作都必须结束；获取访问和释放访问必须是处理器一致的。第55页/共73页6.3

一致性模型6.3.6释放一致性举例释放一致性的有效序列P1:W(x)1P2:Rel(L)W(x)2P3:R(x)1R(x)2Acq(L)Acq(L)Rel(L)说明：进程P1执行获取访问，两次改变共享变量，然后执行释放操作进程P2执行获取访问，读取x。进程P3读共享变量，但在读共享变量前没有执行获取访问第56页/共73页6.3

一致性模型6.3.7入口一致性分布式共享存储器在遵守以下规定时是入口一致的只有某一进程的保护共享变量全部被更新后，该进程才允许执行同步变量的获取访问在一进程以互斥模式访问该进程的同步变量前，不允许其他进程持有此同步变量，即使在非互斥模式下。在结束互斥模式下对一个同步变量的访问后，任意其他进程必须与该变量的拥有者核查，才能试图以非互斥模式访问该同步变量。第57页/共73页6.3

一致性模型6.3.8一致性模型总结不用同步操作的一致性模型（限制程度递减顺序）一致性说明严格所有的共享访问事件都有绝对时间顺序顺序所有进程都以相同的顺序检测到所有的共享访问事件因果所有进程都以相同的顺序检测到所有因果联系的事件处理器PRAM一致性+存储器相关性PRAM所有的进程按照预定的顺序检测到来自一个处理器的写操作，来自其他处理器的写操作不必以相同的顺序出现第58页/共73页6.3

一致性模型6.3.8一致性模型总结使用同步操作的一致性模型一致性说明弱同步完成后，共享数据才能保持一致释放当离开临界区时，共享数据就保持一致入口当进入临界区时，和该临界区相关的共享数据保持一致性第59页/共73页6.4

基于分页的分布式共享存储器6.4.1基本设计DSM系统设计思想试图使用MMU或操作系统软件模仿多处理机中的缓存。地址空间被分成大的页块，散布在系统中的所有的处理机上。第60页/共73页6.4

基于分页的分布式共享存储器6.4.1基本设计DSM系统设计思想如果处理机访问的指令或数据所在块不在本地，会激活DSM系统软件的陷阱程序，软件将该块从那台机器移到本地机器上。当CPU1访问地址块10后的情形第61页/共73页6.4

基于分页的分布式共享存储器6.4.2复制复制只读块复制如程序文本、固定的内容以及其他只读的数据结构，提高系统性能。地址块10为只读且使用复制后的情形第62页/共73页6.4

基于分页的分布式共享存储器6.4.3粒度页调入所需的整个页。由于使用相同的单元，设计简单。缺页中断时，所缺页从另一机器而不是磁盘中换入，处理缺页中断的代码和传统相同。段优点：当移动大量地址空间时，使用大单元传输数据可以减少传输的次数。可以很快访问保存在本地的页。缺点：大量的传输使网络连接更紧密，可能会阻塞其他进程的缺页中断。有效页太大会产生“错误共享”问题。第63页/共73页6.4

基于分页的分布式共享存储器6.4.3粒度段错误共享：无关的变量出现在同一页上，当一进程使用他们之一时，进程也得到了其他的变量。有效页越大，发生错误共享的可能性越大。AB

使用A的代码处理器1AB

使用B的代码处理器2

两个无关的共享变量

共享页包含两个无关变量的页的错误共享第64页/共73页6.4

基于分页的分布式共