Monday, October 14, 2013

PriorityBlockingQueue in Java

Priority Blocking Queue wait for the queue to become non-empty when retrieving an element, and wait for space to become available in the queue when storing an element which is not there in Priority Queue. In this post, we'll how to use PriorityBlockingQueue with examples.

In the following diagram, there is waiting room for 5 people. When it is occupied with 5 people, then 6th person will wait until any one of move of the room.



BlockingQueue interface
A Queue that additionally supports operations that wait for the queue to become non-empty when retrieving an element, and wait for space to become available in the queue when storing an element.

This interface extends the Queue interface. In BlockingQueue, if the queue is empty it waits (i.e., blocks) for an element to be inserted, and if the queue is full, it waits for an element to be removed from the queue.

In Queue interface, there was methods like add(e), offer(e), remove(), poll() with different ways of handling operations that cannot be satisfied immediately, but may be satisfied at some point in the future: one throws an exception, the second returns a special value (either null or false, depending on the operation).
But, in BlockingQueue<E> there are other extra two forms.


Column1 Throws Exception Special value Blocks Time out
Insert add( e ) offer( e ) put( e ) offer(e,time,unit)
Remove remove() poll() take() poll(time,unit)
Examine element() peek() N.A. N.A.
  • A BlockingQueue does not accept null elements. Implementations throw NullPointerException on attempts to add, put or offer a null.
  • A BlockingQueue may be capacity bounded. At any given time it may have a remainingCapacity beyond which no additional elements can be put without blocking.
  • A BlockingQueue without any intrinsic capacity constraints always reports a remaining capacity of Integer.MAX_VALUE.
  • BlockingQueue implementations are thread-safe. All queuing methods achieve their effects atomically using internal locks or other forms of concurrency control.

BlockingQueue implementations are designed to be used primarily for producer-consumer queues,but additionally support the Collection interface.
So, for example, it is possible to remove an arbitrary element from a queue using remove(x). However, such operations are in general not performed very efficiently, and are intended for only occasional use, such as when a queued message is cancelled.


The bulk Collection operations addAll, containsAll, retainAll and removeAll are not necessarily performed atomically unless specified otherwise in an implementation. So it is possible, for example, for addAll(c) to fail (throwing an exception) after adding only some of the elements in c.
This will cleared about the difference between PriorityQueue and BlockingQueue



PriorityBlockingQueue 

Simply to say "Equivalent to java.util.PriorityQueue, but implements the BlockingQueue interface".
  • An unbounded blocking queue that uses the same ordering rules as class PriorityQueue and supplies blocking retrieval operations.
  • This queue is logically unbounded, attempted additions may fail due to resource exhaustion (causing OutOfMemoryError).
  • This class does not permit null elements.
  • A priority queue relying on natural ordering also does not permit insertion of non-comparable objects (doing so results in ClassCastException).
  • The Iterator provided in method iterator() is not guaranteed to traverse the elements of the PriorityBlockingQueue in any particular order. If you need ordered traversal, consider using Arrays.sort(pq.toArray()).
  • Operations on this class make no guarantees about the ordering of elements with equal priority. If you need to enforce an ordering, you can define custom classes or comparators that use a secondary key to break ties in primary priority values.
If you notice, most of the properties are similar to PriorityQueue.

As I said above is that PriorityBlockingQueue used primarily for producer-consumer queues, now we the the same with the help of example.

Now we see first, if we implement producer-consume problem with PriorityQueue what will be the problem. Have a look at the following code
In this code, we create two threads in which one thread inserts the value and other thread removes the values from the priorityQueue.


Sample Output
Exception in thread "Thread-0" java.util.NoSuchElementException
 at java.util.AbstractQueue.remove(Unknown Source)
 at PriorityQueueProducerConsumer$1.run(PriorityQueueProducerConsumer.java:10)
Successfully added

The above output indicate that first thread attempted removing an element from an empty queue, and hence it results in a Exception.

With slight modification in the above code

Sample output
The removed element : 15
Successfully added

In this code, take() method  will block until an element gets inserted by another thread, once inserted, the take() method() will return the value.

In other words, if you’re using a PriorityQueue object, you need to synchronize the threads such that insertion of an element always occurs before removing an element. However, in PriorityBlockingQueue, the order does not matter, and no matter which operation (insertion or removal of an element) is invoked first, the program works correctly
Related Post
Almost everything about Garbage Collection

Semaphore in java with detailed examples
Review of Java Collection Framework
Introduction to Basic of thread


If you know anyone who has started learning Java, why not help them out! Just share this post with them. 
Thanks for studying today!...

No comments:

Post a Comment