活锁的好例子？

Question

我理解livelock是什么,但我想知道是否有人有一个很好的基于代码的例子呢？以代码为基础,我并不是说"两个人试图在走廊里相互过去".如果我再读一遍,我会失去午餐.

Answer 1

这是一个非常简单的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();
    }
}

Answer 2

抛开轻率的评论,已知的一个例子是代码,它试图检测和处理死锁情况.如果两个线程检测到死锁,并试图为彼此"撇开",他们会毫不在意地陷入一个循环中,总是"踩到一边"并且永远无法向前移动.

通过"退出"我的意思是他们会释放锁并试图让另一个人获得它.我们可以想象两个线程这样做的情况(伪代码):

// 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,则不存在死锁的可能性.

Answer 3

由于没有标记为已接受答案的答案,我试图创建实时锁定示例;

原创程序是我在2012年4月编写的,用于学习多线程的各种概念.这次我修改它以创建死锁,竞争条件,活锁等.

所以让我们首先理解问题陈述;

Cookie Maker问题

有一些配料容器:ChocoPowederContainer,WheatPowderContainer.CookieMaker从配料容器中取出一定量的粉末来烘焙饼干.如果cookie制造商发现容器为空,则检查另一个容器以节省时间.等到Filler填满所需的容器.有一个填充程序定期检查容器,并在容器需要时填充一些数量.

请检查github上的完整代码;

让我简要解释一下实施情况.

• 我启动Filler作为守护程序线程.所以它会定期灌装容器.要首先填充容器,它会锁定容器 - >检查是否需要一些粉末 - >填充它 - >发出所有等待它的制造商的信号 - >解锁容器.
• 我创建了CookieMaker并设置它可以并行烘焙多达8个cookie.我开始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();
        :
}

IngredientContainer.java

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

一切都运行良好,直到填料填充容器.但是如果我忘记启动填充物,或者填充物意外离开,则子线程会不断更改其状态以允许其他制造商去检查容器.

我还创建了一个守护进程ThreadTracer,它可以监视线程状态和死锁.这是控制台的输出;

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]

你会注意到子线程并改变它们的状态并等待.

Answer 4

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

在这种情况下，一个好的解决方案是拥有竞争的消费者（通过在不相关的对象上划分工作来尽可能防止重复处理在链的高层）。

一个不太理想的（好吧，肮脏的黑客）解决方案是提前打破定时坏运气（处理中的一种强制差异），或者通过使用不同的算法或某些随机性元素在死锁后打破它。这仍然可能存在问题，因为每个进程的锁获取顺序可能是“粘性的”，并且这需要等待重试中未考虑到的某个最短时间。

另一种解决方案（至少对于 SQL Server 而言）是尝试不同的隔离级别（例如快照）。