课件分布式系统dos ch7consistency

第7章分布式一致性

东北大学信息学院张天成谷峪2014年11月2主要内容7.1一致性与复制7.2以数据为中心的一致性模型7.3以客户为中心的一致性模型7.4复制管理7.5一致性协议*

7.6分布式共享内存（DSM)*

7.7举例：基于页面的DSM7.8习题36.1一致性与复制复制的理由提高可靠性：防止单点失败，数据校验提高性能：并行性，可伸缩性复制的代价一致性维护：更新问题例1：Web页的Cache例2：镜像网站☺Internet☺☺☺4对象复制问题（1）单副本对象的同步控制例：两个客户并发访问一个分布式远程对象5对象复制问题（2）单副本同步控制方法由远程对象自己处理对它的并发调用。如Java,同时只允许执行一个方法线程(b)由对象适配器处理并发调用如一个对象一个线程6对象复制问题（3）多副本对象的同步控制方法(a)构造感知复制对象，由对象自己保证一致性(b)由分布式系统负责复制管理，由系统保证对副本访问的正确次序例，CORBA中，支持全序的、因果一致性的对象调用7支持伸缩性的复制技术将数据的副本放置在处理它们的进程附近以减少访问时间，解决可伸缩性问题复制策略设进程P对数据d的访问N次/秒，d的更新M次/秒当N<<M时，访问/更新比非常低，由于一致性维护带来更大代价，因此，不应复制Internet客户服务器8支持伸缩性的复制技术一致性维护与可伸缩性问题保证所有的副本都是相同的，--〉紧密一致性当某个副本上执行更新操作时，需对所有副本进行全局同步，在大型系统上很难实施--〉可伸缩性问题解决策略松驰一致性，所有副本不一定保持完全相同，尽量减少立即的全局同步97.2以数据为中心的一致性模型分布式数据仓(datastore)模型物理上，分布的和复制的例如，分布式共享内存、数据库、文件操作：每个进程可执行读操作，写操作写操作在本地副本上进行，再传播给其他副本10一致性模型数据相干性（coherency）同一个数据在各个数据仓中的值保持一致从单个数据的视角一致性模型多个进程与多个数据之间的操作，保持一致性进程与数据仓之间的契约(contract)如果进程遵守约定的规则，数据仓就能工作正常。如果进程违反了这些规则，数据仓就不再保证操作的正确性11连续一致性模型连续一致性（continuousconsistency）（数值误差，次序误差，陈旧度）数值误差：未传播的写操作的权重值次序误差：临时写操作的个数陈旧度：写操作传播的延迟12连续一致性模型一致性单元（conit）：受控的数据集举例：conit（x,y）13连续一致性模型原文：HaifengYu,AminVahdat:Designandevaluationofaconit-basedcontinuousconsistencymodelforreplicatedservices.ACMTrans.Comput.Syst.20(3):239-282(2002)

