Reader/Writer Locks in C++

Question

I'm looking for a good reader/writer lock in C++. We have a use case of a single infrequent writer and many frequent readers and would like to optimize for this. Preferable I would like a cross-platform solution, however a Windows only one would be acceptable.

Answer 1

You could copy Sun's excellent ReentrantReadWriteLock. It includes features such as optional fairness, lock downgrading, and of course reentrancy.

Yes it's in Java, but you can easily read and transpose it to C++, even if you don't know any Java. The documentation I linked to contains all the behavioral properties of this implementation so you can make sure it does what you want.

If nothing else, it's a guide.

Answer 2

Newer versions of boost::thread Have read/write locks (1.35.0 and later, apparently the previous versions did not work correctly).

They have the names shared_lock, unique_lock, and upgrade_lock and operate on a shared_mutex.

Answer 3

Using standard pre-tested, pre-built stuff is always good (for example, Boost as another answer suggested), but this is something that's not too hard to build yourself. Here's a dumb little implementation pulled out from a project of mine:

#include <pthread.h>

struct rwlock {
    pthread_mutex_t lock;
    pthread_cond_t read, write;
    unsigned readers, writers, read_waiters, write_waiters;
};

void reader_lock(struct rwlock *self) {
    pthread_mutex_lock(&self->lock);
    if (self->writers || self->write_waiters) {
        self->read_waiters++;
        do pthread_cond_wait(&self->read, &self->lock);
        while (self->writers || self->write_waiters);
        self->read_waiters--;
    }
    self->readers++;
    pthread_mutex_unlock(&self->lock);
}

void reader_unlock(struct rwlock *self) {
    pthread_mutex_lock(&self->lock);
    self->readers--;
    if (self->write_waiters)
        pthread_cond_signal(&self->write);
    pthread_mutex_unlock(&self->lock);
}

void writer_lock(struct rwlock *self) {
    pthread_mutex_lock(&self->lock);
    if (self->readers || self->writers) {
        self->write_waiters++;
        do pthread_cond_wait(&self->write, &self->lock);
        while (self->readers || self->writers);
        self->write_waiters--;
    }
    self->writers = 1;
    pthread_mutex_unlock(&self->lock);
}

void writer_unlock(struct rwlock *self) {
    pthread_mutex_lock(&self->lock);
    self->writers = 0;
    if (self->write_waiters)
        pthread_cond_signal(&self->write);
    else if (self->read_waiters)
        pthread_cond_broadcast(&self->read);
    pthread_mutex_unlock(&self->lock);
}

void rwlock_init(struct rwlock *self) {
    self->readers = self->writers = self->read_waiters = self->write_waiters = 0;
    pthread_mutex_init(&self->lock, NULL);
    pthread_cond_init(&self->read, NULL);
    pthread_cond_init(&self->write, NULL);
}

pthreads not really being Windows-native, but the general idea is here. This implementation is slightly biased towards writers (a horde of writers can starve readers indefinitely); just modify writer_unlock if you'd rather the balance be the other way around.

Yes, this is C and not C++. Translation is an exercise left to the reader.

Edit

Greg Rogers pointed out that the POSIX standard does specify pthread_rwlock_*. This doesn't help if you don't have pthreads, but it stirred my mind into remembering: Pthreads-w32 should work! Instead of porting this code to non-pthreads for your own use, just use Pthreads-w32 on Windows, and native pthreads everywhere else.

Answer 4

I can recommend the ACE library, which provides a multitude of locking mechanisms and is ported to various platforms.

Depending on the boundary conditions of your problem, you may find the following classes useful:

• ACE_RW_Process_Mutex
• ACE_Write_Guard and ACE_Read_Guard
• ACE_Condition

Answer 5

Boost.Thread has since release 1.35.0 already supports reader-writer locks. The good thing about this is that the implementation is greatly cross-platform, peer-reviewed, and is actually a reference implementation for the upcoming C++0x standard.

Answer 6

Whatever you decide to use, benchmark your work load against simple locks, as read/write locks tend to be 3-40x slower than simple mutex, when there is no contention.

Here is some reference

Answer 7

Intel Thread Building Blocks also provide a couple of rw_lock variants:

http://www.threadingbuildingblocks.org/

They have a spin_rw_mutex for very short periods of contention and a queueing_rw_mutex for longer periods of contention. The former can be used in particularly performance sensitive code. The latter is more comparable in performance to that provided by Boost.Thread or directly using pthreads. But profile to make sure which one is a win for your access patterns.

Answer 8

There is an article about reader-writer locks on MSDN that presents some implementations of them. It also introduces the Slim reader/writer lock, a kernel synchronisation primitive introduced with Vista. There's also a CodeProject article about comparing different implementations (including the MSDN article's ones).

Answer 9

Does any one know if the Boost implementation will allow starvation of the writer threads?