Reader-Writer Problem

Implementing a Read/Write Mutex

by Volker Hilsheimer

Developing threaded software is always a challenge. Breaking a complex application into separate units of execution without compromising its stability requires not only a well-structured design that prevents the developer from accessing unsafe data, but also a good understanding of the concepts, tools, and caveats of multithreaded programming.

• Understanding Mutexes and Semaphores

• Mutually Exclusive Readers

• Fast, but Not Fair

• Fair, but Fairly Limited

• Share and Enjoy

• A Read/Write Mutex Class

• Conclusion

In this article, we will review the problems encountered when implementing a read/write mutex, a synchronization tool for protecting resources that can be accessed for reading and writing. We want to allow multiple threads to have simultaneous read-only access, but as soon as one thread wants to write to the resource, all other threads must be blocked until the writing is complete.

Understanding Mutexes and Semaphores

Understanding is a three-edged sword.

-- Kosh

//0c The most basic synchronization tool is the mutex. A mutex guarantees mutually exclusive access to a shared resource at any given time. Threads that want to access a resource protected by a mutex must wait until the currently active thread is finished and unlock the mutex. Mutexes are very easy to use, but can drastically slow down threaded code when overused.

Another frequently used tool is the semaphore. Semaphores represent "available resources" that can be acquired by multiple threads at the same time until the resource pool is empty. Additional threads must then wait until the required number of resources are available again. Semaphores are very efficient, as they allow simultaneous access to resources. But improper use often leads to thread starvation, or to deadlock---where two threads block each other indefinitely, each one waiting for a resource the other thread has currently locked.

In Qt, mutexes and semaphores are provided by the QMutex and QSemaphore classes.

Mutually Exclusive Readers

Let's assume that we have one or many reader threads reading from a file, and one or many writer threads writing to the same file. To ensure that the file isn't modified while a thread is reading it, we can use a mutex. For example:

QMutex mutex; void ReaderThread::run() { ... mutex.lock(); read_file(); mutex.unlock(); ... } void WriterThread::run() { ... mutex.lock(); write_file(); mutex.unlock(); ... }

The mutex ensures that only one thread at a time can access the file. This works, but if multiple reader threads run at the same time, the threads will quickly end up spending a large percentage of their total running time waiting for the mutex to become available.

Fast, but Not Fair

The next solution uses a semaphore instead of a mutex to give multiple readers simultaneous access to the file.

const int MaxReaders = 32; QSemaphore semaphore(MaxReaders); void ReaderThread::run() { ... semaphore++; read_file(); semaphore--; ... } void WriterThread::run() { ... semaphore += MaxReaders; write_file(); semaphore -= MaxReaders; ... }

With this solution, up to MaxReaders threads can read from the file at the same time. As soon as a writer thread wants to modify the file, it tries to allocate all the semaphore's resources, thus making sure that no other thread can access the file during the write operation.

This approach looks reasonable, but there's a problem with it. The writer thread's chance to get access to all resources decreases rapidly with a growing number of reader threads, up to the point where the writer thread will starve completely. This is because QSemaphore's += operator blocks until the semaphore's resource count is zero, instead of acquiring the resources one by one as they are released by reader threads.

In other words, QSemaphore favors threads that request fewer resources. This is "unfair", but prevents a deadlock, as we will see with the next example.

Fair, but Fairly Limited

It is tempting to replace the += operator with a loop that calls the ++ operator repeatedly, to solve the problem described above:

void WriterThread::run() { ... for (int i = 0; i < MaxReaders; ++i) semaphore++; write_file(); semaphore -= MaxReaders; ... }

Now the writer thread has a fair chance to allocate all resources. But as soon as there are two writer threads competing for the same semaphore, we could end up with a deadlock, with each thread having some resources, but neither being able to get all the resources it needs.

Share and Enjoy

To remove this limitation, we must introduce a mutex in addition to the semaphore. The mutex is only used by writer threads:

void WriterThread::run() { ... mutex.lock(); for (int i = 0; i < MaxReaders; ++i) semaphore++; mutex.unlock(); write_file(); semaphore -= MaxReaders; ... }

As soon as one writer thread has started to allocate resources from the semaphore, all other writer threads must wait. The reader threads don't use the mutex, so they can work simultaneously as long as the writer thread is inactive. Once the writer thread starts working, it will have a fair chance of acquiring the semaphore.

A Read/Write Mutex Class

We can encapsulate our solution in a ReadWriteMutex class:

class ReadWriteMutex { public: ReadWriteMutex(int maxReaders = 32) : semaphore(maxReaders) { } void lockRead() { semaphore++; } void unlockRead() { semaphore--; } void lockWrite() { QMutexLocker locker(&mutex); for (int i = 0; i < maxReaders(); ++i) semaphore++; } void unlockWrite() { semaphore -= semaphore.total(); } int maxReaders() const { return semaphore.total(); } private: QSemaphore semaphore; QMutex mutex; };

Here's how we can use it in applications:

ReadWriteMutex mutex; void ReaderThread::run() { ... mutex.lockRead(); read_file(); mutex.unlockRead(); ... } void WriterThread::run() { ... mutex.lockWrite(); write_file(); mutex.unlockWrite(); ... }

For your convenience, the ReadWriteMutex class developed in this article will be made available as a Qt Solution, together with a ReadWriteMutexLocker class.

Conclusion

Correct synchronization of access to resources shared by multiple threads is one of the most important aspects of threaded programming. Missing or insufficient synchronization will produce unpredictable results, and in the worst case crash the application.

At the same time, too much or improperly used synchronization will cause the threads to spend an unnecessarily long time blocking, thereby reducing the benefit of threaded development significantly.