死锁和活锁有什么区别？

Question

请用代码举例解释死锁和活锁之间的区别。

- macindows

---

在“*死锁和活锁、无限递归和饥饿的区别是什么*”中有代码示例。 - Pacerier

Answer 1

从http://en.wikipedia.org/wiki/Deadlock获取：

在并发计算中，死锁是一个状态，在这个状态下，一组操作的每个成员都在等待另一个成员释放锁。

活锁类似于死锁， 除了参与活锁的进程状态 相互之间不断变化，互相影响， 但是没有任何一个进程会向前推进。 活锁是资源饥饿的特例； 普遍定义只是说明了 一个特定的进程没有向前推进。

现实生活中的一个例子是， 当两个人在狭窄的走廊里遇到时， 每个人都试图礼貌地让对方先过去， 但他们最终左右摇摆而没有取得进展， 因为他们都反复地同时朝同一方向移动。

活锁是某些检测和 从死锁中恢复的算法面临的风险。 如果有多个进程采取行动， 死锁检测算法可能会一再被触发。 可以通过确保只有一个进程（随机选择或按优先级选择）采取行动来避免这种情况。

- mah

---

我已经找到了，但是他们那里没有例子，就像你所看到的那样，不管怎样还是谢谢。 - macindows

不会提供代码示例，但考虑两个进程分别以非阻塞方式等待对方拥有的资源。当每个进程发现自己无法继续时，它们会释放所持有的资源并休眠30秒，然后再获取其原始资源，接着尝试获取另一进程持有、释放、重新获得的资源。由于两个进程都试图处理问题（只是不太成功），这就是活锁。 - mah

可以请您给我一个死锁的例子吗？谢谢。 - macindows

死锁示例较为简单...假设有两个进程 A 和 B，每个都想获取资源 r1 和资源 r2。假设 A 接收到（或已经拥有）r1，B 接收到（或已经拥有）r2。现在每个尝试获取对方拥有的资源，而没有任何超时限制。A 被阻塞，因为 B 持有 r2，B 被阻塞，因为 A 持有 r1。每个进程都被阻塞，因此无法释放对方想要的资源，导致死锁。 - mah

在事务内存的语境下，有一段很棒的视频展示死锁和活锁：http://www.youtube.com/watch?v=_IxsOEEzf-c - BlackVegetable

Answer 2

活锁

一个线程通常是响应另一个线程的操作。如果另一个线程的行动也是对另一个线程行动的响应，则可能导致活锁。

与死锁类似，活锁的线程无法继续向前进展。但是，线程不会被阻塞——它们只是忙于相互响应而无法恢复工作。这就像两个人试图在走廊里相互擦肩而过：Alphonse向左移以让Gaston通过，而Gaston向右移以让Alphonse通过。看到他们仍然相互阻挡，Alphonse向右移动，而Gaston向左移动。他们仍然相互阻拦，如此往复......

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

在这张图片中，两个圆圈（线程或进程）将尝试通过左右移动给彼此腾出空间。但是它们无法再移动更远。

- Bruce

---

代码示例：死锁的实例 https://dev59.com/wnNA5IYBdhLWcg3wQ7Uw - Yauhen Yakimovich

这个东西有一个名字。也许是俚语，但仍然是：schlumperdink :P - John Red

Answer 3

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

操作系统：内部原理和设计原则
William Stallings
第8版

死锁：两个或多个进程由于彼此等待对方执行某些操作而无法继续。

