Will ConcurrentLinkedQueue#poll() ever block ?

Question

My thread runs forever and calls ConcurrentLinkedQueue#poll() after a ConcurrentLinkedQueue#peek().

But under some conditions, the thread seems to hang. I know this is a bit vague but can people confirm for me that the methods poll() or peek() will NEVER block. Thanks.

Answer 1

According to the Javadoc, it seems that peek() and poll() should never block. I whipped up a quick producer/consumer test and I've gotten no blocking.

Answer 2

For what I can tell, the ConcurrentLinkedQueue is a "wait-free" implementation.

So I must assume that each independent call to poll() or peek() will NEVER block.

Atomic operations on this collection are synchronized and each individual call to the queue is guaranteed thread-safe.

There must be a problem with your code. For instance, if you do:

Object obj;

if (queue.peek() != null)
   obj = queue.poll()

Does not garentee that obj will not be null.

Answer 3

I do not believe that your problem is due to this, but poll() and peek() can (at least theoretically) block:

As the name implies, ConcurrentLinkedQueue is implemented as a linked list. When polling or peeking, the implementation tries to start from the head and iterates through the linked nodes, trying to find a node that is not deleted. If it finds a non-empty node it returns that, if it reaches the end it returns that the queue is empty, but if it find a deleted node, it retries.

So consider this sequence. P is a producer thread, and we have two consumer threads C1 and C2:

P:  queue.add()
C1: starts queue.poll(), begins to inspect first node
C2: completes a queue.poll() removing the item.
P:  queue.add()
C1: continues inspecting the first node, notes that it is deleted. 
      Restarts and begins to inspect the new first node.
C2: completes a queue.poll() removing the item.
P:  queue.add()
C1: continues inspecting the first node, notes that it is deleted. 
      Restarts and begins to inspect the new first node.
etc.

So poll() and peek() will block until they can determine whether or not the queue is empty.

But unless you are using some very strange thread-priorities, this scenario is highly unlikely, and I would recommend you look elsewhere for your bug.