摘自http://en.wikipedia.org/wiki/Deadlock:

In concurrent computing, a deadlock is a state in which each member of a group of actions, is waiting for some other member to release a lock A livelock is 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.

死锁 死锁是一种任务等待的情况 永远不可能发生的情况 满意 - task要求独占共享的控制权 资源 - task在等待其他任务时持有资源 待释放资源 —不能强制任务放弃资源 —存在循环等待条件

活锁 当两个或 更多的任务依赖和使用some 资源导致循环依赖 这些任务继续执行的条件 永远的奔跑，因此阻挡了一切的下降 优先级任务从运行(这些 低优先级任务出现问题 称为饥饿)

活锁

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

livelock和死锁之间的主要区别是线程不会被阻塞，相反，它们会尝试连续地相互响应。

在此图像中，两个圆圈(线程或进程)都将尝试通过左右移动为另一个圆圈提供空间。但是他们不能再前进了。

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

操作系统:内部原理和设计原则 威廉切除 8º版

死锁:两个或多个进程无法继续进行的情况，因为每个进程都在等待另一个进程执行某项操作。

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

Livelock:两个或多个进程不断地改变它们的状态以响应其他进程的变化而不做任何有用的工作的情况:

饥饿:一种可运行进程被调度程序无限期忽略的情况;虽然它可以继续，但它永远不会被选择。

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.

附录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设置标志[0]为true。 P1设置标志[1]为true。 P0检查标志[1]。 P1检查标志[0]。 P0设置标志[0]为false。 P1设置标志[1]为false。 P0设置标志[0]为true。 P1设置标志[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.

不再满足于书本。

那么自旋锁呢?

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

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

如果您的实现不小心，您可能会使用livelock，将所有CPU都花费在锁机制上。

还看到:

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

简介:

僵局:没有人取得进展，什么也不做(睡觉，等待等)的情况。CPU使用率将较低;

Livelock:没有人进展的情况，但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

---

实例:

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

这两个示例都强制线程以不同的顺序获取锁。 当死锁等待另一个锁时， livelock并不真正等待——它拼命地试图获得锁，却没有机会得到它。每次尝试都会消耗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
         }
    }
}

So, when thread A enters in the while loop and holds the lock, it does what it has to do and set the commonVar to true. Then thread B comes in, enters in the while loop and since commonVar is true now, it is be able to hold the lock. It does so, executes the synchronised block, and sets commonVar back to false. Now, thread A again gets it's new CPU window, it was about to quit the while loop 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.

提到livelock不一定要出现在这里可能也不错。我假设调度程序倾向于另一个线程一旦同步块完成执行。大多数时候，我认为这是一个难以实现的期望，取决于许多事情发生在引擎盖下。

我只是想分享一些知识。

死锁 如果一组线程/进程中的每个线程/进程都在等待一个只有该组中的另一个进程才能引起的事件，则该组线程/进程被称为死锁。

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

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

要产生死锁，必须满足这四个条件。

互斥条件(每个资源分配给1个进程) 保持和等待状态(处理持有资源，同时可以请求其他资源)。 没有抢占条件(以前授予的资源不能被强制拿走)#这个条件取决于应用程序 循环等待条件(必须是由2个或更多进程组成的循环链，每个进程都在等待链的下一个成员所持有的资源)#它将动态发生

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

活锁

每个线程/进程一次又一次地重复相同的状态，但没有进一步的进展。类似于死锁，因为进程不能进入临界区。然而，在死锁中，进程在等待而不做任何事情，但在livelock中，进程试图继续，但进程一次又一次地重复到相同的状态。

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

不同于死锁和活锁

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