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?

score 14 · Accepted Answer · edited May 23 '17 at 10:30

14

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?

edited May 23 '17 at 10:30

Community

1
1

answered Jun 11 '10 at 11:40

Viktor Svub

1,451
10
15

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). – Jun 11 '10 at 19:05
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. – Omnifarious Dec 14 '11 at 15:38
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. – Viktor Svub Dec 16 '11 at 08:56
@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... – supercat Jan 21 '13 at 21:47
3

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. – superK Aug 01 '13 at 02:47

score 3 · Answer 2 · edited Aug 30 '18 at 12:16

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.

score 1 · Answer 3 · answered Jun 11 '10 at 06:47

1

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.

answered Jun 11 '10 at 06:47

weismat

7,195
3
43
58

score 0 · Answer 4 · answered Jun 11 '10 at 06:37

0

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.

answered Jun 11 '10 at 06:37

Sjoerd

74,049
16
131
175

Is that a single CPU instruction? – Jun 11 '10 at 09:37

score 0 · Answer 5 · answered Jun 11 '10 at 14:41

0

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

answered Jun 11 '10 at 14:41

Marjan Venema

19,136
6
65
79

score 0 · Answer 6 · answered Aug 26 '16 at 23:00

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);
        });
}

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

6 Answers6

Sample

Linked