【文档说明】[计算机软件及应用]DOS-CH6-Consistency课件.ppt，共(102)页，1.488 MB，由小橙橙上传

转载请保留链接：https://www.ichengzhen.cn/view-2118.html

以下为本文档部分文字说明：

第6章分布式一致性东北大学信息学院于戈2006年4月2006-4-11东北大学软件所于戈第六章分布式一致性2主要内容6.1一致性与复制6.2以数据为中心的一致性模型6.3以客户端为中心的一致性模型6.4分布协议6.5一致性协议6.6*分布式共享内存（DSM)6.7*举例：基于页面的DSM6.8习

题2006-4-11东北大学软件所于戈第六章分布式一致性36.1一致性与复制❑复制的理由–提高可靠性：防止单点失败，数据校验–提高性能：并行性，可伸缩性❑复制的代价–一致性维护–例：Web页的Cache☺Interne

t☺☺☺2006-4-11东北大学软件所于戈第六章分布式一致性4对象复制问题（1）❑单副本对象的同步–例：两个客户并发访问一个分布式远程对象2006-4-11东北大学软件所于戈第六章分布式一致性5对象复制问题（2）❑解决方法(a)由远程对象自己处理对它的并发调用(b)由对象适

配器处理并发调用2006-4-11东北大学软件所于戈第六章分布式一致性6对象复制问题（3）❑多副本对象的同步(a)构造感知复制对象，由对象自己保证一致性(b)由分布式系统负责复制管理2006-4-11东北大学软件所于戈第六章分布式一致性7可伸缩性问题❑将

数据的副本放置在进程附近减少访问时间❑复制策略–设进程P对数据d的访问N次/秒，d的更新M次/秒–当N<<M时，不应复制❑可伸缩问题–紧一致性需对所有副本进行全局同步❑解决策略–松一致性，所有副本不一定保持完全相同，避免立即全局同步2006-4-11东北大学软件所于戈第六章分布式一致性86.2以

数据为中心的一致性模型❑分布式数据仓(datastore)模型–物理上分布的和复制的–例如，分布式共享内存、数据库、文件–操作：进程发出的读操作，写操作2006-4-11东北大学软件所于戈第六章分布式一致性9一致性模型❑数据相干性（coherency）–数据在各个数

据仓中的值保持一致❑一致性模型–进程与数据仓之间的契约(contract)–如果进程遵守约定的规则，数据仓就能工作正常。–如果进程违反了这些规则，数据仓就不再保证操作的正确性2006-4-11东北大学软件所于戈第六章分布式一致性10严格一致性❑规则：对数据项x的读操作返回的值为

最近写入x的值❑特点：绝对全局时间次序❑例：严格一致性：101S1S2时间P1:W(x)1P2:R(x)1时间2006-4-11东北大学软件所于戈第六章分布式一致性11严格一致性❑不可实现性–没有全局时钟–光速限制：T1:W1(x)→S2,T2:R2(x);T2-T1=10-9❑例：非严格一致性1

01S1S20时间P1:W(x)1P2:R(x)0R(x)1时间2006-4-11东北大学软件所于戈第六章分布式一致性12顺序一致性❑规则：所有进程执行的结果，等同于它们的操作按某种顺序在数据仓上执行的结果。每个进程的操作都按照程序规定的顺序。❑例：顺序一致性

P2P1P4P3P1:W(x)1P2:W(x)2P3:R(x)2R(x)1P4:R(x)2R(x)1时间2006-4-11东北大学软件所于戈第六章分布式一致性13顺序一致性❑所有进程看到相同的内存访问操作次序❑等价于数据库的可串行

化（serializability）❑例：非顺序一致性P1:W(x)1P2:W(x)2P3:R(x)2R(x)1P4:R(x)1R(x)2P2P1P4P3时间2006-4-11东北大学软件所于戈第六章分布式一致性14❑例：–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)P1P2P3

