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 guarantee. For others there should be separate implementation
Can you take a look at the code so you can find some issue that I have missed?
template <class T>
class LockFreeQueue
{
public:
/**
* Write data to the queue. Writer only method.
* Return value can be used by writer to decide when Flush() should be called.
*
* @param data Value to write to the queue
* @return true if data was send to the reader otherwise false
*/
bool Write(T *data);
/**
* Read data from queue. Reader only method.
*
* @param data [OUT] Data to retrieve.
* @return true if data was retrieved otherwise false.
*/
bool Read(T *&data);
/**
* Flush remained data to the reader. Writer only method.
*
* @return true if data was flushed otherwise false.
*/
bool Flush();
/**
* Inform that writer is finished.
*/
void SetWriterFinished() { isWriterFinished = true; }
/**
* Check if writer is finished.
*/
bool IsWriterFinished() { return isWriterFinished; }
private:
T *readerTop = nullptr;
T *writerTop = nullptr;
T *writerBottom = nullptr;
bool isWriterFinished = false;
};
template<class T>
bool LockFreeQueue<T>::Write(T* data)
{
assert(!isWriterFinished);
assert(data != nullptr);
data->next = nullptr;
if (writerTop != nullptr)
{
writerBottom->next = data;
writerBottom = data;
}
else
{
writerTop = writerBottom = data;
}
if (readerTop == nullptr) // reader don't have anything to read
{
readerTop = writerTop; // give reader writer's queue
writerTop = nullptr; // P1: start new writers queue
return true;
}
return false;
}
template<class T>
bool LockFreeQueue<T>::Read(T*& data)
{
// If writer stoped in Write() method before command marked as P1 there could be 2 situations:
// 1. If writer/reader threads/cpus became synchronized reader will not go inside a following 'if' and goes to the
// P2.
// 2. Otherwise reader will go inside following 'if' and will always return false because isWriterFinished will
// always be false in this situation (see first assert in Write() method).
if (readerTop == nullptr)
{
// Magic happens here. If writer is not finished writing and we have nothing to read then we go to the 'false'
// branch and return false.
// If writer is finished we go to the 'true' branch but we will not interfere in accessing to the 'readerTop' or
// 'writerTop' variables with writer because he can not call Write() method after finishing.
if (isWriterFinished && writerTop != nullptr)
{
// Reader will come at this place only when writer stops writing to the queue.
// Reader just read remaining part of the data if present.
readerTop = writerTop;
writerTop = nullptr;
if (readerTop == nullptr) // nothing to read
return false;
}
else
{
return false;
}
}
// P2
// At this place we garantee that readerTop variable is synchronized between reader and writer.
// Also we can garantee here that readerTop != nullptr
data = readerTop;
readerTop = data->next;
return true;
}
/**
* This method should be called by writer in a case when writer doesn't write into its own queue for a long time and
* its queue is not empty. In this case reader will not receive data from writers queue.
* Calling of this method by writer will not influence of calling Read() method by reader.
*/
template<class T>
bool LockFreeQueue<T>::Flush()
{
assert(!isWriterFinished);
if (writerTop == nullptr)
{
return true;
}
if (readerTop == nullptr)
{
readerTop = writerTop;
writerTop = nullptr;
return true;
}
return false;
}
