这是活锁的好例子吗？

小开

抛开轻率的注释不谈，众所周知的一个例子是尝试检测和处理死锁情况的代码。如果两个线程检测到一个死锁，并试图为对方“退一步”，毫不在意，它们最终将陷入一个总是“退一步”的循环，永远无法前进。

我所说的“让开”是指他们会解开锁，试图让另一个人得到它。我们可以想象两个线程这样做的情形(伪代码) :

// thread 1
getLocks12(lock1, lock2)
{
lock1.lock();
while (lock2.locked())
{
// attempt to step aside for the other thread
lock1.unlock();
wait();
lock1.lock();
}
lock2.lock();
}


// thread 2
getLocks21(lock1, lock2)
{
lock2.lock();
while (lock1.locked())
{
// attempt to step aside for the other thread
lock2.unlock();
wait();
lock2.lock();
}
lock1.lock();
}

抛开竞争条件不谈，我们这里的情况是，如果两个线程同时进入，那么它们最终将在内部循环中运行而不继续。显然，这是一个简化的例子。天真的修复方法是在线程等待的时间长度中加入某种随机性。

正确的解决方法是始终尊重封闭的等级制度。选择一个获取锁的顺序，并坚持这个顺序。例如，如果两个线程总是在 lock2之前获取 lock1，那么就不存在死锁的可能性。

小开

这里的一个示例可能是使用一个计时 tryLock 来获取多个锁，如果无法获取所有锁，请退后并重试。

boolean tryLockAll(Collection<Lock> locks) {
boolean grabbedAllLocks = false;
for(int i=0; i<locks.size(); i++) {
Lock lock = locks.get(i);
if(!lock.tryLock(5, TimeUnit.SECONDS)) {
grabbedAllLocks = false;


// undo the locks I already took in reverse order
for(int j=i-1; j >= 0; j--) {
lock.unlock();
}
}
}
}

我可以想象这样的代码会有问题，因为您有许多线程发生冲突并等待获得一组锁。但作为一个简单的例子，我不确定这是否能引起我的注意。

小开

一个真实的(尽管没有精确的代码)示例是两个相互竞争的进程实时锁定，试图纠正 SQL 服务器死锁，每个进程使用相同的等待重试算法进行重试。虽然这是时机的巧合，但我见过这种情况发生在不同的机器上，这些机器具有相似的性能特征，以响应添加到 EMS 主题的消息(例如，多次保存单个对象图的更新) ，并且无法控制锁定顺序。

在这个的情况下，一个好的解决方案是拥有相互竞争的消费者(通过将工作分区到不相关的对象上来防止重复处理在链的尽可能高的位置)。

一个不太理想的解决方案(好吧，脏黑客)是提前打破计时坏运气(处理过程中的力量差异) ，或者在死锁之后通过使用不同的算法或一些随机因素来打破它。这可能仍然存在问题，因为对于每个进程，接受锁的顺序可能是“粘性的”，并且这需要一定的最小时间，而等待重试中没有考虑到这一点。

另一种解决方案(至少对于 SQLServer)是尝试不同的隔离级别(例如快照)。

小开

这里有一个非常简单的关于 livelock 的 Java 例子，一对夫妇正在尝试喝汤，但是他们之间只有一个勺子。夫妻双方都太有礼貌了，如果对方还没有吃饭，他们就会把勺子递给对方。

public class Livelock {
static class Spoon {
private Diner owner;
public Spoon(Diner d) { owner = d; }
public Diner getOwner() { return owner; }
public synchronized void setOwner(Diner d) { owner = d; }
public synchronized void use() {
System.out.printf("%s has eaten!", owner.name);
}
}
    

static class Diner {
private String name;
private boolean isHungry;
        

public Diner(String n) { name = n; isHungry = true; }
public String getName() { return name; }
public boolean isHungry() { return isHungry; }
        

public void eatWith(Spoon spoon, Diner spouse) {
while (isHungry) {
// Don't have the spoon, so wait patiently for spouse.
if (spoon.owner != this) {
try { Thread.sleep(1); }
catch(InterruptedException e) { continue; }
continue;
}
            

// If spouse is hungry, insist upon passing the spoon.
if (spouse.isHungry()) {
System.out.printf(
"%s: You eat first my darling %s!%n",
name, spouse.getName());
spoon.setOwner(spouse);
continue;
}
                

// Spouse wasn't hungry, so finally eat
spoon.use();
isHungry = false;
System.out.printf(
"%s: I am stuffed, my darling %s!%n",
name, spouse.getName());
spoon.setOwner(spouse);
}
}
}
    

public static void main(String[] args) {
final Diner husband = new Diner("Bob");
final Diner wife = new Diner("Alice");
        

final Spoon s = new Spoon(husband);
        

new Thread(new Runnable() {
public void run() { husband.eatWith(s, wife); }
}).start();


new Thread(new Runnable() {
public void run() { wife.eatWith(s, husband); }
}).start();
}
}