x=1;print(y,z);y=1;print(x,z);z=1;print(x,y);2006-4-11东北大学软件所于戈第六章分布式一致性15❑形式化描述❑执行(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时间2006-4-11东北大学软件所于戈第六章分布式一致性16❑合法历程：–保持程序的操作次序–符合数据相干性–例：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顺序一致性2006-4-11东北大学软件所于戈第六章分布式一致性17线性一致性（L

inearizable）❑规则：具有顺序一致性，且如果tsop1(x)<tsop2(y)，则OP1(x)→OP2(y)–每个操作带有全局时钟戳–执行结果是顺序一致性的–每个进程的操作遵照时间戳顺序2006-4

-11东北大学软件所于戈第六章分布式一致性18因果一致性❑因果关系(Causality)：–P1写x,P2读x，则R2(x)与W1(x)具有因果关系。–P1读x,P2写x，则W2(x)与R1(x)具有因果关系。–传递性：例，P1写x,P2读x,然后写y，则W2(y)与W1(x)具

有因果关系。–否则，为并发关系❑定义：–对于具有因果关系的写操作，所有进程看到的执行顺序应相同。–并发写操作在不同主机上被看到的顺序可以不同。2006-4-11东北大学软件所于戈第六章分布式一致性19因果一致性❑例：因果一致性❑例：违反因果一致性P1：

W(x)1W(x)3P2：R(x)1W(x)2P3：R(x)1R(x)3R(x)2P4：R(x)1R(x)2R(x)3P1：W(x)1P2：R(x)1W(x)2P3：R(x)2R(x)1P4：R(x)1R(x)22006-4-11东北大学软件所于戈第六章分布式

一致性20因果一致性❑例：符合因果一致性❑实现技术–操作依赖图–时间戳向量P1：W(x)1P2：W(x)2P3：R(x)2R(x)1P4：R(x)1R(x)22006-4-11东北大学软件所于戈第六章分布式一致性21FIFO一致性❑规则：同一个进程的写操作的执行次序，其它进程看到

的都相同。不同进程的写操作的执行次序，不同进程看到的可以是不同的❑例：符合FIFO一致性，但不符合因果一致性P1：W(x)1P2：R(x)1W(x)2W(x)3P3：R(x)2R(x)1R(x)3P4：R(x)1R(x)2R(x)32006-4-11东北大学软件所于戈第六章分布式一致性22FI

FO一致性❑例：符合FIFO一致性，但不符合顺序一致性x=1;print(y,z);y=1;print(x,z);z=1;print(x,y);Prints:00(a)x=1;y=1;print(x,z);print(y,z)

;z=1;print(x,y);Prints:10(b)y=1;print(x,z);z=1;print(x,y);x=1;print(y,z);Prints:01(c)ProcessP1ProcessP2ProcessP3x=1;p

rint(y,z);y=1;print(x,z);z=1;print(x,y);P1P2P3P1P2P3P2P3P12006-4-11东北大学软件所于戈第六章分布式一致性23FIFO一致性❑也称作内存管道

一致性(PipelinedRAM)–分布式共享内存系统❑实现技术：–写操作标签（进程ID,顺序号）2006-4-11东北大学软件所于戈第六章分布式一致性24处理机一致性❑规则：与FIFO一致性相似–附加条件：–存储相

干性：对于任意存储器地址X,对于写入X的顺序是全局一致的。–写入不同地址,对于不同进程来看,不需要相同顺序2006-4-11东北大学软件所于戈第六章分布式一致性25❑同步变量：与一个数据区相关联–Synchronize(S)–同步所有的数据局部拷贝–导出：导入：❑规则：–对同步变量的访

问必须满足顺序一致性。–在所有先前的写操作完成之前,不能访问同步变量–在所有先前的同步操作完成之前,不能访问（读/写）数据。弱一致性写者读者2006-4-11东北大学软件所于戈第六章分布式一致性26弱一致性❑例：弱一致性❑例：非弱一致性P1：W(x)1W

(x)2SP2：R(x)1R(x)2SP3：R(x)2R(x)1SP1:W(x)1W(x)2SP2:SR(x)12006-4-11东北大学软件所于戈第六章分布式一致性27释放一致性(1)❑被保护数据：–需要保持一致的共享数据❑Acquire(L)操作：进入临界区–导入数据：使被保护数据的局部拷

贝与远程的最新版本一致❑Release(L)操作：退出临界区–导出数据：将被保护数据上的变化传播到其它的局部拷贝上2006-4-11东北大学软件所于戈第六章分布式一致性28释放一致性(2)❑规则–在访问共享数据前

，所有先前的acquire操作都必须完成。–在执行release前，先前的所有读写操作都必须完成。–对同步变量的访问必须满足FIFO一致性❑例：符合释放一致性P1：Acq(L)W(x)1W(x)2Rel(L)P2：Acq(

L)R(x)2Rel(L)P3：R(x)12006-4-11东北大学软件所于戈第六章分布式一致性29释放一致性(3)❑及时释放一致性(EAGERrelease)–当执行了释放操作，执行此操作的处理机将所有修改的数据传给所有那些已经有其缓冲拷贝且

可能需要它的处理机❑滞后释放一致性（LAZYrelease）–在执行释放时，不发送任何数据。–在执行获取操作时，处理机试图从拥有这些变量的机器上取得它们的最新值2006-4-11东北大学软件所于戈第六章分布式一致性30入口项一致性（1）❑同步变量–与某个

共享数据项相关联•不是与数据区中的所有保护型数据关联–拥有者(owner)：最后一个获取（acquire）它的进程。•其他进程必须从当前所有者手中取得拥有权。–非互斥方式（non-exclusive）:可以读，但不能写•多个进程可以非互斥方式同时拥有一个同步变量2006-4-11东北大学软

件所于戈第六章分布式一致性31入口项一致性（2）❑规则：1.在进程P获取同步变量S之前，有关的被保护的共享数据上的全部更新操作都必须完成；2.在进程P以互斥模式访问同步变量S之前，不允许其他进程同时拥

有S，即使在非互斥模式下；3.在进程P以互斥模式获取同步变量S之后，任意其他进程都不能对S执行非互斥式访问，除非在S的拥有者P执行之后。2006-4-11东北大学软件所于戈第六章分布式一致性32入口项一致性（3）❑例：入口项

一致性P1：Acq(Lx)W(x)1Acq(Ly)W(y)2Rel(Lx)P2：P3：Rel(Ly)Acq(Lx)R(x)1R(y)0Acq(Ly)R(y)2❑优点–减少开销–增加并行性2006-4-11东北大学软件所于戈第六章分布式一致性33一致性模型总结（1）无同步操作一致性说明严格所

有的共享访问事件都有绝对时间次序顺序所有进程都以相同的次序看到所有的共享访问事件，不按时间排序因果所有进程都以相同的次序看到所有因果联系事件FIFO所有进程见到的其他进程的写操作次序就是该进程执行写操作的次序，但来自不同进程的写操作不必以相同

的顺序看见2006-4-11东北大学软件所于戈第六章分布式一致性34一致性模型总结（2）❑同步操作一致性说明弱当同步操作完成后,共享数据才保持一致释放当退出临界区后，共享数据才保持一致入口项当进入临界区

时,和该临界区有关的共享数据才保持一致2006-4-11东北大学软件所于戈第六章分布式一致性356.3以客户为中心的一致性模型❑分布式数据存储区–没有同时更新（无写-写冲突）或容易解决–大多数操作为读操作–例：W

eb网页（服务器，代理缓存）❑最终一致性（eventualconsistency）–如果很长时间不发生更新操作，则所有的副本将逐渐变为一致的。2006-4-11东北大学软件所于戈第六章分布式一致性36最终

一致性（1）❑移动用户问题2006-4-11东北大学软件所于戈第六章分布式一致性37最终一致性（1）❑客户为中心的一致性（Client-centric）–保证对一个客户对数据存储的访问是一致的–不考虑

不同客户之间的并发访问❑假设–每个数据项x有一个拥有者，只有拥有者可以修改x–客户的读写操作在本地副本上进行–更新最终将传播给其他副本上。2006-4-11东北大学软件所于戈第六章分布式一致性38客户为中心的一致性❑记号–xi[t]

:数据项x在局部场地Li上在时刻t的版本–WS(xi[t]):得出xi[t]的写操作集–WS(xi[t1],xj[t2]):WS(xi[t])中的写操作在t2时刻在Lj上执行2006-4-11东北大学软件所于戈第六章分布式一致性39单调读一致性❑当一个进程读了数据项x的值后，所有后续的

对x的读操作，都将返回相同的值，或者更新的值–例：读email(旧金山--〉纽约）❑示例：(a)：符合单调读一致性b):不能保证单调读一致性2006-4-11东北大学软件所于戈第六章分布式一致性40单调写一致性❑一个进程对数据项

x的写操作，必须在该进程对x的所有后续写操作之前完成。–例：软件库更新（版本1,...,n)❑示例：(a)：符合单调写一致性(b):不能保证单调写一致性2006-4-11东北大学软件所于戈第六章分布式一致性41读自己写一致性❑一个进程对数据项x的写操作结果，

