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 then one thread is reading or writing? I seen an implementation with a lockless queue that worked with one read and one write thread but never more then one for either. Is it possible? I don't think it is. Can/does anyone want to prove it?

Answer 1

You don't specifically need a lock, but an atomic way of deleting things from the queue. This is also possible without a lock and with an atomic test-and-set instruction.

Answer 2

With .NET 4.0, there is ConcurrentQueue(T) Class.
According to C# 4.0 in a nutshell, this is a lock free implementation. See also this blog entry.

Answer 3

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?

Answer 4

There is a dynamic lock free queue in the OmniThreadLibrary by Primoz Gabrijelcic (the Delphi Geek): http://www.thedelphigeek.com/2010/02/omnithreadlibrary-105.html

Answer 5

Java's implementation of a Lockless Queue allows both reads and writes. This work is done with a compare and set operation (which is a single cpu instruction).

The ConcurrentLinkedQueue uses a method in which threads help eacthoer read (or poll) objects from the queue. Since it is linked, the the head of the queue can accept writes while the tail of the queue can accept reads (assuming enough room). All of this can be done in parallel and is completely thread safe