Lockless reader/writer

Question

Hi,

I have some data that is both read and updated by multiple threads. Both reads and writes must be atomic. I was thinking of doing it like this:

// Values must be read and updated atomically
struct SValues
{
    double a;
    double b;
    double c;
    double d;
};

class Test
{
public:
    Test()
    {
        m_pValues = &m_values;
    }

    SValues* LockAndGet()
    {
        // Spin forver until we got ownership of the pointer
        while (true)
        {
            SValues* pValues = (SValues*)::InterlockedExchange((long*)m_pValues, 0xffffffff);
            if (pValues != (SValues*)0xffffffff)
            {
                return pValues;
            }
        }
    }

    void Unlock(SValues* pValues)
    {
        // Return the pointer so other threads can lock it
        ::InterlockedExchange((long*)m_pValues, (long)pValues);
    }

private:
    SValues* m_pValues;
    SValues m_values;
};

void TestFunc()
{
    Test test;

    SValues* pValues = test.LockAndGet();

    // Update or read values

    test.Unlock(pValues);
}

The data is protected by stealing the pointer to it for every read and write, which should make it threadsafe, but it requires two interlocked instructions for every access. There will be plenty of both reads and writes and I cannot tell in advance if there will be more reads or more writes.

Can it be done more effective than this? This also locks when reading, but since it's quite possible to have more writes then reads there is no point in optimizing for reading, unless it does not inflict a penalty on writing.

I was thinking of reads acquiring the pointer without an interlocked instruction (along with a sequence number), copying the data, and then having a way of telling if the sequence number had changed, in which case it should retry. This would require some memory barriers, though, and I don't know whether or not it could improve the speed.

----- EDIT -----

Thanks all, great comments! I haven't actually run this code, but I will try to compare the current method with a critical section later today (if I get the time). I'm still looking for an optimal solution, so I will get back to the more advanced comments later. Thanks again!

Answer 1

What you have written is essentially a spinlock. If you're going to do that, then you might as well just use a mutex, such as boost::mutex. If you really want a spinlock, use a system-provided one, or one from a library rather than writing your own.

Other possibilities include doing some form of copy-on-write. Store the data structure by pointer, and just read the pointer (atomically) on the read side. On the write side then create a new instance (copying the old data as necessary) and atomically swap the pointer. If the write does need the old value and there is more than one writer then you will either need to do a compare-exchange loop to ensure that the value hasn't changed since you read it (beware ABA issues), or a mutex for the writers. If you do this then you need to be careful how you manage memory --- you need some way to reclaim instances of the data when no threads are referencing it (but not before).

Answer 2

There are several ways to resolve this, specifically without mutexes or locking mechanisms. The problem is that I'm not sure what the constraints on your system is.

Remember that atomic operations is something that often get moved around by the compilers in C++.

Generally I would solve the issue like this:

Multiple-producer-single-consumer by having 1 single-producer-single-consumer per writing thread. Each thread writes into their own queue. A single consumer thread that gathers the produced data and stores it in a single-consumer-multiple-reader data storage. The implementation for this is a lot of work and only recommended if you are doing a time-critical application and that you have the time to put in for this solution.

There are more things to read up about this, since the implementation is platform specific:

Atomic etc operations on windows/xbox360: http://msdn.microsoft.com/en-us/library/ee418650(VS.85).aspx

The multithreaded single-producer-single-consumer without locks:
http://www.codeproject.com/KB/threads/LockFree.aspx#heading0005

What "volatile" really is and can be used for:
http://www.drdobbs.com/cpp/212701484

Herb Sutter has written a good article that reminds you of the dangers of writing this kind of code: http://www.drdobbs.com/cpp/210600279;jsessionid=ZSUN3G3VXJM0BQE1GHRSKHWATMY32JVN?pgno=2