死锁和活锁有什么区别?
有人可以用示例(代码)解释一下死锁和活锁之间的区别吗?
Can somebody please explain with examples (of code) what is the difference between deadlock and livelock?
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
发布评论
评论(7)
一个线程通常会响应另一个线程的操作。如果
另一个线程的操作也是对另一个线程操作的响应
线程,则可能会导致活锁。与死锁一样,活锁线程无法取得进一步进展。然而,线程并没有被阻塞 - 它们只是太忙于相互响应而无法恢复工作。这类似于两个人试图在走廊里超越对方:阿尔方斯移动到他的左边让加斯顿通过,而加斯顿移动到他的右边让阿尔方斯通过。阿尔方斯见他们还在互相阻挡,就往他的右边移动,而加斯顿则往他的左边移动。他们仍然互相阻挡,等等......
活锁和死锁之间的主要区别是线程不会被阻塞,相反,它们会尝试不断地相互响应。
在此图像中,两个圆圈(线程或进程)将尝试通过左右移动为另一个圆圈提供空间。但他们不能再进一步了。
这里的所有内容和示例均来自
操作系统:内部结构和设计原则
威廉·斯托林斯
8° 版
死锁:两个或多个进程无法继续进行的情况,因为每个进程都在等待另一个进程执行某项操作。
例如,考虑两个进程 P1 和 P2,以及两个资源 R1 和 R2。假设每个进程都需要访问这两种资源来执行其部分功能。那么可能会出现以下情况:OS将R1分配给P2,将R2分配给P1。每个进程都在等待这两个资源之一。两者都不会释放它已经拥有的资源,直到它获得为止
另一个资源并执行需要这两个资源的功能。两人
进程死锁
活锁:两个或多个进程不断改变其状态以响应其他进程的变化而不做任何有用的工作的情况:
饥饿:调度程序无限期地忽略可运行进程的情况;尽管它能够进行,但它从未被选择。
假设三个进程(P1、P2、P3)各自需要定期访问资源 R。考虑这样的情况:P1 拥有该资源,而 P2 和 P3 都被延迟,等待该资源。当 P1 退出其关键部分时,应允许 P2 或 P3 访问 R。假设操作系统授予对 P3 的访问权限,并且在 P3 完成其关键部分之前 P1 再次需要访问。如果操作系统在 P3 完成后授予对 P1 的访问权限,随后交替授予对 P1 和 P3 的访问权限,则即使不存在死锁情况,也可能无限期地拒绝 P2 对资源的访问。
附录 A - 并发主题
死锁示例
如果两个进程在执行 while 语句之前将其标志设置为 true,则每个进程都会认为对方已进入其临界区,造成僵局。
/* PROCESS 0 */
flag[0] = true; // <- get lock 0
while (flag[1]) // <- is lock 1 free?
/* do nothing */; // <- no? so I wait 1 second, for example
// and test again.
// on more sophisticated setups we can ask
// to be woken when lock 1 is freed
/* critical section*/; // <- do what we need (this will never happen)
flag[0] = false; // <- releasing our lock
/* PROCESS 1 */
flag[1] = true;
while (flag[0])
/* do nothing */;
/* critical section*/;
flag[1] = false;
活锁示例
/* PROCESS 0 */
flag[0] = true; // <- get lock 0
while (flag[1]){
flag[0] = false; // <- instead of sleeping, we do useless work
// needed by the lock mechanism
/*delay */; // <- wait for a second
flag[0] = true; // <- and restart useless work again.
}
/*critical section*/; // <- do what we need (this will never happen)
flag[0] = false;
/* PROCESS 1 */
flag[1] = true;
while (flag[0]) {
flag[1] = false;
/*delay */;
flag[1] = true;
}
/* critical section*/;
flag[1] = false;
[...]考虑以下事件序列:
- P0 将 flag[0] 设置为 true。
- P1 将 flag[1] 设置为 true。
- P0 检查标志[1]。
- P1 检查标志[0]。
- P0 将 flag[0] 设置为 false。
- P1 将 flag[1] 设置为 false。
- P0 将 flag[0] 设置为 true。
- P1 将 flag[1] 设置为 true。
该序列可以无限期地延长,并且两个进程都不能进入其临界区。严格来说,这不是死锁,因为两个进程相对速度的任何改变都会打破这个循环并允许进入临界区。这种情况称为活锁。回想一下,当一组进程希望进入其临界区但没有进程能够成功时,就会发生死锁。使用活锁,可能存在成功的执行序列,但也可以描述一个或多个没有进程进入其临界区的执行序列。
不再满足于书本。
那么自旋锁呢?
自旋锁是一种避免操作系统锁定机制成本的技术。通常您会这样做:
try
{
lock = beginLock();
doSomething();
}
finally
{
endLock();
}
当 beginLock()
的成本远高于 doSomething()
时,问题就开始出现。用非常夸张的话说,想象一下当 beginLock
花费 1 秒,但 doSomething
只花费 1 毫秒时会发生什么。
在这种情况下,如果你等待 1 毫秒,你就可以避免受到 1 秒的阻碍。
为什么beginLock
会花费这么多?如果锁是免费的,则不会花费很多(请参阅https://stackoverflow.com/a/49712993/5397116 ),但如果锁未释放,操作系统将“冻结”您的线程,设置一种机制在锁释放时唤醒您,然后在将来再次唤醒您。
所有这些都比一些检查锁的循环要昂贵得多。这就是为什么有时最好使用“自旋锁”。
例如:
void beginSpinLock(lock)
{
if(lock) loopFor(1 milliseconds);
else
{
lock = true;
return;
}
if(lock) loopFor(2 milliseconds);
else
{
lock = true;
return;
}
// important is that the part above never
// cause the thread to sleep.
// It is "burning" the time slice of this thread.
// Hopefully for good.
// some implementations fallback to OS lock mechanism
// after a few tries
if(lock) return beginLock(lock);
else
{
lock = true;
return;
}
}
如果您的实现不小心,您可能会遇到活锁,将所有 CPU 都花在锁机制上。
另请参阅:
https://preshing.com/20120226/roll-your-own -轻量级互斥体/
我的自旋锁实现是否正确且最佳?
摘要:
死锁:没有人进步、什么都不做的情况(睡觉、等待等)。 CPU使用率会很低;
活锁:没有人进步的情况,但是CPU花费在锁定机制上而不是在你的计算上;
饥饿:一个进程永远没有机会运行的情况;由于纯粹的运气不佳或由于其某些属性(例如低优先级);
自旋锁:避免等待锁释放的成本的技术。
也许这两个示例向您说明了死锁和活锁之间的区别:
死锁的 Java 示例:
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;
public class DeadlockSample {
private static final Lock lock1 = new ReentrantLock(true);
private static final Lock lock2 = new ReentrantLock(true);
public static void main(String[] args) {
Thread threadA = new Thread(DeadlockSample::doA,"Thread A");
Thread threadB = new Thread(DeadlockSample::doB,"Thread B");
threadA.start();
threadB.start();
}
public static void doA() {
System.out.println(Thread.currentThread().getName() + " : waits for lock 1");
lock1.lock();
System.out.println(Thread.currentThread().getName() + " : holds lock 1");
try {
System.out.println(Thread.currentThread().getName() + " : waits for lock 2");
lock2.lock();
System.out.println(Thread.currentThread().getName() + " : holds lock 2");
try {
System.out.println(Thread.currentThread().getName() + " : critical section of doA()");
} finally {
lock2.unlock();
System.out.println(Thread.currentThread().getName() + " : does not hold lock 2 any longer");
}
} finally {
lock1.unlock();
System.out.println(Thread.currentThread().getName() + " : does not hold lock 1 any longer");
}
}
public static void doB() {
System.out.println(Thread.currentThread().getName() + " : waits for lock 2");
lock2.lock();
System.out.println(Thread.currentThread().getName() + " : holds lock 2");
try {
System.out.println(Thread.currentThread().getName() + " : waits for lock 1");
lock1.lock();
System.out.println(Thread.currentThread().getName() + " : holds lock 1");
try {
System.out.println(Thread.currentThread().getName() + " : critical section of doB()");
} finally {
lock1.unlock();
System.out.println(Thread.currentThread().getName() + " : does not hold lock 1 any longer");
}
} finally {
lock2.unlock();
System.out.println(Thread.currentThread().getName() + " : does not hold lock 2 any longer");
}
}
}
示例输出:
Thread A : waits for lock 1
Thread B : waits for lock 2
Thread A : holds lock 1
Thread B : holds lock 2
Thread B : waits for lock 1
Thread A : waits for lock 2
活锁的 Java 示例:
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;
public class LivelockSample {
private static final Lock lock1 = new ReentrantLock(true);
private static final Lock lock2 = new ReentrantLock(true);
public static void main(String[] args) {
Thread threadA = new Thread(LivelockSample::doA, "Thread A");
Thread threadB = new Thread(LivelockSample::doB, "Thread B");
threadA.start();
threadB.start();
}
public static void doA() {
try {
while (!lock1.tryLock()) {
System.out.println(Thread.currentThread().getName() + " : waits for lock 1");
Thread.sleep(100);
}
System.out.println(Thread.currentThread().getName() + " : holds lock 1");
try {
while (!lock2.tryLock()) {
System.out.println(Thread.currentThread().getName() + " : waits for lock 2");
Thread.sleep(100);
}
System.out.println(Thread.currentThread().getName() + " : holds lock 2");
try {
System.out.println(Thread.currentThread().getName() + " : critical section of doA()");
} finally {
lock2.unlock();
System.out.println(Thread.currentThread().getName() + " : does not hold lock 2 any longer");
}
} finally {
lock1.unlock();
System.out.println(Thread.currentThread().getName() + " : does not hold lock 1 any longer");
}
} catch (InterruptedException e) {
// can be ignored here for this sample
}
}
public static void doB() {
try {
while (!lock2.tryLock()) {
System.out.println(Thread.currentThread().getName() + " : waits for lock 2");
Thread.sleep(100);
}
System.out.println(Thread.currentThread().getName() + " : holds lock 2");
try {
while (!lock1.tryLock()) {
System.out.println(Thread.currentThread().getName() + " : waits for lock 1");
Thread.sleep(100);
}
System.out.println(Thread.currentThread().getName() + " : holds lock 1");
try {
System.out.println(Thread.currentThread().getName() + " : critical section of doB()");
} finally {
lock1.unlock();
System.out.println(Thread.currentThread().getName() + " : does not hold lock 1 any longer");
}
} finally {
lock2.unlock();
System.out.println(Thread.currentThread().getName() + " : does not hold lock 2 any longer");
}
} catch (InterruptedException e) {
// can be ignored here for this sample
}
}
}
示例输出:
Thread B : holds lock 2
Thread A : holds lock 1
Thread A : waits for lock 2
Thread B : waits for lock 1
Thread B : waits for lock 1
Thread A : waits for lock 2
Thread A : waits for lock 2
Thread B : waits for lock 1
Thread B : waits for lock 1
Thread A : waits for lock 2
Thread A : waits for lock 2
Thread B : waits for lock 1
...
这两个示例都强制线程以不同的顺序获取锁。
当死锁等待另一个锁时,
活锁并不真正等待——它拼命地尝试获取锁,但没有机会获得它。每次尝试都会消耗 CPU 周期。
想象一下,您有线程 A 和线程 B。它们在同一个对象上同步
,并且在该块内有一个它们都在更新的全局变量;
static boolean commonVar = false;
Object lock = new Object;
...
void threadAMethod(){
...
while(commonVar == false){
synchornized(lock){
...
commonVar = true
}
}
}
void threadBMethod(){
...
while(commonVar == true){
synchornized(lock){
...
commonVar = false
}
}
}
因此,当线程 A 进入 while
循环并持有锁时,它会执行其必须执行的操作,并将 commonVar
设置为 true
。然后线程B进来,进入while
循环,由于commonVar
现在是true
,它能够持有锁。它这样做,执行synchronized
块,并将commonVar
设置回false
。现在,线程 A 再次获取新的 CPU 窗口,它原本即将退出 while
循环,但线程 B 刚刚将其设置回 false
,因此循环再次重复。线程会做一些事情(因此它们不会被传统意义上的阻塞),但几乎什么也不做。
也许还值得一提的是,活锁不一定必须出现在这里。我假设一旦同步块完成执行,调度程序就会优先考虑另一个线程。大多数时候,我认为这是一个很难实现的期望,并且取决于幕后发生的许多事情。
我只是想分享一些知识。
死锁
如果一组线程/进程中的每个线程/进程都在等待只有该组中的另一个进程才能引发的事件,则一组线程/进程将陷入死锁。
这里重要的是另一个进程也在同一组中。这意味着另一个进程也被阻止,没有人可以继续。
当进程被授予对资源的独占访问权限时,就会发生死锁。
必须满足这四个条件才会发生死锁。
- 互斥条件(每个资源分配给1个进程)
- 保持等待条件(进程持有资源,同时可以请求其他资源)。
- 无抢占条件(之前授予的资源不能被强行夺走)#此条件取决于应用程序
- 循环等待条件(必须是2个或更多进程的循环链,并且每个进程都在等待链中下一个成员持有的资源) # 它会动态发生
如果我们发现这些条件,那么我们可以说可能会发生像死锁这样的情况。
LiveLock
每个线程/进程都一次又一次地重复相同的状态,但不会进一步前进。类似于死锁,因为进程无法进入临界区。然而,在死锁中,进程等待而不执行任何操作,但在活锁中,进程尝试继续,但进程一次又一次地重复到相同的状态。
(在死锁计算中,没有可能成功的执行序列。但在活锁计算中,有成功的计算,但有一个或多个执行序列,其中没有进程进入其临界区。)
与死锁和死锁的区别livelock
当死锁发生时,不会发生任何执行。但在活锁中,会发生一些执行,但这些执行不足以进入临界区。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
摘自http://en.wikipedia.org/wiki/Deadlock:
Taken from http://en.wikipedia.org/wiki/Deadlock: