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

Nathan Reynolds nathan.reynolds at oracle.com
Mon Jun 24 19:31:45 EDT 2013


You might want to check out this blog entry from Dave Dice.  It probably 
is relevant to your work. 

Another entry compares CAS vs atomic add. 

I find Dave Dice's blog to be very enlightening for concurrency work.

Nathan Reynolds 
<http://psr.us.oracle.com/wiki/index.php/User:Nathan_Reynolds> | 
Architect | 602.333.9091
Oracle PSR Engineering <http://psr.us.oracle.com/> | Server Technology
On 6/24/2013 2:48 PM, Mudit Verma wrote:
> 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.
> Thanks,
> Mudit
> On Mon, Jun 24, 2013 at 11:27 PM, Pedro Ramalhete <pramalhe at gmail.com 
> <mailto: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 <mailto:martinrb at google.com>> wrote:
>         On Wed, Jun 19, 2013 at 7:38 AM, Oleksandr Otenko
>         <oleksandr.otenko at oracle.com
>         <mailto: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.
> _______________________________________________
> Concurrency-interest mailing list
> Concurrency-interest at cs.oswego.edu
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20130624/6bfdb150/attachment-0001.html>

More information about the Concurrency-interest mailing list