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

Mudit Verma mudit.f2004912 at gmail.com
Tue Jun 18 16:38:39 EDT 2013


Hello Pedro,

Thanks for your inspection.  Queue is known for two operations,
enqueue and dequeue.  If these two operations are not wait-free, I am
not sure whether it will be right to call whole implementation as
wait-free even thought there are other methods which are wait-free.

Just my take.

Thanks,
Mudit

On Tue, Jun 18, 2013 at 10: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


More information about the Concurrency-interest mailing list