总能被该进程对x的后续读操作读到。–例1：Web网页更新、浏览–例2：数字图书馆密码更新❑示例：(a)：符合读自己写一致性(b):不能保证自己写一致性2006-4-11东北大学软件所于戈第六章分布式一致性

42写跟随读一致性❑一个进程在对数据项x读操作之后对x的写操作，必须在x已读出的相同值或者更近的值之上进行–例：BBS跟帖（读文章A,写文章B）❑示例：(a)：符合写跟随读一致性(b):不能保证写跟随读一致性2

006-4-11东北大学软件所于戈第六章分布式一致性43实现技术（1）❑基本方法–写操作：全局唯一标识符。•服务器ID:执行位置•序号:执行顺序–读集合Rset(c)：与客户c读操作相关的写操作标识符–写集合Ws

et(c)：客户c执行的写操作的标识符S1S2RsetWsetLogLog2006-4-11东北大学软件所于戈第六章分布式一致性44实现技术（2）❑单调读一致性–当客户c执行读操作r；–c的服务器s检查c的读集合Rset(c)，是否所有写操作已

在c的本地更新；–如果c的本地没有更新，则请求更新；–执行读操作r；–将与r有关的写操作标识符加入Rset(c)。SS‘RsetLogLog2006-4-11东北大学软件所于戈第六章分布式一致性45实现

