[计算机软件及应用]DOS-CH6-Consistency课件.ppt

1、第第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 一致性与复制q复制的理由 提高可靠性：防止单点失败，数据校验 提高性能：并行性，可伸缩性q复制的代价 一致性维护 例：Web页的CacheInternet2006-4-11东北大学软件所 于戈第六章 分布

2、式一致性4对象复制问题（1）q单副本对象的同步 例：两个客户并发访问一个分布式远程对象2006-4-11东北大学软件所 于戈第六章 分布式一致性5对象复制问题（2）q解决方法(a)由远程对象自己处理对它的并发调用(b)由对象适配器处理并发调用2006-4-11东北大学软件所 于戈第六章 分布式一致性6对象复制问题（3）q多副本对象的同步(a)构造感知复制对象，由对象自己保证一致性(b)由分布式系统负责复制管理2006-4-11东北大学软件所 于戈第六章 分布式一致性7可伸缩性问题q将数据的副本放置在进程附近减少访问时间q复制策略 设进程P对数据d的访问N次/秒，d的更新M次/秒 当NM时，不应

3、复制q可伸缩问题 紧一致性需对所有副本进行全局同步q解决策略 松一致性，所有副本不一定保持完全相同，避免立即全局同步2006-4-11东北大学软件所 于戈第六章 分布式一致性86.2 以数据为中心的一致性模型q分布式数据仓(data store)模型 物理上分布的和复制的 例如，分布式共享内存、数据库、文件 操作：进程发出的读操作，写操作2006-4-11东北大学软件所 于戈第六章 分布式一致性9一致性模型q数据相干性（coherency）数据在各个数据仓中的值保持一致q一致性模型进程与数据仓之间的契约(contract)如果进程遵守约定的规则，数据仓就能工作正常。如果进程违反了这些规则，数据

4、仓就不再保证操作的正确性 2006-4-11东北大学软件所 于戈第六章 分布式一致性10严格一致性q 规则：对数据项x的读操作返回的值为最近写入x的值q 特点：绝对全局时间次序q 例：严格一致性：101S1S2时间时间P1:W(x)1P2:R(x)1时间时间2006-4-11东北大学软件所 于戈第六章 分布式一致性11严格一致性q不可实现性没有全局时钟光速限制：T1:W1(x)S2,T2:R2(x);T2-T1=10-9q例：非严格一致性101S1S20时间时间P1:W(x)1P2:R(x)0 R(x)1时间时间2006-4-11东北大学软件所 于戈第六章 分布式一致性12顺序一致性q规则：所

5、有进程执行的结果，等同于它们的操作按某种顺序在数据仓上执行的结果。每个进程的操作都按照程序规定的顺序。q例：顺序一致性P2P1P4P3P1:W(x)1P2:W(x)2 P3:R(x)2 R(x)1 P4:R(x)2 R(x)1 时间时间2006-4-11东北大学软件所 于戈第六章 分布式一致性13顺序一致性q所有进程看到相同的内存访问操作次序q等价于数据库的可串行化（serializability）q例：非顺序一致性P1:W(x)1P2:W(x)2 P3:R(x)2 R(x)1 P4:R(x)1 R(x)2 P2P1P4P3时间时间2006-4-11东北大学软件所 于戈第六章 分布式一致性14

6、q例：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=

7、1;print(x,z);z=1;print(x,y);2006-4-11东北大学软件所 于戈第六章 分布式一致性15q形式化描述q执行(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)1q历程(History):合并E1,E2,.,En后的序列就像在一个集中式数据仓上执行顺序一致性P1:W(x)1P2:W(x)2 P3:R(x)2 R(x)1 P4:R(x)2 R(x)1 时间时间2006-4-11东北大学软件所 于戈第六章 分布式一致性16q合法历程：保持程序的操

