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