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

Pedro Ramalhete pramalhe at gmail.com
Tue Jun 18 16:23:32 EDT 2013


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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20130618/17c9b6d7/attachment.html>


More information about the Concurrency-interest mailing list