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