有关“活锁“的疑问

vupiggy

二来Tam可是这方面的大师，因此之前并没有将书名及作者写出来........
tomkedy 发表于 2011-06-13 15:44

印象当中没有人称呼他 Tam 的，貌似外界都称呼 AST，在 VU，中国学生私底下管他叫老T，见面叫 Andy，管和 AST 合作《Distributed System》的 Maarteen van Steen 叫老马 。

言归正传，大师也会犯错误甚至是低级错误，如果确信他书里有问题可以直接给他们写信，老T一般是来信必复，老马也差不多，只要你的信是 ASCII 编码且不夹带任何附件。VU的一干中国学生不止一次给他们发信指出《Distributed System》里的逻辑错误，在新版的书里他们都给改正了。

个人认为活锁/死锁还得从逻辑上判定而不是从最终效果，前一阵子写一个调度 MPI 程序的调度器就碰到活锁问题，比正常情况慢300到400倍 (100sec vs 30000 sec)，大部分时间在抢锁，但是偶尔还跳回用户空间转几下，最终还是能结束产生正确结果，改了改，改出死锁来，那就地老天荒了，机器在内核里自旋，一个星期结果也出不来。

tempname2

回复 11# vupiggy

我又看了一下WIKI上关于resource starvation的解释，里面提到了deadlock,livelock,starvation间的联系，我觉得很有道理。

http://en.wikipedia.org/wiki/Resource_starvation

照这上面的说法，deadlock的特征：1 永远僵持；2 竞争者都无法改变自身状态； 3 所竞争的资源都在相互牵制的竞争者之间占有。其它类似情况都叫starvation。livelock正是不满足条件2，但是满足条件1和3。所以宽泛来说，livelock也是starvation，再宽泛一点，deadlock也是starvation。如果像你所说获取其它锁失败会释放自己的锁但时机不好而产生长时间两者反复获得释放锁却无法make process的情况，应该算是一般意义的starvation。总之，这些是几种客观存在的情况，至于怎么称呼，恐怕只有一般认识，没有什么权威说法。老谭的书上也并没有在概念上做这么细致的区别。

这么一说，我还真觉得书上最后一段是想说“有些人不区分死锁或活锁”。此时并未介绍starvation(正好是下一节的内容)，比较livelock与deadlock似乎更合逻辑。

PS:我想搜搜《Modern Operating Systems》的勘误，看看有没有人提出这个问题。虽然没搜到，但是发现《Compute Networks》去年就出第五版了。已经一年多了，影印版还没有动静，可能培森真的不让再出影印版了。

vupiggy

其实要严格区分也是可行的，在 http://en.wikipedia.org/wiki/Dining_philosophers_problem 里有一段论述听上去可以采用。就是以系统的状态迁移是否仍在发生为界。死锁发生以后，该算法的状态不再发生任何迁移(进程切换不属于算法内部的状态迁移)，而活锁发生以后，哲学家的状态在举叉放叉之间做迁移，于是在实际应用中，死锁的哲学家就餐算法死锁以后导致确定的无限等待，而导致活锁的算法在活锁发生以后仍然可能因哲学家的时钟有略微的不同步就可以让整个算法继续，哲学家可能吃完饭走人，万事大吉，用陈冠希的话就是 ``indefinitely'' 地等待

题外话：细分活锁死锁的确有点无聊，不过经验上看导致活锁的算法更难被检测到，也更难调试，更容易出现在自己机器上运行得好好的，作业一交，助教说根本不工作，更摸不着头脑。

AD8018

这段“活锁”的提法，典型的层次不清，故作玄虚。
enter_region应看做一个原语，
在更高的层次上看，不应该纠结于其内部的实现。
通过不断查询锁定的，还是通过改变任务状态实现的，跟本题讨论的毫无关系。

别理他，这就是典型的“死锁”。

guocslock

同意楼上的，这明显是典型的死锁案例，实现的逻辑是spinlock。
解决的方法也很简单，在需要获取多个锁的时候，记住要以相同的顺序来获取锁就OK了。比如两个进程都采取先获取A锁，再获取B锁的顺序。