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

Martin Buchholz martinrb at google.com
Tue Jun 18 16:52:54 EDT 2013


I don't think any of the listed methods are technically wait-free.
Frantic activity from other threads can cause even isEmpty to spend
unbounded time traversing the linked list of nodes.


On Tue, Jun 18, 2013 at 1:23 PM, Pedro Ramalhete <pramalhe at gmail.com> wrote:

> Hi Mudit,
>
> After a quick inspection it seems to me that some of the methods of
> ConcurrentLinkedQueue are Lock-Free and others are Wait-Free, namely:
>
> Lock-Free:
> add()
> addAll()
> offer()
> poll()
> remove()
> clear()
>
> Wait-Free:
> contains()
> isEmpty()
> peek()
> size()
> toArray() - uses "new" which by itself is not truly wait-free
> iterator()
> element()
>
> To be more accurate, the functions described above are not just Wait-Free,
> they are Wait-Free Population-Oblivious.
>
> Hope it helps,
> Pedro Ramalhete
>
> ------------------------------
> Date: Wed, 12 Jun 2013 18:47:09 +0200
> From: Mudit Verma <mudit.f2004912 at gmail.com>
> To: concurrency-interest <concurrency-interest at cs.oswego.edu>
> Subject: [concurrency-interest] is ConcurrentLinkedQueue is truely
>         wait-free?
> Message-ID:
>         <CAMM2gsP_
> x7387eCaR1jsm1RsoDFf3ijw=4u+YJCjPyyW+=nnDQ at mail.gmail.com>
> Content-Type: text/plain; charset=ISO-8859-1
>
> Hi All,
>
> As I read the documentation in java.util.concurrent it says the
> implementation is wait-free. However, I doubt it.  For example an
> enqueue operation loops forever until it is able to CAS new element to
> the tail of queue.  Now, there could be a case, where other threads
> are just fast enough and never give this guy a chance to apply its
> CAS.
>
> However, it helps other threads to update their 2nd CAS (which is to
> update the tail pointer).     As far as first CAS goes, it's not
> wait-free I believe.   Any thoughts?
>
>
>  188:     public boolean offer(E e) {
>  189:         if (e == null) throw new NullPointerException();
>  190:         Node<E> n = new Node<E>(e, null);
>  191:         for (;;) {
>  192:             Node<E> t = tail;
>  193:             Node<E> s = t.getNext();
>  194:             if (t == tail) {
>  195:                 if (s == null) {
>  196:                     if (t.casNext(s, n)) {
>  197:                         casTail(t, n);
>  198:                         return true;
>  199:                     }
>  200:                 } else {
>  201:                     casTail(t, s);
>  202:                 }
>  203:             }
>  204:         }
>  205:     }
>  206:
>
>
> Thanks,
> Mudit
>
> _______________________________________________
> 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/20130618/133f8d2d/attachment.html>


More information about the Concurrency-interest mailing list