multithreading 死锁和活锁有什么区别？

Question

提问by macindows

Can somebody please explain with examples (of code) what is the difference between deadlockand livelock?

有人可以用示例（代码）解释死锁和活锁之间的区别吗？

Answer 1

回答by mah

Taken from http://en.wikipedia.org/wiki/Deadlock:

取自http://en.wikipedia.org/wiki/Deadlock：

In concurrent computing, a deadlockis a state in which each member of a group of actions, is waiting for some other member to release a lock
A livelockis similar to a deadlock, except that the states of the processes involved in the livelock constantly change with regard to one another, none progressing. Livelock is a special case of resource starvation; the general definition only states that a specific process is not progressing.
A real-world example of livelock occurs when two people meet in a narrow corridor, and each tries to be polite by moving aside to let the other pass, but they end up swaying from side to side without making any progress because they both repeatedly move the same way at the same time.
Livelock is a risk with some algorithms that detect and recover from deadlock. If more than one process takes action, the deadlock detection algorithm can be repeatedly triggered. This can be avoided by ensuring that only one process (chosen randomly or by priority) takes action.

在并发计算中，死锁是一组动作的每个成员都在等待其他成员释放锁的状态
阿活锁类似于死锁，不同之处在于所涉及的活锁的过程的状态不断地关于彼此，无进展而改变。Livelock 是一种资源匮乏的特例；一般定义仅说明特定过程没有进展。
活锁的一个真实例子发生在两个人在狭窄的走廊里相遇，每个人都试图通过让对方通过来保持礼貌，但他们最终左右摇晃，没有任何进展，因为他们都反复移动同时以同样的方式。
活锁是一些检测死锁并从死锁中恢复的算法的风险。如果多个进程采取行动，死锁检测算法可以重复触发。这可以通过确保只有一个进程（随机或按优先级选择）采取行动来避免。

Answer 2

回答by Buru

Livelock

活锁

A thread often acts in response to the action of another thread. If the other thread's action is also a response to the action of another thread, then livelock may result.
As with deadlock, livelocked threads are unable to make further progress. However, the threads are not blocked— they are simply too busy responding to each other to resume work. This is comparable to two people attempting to pass each other in a corridor: Alphonse moves to his left to let Gaston pass, while Gaston moves to his right to let Alphonse pass. Seeing that they are still blocking each other, Alphonse moves to his right, while Gaston moves to his left. They're still blocking each other, and so on...

一个线程通常会响应另一个线程的操作。如果另一个线程的动作也是对另一个线程动作的响应，则可能会导致活锁。
与死锁一样，活锁线程无法取得进一步进展。然而，线程并没有被阻塞——它们只是忙于相互响应而无法继续工作。这类似于两个人在走廊中试图通过对方：阿尔方斯向左移动让加斯顿通过，而加斯顿向右移动让阿尔方斯通过。阿尔方斯见他们还在互相阻拦，便向右移动，而加斯顿则向左移动。他们仍然互相阻止，等等......

The main difference between livelockand deadlockis that threads are not going to be blocked, instead they will try to respond to each other continuously.

活锁和死锁的主要区别在于线程不会被阻塞，而是会尝试不断地相互响应。

In this image, both circles (threads or processes) will try to give space to the other by moving left and right. But they can't move any further.

在此图像中，两个圆圈（线程或进程）都将尝试通过向左和向右移动来为另一个提供空间。但他们不能再进一步了。

enter image description here

在此处输入图片说明

Answer 3

回答by Daniel Frederico Lins Leite

All the content and examples here are from

这里所有的内容和例子都来自

Operating Systems: Internals and Design Principles
William Stallings
8o Edition

操作系统：内部结构和设计原则
William Stallings
8o 版

Deadlock: A situation in which two or more processes are unable to proceed because each is waiting for one the others to do something.

死锁：两个或多个进程无法继续进行的情况，因为每个进程都在等待另一个进程做某事。

For example, consider two processes, P1 and P2, and two resources, R1 and R2. Suppose that each process needs access to both resources to perform part of its function. Then it is possible to have the following situation: the OS assigns R1 to P2, and R2 to P1. Each process is waiting for one of the two resources. Neither will release the resource that it already owns until it has acquired the other resource and performed the function requiring both resources. The two processes are deadlocked

例如，考虑两个进程 P1 和 P2，以及两个资源 R1 和 R2。假设每个进程都需要访问这两种资源来执行其部分功能。那么就有可能出现以下情况：操作系统将R1分配给P2，将R2分配给P1。每个进程都在等待两种资源之一。两者都不会释放它已经拥有的资源，直到它获得了另一个资源并执行了需要这两种资源的功能。两个进程都死锁了

Livelock: A situation in which two or more processes continuously change their states in response to changes in the other process(es) without doing any useful work:

活锁：两个或多个进程不断改变其状态以响应其他进程的变化而不做任何有用工作的情况：

Starvation: A situation in which a runnable process is overlooked indefinitely by the scheduler; although it is able to proceed, it is never chosen.

