第6章互斥问题及选举算法.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,Lamport,时钟练习,假设系统中只存在消息发送和接收事件，如图所示，请给出事件,a-g,的逻辑时钟。,A,B,C,逻辑时钟,0,a3,b4,c7,d5,e7,f5,g9,a,b,c,d,e,f,g,的时间分别为,3,4,7,5,7,5,9,不同进程产生的消息可能具有相同数值的,Lamport,时间戳。,分布式系统中的互斥,本章主要内容,分布式系统互斥目标,分布式系统互斥基本类型,分布式系统互斥算法类型,分布式系统互斥算法的实现,临界区的调度原则,临界资源：一次只允许一个进程访问的共享资源。,临界区：每个进程中访问临界资源的一段程序代码。,进程进入临界区的调度原则：,如果有若干进程要求进入空闲的临界区，一次仅允许一个进程进入。,任何时候，处于临界区内的进程不可多于一个。如已有进程进入自己的临界区，则其它所有试图进入临界区的进程必须等待。,进入临界区的进程要在有限时间内退出，以便其它进程能及时进入自己的临界区。,互斥算法的目标,互斥的主要目标是保证在一个时刻只能有一个进程访问临界区。,在非基于令牌的算法中，所有进程相互通信来决定哪个进程可以执行临界区。,在基于令牌的算法中引入了令牌的概念。令牌代表了一个控制点，它在所有的进程间传递。一个进程拥有令牌时就可以进入临界区。,分布式系统中的互斥算法,在分布式系统中，经常出现多个进程请求访问同一个临界资源的问题，为了协调访问，保证访问的正确性（无死锁，无饥饿现象），需要给出一种有效的互斥算法。,互斥是分布式系统设计的关键问题。,为了保证数据一致性、逻辑一致性及时序一致性，分布式互斥算法必须具有公平、健壮和易于实现的特点。,互斥算法的控制机制,互斥算法的分类,基于令牌的算法：通过令牌拥有权来控制对共享资源的访问。,非基于令牌的算法：通过进程之间的消息交换来协商对共享资源的访问。,互斥算法的适应性,静态互斥算法：算法的行为独立于系统的状态,动态互斥算法：算法的行为依赖于系统的状态,互斥算法应满足的条件,无死锁：当资源可用时进程不应该永远等待,无饥饿现象：每个对资源的访问请求最终都应能得到满足,公平性：进程对资源访问权的获得应是相对公平的。,衡量互斥算法性能的参数,每个请求的,消息数,同步延迟,：一个进程离开临界区到下一个进程进入该临界区的时间间隔，对共享资源的有效访问间隔。,反应时间,：进程发出访问请求到执行完访问操作的时间间隔，主要依赖于系统的负载和调度的合理性。,Lamport,互斥算法,为了请求资源，进程,P,i,发送带时标的消息,r,给系统中的所有进程，包括它自己；,任意进程,P,j,收到请求资源的消息时，将该消息按时标顺序放在自己的局部请求队列中并发回一个带时戳的应答；,进程,P,i,获得资源访问权的条件是,它已收到从其它所有进程发来的应答,它的请求,r,在它的请求队列的顶部,它从所有其它进程处收到的消息的时标均比,r,的时戳大；,为了释放资源，进程,P,i,发送一个带时戳的消息给所有的进程，包括它自己；,任意进程,P,j,收到来自,P,i,的资源释放消息时，要从自己的局部请求队列中清除所有来自,P,i,的请求。,一个例子,改进的,Lamport,互斥算法,（,1,）当进程,P,i,需要占用公区时，向所有进程发送请求，对于,K-,互斥问题，请求消息包括公区号、进程号和时间戳。,接收进程,P,j,收到请求消息后，执行如下操作：,如果,P,j,没有占用该公区也没有申请使用它，则向请求进程发送一个确认消息。,如果,P,j,正在使用该公区，则不发送确认消息，暂存请求消息。,如果,P,j,正在申请使用该公区，则比较请求消息时间戳与本身请求时间戳的大小，时间戳小者优先。若,P,i,的时间戳小，则,P,j,发送一个确认消息，若,P,j,的时间戳小，则,P,i,不发送确认消息。（,2,）当进程,P,i,收到所有其他进程发来的响应时，便可访问该资源。（,3,）当进程释放该资源后，向所有被暂存的请求发送一个确认消息并删除暂存队列。,Ricart,和,Agrawala,互斥算法,Ricart,和,Agrawala,互斥算法,要求分布式系统的所有事件是全序的，进程按请求的顺序获得对公区的访问。,进程若未收到所有的应答，就表明有优先级更高的请求存在。,交换的消息数量降至,2(n-1),个,t,11,t,12,Ricart,和,Agrawala,互斥算法的特点,能够实现诸进程对共享资源的互斥访问。,能够保证不发生死锁，因为在进程,-,资源图中，不会出现环路。,不会出现饥饿现象，因为对共享资源的访问是按照邮戳时间排序的，即按照,FCFS,原则服务的。,每次对共享资源访问时，只要求发,2(N-1),个消息。,Ricart,和,Agrawala,算法的缺陷,由于不应答被认为是资源被占用，所以如果有某个节点故障，会导致该算法的异常终止。,各进程对资源的使用情况缺乏了解。,Maekawa,算法,基本思想,将进程分成多个请求子集，要求这些集合两两相交。,进程,P,i,只要得到所属集合中所有进程的应答后可访问共享资源。,Maekawa,算法,将,n,个进程分成多个子集，子集长度,k,与进程个数的关系为,n=k(k-1)+1,进程,P,i,在请求访问资源时，向自己的请求子集,R,i,发出请求消息,R,i,中的进程,P,j,在收到请求后，执行如下操作：,如果,P,j,记录的资源状态为可用，向,P,i,返回一个应答,如果,P,j,记录的资源状态为占有，则将这个请求放入自己的请求队列,(,时标取请求到达的时间,),。,P,i,只有在得到,R,i,中所有进程的应答后才能访问资源,P,i,在访问结束后要向,R,i,中的所有进程发送释放消息。,R,i,中的进程在收到释放消息后，如果自己的请求队列为空，则将资源状态改为可用，否则从队列中选择一个请求发送应答。,Maekawa,算法的实现,Maekawa,算法缺陷,容易导致死锁,:,假设,P1,P6,P7,同时申请临界区,ACK,P1,P7,P2,P6,P3,P4,ACK,ACK,REQ,REQ,REQ,作业,13,个进程共享一个资源，用,Maekawa,算法来支持互斥，请划分进程请求子集,基于令牌的互斥算法,在基于令牌的互斥算法中，互斥是通过在进程之间传递一个特殊的消息来实现的。这个消息即是令牌。,令牌代表了一个控制点，它在所有的进程间传递。,一个进程当且仅当拥有令牌时就可以进入临界区。,当令牌被传递到某一个进程时，如果这个进程不需要访问临界区，则把令牌传递给下一个进程，否则在访问完临界区才将令牌传递到下一个进程。,基于令牌的互斥算法,R i c a r t,和,A g r a w a l a,提出了进一步改进：进入临界区的进程保留令牌。,初始时，令牌被赋予任意一个进程,Pi,。,进程,Pj,通过向其他进程广播一个带时戳的消息来请求令牌。,如果当前拥有令牌的进程,Pi,不再需要使用临界区，它就按照,i,1,i,2,n,1,2,i,1,的顺序搜索其他进程,找出第一个进程,Pj,，满足条件：,Pj,最后一次请求令牌的时戳大于在令牌中记录的,Pj,最后一次拥有令牌的时戳。,当满足以上条件时，,Pi,把令牌传递给,Pj,。,Ricart-Agrawala,令牌互斥算法,Ricart,和,Agrawala,的第二个算法,算法描述,P(i,):=*,请求资源,消费,释放资源,处理,-,请求,-,消息,其他,Ricart,和,Agrawala,的第二个算法,需要的变量,Clock:0,1,（初始化为,0,）,token_present:Boolean,(,除了一个进程，对其他进程均为,F),token_held:Boolean,(,令牌为当前进程拥有，初始为,F),token:array(1.n)of clock(,最后用完时间,),request:array(1.n)of clock(,最后申请时间,),每个进程有一个局部,clock,token_present,和,token_held,Ricart,和,Agrawala,的第二个算法,P,i,中的函数定义：,其他,:=,所有其他不请求进入临界区的动作,消费,:=,进入临界区后消费资源,请求资源,:=,token_present,=,Tsend(request_signal,clock,i,)to all;,receive(access_signal,token,);,token_present,:=T;,token_held,:=T,释放资源,:=,token(i,):=clock;,token_held,:=F;,min j in the order i+1,n,1,2,i-2,i-1(,request(j,),token(j,),token_present,:=F;,send(access_signal,token,)to,P,j,Ricart,和,Agrawala,的第二个算法,处理,-,请求,-,消息,:=,receive(request_ signal,k,j),request(j,):=,max(request(j),k,);,token_presenttoken_held,释放资源,存在问题,当请求进程没有持有令牌时，以上算法需要,n,个消息（,n,1,个用于广播请求，,1,个用于传送令牌）。,当请求进程持有令牌时，以上算法需要,0,个消息。,存在问题：,请求资源可能在,token_present,:=T,之后而在,token _held:,T,之前被处理,-,请求,-,消息所中断。这种情况下，被中断的进程将不得不释放刚刚收到的令牌。,解决问题的方法：,让这两个语句合并为一个原子语句，也就是说，这两个语句作为一个语句来对待。,把,token_held,:=T,放在,token_present,:=T,之前。,基于令牌环的简单算法,如果进程,Pi,(i,=1n),连接成一个环，该令牌绕环传递。,在简单令牌环算法中，进程有序构成一个逻辑环，令牌有序绕环前进，使得每个进程都能拥有令牌。,基于令牌环的简单算法,图,2,基于令牌环的算法,Pi(1.n):,receive token from,P(i,1)mod n,）；,如果需要消费资源,;,send token to,P(i,1)mod n,）,分布式,-,互斥,:,|,P(i,：,1.n),基于令牌环的简单算法,适合高负荷的环境，低负荷环境造成令牌的低效移动，浪费系统资源。,令牌在移动过程中可能会丢失。,基于令牌环的容错算法,(,双令牌互斥算法,),动态单一控制点算法（,dynamic single,contrl,point algorithm,）有可能丢失控制点,(,令牌,),。,容错算法使用两个令牌（,A,和,B,）,其中一个令牌负责检测另一个令牌可能的丢失。其中的一个令牌用来控制访问共享资源。,两个令牌按照相反方向沿着环访问进程。,在该算法中，如果某一个进程被同一个令牌连续两次访问，则令牌的丢失被检测到。,算法基本思想,双令牌互斥算法使用两个令牌,(A,B),，每个令牌各自带有一个变量,(NA,NB),。,NA,：保存连续访问,Mi,值为,1,的进程的个数,NB,：保存连续访问,Mi,值为,-1,的进程的个数,Mi,：指定某个进程是否为,A,令牌或,B,令牌访问，如果为正值，则被,A,令牌访问，如果为负值，则被,B,令牌访问。访问次数由具体的数值决定。,假设环中有,n,个进程,(P1,到,Pn,),，每个进程带有一个变量,Mi(1in),。,当两个令牌相遇时，更新,NA,NB,。,基本步骤：,(1),算法开始时：,NA:=1,NB:=-1;Mi=0(1in),双令牌算法示意图,P1,P6,P3,P4,P5,P2,A,令牌,B,令牌,双令牌互斥算法,算法基本思想,(2),当进程,Pi,接收到令牌,A,时,If Mi=NA,Then,令牌,B,丢失：令牌,A,在没有改变,NA,的情况下绕令牌环网转了一周，也同时表示在令牌,B,这段时间内没有访问过,Pi,重构令牌,B,；,Else,令牌,B,无丢失,Mi=NA;,算法基本思想,(3),当两个令牌相遇时：,NA:=NA+1;NB:=NB-1,(4),当进程,Pi,重构令牌,B,时：,NA:=NA+1;NB:=-NA;,(,这个时候进程,Pi,持有两个令牌,),双令牌互斥算法性能分析,该算法同简单令牌环算法一样，可以避免死锁和无饥饿现象。,基于该算法可以实现,K,令牌互斥算法。,如果某一进程连续被同一个令牌访问，则可以判断其中一个令牌丢失，执行重构令牌的操作。,双令牌互斥算法的,DCDL,描述,图,3,基于令牌环的容错算法,基于令牌的树结构的互斥算法,在基于树的算法中，进程被排为一棵有向树，根节点持有令牌。,对令牌的请求沿着从请求者到根节点的路径向上传递。,令牌从根节点传向请求者并经过从根节点到请求者的路径上的边。,与此同时，沿该路径的边的方向被反过来，于是请求者成了新的根节点。,图,4a,表示一个从叶节点到根节点的请求。图,4b,表示根节点把令牌传给叶节点（新的根节点）后的相应结果。,新树中的每个节点仍然可以沿着一条有向路径把它的请求发给持有令牌的节点。,图,4,基于树的互斥算法,选举算法,