技术（3）❑单调写一致性–当客户c执行写操作w;–它的服务器s检查c的写集合Wset(c)，是否所有写操作已在c的本地执行；–如果在c的本地没有执行，则请求执行；–执行写操作w;–将w的标识符加入Wset(c)。

SS‘WsetLogLog2006-4-11东北大学软件所于戈第六章分布式一致性46实现技术（4）❑读自己写一致性(写后读)–当客户c执行读操作r；–c的服务器s检查c的写集合Wset(c)，是否所有写操作已在c的本地执行；–如果在c的本地没有执行，则请求执行；–执行读操作

r;SWsetLog2006-4-11东北大学软件所于戈第六章分布式一致性47实现技术（5）❑写跟随读一致性（读后写）–当客户c执行写操作w时，–c的服务器s检查c的读集合Rset(c)，是否所有写操作已在c的本地执行；–如果在

c的本地没有执行，则请求执行；–将这些写操作标识符加入Rset(c)。SS‘RsetLogLog2006-4-11东北大学软件所于戈第六章分布式一致性48优化方法（1）❑性能问题–Wset(c)和Rset(c

)将非常大，造成性能降低❑基于session的优化方法–减少写集和读集中的元素个数–定义session:打开，关闭–WS(c)和RS(c)在session打开时建立，关闭时清除。2006-4-11东北大学软件所于戈第六章分布式一致性49优化方法（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]2006-4-11东北大学软件所于戈第六章分布式一致性50优化方法（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]}2006-4-11东北大学软件所

