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

Martin Buchholz martinrb at google.com
Mon Jun 17 00:53:52 EDT 2013


Your code snippet is outdated, but yes, I think the term "wait-free" seems
sloppy to me as well.

- * <p>This implementation employs an efficient "wait-free"
+ * <p>This implementation employs an efficient <em>non-blocking</em>
  * algorithm based on one described in <a
  * href="http://www.cs.rochester.edu/u/michael/PODC96.html"> Simple,
  * Fast, and Practical Non-Blocking and Blocking Concurrent Queue



On Wed, Jun 12, 2013 at 9:47 AM, Mudit Verma <mudit.f2004912 at gmail.com>wrote:

> 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/20130616/b3355199/attachment.html>


More information about the Concurrency-interest mailing list