3 ms·

I'm not sure you're aware of this, but there's a distinction between wait-free and lock-free. http://rethinkdb.com/blog/lock-free-vs-wait-free-concurrency/ htt

• jstimpfle 10y ago
  Wouldn't the ring buffer queue be also wait-free in this sense? (except that the number of unread items in the queue is restricted).
• adrianratnapala 10y ago
  I became aware of the distinction when I skimmed the paper. But I couldn't figure out what it meant in this case. Specifically does the every thread requirement rule out algorithms where there only one reader and one writer is allowed? If not, then this ring buffer is wait-free, since there is no CAS-and-retry step. (Of course an operation can fail because the queue is empty/full, but that is still completion).
  • the8472 10y ago
    there are several aspects to consider when talking about a concurrent queue: * multiple/single producer, multiple/single consumer * progress guarantees (wait-free, lock-free) * bounded vs. unbounded * whether it's double-ended or single-ended * memory reclamation being dependant on a GC or not * which atomic operations they need (e.g. some require double-CAS) What you mention is a spsc bounded queue. this is about a mpmc unbounded queue. And from skimming the paper is seems like it does not require a GC either. So it's far more powerful. Of course spsc queues still have their use even if we have a good mpmc queue, they generally incur less overhead.