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

Oleksandr Otenko oleksandr.otenko at oracle.com
Wed Jun 19 10:38:16 EDT 2013


If the queue is blocking, how can it be wait-free.

If the queue is non-blocking, there must be a non-blocking alternative 
to (possibly even wait-free) failure to poll() or offer().

I am not sure what a certain *-freedom gives you in this context.

Alex

On 18/06/2013 21:38, Mudit Verma wrote:
> 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
> _______________________________________________
> Concurrency-interest mailing list
> Concurrency-interest at cs.oswego.edu
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest



More information about the Concurrency-interest mailing list