Java Blocking Queue Implementation Questions

Question

The common implementation is here, Java's built-in implementation is here. I have two questions regarding these two implementations:

1) The first implementation use synchronized key word on put() and take() methods, which means only one thread can access one method. Let's say if thread A call put() and found the queue is full, so it's waiting, then no one can ever call take() method since the lock is not released yet, how can the implementation be used?

2) Java's built-in uses two locks: takeLock and putLock, and used in put() and take() respectively. I saw that the interval queue is a linked list, which is not thread-safe, how can that be done?

for 1: Waiting releases the lock, so it doesn't block other threads from taking. — Nathan Hughes
– Nathan Hughes, Commented Apr 9, 2015 at 15:15
Your assumption in #1 is wrong: Invoking wait() actually releases the lock for that thread. Another thread can then capture the lock in the take() method, and the thread stuck in put() will be awakened when notifyAll() is called by a different thread. — Platinum Azure
– Platinum Azure, Commented Apr 9, 2015 at 15:15

hemant1900 · Accepted Answer · 2015-04-09 16:34:09Z

1

As already mentioned in some of the comments the first implementation just uses traditional wait()/notify() mechanism where one thread waits (and of course releasing lock) for being notified by other threads.

The second one uses different locks each for put and take operations. So the individual operations (simultaneous put() or take()) are synchronous. But they need to communicate with each other when queue is full or empty. So they interact with each other through condition. Checkout the two private methods-

    /**
     * Signals a waiting take. Called only from put/offer (which do not
     * otherwise ordinarily lock takeLock.)
     */
    private void signalNotEmpty() {
        final ReentrantLock takeLock = this.takeLock;
        takeLock.lock();
        try {
            notEmpty.signal();
        } finally {
            takeLock.unlock();
        }
    }

    /**
     * Signals a waiting put. Called only from take/poll.
     */
    private void signalNotFull() {
        final ReentrantLock putLock = this.putLock;
        putLock.lock();
        try {
            notFull.signal();
        } finally {
            putLock.unlock();
        }
    }

put method signals other threads trying to take/poll from empty queue and take method signals other threads trying to put elements into full queue.

answered Apr 9, 2015 at 16:34

hemant1900

1,2268 silver badges9 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Leo Li Over a year ago

Thanks, I was trying to understand how do two locks guarantee thread-safety, double check the code, found put/take operations are performed on two nodes (head/tail respectively), which explains everything.

Collectives™ on Stack Overflow

Java Blocking Queue Implementation Questions

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related