第4章-互斥和选举算法

第4章互斥和选举算法2008.3《分布式系统》(四)08-032互斥（Exclusion）问题互斥保证了相互冲突的并发进程可以共享资源，即通过定义基本的操作来解决多个并发进程访问共享资源（进入临界区）时的冲突问题。集中式系统实现互斥控制相对简单。Dekker和Dijkstra引入了信号量，通过P、V操作以软件方法实现互斥。硬件原子指令如：TestandSet、CompareandSwap和FentchandAdd也可以较好地实现互斥。《分布式系统》(四)08-033分布式互斥分布式系统也可以简单地通过一个公共的协调者（管理信号量）来实现互斥（协调者接受带时戳的请求，发放许可），但是由于协调者是个瓶颈，它的性能和可靠性很难像集中式系统那样得到保障。分布式互斥：基于权标（Token）：不同进程共享唯一（或k个）的权标，拥有权标的进程就可以访问临界区；非基于权标：不同进程通过消息交换，协商出一个（或k个）可以访问临界区的进程。《分布式系统》(四)08-034互斥算法互斥（及其算法）的主要目标是保证在一个时刻只能有一个（或不多于设定的k个）进程访问临界区。一个正常的互斥算法必须满足：不死锁：当临界区可用时，进程不应该无限等待而没有一个进程可以进入。无饥饿现象：每个对临界区的请求最后都必须得到满足（不会被无限延迟）。公平性：对临界区的请求必须基于一定的公平原则（如由逻辑时钟确定的请求时间）予以批准。《分布式系统》(四)08-035互斥算法互斥算法的性能参数：1)每个请求的消息数。2)同步延迟一个进程离开临界区到下一个进程进入该临界区之间的时间。3)反应时间一个进程发出请求到该进程离开该临界区之间的时间。衡量一个互斥算法的性能主要是前2个参数，第3个参数更多地取决于系统的负载和/或进程进入临界区的时间长短。然而，互斥算法的性能与系统负载很多情况下是有很大关系的。《分布式系统》(四)08-036分布式互斥算法的假设进程间通过消息传递进行通信。网络在逻辑上是全连接的。传输是可靠的。通信是异步的。即：传输延迟不可预测，但是有限的。消息是可以按照发送的顺序递交（FIFO）。《分布式系统》(四)08-037非基于权标的分布式互斥所有进程相互通信来决定哪个进程可以访问临界区，决策是以分散的方式形成。介绍：Lamport算法Ricart和Agrawala算法（非权标）Maekawa算法《分布式系统》(四)08-038Lamport算法通过带时戳的请求、应答和释放消息的交换来确定优先访问临界区的进程；一个进程只有收到所有进程的应答（或释放）且没有收到更高优先级（时戳更小）的请求才能访问临界区；进程离开临界区，需发送释放消息给所有的其它进程；需要3(n-1)个消息来实现。P1P2P3CSCS*《分布式系统》(四)08-039改进的Lamport算法进程Pj在发出它自己的请求后收到一个来自进程Pi的请求，而它的请求的时戳大于Pi的请求；此时，进程Pj没有必要发送进程Pi的应答，因为当进程Pi收到进程Pj的请求时，它发现Pj的请求的时戳大于自己的请求时戳，于是它就知道Pj没有任何时戳更小的未决请求；改进的Lamport算法可以减少传递的消息数，但最坏的情况仍然需要3(n-1)个消息。（Lamport算法还可以作更多的改进！）P1P2P3CSCS*《分布式系统》(四)08-0310Ricart和Agrawala算法（非权标）在Lamport算法的基础上去掉释放消息，或者说将释放消息合并到应答消息中，变成一个许可消息；一个进程只有收到所有进程的许可后才能访问临界区；P1P2P3CSCS*《分布式系统》(四)08-0311Ricart和Agrawala算法（非权标）具体算法：当进程Pj收到来自进程Pi的请求时，如果Pj既不请求临界区也不执行临界区，或者它正请求临界区而且它的请求的时戳大于Pi的请求的时戳，那么进程Pj给Pi发回一个许可消息；进程释放临界区时，发送许可消息给所有被延迟的请求。P1P2P3CSCS*《分布式系统》(四)08-0312Ricart和Agrawala算法（非权标）算法分析：一个进程可以同时给许多进程授予许可，但同时只有一个进程可以得到所有进程的许可，因为请求时戳小的高优先级的未决进程不会给请求时戳大的低优先级的进程发送许可，这些低优先级的请求被延迟（缓冲），只有高优先级的进程在执行临界区后、释放时，才发送许可消息给这些被延迟的请求。需要2(n-1)个消息来实现。P1P2P3CSCS*《分布式系统》(四)08-0313Maekawa算法Maekawa算法是Ricart和Agrawala算法的扩展；进程根据一定优先级原则（如请求的到达时间顺序：由于延迟是有限的，不会发生饥饿现象），一次只给一个请求进程授予许可；进程不用请求所有进程的许可，只需请求一个进程子集的许可（请求子集）；为了实现互斥，任何两个请求子集的交集必须非空，确保同一时刻只有一个进程能得到请求子集里全部进程的许可。（这个非空的交集也是这两个进程的仲裁者）《分布式系统》(四)08-0314Maekawa算法具体算法：假设进程Pi和进程Pj的请求子集分别是Ri和Rj，且RiRj；当进程Pi请求临界区时，它只给Ri中的进程发送请求消息；当进程Pj收到一个请求消息时，若它自从上一次释放临界区后还没有发出过回答消息给任何进程，它就发出一个回答消息，否则请求消息被放入队列中；进程Pi只有在收到Ri中的所有进程的回答消息后才能访问临界区；释放临界区，进程Pi只给Ri中的进程发送释放消息。《分布式系统》(四)08-0315Maekawa算法一个7个进程的例子：P1－R1：{P1，P3，P4}P2－R2：{P2，P4，P5}P3－R3：{P3，P5，P6}P4－R4：{P4，P6，P7}P5－R5：{P5，P7，P1}P6－R6：{P6，P1，P2}P7－R7：{P7，P2，P3}Maekawa算法容易死锁，如例中：由于不同的通信延迟，P4可能给P1回答、P2给P6、P3给P7，则P1、P6、P7没有一个能执行临界区，也就都不能释放P4、P2、P3，于是发生死锁。避免死锁的2个办法：1、低优先级（时戳大）的请求的进程放弃请求；2、确保优先回答高优先级的请求。*《分布式系统》(四)08-0316Maekawa算法算法分析：如果每个请求子集的大小一样，均为k，进程数为n，则n的最小值n=k(k-1)+1，因此每次发出的访问请求消息数是k=O(n)；2个极端的情况：所有Ri中的进程是唯一的固定进程Pc，即：Ri：{Pc}，1in这是集中式互斥中的信号量方案；所有Ri中的进程是全部进程，即：Ri：{P1，P2……Pn}，1in这是Ricart和Agrawala算法；《分布式系统》(四)08-0317基于权标的分布式互斥权标（Token）是一个动态控制点，它在所有的进程间传递，一个进程拥有权标时就可以进入临界区。介绍：Carvalho和Roucariol算法（基于权标的Ricart和Agrawala算法）权标环算法《分布式系统》(四)08-0318Carvalho和Roucariol算法初始的Carvalho和Roucariol算法是Ricart和Agrawala算法的改进，即：进程Pi收到进程Pj的许可后，可以一直保留这个许可（以后不需每次再向Pj请求），直到收到来自进程Pj的请求，这个改进可以有效地减少消息数，使消息数在0到2(n-1)之间；完全的Carvalho和Roucariol算法引入了一个完整的权标。《分布式系统》(四)08-0319Carvalho和Roucariol算法进入临界区的进程保留权标；初始时，唯一的权标被赋予任意一个进程；希望访问临界区的进程Pj向所有其它进程广播一个带时戳的消息来请求权标；如果当前拥有权标的进程Pi不再需要使用临界区，它就按照i+1,i+2,…,n,1,2,…,i-1的逻辑环形顺序搜索其它进程，找出第一个j，满足Pj最后一次请求权标的时戳大于在权标中记录的Pj最后一次拥有权标的时戳（即Pj有未决请求），于是Pi把权标传递给Pj。123i-1ii+1权标拥有请求传递权标j《分布式系统》(四)08-0320Carvalho和Roucariol算法算法分析：权标的唯一性确保互斥；没有严格意义的时戳优先级，但权标的单向环绕传递确保无饥饿现象；权标的环绕传递也确保了公平性；当请求进程没有持有权标时，算法需要n个消息（n-1个用于广播，1个用于传递权标）；当请求进程持有权标时，算法需要0个消息；《分布式系统》(四)08-0321Carvalho和Roucariol算法算法的DCDL形式描述：主程序：P(i)::=*[request-resourceconsumerelease-resourcetreat-request-messageothers]distributed-mutual-exclusion::=||P(i:1…n)《分布式系统》(四)08-0322Carvalho和Roucariol算法以下变量用于每个Pi中：clock:0,1,…（Lamport时戳，初始化为0）token_present:Boolean（持有权标标志，初始化只有一个进程为T）token_held:Boolean（使用权标标志，初始化为F）token:array(1…n)ofclock（最后持有权标时的时戳，初始化为全0）request:array(1…n)ofclock（请求权标时的时戳，初始化为全0）其中：clock,token_present,token_held在每个局部有一个拷贝，token,request全局只有一个拷贝。《分布式系统》(四)08-0323Carvalho和Roucariol算法每个Pi中的函数定义：others::=alltheotheractionsthatdonotrequestconsume::=consumestheresourceafterenteringthecriticalsectionrequest-resource::=[token_present=F[send(request_signal,clock,i)toall;receive(access_signal,token);token_present:=T]token_held:=T]*《分布式系统》(四)08-0324Carvalho和Roucariol算法release-resource::=[token(i):=clock;token_held:=F;minjintheorder[i+1,…,n,1,2,…,i-2,i-1](request(j)token(i))[token_present:=F;send(access_signal,token)toPj]]《分布式系统》(四)08-0325Carvalho和Roucariol算法treat-request-message::=[receive(request_signal,k,j)[request(j):=max(request(j),k);token_presenttoken_heldrelease-resource]]注：为了避免在拥有权标，而没有使用前就释放，将request-resource函数中的token_present:=T;token_held:=T合为一个原子语句或将token_held:=T置前。为保证更强的公平性，优先级还可以根据请求的时戳进行。(?)《分布式系统》(四)08-0326权标环算法若进程Pi，1in，在物理上连成一个环，那么存在一个简单的权标环算法；同样引入权标，该权标环绕传递。(i-1)modni(i+1)modn权标《分布式系统》(四)08-0327权标环算法算法的DCDL形式描述：P(i:0…n-1)::=