举例：conit（x,y）14一致性单元的粒度选择粗粒度：任一个更新操作都导致更新传播虚假共享问题细粒度：当一个数据更新时，另一个数据无需更新15严格一致性规则：对数据项x的读操作返回的值为最近写入x的值特点：绝对全局时间次序例：严格一致性：101S1S2时间P1:W(x)1P2:R(x)1时间16严格一致性不可实现性没有全局时钟光速限制：t1:W1(x)→S2,t2:R2(x);如t2-t1=10-9秒，S1和S2的距离为3米，则需要10倍的光速进行传输例：非严格一致性101S1S20时间P1:W(x)1P2:R(x)0R(x)1时间17顺序一致性规则：所有进程执行的结果，等同于它们的操作按某种顺序在数据仓上执行的结果。每个进程的操作都按照程序规定的顺序。例：顺序一致性P2P1P4P3P1:W(x)1P2:W(x)2P3:R(x)2R(x)1P4:R(x)2R(x)1时间18顺序一致性所有进程看到相同的内存访问操作次序等价于数据库的可串行化（serializability）操作粒度：命令vs.事务例：非顺序一致性P1:W(x)1P2:W(x)2P3:R(x)2R(x)1P4:R(x)1R(x)2P2P1P4P3时间19例：3个并行执行的进程90种正确的执行顺序顺序一致性举例x=1;print((y,z);y=1;print(x,z);z=1;print(x,y);Prints:001011(a)x=1;y=1;print(x,z);print(y,z);z=1;print(x,y);Prints:101011(b)y=1;z=1;print(x,y);print(x,z);x=1;print(y,z);Prints:010111(c)y=1;x=1;z=1;print(x,z);print(y,z);print(x,y);Prints:111111(d)P1P2P3x=1;print(y,z);y=1;print(x,z);z=1;print(x,y);20形式化描述执行(Execution)：进程Pi在数据仓S上的读写操作序列，记为Ei例：E1=W1(x)1;E2=W2(x)2;

E3=R3(x)2,R3(x)1

E4=R4(x)2,R4(x)1历程(History):合并E1,E2,..,En后的序列就像在一个集中式数据仓上执行顺序一致性P1:W(x)1P2:W(x)2P3:R(x)2R(x)1P4:R(x)2R(x)1时间21合法历程：保持程序的操作次序符合数据相干性例：H=W2(x)2,R3(x)2,R4(x)2,W1(x)1,R3(x)1,R4(x)1非法历程例：H=W2(x)2,R3(x)2,R4(x)1,R4(x)2,W1(x)1,R3(x)1性能问题：设读操作时间为r,写操作时间为w,包传输时间为t则r+w≥t。如果减少r时间,则必然增加w时间顺序一致性22线性一致性（Linearizable）规则：具有顺序一致性，且如果tsop1(x)<tsop2(y)，则OP1(x)OP2(y)每个操作带有全局时钟戳执行结果是顺序一致性的每个进程的操作遵照时间戳顺序23因果一致性因果关系(Causality)：P1写x,P2读x,然后写y，则W2(y)与W1(x)具有潜在的因果关系。否则，操作之间的关系为并发(Concurrent)关系例：P1写x,P2写z，则W1(x)与W2(z)不具有潜在因果关系。定义：对于具有潜在因果关系的写操作，所有进程看到的执行顺序应相同。并发写操作在不同主机上被看到的顺序可以不同。24因果一致性例：因果一致性例：违反因果一致性P1：W(x)1W(x)3P2：R(x)1W(x)2P3：R(x)1

R(x)3

R(x)2P4：R(x)1

R(x)2

R(x)3P1：W(x)1P2：R(x)1W(x)2P3：R(x)2

R(x)1P4：R(x)1

R(x)225因果一致性例：符合因果一致性实现技术操作依赖图向量时钟(vectorclock)P1：W(x)1P2：W(x)2P3：R(x)2R(x)1P4：R(x)1R(x)226FIFO一致性规则：同一个进程的写操作的执行次序，其它进程看到的都相同。不同进程的写操作的执行次序，不同进程看到的可以是不同的例：符合FIFO一致性，但不符合因果一致性P1：W(x)1P2：R(x)1W(x)2W(x)3P3：R(x)2R(x)1R(x)3P4：R(x)1R(x)2

R(x)327FIFO一致性例：符合FIFO一致性，可输出“001001”,但不符合顺序一致性ProcessP1ProcessP2ProcessP3x=1;print(y,z);y=1;print(x,z);z=1;print(x,y);y=1;print(x,z);z=1;print(x,y);x=1;print(y,z);Prints:01(c)x=1;y=1;print(x,z);print(y,z);z=1;print(x,y);Prints:10(b)x=1;print(y,z);y=1;print(x,z);z=1;print(x,y);Prints:00(a)P1P2P3P1P2P3P2P3P128FIFO一致性也称作内存管道一致性(PipelinedRAM)分布式共享内存系统实现技术：写操作标签（进程ID,顺序号）29处理机一致性*规则：与FIFO一致性相似附加条件：存储相干性：对于任意存储器地址X,对于写入X的顺序是全局一致的。写入不同地址,对于不同进程来看,不需要相同顺序30同步变量：与一个数据区相关联Synchronize(S)同步所有的数据局部拷贝导出：导入：规则：对同步变量的访问必须满足顺序一致性。在所有先前的写操作完成之前,不能访问同步变量在所有先前的同步操作完成之前,不能访问（读/写）数据。

分组操作--弱一致性写者读者31弱一致性例：弱一致性例：非弱一致性

P1：W(x)1W(x)2

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

SP2:S

R(x)132释放一致性(1)被保护数据：需要保持一致的共享数据Acquire(L)操作：进入临界区导入数据：使被保护数据的局部拷贝与远程的最新版本一致Release(L)操作：退出临界区导出数据：将被保护数据上的变化传播到其它的局部拷贝上33释放一致性(2)规则在访问共享数据前，所有先前的acquire操作都必须完成。在执行release前，先前的所有读写操作都必须完成。对同步变量的访问必须满足FIFO一致性例：符合释放一致性P1：Acq(L)W(x)1W(x)2Rel(L)P2：Acq(L)R(x)2Rel(L)P3：R(x)134释放一致性(3)及时释放一致性(EAGERrelease)当执行了释放操作，执行此操作的处理机将所有修改的数据传给所有那些已经有其缓冲拷贝且可能需要它的处理机滞后释放一致性（LAZYrelease）在执行释放时，不发送任何数据。在执行获取操作时，处理机试图从拥有这些变量的机器上取得它们的最新值

35入口项一致性（1）同步变量与某个共享数据项相关联不是与数据区中的所有保护型数据关联拥有者(owner)：最后一个获取（acquire）它的进程。其他进程必须从当前所有者手中取得拥有权。非互斥方式（non-exclusive）:可以读，但不能写多个进程可以非互斥方式同时拥有一个同步变量36入口项一致性（2）规则：在进程P获取同步变量S之前，有关的被保护的共享数据上的全部更新操作都必须完成；在进程P以互斥模式访问同步变量S之前，不允许其他进程同时拥有S，即使在非互斥模式下；在进程P以互斥模式获取同步变量S之后，任意其他进程都不能对S执行非互斥式访问，除非在S的拥有者P执行之后。37入口项一致性（3）例：入口项一致性P1：Acq(Lx)W(x)1Acq(Ly)W(y)2Rel(Lx)P2：P3：

Rel(Ly)Acq(Lx)R(x)1

R(y)0

Acq(Ly)R(y)2优点减少开销增加并行性38一致性模型总结（1）无同步操作

一致性说明严格所有的共享访问事件都有绝对时间次序顺序所有进程都以相同的次序看到所有的共享访问事件，不按时间排序因果所有进程都以相同的次序看到所有因果联系事件FIFO所有进程见到的其他进程的写操作次序就是该进程执行写操作的次序，但来自不同进程的写操作不必以相同的顺序看见39一致性模型总结（2）同步操作

一致性说明弱当同步操作完成后,共享数据才保持一致释放当退出临界区后，共享数据才保持一致入口项当进入临界区时,和该临界区有关的共享数据才保持一致407.3以客户为中心的一致性模型分布式数据存储区没有同时更新（无写-写冲突）或容易解决大多数操作为读操作例：Web网页（服务器，代理缓存）最终一致性（eventualconsistency）如果很长时间不发生更新操作，则所有的副本将逐渐变为一致的。41最终一致性（1）移动用户问题42最终一致性（1）客户为中心的一致性（Client-centric）保证对一个客户对数据存储的访问是一致的不考虑不同客户之间的并发访问假设每个数据项x有一个拥有者，只有拥有者可以修改x客户的读写操作在本地副本上进行更新最终将传播给其他副本上。43客户为中心的一致性记号xi[t]:数据项x在局部场地Li上，在时刻t的版本WS(xi[t]):产生xi[t]的所有写操作的集合WS(xi[t1],xj[t2]):WS(xi[t])中的写操作在t2时刻在Lj上执行XjXiXWS(xi)WS(xi,xj)44单调读一致性当一个进程读了数据项x的值后，所有后续的对x的读操作，都将返回相同的值，或者更新的值例：读email旧金山--〉纽约）示例：(a)：符合单调读一致性b):不能保证单调读一致性X1X2X1X245单调写一致性一个进程对数据项x的写操作，必须在该进程对x的所有后续写操作之前完成。例：软件库更新（版本1,...,n)示例：(a)：符合单调写一致性(b):不能保证单调写一致性X1X2X1X246读自己写一致性一个进程对数据项x的写操作结果，总能被该进程对x的后续读操作读到。例1：Web网页更新、浏览例2：数字图书馆密码更新示例：(a)：符合读自己写一致性(b):不能保证自己写一致性X1X2X1X247写跟随读一致性一个进程在对数据项x读操作之后对x的写操作，必须在x已读出的相同值或者更近的值之上进行例：BBS跟帖（读文章A,写文章B）示例：(a)：符合写跟随读一致性(b):不能保证写跟随读一致性X1X2X1X2487.4复制管理副本服务器的放置问题从N个位置中选出K个最优位置基于距离的方法最优：所有客户与所有位置的距离最短距离：延时、带宽等指标49副本服务器的放置策略基于自治系统的方法不考虑客户的位置，假设客户在网络上均匀分布自治系统（autonomoussystem,AS）.所有节点运行相同的路由协议，且由单个组织管理。在含有最大链接数量的网络接口的路由器上放置副本服务器存在问题计算复杂度高〉O(N2)而在瞬时拥塞（flashcrowds）情况下，要求快速布置副本服务器。50副本服务器的放置策略基于单元的方法将m维空间划分成多个相同大小的单元选择K个密度最大的单元放置副本服务器计算复杂度：O(N*max{log(N),K})选择适当的单元大小太大：集群太多，而副本服务器太少；太小：导致副本服务器太多(太小)(太大)正好51内容复制与放置分布式数据仓的设计复制副本的类型：永久型、服务器发起型、客户发起型52永久型副本构成分布式数据仓的初始集合静态的、固定的副本数量较少例1：Web场地的分布类型局域网：轮回策略型服务器Internet：镜像服务器例2：分布式数据库工作站集群（COW）联邦数据库53服务器发起型副本（1）推送式缓存（pushcache）由服务器，动态地设置新的副本作用：当负载发生变化时，如突然增加。减少服务器负担减少客户的通信开销问题？在何时、何地发起复制54服务器发起型副本（2）实现方法访问计数：cnt(S,F)，

