高级操作系统课件-第八章容错性PPT资料.ppt
- 文档编号:7032069
- 上传时间:2023-05-07
- 格式:PPT
- 页数:43
- 大小:498.50KB
高级操作系统课件-第八章容错性PPT资料.ppt
《高级操作系统课件-第八章容错性PPT资料.ppt》由会员分享,可在线阅读,更多相关《高级操作系统课件-第八章容错性PPT资料.ppt(43页珍藏版)》请在冰点文库上搜索。
增加额外的设备或进程,进程恢复平等组与等级组,为防止进程失败,把进程复制到组当消息发送到组时,组中所有成员都接收它,一个进程失败,其他进程可以接管它进程组是动态的平等组通信:
增加延迟和开销简单等级组通信:
单点失效,组成员,组通信时,需要创建和删除组,以及允许进程加入和离开使用组管理器:
存储相应数据库,直接、有效、容易实现;
单点失败分布式的方法:
加入组:
发消息给所有的组成员离开组:
发消息给所有的组成员,需考虑崩溃的情况进程加入和离开必须与数据消息的发送同步重建组,故障掩盖和复制,复制进程,用一个容错的进程组来代替一个脆弱的进程需要多少复制?
如果系统能经受K个组件的故障而且能满足规范的要求,被称为K容错的如果组件是失败沉默的,具有K+1个组件即可如果组件发生拜占庭错误(Byzantinefault),继续错误运行,则至少需要2K+1个组件才能获得K容错拜占庭错误:
在非失败沉默模型下,一个有故障的进程可能会对其它进程发出干扰消息,从而影响这些进程的正常工作。
拜占庭错误是所有故障类型中最严重的,故障系统的协议
(1),分布式协议算法的目标是使所有的非故障进程就一些问题在有限步骤内达成一致通信是否可靠:
两军问题进程故障:
拜占庭将军问题Lamport证明在具有m个故障进程的系统中,只有存在2m+1的正常工作的进程才能达成协议,故障系统的协议
(2),三个忠诚将军和一个叛徒的问题将军宣布他们的兵力在(a)基础上每个将军的向量每个将军收到的向量,故障系统的协议(3),两个忠诚将军和一个叛徒的问题,可靠的C-S通信,RPC系统失败的五种情况:
客户不能定位到服务器客户到服务器的请求消息丢失:
使用定时器服务器在收到请求后崩溃最少一次语义:
再次尝试操作,将应答传给用户,RPC最少执行一次最多一次语义:
放弃并报告失败,RPC最多执行一次从服务器到客户的响应消息丢失:
使用定时器;
幂等操作;
为每个请求分配一个序列号客户在发送请求后崩溃:
孤儿进程浪费资源处理孤儿进程的方法消灭:
客户重启后根据客户端日志清除孤儿进程再生:
将时间分为顺序编号的时期,客户重启后广播清除孤儿进程优雅再生:
找不到拥有者,再清除孤儿进程到期:
给每个RPC指定标准的执行时间,服务器崩溃ServerCrashes
(1),client-server通信中的服务器通常情况执行后崩溃执行前崩溃,可靠的组通信,可靠多播:
发送到一个进程组的消息被传递到该组的每个成员问题:
如果通信期间有进程加入如果通信期间一个(发送)进程崩溃基本的可靠多播方法:
假定所有的接收者已知而且假定不会失败的简单可靠多播方法可靠多播的可扩展性原子多播:
实现存在进程失败的情况下的可靠多播,可靠的组通信-基本的可靠多播方法,当所有的接收者已知而且假定不会失败的简单的可靠多播方法消息传递反馈,可靠多播的可扩展性,上面介绍的可靠多播方法不能支持过多的接收者:
反馈拥塞解决办法:
接收者不反馈,只有通知消息丢失时反馈一消息不能保证永远不发生反馈拥塞发送者需要一直在缓存器中保留消息无等级的反馈控制分等级的反馈控制,无等级的反馈控制NonhierarchicalFeedbackControl,反馈抑制:
几个接收者要发送重发请求,但是第一个重发请求抑制了其他的请求。
具有很好的可扩展性问题:
需要每个接收者对反馈消息进行准确的调度,否则还会有多个接收者同时反馈中断其他成功接收消息的进程,分等级的反馈控制HierarchicalFeedbackControl,在非常大的接收组中获得扩展性多等级的可靠多播:
每个本地协调者都把消息转发给它的孩子然后再处理重发请求每个子组内可使用适合小组的可靠多播方式协调者有自己的缓存器,如果自身丢失消息,则请求父组的协调者重发消息在基于确认的方法中,如果收到消息,协调者向父亲发送确认。
如果协调者从子组的所有成员和它的孩子得到对消息m的确认,则删除消息m,原子多播,需要在存在进程失败的情况下获得可靠多播的情况原子多播:
消息要么发送给所有进程,要么一个也不发送通常需要所有的消息都按相同的顺序发送给所有的进程分布式系统中的复制数据库原子多播确保没有故障的进程对数据库保持一致;
当一个副本从故障中恢复并重新加入组时,原子多播强制它与其他组成员按保持一致虚拟同步消息排序实现虚拟同步,虚拟同步VirtualSynchrony
(2),虚拟同步多播的原理,虚拟同步:
保证多播到组视图的消息被传送给组中的每个正常进程如果发送消息的进程在多播期间失败,则消息或者传递给剩余的所有进程,或者被每个进程忽略所有多播都在视图改变之间进行,消息排序,可靠不排序的多播:
对接收不同进程发送的消息的次序不做任何保证FIFO顺序的多播:
按照消息发送的顺序传送同一进程的消息,对不同进程发送的消息的传送顺序没有约束按因果关系排序的多播:
按因果关系排序多播来保留消息间的因果关系全序多播:
无论消息传送是无序、FIFO顺序还是按因果关系排序,对所有的组成员按相同的次序传送,消息排序
(1)-不排序的多播,同组中的三个通信进程,每个进程中时间的顺序按垂直顺序排列,消息排序
(2)-FIFO顺序的多播,同组中的四个通信进程,具有两个不同的发送者,在FIFO多播下可能的消息传送顺序,消息排序(3)-全序多播,对所有的组成员按相同的次序传送,消息排序(4),六种不同的虚拟同步可靠传播提供了全序的消息传送的虚拟同步可靠多播称为原子多播,实现虚拟同步,保证发送到组视图G的所有消息在组成员关系改变之前发送到G中的所有正常进程进程4注意到进程7已经崩溃,发送一个视图改变进程6发送所有的不稳定消息(所有进程都收到的消息称为稳定消息),然后发送一个flush消息当进程6从其他每个进程收到flush消息后,建立一个新的视图,分布式提交单阶段提交,分布式提交:
具有原子性:
要使一个操作被进程组中每一个进程都执行或都不执行。
通常使用协调者。
协调者向事务所有的参与者发出提交或者中止请求,并不断重复该请求,直到所有参与者报告它们执行了该请求。
问题:
如果遇到某一问题,导致某一参与者无法完成提交,本协议就无法实现。
分布式提交两阶段提交
(1),简单、实用、可靠,成为事实上的工业标准。
在两段提交协议中,将提交分成两个阶段,第一阶段(表决阶段),事务的协调者询问各个参与者是否可以提交,此时,各个参与者将回答消息发给协调者。
协调者根据收到的消息,看是否可以真正提交。
第二阶段(完成阶段),如果可以提交,则通知各参与者立即执行提交,否则,通知它们中止此事务。
两阶段提交
(2),2PC中的协调者的有限状态机2PC中的参与者的有限状态机参与者一旦投票,则失去自主能力,必须等待协调者的最终决定,可能造成阻塞可能的阻塞状态:
参与者在INIT状态等待协调者的VOTE_REQUEST消息协调者在WAIT状态等待来自每个参与者的表决参与者在READY状态等待协调者发送的全局表决消息,两阶段提交(3),参与者P在READY状态下与另一个参与者Q联系时采取的行动当所有运行的参与者都处于READY状态时,尽管都已同意提交,但可能有崩溃的参与者(不一定同意提交),因而无法做出决定(即使选举出新的协调者),只能等待原协调者恢复,两阶段提交(4),2PC中协调者采取的操作,whileSTART_2PCtolocallog;
multicastVOTE_REQUESTtoallparticipants;
whilenotallvoteshavebeencollectedwaitforanyincomingvote;
iftimeoutwhileGLOBAL_ABORTtolocallog;
multicastGLOBAL_ABORTtoallparticipants;
exit;
recordvote;
ifallparticipantssentVOTE_COMMITandcoordinatorvotesCOMMITwriteGLOBAL_COMMITtolocallog;
multicastGLOBAL_COMMITtoallparticipants;
elsewriteGLOBAL_ABORTtolocallog;
两阶段提交(5),2PC中参与者采取的操作,writeINITtolocallog;
waitforVOTE_REQUESTfromcoordinator;
iftimeoutwriteVOTE_ABORTtolocallog;
ifparticipantvotesCOMMITwriteVOTE_COMMITtolocallog;
sendVOTE_COMMITtocoordinator;
waitforDECISIONfromcoordinator;
iftimeoutmulticastDECISION_REQUESTtootherparticipants;
waituntilDECISIONisreceived;
/*remainblocked*/writeDECISIONtolocallog;
ifDECISION=GLOBAL_COMMITwriteGLOBAL_COMMITtolocallog;
elseifDECISION=GLOBAL_ABORTwriteGLOBAL_ABORTtolocallog;
elsewriteVOTE_ABORTtolocallog;
sendVOTEABORTtocoordinator;
两阶段提交(6),处理(来自其他READY进程)决定请求的步骤,actionsforhandlingdecisionrequests:
/*executedbyseparatethread*/whiletruewaituntilanyincomingDECISION_REQUESTisreceived;
/*remainblocked*/readmostrecentlyrecordedSTATEfromthelocallog;
ifSTATE=GLOBAL_COMMITsendGLOBAL_COMMITtorequestingparticipant;
elseifSTATE=INITorSTATE=GLOBAL_ABORTsendGLOBAL_ABORTtorequestingparticipant;
elseskip;
/*participantremainsblocked*/,三阶段提交,三阶段提交阶段1同两阶段方式阶段2收到有一个abortT,则abortT收到所有readyT,则precommitT节点precommitT之后,写Log,发出acknowledgeT阶段3收到所有ack,则commitT节点commit后,发出ackT收到所有ackT后,completeT,三阶段提交,3PC中的协调者的有限状态机3PC中的参与者的有限状态机没有一个直接转换到COMMIT和ABORT的状态不存在这样的状态:
它不能做出最后决定,而且可以直接转换到COMMIT状态可能的阻塞状态:
参与者在INIT状态等待协调者的VOTE_REQUEST消息协调者在WAIT状态等待来自每个参与者的表决协调者在PRECOMMIT状态等待来自每个参与者的表决:
超时时,认为参与者已崩溃,但已投票参与事务,所以可以多播提交参与者在READY状态等待协调者发送的全局消息:
超时时,认为协调者已崩溃,联系其他参与者的状态ABORT-ABORT;
PRECOMMIT-PRECOMMIT;
都处于READY-事务可以被安全中止(因为出故障的参与者还未作出提交的决定),选举出新的协调者继续执行参与者在PRECOMMIT状态等待协调者发送的全局消息:
超时时,认为协调者已崩溃,联系其他参与者的状态COMMIT-COMMIT;
都处于PRECOMMIT-事务安全提交,恢复,恢复:
用正确的状态代替错误的状态回退恢复(backwardrecovery):
从当前错误的状态回到先前正确的状态需要记录系统的状态(检查点)通用的技术,不依赖特定的系统或进程向前恢复(forwardrecovery):
尝试从可以继续进行的某点开始把系统带入一个正确的状态需要预先知道会发生什么错误回退恢复技术存在的问题开销较大还可能发生相同的错误有些状态无法回退,恢复-稳定存储,要恢复到先前的状态,需要存储所需的信息存储分类:
RAM、磁盘和稳定存储稳定存储(一对磁盘实现)在驱动器1更新后崩溃坏点,检查点(Checkpointing),恢复线:
最近的分布式快照(一致的全局状态)独立检查点协调检查点,独立检查点IndependentCheckpointing,多米诺效应,独立检查点:
每个进程独立地按时记录它的本地状态不能保证组成一个分布式快照,可能产生多米诺效应进程可能会记录不属于全局一致状态的无用检查点,导致不必要的开销为达到一致的全局状态,计算恢复线需要对每个进程设置检查点时记录的时间间隔依赖关系进行分析,协调检查点,协调检查点:
每个进程都同步地把它们的本地状态记录在本地的稳定存储中保存的状态自动保持全局状态一致可以使用分布式快照算法来协调检查点,消息日志MessageLogging,因为涉及到向稳定存储中写入状态,设置检查点是开销很大的操作需要可以减少检查点数目但仍允许恢复的技术消息日志思想:
错误恢复时,使用一个检查点作为开始,然后把从该点以后发送的所有消息都重发并进行处理所有发送和接收的消息都可记录下来,前者称为发送者日志,后者称为接收者日志。
接收者的恢复只需重放接收者日志的内容即可。
小结,容错性简介进程恢复可靠的C-S通信可靠的组通信分布式提交恢复,习题,下面情况下,最少一次语义合适还是最多一次语义合适?
从文件服务器读写文件编译一个程序远程银行,下图中,FIFO与全序结合情况下。
可能的消息发送顺序?
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 高级 操作系统 课件 第八 容错