于戈第六章分布式一致性516.4分布协议❑分布式数据仓的设计–复制副本的类型：永久型、服务器型、客户型2006-4-11东北大学软件所于戈第六章分布式一致性52永久型副本❑构成分布式数据仓的初始集合–静态的、固定的–副本数量较少❑例1：Web场

地的分布类型–局域网：轮回策略型服务器–Internet：镜像服务器❑例2：分布式数据库–工作站集群（COW）–联邦数据库2006-4-11东北大学软件所于戈第六章分布式一致性53服务器发起型副本（1）❑推送式缓存（pushcache）

–动态设置新的副本❑作用：–当负载发生变化时，如突然增加。–减少服务器负担–减少客户的通信开销❑问题–在何时、何地发起复制2006-4-11东北大学软件所于戈第六章分布式一致性54服务器发起型副本（2）❑实现方法–访问计数：cnt(S,

F)，S为服务器，F为文件–复制阈值：rep(S,F)–删除阈值：del(S,F)–距离：dist(S,C),C为客户。该信息来自路由数据库❑复制副本–复制副本条件：cnt(S,F)>rep(S,F)❑删除副本–删除副本条件：cnt(S,F)<del(

S,F)❑迁移副本–迁移副本条件：del(S,F)<cnt(S,F)<rep(S,F)2006-4-11东北大学软件所于戈第六章分布式一致性55服务器发起型副本（3）❑举例：计数来自不同客户的请求，将文件复制到离客户附近的服务器上。–如果cntQ(P,F)〉cnt(Q,F)/2，将F从Q迁移

到P2006-4-11东北大学软件所于戈第六章分布式一致性56客户端发起型副本❑客户缓存(cache)–客户端的本地存储❑缓存命中率(cachehit)：–请求的数据可在缓存中取出的概率–提高命中率：缓存可由多个客户共享❑客户缓存的设置–与客户相同的机器–局域网上多个

客户共享的机器上–广域网上的代理服务器上2006-4-11东北大学软件所于戈第六章分布式一致性57更新传播（1）❑当客户执行一个更新操作后，该操作将传播到所有副本❑传播状态与传播操作1.传播更新通告2.传输数据拷贝3.传播更新操作20

06-4-11东北大学软件所于戈第六章分布式一致性58更新传播（2）❑通告无效协议（invalidation）–传输被修改的数据的位置–占用很少网络带宽–适用于读/写比非常低的情况❑数据传输(datashipping)

–传输被修改的数据–占用较多网络带宽–适用于读/写比非常高的情况2006-4-11东北大学软件所于戈第六章分布式一致性59更新传播（3）❑操作传输(operationshipping)–主动复制技术-每个

副本有一个进程主动地进行更新–占用最少网络带宽–要求有较高处理能力2006-4-11东北大学软件所于戈第六章分布式一致性60推式与拉式协议（1）❑推式协议：基于服务器的协议–不需要请求，就将更新传播给副本–可保持高度的一致性，通常用于永久性副本和服

务器副本之间–优点：适用于读/写比非常高的情况❑拉式协议：基于客户的协议–由客户请求服务器发送更新–优点：适用于读/写比非常低的情况–缺点：当cachemiss时，响应时间长2006-4-11东北大学软件所于戈第六章分布式一致性61推式与拉式协议（2）❑推

式协议与拉式协议的比较项目推式协议拉式协议服务器的状态客户端副本和cache的清单无发送的消息更新(以及稍后读取数据)轮询和更新客户端响应时间立即(或者读取被更新数据时间)读取被更新数据时间2006-4-11东北大学软件所于戈第六章分布式一致性62推式与拉式协议（3）❑推拉

