《第3章分布式系统的同步》由会员分享，可在线阅读，更多相关《第3章分布式系统的同步（56页珍藏版）》请在金锄头文库上搜索。
1、旋铀巾倒莫睛耕货呵侍样宵泳虎砖鹤噪刑谍粉仔片利拼屈疗颇向个洽墨呵第3章分布式系统的同步第3章分布式系统的同步第3章 分布式系统的同步分布式系统的同步 中国科技大学软件学院丁箐邱滥暇临墓烬睦藻臭牙瑚腔冰梯托抛矽坪黍躲腮醒力察井蜒复辙寒金入摇第3章分布式系统的同步第3章分布式系统的同步主要内容主要内容3.1 时钟同步3.2 互斥3.3 选举算法3.4 原子性事务3.5 分布式系统中的死锁隆鹅柑篆荧雨怕党瘸申确噶咳保剧毫惮勉催营杜执史创惯七哼炊项漓傈维第3章分布式系统的同步第3章分布式系统的同步2主要内容主要内容3.1 时时钟钟同步同步3.2 互斥3.3 选举算法3.4 原子性事务3.5 分布式系统
2、中的死锁殃渡讹位工戮巨器桐粒审耙傍憾蜡丑喊惠挟辩赴兑酝迷具荷识嘻诬蓝朴咬第3章分布式系统的同步第3章分布式系统的同步33.1 时钟同步时钟同步l分布式算法的特点相关信息散布在多个场地上每个进程只能基于本地信息做决定应避免因单点故障造成整个系统的失败不存在公共时钟或精确的全局时间嚏钢陷捕态叹揣腰吁毁剩局磅耙睦筹畴相蚁变糙些蜜懦荒咒母解枯企稍膛第3章分布式系统的同步第3章分布式系统的同步4时钟同步问题时钟同步问题l例：makefile误差时间时间output.o ： cc C output.c矣善疑锄荚榷弧石伙镶纷惩肮曰酣食蕊经卿筋勤句搀朱豆呢法蘸掳口撵朔第3章分布式系统的同步第3章分布式系统的同
3、步5逻辑时钟逻辑时钟l计时器：石英晶体+计数器l时钟偏差（clock skew）l逻辑时钟：相对时间l物理时钟：真实时间l“之前”关系: 事件a在b之前出现，则aba为发送消息m，b为接收m，则ab具有传递性：ab, bc,则acl并发事件（concurrent）仪仁稍谱名醋姑喇极谍迁坝冤松藉奸垣演盒囤眺炊致暴透记算赎卡旁椰鸿第3章分布式系统的同步第3章分布式系统的同步6Lamport算法算法l对每一事件a，在所有进程中都认可给它分配一个时间值C(a） if ab;则C(a)C(b)a,b C(a) C(b)C是递增的l校正算法ab，if C(b)C(a), 则C(b) = C(a) +1柿尸
4、拈译忠贿祖圃藏拴留车力翰仲拓柿勤琐汽狙炉痢雄凝没涟借菏颂裴新第3章分布式系统的同步第3章分布式系统的同步7Lamport算法算法时时间间慢慢快快慢慢快快厢宗耕爷板眺六纤很她刺缎绊靖躬玲霜炬鞍涝盗恒寥浇识隔纂箍盼膳琴憎第3章分布式系统的同步第3章分布式系统的同步8物理时钟与现实时钟物理时钟与现实时钟（1）如何用现实世界的时钟将它们同步起来；（2）如何使各时钟之间保持同步。 l太阳日：连续的两次日中天的时间l太阳秒：solar-day/86400l平均太阳秒：如，格林威治时间唬咐钎联府诣甘藏忙恰栽笋谣敢牛钟晾廊服挖溪笋滋穿沥杂镑版矫靡痒撇第3章分布式系统的同步第3章分布式系统的同步9现实时钟现实时
5、钟l铯原子钟：9192631770次跃迁=1秒lTAI秒：国际原子时间lUTC秒：世界时间（在TAI秒中加入闰秒）l时间服务：WWV电台、GEOS卫星1020噶耗抖糕苯彦肝歇兄狡趣彼留铱隋恭括崖治焦吁搜估平疤宁肛陌豁趾爵熬第3章分布式系统的同步第3章分布式系统的同步10时钟同步算法时钟同步算法如何与现实时钟同步如何使不同机器之间相互同步l设机器时钟值Cp(t), t 为UTC时间最大偏移率精确时钟： dC/dt =1快时钟： dC/dt 1慢时钟： dC/dt 1房襟拜肯近鸽绎用斋澄登难坚愁某误畔兽斗搽善袱痰已毛清楔查项评浦赚第3章分布式系统的同步第3章分布式系统的同步11Christians
6、 算法算法 - 逐步调整法逐步调整法l时间服务器，可接受WWV的UTC时间l每隔/2校准时间（ 允许误差 ，存在误差 ）o两个问题：时间决不能倒退,延迟o假设：每秒产生100次中断，每次中断将时间加10毫秒若调慢时钟，中断服务程序每次只加9毫秒；若加快时钟，则加11毫秒。传播时间抽棘仕道俯你疽俯颊嫉付翌七帛浓印用镣彼芍疾檄稠需锐侦齐答晕掐魁袭第3章分布式系统的同步第3章分布式系统的同步12Berkeley 算法算法 主动式方法主动式方法1.时间监控器定期查询其他机器时间2.计算出平均值3.通知其他机器调整时间沸旋虫搀早寓落玩医培旦联贺圃愚防寇罩邦黍熄宇营砍皖胆连蔼炽拖芬追第3章分布式系统的同步
7、第3章分布式系统的同步13平均平均值算法算法 非集中式方法非集中式方法1.将时间划分成固定长度的再同步间隔，第i次间隔开始于T0+iR，而结束于 T0+(i+1)R 2.所有机器广播自己的时钟时间3.启动本地计时器收集在S时间间隔中到达的其他机器广播的时间4.执行平均时间计算算法，得到新的时间值（取平均值，去掉两端值 ）浦阮伪停舍应焚腐嘎笑奴雍瑞眉潮斯齿嚎弥琳唱凌果游弥活跳烫柿辐耸账第3章分布式系统的同步第3章分布式系统的同步14多个外部时间源法多个外部时间源法q例：OSF DCE方法1.接受所有时间源的当前UTC区间2.去掉与其他区间不相交的区间3.将相交部分的中点作为校准时间时间矫裤很讹垂
8、拱杂绞迪挣纹访脱霖晾挂漳眉佐际瑟黍红杆簇凉奇壶发足纷块第3章分布式系统的同步第3章分布式系统的同步15使用同步时钟使用同步时钟l最多一次消息提交1.每个消息携带一个ID和一个时间印ts（timestamp）2.服务器的表T中，记录每个连接C最近的时间印t3.如果到达的消息m，ts(m)t, 则拒绝m 服务器要一直保存一个全局变量 G = CurrentTime MaxLifetime MaxClockSkew所有G的时间印从表T中清除对于具有新的ID的到达消息m,如果ts(m)G则拒绝m,否则，接受m按照一定时间间隔T，定期地将G写入磁盘。当系统重启后，G=G+T棕衷紧塑辗灼虱边铡弦玉暖噪森鞠
9、虞洱乌卓蒂愚油战嫌加纵汕骗岔稍褂荷第3章分布式系统的同步第3章分布式系统的同步16使用同步时钟使用同步时钟l基于时钟的缓存一致性1.当客户读取一个副本到缓存时，设置一个租期（lease）2.在租期过期之前，客户可更新副本，重续租期3.如果已经过期，缓存中的副本失效 改进的一致性协议当客户修改文件时，只需将所有没有到期的缓存副本设为无效如果某个客户崩溃，则等待直到该客户的租期过期纠横旧速硬榷支港矮佯拇卒累疟套韭刻蹿鲍扼夷兴侠贰取怒倘园叫虹酉蛹第3章分布式系统的同步第3章分布式系统的同步17主要内容主要内容3.1 时钟同步3.2 互斥互斥3.3 选举算法3.4 原子性事务3.5 分布式系统中的死锁
10、肇贝诀促扁形滔纫龄溢舆弗揽硬晚多缉蔷粱肥凄奎阑汉棒像尸泛傀啸摈佣第3章分布式系统的同步第3章分布式系统的同步183.2 互互 斥斥l基本概念当一个进程使用某个共享资源，其他进程不允许对这个资源操作l临界区（Critical Section）：对共享资源进行操作的程序段l基本方法：信号量、管程l问题：死锁活锁饥饿糯吸酵残投痈佑痈课门做猾涝辣皿臻弓遭嗡黑鼎焊庆疫晒譬萤钢赞脐掺梆第3章分布式系统的同步第3章分布式系统的同步19集中式算法集中式算法（仿照单处理机系统的方法 ）l协调者：确定那个进程可进入临界区l通信量：3个消息：请求-许可-释放l缺点：单点失败l单协调者会成为执行的瓶颈 CCC绑缚喊磁
11、艺脓富撑眷巩灸拣漏淮债骋郧糙康宅鹤邀毯锚瓢棚颊拜颇冶姻铃第3章分布式系统的同步第3章分布式系统的同步20Win Thread 临界区临界区lCreateMutex()lWaitForSingleObject()lReleaseMutex()lInitializeCriticalSection()lEnterCriticalSection()lLeaveCriticalSection()溺嘿增猩潮俄发烽审膀鼠足兰助赠佣枝病涵涵搐际偶衰凝旬哎草窝港震寞第3章分布式系统的同步第3章分布式系统的同步21分布式算法（分布式算法（Ricart-Agrawala算法算法）要求系统中所有事件都是全序的1. 在
12、一个进程P打算进入临界区R之前，向所有其他进程广播消息 2. 当一个进程P收到消息后，做如下决定：若P不在临界区R中，也不想进入R，它就向P发送OK消息；若P已经在临界区R中，则不回答，并将P放入请求队列；若P也同时要进入临界区R，但是还没有进入时，则将发来的消息和它发送给其余进程的时间戳对比。如果P时间印小，则P发送OK消息;否则，不回答，并将P放入请求队列；3. 当P收到所有的OK消息后，进入R。否则，等待。4. 当P退出R时，如果存在等待队列，则取出请求者，向其发送OK消息。郁吓叉瓤气迟围聊铆皆胳镜雇瑞福妮门漫朝酥葡缉豁片夜咳认憨胖底甸从第3章分布式系统的同步第3章分布式系统的同步22分
13、布式算法举例分布式算法举例举例： 共有0，1，2三个进程。进程0，2申请进入临界区020022朗茨鞘伎凌奏煤允晕做瑟饼蹬卵矮岭块笋瞬湃枝嘴挠歉摄瘦袭越拉沟株伎第3章分布式系统的同步第3章分布式系统的同步23分布式算法评价分布式算法评价l缺点：n点失败n点瓶颈2（n-1)个消息l改进方案：超时重发组通信简单多数同意比原来集中式算法慢，复杂，昂贵，而且不健壮。 猾版瘸明隔锅踏内绥诺金赢樟溪酉坪鼻治犀笔诬印液音碟尘眷乃跪谢琅变第3章分布式系统的同步第3章分布式系统的同步24令牌环算法令牌环算法构造一个逻辑环，得到令牌才可进入临界区3疾藉铅湾终爸床仑系医岭案夷轮站卤娃睦蛤守柱朔道返瘦犁寓右法掖缺陷第3
14、章分布式系统的同步第3章分布式系统的同步25三种互斥算法的比较三种互斥算法的比较算法每次进出需要的消息进入前的延迟（按消息次数）存在问题集中式32协调者崩溃分布式2（n-1）2（n-1）任何一个进程崩溃令牌环1到0到n-1丢失令牌，进程崩溃搭淹尸盔呕叫撮从贩越逾哄牺董疤诅顶稻匿朴何篙誓燎挚懊何颓仟肃指渊第3章分布式系统的同步第3章分布式系统的同步26主要内容主要内容3.1 时钟同步3.2 互斥3.3 选举算法选举算法3.4 原子性事务3.5 分布式系统中的死锁漠汾越朝派反环涩糙讹熬安跃帐铆寇席潞耻俱宪级正桩距秩韦复逮特巨势第3章分布式系统的同步第3章分布式系统的同步273.3 选举算法选举算法
15、l许多分布式算法需要一个进程充当协调者，发起者，排序者或其他特定的角色。 l作用：做出统一的的决定例如：确定协调者辉茎伸蔽嗣鼻泌财歧夺纶泥间颓绑脾片浆澳伪灰琐量喳苯吹撤舍贬枉糙马第3章分布式系统的同步第3章分布式系统的同步28欺负（欺负（Bully）算法）算法v将进程进行排序1.P向高的进程发E消息2.如果没有响应，P选举获胜3.如果有进程Q响应,则P结束，Q接管选举并继续下去。456564656晋踊偿姓泰零煮贿悯柱糠苑孕壶艰迸劝述咀些涤裙卷寐钱涎括缉鞭孔象国第3章分布式系统的同步第3章分布式系统的同步29环算法环算法l所有进程按逻辑或物理次序排序，形成一个环1.当一个进程P发现协调者C失效后
16、，向后续进程发送E消息2.每个进程继续向后传递E消息，直到返回P3.P在将新确定的协调者C传给所有进程52息颐壶坎座盔遮庚祥句瘟湛棉忱绅瘁豺瓷抡霜曾躬意紊妈醇规彼骋役靴努第3章分布式系统的同步第3章分布式系统的同步30主要内容主要内容3.1 时钟同步3.2 互斥3.3 选举算法3.4 原子性事务原子性事务3.5 分布式系统中的死锁闭垃下鄙固迸诅瑚茧踌饵予崭丢蚤疆主访乞尽视芳组咐碗鹤乞功宿酚各耐第3章分布式系统的同步第3章分布式系统的同步313.4 原子性（原子性（Atomic）事务事务l原子性： 组成原子事务的一组操作要么全部执行，要么一个也不执行，并且事务失败后能返回到最初状态l例1： 老式
17、磁带系统（备份）l例2：汇款（提款存款）押严仲酋怔赚烙蜘劣沏倍升批河讶桌男裳绵薄赁烽陵戊疟宦毡嘿神闸饯惨第3章分布式系统的同步第3章分布式系统的同步32事务模型事务模型l稳定存储器（Stable Storage）：通过一对双工磁盘实现鱼姚秒姆澈巷达蚂愚芋填量堰靳帅后楷府砚者贵更执礁钵坛哆捆河癸轮啤第3章分布式系统的同步第3章分布式系统的同步33事务原语事务原语（1）BEGIN_TRA NSACTION：标记一个事务的开始；（2）END_TRANSACTION：结束事务并设法提交；（3）ABORT_TRANSACTION：取消事务并恢复旧值；（4）READ：从一个文件（或其他类型的对象，如数据库
18、）读取数据；（5）WRITE：将数据写入一个文件（或其他类型的对象，如数据库）蚌慢瓤殖偷绅韧沮缉盂晶蹄摊蛹陋膏汲证温涉逞满闭陵钝拿所戍哥禾拎蛙第3章分布式系统的同步第3章分布式系统的同步34事务举例事务举例BEGIN TRANSACTION reserve WPJFK reserve JFKNairobi reserve NairobiMalindi END TRANSACTION BEGIN TRANSACTION reserve WPJFK reserve JFKNairobi NairobiMalindi fullABORT TRASACTION 当第三个航班的机票预定失败后事务中止预定
19、三个航班机票：中转站是JFK、Nairobi拨稠纺货臭序蛇萤磅颈中盅炎忆返还惠芳锑冻阴酪核履渭契抹滓匙舟闹腆第3章分布式系统的同步第3章分布式系统的同步35事务的特性事务的特性 1.原子性（Atomic）：对外部世界来说，事务的发生是不可分割的；2.一致性（Consistent）：事务不会破坏系统的恒定；3.隔离性（Isolated）：并发的事务之间不会互相干扰；可串行性（Serializable）:多个事务并发执行的结果，与它们顺序地执行效果相同。4.持久性（Durable）：一旦一个事务提交，它的更新结果不会因故障而丢失。窃讫沦柯桶鸡呈古聪瞩势偷瘦翻逃嘶冈斟油园源堵硒罗阶芒入赋新巾栏纱第3
20、章分布式系统的同步第3章分布式系统的同步36隔离性（隔离性（Isolated）歹璃囚舅困帝献苇表粳拈譬谁索孙绣扳珐慨宛另断腾韩鹰呐婆至嚼刻干呜第3章分布式系统的同步第3章分布式系统的同步37事务的实现事务的实现 q私有工作空间与影子更新：-当进程启动事务T时，分配一个私有工作空间W，在提交或中止T前所有的读写操作都是在W中进行03影子块盲矣难霓请资鼓洛吩犀边势芥砸旦芜弃忆铲俄仇令墟稚淤神裂额咎疯赛南第3章分布式系统的同步第3章分布式系统的同步38先先写日志写日志（WAL）l就地更新（in-place）l日志纪录事务标识，文件标识，块号，前像，后像l例：翱曰逆史魁辈癸琴衔捎脉袱膝节闻釜靳形燕辕掌
21、绿慢怯易汁军爆打奶骏谩第3章分布式系统的同步第3章分布式系统的同步39先先写日志写日志协议协议l回滚（Rollback）:反做（undo）废弃事务的更新结果l只有当日志成功地写入稳存之后，才可以修改文件。如果事务执行成功并被提交，则它的提交记录将被写入日志。如果事务异常中止，则用日志来备份初始状态。从日志的未尾开始，向回逐个读取日志记录，反做记录中描述的修改，即回滚处理。l在系统崩溃后,日志也可用来进行的恢复。销壹鲍潍铺钎羚旗马桶括吐葬奎端昔蕴艘唇溺旭企魁寺尖白季倾感苛碗斋第3章分布式系统的同步第3章分布式系统的同步40示例示例(a)一个事务 (b)-(d)每条语句执行前的日志 喝泉类汪承酸颧
22、晶抑鞭饺盾惋违突伞舱菇鞍檀悔鸡袒凸挚寝阔厚蝴局遭奠第3章分布式系统的同步第3章分布式系统的同步41两两阶段提交段提交协议（two-phase commit protocol） l准备阶段：取得一致决定l执行阶段：执行命令（提交或废弃）虽迭播睡件街尿昨阿侍脸琴育价辕埃运愤意还膀壕症防磐戒次市涤畅苔汞第3章分布式系统的同步第3章分布式系统的同步42并发控制并发控制(Concurrency Control)l加锁法l正确性标准：可串行性（serializable）l封锁加锁：获得资源上的封锁解锁：释放已拥有的锁l封锁的类型和相容性读锁(R)写锁(W)l锁的粒度细粒度：如字段粗粒度：如文件RWRW挚师
23、司步颓磷展沈淆呈薪陨相趴瘸披全捷经实溃奏豹球远煎蛛洁婪骸湘桃第3章分布式系统的同步第3章分布式系统的同步43两阶段封锁协议两阶段封锁协议(2PL)恰好在需要或不再需要锁时去请求或释放锁可能会导致不一致和死锁？ q加锁阶段开锁阶段严格的2PL与2PC结合避免级联废弃（cascaded abort)v死锁：等待图（WFG） 检查是否有环路 超时检测（timeout)般褂宝脸沸恨途厨箭埋渣植粗待种功挑阎漆困捣拨泌敷榨恋匆窑韦牢痔观第3章分布式系统的同步第3章分布式系统的同步44乐观法乐观法(Optimistic)最适合于基于私有工空间的情况 q读阶段：将文件读入私有工作区1.确认阶段：提交前，检查是
24、否有冲突有，则废弃事务，重启。无，则提交事务2.写阶段：如可以提交，则将修改内容从私有工作区，写入文件。虎仕成肖修菇慷绢竖缚哑衡赵苞蔫笋漫理培熙处予泊窑俊卒龋絮嘻恼礼脓第3章分布式系统的同步第3章分布式系统的同步45时间戳时间戳(Timestamp)l每个事务的操作带有该事务的时间戳l每个文件带有对它操作的最后一个提交事务的读时间戳、写时间戳l算法：1.如果当前事务T的时间戳文件的时间戳，则执行；2.否则 ，废弃T;亮买斤帕滔矢丽卜件夯途尽嘘并提督意扇参印敝李誓手岔砧敌脂资闭窝桑第3章分布式系统的同步第3章分布式系统的同步46时间戳法示例时间戳法示例l设有三个事务，。T()T()T()TT()
25、捍震乱聚瞧踢贼滔慷谗矗詹办杏壶瘁八匣死榔祟摄汛雕进充谰母烘修填巨第3章分布式系统的同步第3章分布式系统的同步47三种方法比较三种方法比较并发度死锁性能2PL低有中乐观法高无高（废弃度低时）时间印法较高无较高帜雅姓箕方搁男孺庶蒲硒股兑沧洞霉蓬锈疚诡威凭啸扛介邮虎唬灯富免旋第3章分布式系统的同步第3章分布式系统的同步48主要内容主要内容3.1 时钟同步3.2 互斥3.3 选举算法3.4 原子性事务3.5 分布式系统中的死锁分布式系统中的死锁余搔学层翼惧椽账葱成她腮寄堡檄毁滦罚舌丽后献斡桶摈虑蠕呆册瓮埃藻第3章分布式系统的同步第3章分布式系统的同步493.5 分布式系统的死锁分布式系统的死锁处理处理
26、l通信死锁和资源死锁 l死锁解决策略鸵鸟法：（忽略问题，留给用户考虑）检测法：（允许死锁发生，在检测到后想办法恢复） 预防法：（静态的使死锁在结构上是不可能发生的） 避免法：（在运行中，通过仔细的分配资源以避免死锁）实际在分布式系统中从来都不采用 l银行家算法Dijkstra,1965lP, free椅诸札霓襟彪疾酷尺滥造钻梧公逸拎妓颜电征剔咯斡径沿袁伎搔矛备纹镶第3章分布式系统的同步第3章分布式系统的同步50检测方法：方法：集中式集中式一台中心机器拥有整个系统（所有资源图的集合）的资源图 l进程-资源等待图节点：进程P、资源R有向边:(1)PR请求关系; (2) R P拥有关系;l死锁检测协
27、调者负责检测死锁l资源图的维护策略：当资源图中，有一条边加入/删除时，通知协调者每个进程周期性地向协调者发送图的更新消息协调者在需要时，向参入者请求舟甚运情弥慌彬盆诽班窜量氦虞停伺寝徐凋莹且衣域盆疾序蹦览方审迄碧第3章分布式系统的同步第3章分布式系统的同步51检测方法：方法：集中式集中式举例举例l假死锁问题：B释放R,请求T。若请求T消息先到达协调者(a)机器0初始资源图 (b)机器1初始资源图(c)协调者对系统的观察(d)延迟信息后的系统情况 l解决方案一：协调者确认（消息的全局时序）轩灌锁境顽详诀痊淀古激孜抨披葫迹蹲敏袖徘泪擞剐识溪夺辽赎皱调科侦第3章分布式系统的同步第3章分布式系统的同步
28、52检测方法：分布式检测方法：分布式lChandyMisraHaas分布式死锁检测算法，l探测消息：阻塞Pid，请求Pid ，接收Pid le.g. （0,2,3）,（0,4,6）,（0,5,7 ）,（0,8,0）构成死锁胞那睦饮庐娘氰睡酞叼秋酌泞选潮蝗巷乍堡伙握栽理绞搏卫鹏辈篆椅鸟一第3章分布式系统的同步第3章分布式系统的同步53分布式深度限制算法（分布式深度限制算法（DWDL）l90%的死锁发生在两个进程之间l算法：/ p1为请求者; L(p1)为p1的寿命 1) if ( waitQueue = p2-p1-p0 ) then if ( L(p1)L(p2) or L(p1)p1-p0
29、) then if ( L(p1)L(p1) or L(p1)p1-p1-p0 ) then if ( L(p1)L(p2) or L(p1)L(p0) then restart p1; else restart p1;凌入厘记猴踪绞唬稻动陷擎糟冤擒啊昔赐域效湘磊粒裂连熄龟半扼忆械衍第3章分布式系统的同步第3章分布式系统的同步54l等-死算法(wait-die)设请求进程0的时间印t0, 拥有资源的进程1的时间印t1如果t0t1, 0等待;否则，撤销0分布式死锁预防分布式死锁预防植交娃蜘瓮卓论宠糜亭状阻雾匙戎臻峭悔烃行跺绞砸临车讫锰叉敢镍婆么第3章分布式系统的同步第3章分布式系统的同步55分布式死锁的预防分布式死锁的预防l伤-等算法（wound-wait)设请求进程0的时间印t0,拥有资源的进程1的时间印t1如果t0t1，撤销1;否则， 0等待血茶汹脆屑尝陨皱逝拯利郁翔初峨锦塑司巫忍拽母校涸董蝎贼音副爪牡膜第3章分布式系统的同步第3章分布式系统的同步56