8、作次序符合数据相干性 例：H=W2(x)2,R3(x)2,R4(x)2,W1(x)1,R3(x)1,R4(x)1q非法历程 例：H=W2(x)2,R3(x)2,R4(x)1,R4(x)2,W1(x)1,R3(x)1q性能问题：设读操作时间为r,写操作时间为w,包传输时间为t 则r+wt顺序一致性2006-4-11东北大学软件所 于戈第六章 分布式一致性17线性一致性（Linearizable）q规则：具有顺序一致性，且如果tsop1(x)rep(S,F)q删除副本 删除副本条件：cnt(S,F)del(S,F)q迁移副本 迁移副本条件：del(S,F)cnt(S,F)N；Nw N/22006-

9、4-11东北大学软件所 于戈第六章 分布式一致性76基于合法数的协议（2）q举例：ROWA协议不正确写合法数正确读写合法数2006-4-11东北大学软件所 于戈第六章 分布式一致性776.6分布式共享内存（DSM)CPU与存储器连接模型q 单片机q 理想的共享存储器多处理机2006-4-11东北大学软件所 于戈第六章 分布式一致性78层次结构2006-4-11东北大学软件所 于戈第六章 分布式一致性79UNIX共享内存举例系统调用系统调用描述描述int shmget(key,size,ishmflg);返回具有返回具有key的的 SM identifiervoid*shmat(shmid,*s

10、hmaddr,shmflg);将将 具有具有shmid 的的SM段段连到调用进程的数据段连到调用进程的数据段上上int shmdt(const void*shmaddr);将位置在将位置在shmaddr 上上的的SM 从调用进程的数从调用进程的数据段上拆开据段上拆开int shmctl(shmid,cmd,*buf)由由cmd指定的各种指定的各种SM控制操作控制操作 cmd 2006-4-11东北大学软件所 于戈第六章 分布式一致性801.多处理器结构2.带缓存的多处理器结构总线仲裁机制：集中式和非集中式基于总线的多处理机CPU内存总线(a)总线(b)缓存CPUCPUCPU内存缓存CPU缓存C

11、PU2006-4-11东北大学软件所 于戈第六章 分布式一致性81通写缓冲(write-though)一致性协议事件对本地CPU操作响应对远程CPU响应读失败（miss）从内存中取得数据并存储到缓存中（MC）（无动作）读命中(hit)从本地缓存中取得数据（无动作）写失败（miss）更新内存中的数据并存储到缓存中（MC M）（无动作）写命中(hit)更新存储器和缓存（C M）置为无效2006-4-11东北大学软件所 于戈第六章 分布式一致性82缓存拥有权（ownership）协议qCache分成若干个cache块q每个Cache块处于三种状态：1.Invalid数据无效2.Clean与存储器数据

12、一致3.Dirty数据被更新，与存储器数据不一致q各CPU监听（snoopy）其它CPU在总线的操作2006-4-11东北大学软件所 于戈第六章 分布式一致性83缓存拥有权（ownership）协议q多个CPU可有读拥有权q只有一个CPU有写拥有权q当一个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

13、)2006-4-11东北大学软件所 于戈第六章 分布式一致性85缓存拥有权（ownership）协议q特点1.通过各CPU对总线的监听保持缓存一致性2.该协议实现在存储器管理单元中3.整个算法在一个存储器周期中完成 召回（callback）协议用软件实现2006-4-11东北大学软件所 于戈第六章 分布式一致性866.7 举例：基于页面的DSMq页块：地址空间管理的基本单位0 1 2 3 4 5 6 7 8 9CPU 10259CPU 21368CPU 347CPU 4存储器(a)全局共享地址空间10 111512 1314111012 1413 15(b)CPU 10259CPU 21368

14、CPU 347CPU 41112 1413 1510(c)CPU 10259CPU 21368CPU 347CPU 4111012 1413 1510CPU1写访问P10CPU1读访问P10P1P15分布在CPU1 CPU4上2006-4-11东北大学软件所 于戈第六章 分布式一致性87实现技术q虚拟地址空间(Virtual Address Space)q内存映射（memory mapping）q缺页中断（pagefault）q拥有权（ownership）协议-无效协议2006-4-11东北大学软件所 于戈第六章 分布式一致性88存储映射技术q两个进程共享同一个文件2006-4-11东北大学软

