分布式系统中处理机管理

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第四章 分布式系统中的处理机管理,1 进程调度,1.进程的状态与切换,进程的状态可以分为活跃态与非活跃态两大类。,运行态：所属线程正在占用,CPU,运行,就绪态：具备运行条件，但未占有,CPU,运行,等待态：由于自身原因不能运行，但传输尚未结束,挂起态：由于自身原因不能运行，放弃所占用的资源,原则上，统一进程的线程应该在同一,CPU,1,第四章 分布式系统中的处理机管理,线程调度管理的方式,核心管理模式：,对每一个进程。核心为其建立一个线程调度表。同一个进程的线程可以并行。,线,程,线,程,线,程,线,程,核 心,2,第四章 分布式系统中的处理机管理,进程管理模式：,在用户区内进程创建一个虚拟处理器（又称为进程的运行系统），对应一个物理,CPU。,线程可以在阻塞时调用运行系统保留现场和挂起，运行系统负责调度线程运行。这样进程可以设定自己的调度策略，但效率较低。,现代分布式系统中，线程是独立的运行单位和调度单位。,2.,线程组织模型,线程工作的组织方式分为三种：派遣工作模型（在进程中设立派遣进程负责选择工作线程运行）、小组模型（线程平等工作）和管道模型（流水线方式）。,3,第四章 分布式系统中的处理机管理,派遣模型,派遣线程,工作线程,邮 箱,核 心,共享,cache,进 程,工作请求,工作请求,4,第四章 分布式系统中的处理机管理,小组模型,邮 箱,核 心,工作请求,进 程,共享,cache,工作请求,5,第四章 分布式系统中的处理机管理,管道模型,邮 箱,工作请求,核 心,进 程,共享,cache,工作请求,6,第四章 分布式系统中的处理机管理,动态模型,进程初启时只有一个线程，称为服务线程，向核心输入进程的接口。,核心准备调用数据借口，例如数据栈，供服务线程和客户线成共享。,客户线程初启后，从核心输入这些接口。,客户线程调用过程时，将参数入栈，将过程名存入指定寄存器，通过,trap,进入核心。,核心查看知道是本地调用，将客户线程内存映射到服务线程地址空间，启动服务进程，执行过程调用。,远程调用到来时，核心创建一个线程，将远程请求消息映射到它的地址空间，线程相应服务请求，执行过程调用，结束后自动消亡。,7,第四章 分布式系统中的处理机管理,2 负载平衡与系统模型,工作站模型,属于对称型模型，各结点是平等的。 负载平衡的要点之一是如何发现空载结点（潜在的计算服务器）。涉及三个问题：,如何发现空载结点,远程进程如何透明地运行,当本地进程需要运行时，如何处理,8,第四章 分布式系统中的处理机管理,服务器驱动,每个结点装备空载监测程序，监测自身。,设管理者，维护空载注册表，记录空载结点地址。,每个结点发现自己空载时，发消息给管理者，后者将其地址记入空载注册表。,A,结点需要分散计算负载，发远程命令询问管理者，后者给它发送空载结点地址,B，A,结点向,B,发送远程任务，,B,执行远程任务，负载增加，发消息要求管理者删去自己。,为避免几个结点同时发现某空载结点引起冲突，可引入二次确认：请求者向空载结点发送请求确认消息，空载结点选择其中一个结点为雇主，要求管理者从空载表中删去自己，向雇主发回确认消息。未接到确认的结点只好再次向管理者询问。,9,管理者,注册程序,空载注册表,请求者,空载结点,远程过程,远程过程,1. 空载注册,2. 请求空载结点,3. 回复空载结点,4. 要求确认,5. 注销空载,6. 确认,7. 设置运行环境,8. 启动远程进程,9. 进程运行,10. 进程结束,11. 返回结果,10,第四章 分布式系统中的处理机管理,客户驱动,结点需要分散负载时，广播请求，指明具体要求。,其他结点收到后，根据情况自行判断，同意者回复。,收到所有回复后，选取负载最小者，分散计算负载。,请求者,其他结点,其他结点,其他结点,其他结点,1,1,1,1,2,3,4,1,广播分散负载请求,2,3,4,应答：负载空,发送运行环境,11,第四章 分布式系统中的处理机管理,分散负载注意问题,远程进程的运行环境必须与本地环境一样,远程进程运行中的某些系统调用必须发回本地执行，如键盘、鼠标操作等人机交互工作,涉及时间处理要十分慎重，因为机器时间可能不同,空载结点本地进程要求运行时的策略,不理，等远程进程完成：简单但不友好,立即杀死远程进程，让位于本地进程：简单但造成计算浪费，有时会产生完整性问题（如文件），需要额外维护工作,先给警告，留一段善后处理时间，然后杀死远程进程,12,第四章 分布式系统中的处理机管理,注意：远程进程执行完成以后，接点必须恢复到空载时的状况。,包括：,清除所有远程进程及其子进程,清除这期间的邮箱内容、网络连接以及其它系统级数据,清除这期间的临时文件,清理,Cache,做好以后可能到来的与远程进程有关的消息的拒绝预防工作,13,第四章 分布式系统中的处理机管理,处理器池模型,单服务器基本排队模型,令用户产生请求,/秒，处理机能处理请求/秒，平均周转时间,T 1/(- ),如果服务器处理能力加大，有,n,个,CPU，,处理能力将为,n,，而请求率同步扩大为,n,，平均周转时间将为1/(,n,-n,) = T/n,原因：减少了,CPU,的空闲率,排队论的结论是反对分布式计算的重要论据，但分布式的潜在好处（代价、灵活、方便、坚固）也是不可替代的。,M,1,M,2,M,3,M,4,M,5,S,用 户,用 户,用 户,14,第四章 分布式系统中的处理机管理,分布式系统任务分配示意,假定：所有机器兼容，全连通。,优化目标：平均相应时间最小化，响应率最小化,响应率 = 进程实际运行时间/在无负载标准,CPU,上的运行时间,实际运行时间包括排队、调度、通信、计算的花费的时间,任务类型：可迁移任务，不可迁移任务,考虑： 任务间的通信开销（,ITC,）,问题,m,1,m,2,m,3,m,4,m,5,S,P,1,P,2,P,n,15,第四章 分布式系统中的处理机管理,基于图论的任务分配策略,通信图,图中：圆圈表示任务，旁边的数字表示计算工作量；连线表示有通信，连线的权（可以是,，显然两个任务不能异地计算）,表示开销。,假定同一个结点上的两个任务的通信量为零。任务优化的目标是处理开销和,ITC,之和最小。,A,B,C,D,5,12,8,6,3,6,3,9,16,第四章 分布式系统中的处理机管理,数据结构定义,分配矩阵,X,1,若任务,m,i,分配给处理机,P,k,x,ik,=,0,若任务,m,i,不在处理机,P,k,上,处理开销矩阵,Q,q,ik,表示任务,m,i,在处理机,P,k,上的处理开销，若为,，表示,m,i,不能在,P,k,上运行,ITC,开销矩阵,C,c,ij,表示任务,m,i,和,m,j,之间的,ITC,开销，若为0，表示两个任务在同一处理机上,于是，,ITC,总开销,T = q,ki,x,ik,+ c,ij,x,ik,x,jh,k,i,hk,ji,17,第四章 分布式系统中的处理机管理,其中，第一项是每个任务在其分配的处理机上的运行开销，第二项代表不同处理机上任务间的,ITC,开销。,以上图为例，任务,C,和,D,之间通信量为无穷大，显然应该分配在一个结点上。如有两个结点，那么分配将是,ITC,开销：,A B C D,处理开销：,A B C D,A 0,0 8 6,处理机1 3 9 6 3,B 0 0,12 0,处理机2 3 9 6 3,C 8 12 0,0,D 6 0 0 0,A，B,C，D,18,第四章 分布式系统中的处理机管理,显然，优化的方向是力求使得目标函数,X,最小。, 例： 一张完全图,利用最小分割算法得到分配结果为,P,1,：A，B，C，D，E； P,2,：F；,计算复杂性为,O(m,2,n,2,),P,1,P,2,A,F,C,B,E,D,6,12,4,11,5,8,12,3,5,4,10,2,4,6,5,4,4,3,分割线,8,15,19,第四章 分布式系统中的处理机管理,评论：,最小分割法以图论为基础，可以作为分配负载的一种方法。通过对目标函数求极小值的方法进行。,优点：简明,缺点：计算复杂性较大，只能处理2、3个处理机的情形,不能考虑处理机负载平衡问题以及由此带来的排队延迟、存储限制、实时（即时）要求等问题。,20,第四章 分布式系统中的处理机管理,0,1策略,指导思想：将任务分配概括为一个优化问题。,数据结构,分配矩阵,X,，,处理开销矩阵,Q,，,引入卷宗矩阵,V,，,v,ij,表示,m,i,向,m,j,发送的数据卷宗,引入距离矩阵,D，d,ij,表示处理机,P,i,与,P,j,的距离，代表互连状况（交通条件），为则表示不连通，于是,d,ij,v,ij,就是两个任务的,ITC,开销了。,目标函数,T = q,ki,x,ik,+ w,v,ij,d,ij,x,ik,x,jh,k,i,hk,j0,，,用随机方法在,P,j,上选取一个任务迁移到,P,j+1,上，否则不做任何动作。重复进行，直到所有的,D,j,都不大于0；必要时可对合一的任务进行分解。,若,D,m,大于0，失败！,25,第四章 分布式系统中的处理机管理,评论：,算法以追求次优解为目标，合一时采用“贪心”策略，不一定会实现最佳分配；,调整过程采用随机迁移，有盲目性；,成功的合一可以减少通信开销，成功的调整可使负载基本平衡，有利于提高系统吞吐量；,合一阶段计算复杂性,O(n,3,)，,调整阶段,O(m,2,) ，,可以忍受；,合一结束后，任务数目可能大于处理机数，需将多余任务分配给各处理机，甚至需要分解任务，这时寻找通信量最大的任务对工作量大；,在特殊情况，如存在附属任务（某个任务必须分给特定的一个或数,个处理机），合一时以附属任务为中心形成组合任务，先分配对处理机有特殊要求的组合任务，再分配包含其他附属任务的组合任务，最后分配不含附属任务的组合任务。调整阶段先排除负载平衡的处理机，在轻载和重载处理机之间进行调整。,26,第四章 分布式系统中的处理机管理,改进后的启发式算法, 数据结构定义,系统中有,n,个处理机，,m,个计算任务（,mn）。,任务间通信开销矩阵,C,m,m,：,C,m,m,= c,ij,| 1,im，1jm ，,为任务,t,i,，t,j,之间的通信开销,任务执行开销矩阵,Q,m,n,：,Q,m,n,= ,q,ij,| 1,im，1jn ，,为,t,i,在,P,j,上的运行开销,任务优先矩阵,A,m,n,：,a,ij,= 1,表示任务,t,i,不能分配给处理机,P,j,，,否则为0,任务互斥矩阵,E,m,m,：,e,ij,= 1 表示任务,t,i,与,t,j,不能分配给同一台处理机，否则为0,27,第四章 分布式系统中的处理机管理,任务分配矩阵,X,m,n,：,x,ij,= 1,表示任务,t,i,已经分配给处理机,P,j,，否则为0,处理机,P,k,上的负载：,L,k,= w,q,ik,x,ik,，,其中常数,w,用来调整执行开销与通信开销的量纲,某个任务与组合任务中的任一分任务互斥，即为与该组合任务互斥。,算法,将附属于同一处理机的任务合一，得到压缩后的矩阵,A,和,E,A,的行数为,m,，,E,的行列数均为,m,，记为,A,mn,和,E,mm,。同样，,Q,和,C,也变为,Q,mn,，,C,mm,，它们的元素值也会相应改变。,对,C,mm,的每一行进行排序，查找最大通信量的任务对,对处理机按现有负载建栈，栈顶为负载最轻的,P,k,。若栈非空，选,P,k,，否则转,。,i=1,m,28,第四章 分布式系统中的处理机管理,若所有任务已分配完，转,，否则，若,P,k,有附属任务，记该任务为,t,若,P,k,无附属任务，任选一个未分配任务为,t,。,寻找与,t,由最大通信量的未分配任务,t,j,，若加入后仍满足：,实时限制,R,k,，存储限制,S,k,；,a,ij,= 0,，即,t,j,可以分配到,P,k,上；,t,j,不与任何已分配到,P,k,上的任务互斥；,将,t,j,分配到,P,k,上。否则选下一个与,t,有最大通信量的未分配任务,t,j,，重复,。若无法找到这样的,t,j,，若可分配就将,t,分配给,P,k,。,若没有这样的任务,t,和,t,j,能分配给,P,k,，将,P,k,从栈中删去。否则修改,P,k,的负载，转,。,检查剩余任务，如有，设当前任务为,t,i,，其优先任务为,t,j,，若,t,j,已经分配给,P,k,，则从,P,k,中取出,t,j,，将,t,i,分配给,P,k,，并寻找可以接收,t,j,的处理机。若剩余任务不能分配给任何处理机，分配失败，退出。,29,第四章 分布式系统中的处理机管理,计算处理机,P,k,（,k=1,2,，,n,）的负载,L,k,并求出平均负载,L,，定义,r,k,= L,k,/L,。,若,1-d,r,k,1+d,，,P,k,为平衡；,若,r,k,1-d,，,P,k,为轻载；,若,r,k,1+d,，,P,k,为超载；,去掉分配给平衡处理机的任务，将轻载处理机上的任务合一为一个组合任务。以轻载、超载处理机上的任务集合为对象，转,重新建栈。若此次分配未引起负载变化，算法终止。,30,第四章 分布式系统中的处理机管理,基于遗传算法和模拟退火算法的任务分配算法,数据结构,建立一个五元组,=,（,T,，,，,Q,，,C,，,X,）,其中,T,为任务集合；“”为,T,上的优先关系，,t,i,t,j,表示,t,i,必须在,t,j,执行之前完成；,Q,为,m,m,矩阵，,q,ij,表示任务,t,i,在处理机,P,j,上的执行时间；,C,是一个,m,n,矩阵，,C,ij,表示任务,t,i,与任务,t,j,的通信开销；,X,是一个,m,n,的任务分配矩阵，,x,ij,=1,表示,t,i,分配到处理机,P,j,上，否则为,0,。,设计目标函数,cost,，例如,cost =,(q,ik,x,ik,+w,c,kr,x,ik,x,jr,),其中常数,w,用来调节量纲差异,i=1,k=1,m,n,r=1,j=1,K-1,i-1,31,第四章 分布式系统中的处理机管理,迭代过程,进行初始化，随机生成一个初始任务分配集合。例如：,处理机,任务,P,0,P,1,P,1,t,1,t,2,t,3,t,4,t,5,t,6,t,7,1,1,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,1,1,1,32,第四章 分布式系统中的处理机管理,描述与生成一个初始任务分配集合,TA,。,其中，特定的任务分配方案用（,S,，,R1.n,）表示。其中，,S,是一个,log,2,n,m,的二进制串，每个,log,2,n,位称为一节，自左到右的第,i,节就表示任务,t,i,所在的处理机号码。上例中，,S = 00 00 01 01 10 10 10,。,R,是一个有,n,个分量的链表数组，每个分量的类型为,m,元整数数组，自左向右表示任务执行的顺序。假定上例中的优先次序为,t,1,t,2,，,t,4,t,5,，,t,6,t,7,，这样,R,为：,R0,：,12,，,R1,：,34,，,R2,：,567,（或,675,，或,657,，因为只有,6,、,7,有次序关系）。,这样，,TA,1,.S = 00 00 01 01 10 10 10,；,TA,1,R =,（,12 34 567,）,TA,2,.S = 00 00 01 01 10 10 10; TA,2,.R =,（,12 34 675,）,TA,3,.S = 00 00 01 01 10 10 10; TA,3,.R,=,（,12 34 657,）,于是，可以选取若干分配方案，形成初始任务分配集合：,TA = S,，,R1.n ,33,第四章 分布式系统中的处理机管理,设置退火算法中的初始温度,temp,0,和收敛率,（,0, 1,），温度,temp,i+1,=,temp,i,，,逐步降低。这里，,i,既代表第,i,次迭代，也代表遗传算法中的地,i,代个体。,一般在任务量较大的情形，,temp,0,可以取,1000,，,temp,取为,1,，,取,0.9,，效果较好。,进行迭代循环。对初始任务分配集合中的方案采用交叉繁殖、变异等方法，形成新一代分配方案集合，不断进行。,交叉繁殖,对父代的两个分配方案中,S,的某些节进行替换，选取其中的优良者（,cost,较小）插入分配集合，形成第二代分配集合。,例,两个父代方案：,TA,1,.S = 00 00 01 01 10 10 10,；,TA,1,.R =,（,12 34 567,）,TA,2,.S = 01 01 01 00 10 00 10,；,TA,2,.R =,（,46 123 57,）,34,第四章 分布式系统中的处理机管理,用,TA,1,.S,中的,1,、,3,、,6,节替换,TA,2,.S,中的相应节，形成新方案：,TA,3,.S,=,00 01 01 00 10 10 10,；,TA,3,.R,=,（,14 23 567,）,计算,cost = cost(TA,3,) cost(TA,2,),：, 0,表示新方案优于原方案，将,TA,3,插入新的分配集合；,0,表示原方案优于新方案，计算概率值：,prob = exp |,cost/k,temp |,，式中,k,为波尔兹曼常数，,temp,为当前温度；,由系统产生（,0,，,1,）之间的随机数,rand,，若,prob,rand,，将新方案加入分配集合，反之舍弃。,变异,对某些方案作变异处理，形成新方案。如对,TA.S,某些节求反、互换处理任务等。变异不会造成个体数量的变化。每次变异后，对一个原方案只保留一种有效的变异方案。,通过这种方法，可以得到比较理想的分配方案。,35,第四章 分布式系统中的处理机管理,基于有向任务图的调度策略,假定：已知每个任务的执行时间，任务之间的时序关系、任务间的通信量、可使用计算机的数目；,分布式系统中有统一的时钟、结点同构（从而保证每个任务在不同计算机上的处理时间相同、通信开销固定）,；计算任务除通信以外的资源都可以从本机上获得。,步骤,生成非循环的任务有向图,G = V，E，e，c ,T,1,4,T,2,3,T,3,7,T,4,9,2,5,2,2,36,第四章 分布式系统中的处理机管理,上图中，,结点集合,V = T,1,，T,2,，T,3,，T,4,有向边集合,E = (T,1,T,2,)，(T,1,T,3,)，(T,2,T,4,)，(T,3,T,4,) ,运行开销集合,e = 4，3，7，9 ,通信开销集合,c = 2，5，2，2 ,任务复制,使任务在两个以上的计算机上有执行副本。,T,1,3,T,2,7,T,3,2,7,6,37,第四章 分布式系统中的处理机管理,上图中，三个任务在两个计算机上有三种分配方案（未复制）：,T,1,T,1,T,1,T,2,T,2,T,2,T,3,T,3,T,3,6,7,38,第四章 分布式系统中的处理机管理,第一种情况：总时间11,第二种情况：总时间17,第三种情况：总时间12（在一个计算机上）,如果进行任务复制：,T,1,T,1,T,3,T,2,总时间：10,任务复制将带来好处,39,第四章 分布式系统中的处理机管理,计算最早开始时间,贪心函数,f：,假定,C,是包含结点,v,以及它的父结点,1,，,2,，,3,，,k,的聚集。定义,f ( ,1,，,2,，,3,，,k, ),为全部完成 ,1,，,2,，,3,，,k,的最早可能结束时间。定义,s ( v ),为结点,v,的开始执行时间。显然：,s ( v ),f ( ,1,，,2,，,3,，,k,) = f ( C v ),考虑：,T,1,4,T,2,2,T,3,2,T,4,4,贪心函数,f ( C T,4, ) = 0 + 4 + 2 = 6,只有,T,1,，T,3,，T,4,分配在同一个计算机上才能达到：,8,6,8,40,第四章 分布式系统中的处理机管理,最大弦值函数,maxg：,非循环优先图中的边,(,u,w ),E，,定义弦值函数,g ( u,w ) = s ( u ) + e ( u ) + c ( u,w )；,这里,s (u),是结点,u,的最早开始时间，,e(u),是,u,的运行时间，,c ( u,w ),是,u，w,的通信开销。,最大弦值函数,macg(C),定义为由不属于,C,的节点到,C,中节点的最大弦值。,T,1,4,T,2,2,T,3,2,T,4,4,5,1,令,C = T,3,，,T,4,，,maxg,（,C,）,= 9,41,第四章 分布式系统中的处理机管理,在一个给定的分配方案里，节点,v,的最早开始时间,s,v,f（Cv）；,在上例中，,T,4,的最早开始时间为11。, 计算聚集的算法,令结点集合,G，,刚开始时，所有结点均未作标记。, 取,G,中未标记结点,v；, 若,v,未根结点，作标记后转 ；, 令,C,为空，,v,加入,C，,计算,s = maxg ( C )；, 选择具有最大弦值的(,u,w )，,其中,u,C，,且,u,为第一次被选择，,wC，C = C + u ，,若无转,；, 若,maxg 、f ( C-v ),均不大于,S，,则,S = max( maxg(C) , f( C v)），,否则,C = C u ，,转 ；,C = C u , 输出,C,和,v，,对,v,做标记，若,G,中为全部标记转 ，否则结束。,42,第四章 分布式系统中的处理机管理,评述：,总思路：对任一非根结点，计算其最大聚集弦值，找出满足该弦值得一对结点。尝试将聚集外的结点加入该聚集，看能否降低其最大弦值，若能则继续，否则去掉加入的结点，输出聚集。,例,T1,10,T3,5,T2,9,T4,5,T5,5,T6,6,14,12,6,4,3,起始，,C,中有,T,6,，这时,maxg(C) = 41,；,第一次循环结束，,C = T5,T6 , maxg(C) = 33,；,第二次循环开始，,u = T,4,，取,u = T,4,，,则,f ( C T4 ) = 27,，送入,s,；,加入,T4,，则,maxg(C),21,43,第四章 分布式系统中的处理机管理,该算法对每一个非根结点都会输出一个聚集，若某一聚集为另一个聚集的子集，则删去，最后得到若干相互没有包含的狙击。若聚集的数目不大于计算机的数目，为每一个聚集分配一个计算机，否则根据情况再进行调整。,在上例中，如果有两台计算机，那么分配方案：,T,2,T,4,T,5,T,6,T,1,T,3,若有三台计算机，分配方案改为：,T,2,T,4,T,1,T,3,T,5,T,6,44,第四章 分布式系统中的处理机管理,3.,调度问题,正常情况下，分布式系统中的各结点机有自己的本地调度程序，负责调度本机上的任务进程。,问题：,在需要进行远程通信时，各自计算机上的独立调度可能会影响系统的性能。,例,两个节点的系统，每个结点各有两个进程，结点,1,有进程,A,，,B,：结点,2,有进程,C,，,D,。两个结点各自采用分时方式调度方式调度，时间片为,100,ms,。,45,第四章 分布式系统中的处理机管理,时间片,处 理 机,0 1,0,1,2,3,4,5,A,C,B,D,C,A,C,A,B,D,D,B,在时间片,0,，,A,启动后立即向,D,发出远程调用，自己等待结果；但处理机,1,上,C,正在运行。到第二个时间片，,D,立即处理远程调用并返回结果，但此时,A,已经不在运行状态（,B,在运行）,由于通信与运行不同步，将导致处理机无谓等待。,46,第四章 分布式系统中的处理机管理,解决办法,1,：,处理机采用时间片轮转方法时，将进程按通信关系编组，尽可能将处于同一通信组的进程安排在相同时间片里运行。,问题：远程调用发生的时机是随机的，很难做到准确,。,解决办法,2,：,处理机调度采用分时和可抢占方法相结合。当一个远程调用到来时，被调用进程所在的处理机将当前运行进程挂起，调度相应进程运行；调用结束后再恢复原进程运行完剩余的时间片。处理远程调用不占进程的时间片。,好处：通信量较大的进程可以在运行时间上有所优待，以保证与其通信的它机进程正常运行。,缺点：进程间切换可能过于频繁，影响处理机的有效利用率。,47,第四章 分布式系统中的处理机管理,3,系统容错,1.,需要讨论的问题,设备故障的两种情况,fail and stop,Byzantine,容错的通常做法,冗余技术，包括信息冗余、时间冗余和物理设备的冗余。,信息冗余：增加效验码、镜像存放、多副本等,时间冗余：必要的重复执行，如原子事务技术等,物理冗余：增加设备，包括主动备份、被动备份,48,第四章 分布式系统中的处理机管理,2.,主动备份,对,fail and stop,类型故障比较有效,容错级别：,系统称为,K,级容错，是指,k,个部件出现故障，系统仍能正常工作，需要配备,K+1,套设施。,对服务器，设置,K+1,个，要求每个,Client,的请求按照相同的（服务器）次序执行并应答，称为原子广播。但在网络环境很难实现。,方法,1,：对远程请求实行全局编号，需要一台编号服务器实现编号与分发，集中式弊病。,方法,2,：使用逻辑时钟，请求加盖时间邮戳。但有麻烦：如何知道,还有没有更早的请求正在路上？,49,第四章 分布式系统中的处理机管理,2.,被动备份,指定一台设备为主设备，处理一切有关的事务，其它同类设备为备份设备。只有当主设备故障时，才由备份机接替工作。,正常情况下，运行策略简单：消息秩序相主服务器发送，不必向整个服务器群发送，次序问题基本上不存在。而且备份机也比较节省。,client,Primary,server,backup,server,发送请求,工作，完成请求任务,发送更新要求,工作，完成更新,确认，完成更新,返回结果,50,第四章 分布式系统中的处理机管理,在执行一个,RPC,过程中，服务器故障时刻分析：,在,以前，不会有影响，,client,发现响应超时重新请求，再三请求未果，确认服务器故障，转向备份服务器；,在,、,阶段，同上面情况，备份机接替工作，完成服务；,在,以后，,完成前，备份机接替工作。,系统运行过程中，备份机与主机不断通信，询问是否正常。,改进方法：主机与备份机共享磁盘，采用磁盘镜像或交换式磁盘两种方法。平时备份机不必进行,RPC,的计算工作，直到主机故障才接替工作。,显然，这种方法也不能解决,Byzantine,故障问题，适合,fail and stop,情况,51,第四章 分布式系统中的处理机管理,3.,分布式系统中故障点的确定,在,fail-stop,故障情形，比较简单：消息发出后久未回应，几次后即可认定故障。,在,Byzantine,故障情形，需要进行诊断以确定故障结点。,递归故障监测法：,假定3号机故障。,1,2,3,4,1,1,1,x,2,4,y,z,2,4,4,2,52,第四章 分布式系统中的处理机管理, 每个结点各自向其他结点发一条内容有规律的消息，例如自己的结点号（也可以是某个计算内容）。由于3号机故障，它的消息是杂乱无章的，例如，它给1号机发的是,x，,给2号机发的是,y，,给4号机发的是,z。,每个结点收到来自其他结点的消息后，将内容组成一个向量：,1号机： （1，2，,x，4）,2,号机： （1，2，,y，4）,3,号机： （1，2，3，4）,4号机： （1，2，,z，4）,53,第四章 分布式系统中的处理机管理, 各结点将生成的向量向其他结点发送，由于3号机故障，其向量也是混乱的。各结点收到的分别为：,1号机:（1，2，,y，4）,来自2号机； 2号机:（1，2，,x，4）,来自1号机;,（r，n，o，p）,来自3号机； （,n，a，b，q）,来自3号机；,（1，2，,z，4）,来自4号机； （1，2，,z，4）,来自4号机；,3号机:（1，2，,x，4）,来自1号机；4号机: （1，2，,x，4）,来自1号机;,（1，2，y，4）,来自2号机； （,1，2，y，4）,来自2号机；,（1，2，z，4）,来自4号机； （,d，e，w，i）,来自3号机；, 各结点独立对收到的向量进行比较，每一列多数内容相同的，认定该列号对应的结点正常，否则为故障机。,这样，就可以容易地判断出，3号机故障。,54,第四章 分布式系统中的处理机管理,评述：, 这种方法对系统中正常机与故障机的比例有限制，如果系统中有,n,个故障机，则正常机的数量不得小于,n+2,个。否则将无法做出正确的判断。,例如，三个结点中有一个故障。,假定2号机故障。,1号机收到: （,r，n，q）,来自2号机,（1，,y，3）,来自3号机,2号机收到: （1，,x，3）,来自1号机,（1，,y，3）,来自3号机,3号机收到: （1，,x，3）,来自1号机,（,s，t，w）,来自2号机,1,2,3,1,1,3,3,x,y,将无法判断故障位置！,55,第四章 分布式系统中的处理机管理, 这种方法只有在同步通信、通信延迟有限的情况下才适用。,56,