Is there such a thing as a lockless queue for multiple read or write threads?

Question

I was thinking, is it possible to have a lockless queue when more than one thread is reading or writing? I've seen an implementation with a lockless queue that worked with one read and one write thread but never more than one for either. Is it possible? I don't think it is. Can/does anyone want to prove it?

Answer 1

There are multiple algorithms available, I ended up implementing the An Optimistic Approach to Lock-Free FIFO Queues, which avoids the ABA problem via pointer-tagging (needs the CMPXCHG8B instruction on x86), and it runs fine in a production app (written in Delphi). (Another version, with Java code)

Nevertheless, to be really-really lockless, you would also need a lock-free memory allocator - see Scalable Lock-Free Dynamic Memory Allocation (implemented in Concurrent Building Block) or NBMalloc (but so far, I didn't get to use one of these).

You may also want to look at answers for optimistic lock-free FIFO queues impl?