死锁和活锁有什么区别？

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

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

---

Livelock

一个线程经常响应另一个线程的动作。如果另一个线程的动作也是对另一个线程动作的响应，那么可能会导致活锁。与死锁一样，活锁线程无法取得进一步进展。但是，线程并没有被阻塞——它们只是忙于相互响应而无法恢复工作。这类似于两个人试图在走廊里互相超越：Alphonse 向左移动让 Gaston 通过，而 Gaston 向右移动让 Alphonse 通过。阿尔方斯看到他们仍然互相阻挡，他向右移动，而加斯顿则向左移动。他们仍然互相阻挡，等等......

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

在此图像中，两个圆圈（线程或进程）都将尝试通过左右移动来给对方留出空间。但他们不能再进一步了。

https://i.stack.imgur.com/OAda8.jpg

---

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

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

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

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

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

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

假设三个进程（P1、P2、P3）每个都需要定期访问资源 R。考虑 P1 拥有资源的情况，而 P2 和 P3 都被延迟，等待该资源。当 P1 退出其临界区时，应允许 P2 或 P3 访问 R。假设操作系统授予对 P3 的访问权限，并且 P1 在 P3 完成其临界区之前再次需要访问。如果操作系统在 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] 设置为真。

P1 将 flag[1] 设置为真。

P0 检查标志[1]。

P1 检查标志[0]。

P0 将 flag[0] 设置为 false。

P1 将 flag[1] 设置为 false。

P0 将 flag[0] 设置为真。

P1 将 flag[1] 设置为真。

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

不再是书中的内容。

那么自旋锁呢？

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

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-lightweight-mutex/
Is my spin lock implementation correct and optimal?

概括：

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

Livelock：没有人进展，但 CPU 用于锁定机制而不是您的计算的情况；

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

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

---

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

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

---

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

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。它们都是 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，它能够持有锁。它这样做，执行 synchronised 块，并将 commonVar 设置回 false。现在，线程 A 再次获得它的新 CPU 窗口，它正要退出 while 循环，但线程 B 刚刚将其设置回 false，因此循环再次重复。线程做一些事情（所以它们不会在传统意义上被阻塞）但几乎没有。

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

---

我只是打算分享一些知识。

死锁 如果集合中的每个线程/进程都在等待只有该集合中的另一个进程可以引发的事件，那么一组线程/进程就会死锁。

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

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

必须满足这四个条件才有死锁。

互斥条件（每个资源分配给1个进程） 保持等待条件（进程持有资源，同时可以请求其他资源）。无抢占条件（不能强行夺走之前授予的资源） # 它会动态发生

如果我们找到了这些条件，那么我们可以说可能会发生像死锁这样的情况。

活锁

每个线程/进程一次又一次地重复相同的状态，但没有进一步进展。由于进程无法进入临界区，因此类似于死锁。然而，在死锁中，进程处于等待状态，除了在活锁中之外什么都不做，进程试图继续，但进程一次又一次地重复到相同的状态。

（在死锁计算中，没有可能成功的执行序列。但在活锁计算中，有成功的计算，但是有一个或多个执行序列，其中没有进程进入其临界区。）

死锁和活锁的区别

当死锁发生时，不会发生执行。但是在活锁中，会发生一些执行，但这些执行不足以进入临界区。

---