Implementing a parallel queue with two locks

Question

I am trying to implement a parallel queue with two locks in Java, but I cannot get it to pass automatic tests. Please let me know the errors in my code:

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

The biggest problem here is that you change which object is synchronized. What ends is truly determinate.

In your synchronized block, you:

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

As the latter changes, another thread can enter the enque method and simultaneously enter a synchronized block. It is best to have two objects to block:

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

, , , concurrency.

: , , , , .