《第8章高级操作系统容错性要点》由会员分享，可在线阅读，更多相关《第8章高级操作系统容错性要点（60页珍藏版）》请在金锄头文库上搜索。
1、第第8章章 容错性主要内容8.1 容错性概述8.2 进程恢复8.3 可靠的客户服务器通信8.4 可靠的组通信8.5 分布式提交 8.6 恢复28.1 容错性概述n可依赖系统（Dependable, Trustworthy）n可用性（availability）n在给定时刻能正确操作的概率n可靠性（Reliablity）n在给定期间能正确操作的概率n安全性（Safty）n临时失效不会造成灾难n可维护性（Maintainability）n易于对失效进行修复的系统3基本概念（1）n失效（fail, failure）、失灵n一个系统不能满足它的承诺（提供服务）n差错（error）：n导致系统失效的系统状
2、态n故障（fault）：n导致差错发生的原因4基本概念（2）n平均无故障时间(MTTF)n平均能够正常运行多长时间，才发生一次故障。用来度量可靠性np为每秒失效概率n平均无故障时间(MTTF) = 1kp(1-p)k-1=1/pn例：p=10-6，MTTF=106秒=11.6天n平均维修时间（MTTR） n系统发生故障后维修和重新恢复正常运行平均花费的时间 n用来度量可维护性n可用性= (MTTF / (MTTF + MTTR) 5基本概念（2）n故障控制n预防n去除n预告n容错（fault tolerance）n即使发生故障，系统仍能提供服务n故障类型n短暂型(transient):出现一次
3、，再也不出现n间歇型(intermittent)：消失后，再重复出现n永久型(permanent)：一直存在6失效（失败）模型失失效类型效类型描述描述崩溃性失效服务器停止。但在停止前一直正确工作遗漏性失败 接收遗漏 发送遗漏服务器不能响应连入的请求服务器不能接收连入的消息服务器不能发送消息定时性失效服务器的响应超出规定的时间间隔响应性失效 值失效 状态变迁失效服务器的响应不正确响应的值是错误的服务器偏离正确的控制流任意性失效服务器在任意的时刻产生任意的响应7失效（失败）模型n失败模型n失败缄默(fail-silent)。不通知失效。n失败即停 (fail-stop)。良性的。易检测。n失败安全
4、(fail-safe)。不产生恶果。n拜占庭(Byzantine)故障。恶意的。难检测。n拜占庭帝国（330-1453）n系统类型n同步系统：在规定上限时间内有响应n异步系统：响应时间没有上限8基于冗余的失效屏蔽技术n冗余类型n信息冗余：如，海明码。n时间冗余：如，重发，重做n物理冗余：n软件:如复制进程n硬件：如复制电路n信息冗余和物理冗余都属于空间冗余9基于冗余的失效屏蔽技术n三模冗余方法(TMR,Triple Modular Redundancy)n三路表决器(voter)：三路输入，一路输出n可屏蔽一路错误（任意性失效）108.2 进程恢复n进程容错n进程组：具有相同功能的进程集合n组
5、成员籍n加入：具有成员籍n脱离：注销成员籍n多成员籍：同时属于不同的组n设计问题n需要复制的程度n无故障时，平均情况和最坏情况下的系统性能n有故障时，平均情况和最坏情况下的系统性能 11组的管理（1）n扁平组：所有成员是同等的n层次组：协调程序和工作程序12组的管理（2）n组成员籍管理n组服务器：集中式管理n多播通信：分布式管理NNn故障后，组的退出nfail-stop类型：发送Goodbye信息nfail-silent类型：需其他成员发现13组的管理（3）n消息同步n加入组时：立刻收到所有消息n退出组时：不再受到任何消息n组的重建n当组崩溃后，重新建立组n重建协议14复制容错技术nk-容错度
6、：n在有k个进程发生故障时，系统仍能正确运行nFail-stop型故障：n对k-容错度，需k+1冗余度n拜占庭型故障：n对k-容错度，需2k+1冗余度n容错的前提条件 n所有的请求到达所有服务器的顺序应相同 n原子广播问题（atomic broadcast problem） 15故障系统的协定问题n协定(agreemnt)n对某些问题的一致意见。如，是否提交事务，负载划分，同步等n分布式协定算法n在有限的步骤内，所有非故障进程达成协定n底层系统中可能的情况：1.同步vs异步系统2.限定的或无限定的通信延迟3.有序的或无序的消息递交4.单播(unicast)或多播(multicast)式消息传送
7、16故障系统的协定问题n能够达成分布式协定的环境17故障系统的协定问题可以取得一致的三种情况：1、处理机同步方式、通信延时有限n处理机可用超时检测机制，确定其他失败进程2、消息有序，广播式传输n每个处理机原子式广播一个初始值，其他处理器按照次序接收，能够同意谁是第一个发送的3、处理机同步，消息有序18举例：故障系统的协定问题n拜占庭将军协定问题n假设通信是可靠的，但进程可能是不可靠的n例：3个忠诚将军，1个叛变将军nLamport递归算法n共4步：(a)对外报告(b)收集向量(c)报告向量(d)生成结果向量：（1，2，未知，4）19举例：故障系统的协定问题n若三个将军中，有两个忠诚将军，一个叛
8、变将军，则不能判断出哪个将军叛变。n若要有m个进程出错的系统实现协同一致，最少要有2m1个正常进程。进程总数为3m+1。n需超过2/3多数，才能达成协定20故障检测n进程故障检测n主动式方法，发送 “Are you alive?”消息n常用方法， ping操作n被动式方法，等待发来的故障消息n预测方法：超时机制，在规定时间内作出响应，否则，视为发生故障218.3 客户服务器通信的可靠性n点到点通信n可靠通信：防止通信失效n遗漏型失效：消息丢失n解决策略：利用可靠的传输协议，如TCP协议。确认和重新传输n连接崩溃失效：连接中断n不能屏蔽，需重建连接n解决策略：抛出例外，通知客户进程22RPC失效
9、(1)nRPC失效n5种失效情况客户服务器1.定位失败2.请求消息丢失3.服务器失败5.客户失败4.应答消息丢失23RPC失效(2)n1、客户不能定位服务器n可能服务器被修改，客户存根（stub）与新的服务器存根不匹配n解决策略：n抛出例外信号SIG-NOSERVER，然后由编写的信号处理程序做相应处理。n没有透明性n2、丢失请求消息n解决策略：n客户发现超时，重发请求24RPC失效(3)n3、服务器崩溃n崩溃情况n解决策略：n至少一次语义n最多一次语义n听之任之n确切一次语义(a) 正常情况; (b) 在执行后崩溃 (c) 在执行前崩溃25RPC失效(4)n举例：打印文本。在打印服务器失效时
10、，客户和服务器的策略组合nM(发送完成消息)；P(打印)；C(崩溃)客户客户服务器服务器策略策略 M - P策略策略 P - M重发策略重发策略MPCMC(P)C(MP)PMCPC(M)C(PM)总是重发请求DUPOKOKDUPDUPOK不重发OKOKOK当收到ACK时，重发DUPOKDUPOK当没收到ACK时，重发OKOKOKDUPOK26RPC失效(5)n4. 丢失应答消息n解决策略n定时器，超时检测，重发请求n问题：重复操作n解决策略n构造幂等性操作（idempotent）n顺序号n标志：区分原始消息和重发消息27RPC失效(6)n5. 客户崩溃n孤儿进程问题n解决策略：n根除法：利用日
11、志，撤销孤儿进程n再生法：设置时期（epoch）。到达epoch时，重新创建客户进程n温和再生法：撤销无主的孤儿n过期法：设置时间量T。如果超过T，则撤销客户的请求（不一定是孤儿）。288.4可靠的组通信n假定：进程操作正确，在通信中不加入或退出分组n可靠多播n将每一个消息递交给每一个当前组员n不可靠多播n不能保证将一个多播消息递交给所有组员SRRRmmm29基本的可靠多播模式n解决策略a)消息传播：记录顺序号b)报告反馈：如果丢失，返回负ACK，重新发送30可靠多播的可伸缩性（1）n反馈爆炸问题：N1n简单解决方案：n接收者只返回NACK(否定)消息n发送者保留消息到历史缓冲区n仍然存在的问
12、题历史缓冲区溢出问题NACK反馈爆炸SRRRACKACKACK31可靠多播的可伸缩性（2）n无层次反馈抑制技术（SRM,可伸缩的可靠多播协议）n不返回ACK，只返回NACK，广播式发送。n压缩NACK。随机延迟后，如果接收到其他的重发请求，就禁发NACK。这样，只有一个重法请求。n用途：例，白板系统32可靠多播的可伸缩性（3）n层次化反馈控制n一个大组划分成若干个小组，形成一个树n发送者所在的小组为树的根n每个局部协调者转发消息给它的孩子n局部协调者负责请求重发33原子性多播 (1)n原子性多播问题n消息要么递交给所有组员，要么一个也不递交n对于每个组员，所有消息的递交次序是相同的n用途举例：
13、主动式复制协议 n故障组员处理n出故障后，自动退出组n修复后，重新加入组n 组视图G（group view）n在发送一个消息时，属于该组的所有进程的名单34原子性多播 (2)n视图变更n向所有的组员宣布加入或者退出该组n带有通信层的分布式系统结构n能区分消息接收和消息递交35原子性多播(3)n虚拟同步(virtually synchronous)的可靠多播n如果发送者在多播时崩溃，消息将递交给其他所有组员，或者，被它们丢弃n原理：所有多播在视图变更之间进行36原子性多播(4)n消息递交次序n1. 可靠的无序多播n不保证接收到消息的递交次序是相同的n举例：Process P1Process P2
14、Process P3sends m1receives m1receives m2sends m2receives m2receives m1时间37原子性多播(5)n2. 可靠的FIFO次序多播n从同一发送者接收到的消息的递交次序与发送次序一致n举例：发送者P1,P4；接收者P2,P3Process P1Process P2Process P3Process P4sends m1receives m1receives m3sends m3sends m2receives m3receives m1sends m4receives m2receives m2receives m4receives
15、 m4时间38原子性多播(6)n3. 可靠的因果次序多播n具有因果关系的消息的递交次序与发送次序一致，无论消息是否由同一发送者发送的n可使用时间戳向量实现39原子性多播(7)n4. 全序递交（Total-ordered delivery）n对于所有组员的消息递交次序，是相同的。n原子性多播：n提供全序递交的虚拟同步可靠多播40原子性多播(8)n虚拟同步的可靠多播的6个版本多播基本的消息次序全序递交?可靠多播无NoFIFO多播FIFO次序型递交No因果多播因果-次序型递交No原子性多播无YesFIFO原子性多播FIFO-次序型递交Yes因果原子性多播因果-次序型递交Yes41原子性多播(8)n虚
16、拟同步性的实现n举例：ISIS系统P4发现P7崩溃，多播视图变更消息(vc)P6发送所有不稳定消息，后跟 flush（刷新）消息P6 接收到所有返回的flush消息后，确定新的视图Gi+1428.5 分布式提交n两阶段提交协议 (a) 协调者的有限状态机 (b) 参与者的有限状态机43两阶段提交协议n当参与者P处于READY状态 ， 并已与另一参与者Q通信之后，可能采取的动作.进程进程 Q状态状态进程进程 P动作动作COMMIT变迁到 COMMITABORT变迁到ABORTINIT变迁到ABORTREADY与其他参与者联络44两阶段提交协议n协调者执行步骤write START _2PC to
17、 local log;multicast VOTE_REQUEST to all participants;while not all votes have been collected wait for any incoming vote; if timeout write GLOBAL_ABORT to local log; multicast GLOBAL_ABORT to all participants; exit; record vote;if all participants sent VOTE_COMMIT and coordinator votes COMMIT write
18、GLOBAL_COMMIT to local log; multicast GLOBAL_COMMIT to all participants; else write GLOBAL_ABORT to local log; multicast GLOBAL_ABORT to all participants;45两阶段提交协议n参与者执行步骤write INIT to local log;wait for VOTE_REQUEST from coordinator;if timeout write VOTE_ABORT to local log; exit; if participant vot
19、es COMMIT write VOTE_COMMIT to local log; send VOTE_COMMIT to coordinator; wait for DECISION from coordinator; if timeout multicast DECISION_REQUEST to other participants; wait until DECISION is received; /* remain blocked */ write DECISION to local log; if DECISION = GLOBAL_COMMIT write GLOBAL_COMM
20、IT to local log; else if DECISION = GLOBAL_ABORT write GLOBAL_ABORT to local log; else write VOTE_ABORT to local log; send VOTE ABORT to coordinator;46两阶段提交协议n对来自其他参入者的决策请求的处理步骤/* executed by separate thread */while true wait until any incoming DECISION_REQUEST is received; /* remain blocked */ read
21、 most recently recorded STATE from the local log; if STATE = GLOBAL_COMMIT send GLOBAL_COMMIT to requesting participant; else if STATE = INIT or STATE = GLOBAL_ABORT send GLOBAL_ABORT to requesting participant; else skip; /* participant remains blocked */47三阶段提交协议n目的：n在失败即停故障情况下，避免进程阻塞 (a) 协调者的有限状态机
22、 (b) 参与者的有限状态机48三阶段提交协议n协调者（WAIT）：发现超时,则abortn协调者(PRECOMMIT)：发现超时,继续commitn参与者(INIT)：发现超时,则abortn参与者(READY)：n发现超时，询问其他参与者n如果有COMIT/ABORT,则执行n如果都为PRECOMMIT,则commitn如果有INIT，则abortn如果都为READY，则abortn参与者(PRECOMMIT)：发现超时,继续commit498.6 恢复处理n目的: 使系统从错误状态到正确状态n类型：n向后恢复(backward recovery)：使系统返回到上一个正确状态n向前恢复(f
23、orward recovery)：使系统前进到一个正确的新状态n检查点技术(checkpoint)n消息日志技术（logging）n基于发送者的写日志n基于接受者的写日志50可恢复的稳定存储器n稳定存储器状态a)稳定存储状态b)崩溃状态：在更新驱动器1后发生c)坏点状态：出现坏扇区51检查点n分布式快照（snapshot）n一致的全局状态n恢复线n最近的分布式快照，最近的一致性割集n举例52独立检查点（1）n独立检查点n每个进程的检查点是相互独立的n问题：多米诺效应n局部状态没有形成分布式快照，导致级联回滚（cascaded rollback）过程n举例：只有m,m的接受记录，没有发送记录53
24、独立检查点（2）n解决方法n设CPi(m)表示Pi的第m个检查点n设INTi(m)表示CPi(m)和CPi(m-1)之间的间隔n当Pi在INTi(m)中发送消息x时，带上(i,m)n当Pj在INTj(n)收到x后，记录依赖关系INTi(m) INTj(n)nPj在CPj(n)中加入该依赖关系n当Pi需要回滚到CPi(m-1)时，则Pj需要回滚到CPj(n-1)54协作式检查点（2）n同步写检查点n所有进程同步地在本地稳存中写检查点，使保存的状态自动地保持全局一致。n非阻塞式算法n分布式快照算法n两阶段阻塞式算法nCHECKPOINT_REQUEST：n协调者发送命令，所有进程写局部检查点，将要
25、发送消息插入队列，向协调者返回ACK消息。nCHECKPOINT_DONE：n当协调者收到所有的ACK后，发送命令，所有进程继续55协作式检查点（2）n改进算法 - 增量快照算法n最近发送进程：n进程P在上一个检查点向其发送过请求的进程。n协调者恢复依赖进程：n在上一个检查点，直接或间接收到协调者消息的进程。因此，由最近发送进程的闭包集组成。n协调者只向其最近发送进程多播命令。n当进程P收到写检查点请求时，仅向P的最近发送进程，转发该请求。每个进程仅转发该请求一次。n当所有进程被确认后，协调者发送第二个多播命令，开始实际写检查点56消息日志（1）n基本思想n减少检查点的个数n如果消息的传送可以
26、重放(replay)，则可取得全局一致性状态，而不必从稳存恢复。n分段确定性模型(piecewise deterministic model)，假定：n每个进程在一序列的间隔中执行，有先后次序，是确定性的。每个间隔是可重放的。n每个间隔以一个非确定性事件开始，以下一个非确定形式件发生而结束。n如果记录所有非确定性事件，则全部执行可重放。57消息日志（2）n孤儿进程n在进程P崩溃后，仍然存活的进程。但在P恢复后，其状态与P不一致n举例：n进程Q崩溃，消息m2没有写日志nQ恢复后，m2,m3消息没有重放，导致R为孤儿进程58消息日志（3）n消息n消息头：发送者、接受者、顺序号、递交号n稳定消息：已记入稳存，不会丢失nDEP(m)：n依赖于消息m递交的进程集合。n与m有因果关系的进程集合nCOPY(m)：n拥有m的副本，但未将m写入稳存的进程集合.n孤儿进程nQ存在于DEP(m)，而COPY(m)中的所有进程崩溃59消息日志（4）n避免孤儿进程n如果QDEP(m)，则保证QCOPY(m)n悲观型(pessimistic logging)日志协议n保证每个不稳定的消息m最多提交到一个进程n不可能出现孤儿进程n乐观型(optimistic logging)日志协议n在崩溃后处理，将DEP(m)中的孤儿进程都回滚到不再属于DEP(m)的状态60
