死锁的坏兄弟Livelock

想象一下,夫妻俩最近搬进新房子后共进晚餐。 他们只有两个人的汤匙(其余在移动的面包车中),而且他们都很有礼貌。 如果他们还没吃饭,他们就把汤匙交给配偶。 这是一个活锁可以做什么的真实示例。

在讨论活锁之前,我们必须首先解释什么是死锁。 死锁是一种情况,而不是例如锁和信号量之类的对象。 当两个或多个进程拥有一个资源并等待同一组进程中的另一个进程拥有另一个资源时,就会发生这种情况。 这是为了防止任何进程前进到下一个状态。 您可以举一个“现实世界”的示例,其中两个人在画,但是只有一支铅笔和一根直尺用于两个。 如果一支铅笔的人需要尺子,而一支铅笔的人需要铅笔,然后再完成尺子,那么这两个请求都无法满足,那么我们就会陷入僵局。

但是活锁呢?

活锁是死锁的一种特殊情况,其中死锁中涉及的进程在彼此之间不断变化的状态而无法前进。 与其中涉及的所有进程都处于等待状态的死锁相比,活动锁中涉及的进程可以同时运行。 另一个真实世界的类比是两个人在一条狭窄的走廊里互相走动。 他们俩都想保持礼貌并向一边走,但他们不断向同一边走,因此无法前进。 当算法解决检测并解决死锁情况时,可能会发生活锁。 如果一个以上的过程起作用,则该算法可以重复触发。 显然,可以通过确保在特定时刻只有一个进程可以操作来轻松避免这种情况,但这不会阻止死锁的发生。

这些情况如何发生?

系统没有采取任何措施来防止死锁,因为预见到死锁要比从死锁中恢复要复杂得多,但这并不一定意味着预料到死锁不是更好的选择。 另外,尝试防止死锁会导致出现活锁的情况,这种情况并不好。

要同时发生死锁/活锁,需要同时满足四个条件:

·互斥:一次只能由一个进程使用资源

·保留并等待:已经拥有资源的进程可能会请求新的资源

·无抢占:只有拥有资源的进程可以释放它

·循环等待:两个或多个进程形成一个循环链,其中每个进程都等待下一个进程拥有的资源

似乎可以管理四个条件,但这取决于您所站的位置。 从OS的角度来看,您不希望借此机会创建活动锁或使情况复杂化。 从开发人员的角度来看,如果系统试图解决僵局,那么在程序开发过程中进行调试将变得更加复杂。

那么我们该怎么办?

从理论上讲(尽管很少使用),存在避免或防止死锁和活锁(以及其他任何发生的锁)的解决方案。 如果在资源分配之前可以获得有关流程的某些信息,则可以避免发生这种情况。 可以通过确保上述条件中的一个(或多个)不成立来进行预防。 实际上,通常不使用这些解决方案。 取而代之的是,检测和进程重启是触发的算法,这些算法跟踪资源分配和进程状态,并将回滚一个或多个进程以消除死锁/活动锁。 特别是对于活锁,实现层次结构有时可以解决问题。

为什么要做那么少阻止这种事情发生呢?

有趣的是,这个问题在开发过程中非常普遍,幸运的是,大多数系统并不太在乎。 死锁通常被认为是开发人员没有注意到的设计缺陷,但是在某些情况下(您有许多无法同时控制的进程同时运行),使用“检测并重新启动”算法来解决问题可能更简单,有时更好。不久的将来会出现问题。 关于此问题的一个有趣的事实是,大多数情况下,当它发生时,系统会忽略它,并假装永远不会发生死锁/活锁。 这似乎有问题,但对于开发人员而言,这意味着他们可以识别问题并提出解决方案,而不是使用可能产生活锁的潜在防死锁算法。

总体而言,死锁主要来自程序开发过程中的设计缺陷,应尽可能进行适当处理(调试或算法取决于情况)。 活锁是死锁预防算法将死锁变成活锁或类似于死锁的结果,它们也是设计缺陷。

参考书目

https://stackoverflow.com/questions/6155951/whats-the-difference-between-deadlock-and-livelock

活锁的好例子?
我知道什么是活锁,但是我想知道是否有人有一个基于代码的良好示例? 基于代码,我… stackoverflow.com

https://medium.com/@esmerycornielle/deadlock-dfa195d32ff5

操作系统设计– Wikibooks,开放世界的开放书籍
提供了《操作系统设计》的可打印版本。 en.wikibooks.org

http://iips.icci.edu.iq/images/exam/Abraham-Silberschatz-Operating-System-Concepts — 9th2012.12.pdf

http://pages.mtu.edu/~shene/FORUM/台湾论坛/ComputerScience/004-Concurrency/WWW/SLIDES/11-Deadlock.pdf