S为服务器，F为文件复制阈值：rep(S,F)删除阈值：del(S,F)距离：dist(S,C),C为客户。该信息来自路由数据库55服务器发起型副本（3）复制副本复制副本条件：cnt(S,F)>rep(S,F)删除副本删除副本条件：cnt(S,F)<del(S,F)迁移副本迁移副本条件：del(S,F)<cnt(S,F)<rep(S,F)56服务器发起型副本（4）举例：计数来自不同客户的请求，将文件复制到离客户附近的服务器上。如果cntQ(P,F)>cnt(Q,F)/2，将F从Q迁移到P57客户端发起型副本客户缓存(cache)客户端的本地存储缓存命中率(cachehit)：请求的数据可在缓存中取出的概率提高命中率：缓存可由多个客户共享客户缓存的设置场地与客户相同的机器局域网上多个客户共享的机器上广域网上的代理服务器上客户端服务器代理服务器58内容分发当客户执行一个更新操作后，该操作将传播到所有副本传播状态与传播操作策略传播更新通告传输数据拷贝传播更新操作59更新传播通告无效协议（invalidation）只传输被修改的数据的位置信息数据量少，占用很少网络带宽适用于读/写比非常低的情况数据传输(datashipping)传输被修改的数据数据量多，占用较多网络带宽适用于读/写比非常高的情况60更新传播操作传输(operationshipping)主动复制技术-每个副本有一个进程主动地进行更新占用最少网络带宽要求有较高处理能力61推送式与拉取式协议（1）推送式协议：基于服务器的协议不需要请求，就将更新传播给副本可保持高度的一致性，通常用于永久性副本和服务器副本之间优点：适用于读/写比非常高的情况拉取式协议：基于客户的协议由客户请求服务器发送更新优点：适用于读/写比非常低的情况缺点：当cachemiss时，响应时间长62推送式与拉取式协议（2）推送式协议与拉取式协议的比较项目推式协议拉式协议服务器的状态客户端副本和cache的清单无发送的消息更新(以及稍后读取数据)轮询和更新客户端响应时间立即(或者读取被更新数据时间)读取被更新数据时间63推送式与拉取式协议（3）推拉混合式方法基于租期的更新传播方法租期（lease）：服务器承诺在租期时间内向客户传播更新(推送式)。当租期过期后，客户申请新的租期，或自己取修改数据（拉取式）64推送式与拉取式协议（3）设置租期的准则基于年龄的租期：对年龄大(不经常修改)的数据，租期长。年龄：数据项最后一次修改后的延续时间。假设长时间未被修改的数据，今后也不打可能修改基于刷新频率的租期：对经常被刷新的缓存中(经常使用的)数据，租期长。基于状态空间开销的租期：当服务器负载小时，租期长。65单播方式与多播方式多播一对多通信适用于从服务器到客户的推送式协议单播一对一通信适用于从客户到服务器的抽拉式协议SS667.5一致性协议一致性协议：对一致性模型的实现方法的描述67连续一致性协议数值误差限制的实现记号：服务器Si,；日志Li写操作W(x)weight(W),W的权重值Origin(W)，W的源站点TW[i,j]源自Sj,传输到Si的写操作TW[i,j]=∑{weight(W)|origin(W)=Sj&W∈Li}v(t)为实际值（所有已提交的写操作决定）vi：Si的当前值当不满足v(t)-vi≤δi时，进行更新传播，执行感染协议。SiLiSkLkpush68连续一致性协议陈旧度限制的实现记号：RVCi[]:服务器Si实时向量时钟T(i):服务器Si的本地时间RVCk[j]：已接受的Sj写操作时间戳di:允许的最大陈旧度当不满足T[i]-RVCi[j]≤di时，进行更新传播，拉取Sj的写操作SiLiSkLkpull69连续一致性协议次序误差限制的实现记号：Qi:服务器Si的暂时写操作队列length(Qi):Qi的长度当不满足length(Qi)≤li时，提交本地的暂时写操作提交操作要进行一致性检验。如不通过，需回滚Si的暂时写操作要保证全局次序pushQSiLiSjLj70基于主副本的协议主副本：在数据的所有复制副本中，写操作必须先在主副本上进行。实现了顺序一致性远程写协议：所有写操作由远程服务器执行本地写协议：将主副本读到执行写操作的本地上执行71远程写协议（1）单个主副本服务器72远程写协议（2）带有备份的主副本服务器73本地写协议（1）单个主副本服务器主副本迁移到当前写操作的场地上74本地写协议（2）带有备份的主副本服务器75复制式写协议(1)写操作可在多个副本上执行主动复制协议将各更新操作发给各个副本上的进程问题1：更新顺序问题解决方案：全序多播机制：如Lamport时间戳向量顺序管理器（sequencer）：集中式协调器，负责为每个操作赋予唯一的顺序号，转发给各个副本。76主动复制协议问题2：重复调用问题对象副本的重复调用服务器的重复调用77主动复制协议解决方案：设置了解副本的通信层基于发送者模式：由协调者决定发送调用/响应示例：(a)对复制对象的调用(b)复制对象返回的应答78基于合法数的协议（1）基于多数表决的复制写协议与主副本协议的区别：多个副本同时执行写操作基本算法：设有N各副本设置读合法数NR，写合法数Nw要求：NR+Nw>N；Nw>N/279基于合法数的协议（2）举例：ROWA协议不正确写合法数正确读写合法数80以客户为中心一致性的实现技术基本方法写操作：全局唯一标识符。服务器ID:执行位置序号:执行顺序读集合Rset(c)：与客户c读操作相关的写操作标识符写集合Wset(c)：客户c执行的写操作的标识符S1S2RsetWsetLogLog81实现技术（1）单调读一致性当客户c执行读操作r；c的服务器s检查c的读集合Rset(c)，是否所有写操作已在c的本地更新；如果c的本地没有更新，则请求更新；执行读操作r；将与r有关的写操作标识符加入Rset(c)。SS‘RsetLogLog82实现技术（2）单调写一致性当客户c执行写操作w;它的服务器s检查c的写集合Wset(c)，是否所有写操作已在c的本地执行；如果在c的本地没有执行，则请求执行；执行写操作w;将w的标识符加入Wset(c)。SS‘WsetLogLog83实现技术（3）读自己写一致性当客户c执行读操作r；c的服务器s检查c的写集合Wset(c)，是否所有写操作已在c的本地执行；如果在c的本地没有执行，则请求执行；执行读操作r;SWsetLog84实现技术（4）写跟随读一致性当客户c执行写操作w时，c的服务器s检查c的读集合Rset(c)，是否所有写操作已在c的本地执行；如果在c的本地没有执行，则请求执行；将这些写操作标识符加入Rset(c)。SS‘RsetLogLog85优化方法（1）性能问题Wset(c)和Rset(c)将非常大，造成性能降低基于会话(session)的优化方法减少写集和读集中的元素个数定义session:打开，关闭操作。对应一个应用程序的开始和结束。WS(c)和RS(c)在session打开时建立，关闭时清除。86优化方法（2）基于时间戳向量的优化方法减小写集和读集表示形式的大小对一个写操作WID,赋予时间戳ts(WID)服务器Si维持一个时间戳向量RCVD(i)。RCVD(i)[j]=Si收到的来自Sj的最近写操作的时间戳。对写集或读集A维持一个时间戳向量VT(A)。VT(A)[i]为在Si上的最大时间戳并操作：VT(A+B)[i]=max{VT(A)[i],VT(B)[i]}包含关系：VT(A)≤VT(B)VT(A)[i]≤VT(B)[i]87优化方法（3）例：单调读一致性设客户c在服务器Si上执行读操作r;c的读集为VT(Rset)，Si有RCVD(i)如果RCVD(i)[j]≤VT(Rset)[j]，则在Si进行更新执行后，VT(Rest)[j]=max{VT(Rest)[j],RCVD(i)[j]}887.6分布式共享内存（DSM)*CPU与存储器连接模型单片机理想的共享存储器多处理机89层次结构90UNIX共享内存举例系统调用描述intshmget(key,size,ishmflg);返回具有key的SMidentifiervoid*shmat(shmid,*shmaddr,shmflg);将具有shmid的SM段连到调用进程的数据段上intshmdt(constvoid*shmaddr);将位置在shmaddr上的SM