混合式方法–基于租期的更新传播方法–租期（lease）：服务器承诺在租期时间内向客户传播更新。当租期过期后，客户申请新的租期，或自己取修改数据❑租期的准则–基于年龄的租期：经常修改的数据，租期长。–基于刷新频率的租期：经常使用的数据，租期长。–基于状态空间开销的租期：负载小时，租期长

。2006-4-11东北大学软件所于戈第六章分布式一致性63单播方式与多播方式❑多播–一对多通信–适用于从服务器到客户的推式协议❑单播–一对一通信–适用于从客户到服务器的拉式协议SS2006-4-11东北大学软件所于戈第六章分布式一致性64传染协议（1）❑传染算法–单个消息，服务器之间

的信息交换–实现最终一致性❑更新传播模型–基于传染病理论❑服务器状态–感染的（infective）：已被更新，并愿意参加传播–疑似的（susceptible）：还未被更新–隔离的（removed）:不愿意参加传播20

06-4-11东北大学软件所于戈第六章分布式一致性65传染协议（2）❑反熵（anti-entropy）传播模型–熵:系统混乱度的量度❑服务器P随机地选择服务器Q,交换更新–P只将自己的更新推送给Q–P只从Q中拉取新的更新–P和Q互相发送更新❑传播方法–传播谣言(rumorspreading

)、传言（gossiping）–仍为疑似的服务器的比例：s=e-(k+1)(1-s)2006-4-11东北大学软件所于戈第六章分布式一致性66传染协议❑删除数据–旧版本问题❑解决方案–死亡证删除旧版本时间2006-4-11东北大学软件所于戈第六章分布式一致性676.5一致性

协议❑一致性协议：–对一致性模型的实现方法的描述❑基于主副本的协议–主副本：在数据的所有复制副本中，写操作必须先在主副本上进行。–远程写协议：所有写操作由远程服务器执行–本地写协议：将主副本读到执行写操作的本地上执行2006-4-11东北大学软件所于戈第六章分布式一致性68远程写协议（1）❑单个主

副本服务器2006-4-11东北大学软件所于戈第六章分布式一致性69远程写协议（2）❑带有备份的主副本服务器2006-4-11东北大学软件所于戈第六章分布式一致性70本地写协议（1）❑单个主副本服务器2006-4-

11东北大学软件所于戈第六章分布式一致性71本地写协议（2）❑带有备份的主副本服务器2006-4-11东北大学软件所于戈第六章分布式一致性72复制式写协议(1)❑主动复制–将各更新操作发给各个副本上的进程❑问题1：更新顺序问题❑解决方案

：–全序多播机制：如Lamport时间戳向量–顺序管理器（sequencer）：集中式协调器，负责为每个操作赋予唯一的顺序号，转发给各个副本。2006-4-11东北大学软件所于戈第六章分布式一致性73复制式写协议(2)❑问题2：重复调用问题

–对象副本的重复调用–服务器的重复调用2006-4-11东北大学软件所于戈第六章分布式一致性74复制式写协议(3)❑解决方案：设置了解副本通信层–基于发送者模式：由协调者决定发送调用/响应❑示例：(a)对复制对象的调用(b)复制对象返回的应答2006-4

-11东北大学软件所于戈第六章分布式一致性75基于合法数的协议（1）❑基于多数表决的复制写协议–与主副本协议的区别：多个副本同时执行写操作❑基本算法：–设有N个副本–设置读合法数NR，写合法数Nw–要求：NR+Nw>N；Nw>N/22006-4-11东北大学软件所于戈第六章分布式

一致性76基于合法数的协议（2）❑举例：ROWA协议不正确写合法数正确读写合法数2006-4-11东北大学软件所于戈第六章分布式一致性776.6分布式共享内存（DSM)CPU与存储器连接模型❑单片机❑理想的共享存储器多处理机2006-4-11东北大学软件所于戈第六章分布式一