饥饿：调度程序无限期忽略可运行进程的情况；尽管它能够继续进行，但它从未被选中。

Suppose that three processes (P1, P2, P3) each require periodic access to resource R. Consider the situation in which P1 is in possession of the resource, and both P2 and P3 are delayed, waiting for that resource. When P1 exits its critical section, either P2 or P3 should be allowed access to R. Assume that the OS grants access to P3 and that P1 again requires access before P3 completes its critical section. If the OS grants access to P1 after P3 has finished, and subsequently alternately grants access to P1 and P3, then P2 may indefinitely be denied access to the resource, even though there is no deadlock situation.

假设三个进程（P1、P2、P3）每个都需要定期访问资源 R。考虑 P1 拥有资源的情况，P2 和 P3 都被延迟，等待该资源。当 P1 退出其临界区时，应允许 P2 或 P3 访问 R。假设操作系统授予对 P3 的访问权限，并且在 P3 完成其临界区之前 P1 再次需要访问。如果操作系统在 P3 完成后授予对 P1 的访问权限，并随后交替授予对 P1 和 P3 的访问权限，则 P2 可能会无限期地被拒绝访问资源，即使没有死锁情况。

APPENDIX A - TOPICS IN CONCURRENCY

附录 A - 并发主题

Deadlock Example

死锁示例

If both processes set their flags to true before either has executed the while statement, then each will think that the other has entered its critical section, causing deadlock.

如果两个进程在其中一个执行 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;

Livelock Example

活锁示例

