目录

活锁

参考:https://www.zhihu.com/question/20566246

活锁现象

活锁、死锁本质上是一样的,原因是在获取临界区资源时,并发多个进程/线程声明资源占用(加锁)的顺序不一致,死锁是加不上就死等,活锁是加不上就放开已获得的资源重试,其实单机场景活锁不太常见。举个例子资源A和B,进程P1和P2,

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
start:

P1 lock A
P2 lock B

P1 lock B fail context switch
P2 lock A fail context switch

P1 release A
P2 release B

goto start

单个core时如果调度的不好还是有可能出现的,多core情况下,冲突窗口很小,很难出现两个进程的节奏碰的这么巧。

但是在分布式场景下,由于加锁失败,而要释放已获得的资源再重试,这个过程涉及网络通信,冲突窗口变大,使得活锁出现概率也变大。比如paxos的prepare和accept,两个并发提案P1和P2,P2用更大proposal id的prepare形成多数派,将使得之前已经prepare成功的P1无法accept,P1只能用更更大的proposal id重试,而使得P2又无法accept,把prepare和accept看做两个资源A和B,每个提案都是按BAB的顺序获取资源(因为prepare阶段的应答蕴含了对accept增加了限制),过程中存在BA和AB两种资源获取顺序,是典型的活锁场景

活锁和死锁的区别

活锁和死锁在表现上是一样的两个线程都没有任何进展,

但是区别在于: 死锁,两个线程都处于阻塞状态, 而活锁呢,并不会阻塞,而是一直尝试去获取需要的锁,不断的try,这种情况下线程并没有阻塞所以是活的状态,但是只是在做无用功。 对应Wikipedia的例子的话,两个人都没有停下来等对方让路,而是都有很有礼貌的给对方让路,但是两个人都在不断朝路的同一个方向移动,这样只是在做无用功,还是不能让对方通过。

活锁的解决

活锁在工业上是非常好解决的

  • 增加一个random的timeout,比如使用redis做分布式锁的实现里就有采用这种方法来避免活锁现象。
  • proposer选主,其实Leader的概念也应该属于Paxos范畴的。如果议员人人平等,在某种情况下会由于提议的冲突而产生一个“活锁”(所谓活锁我的理解是大家都没有死,都在动,但是一直解决不了冲突问题)。Paxos的作者Lamport在他的文章”ThePart-TimeParliament“中阐述了这个问题并给出了解决方案——在所有议员中设立一个总统,只有总统有权发出提议,如果议员有自己的提议,必须发给总统并由总统来提出。好,我们又多了一个角色:总统。