复习真是一种享受啊，很喜欢这种大段文字从视网膜穿过的感觉
要飞天了，好爽
基本概念（？）
什么是分布式共享存储器
分布式共享存储器系统是分布式操作系统中的一个资源管理部件，它在没有物理上共享的存储器的分布式操作系统中实现了共享存储器模式。这种共享存储器模式在分布式系统中提供了一个可供系统内所有节点所共享的虚拟地址空间。程序设计者可以像使用传统的存储器一样使用该虚拟地址空间。这种物理上分布逻辑上共享的存储器就叫做分布式共享存储器(Distributed Shared Memory—DSM)。
每一个节点都可以拥有存储在共享空间的数据，数据的所有者也可以跟随数据从一个节点移到另一个节点。当一个进程访问共享地址空间中的数据时，映像管理员就把共享存储器地址变换到本地地址或远程的物理存储器地址。
为什么要分布式共享存储器
DSM的计算模型和RPC的计算模型相比各有优缺点：
- DSM的计算模型支持数据在系统内移动，使数据更容易访问。
- RPC计算模型是把操作移到数据所在位置。RPC不支持程序利用其访问的局部性优点，对一块远程数据的每个操作都产生通信，对数据的操作必须先定义好。但是RPC支持异构型。
- DSM可把数据移到本地节点，允许程序利用其访问的局部性优点，使用缓存器可以改善响应时间。移动性要求对数据位置进行跟踪；缓存要求解决各副本的一致性。当数据正向某个主机移动时，不能对它进行处理。如果数据经常修改，RPC模型可能更好些。
从通信机制来看，DSM与报文传递方式有以下不同 ：
- 访问的透明性。使用报文传递方式访问共享的数据变量时，程序必须明确地使用节点地址信息和通信原语(如SEND和RECEIVE)。而在DSM中系统提供了一种抽象的共享地址空间从而隐匿了物理地址和通信细节，使得程序直接面向共享的数据。
- 共享数据结构的复杂性和异构性。使用报文传递方式，由于数据是在不同的地址空间之间传递，从而使得具有复杂数据结构的数据难于在不同类型的计算机及进程之间传递。而在DSM中，可以借助引用机制(reference)去实现上述数据访问，复杂性与异构性的问题由引用机制去处理，从而进一步简化了并行程序设计。
- 数据的局部性。在DSM中，新访问的数据项与其周围的数据一起按块或按页移动，而不是只移动新访问的数据本身。根据程序的局部性原理，这样可以大大地减小网络的通信开销。
与紧密耦合的多机系统相比，DSM系统具有以下特点：
- 规模可扩充。在紧密耦合的多机系统中，由于各处理机共享的是一个单一的物理存储器，主存访问都要经过一个集中环节(例如总线)进行，这就限制了多机系统的规模(一般为几十台处理机)。DSM不存在这样的限制，可以扩充至很大的规模(多至上千个节点)。
- 廉价。由于DSM系统可以用现有的硬件来构造，并且无需连接共享存储器与处理机的复杂接口，因而DSM的构造成本要低于紧密耦合的多机系统。
- 兼容性。在共享存储器多机系统上编写的程序原则上都可以无需修改或稍加修改后转换到DSM系统上运行。
缓存一致性方法
探听缓存方法、使用目录的方法
探听(snooping)缓存方法用于具有广播能力的通信介质中，例如共享总线。每个缓存器为了保持自己数据的一致性要监听共享总线上进行的由其他处理机发出的存储器操作。
Berkeley是一种写无效协议，它假设通过单总线访问共享的物理存储器。此协议采用一个所有权方案。一个数据块的所有者是一个缓存器，是上次对该数据块的修改者，如果该块被其所有者清除，则主存作为其所有者。
Berkeley探听协议数据块有四种状态：重写(dirty)、共享重写、有效和无效：
- 无效。该缓存块不包含有效数据。
- 有效。该缓存块中数据是有效的。
- 重写。共享存储器中的数据是不正确的，该缓存块是唯一有效的数据副本。该缓存块是数据的所有者。
- 共享重写。共享存储器中的数据是不正确的，该缓存块是数据的所有者，其他缓存中有同样的副本。
探听协议的写操作：数据只能由所有者提供。有效块和无效块在替换时可以简单地扔掉。重写块和共享重写块在替换时要写回共享存储器，并把共享存储器设置为所有者。如果对缓存块进行写，而缓存块的状态是重写的，则写操作可以直接进行；但是如果缓存块是共享重写、或有效，则必须向其他缓存器发送“无效”信号，然后可以进行写操作；如果缓存块是无效的，要从当前所有者那里取得数据块，再向其他缓存器发送“无效”信号，然后可以进行写操作。
目录协议：在共享存储器中设置存储器块的目录。当发生缓存不命中时，先把请求转到此目录。通常目录项中包含所有权、副本集(copyset)和该块的重写位。副本集指出该块数据在哪些缓存器中有副本，可用位向量来实现。发生读未命中时，先检查重写位，如果该块不处于重写状态，则共享存储器中的版本是有效的，于是简单地返回该块，并对副本集信息进行更新；如果该块的重写位置位，则该块的所有者必须修改该块，并且要更新共享存储器中的版本，向读者提供读副本。写未命中或者从读权变成写权时，要求目录的副本集使其他副本无效。与探听缓存方案不同，读副本的位置都已经知道，因此，可以用顺序方式而不是以广播方式发送“无效”报文。目录方案不要求广播介质，但在每次缓存未命中时要增加一次查表。
DSM的设计与实现问题：略
一致性语义
- 严格一致性。对一个数据项所进行的任何读操作所返回的值总是对该数据项最近一次进行写操作的结果。
- 顺序一致性。所有进程对数据项的所有操作可以认为是按照某个顺序进行的，任何进程对这个顺序的观点是一样的。
- 处理机一致性。不仅要求一个进程中的所有写操作能够以它在该进程中出现的顺序被所有其他进程看见，还要求不同进程对同一个数据项的写操作，应该被所有进程以相同的顺序看见。
- 弱一致性。程序员使用同步算符，使得对数据的多个操作组来说是顺序一致性的。即不同进程的多个操作组可以认为是按照某个顺序进行的，任何进程对这个顺序的观点是一样的。但是操作组内的多个操作其他进程是不可见的。对同步算符是顺序一致性的。
- 释放一致性。使用了“获得”和“释放”这两类同步算符，对同步算符是处理机一致的。
实现DSM的算法
| 非复制 | 复制 | |
|---|---|---|
| 非迁移 | 中央服务员 | 全复制 |
| 迁移 | 迁移 | 读复制 |
中央服务员算法
使用一个中央服务员，负责为所有对共享数据的访问提供服务并保持共享数据唯一的副本。读和写操作都包括由执行该操作的进程向中央服务员发送请求报文，中央服务员执行请求并回答，读操作时回答数据项，写操作时回答一个承认。
迁移算法
数据总是被迁移到访问它的节点。这是一个“单读者/单写者”(SRSW)协议，因为在整个系统中，一次只有一个进程读或写一个给定的数据项。
读复制算法
对于一个当前不在本地的块中的一个数据项进行读操作时，先与远程节点通信以获得那个块的一个只读副本，然后再进行读操作。若被执行写操作的数据所在的块不在本地或在本地但主机无写权时，必须先使此块在其他节点的所有副本无效，之后再进行写操作。
全复制算法
全复制算法允许数据块在进行写时也可以复制，因而它遵从了“多读者/多写者”(MRMW)协议。保持复制数据一致性的一种可能的方法是对所有的写操作进行全局排序，而只对与发生在执行读操作节点上的写操作相关的那些读操作进行排序 。
性能和代价
不会算
使用目录的DSM
不用广播的缓存器一致性协议必须保存每块共享数据的所有缓存器副本的位置。此缓存位置表，不管是集中的还是分散的，都叫做目录。
每个数据的目录项包括许多指针，用来指出此块各副本所在位置。每一个目录项还有一个“重写”位用来指明是否允许某一个(只有一个)缓存器进行写。
目录协议有三种主要类型：全映像目录、有限目录和链式目录 。全映像目录的每个目录项保持N个指针，这里N是系统中处理器的个数。有限目录和全映像目录的不同之处在于，有限目录的每个目录项具有固定数量的指针，与系统中处理机数量无关。链式目录与全映像目录相似，只是它将目录分布于各缓存器。
全映像目录
全映像目录协议使用的目录每项包含每个处理机，有一个指针并且有一个“重写”位。指针所对应的每一位代表该块在相应处理机缓存器中的状态(存在或不存在)。如果“重写”位置位，那么有且只有一个处理机的指针位被置位，允许这个处理机对该数据块进行写操作。缓存器保存每块数据的两个状态位：一位表明此数据块是否有效，另一位表明一个有效的数据块是否可写。缓存器一致性协议必须在存储器目录中保存这些状态位，并维持缓存一致性。
写过程：
- C3检测到包含单元X的数据块是有效的，但是该处理机对数据块无写的权限，这由块的允许写位表示。
- C3发出一个对包含单元X的存储模块的写请求，并且停止处理机P3。
- 存储器模块向C1和C2发出无效请求。
- C1和C2收到无效请求后，设置对应的位指出包含单元X的数据块是无效的，并向存储器模块发回一个承认。
- 存储器模块收到这个承认，将“重写”位置位，清除指向C1和C2的指针，并向C3发出写允许报文。
- C3收到写允许报文，更新该缓存器中的状态，并且激活处理机P3。
有限目录:限制了缓存数，解决了目录大小问题
链式目录：保持一个目录指针链对共享副本进行跟踪
缓存器块的替换 ：假设从C1到CN都有单元X的副本，并且单元X和单元Y都直接映射到缓存器同一行上。如果处理机Pi读单元Y，必须从它的缓存器中先驱逐单元X。在这种情况下，有两种可能性：
- 沿着链路向Ci-1发送一个报文，将Ci-1的指针指向Ci+1，将Ci从链路中脱离开。
- 使从Ci到CN中的单元X无效。
双向链式结构：另外一种解决替换问题的方法是使用双向链。这种方案为每个缓存器副本保持一个向前和一个向后的指针，这样当缓存器替换时，协议不必遍历整个链。双向链目录优化替换条件是以更大的平均报文长度(由于传送更多的目录指针)、缓存器中的指针的存储空间加倍和更为复杂的一致性协议为代价的。
DSM系统的实现
不记得了，就算没讲吧