/* 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;

[...] consider the following sequence of events:

[...] 考虑以下事件序列：

P0 sets flag[0] to true.
P1 sets flag[1] to true.
P0 checks flag[1].
P1 checks flag[0].
P0 sets flag[0] to false.
P1 sets flag[1] to false.
P0 sets flag[0] to true.
P1 sets flag[1] to true.

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。

This sequence could be extended indefinitely, and neither process could enter its critical section. Strictly speaking, this is not deadlock, because any alteration in the relative speed of the two processes will break this cycle and allow one to enter the critical section. This condition is referred to as livelock. Recall that deadlock occurs when a set of processes wishes to enter their critical sections but no process can succeed. With livelock, there are possible sequences of executions that succeed, but it is also possible to describe one or more execution sequences in which no process ever enters its critical section.

这个序列可以无限延长，两个进程都不能进入它的临界区。严格来说，这不是死锁，因为两个进程相对速度的任何改变都会打破这个循环，让一个人进入临界区。这种情况称为活锁。回想一下，当一组进程希望进入其临界区但没有进程可以成功时，就会发生死锁。使用livelock，有可能成功的执行序列，但也可以描述一个或多个没有进程进入其临界区的执行序列。

Not content from the book anymore.

不再是书中的内容。

And what about spinlocks?

那么自旋锁呢？

Spinlock is a technique to avoid the cost of the OS lock mechanism. Typically you would do:

自旋锁是一种避免操作系统锁定机制成本的技术。通常你会这样做：

try
{
   lock = beginLock();
   doSomething();
}
finally
{
   endLock();
}

A problem start to appear when beginLock()costs much more than doSomething(). In very exagerated terms, imagine what happens when the beginLockcosts 1 second, but doSomethingcost just 1 millisecond.

当beginLock()成本远远超过时，问题开始出现doSomething()。用非常夸张的说法，想象一下当beginLock成本为 1 秒而doSomething成本仅为 1 毫秒时会发生什么。

In this case if you waited 1 millisecond, you would avoid being hindered for 1 second.

在这种情况下，如果您等待 1 毫秒，您将避免被阻碍 1 秒。

Why the beginLockwould cost so much? If the lock is free is does not cost a lot (see https://stackoverflow.com/a/49712993/5397116), but if the lock is not free the OS will "freeze" your thread, setup a mechanism to wake you when the lock is freed, and then wake you again in the future.

为什么beginLock要花这么多钱？如果锁是免费的，则不会花费很多（参见https://stackoverflow.com/a/49712993/5397116），但如果锁不是免费的，操作系统将“冻结”您的线程，设置一种机制来唤醒您当锁被释放时，然后在将来再次唤醒你。

All of this is much more expensive than some loops checking the lock. That is why sometimes is better to do a "spinlock".

所有这些都比一些检查锁的循环要昂贵得多。这就是为什么有时做一个“自旋锁”会更好。

For example:

例如：

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;
   }
}

If your implementation is not careful, you can fall on livelock, spending all CPU on the lock mechanism.

如果你的实现不小心，你可能会陷入活锁，把所有的 CPU 都花在锁机制上。

Also see:

另见：

https://preshing.com/20120226/roll-your-own-lightweight-mutex/
Is my spin lock implementation correct and optimal?

https://preshing.com/20120226/roll-your-own-lightweight-mutex/
我的自旋锁实现是否正确和最佳？

Summary:

总结：

Deadlock: situation where nobody progress, doing nothing (sleeping, waiting etc..). CPU usage will be low;

死锁：没有人进步，什么都不做（睡觉，等待等）的情况。CPU使用率会很低；

Livelock: situation where nobody progress, but CPU is spent on the lock mechanism and not on your calculation;

Livelock: 没有人进步的情况，但 CPU 花在锁定机制上而不是你的计算上；

Starvation: situation where one procress never gets the chance to run; by pure bad luck or by some of its property (low priority, for example);

饥饿：一个进程永远没有机会运行的情况；纯粹是因为运气不好或其某些财产（例如，低优先级）；

Spinlock: technique of avoiding the cost waiting the lock to be freed.

自旋锁：避免等待释放锁的成本的技术。

Answer 4

回答by Deepak Lamichhane

DEADLOCKDeadlock is a condition in which a task waits indefinitely for conditions that can never be satisfied - task claims exclusive control over shared resources - task holds resources while waiting for other resources to be released - tasks cannot be forced to relinguish resources - a circular waiting condition exists

DEADLOCK死锁是一种条件，其中任务无限期地等待永远不会满足的条件 - 任务声称对共享资源具有独占控制权 - 任务持有资源，同时等待其他资源被释放 - 任务不能被迫放弃资源 - 循环等待条件存在

LIVELOCKLivelock conditions can arise when two or more tasks depend on and use the some resource causing a circular dependency condition where those tasks continue running forever, thus blocking all lower priority level tasks from running (these lower priority tasks experience a condition called starvation)

LIVELOCK当两个或多个任务依赖并使用导致循环依赖条件的某些资源时，可能会出现活锁条件，这些资源将永远继续运行，从而阻止所有较低优先级的任务运行（这些较低优先级的任务会遇到称为饥饿的情况）

Answer 5

回答by mmirwaldt

Maybe these two examples illustrate you the difference between a deadlock and a livelock:

也许这两个例子可以说明死锁和活锁之间的区别：

Java-Example for a deadlock:

死锁的 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");
        }
    }
}

Sample output:

示例输出：

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-Example for a livelock:

活锁的 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
        }
    }
}

Sample output:

示例输出：

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
...

Both examples force the threads to aquire the locks in different orders. While the deadlock waits for the other lock, the livelock does not really wait - it desperately tries to acquire the lock without the chance of getting it. Every try consumes CPU cycles.

这两个示例都强制线程以不同的顺序获取锁。当死锁等待另一个锁时，活锁并没有真正等待——它拼命尝试获取锁而没有获得它的机会。每次尝试都会消耗 CPU 周期。

Answer 6

回答by stdout

Imagine you've thread A and thread B. They are both synchronisedon the same object and inside this block there's a global variable they are both updating;

假设你有线程 A 和线程 B。它们都synchronised在同一个对象上，并且在这个块内有一个全局变量，它们都在更新；

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
         }
    }
}

So, when thread A enters in the whileloop and holds the lock, it does what it has to do and set the commonVarto true. Then thread B comes in, enters in the whileloop and since commonVaris truenow, it is be able to hold the lock. It does so, executes the synchronisedblock, and sets commonVarback to false. Now, thread A again gets it's new CPU window, it wasabout to quit the whileloop but thread B has just set it back to false, so the cycle repeats over again. Threads do something (so they're not blocked in the traditional sense) but for pretty much nothing.

所以，当线程 A 进入while循环并持有锁时，它会做它必须做的事情并将设置commonVar为true。然后线程B进来，在进入while循环，因为commonVar是true现在，它是能够持有锁。它这样做，执行synchronised块，然后设置commonVar回false. 现在，线程A再次得到它的新的CPU窗口，它是要退出while循环，但线程B刚刚设置回false，如此循环重复了一遍。线程可以做一些事情（所以它们不会在传统意义上被阻塞）但几乎没有任何作用。

It maybe also nice to mention that livelock does not necessarily have to appear here. I'm assuming that the scheduler favours the other thread once the synchronisedblock finish executing. Most of the time, I think it's a hard-to-hit expectation and depends on many things happening under the hood.

值得一提的是，livelock 不一定非要出现在这里。我假设一旦synchronised块完成执行，调度程序就会支持另一个线程。大多数时候，我认为这是一个难以实现的期望，取决于幕后发生的许多事情。

multithreading 死锁和活锁有什么区别？

提问by macindows

回答by mah

回答by Buru

回答by Daniel Frederico Lins Leite

回答by Deepak Lamichhane

回答by mmirwaldt

回答by stdout

相关推荐

最近更新

标签

multithreading 死锁和活锁有什么区别？

提问by macindows

回答by mah

回答by Buru

回答by Daniel Frederico Lins Leite

回答by Deepak Lamichhane

回答by mmirwaldt

回答by stdout

相关推荐

multithreading SMP 内核、进程和线程如何准确地协同工作？

multithreading 多线程：线程数多于内核数有什么意义？

multithreading 竞争条件和死锁之间的区别

multithreading 线程与核心

相关推荐

最近更新

标签