BlockingQueues and thread access order

Question

I have a situation where multiple threads will be polling a single BlockingQueue by calling take(). What I want to know is the following:

If multiple threads are waiting for the queue to receive an item, will they be given priority for taking items off the queue in the order that they made their calls to take() or will the order in which the threads take things off the queue be arbitrary?

Thanks!

Note: I have written my own implementations for this kind of thing in the past, but I'm wondering if the BlockingQueue implementations in Java would do this for me.

In general any multithreaded application should not make any assumptions about the order of thread execution. There are ways to enforce it, but the idea behind MT applications is that it should not be done. — Dariusz, Aug 27 '13 at 14:19
Interesting question, I've written and ran a program - there is no fixed order. — Tala, Aug 27 '13 at 14:19
[Related question](http://stackoverflow.com/questions/1301691/java-queue-implementations-which-one) which also discusses fairness. — Josef Borkovec, Aug 27 '13 at 14:23

score 5 · Accepted Answer · answered Aug 27 '13 at 14:16

It depends on the implementation.

If you use a LinkedBlockingQueue, the take() method checks with a ReentrantLock

public E take() throws InterruptedException {
    E x;
    int c = -1;
    final AtomicInteger count = this.count;
    final ReentrantLock takeLock = this.takeLock;
    takeLock.lockInterruptibly();
    ...
}

// declared as
private final ReentrantLock takeLock = new ReentrantLock(); // no fairness argument, defaults to false

The javadoc says

The constructor for this class accepts an optional fairness parameter. When set true, under contention, locks favor granting access to the longest-waiting thread. Otherwise this lock does not guarantee any particular access order. Programs using fair locks accessed by many threads may display lower overall throughput (i.e., are slower; often much slower) than those using the default setting, but have smaller variances in times to obtain locks and guarantee lack of starvation. Note however, that fairness of locks does not guarantee fairness of thread scheduling. Thus, one of many threads using a fair lock may obtain it multiple times in succession while other active threads are not progressing and not currently holding the lock. Also note that the untimed tryLock method does not honor the fairness setting. It will succeed if the lock is available even if other threads are waiting.

score 2 · Answer 2 · answered Aug 27 '13 at 14:15

In many cases the javadocs mention if the class is "fair", i.e. the blocking is distributed so that all threads get the same chance. This doesn't necessary mean the same as "gets in the same order" however. Check the javadocs for your particular queue implementation to see whether it has information on fairness and/or order.

At least ArrayBlockingQueue informs of the fairness as follows:

This class supports an optional fairness policy for ordering waiting producer and consumer threads. By default, this ordering is not guaranteed. However, a queue constructed with fairness set to true grants threads access in FIFO order. Fairness generally decreases throughput but reduces variability and avoids starvation.

score 1 · Answer 3 · answered Aug 27 '13 at 14:22

It depends on the implementation, whether a class supports an optional fairness policy for ordering waiting producer and consumer threads or not. E.g. ArrayBlockingQueue can be fair since it has constructor ArrayBlockingQueue(int capacity, boolean fair), but LinkedBlockingQueue cant.

BlockingQueues and thread access order

3 Answers3