What’s the purpose of the PriorityBlockingQueue?

I’ve been playing with blocking queues and PriorityQueue, and it got me thinking. I can’t see a good usecase for PriorityBlockingQueue. The point of a priority queue is to sort the values put into it before they’re retrieved. A blocking queue implies that values are inserted into it and retrieved from it concurrently. But, if that’s the case, you’d never be able to guarantee the sort order.

BlockingQueue<Integer> q = new PriorityBlockingQueue<>();

new Thread (()->{ randomSleep(); q.put(2); randomSleep(); q.put(0); }).start();
new Thread (()->{ randomSleep(); q.put(3); randomSleep(); q.put(1); }).start();

ArrayList<Integer> ordered = new ArrayList<>(4);
for (int i = 0; i < 4; i++) {
    randomSleep();
    ordered.add(q.take());
}
System.out.println(ordered);

In this example, the order in which the main thread gets the offered values is quite random, which seems to defeat the purpose of a priority queue. Even with a single producer and single consumer, the order can not be ensured.

So, what is the use of PriorityBlockingQueue then?

Answer

In this example, the order in which the main thread gets the offered values is quite random

Well you have a race-condition during the insertion and the retrieve of those elements. Hence, the reason why it looks random.

Nonetheless, you could use for instance the PriorityBlockingQueue to sequentially field up with some elements (or tasks) that need to be pick up by multiple threads in parallel by their highest priority element/task. In such case you can take advantage of the thread-safe properties of a structure that guarantees you that the the highest priority element is always ordered first.

One example would be a Queue of tasks in which those tasks have a priority, and you want those same tasks to be processed in parallel.

Leave a Reply

Your email address will not be published. Required fields are marked *