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

by

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.

More Related Contents:

  1. C++11 introduced a standardized memory model. What does it mean? And how is it going to affect C++ programming?
  2. How do I terminate a thread in C++11?
  3. Concurrency: Atomic and volatile in C++11 memory model
  4. Passing object by reference to std::thread in C++11
  5. Why don’t compilers merge redundant std::atomic writes?
  6. Reader/Writer Locks in C++
  7. What are the correct link options to use std::thread in GCC under linux?
  8. std::thread pass by reference calls copy constructor
  9. C++11 thread-safe queue
  10. Does the C++ volatile keyword introduce a memory fence?
  11. How to use std::async on a member function?
  12. Which std::async implementations use thread pools?
  13. C++0x thread interruption
  14. How can I use something like std::vector?
  15. What is the difference between packaged_task and async
  16. Get the status of a std::future
  17. How to easily make std::cout thread-safe?
  18. Is it ok to read a shared boolean flag without locking it when another thread may set it (at most once)?
  19. Delayed start of a thread in C++ 11
  20. Is it smart to replace boost::thread and boost::mutex with c++11 equivalents?
  21. C++11 STL containers and thread safety
  22. Can I use std::async without waiting for the future limitation?
  23. C++ terminate called without an active exception
  24. What is different between join() and detach() for multi threading in C++?
  25. std::thread error (thread not member of std)
  26. Double-Checked Lock Singleton in C++11
  27. I want to kill a std::thread using its thread object? [duplicate]
  28. thread safety of MPI send using threads created with std::async
  29. C++11 Implementation of Spinlock using header “
  30. About thread-safety of weak_ptr

Leave a Comment