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?

Shanan

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?

Accession

I didnt understand CAS until i read the CMPXCHG instruction. The CMPXCHG instruction looks cool, so i take it if its a success it will set the Z flag? Now after minutes of confusion with CAS until reading CMPXCHG CAS looks like CAS(dst, oldValue, newVal); where dst is the address destination and the other two are values? returning true if dst was old value and has been now replace by newValue? (I know i said a lot but i think i got this right, it seems very right). – Shanan

Do you know if there are any existing C++11 implementations of your paper? It looks like it requires some care to implement, and while I could really use this, I'm going to go for a locking implementation that's easier to understand and analyze. – Transatlantic

Sorry, the paper starts to become quite aged and I didn't look for any current implementations, as it is possible to implement and debug the algorithm based on the pseudo-code. – Accession

@acidzombie24: I find it curious that CAS is "compare and swap" when its real behavior seems to be "compare and [conditional] store". CAS represents the intersection of two paradigms: load-linked/store-conditional and compare-exchange. A system which implements load-linked/store conditional has a special "read" instruction which sets a flag and causes the system to start watching the destination address somehow. If anything happens that might disturb that address, the flag will be cleared. Store conditional performs a store if the flag is still set, and sets a register to indicate... – Panek

After boost 1.53, there is a library named lockfree in it. It supply boost::lockfree::queue witch descripted 'a lock-free multi-produced/multi-consumer queue', enjoy it. – Loco

Answer 2

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 each other read (or poll) objects from the queue. Since it is linked, 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.

Pneumatometer

Answer 3

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.

Kaleidoscope

Answer 4

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.

Jimmiejimmy

Is that a single CPU instruction? – Shanan

Answer 5

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

Carbon

Answer 6

With .NET 4.0, there is ConcurrentQueue Class.

Sample

https://dotnetfiddle.net/ehLZCm

public static void Main()
{
    PopulateQueueParallel(new ConcurrentQueue<string>(), 500);
}

static void PopulateQueueParallel(ConcurrentQueue<string> queue, int queueSize)
{
    Parallel.For(0, queueSize, (i) => queue.Enqueue(string.Format("my message {0}", i)));
    Parallel.For(0, queueSize,
        (i) =>
        {
            string message;
            bool success = queue.TryDequeue(out message);
            if (!success)
                throw new Exception("Error!");

            Console.WriteLine(message);
        });
}

Lilalilac