[concurrency-interest] is ConcurrentLinkedQueue is truely wait-free?

Mudit Verma mudit.f2004912 at gmail.com
Mon Jun 24 17:48:31 EDT 2013

Hello Everyone,

I think, its only right to change the documentation.

I am currently doing my master thesis on Concurrent Data Structures
(specially on queue) and we have experimental proofs that with large scale
multicore systems (such as ccNUMA), some of the threads just don't get fair
access to shared data structures (queue in this case).

This totally depends on, which NUMA node hosts the queue memory. Threads
running locally on that NUMA node gets unfairly easy access to the queue as
compared to threads running on other nodes. In this case, other threads
have to send remote memory access request for queue operations, which makes
the whole difference.  The time it takes to access the remote memory, by
that time local threads already changes the structure by applying their
operations. This results in failed CAS for remote threads.

In our results we have seen starvation for few threads (worst case), or
highly disproportionate per operation completion time (normal case).

Therefore, I believe, wait-freedom is as much required in queues as in any
other data structure. Obviously this problem is only seen when the queue is
accessed heavily left right center by all the threads.


On Mon, Jun 24, 2013 at 11:27 PM, Pedro Ramalhete <pramalhe at gmail.com>wrote:

> Hi Mudit,
> I completely agree with you. According to the the definition of wait-free,
> an object or data-structure can only be called wait-free if _all_ of its
> methods are wait-free, which is clearly not the case of the
> ConcurrentLinkedQueue and, therefore, the documentation should be corrected.
> Martin, I believe that some of the methods in the CLQ are technically
> wait-free, but in case I'm wrong, then it's even a stronger reason to
> change the documentation ;)
> Moreover, I agree with you that the difference between a wait-free queue
> and a lock-free queue is mostly academic, but only for queues, not for
> other data structures.
> On Wed, Jun 19, 2013 at 6:45 PM, Martin Buchholz <martinrb at google.com>wrote:
>> On Wed, Jun 19, 2013 at 7:38 AM, Oleksandr Otenko <
>> oleksandr.otenko at oracle.com> wrote:
>>> If the queue is blocking, how can it be wait-free.
>>> If the queue is non-blocking, there must be a non-blocking alternative
>>> to (possibly even wait-free) failure to poll() or offer().
>>> I am not sure what a certain *-freedom gives you in this context.
>> If you're saying it doesn't matter much to the user whether poll() is
>> wait-free or lock-free, then I agree.  This is mostly of academic interest.
>>  Especially when java thread priorities generally don't work, and there's
>> no risk of priority inversion.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20130624/3e002032/attachment.html>

More information about the Concurrency-interest mailing list