致性78层次结构2006-4-11东北大学软件所于戈第六章分布式一致性79UNIX共享内存举例系统调用描述intshmget(key,size,ishmflg);返回具有key的SMidentifiervoid*shmat(shmid,*shmaddr,shmflg);将具有shmid的S

M段连到调用进程的数据段上intshmdt(constvoid*shmaddr);将位置在shmaddr上的SM从调用进程的数据段上拆开intshmctl(shmid,cmd,*buf)由cmd指定的各种SM控制操作cmd2006-4-11东北大学软件所于戈第六章分布式一致性801.多处理器结构2

.带缓存的多处理器结构✓总线仲裁机制：集中式和非集中式基于总线的多处理机CPU内存总线(a)总线(b)缓存CPUCPUCPU内存缓存CPU缓存CPU2006-4-11东北大学软件所于戈第六章分布式一致性81通写缓冲(write-though)一致性协议事件对本地CPU操作响应对远程CPU响应

读失败（miss）从内存中取得数据并存储到缓存中（M→C）（无动作）读命中(hit)从本地缓存中取得数据（无动作）写失败（miss）更新内存中的数据并存储到缓存中（M→C→M）（无动作）写命中(hit)更新存储器和缓存（C→

M）置为无效2006-4-11东北大学软件所于戈第六章分布式一致性82缓存拥有权（ownership）协议❑Cache分成若干个cache块❑每个Cache块处于三种状态：1.Invalid－数据无效2.Clean－与存储器数据一致3.Di

rty－数据被更新，与存储器数据不一致❑各CPU监听（snoopy）其它CPU在总线的操作2006-4-11东北大学软件所于戈第六章分布式一致性83缓存拥有权（ownership）协议❑多个CPU可有读拥有权❑只有一个CPU

有写拥有权❑当一个CPU写一个数据–取得对该数据的拥有权–其它CPU将该数据的缓存块置为“invalid”–在本地缓存块中，写数据，并置为“dirty”–适当时候，刷新存储区，或提供给其它CPU2006-4-11东北大学软件所于戈第六章分布式一致性84缓存拥有权

协议举例1.W初始状态(W1)2.A读W(W1)3.A写W(W2)4.A再写W(W3)5.C读写W(W3)2006-4-11东北大学软件所于戈第六章分布式一致性85缓存拥有权（ownership）协议❑特点1.通过各CPU对总线的监听保持缓存一致性2.该协议实现在存储器管理单元中3.整个算法

在一个存储器周期中完成➢召回（callback）协议•用软件实现2006-4-11东北大学软件所于戈第六章分布式一致性866.7举例：基于页面的DSM❑页块：地址空间管理的基本单位0123456789C

PU10259CPU21368CPU347CPU4存储器(a)全局共享地址空间101115121314111012141315(b)CPU10259CPU21368CPU347CPU4111214131510(c)CP

U10259CPU21368CPU347CPU411101214131510CPU1写访问P10CPU1读访问P10P1…P15分布在CPU1…CPU4上2006-4-11东北大学软件所于戈第六章分布式一致性87实现技术❑虚拟地址空间(VirtualAddressSpace)❑内存映射（memo

rymapping）❑缺页中断（pagefault）❑拥有权（ownership）协议-无效协议2006-4-11东北大学软件所于戈第六章分布式一致性88存储映射技术❑两个进程共享同一个文件2006-4-11东北大学软件所

于戈第六章分布式一致性89存储映射技术❑s错误代码addr内存地址❑len长度protcontrolsprotection❑flags标志位❑fd文件描述符号offset文件内位移系统调用描述s=brk(addr)改变数据段大小a=mmap(addr,len,prot,f

lags,fd,offset)映射文件s=unmap(addr,len)取消文件映射2006-4-11东北大学软件所于戈第六章分布式一致性90页面的大小❑错误共享：两个无关的变量位于同一页使用A的代码使用B的代码处理器1处理器2共享页面两个无关的共享变量AB

