我要投搞

标签云

收藏小站

爱尚经典语录、名言、句子、散文、日志、唯美图片

当前位置:白小姐 > 分布式算法 >

分布式系统中进程互斥算法的研究

归档日期:06-11       文本归类:分布式算法      文章编辑:爱尚语录

  在单机操作系统中,临界区、互斥以及其他有关同步问题,通常是用信号量和P*V操作、管程来解决。而在分布式系统当中,各个进程被认为是运行在不同的处理机上,为了防止出现以下情况:多个进程同时处于临界区;临界区外的进程阻塞其他的进程;有些进程在临界区外无休止的等待等等,多处理机系统的互斥不能简单地用单机的方法来实现,而是要用更为方便和高效的手段来实现多处理机系统的互斥。

  解决进程互斥问题有软件的方法和硬件的方法,本文重点介绍软件方法,硬件方法从略。

  二、经典互斥算法的探讨(一)集中式算法算法:选择一个进程作为协调器,用于协调临界区得进入。

  特点:协调器在同一时间只允许一个进程进入临界区,故能保证互斥;因为请求消息是顺序排队得,不会出现“饿死”现象;单一的协调器是瓶颈。

  (二)分布式算法算法:想进入临界区的进程首先建立一个消息,该消息包括待进入的临界区名、进程名和时间戳。一个进程收到消息后,会有如下操作:不在临界区内且不想进入的话回复一个消息;在临界区内的话不回消息,将请求放入队列;不在临界区,也想进入的话就比较时间戳,时间戳小的进入。

  特点:算法复杂,易出现“饿死”现象,系统不健壮;但它从理论上表明了算法的可行性,必将发展出实际可行的算法。

  1、Lamport算法。特点:Lamport算法统一定序所有对临界段的请求,按先来先服务的原则让请求临界资源的进程进入其临界段;进程Pi发送的请求消息形如request(Ti,i),其中Ti=Ci是进程Pi发送此消息时对应的逻辑时钟值,i代表消息内容;每个进程保持一个请求队列,队列中的请求消息根据?准关系定序,队列初始为空。

  2、Ricart and Agrawala算法。特点:算法实现了进程互斥,其控制是全分布的。因为进入临界区是根据时间戳的顺序来安排的(即先来先服务方式),所以根本不可能有进程“饥饿”现象发生。死锁也不可能发生,因为不存在环路等待。问题:其一,当有一个进程请求进入临界段时,所有其他进程都被牵连到。这就是说,每个进程都要知道其他进程的名字,当有新进程出现时,必须把新进程名字通知其他各进程,同时新进程要获知全部其他进程名。其二,如果某一进程故障,那么该算法因无法收到全部应答消息而崩溃。其三,没能进入临界区的进程只能频繁地暂停,因而只适用于小的进程集。

  (三)令牌环算法算法思想:整个系统只有一块令牌,只有令牌持有者才具有进入临界区的资格。当进程i从进程i-1接到令牌时,它检查是否想进入临界区,如果是,则进入,待其推出后,将令牌传递给进程i+1;如果不想进入,则直接把令牌向下传递。

  问题:一是令牌丢失,事实上,检测令牌丢失是很困难的。二是进程故障,较容易恢复。

  三、算法的改进(基于令牌的解决方案)将令牌的概念引入到分布式的Ricart和Agrawala算法中,通过令牌即动态的单一点控制,使用对称的不同定义,这个算法要求的消息数在0到2(n-1)之间。在这个算法中,进程Pi收到来自Pj的回答消息后可以进入临界区(假设它得到所有其他进程的回答消息)任意次而无需再请求Pj的许可。因为当进程Pi收到Pj的回答消息时,隐含在该消息中的授权保持有效直到Pi收到来自Pj的请求消息。

  算法思想:进入临界区的进程保留令牌。初始时,令牌被赋予任意一个进程。希望使用临界区的进程Pj不知道哪个进程拥有令牌,所以它通过向所有其他进程广播一个带时戳的消息来请求令牌。如果当前拥有令牌的进程Pi不再需要使用临界区,它就按照i+1,i+2,n,1,2,i-1的顺序搜索其他进程,找出第一个j,满足Pj最后一次请求令牌的时戳大于在令牌中记录的Pj最后一次拥有令牌的时戳,也就是说,Pj有一个未决的请求。于是,Pi把令牌传递给Pj。注意,优先级不是严格基于每个请求的时戳的,但是,由于令牌是沿着一个方向环绕传递的,所以不会有饥饿现象发生。算法:

  四、以上各种算法的性能分析Lamport的算法需要3(n-1)个消息和两个时间单位的延迟来保证n个进程的互斥,消息量很大,且发送的应答信号的目的并不是出于可靠性。

  Ricart和Agrawala算法在消息量上有了一定的改进,需要2(n-1)个消息来保证。

  改进后的算法即基于令牌的Ricart和Agrawala算法:当请求进程没有持有令牌时,以上算法需要n个消息(n-1个用于广播请求,1个用于传送令牌);当请求进程持有令牌时,以上算法需要0个消息。

  五、结论集中式算法比较健壮,不会出现“饿死”现象,但是单一的协调器是系统瓶颈。

  分布式算法虽然没有前一算法健壮,但是从理论角度论证了分布式算法的可行性。

  基于令牌的算法比非基于令牌的算法的时间复杂性和消息复杂性小。不会发生饥饿现象,不需要关心当前谁在临界区中,是通过竞争的方式进入临界区。这在基于令牌的Ricart和Agrawala算法中得以验证。

  综上所述,基于令牌的算法在排除了令牌丢失和进程故障等问题之后,在今后的分布式系统中,能有更好的应用。

本文链接:http://frankstella.net/fenbushisuanfa/468.html