运行程序，你会得到:

Bob: You eat first my darling Alice!
Alice: You eat first my darling Bob!
Bob: You eat first my darling Alice!
Alice: You eat first my darling Bob!
Bob: You eat first my darling Alice!
Alice: You eat first my darling Bob!
...

如果不被打扰，这将永远持续下去。这是一个活锁，因为 Alice 和 Bob 都反复要求对方在无限循环中先开始(因此是 活下去)。在陷入僵局的情况下，Alice 和 Bob 都会被冻结，只能等待对方先走ーー除了等待(因此是死了) ，他们不会做任何事情。

小开

Jelbourne 代码的 Python 版本:

import threading
import time
lock = threading.Lock()


class Spoon:
def __init__(self, diner):
self.owner = diner


def setOwner(self, diner):
with lock:
self.owner = diner


def use(self):
with lock:
"{0} has eaten".format(self.owner)


class Diner:
def __init__(self, name):
self.name = name
self.hungry = True


def eatsWith(self, spoon, spouse):
while(self.hungry):
if self != spoon.owner:
time.sleep(1) # blocks thread, not process
continue


if spouse.hungry:
print "{0}: you eat first, {1}".format(self.name, spouse.name)
spoon.setOwner(spouse)
continue


# Spouse was not hungry, eat
spoon.use()
print "{0}: I'm stuffed, {1}".format(self.name, spouse.name)
spoon.setOwner(spouse)


def main():
husband = Diner("Bob")
wife = Diner("Alice")
spoon = Spoon(husband)


t0 = threading.Thread(target=husband.eatsWith, args=(spoon, wife))
t1 = threading.Thread(target=wife.eatsWith, args=(spoon, husband))
t0.start()
t1.start()
t0.join()
t1.join()


if __name__ == "__main__":
main()

小开

我编写了两个人在走廊上经过的例子。一旦两条线意识到它们的方向是一样的，它们就会避开对方。

public class LiveLock {
public static void main(String[] args) throws InterruptedException {
Object left = new Object();
Object right = new Object();
Pedestrian one = new Pedestrian(left, right, 0); //one's left is one's left
Pedestrian two = new Pedestrian(right, left, 1); //one's left is two's right, so have to swap order
one.setOther(two);
two.setOther(one);
one.start();
two.start();
}
}


class Pedestrian extends Thread {
private Object l;
private Object r;
private Pedestrian other;
private Object current;


Pedestrian (Object left, Object right, int firstDirection) {
l = left;
r = right;
if (firstDirection==0) {
current = l;
}
else {
current = r;
}
}


void setOther(Pedestrian otherP) {
other = otherP;
}


Object getDirection() {
return current;
}


Object getOppositeDirection() {
if (current.equals(l)) {
return r;
}
else {
return l;
}
}


void switchDirection() throws InterruptedException {
Thread.sleep(100);
current = getOppositeDirection();
System.out.println(Thread.currentThread().getName() + " is stepping aside.");
}


public void run() {
while (getDirection().equals(other.getDirection())) {
try {
switchDirection();
Thread.sleep(100);
} catch (InterruptedException e) {}
}
}
}

小开

C # 版本的杰尔伯恩代码:

using System;
using System.Runtime.CompilerServices;
using System.Threading;
using System.Threading.Tasks;