从调用进程的数据段上拆开intshmctl(shmid,cmd,*buf)由cmd指定的各种SM控制操作cmd91多处理器结构带缓存的多处理器结构总线仲裁机制：集中式和非集中式基于总线的多处理机CPU内存总线(a)总线(b)缓存CPUCPUCPU内存缓存CPU缓存CPU92通写缓冲(write-though)一致性协议事件对本地CPU操作响应对远程CPU响应读失败（miss）从内存中取得数据并存储到缓存中（MC）（无动作）读命中(hit)从本地缓存中取得数据（无动作）写失败（miss）更新内存中的数据并存储到缓存中（MCM

）（无动作）写命中(hit)更新存储器和缓存（C

M

）置为无效93缓存拥有权（ownership）协议Cache分成若干个cache块每个Cache块处于三种状态：Invalid－数据无效Clean－与存储器数据一致Dirty－数据被更新，与存储器数据不一致各CPU监听（snoopy）其它CPU在总线的操作94缓存拥有权（ownership）协议多个CPU可有读拥有权只有一个CPU有写拥有权当一个CPU写一个数据取得对该数据的拥有权其它CPU将该数据的缓存块置为“invalid”在本地缓存块中，写数据，并置为“dirty”适当时候，刷新存储区，或提供给其它CPU95缓存拥有权协议举例W初始状态(W1)A读W(W1)A写W(W2)A再写W(W3)C读写W(W3)96缓存拥有权（ownership）协议特点通过各CPU对总线的监听保持缓存一致性该协议实现在存储器管理单元中整个算法在一个存储器周期中完成召回（callback）协议用软件实现97*7.7举例：基于页面的DSM页块：地址空间管理的基本单位0123456789CPU10259CPU21368CPU347CPU4存储器(a)全局共享地址空间101115121314111012141315(b)CPU10259CPU21368CPU347CPU4111214131510(c)CPU10259CPU21368CPU347CPU411101214131510CPU1写访问P10CPU1读访问P10P1…P15分布在CPU1…CPU4上98实现技术虚拟地址空间(VirtualAddressSpace)内存映射（memorymapping）缺页中断（pagefault）拥有权（ownership）协议-无效协议99存储映射技术两个进程共享同一个文件100存储映射技术s

