patterncppMinor
Thread-safe lock free FIFO queue
Viewed 0 times
fifofreethreadsafequeuelock
Problem
A few years ago there was a need to add a FIFO queue between 2 threads into my project. At that time I've got some interesting idea how to do that without any atomics and locks. (There was a discussion about this algorithm but it is in Russian.)
The idea is the following:
We have 2 threads: writer and reader. Queue class keeps 2 separate queues: one for the reader and one for the writer.
The reader reads data from its queue until it became empty. The writer writes into its own queue and after each write it checks if reader has anything to read. If it doesn't then writer pass its queue to reader and starts new one for itself.
The only place where reader and writer touch each other is passing writers queue to reader but it's safe. For details look at the code comments below or at the GitHub.
The only situation when we can face some problem is when writer write a data into its own queue but reader still has something to read. Then writer will not pass queue to the reader. If after this writer will not write any data for a long time we have a situation when there is a data in writer's queue but reader can not access it.
This can be solved in 2 ways:
-
The writer can set a flag that informs reader that writer will not write any data into the queue anymore. In this case reader will safely take writers queue itself.
-
When the writer is still planning to put some data in the queue it can call Flush method (probably several times) to force passing its queue to reader.
NOTE: It is also possible to add support for multiple writers and/or readers. It can be done by adding 2 locks: one for writers and one for readers.
In this case writers will block writers and readers will block readers but writers will not block readers.
I just verified this algorithm with my friend who is very good in thread safe area and we didn't find any problems in it.
UPD: As it is mentioned by JS1 below this code will properly work only on the platforms with strong memory ordering guarante
The idea is the following:
We have 2 threads: writer and reader. Queue class keeps 2 separate queues: one for the reader and one for the writer.
The reader reads data from its queue until it became empty. The writer writes into its own queue and after each write it checks if reader has anything to read. If it doesn't then writer pass its queue to reader and starts new one for itself.
The only place where reader and writer touch each other is passing writers queue to reader but it's safe. For details look at the code comments below or at the GitHub.
The only situation when we can face some problem is when writer write a data into its own queue but reader still has something to read. Then writer will not pass queue to the reader. If after this writer will not write any data for a long time we have a situation when there is a data in writer's queue but reader can not access it.
This can be solved in 2 ways:
-
The writer can set a flag that informs reader that writer will not write any data into the queue anymore. In this case reader will safely take writers queue itself.
-
When the writer is still planning to put some data in the queue it can call Flush method (probably several times) to force passing its queue to reader.
NOTE: It is also possible to add support for multiple writers and/or readers. It can be done by adding 2 locks: one for writers and one for readers.
In this case writers will block writers and readers will block readers but writers will not block readers.
I just verified this algorithm with my friend who is very good in thread safe area and we didn't find any problems in it.
UPD: As it is mentioned by JS1 below this code will properly work only on the platforms with strong memory ordering guarante
Solution
Concurrency
You do have a data race in your program. By the standard, if there is any variable which is can be written by one thread and read by another concurrently, there is a data race.
C++11 (N3337) 1.10 [intro.multithread]:
[...] Two expression evaluations conflict if one of them modifies a memory location (1.7) and the other one
accesses or modifies the same memory location.
[...] The execution of a program contains a data race if it contains two conflicting actions in different threads,
at least one of which is not atomic, and neither happens before the other. Any such data race results in
undefined behavior.
In your code you implicitly assume that writes and reads of pointers are atomic. Which is almost the case on x86, but not other architectures.
And even on x86, the compiler can reorder some operations.
So you must make
General
-
You container in intrusive. It can be beneficial from the performance point of view. But the container documentation shall clearly specify what interface type T shall provide. (Only
-
Another potential problem is that the queue is unbounded. What if the producer is faster than the consumer? The queue will grow indefinitely, and there is no facility to even detect that. (It can have it's use cases, but it dangerous for general purpose).
-
The class has no destructor defined. What will happen then the class is destructed? If the lack of destructor is intentional, it shall also be specified. Who is responsible of the elements which are still in the queue at that moment?
-
The class has no constructors or assignment operators defined. Most likely, it is not intended to be copied or moved. If that is the case, these members shall be explicitly declared as
You do have a data race in your program. By the standard, if there is any variable which is can be written by one thread and read by another concurrently, there is a data race.
C++11 (N3337) 1.10 [intro.multithread]:
[...] Two expression evaluations conflict if one of them modifies a memory location (1.7) and the other one
accesses or modifies the same memory location.
[...] The execution of a program contains a data race if it contains two conflicting actions in different threads,
at least one of which is not atomic, and neither happens before the other. Any such data race results in
undefined behavior.
In your code you implicitly assume that writes and reads of pointers are atomic. Which is almost the case on x86, but not other architectures.
And even on x86, the compiler can reorder some operations.
So you must make
readerTop and readerBottom variables atomic. If you are worried about performance, the compiler will use the architecture properties for your advantage (on x86 atomic loads will be compiled to plain loads, for example), and you need even more, you could play with memory_order_* arguments.isWriterFinished must be atomic for the same reasons.General
-
You container in intrusive. It can be beneficial from the performance point of view. But the container documentation shall clearly specify what interface type T shall provide. (Only
T * next member variable if I am not mistaken.)-
Another potential problem is that the queue is unbounded. What if the producer is faster than the consumer? The queue will grow indefinitely, and there is no facility to even detect that. (It can have it's use cases, but it dangerous for general purpose).
-
The class has no destructor defined. What will happen then the class is destructed? If the lack of destructor is intentional, it shall also be specified. Who is responsible of the elements which are still in the queue at that moment?
-
The class has no constructors or assignment operators defined. Most likely, it is not intended to be copied or moved. If that is the case, these members shall be explicitly declared as
= delete, otherwise the compiler will generate them for you. Or if you decide to make your members atomic, it will be deleted automatically, since atomics are not copyable nor movable.Context
StackExchange Code Review Q#97988, answer score: 3
Revisions (0)
No revisions yet.