namespace LiveLockExample
{
static class Program
{
public static void Main(string[] args)
{
var husband = new Diner("Bob");
var wife = new Diner("Alice");


var s = new Spoon(husband);


Task.WaitAll(
Task.Run(() => husband.EatWith(s, wife)),
Task.Run(() => wife.EatWith(s, husband))
);
}


public class Spoon
{
public Spoon(Diner diner)
{
Owner = diner;
}




public Diner Owner { get; private set; }


[MethodImpl(MethodImplOptions.Synchronized)]
public void SetOwner(Diner d) { Owner = d; }


[MethodImpl(MethodImplOptions.Synchronized)]
public void Use()
{
Console.WriteLine("{0} has eaten!", Owner.Name);
}
}


public class Diner
{
public Diner(string n)
{
Name = n;
IsHungry = true;
}


public string Name { get; private set; }


private bool IsHungry { get; set; }


public void EatWith(Spoon spoon, Diner spouse)
{
while (IsHungry)
{
// Don't have the spoon, so wait patiently for spouse.
if (spoon.Owner != this)
{
try
{
Thread.Sleep(1);
}
catch (ThreadInterruptedException e)
{
}


continue;
}


// If spouse is hungry, insist upon passing the spoon.
if (spouse.IsHungry)
{
Console.WriteLine("{0}: You eat first my darling {1}!", Name, spouse.Name);
spoon.SetOwner(spouse);
continue;
}


// Spouse wasn't hungry, so finally eat
spoon.Use();
IsHungry = false;
Console.WriteLine("{0}: I am stuffed, my darling {1}!", Name, spouse.Name);
spoon.SetOwner(spouse);
}
}
}
}
}

小开

我修改了@jelbourne 的答案。当其中一个发现另一个饿了，他(她)应该放开勺子，等待另一个通知，这样就发生了一只活骆驼。

