同时从列表中推入和弹出元素时发生死锁

Question

下面代码的目的是实现一个像 Stack 一样的 LIFO 容器，同时，当检索一个元素时，它会检查列表中是否有任何现有元素，或者它会保留在检索元素的线程上，直到有新的元素为止元素被插入。

public class Stack {

LinkedList list = new LinkedList();

public synchronized void push(Object x) {
    synchronized (list) {
        list.addLast(x);
        notify();
    }
}

public synchronized Object pop() throws Exception {
    synchronized (list) {
        if (list.size() <= 0) {
            wait();
        }
        return list.removeLast();
    }
}  

但是

只要在 List 中没有元素的情况下调用 pop() 就可能会发生死锁。如何修改这个类来达到最初的目的，同时避免潜在的死锁。谢谢

Answer 1

关于这门课，我要改变的事情太多了，很难知道从哪里开始。最简单的解决方案是删除 synchronized(list) 块，因为这些块是多余的，只会导致问题，如您所见。

另一种解决方案是使用 Java 内置的 Stack 类。您的类可能会与构建的类混淆，因为它具有相同的名称。

或者我会使用 LinkedBlockingDeque ，它作为我的集合是线程安全的，并且具有 pop() 和 push() 方法。

编辑：如果你想知道为什么会出现死锁，那是因为你持有两个锁（一个在堆栈上，另一个在 LinkedList 上），但你只用 wait() 释放了一个锁（一个）在堆栈上）意味着没有其他线程可以获得列表上的锁。无法同时对两个对象进行 wait()。

您的代码与此大致相同（可能更清晰）

public void push(Object x) {
  synchronized(this) {
    synchronized (list) { // cannot get a lock on `list` while pop() is called.
        list.addLast(x);
        this.notify();
    }
  }
}

public Object pop() throws Exception {
  synchronized(this) {
    synchronized (list) {
        if (list.size() <= 0) {
            this.wait(); // releases the lock on `this`, but keep the lock on `list`
        }
        return list.removeLast();
    }
  }
}

Answer 2

当您在空堆栈上调用 pop，然后从其他线程推送时，会发生这种情况。
pop 中的 wait() 位于 synchronized 块中，因此从另一个线程调用 push 将等待pop 方法返回，但是 pop 被阻塞等待 push 并且你陷入了死锁。

Answer 3

问题是您正在两个不同的对象上同步：在堆栈实例上（通过两个方法上的 synchronized 关键字）和在列表上（通过 synchronized (list) 语句）

因此，当 pop 方法等待时，它会在堆栈实例上调用 wait，从而释放它在堆栈实例上持有的监视器，从而允许另一个线程进入 push 方法。但它不会释放它在列表中持有的监视器，因此另一个线程被阻塞，等待列表上的监视器被释放。

Answer 4

你的问题是问题的组合。

首先，您的代码为每个方法获取两个锁 - 一个在堆栈上，一个在列表上。当调用“wait”时，堆栈上的那个被释放，但列表上的那个没有被释放。这将阻止执行任何其他方法。这实际上是一个僵局。 （感谢 Peter Lawrey）

其次，代码：

if (list.size() <= 0) {
   wait();
}

将导致尝试弹出操作等待推送，然后再继续。这看起来像是一个僵局，但实际上只是等待。然而调用

notify();

只会唤醒一个线程。如果有多个线程正在等待弹出，则除一个之外的所有线程都将继续等待。这看起来更像是一个僵局（尽管从技术上来说并非如此）。

您应该对此代码进行修复：

• 摆脱双重同步。您需要同步方法或同步（列表）方法，而不是两者都需要。
• 使用“notifyAll()”而不是“notify()”，并在等待时使用“while”而不是“if”。

如果堆栈上没有项目，则抛出异常比堆栈抛出异常更正常。等待推动。