精华内容
下载资源
问答
  • 分布式系统进程互斥算法的研究与改进
  • 2.13 互斥 要求 空闲让进:若空闲,申请即进 忙则等待:只允许临界区存在一个进程,若忙碌,区外等待 有限等待:进程等待的时间是有限的,不会造成死锁、饥饿 让权等待:进程不能在临界区长时间阻塞等待某事件 以上...

    2.13 互斥

    要求
    • 空闲让进:若空闲,申请即进
    • 忙则等待:只允许临界区存在一个进程,若忙碌,区外等待
    • 有限等待:进程等待的时间是有限的,不会造成死锁、饥饿
    • 让权等待:进程不能在临界区长时间阻塞等待某事件
    • 以上类比生活中任何公共资源都可,如公用电话

    2.13.1 互斥:软件方法

    思路
    1. 在进入区设置标志来判断是否有进程在临界区
    2. 若临界区已有进程,则循环等待
    3. 进程离开临界区后在退出区修改标志
    第一代:轮换使用临界区

    每个进入临界区的进程的权限只能被另一个进程赋予

    int turn=0;
    
    //进程P0
    do{
    	while(turn!=0);//进入区
    	P0代码;//退出区
    	turn=1//退出区
    }while(true)
    
    //进程P1
    do{
    	while(turn!=1)//进入区
    	P1代码;//临界区
    	turn=0;//退出区
    }while(true)
    

    严格轮换,实现了互斥访问
    违反了空闲让进的原则:比如turn=1时,临界区空,但P1无法进入

    第二代:设置临界区状态标志

    进入之前看有没有其他进程要进入,没有则将自己的状态置为true

    boolean flag[2]={false,false}//该全局变量标志临界区空闲与否
    
    //进程P0
    do{
    	while(flag[1]);//进入区
    	flag[0]=true;//进入区
    	P0代码;//临界区
    	flag[0]=false;//退出区
    }while(true)
    
    //进程P1
    do{
    	while(flag[0]);//进入区
    	flag[1]=true;//进入区
    	P1代码;//临界区
    	flag[1]=false;//退出区
    }while(true)
    	
    

    违反了忙则等待原则:假设CPU先将时间片分给P0,然后P0判断flag[1]=false跳出循环向下执行,这时CPU又将时间片分给 P1,P0尚未执行到置flag[0]=true;P1判断flag[0]=false跳出循环向下执行,两者都将进入临界区
    注意:while(flag[1]);这一句表明:当flag[1]=true时停在这一句,flag[1]=false时跳出循环执行下一句,P0即进入临界区

    第三代:表明使用临界区的状态

    先亮明状态,再循环等待

    boolean flag[2] = {false, false};//共享的全局变量
    
    //进程P0
    do {
        flag[0] = true;    //进入区
        while (flag[1]) ;//进入区
        进程P0的临界区代码; //临界区
        flag[0] = false;   //退出区
        进程P0的其它代码     //剩余区
    } while (true)
    
    //进程P1
    do {
        flag[1] = true;    //进入区
        while (flag[0]) ;//进入区
        进程P1的临界区代码; //临界区
        flag[1] = false;   //退出区
        进程P1的其它代码     //剩余区
    } while (true)
    

    违反了空闲让进原则:CPU先将时间片分给P0,然后P0置flag[0]=true,这时CPU又将时间片分给 P1,P1置flag[1]=true;那么接下来两者都在while循环处等待对方清零,都无法进入临界区,形成死锁

    第四代:表明使用临界区的态度+谦让

    预先表明想进入临界区,但为了防止死锁,在进入临界区前会延迟一段时间

    boolean flag[2] = {false, false};//共享的全局变量
    
    //进程P0
    do {
        flag[0] = true;                 
        while (flag[1])  {              
            flag[0] = false;
             <随机延迟一小段时间>//谦让
            flag[0] = true;
        }
        进程P0的临界区代码; //临界区
        flag[0] = false;   //退出区
        进程P0的其它代码     //剩余区
    } while (true)
    
    //进程P1
    do {
        flag[1] = true;                  
        while (flag[0]) {                
            flag[1] = false; 
            <随机延迟一小段时间>//谦让
          flag[1] = true;
        }
        进程P1的临界区代码; //临界区
        flag[1] = false;   //退出区
        进程P1的其它代码     //剩余区
    } while (true)
    

    可能会活锁,过分谦让,长时间僵持:CPU先将时间片分给P0,然后P0置flag[0]=true,这时CPU又将时间片分给 P1,P1置flag[1]=true;接下来CPU先将时间片分给P0,P0发现flag[1]=true;进入while循环,先将flag[0]清零,再挂起一段时间,重新置位flag[0],查看flag[1]是否仍为1,若是则继续清零等待,重复这个过程,监听flag[1]的变化;同理,P1可能会与P0默契地进行同样的活动,两者同时监听,同时挂起,形成活锁,可能随时间自动解除

    Dekker互斥算法

    由于前一种算法活锁的原因是只监听了对方的flag,这时添加一个只能由对方改变的信息turn即可
    在这里插入图片描述

    boolean flag[2] = {false, false};      //共享的全局变量
    int turn = 1;                          //共享的全局变量
    
    //进程P0
    do {
        flag[0] = true;              //进入区
        while (flag[1]) {
           if (turn == 1)  {
               flag[0] = false;
               while  (turn == 1) ;  //等待
               flag[0] = true;
            }
         }                           //进入区
        进程P0的临界区代码;           //临界区
        turn = 1;
        flag[0] = false;             //退出区
        进程P0的其它代码               //剩余区
    } while (true)
    
    //进程P1
    do {
        flag[1] = true;              //进入区
        while (flag[0]) {
           if (turn == 0)  {
               flag[1] = false;
               while  (turn == 0) ;  //等待
               flag[1] = true;
            }
         }                           //进入区
        进程P1的临界区代码;           //临界区
        turn = 0;
        flag[1] = false;             //退出区
        进程P1的其它代码               //剩余区
    } while (true)
    
    

    在预先表明态度+谦让的基础上改进了谦让机制:
    P1在退出临界区时会置turn=0;P0退出临界区会将turn置为1
    这样一来,可以在监听对方flag时知道对方是否已经退出临界区,而不是等待一段随机时间,我认为这时重新尝试将自己的flag置为true是更好的做法,不会产生活锁

    Peterson互斥算法

    与dekker算法的区别:不是在退出时而是在进入前将turn改变

    boolean flag[2] = {false, false};    //共享的全局变量
    int turn;                            //共享的全局变量
    
    //进程P0
    do {
        flag[0] = true;                //进入区
        turn = 1;                      //进入区
        while (flag[1] && turn == 1) ; //进入区
        进程P0的临界区代码;             //临界区
        flag[0] = false;               //退出区
        进程P0的其它代码          	   //剩余区
    } while (true)
    
    进程P1
    do {
        flag[1] = true;                       //进入区
        turn = 0;                             //进入区
        while (flag[0] && turn == 0) ; 	      //进入区
        进程P1的临界区代码;           		  //临界区
        flag[1] = false;                      //退出区
        进程P1的其它代码                   	  //剩余区
    } while (true)
    
    

    假设P0进程先置自己的flag为true,改变turn=1,此时有一个while循环,当P1的flag=false时,说明P1还没有运行到置flag=true的行,可以继续进入临界区,或当turn=0时,这时说明P1执行后转而执行P0,P0此时在turn行,但P0无法进入临界区,因为此时flag[0]=true,而此时P0可以无视flag[1]=true的条件而继续进入临界区

    评价软件互斥方法
    1. 不能解决忙等问题(使用while监听方法),效率低
    2. 进程互斥使用临界资源困难,难以控制两个以上进程的互斥
    3. 算法设计时容易死锁或互斥失败
    展开全文
  • 经典互斥算法解析

    2019-10-07 23:34:33
    本文用较为轻松的方式介绍了几个经典的互斥算法: Dekker 算法、Dijkstra 提出的算法、Peterson 算法和面包店算法,并简单地给出了每一个算法的正确性证明和相关的讨论。本文探寻分布式计算历史上的几个非常有名非常...

    本文用较为轻松的方式介绍了几个经典的互斥算法: Dekker 算法、Dijkstra 提出的算法、Peterson 算法和面包店算法,并简单地给出了每一个算法的正确性证明和相关的讨论。本文探寻分布式计算历史上的几个非常有名非常经典的互斥算法,尽管这些算法几乎是所有操作系统、分布式系统或多线程编程课本中必介绍的算 法,可是由于这些算法由于性能问题已经被现代的算法或机制替代了,实际中不会有人使用这些算法。尽管如此,了解这些算法可以帮助我们理解同步领域的基本原理。此外,了解这些算法的正确性证明可还可以训练并发算法正确性推导的思维。 

    由于博客上不容易做出精美的排版,所以本文采用LaTeX排版并输出pdf,下面是pdf文件的新浪微盘链接,欢迎下载!

    http://vdisk.weibo.com/s/muyTn

     

    转载于:https://www.cnblogs.com/zhengsyao/archive/2013/01/04/classical_mutual_exclusion_algorithms.html

    展开全文
  • Dekker互斥算法

    2019-03-26 17:20:04
    Dekker互斥算法详解 转载:https://blog.csdn.net/wsw875421872/article/details/17222219 大家好,这是本人的第一个技术博客(也是第一个博客),曾经看过《一个程序员的奋斗史》,从而萌生了写博...

                                                                            Dekker互斥算法详解

    转载:https://blog.csdn.net/wsw875421872/article/details/17222219 

    大家好,这是本人的第一个技术博客(也是第一个博客),曾经看过《一个程序员的奋斗史》,从而萌生了写博客的想法。本人目前正在自学嵌入式方向,是一个不折不扣的小鸟。这篇博客亦来自于我学习计算机操作系统原理过程中的总结成果(视频下载地址http://xidong.net/File001/File_53948.html)。如果有人也正在学习这方面内容,我非常希望能够帮到你。如果有不对的地方欢迎大家指出和改正。

    大多数系统允许多个进程共享资源(如CPU,IO设备,硬盘等),而为了保证进程间能够互不影响、安全正确地访问这些共享资源,就必须对进程访问共享资源采取某种控制。对于某一时刻仅允许一个进程访问的共享资源就叫临界资源,而访问这些临界资源的程序代码段就叫做临界区。而计算机术语中,对进程排它地访问临界资源的这种控制手段就叫做互斥(也就是说某一时刻临界区的进程只能为一个)。

    解决进程互斥的方法有很多,比如软件方法、硬件方法、信号量方法、管程等方法,而今天我所说的Dekker互斥算法就是软件方法中的一种。

    菜鸟设想:先让我们看看一个初学者所能想到的最简单的互斥访问临界区的伪代码:

    初学者看见这段代码,可能有人会觉得很奇怪。flag初始化为0,然后执行process方法的时候,while判断不通过,故执行后面的代码,而最后方法结束的时候,flag的值任然为0,这不是相当于while循环体永远不会执行吗???注意!!不能再用单进程编程那样一段代码从头执行到底的“直线式”思维了。这里可是多进(线)程编程!程序完全有可能在执行到任意一条语句时被中断,从而跳到另外一个进程执行另外一段代码。

    上述代码中,设置一个状态值用于判断进程是否可以进入临界区,有程序进入临界区的时候便将flag修改为忙碌,等到出临界区的时候则重置为空闲,从而释放资源。表面上来看仿佛做到了互斥(当一个进程在临界区时阻止了其他进程进入)。可是仔细看,其实上述代码根本没有达到互斥的功能!!!为什么呢?先休息一下。等我谈到改进设想1的时候再说原因。^_^

    总之,上述的代码并没有达到我们所需要的功能,那么我现在就推出一个很好的解决了互斥功能的代码吧(仅仅是解决了互斥),这就是初步设想。

    初步设想:代码献上:

    注意到这段代码,其实这段代码的思路很清晰:将每个要访问临界区的进程设置一个序号,每个进程必须按照这个序号依次访问临界区。看上去貌似可以达到互斥。实际上的确如此,他完美的达到了互斥,仅此而已。程序严格地按照一定的次序(0->1->0->1...)访问临界区,从而当一个进程进入临界区时,完全没有留给任何进入临界区的机会给其他进程。为什么呢?同样等到改进设想1的时候再说原因。^_^

    基础比较好的同学肯定会注意到:这样做留下了好几个要命的问题:首先访问临界区的两个进程完全依赖彼此对number值的修改,假设一个进程在将序号值修改成其他进程需要的序号值之前,出现了错误直接退出进程,那么序号将永远得不到修改,那么依赖这个序号值的进程将永远得不到执行!这是很要命的,它违背了进程“有限等待、空闲让进”的互斥原则。此外,当两个进程访问临界资源的频率不同时将会严重影响系统效率。比如,进程0每1分钟要访问临界区,进程1每10分钟访问临界区。当进程1退出临界区后,十分钟后才会进入临界区,而进程0的每一分钟就要进入临界区,可是当进程0退出临界区后必须等进程1退出临界区后才能进入,而此时进程1并不需要进入临界区,进程0必须在临界区空闲的情况下在9分钟后等到临界区被进程1访问并退出后才能进入,而且每进行一个周期就要等一个9分钟!也就是说访问频率低的进程严重影响了访问频率高的进程的执行效率,这明显违背了“空闲让进”原则。

    可能菜鸟们(本人也是)对以上的表述;理解得不是太清楚。下面我来类比这样一个例子:上面的情形就好像两个人想进入一个仅有一个蹲位的厕所,门口有一个大爷将两个人分别给了一个号码牌(0、1),且规定必须按照“01010101...”的规则进入厕所。假如人A在上厕所的时候一个不小心将号码牌0丢进了下水道,那么人B就悲剧了,因为守门的大爷很奇怪,他永远要等到号码牌0从厕所里出来才会让人B进去。。。。另外一钟情况,假如人A每一天上一次厕所,而人B肾功能不太好每5分钟上一次厕所,那么等人A上完厕所后,人B也第一次上完厕所后。。。天啊!他不给憋死才怪。

    这下大家应该知道这种制度的可恨之处了吧,介于初步设想有这么多弊端,下面进行了第一次改进。

    改进设想1:代码如下:

    改进设想1取消了初步设想的序号访问方式,使得上面的大部分问题得到解决。此方法其实与菜鸟设想大同小异,它们给了临界区一个状态标识,当标识为空闲则允许进程进入,使得临界区得到充分利用,不同地方在于改进设想1状态信息更为精确,它使得程序知道是哪个进程占用了临界区,加大了编程的灵活性,但是却限制了互斥算法的使用条件:仅能控制两个进程进行互斥操作,其实这也是Dekker算法的缺点之一。

    不幸的是,改进设想1与菜鸟设想一样,同样不能实现真正的互斥,这到底是为什么呢?我前面提到,多进程的并发具有不确定性,程序执行过程中可能会不停地进行进程切换。让我们看一下这样一种情形:进程0一路执行完(1)处,由于flag[1]被初始化为0,因而跳过循环体,准备开始执行(2),此时进程突然被切换,转而执行进程1,等到进程1执行到(3)时,因为(2)处还未得到执行,flag[0]的值还没有来的修改,还是初始值0,结果进程1同样绕过了循环体顺利的进入了临界区,这样就导致了进程0和进程1同时进入了临界区,使得互斥失效。同样的道理菜鸟设想也犯了这个致命的错误。然而为什么序号访问就能顺利的互斥呢?这是因为无论如何切换,number的值不是0就是1,这就决定了两个while循环(一个判断是否为0,一个判断是否为1)只有一个能顺利“绕过”循环体,并进入临界区,从而达到互斥访问。

    回到刚才我类比的例子,就好比此时厕所上装了一个信号灯,用来表示厕所里是否有人,当厕所外面的人看见信号灯亮则表示里面有人而不能进厕所,反之则表示无人可进。这时候假如人A看见信号灯是黑的,进去之后还没来得急按下信号灯的开关,而此时恰好人B又看见灯是黑的,于是也进入了厕所,这时,就尴尬了。。。

    可见由于进程的切换的不确定性导致了进程同时进入了临界区,而上述情况的原因在于修改状态的“时机”不对,因此就有了改进设想2。

    改进设想2:代码如下:

    改进设想2将状态的修改放在了循环之前,即进程访问临界区时需提前表达访问临界区的“意愿”,这样一来,无论进程如何切换等到其中一个进程开始执行循环条件判断时,要么仅有一个flag为0,要么两个均为1,这就保证了两个进程无法同时绕过循环体。可是细心的人会发现这样一个问题:当进程0一路执行完(1)处,由于flag[1]被初始化为0,因而跳过循环体,准备开始执行(2),此时进程若被切换至进程1,等进程1执行完(3)时,又被切换回进程0执行,而此时flag[1]被修改为1满足循环条件进入循环体,在循环的某一时刻又切换到(4)执行,同样由于flag[0]被修改为1进入循环体,结果可想而知,两个进程都进入了循环体而不能修改自己状态值,导致两个进程永远都不能跳出循环。这种情形在计算机中叫做“死锁”,除非某一进程主动放弃资源,或系统主动干涉,否则进程永远占用资源但却又得不到推进。

    用厕所的类比来说,此种方法就是给了每个人一个遥控器,使之能在进入厕所之前就能够远程点亮信号灯,从而避免同时进入厕所,可是倘若人A点亮了属于自己的信号灯,但还没来得及进入厕所时,人B也不甘示弱的点亮了自己的信号灯,两个人都互不谦让,从而造成谁也进不了厕所。。。

    可以看出上述问题出现的根结所在,由于两个进程均提前表达了进入临界区的企图,可是谁也不肯放弃自己进入临界区的意愿,互不退让,并且不断查看状态值,从而导致死锁。


    改进设想3:代码如下:    

         

    改进的思路很简单,让进程在发现对方进入想临界区的愿望后,将自己的意愿停止一个随机时长,从而达到相互谦让地表达自身的意愿。这样一来即使双发进程在某一刻因为对方的状态值均为1而都进入了while循环体,可是由于进程将会放弃进入意愿而使得某一进程总会因为不满足循环条件而跳出循环,从而进入临界区。由于停止时间是随机的,或许会经过很多次循环判断的时候对方的状态都为1,可是,总会有一时刻

    使得两个进程的执行进度会得到错开,使得双方进行循环判断的时候不会两个flag都为1。虽然此种方法不会进入死锁,可是却存在一种发生可能性非常低的僵局,即双方在谦让过后可能同时又进行循环判断,从而一次又一次的谦让下去,导致程序效率降低,甚至出现双方的谦让导致两个进程的阻塞时间接近于无穷大的情况。

    再用到厕所的例子来说明:人A与人B看见对方进入厕所的信号灯都是亮着的,便都主动礼貌地谦让,关掉了自己的信号灯,可是呢,两人实在过于默契,两人都在同一时刻关灯,并且又在同一时间开灯,双发就这么一直让来让去,两人就这么僵持着很长一段时间,谁也没能进入临界区。。。

    然而,程序设计必须保持绝对的严谨,虽然在停止了一个随机时间的情况下,两个进程仍然保持“同步推进”的情况实在微乎其微,但是即使有%0.00...001的可能性使得程序死锁,那么这个设计便是不完美的。为了彻底杜绝决形成这种僵局的可能性,便诞生了最终算法也就是大名鼎鼎的Dekker互斥算法。(抱歉,这一段,实在不知道该怎么表达才通俗易懂)

    最终设想(Dekker互斥算法):

    Dekker算法终于出炉了,可以看出Dekker算法是基于改进设想3的谦让思路的基础上,采取的一种“谦让而又不过分谦让”的折中思想。如何避免双方不停的谦让呢?Dekker算法采用了初步设想的序号访问思想,使得进入循环的进程按照序号来决定到底该不该一直谦让,有人会问,采用序号的是否使得进程出现按照序号访问临界区的老毛病呢?答案是不会的,至少是不会严格的按照序号轮流访问临界区,原因在于,按照序号来谦让有一个前提条件:两个进程必须因为对方的状态值恰好都为忙碌而同时进入循环体,而在此之前,两个进程进入临界区的概率是相同的,跟序号是没有关系的。也就是说想要序号访问临界区还需要一点“运气”。

    总之,Dekker算法首先使用状态值的方式解决了序号访问临界区的弊端,又利用改进思想2使得进程可以互斥的访问临界资源,同时又采用了改进思想3的方法避免了死锁现象,而最后结合了序号谦让方式解决了因为避免死锁而产生的僵局现象,就这样循序渐进地用软件方法解决了进程的互斥的问题。

    然而,Dekker方法就真是完美无缺的吗?很遗憾,就算是Dekker算法也无法避免软件互斥方法的一个通病,那就是忙等现象。大家注意以上的每一个设想中,都不可或缺地使用while循环,而循环体中,执行地都是毫无意义的代码,也就是说软件方法利用无意义的循环使得进程无法向前推进来达到阻塞进程的目的,然而让CPU去执行无意义的代码本身就是一种严重资源浪费,进程既占用了CPU,然而却没有生产任何有效数据,可以说,这样做严重降低了CPU的效率。这是整个软件方法都无法回避的问题。

    此外,大家可以看见Dekker算法仅能进行两个进程的互斥,对于两个以上的互斥问题,实现起来相当复杂。

    并且,软件方法在实现互斥的时候,需要相当小心,一会不小就是互斥失败啦,死锁啦,之类的.

    展开全文
  • 分布式互斥算法解析

    2020-04-09 16:48:30
    文章目录引言集中式算法分布式算法基于请求的算法基于令牌的算法总结 ...保证任何给定时刻只允许一个进程或者给定的进程去执行临界区的算法称为互斥算法. 传统的单机达到互斥的方法有互斥锁,条件变...

    引言

    分布式系统中可能会出现多个节点访问一个资源或者同时执行一个给定的函数,这些资源或者函数一般成为临界资源(Critical Resource),有时这些 临界资源需要在同一时刻只有一个进程执行,这就是分布式互斥.保证任何给定时刻只允许一个进程或者给定的进程去执行临界区的算法称为互斥算法.

    传统的单机达到互斥的方法有互斥锁,条件变量,读写锁,共享内存,信号量,内存序,内存屏障等,这些方法在分布式系统中通通不可用,在分布式系统中消息传递是实现互斥的唯一的方法.

    分布式互斥算法可以分为集中式算法(Centralized Algorithm)和分布式算法(Distributed Algorithm),其中分布式算法又可以分为基于令牌的算法(Token Based Algorithm)和基于请求的算法(Permission Based Algorithm).下来我们就来看看吧!

    集中式算法

    在所有的节点中引入一个协调者,这个协调者负责所有节点申请资源请求的调度.每个节点想要申请资源需要向协调者发送请求,如果当前节点没有人使用的话,协调者就授权这个节点进行访问.对于协调者来说维护一个队列,用先来后到的顺序为没有申请到资源的节点排序,当得到资源的节点执行完毕以后返回一个消息代表使用完毕,这个时候协调者再次分配.
    在这里插入图片描述

    集中式互斥算法在一次申请资源的交互中需要三次消息交互:

    1. 节点向协调者请求资源.
    2. 协调者给予权限.
    3. 节点完成以后返回释放消息.

    这也是集中式算法的优点,即通信成本较低,且直观,简单,所有的节点只需要于协调者通信.当然这也正是它的缺点,因为所有的压力全部落在了协调者身上,这里有两个问题:

    1. 可用性,如果协调者宕机,整个服务直接不可用,假如重启以后信息丢失,还有可能破坏一致性假设.可以搭配哨兵和主从复制模型,这样可以保证一定的可用性,但还是会出现一定时间内服务下线.
    2. 有效率瓶颈,所有的压力全部落在了协调者上,一定会有瓶颈,最好选一个不错的硬件来做协调者.

    分布式算法

    在分布式算法中又分为基于令牌的算法和基于请求的算法,它们之间也是各有优缺点.

    基于请求的算法

    这里介绍Ricart-Agrawala算法,其他基于请求的算法大都在这个基础上修改.如果把一次选举的leader看做是资源的话,选举的过程其实也是一个分布式互斥算法的实现.这样看来这种基于请求的算法其实比较常见,也就是所有的节点之间互相连接,形成网状的网络拓扑结构,在每次使用资源的时候向其他节点发起资源的申请,如果获取全票同意的话则获取资源使用权,在使用的过程中也可能有其他节点同样请求资源,发送请求的双方都可以得到对方使用资源的消息,这个时候对比出时间戳最小的(基于逻辑时钟而不是物理时间戳,见另一篇文章 不可靠的时钟),即最先发起请求的获取资源访问权,得到资源访问权的节点也要维护一个队列,存储其他申请请求,在完成资源访问以后向其他申请资源的节点发送同意使用资源的消息,一般不申请资源的节点在收到其他申请资源的请求时直接同意.

    从以上流程不难看出,信息的交互过程是这样的,首先我们假设集群有N个节点:

    1. 向其他N-1个节点发送请求资源消息.需要N-1次交互.
    2. 需要接收N-1个节点的回复消息,需要N-1次交互.

    这样每个节点每次申请资源需要2(N-1)此信息交互.而且当集群内每个节点都进行资源申请的时候会有2N(N-1)次交互,也就是说随着集群的扩展,通信成本是平方上涨的.它还有以下问题:

    1. 当系统内需要访问临界资源的程序增多时,容易产生“信令风暴”,也就是程序收到的请求完全超过了自己的处理能力,而导致自己正常的业务无法开展.
    2. 因为采用的是全部节点同意,为了防止只有两个节点请求,它们之间只有一个可以得到N-1个投票剩下一个得到N-2个投票,这意味着一个节点故障的话整个系统就处于停滞状态.

    这种基于请求的分布式互斥算法适合与节点数目少,变动不频繁的系统,且适用与P2P结构,因为每个程序之间都需要互相交互.HDFS就是一个典型的运用场景.

    基于令牌的算法

    如下图所示,所有程序构成一个逻辑上的环结构,令牌按照顺时针(或逆时针)方向在程序之间传递,收到令牌的程序有权访问临界资源,访问完成后将令牌传送到下一个程序.若该程序不需要访问临界资源,则直接把令牌传送给下一个程序.
    在这里插入图片描述
    这样每一个节点在适用资源之前就不需要向每一个节点请求了,只需要传递令牌即可,得到令牌的节点获取资源,这样在一个周期内全部节点都有机会适用资源,不需要的话直接转发就可以了.当然这也带来一些无效的通信成本,且降低了实时性.因为就算只有一个节点请求资源,全部的节点都需要进行信息传递,而且考虑到节点宕机,每个节点也不能仅存储自己的下一位节点.令牌环算法非常适合通信模式为令牌环方式的分布式系统.

    总结

    1. 集中式算法: 优点就是简单,易于实现,只有搭配上哨兵和主从复制可用性才说的过去,但是宕机仍会服务下线.且有单机的效率瓶颈.’
    2. 分布式算法-基于请求: 可用性强,一般也不使用全部同意,而是配置纪元搭配选举,可容忍一半以下节点宕机,比较类似与无主节点的结构.缺点就是通信成本过高.适用于临界资源使用频率较低的时候.(redis中故障转移选举执行的节点不就是这样实现的)
    3. 分布式算法-基于令牌: 通信效率高且可用性不差.使用与请求资源频繁且使用时间短的情况,缺点就是容易带来大量的无用通信.

    其实分布式互斥算法应用很广泛,比如选举的过程(一次只需要一个leader),Redlock(Redis官方钦点的分布式锁实现),HDFS(Hadoop的分布式文件系统),它对于我们学习分布式至关重要.

    参考:
    P2P结构

    逻辑时钟

    基于请求的分布式互斥算法 很详细

    聂鹏程 分布式技术原理与算法解析

    展开全文
  • PETERSON互斥算法解析

    2019-09-19 10:06:55
    对于互斥算法,主要有两种,一种是DEKKER算法,另一种是PETERSON算法,这一篇主要来说PETERSON算法。 相比于DEKKER算法,PETERSON算法也解决了互斥访问问题,并且不需要像DEKKER算法一样强制轮流访问,可以正常的...
  • Dekker互斥算法解析

    2019-09-18 22:46:02
    引入Dekker互斥算法解决的是多进程访问一个临界区的保护问题和“after you”问题。 我们首先来看,两个进程访问一段临界区的互斥问题: //P进程如下: pturn = true; while(qturn); //临界区的资源 pturn = ...
  • 摘要 互斥能有效解决分布式系统中的资源申请的相互冲突并实现资源共享本文 首先简要介绍了分布式异步系统中互斥算法的一些基本要求及评价标准并介绍 单令牌环算法和双令牌环算法的算法思想及存在的不足分析了双令牌...
  • 进程互斥原则模板: (1)互斥性 枚举所有情况,一个进程进入临界区后,另一个进程不能进入临界区 ...Dekker互斥算法 int flag[2]; int turn; P0:do{ flag[0] = 1; while flag[1] do if(turn == 1){ flag[0] =.
  • 操作系统之互斥算法

    2020-04-27 17:22:07
    Dekkel互斥算法 flag表示是否想进入临界区,turn表示轮到谁 int flag[2]; (init 0) int turn; (0 or 1) P0: do{ flag[0]=1; while(flag[1]) if(turn==1){ flag[0]=0; wh...
  • Peterson互斥算法 1981年,G.L.Peterson 提出的一个简单的互斥算法。 int flag[2];//初值为0,表示进程是否在临界区内 int turn;//初值为0或1,表示当前轮流次序 P0: do { flag[0]=1; turn=1; while (flag[1...
  • 分布式系统互斥算法---集中式算法

    千次阅读 2015-05-10 14:54:58
    在分布式系统中可能会稍微复杂一点,有些互斥算法的大体思想和单系统中的互斥锁比较类似(比如令牌);但是分布式系统中还有其他更多的互斥方法; 分布式互斥算法可以分为两种不同类型: 1)基于令牌的解决方法,...
  • 看了一个论文分布式互斥算法的综述。 感觉一头雾水,打算把这些分布式算法的伪代码都写出来。 看国产的那么多的论文都觉得没能看出什么真知灼见,有刘心松老师带的两个博士论文还可以以后慢慢的看 还要根据wiki中...
  • 我们一起看看有哪些类型的分布式互斥算法。 1、集中式算法 在集中式算法中,一般需要一个协调者。每个程序在访问临界资源的时候,需要先给协调者发送一个请求。如果当前临界资源没有使用者,则授权该程序使用该资源...
  • peterson互斥算法 1981

    千次阅读 2011-12-04 00:24:24
    源自:>,page 36 peterson互斥算法 1981 #define FALSE 0 #define TRUE 1 #define N 2 /*进程数*/ int turn; /*轮到谁了?*/ in
  • 操作系统的实验课设,实现Dekker,Lamport,Peterson,Eisenberg进程互斥访问临界区算法,使用java语言完成,可以动态显示进程访问临界区时各个进程的状态
  • 操作系统原理——Dekker互斥算法详解

    千次阅读 多人点赞 2013-12-10 02:24:08
    Dekker互斥算法详解 大家好,这是本人的第一个技术博客(也是第一个博客),曾经看过《一个程序员的奋斗史》,从而萌生了写博客的想法。本人目前正在自学嵌入式方向,是一个不折不扣的小鸟。这篇博客亦来自于我学习...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,517
精华内容 606
关键字:

互斥算法