BlockedLinkedQueue deadlock inside synchronized method

Question

This could be a newbie question - I am running into a deadlock situation while using BlockedLinkedQueue - Here is a snipped of my code:

public class mytest {
    private BlockedLinkedQueue myQueue;

    public synchronized void consumer() {
        ...
        myQueue.take()
        ...
    }

    public synchronized void producer() {
        ...
        myQueue.put()
        ...
    }
}

I am noticing that sometimes I run into deadlock. A lot of producer() threads are waiting on the method monitor, and one consumer is blocked on take(). Is this expected? I know that I don't really have to synchronize BLockedLinkedQUeue - but I have lot of other objects and I need to synchronize these methods..

Answer 1

BlockedLinkedQueue? I think you mean LinkedBlockingQueue.

LinkedBlockingQueue is thread safe and you should not be hiding it behind the synchronization method modifiers. Removing those will may end your deadlock issue. Liberal use of synchronization is generally not a good idea--keep it to a minimum, just where you need it.

As maxkar points out, BlockingQueue.take() waits until there is something in the queue.

Retrieves and removes the head of this queue, waiting if necessary until an element becomes available.

If you are adamant about keeping the synchronization on the consumer() method in your class, consider using BlockingQueue.poll(long timeout, TimeUnit unit). This will allow you to craft logic that gracefully deals with an empty queue.

Answer 2

Yes, this deadlock is expected. It occurs when consumer() is called with the empty queue. In this case consumer() holds lock on "this" and waits for an object from myQueue. Same time any producer() can't take lock on "this" (held by consumer) and thus can't put any object to myQueue, which prevents consumer from taking an object.

To resolve deadlock, you may make only part of methods synchronized or use simple queue and implements your own waiting for a data. Example of partial synchronization:

public class mytest {
private BlockedLinkedQueue myQueue;

public void consumer() {
    synchronized(this) {
        ...
    }
    myQueue.take();
    synchronized (this) {
        ...
    }
}

public void producer() {
    synchronized(this) {
        ...
    }
    myQueue.put()
    synchronized(this) {
        ...
    }
}
}

In this case, lock on "this" is released during myQueue operation. And it will allow producer() to procede it's way and put an object to the queue.

Second example:

public class mytest {
private Queue myQueue;

public synchronized void consumer() {
    ...
    while (myQueue.isEmpty()) {
        this.wait();
    }
    myQueue.take()
    ...
}

public synchronized void producer() {
    ...
    myQueue.put()
    this.notify();
    ...
}
}

In this example lock on "this" is released during call to this.wait() (see Object.wait() for details) and it allows producer to put object to the queue. Also, producer wakes up one of consumers waiting for data.

Please, note, that in both cases producer method will be executed when only a "half" of consumer method is executed. I.e. consumer method is no more atomical at all, but only at it halfs. And if you need atomicity of the consumer, then you should think about better specification of the producer/consumer methods, because described deadlock is logical flaw in the "synchronization". You can't put object during execution of "atomic" consumer() method and at the same time consumer() requires object to be in the queue.