public class LiveLock {
static class Spoon {
Diner owner;


public String getOwnerName() {
return owner.getName();
}


public void setOwner(Diner diner) {
this.owner = diner;
}


public Spoon(Diner diner) {
this.owner = diner;
}


public void use() {
System.out.println(owner.getName() + " use this spoon and finish eat.");
}
}


static class Diner {
public Diner(boolean isHungry, String name) {
this.isHungry = isHungry;
this.name = name;
}


private boolean isHungry;
private String name;




public String getName() {
return name;
}


public void eatWith(Diner spouse, Spoon sharedSpoon) {
try {
synchronized (sharedSpoon) {
while (isHungry) {
while (!sharedSpoon.getOwnerName().equals(name)) {
sharedSpoon.wait();
//System.out.println("sharedSpoon belongs to" + sharedSpoon.getOwnerName())
}
if (spouse.isHungry) {
System.out.println(spouse.getName() + "is hungry,I should give it to him(her).");
sharedSpoon.setOwner(spouse);
sharedSpoon.notifyAll();
} else {
sharedSpoon.use();
sharedSpoon.setOwner(spouse);
isHungry = false;
}
Thread.sleep(500);
}
}
} catch (InterruptedException e) {
System.out.println(name + " is interrupted.");
}
}
}


public static void main(String[] args) {
final Diner husband = new Diner(true, "husband");
final Diner wife = new Diner(true, "wife");
final Spoon sharedSpoon = new Spoon(wife);


Thread h = new Thread() {
@Override
public void run() {
husband.eatWith(wife, sharedSpoon);
}
};
h.start();


Thread w = new Thread() {
@Override
public void run() {
wife.eatWith(husband, sharedSpoon);
}
};
w.start();


try {
Thread.sleep(10000);
} catch (InterruptedException e) {
e.printStackTrace();
}
h.interrupt();
w.interrupt();


try {
h.join();
w.join();
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}

小开

package concurrently.deadlock;


import static java.lang.System.out;




/* This is an example of livelock */
public class Dinner {


public static void main(String[] args) {
Spoon spoon = new Spoon();
Dish dish = new Dish();


new Thread(new Husband(spoon, dish)).start();
new Thread(new Wife(spoon, dish)).start();
}
}




class Spoon {
boolean isLocked;
}


class Dish {
boolean isLocked;
}


class Husband implements Runnable {


Spoon spoon;
Dish dish;


Husband(Spoon spoon, Dish dish) {
this.spoon = spoon;
this.dish = dish;
}


@Override
public void run() {


while (true) {
synchronized (spoon) {
spoon.isLocked = true;
out.println("husband get spoon");
try { Thread.sleep(2000); } catch (InterruptedException e) {}


if (dish.isLocked == true) {
spoon.isLocked = false; // give away spoon
out.println("husband pass away spoon");
continue;
}
synchronized (dish) {
dish.isLocked = true;
out.println("Husband is eating!");


}
dish.isLocked = false;
}
spoon.isLocked = false;
}
}
}


class Wife implements Runnable {


Spoon spoon;
Dish dish;


Wife(Spoon spoon, Dish dish) {
this.spoon = spoon;
this.dish = dish;
}


@Override
public void run() {
while (true) {
synchronized (dish) {
dish.isLocked = true;
out.println("wife get dish");
try { Thread.sleep(2000); } catch (InterruptedException e) {}


if (spoon.isLocked == true) {
dish.isLocked = false; // give away dish
out.println("wife pass away dish");
continue;
}
synchronized (spoon) {
spoon.isLocked = true;
out.println("Wife is eating!");


}
spoon.isLocked = false;
}
dish.isLocked = false;
}
}
}

小开

由于没有标记为接受答案的答案，我尝试创建实时锁示例;

最初的程序是我在2012年4月写的，目的是学习多线程的各种概念。这次我修改了它来创建死锁、竞争条件、活锁等。

因此，让我们首先理解问题陈述;

饼干机问题

有一些成分容器: 巧克力容器，麦粉盒。饼干机从成分容器中取出一定量的粉末来烘烤饼干。如果一个 cookie 制造者发现一个容器是空的，它会检查另一个容器以节省时间。并等待 填充物填满所需的容器。有一个 填充物谁定期检查容器，并填补了一些数量，如果容器需要它。

请检查 Github上的完整代码;

让我简单地解释一下实现。

我将 填充物作为守护进程线程启动。因此，它将保持定期填充容器。要先装满一个容器，它会锁住容器—— > 检查是否需要一些粉末—— > 装满容器—— > 向所有等待的制造商发出信号—— > 解锁容器。
我创建了 饼干机，并设置它可以同时烤8个饼干。我开了8个线程来烤饼干。
每个制造者线程创建2个可调用的子线程，以采取粉从容器。
子线程需要一个容器上的锁，并检查是否有足够的粉末。如果没有，等待一段时间。一旦填料装满容器，它采取粉末，并打开容器。
现在它完成了其他的活动，比如: 制作混合物和烘焙等等。

让我们看看代码:

CookieMaker.java

private Integer getMaterial(final Ingredient ingredient) throws Exception{
:
container.lock();
while (!container.getIngredient(quantity)) {
container.empty.await(1000, TimeUnit.MILLISECONDS);
//Thread.sleep(500); //For deadlock
}
container.unlock();
:
}

Java

public boolean getIngredient(int n) throws Exception {
:
lock();
if (quantityHeld >= n) {
TimeUnit.SECONDS.sleep(2);
quantityHeld -= n;
unlock();
return true;
}
unlock();
return false;
}

一切运行良好，直到 填充物填满容器。但是，如果我忘记开始填料，或填料进行意外休假，子线程不断改变他们的状态，以允许其他制造商去检查容器。

我还创建了一个守护程序线索追踪器，它可以监视线程状态和死锁

2016-09-12 21:31:45.065 :: [Maker_0:WAITING, Maker_1:WAITING, Maker_2:WAITING, Maker_3:WAITING, Maker_4:WAITING, Maker_5:WAITING, Maker_6:WAITING, Maker_7:WAITING, pool-7-thread-1:TIMED_WAITING, pool-7-thread-2:TIMED_WAITING, pool-8-thread-1:TIMED_WAITING, pool-8-thread-2:TIMED_WAITING, pool-6-thread-1:TIMED_WAITING, pool-6-thread-2:TIMED_WAITING, pool-5-thread-1:TIMED_WAITING, pool-5-thread-2:TIMED_WAITING, pool-1-thread-1:TIMED_WAITING, pool-3-thread-1:TIMED_WAITING, pool-2-thread-1:TIMED_WAITING, pool-1-thread-2:TIMED_WAITING, pool-4-thread-1:TIMED_WAITING, pool-4-thread-2:RUNNABLE, pool-3-thread-2:TIMED_WAITING, pool-2-thread-2:TIMED_WAITING]
2016-09-12 21:31:45.065 :: [Maker_0:WAITING, Maker_1:WAITING, Maker_2:WAITING, Maker_3:WAITING, Maker_4:WAITING, Maker_5:WAITING, Maker_6:WAITING, Maker_7:WAITING, pool-7-thread-1:TIMED_WAITING, pool-7-thread-2:TIMED_WAITING, pool-8-thread-1:TIMED_WAITING, pool-8-thread-2:TIMED_WAITING, pool-6-thread-1:TIMED_WAITING, pool-6-thread-2:TIMED_WAITING, pool-5-thread-1:TIMED_WAITING, pool-5-thread-2:TIMED_WAITING, pool-1-thread-1:TIMED_WAITING, pool-3-thread-1:TIMED_WAITING, pool-2-thread-1:TIMED_WAITING, pool-1-thread-2:TIMED_WAITING, pool-4-thread-1:TIMED_WAITING, pool-4-thread-2:TIMED_WAITING, pool-3-thread-2:TIMED_WAITING, pool-2-thread-2:TIMED_WAITING]
WheatPowder Container has 0 only.
2016-09-12 21:31:45.082 :: [Maker_0:WAITING, Maker_1:WAITING, Maker_2:WAITING, Maker_3:WAITING, Maker_4:WAITING, Maker_5:WAITING, Maker_6:WAITING, Maker_7:WAITING, pool-7-thread-1:TIMED_WAITING, pool-7-thread-2:TIMED_WAITING, pool-8-thread-1:TIMED_WAITING, pool-8-thread-2:TIMED_WAITING, pool-6-thread-1:TIMED_WAITING, pool-6-thread-2:TIMED_WAITING, pool-5-thread-1:TIMED_WAITING, pool-5-thread-2:TIMED_WAITING, pool-1-thread-1:TIMED_WAITING, pool-3-thread-1:TIMED_WAITING, pool-2-thread-1:TIMED_WAITING, pool-1-thread-2:TIMED_WAITING, pool-4-thread-1:TIMED_WAITING, pool-4-thread-2:TIMED_WAITING, pool-3-thread-2:TIMED_WAITING, pool-2-thread-2:RUNNABLE]
2016-09-12 21:31:45.082 :: [Maker_0:WAITING, Maker_1:WAITING, Maker_2:WAITING, Maker_3:WAITING, Maker_4:WAITING, Maker_5:WAITING, Maker_6:WAITING, Maker_7:WAITING, pool-7-thread-1:TIMED_WAITING, pool-7-thread-2:TIMED_WAITING, pool-8-thread-1:TIMED_WAITING, pool-8-thread-2:TIMED_WAITING, pool-6-thread-1:TIMED_WAITING, pool-6-thread-2:TIMED_WAITING, pool-5-thread-1:TIMED_WAITING, pool-5-thread-2:TIMED_WAITING, pool-1-thread-1:TIMED_WAITING, pool-3-thread-1:TIMED_WAITING, pool-2-thread-1:TIMED_WAITING, pool-1-thread-2:TIMED_WAITING, pool-4-thread-1:TIMED_WAITING, pool-4-thread-2:TIMED_WAITING, pool-3-thread-2:TIMED_WAITING, pool-2-thread-2:TIMED_WAITING]

您会注意到，子线程和改变他们的状态和等待。

小开

考虑一个有50个进程槽的 UNIX 系统。

正在运行的程序有10个，每个程序都必须创建6个(子)进程。

在每个进程创建了4个进程之后，10个原始进程和40个新进程用完了表。原来的10个进程现在每一个都处于无休止的循环分叉和失败之中——这恰好是一个活骆驼的情况。这种情况发生的可能性很小，但它可能会发生。

小开

例如:

线程1

top:
lock(L1);
if (try_lock(L2) != 0) {
unlock(L1);
goto top;

线程2

top:
lock(L2);
if (try_lock(L1) != 0) {
unlock(L2);
goto top;

唯一的区别是 Thread1和 Thread2尝试以不同的顺序获取锁。Livelock 可能会发生以下情况:

线程1运行获取 L1，然后发生上下文切换。线程2运行获取 L2，然后发生另一个上下文切换。线程1运行并且不能获得 L2，但是在释放 L1之前会发生上下文切换。线程2运行并且不能获取 L1，释放 L2，并且发生上下文切换。线程1释放了 L1，现在我们基本上回到了开始状态，理论上这些步骤可以一直重复下去。