4
\$\begingroup\$

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:

  1. 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.

  2. 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;
}
\$\endgroup\$
  • \$\begingroup\$ I just updated a Github repository. There you can find refactored version of the queue algorithm with multiple to multiple case. There are also several tests: one that is using Relacy Race Detector (only for 1 to 1 test case) and 2 direct tests that run several threads for reading and writing. Tests are successfully passing so I hope that it shows correctness of the algorithm. \$\endgroup\$ – Haron Aug 17 '15 at 19:18
3
\$\begingroup\$

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 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.

\$\endgroup\$
  • \$\begingroup\$ I know that my code is not complete but my intention was to make it as simple as possible so other people can understand the logic. Regarding data race you mentioned in your answer. Can you give me an example assuming that we are going to use this code on a platforms with strong memory ordering guarantee (sorry I didn't mention it). For other platforms as I answered below there could be other implementation with atomics and memory barriers. \$\endgroup\$ – Haron Jul 25 '15 at 0:19
2
\$\begingroup\$

Needs memory barriers

Your code will work on an x86 target which has strong memory ordering guarantees. But it won't work on other targets such as ARM.

Here is an example of how the code could fail. In Write(), the following sequence of events could happen in the writer thread:

    // Add new item to queue.
    data->next = nullptr;          // Write #1
    writerBottom->next = data;     // Write #2
    writerBottom = data;

    // Need memory barrier here!

    // Give queue to reader.
    readerTop = writerTop;         // Write #3

The problem is that these memory writes are not guaranteed to occur in the same order on another core. So on the reader's core, it could see that readerTop has changed (write #3). But when iterating through the list, it may not see the last element that was appended to the queue (write #2). Worse, may not even see the null pointer in the last element (write #1) and end up dereferencing a random pointer.

I didn't see an example of how you used isWriterFinished, but I'm sure that it suffers from the same problem.

To solve the problem, I would suggest using C++ atomics for the variables shared between the threads and using the proper memory_order arguments when reading/writing to your atomics to provide the proper fences.

\$\endgroup\$
  • \$\begingroup\$ Yes, you are right. At that moment I was thinking only about x86 platform. But if we will concentrate now only on platforms with strong memory ordering I assume from your answer that my code in current form will work. Am I right? About isWriterFinished variable. As I mentioned above it can be set by writer to true when writer is stopping to put data into the queue. In this case reader can safely take remaining part of the data from the writer's queue. You can see this in the Read() method in first 'if'. \$\endgroup\$ – Haron Jul 25 '15 at 0:06
  • \$\begingroup\$ For the other platforms without strong memory ordering guarantee there could be other implementation with atomics and memory barriers. \$\endgroup\$ – Haron Jul 25 '15 at 0:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.