AB2006-4-11东北大学软件所于戈第六章分布式一致性91处理机读页举例PW拥有者1.读PR拥有者1.读PR拥有者1.读页面处理器1处理器2RPR1.读P1.请求复制2.将页标志为R3.读PR拥有者R拥有者W拥有者1.请求降级2.请求复制3.将页标志为

R4.读❑进程P读一个页的6种不同情况2006-4-11东北大学软件所于戈第六章分布式一致性92处理机写页举例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种不同情况2006-4-11东北大学软件所于戈第六

章分布式一致性93拥有者定位协议❑四消息协议：请求-响应-请求-响应❑三消息协议：请求-转发请求-响应P拥有者页面管理器3.请求4.响应P拥有者页面管理器3.响应(a)(b)2006-4-11东北大学软件所于戈第六章分布式一致性94查找拷贝.❑

每个页面的拥有者通过拷贝集得知哪个其它CPU正共享该页面❑例：4个页面，5个CPU3242134245342341页面CPU1CPU2CPU3CPU4CPU5拷贝集网络43122006-4-11东北大学软件所于戈第

六章分布式一致性95DSM应用举例❑分布并行式对象数据库系统FISHNetworkＯＳ（Ｓｏｌａｒｉｓ，Ｌｉｎｕｘ，ＷｉｎｄｏｗｓＮＴ）Wakashi•PersistentObjects（conformingtoODMG2.0）•ObjectProgrammingLang.（C++bindi

ng）InadaWarasa•VisualInterface•ObjectQueryLanguage（OQL）•PersistentDistributedSharedMemory)•TransactionControl(Lock,Reco

very)2006-4-11东北大学软件所于戈第六章分布式一致性96分布透明性❑Fragment1copyFragment2copyQuery1Query2Database2006-4-11东北大学软件所于戈第六章分布式一致性97存储器映射技术clien

t1databaselocaldiskcachesite1sitenheapserver1serveriservernheapheapDSVMmappingLocaldiskcachememorymappingNetworkDSVMmappingclienticlientn

diskmappinglocaldiskcachinglocaldiskcachingsitei2006-4-11东北大学软件所于戈第六章分布式一致性98进程结构RPCSocketserverprocessserverthreadServe

rclientprocessclientthreadcleintserverprocessserverthreadlocktableServerclientprocessclientthreadclientlocktableSite1Site

2RPCSocket2006-4-11东北大学软件所于戈第六章分布式一致性99基于pagefault的封锁Transaction_Begin();。。。O1->amount=O2->amount+500;。。。Tran

scation_End();ServerReceiverequesting;checklockingtable;Grantlocking;sendresponse;PagefaultexceptionClientgetadd

r.,conflicttypegetpagenumbersendlockingrequestsetattr.(read/write)Lockingtable;memoryobjecttabeleOidaddrsizepidtypeuser(3)(1)(2)(7

)(4)(6)(5)2006-4-11东北大学软件所于戈第六章分布式一致性100小结❑以数据为中心的一致性模型❑以客户为中心的一致性模型❑复制的一致性维护策略❑一致性协议2006-4-11东北大学软件所于戈第六章分布式一致性1016.7习题1.在内存一致性模型的讨论中，经常提到软件和内存的约定

。为什么需要这样的约定，举例说明？2.下图为顺序一致性内存的一个例子。对P2做少量改动，使它破坏顺序一致性。3.释放一致性的大多数实现方法是在release时同步共享变量，而不是在acquire时同步,但为什么还需要acquire操作

？P1：W(x)1P2：R(x)0R(x)12006-4-11东北大学软件所于戈第六章分布式一致性102习题(续)4.在如下并行执行的进程P1和P2，列出顺序一致性所允许的6种语句交叉执行情况。5.假设两个变量a和b,恰好位于基于分页的DSM系统的同一页

上。然而，它们都不是共享变量。是否会发生错误共享？a=1;b=1;If(b==0)kill(P2)if(a==0)kill(P1)(a)P1（b)P2