How would you implement your own reader/writer lock in C++11?

Question

I have a set of data structures I need to protect with a readers/writer lock. I am aware of boost::shared_lock, but I would like to have a custom implementation using std::mutex, std::condition_variable and/or std::atomic so that I can better understand how it works (and tweak it later).

Each data structure (moveable, but not copyable) will inherit from a class called Commons which encapsulates the locking. I'd like the public interface to look something like this:

class Commons {
public:
    void read_lock();
    bool try_read_lock();
    void read_unlock();

    void write_lock();
    bool try_write_lock();
    void write_unlock();
};

...so that it can be publicly inherited by some:

class DataStructure : public Commons {};

I'm writing scientific code and can generally avoid data races; this lock is mostly a safeguard against the mistakes I'll probably make later. Thus my priority is low read overhead so I don't hamper a correctly-running program too much. Each thread will probably run on its own CPU core.

Could you please show me (pseudocode is ok) a readers/writer lock? What I have now is supposed to be the variant that prevents writer starvation. My main problem so far has been the gap in read_lock between checking if a read is safe to actually incrementing a reader count, after which write_lock knows to wait.

void Commons::write_lock() {
    write_mutex.lock();
    reading_mode.store(false);
    while(readers.load() > 0) {}
}

void Commons::try_read_lock() {
    if(reading_mode.load()) {
        //if another thread calls write_lock here, bad things can happen
        ++readers; 
        return true;
    } else return false;
}

I'm kind of new to multithreading, and I'd really like to understand it. Thanks in advance for your help!

Answer 1

Check this class:

//
// Multi-reader Single-writer concurrency base class for Win32
//
// (c) 1999-2003 by Glenn Slayden ([email protected])
//
//


#include "windows.h"

class MultiReaderSingleWriter
{
private:
    CRITICAL_SECTION m_csWrite;
    CRITICAL_SECTION m_csReaderCount;
    long m_cReaders;
    HANDLE m_hevReadersCleared;

public:
    MultiReaderSingleWriter()
    {
        m_cReaders = 0;
        InitializeCriticalSection(&m_csWrite);
        InitializeCriticalSection(&m_csReaderCount);
        m_hevReadersCleared = CreateEvent(NULL,TRUE,TRUE,NULL);
    }

    ~MultiReaderSingleWriter()
    {
        WaitForSingleObject(m_hevReadersCleared,INFINITE);
        CloseHandle(m_hevReadersCleared);
        DeleteCriticalSection(&m_csWrite);
        DeleteCriticalSection(&m_csReaderCount);
    }


    void EnterReader(void)
    {
        EnterCriticalSection(&m_csWrite);
        EnterCriticalSection(&m_csReaderCount);
        if (++m_cReaders == 1)
            ResetEvent(m_hevReadersCleared);
        LeaveCriticalSection(&m_csReaderCount);
        LeaveCriticalSection(&m_csWrite);
    }

    void LeaveReader(void)
    {
        EnterCriticalSection(&m_csReaderCount);
        if (--m_cReaders == 0)
            SetEvent(m_hevReadersCleared);
        LeaveCriticalSection(&m_csReaderCount);
    }

    void EnterWriter(void)
    {
        EnterCriticalSection(&m_csWrite);
        WaitForSingleObject(m_hevReadersCleared,INFINITE);
    }

    void LeaveWriter(void)
    {
        LeaveCriticalSection(&m_csWrite);
    }
};

I didn't have a chance to try it, but the code looks OK.

Answer 2

Here's pseudo-code for a ver simply reader/writer lock using a mutex and a condition variable. The mutex API should be self-explanatory. Condition variables are assumed to have a member wait(Mutex&) which (atomically!) drops the mutex and waits for the condition to be signaled. The condition is signaled with either signal() which wakes up one waiter, or signal_all() which wakes up all waiters.

read_lock() {
  mutex.lock();
  while (writer)
    unlocked.wait(mutex);
  readers++;
  mutex.unlock();
}

read_unlock() {
  mutex.lock();
  readers--;
  if (readers == 0)
    unlocked.signal_all();
  mutex.unlock();
}

write_lock() {
  mutex.lock();
  while (writer || (readers > 0))
    unlocked.wait(mutex);
  writer = true;
  mutex.unlock();
}

write_unlock() {
  mutex.lock();
  writer = false;
  unlocked.signal_all();
  mutex.unlock();
}

That implementation has quite a few drawbacks, though.