错误代码addr

内存地址len

长度protcontrolsprotectionflags

标志位fd

文件描述符号offset文件内位移系统调用描述s=brk(addr)改变数据段大小a=mmap(addr,len,prot,flags,fd,offset)映射文件s=unmap(addr,len)取消文件映射101页面的大小错误共享：两个无关的变量位于同一页使用A的代码使用B的代码处理器1处理器2共享页面两个无关的共享变量ABAB102处理机读页举例

PW拥有者1.读PR拥有者1.读PR拥有者1.读页面处理器1处理器2RPR1.读P1.请求复制2.将页标志为R3.读PR拥有者R拥有者W拥有者1.请求降级2.请求复制3.将页标志为R4.读进程P读一个页的6种不同情况103处理机写页举例

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.写入进程P写一个页的6种不同情况104拥有者定位协议

四消息协议：请求-响应-请求-响应三消息协议：请求-转发请求-响应P拥有者页面管理器1.请求2.响应3.请求4.响应P拥有者页面管理器1.请求3.响应2.转发请求(a)(b)105查找拷贝.每个页面的拥有者通过拷贝集得知哪个其它CPU正共享该页面例：4个页面，5个CPU3242134245342341页面CPU1CPU2CPU3CPU4CPU5拷贝集网络4312106DSM应用举例分布并行式对象数据库系统FISHNetworkＯＳ（Ｓｏｌａｒｉｓ，Ｌｉｎｕｘ，ＷｉｎｄｏｗｓＮＴ）Wakashi

PersistentObjects（conformingtoODMG2.0）

ObjectProgrammingLang.（C++binding）InadaWarasa

Vis