[concurrency-interest] is ConcurrentLinkedQueue is truely wait-free?
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.
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.
> 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
> 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
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Concurrency-interest