例如，考虑两个进程P1和P2，以及两个资源R1和R2。假设每个进程都需要访问两个资源才能执行其功能的一部分。那么可能出现以下情况：操作系统将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检查flag [1]。
• P1检查flag [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://dev59.com/AXA65IYBdhLWcg3wvxeE#49712993），但如果锁定未被释放，操作系统将“冻结”您的线程，设置一个机制，在锁定被释放时唤醒您，然后在未来再次唤醒您。

所有这些都比一些循环检查锁定要昂贵得多。这就是为什么有时最好使用“自旋锁”的原因。

例如：

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

如果你的实现不小心，可能会陷入活锁（livelock）的状态，导致所有的CPU时间都花费在锁机制上。

另请参见：

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

总结：

死锁（Deadlock）：所有进程都没有进展，什么都不做（睡眠、等待等）。CPU使用率很低；

活锁（Livelock）：所有进程都没有进展，但CPU时间都花费在锁机制上，而不是计算上；

饥饿（Starvation）：某个进程永远没有机会运行，由于纯粹的运气不好或者某些属性（例如低优先级）；

自旋锁（Spinlock）：一种避免等待锁释放成本的技术。

- Daniel Frederico Lins Leite

---

先生，您提供的死锁示例实际上是自旋锁的示例。当一组进程被阻塞且不处于就绪或运行状态并正在等待某些资源时，才会发生死锁。但在我们的示例中，每个人都在执行某些任务，即一遍又一遍地检查条件。如果我错了，请纠正我。 - Vinay Yadav

这个例子非常简单，以至于存在这种解释的可能性，因此我尝试改进它，使其更加明确它们之间的区别。希望能有所帮助。 - Daniel Frederico Lins Leite

谢谢您提到自旋锁，根据您的解释，自旋锁是一种技术，您也进行了合理的辩解，我已经理解了。但是当一个进程P1处于临界区时，另一个高优先级进程P2被调度并抢占了P1时，会出现什么情况呢？此时CPU在P2手中，而我们的同步机制在P1手中，这就是所谓的自旋锁，因为P1处于就绪状态，而P2处于运行状态。在这种情况下，自旋锁是一个问题。 我理解得对吗？我还没有完全理解其中的复杂性，请帮忙解释。 - Vinay Yadav

我建议您创建另一个问题，更清楚地陈述您的问题。现在，如果您在“用户空间”，而P1位于由无限循环实现的SpinLock保护的关键会话内并被抢占，则P2将尝试进入该会话，失败并将烧掉其所有时间片。 您创建了一个活锁（一个CPU将达到100％）。 （保护同步IO使用自旋锁是一个不好的例子。您可以轻松尝试此示例）在“内核空间”中，也许这个注释可以帮助您：http://lxr.linux.no/linux+v3.6.6/Documentation/preempt-locking.txt#L117 - Daniel Frederico Lins Leite

非常感谢您的澄清。无论如何，与其他人不同，您的回答非常详细和有帮助。 - Vinay Yadav

Answer 4

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

活锁 当两个或多个任务依赖并使用同一资源时，可能会出现活锁条件，导致这些任务无休止地运行，从而阻塞所有优先级较低的任务运行（这些较低优先级的任务经历饥饿状态）。

- Deepak Lamichhane

---

如果“活锁”任务遵循包括“退后”延迟在内的资源仲裁协议，并且大部分时间处于睡眠状态，那么其他任务就不会被饿死。 - greggo

Answer 5

也许这两个例子可以帮助你理解死锁和活锁之间的区别：

---

一个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周期。

- mmirwaldt

---

代码不错。但是活锁的例子不好。无论线程是在一个值上被堵塞还是在轮询值的变化，概念上并没有区别。为了更好地说明活锁，可以简单改变一下，让A和B线程在意识到不能获取第二个所需的锁时，释放他们已经拥有的锁。然后它们分别睡眠一秒钟，重新获取原来拥有的锁，再睡眠一秒钟，尝试重新获取其他锁。这样每个线程的周期是：1）获取自己的锁，2）睡眠，3）尝试获取其他锁并失败，4）释放自己的锁，5）睡眠，6）重复。 - CognizantApe

我怀疑你所想的活锁是否真的存在足够长的时间，以至于它们会引起麻烦。当你在无法分配下一个锁时总是放弃所有持有的锁时，死锁（和活锁）条件中的“持有并等待”已经不存在了，因为实际上不再需要等待。（https://en.wikipedia.org/wiki/Deadlock） - mmirwaldt

确实，死锁条件缺失，因为我们讨论的是活锁。我给出的例子类似于标准的走廊示例：https://www.geeksforgeeks.org/deadlock-starvation-and-livelock/，https://en.wikibooks.org/wiki/Operating_System_Design/Concurrency/Livelock，https://docs.oracle.com/javase/tutorial/essential/concurrency/starvelive.html。 - CognizantApe

第一个链接中的代码示例缺少解锁语句，这让我感到非常困惑。不清楚临界区从哪里开始和结束。我的观点是，语句执行的顺序每次尝试都会改变，下一轮实际上永远不会相同。而且，并不是每个执行顺序最终都会导致活锁。大多数情况下甚至不会！因此，您不会观察到那些活锁，因为它们很快就会消失，随后是下一个无害的执行顺序，这是非常可能的。没有完美的活锁示例可以观察到;-) - mmirwaldt

