Возникает DeadLock при одновременном нажатии и извлечении элемента из списка

Question

Целью следующего кода является реализация контейнера 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();
    }
}  

}

но тупик может возникать всякий раз, когда вызывается pop (), когда в списке нет элемента. Как изменить этот класс для достижения первоначальной цели, избегая при этом потенциального тупика. Спасибо

Answer 1

В этом классе я бы изменил так много вещей, что трудно понять, с чего начать. Это самое простое решение - удалить блоки synchronized(list), поскольку они являются избыточными и, как вы можете видеть, просто вызывают проблемы.

Другим решением было бы использование класса Stack, встроенного в Java. Ваш класс может быть сбит с толку за встроенный, так как он имеет то же имя.

Или я бы использовал LinkedBlockingDeque, который является потокобезопасным в качестве моей коллекции и имеет методы pop () и push ().

РЕДАКТИРОВАТЬ: Если вы хотите знать, почему вы получаете мертвую блокировку, это потому, что вы держите две блокировки (одна в стеке, другая в LinkedList), но вы отпускаете только одну блокировку с вашим ожиданием () (тот, что в стеке), что означает, что никакой другой поток не может получить блокировку в списке. Нет возможности 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

Ваша проблема - это совокупность проблем.

Во-первых, ваш код получает две блокировки для каждого метода - одну в стеке и одну в списке. Когда вызывается «wait», тот, кто находится в стеке, освобождается, а тот, что в списке, - нет. Это предотвратит выполнение любых других методов. Это фактически тупик. (Спасибо, Питер Лори)

Во-вторых код:

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

приведет к тому, что попытка всплывающего окна будет ждать нажатия, прежде чем продолжить. Это может показаться тупиковым, но на самом деле это просто ожидание. Однако звонок

уведомить ();

разбудит только одну нить. Если более одного потока ожидает появления, все, кроме одного, продолжат ожидание. Это похоже на тупик (хотя технически это не так).

Исправления, которые вы должны сделать с этим кодом:

• избавиться от двойной синхронизации. Вам нужен либо метод синхронизации, либо синхронизация (список), а не оба.
• используйте «notifyAll () вместо« notify () »и соедините его с использованием« while »вместо« if »во время ожидания.

Также гораздо более нормально, чтобы стек выдавал исключение, если на нем нет элементов, вместо того, чтобы ждать нажатия.

Answer 3

Проблема в том, что вы синхронизируете два разных объекта: в экземпляре стека (через ключевое слово synchronized в обоих методах) и в списке (через операторы synchronized (list))

когда метод pop ожидает, он вызывает wait для экземпляра стека и, таким образом, освобождает монитор, который он хранит в экземпляре стека, позволяя другому потоку войти в метод push.Но он не освобождает монитор, который находится в списке, поэтому другой поток блокируется в ожидании освобождения монитора в списке.

Answer 4

Это то, что происходит, когда вы вызываете pop в пустом стеке, а затем отправляете из другого потока.
wait() в pop находится в блоке synchronized, поэтому вызов push из другого потока будет ждатьдля возврата метода pop, но pop заблокирован в ожидании push, и вы получили тупик.