Реализация параллельной очереди с двумя замками

Question

Я пытаюсь реализовать параллельную очередь с двумя блокировками в Java, но не могу заставить ее пройти автоматические тесты. Пожалуйста, дайте мне знать об ошибках в моем коде:

private static class Link<L> {
    L val;
    Link<L> next;
    Link(L val) { this.val = val; this.next = null; }
}
T v;
private Link<T> initNode = new Link<T> (v);
private Link<T> first = initNode;
private Link<T> last = initNode;

public void enque(T val) {
    Link<T> newLink = new Link<T> (val);
    synchronized (this.last) {
        last.next = newLink;
        last = newLink;
    }
}

public T deque() {
    synchronized (this.first) {
        Link<T> new_head = first.next;
        if (new_head == null)
            return null;
        T rtnVal = new_head.val;
        first = new_head;
        return rtnVal;
    }
}

Answer 1

Самая большая проблема здесь заключается в том, что вы меняете, какой объект синхронизируется. То, что в итоге происходит, действительно недетерминировано.

В вашем синхронизированном блоке у вас есть:

synchronized (this.last) {
    last.next = newLink;
    last = newLink;
}

Поскольку последний изменяется, другой поток может ввести метод enque и одновременно войти в синхронизированный блок. Лучше всего иметь два объекта для блокировки:

private final Object ENQUEUE_LOCK = new Object();
private final Object DEQUEUE_LOCK = new Object();

Я не знаю, обязательно ли по этой причине ваши тесты не выполняются, но это решило бы проблему параллелизма.

Редактировать: Оказывается, по крайней мере для меня и моего тестирования наличие двух выделенных блокировок решает странные проблемы, которые я видел с очередью.