这取决于操作的触发器及其所需的时间。它绝对可以是一种有效的锁定方式。如果需要10秒钟的计算才能跳转到一个状态或返回，并且两个线程以5秒的相位差彼此作出反应，那么在同一进程中两个线程之间的计算速度变化足以使其偏移5秒的机会非常低。自己试试吧。创建两个运行10秒钟的程序，并在它们之间相隔5秒钟启动它们，看看它们在某个范围内（比如1秒）内进入相位需要多长时间。 - CognizantApe

Answer 6

假设您有线程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
         }
    }
}

因此，当线程A进入while循环并持有锁时，它会执行必要的操作并将commonVar设置为true。然后，线程B进入，进入while循环，并且由于commonVar现在是true，因此可以持有锁。它这样做，执行synchronized块，并将commonVar重新设置为false。现在，线程A再次获得它的新CPU窗口，它已经准备退出while循环，但是线程B刚刚将它重新设置为false，所以循环重复了。线程做了些事情（因此它们不被传统意义上的阻塞），但基本上没有任何作用。

可能还值得一提的是，活锁不一定会在这里出现。我假设调度程序在synchronized块完成执行后更喜欢另一个线程。大多数情况下，我认为这是一个难以达到的期望，并且取决于许多在幕后发生的事情。

- stdout

---

不错的例子。它也说明了在并发环境中为什么应该始终以原子方式读取和写入数据。如果 while 循环在同步块内部，那么上述问题就不会存在。 - CognizantApe

Answer 7

我只是想分享一些知识。

死锁是指一个线程/进程集合被死锁了，如果集合中的每个线程/进程都在等待只有集合中的另一个进程才能引发的事件。

重要的是，在同一集合中还有另一个进程。这意味着另一个进程也被阻塞了，没有人可以继续进行。

当进程被授予对资源的独占访问权时，会发生死锁。

要满足以下四个条件才能发生死锁。

1. 互斥条件（每个资源分配给1个进程）
2. 保持和等待条件（进程持有资源，同时它还可以请求其他资源）。
3. 无抢占条件（先前授予的资源不能强制性地被收回）#此条件取决于应用程序
4. 循环等待条件（必须是2个或多个进程的循环链，每个进程都在等待由链中下一个成员持有的资源）#它将动态发生

如果我们发现这些条件，则可以说可能会出现死锁的情况。

活锁

每个线程/进程一遍又一遍地重复相同的状态，但不会进展。这类似于死锁，因为进程无法进入关键部分。但是在死锁中，进程正在等待而不执行任何操作，但在活锁中，进程正在尝试继续执行，但是进程一遍又一遍地重复相同的状态。

（在死锁计算中，没有可能成功的执行顺序。但在活锁计算中，有成功的计算，但存在一种或多种执行顺序，在其中没有进程进入其关键部分。）

与死锁和活锁的不同之处

当发生死锁时，不会发生任何执行。但在活锁中，一些执行将发生，但这些执行不足以进入关键部分。

- Sivaram Rasathurai