Wakes up all waiters whenever the lock becomes available

If most of the waiters are waiting for a write lock, this is wastefull - most waiters will fail to acquire the lock, after all, and resume waiting. Simply using signal() doesn't work, because you do want to wake up everyone waiting for a read lock unlocking. So to fix that, you need separate condition variables for readability and writability.

No fairness. Readers starve writers

You can fix that by tracking the number of pending read and write locks, and either stop acquiring read locks once there a pending write locks (though you'll then starve readers!), or randomly waking up either all readers or one writer (assuming you use separate condition variable, see section above).

Locks aren't dealt out in the order they are requested

To guarantee this, you'll need a real wait queue. You could e.g. create one condition variable for each waiter, and signal all readers or a single writer, both at the head of the queue, after releasing the lock.

Even pure read workloads cause contention due to the mutex

This one is hard to fix. One way is to use atomic instructions to acquire read or write locks (usually compare-and-exchange). If the acquisition fails because the lock is taken, you'll have to fall back to the mutex. Doing that correctly is quite hard, though. Plus, there'll still be contention - atomic instructions are far from free, especially on machines with lots of cores.

Conclusion

Implementing synchronization primitives correctly is hard. Implementing efficient and fair synchronization primitives is even harder. And it hardly ever pays off. pthreads on linux, e.g. contains a reader/writer lock which uses a combination of futexes and atomic instructions, and which thus probably outperforms anything you can come up with in a few days of work.

Answer 3

I believe this is what you are looking for:

class Commons {
    std::mutex write_m_;
    std::atomic<unsigned int> readers_;

public:
    Commons() : readers_(0) {
    }

    void read_lock() {
        write_m_.lock();
        ++readers_;
        write_m_.unlock();
    }

    bool try_read_lock() {
        if (write_m_.try_lock()) {
            ++readers_;
            write_m_.unlock();
            return true;
        }
        return false;
    }

    // Note: unlock without holding a lock is Undefined Behavior!
    void read_unlock() {
        --readers_;
    }

    // Note: This implementation uses a busy wait to make other functions more efficient.
    //       Consider using try_write_lock instead! and note that the number of readers can be accessed using readers()
    void write_lock() {
        while (readers_) {}
        if (!write_m_.try_lock())
            write_lock();
    }

    bool try_write_lock() {
        if (!readers_)
            return write_m_.try_lock();
        return false;
    }

    // Note: unlock without holding a lock is Undefined Behavior!
    void write_unlock() {
        write_m_.unlock(); 
    }

    int readers() { 
        return readers_; 
    }
};

For the record since C++17 we have std::shared_mutex, see: https://en.cppreference.com/w/cpp/thread/shared_mutex

Answer 4

You can implement a Readers-Writers lock following the exact Wikipedia algorithm from here (I wrote it):

#include <iostream>
#include <thread>
#include <mutex>
#include <condition_variable>

int g_sharedData = 0;
int g_readersWaiting = 0;
std::mutex mu;
bool g_writerWaiting = false;
std::condition_variable cond;

void reader(int i)
{
    std::unique_lock<std::mutex> lg{mu};
    while(g_writerWaiting)
        cond.wait(lg);
    ++g_readersWaiting;
    // reading
    std::cout << "\n reader #" << i << " is reading data = " << g_sharedData << '\n';
    // end reading
    --g_readersWaiting;
    while(g_readersWaiting > 0)
        cond.wait(lg);
    cond.notify_one();
}

void writer(int i)
{
    std::unique_lock<std::mutex> lg{mu};
    while(g_writerWaiting)
        cond.wait(lg);
    // writing
    std::cout << "\n writer #" << i << " is writing\n";
    g_sharedData += i * 10;
    // end writing
    g_writerWaiting = true;
    while(g_readersWaiting > 0)
        cond.wait(lg);
    g_writerWaiting = false;
    cond.notify_all();
}//lg.unlock()


int main()
{
    std::thread reader1{reader, 1};
    std::thread reader2{reader, 2};
    std::thread reader3{reader, 3};
    std::thread reader4{reader, 4};
    std::thread writer1{writer, 1};
    std::thread writer2{writer, 2};
    std::thread writer3{writer, 3};
    std::thread writer4{reader, 4};

    reader1.join();
    reader2.join(); 
    reader3.join();
    reader4.join();
    writer1.join();
    writer2.join();
    writer3.join();
    writer4.join();

    return(0);
}