15、件所 于戈第六章 分布式一致性89存储映射技术q s 错误代码 addr 内存地址q len 长度 prot controls protectionq flags 标志位q fd 文件描述符号 offset文件内位移文件内位移系统调用描述s=brk(addr)改变数据段大小a=mmap(addr,len,prot,flags,fd,offset)映射文件s=unmap(addr,len)取消文件映射2006-4-11东北大学软件所 于戈第六章 分布式一致性90页面的大小q错误共享：两个无关的变量位于同一页使用A的代码使用B的代码处理器 1处理器 2共享页面两个无关的共享变量ABAB2006-4

16、-11东北大学软件所 于戈第六章 分布式一致性91处理机读页举例 PW拥有者1.读PR拥有者1.读PR拥有者1.读页面处理器1处理器2RPR1.读P1.请求复制2.将页标志为R3.读PR拥有者R拥有者W拥有者1.请求降级2.请求复制3.将页标志为R4.读q进程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拥有

17、者W拥有者1.请求置无效2.请求拥有者3.请求页面4.将页标志为W5.写入q进程P写一个页的6种不同情况2006-4-11东北大学软件所 于戈第六章 分布式一致性93拥有者定位协议 q四消息协议：请求-响应-请求-响应q三消息协议：请求-转发请求-响应P拥有者页面管理器1.请求2.响应3.请求4.响应P拥有者页面管理器1.请求3.响应2.转发请求(a)(b)2006-4-11东北大学软件所 于戈第六章 分布式一致性94查找拷贝.q 每个页面的拥有者通过拷贝集得知哪个其它CPU正共享该页面q 例：4个页面，5个CPU3242134245342341页面CPU 1CPU 2CPU 3CPU 4CP

18、U 5拷贝集网络43122006-4-11东北大学软件所 于戈第六章 分布式一致性95DSM应用举例q分布并行式对象数据库系统FISHNetwork（，）Wakashi Persistent Objects（conforming to ODMG2.0）Object Programming Lang.（C+binding）InadaWarasa Visual Interface Object Query Language（OQL）Persistent Distributed Shared Memory)Transaction Control(Lock,Recovery)2006-4-11东北大学

19、软件所 于戈第六章 分布式一致性96分布透明性q Fragment 1copyFragment 2copyQuery 1Query 2Database2006-4-11东北大学软件所 于戈第六章 分布式一致性97存储器映射技术client1databaselocal disk cachesite1site nheapserver 1server iserver nheapheapDSVMmappingLocal disk cachememorymappingNetworkDSVMmappingclient iclient ndisk mappinglocal disk cachinglocal

20、 disk cachingsite i2006-4-11东北大学软件所 于戈第六章 分布式一致性98进程结构RPC Socket serverprocessserverthreadServerclient processclient threadcleintserverprocessserverthreadlocktableServerclient processclient threadclientlock tableSite 1Site 2RPCSocket2006-4-11东北大学软件所 于戈第六章 分布式一致性99基于pagefault的封锁 Transaction_Begin();。

21、O1-amount=O2-amount+500;。Transcation_End();ServerReceive requesting;check locking table;Grant locking;send response;PagefaultexceptionClientget addr.,conflict typeget page numbersend locking requestset attr.(read/write)Locking table;memory object tabeleOid addr sizepid type user (3)(1)(2)(7)(4)(6)(5

22、)2006-4-11东北大学软件所 于戈第六章 分布式一致性100小结q以数据为中心的一致性模型q以客户为中心的一致性模型q复制的一致性维护策略q一致性协议2006-4-11东北大学软件所 于戈第六章 分布式一致性1016.7 习习 题题1.在内存一致性模型的讨论中，经常提到软件和内存的约定。为什么需要这样的约定，举例说明？2.下图为顺序一致性内存的一个例子。对P2做少量改动，使它破坏顺序一致性。3.释放一致性的大多数实现方法是在release时同步共享变量，而不是在acquire时同步,但为什么还需要acquire 操作？P1：W(x)1W(x)1P2：R(x)0 R(x)1R(x)0 R(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