Reader-Writer Locks

In this lesson, we see what happens when we may want different kinds of locking on a data structure for different kinds of users.

We'll cover the following

Another classic problem stems from the desire for a more flexible locking primitive that admits that different data structure accesses might require different kinds of locking. For example, imagine a number of concurrent list operations, including inserts and simple lookups. While inserts change the state of the list (and thus a traditional critical section makes sense), lookups simply read the data structure; as long as we can guarantee that no insert is on-going, we can allow many lookups to proceed concurrently. The special type of lock we will now develop to support this type of operation is known as a reader-writer lock“Concurrent Control with Readers and Writers” by P.J. Courtois, F. Heymans, D.L. Parnas. Communications of the ACM, 14:10, October 1971. The introduction of the reader-writer problem, and a simple solution. Later work introduced more complex solutions, skipped here because, well, they are pretty complex.. The code for such a lock is shown below.

Press + to interact
typedef struct _rwlock_t {

  sem_t lock;      // binary semaphore (basic lock)

  sem_t writelock; // allow ONE writer/MANY readers

  int   readers;   // #readers in critical section

} rwlock_t;



void rwlock_init(rwlock_t *rw) {

  rw->readers = 0;

  sem_init(&rw->lock, 0, 1);

  sem_init(&rw->writelock, 0, 1);

}



void rwlock_acquire_readlock(rwlock_t *rw) {

  sem_wait(&rw->lock);

  rw->readers++;

  if (rw->readers == 1) // first reader gets writelock

    sem_wait(&rw->writelock);

  sem_post(&rw->lock);

}



void rwlock_release_readlock(rwlock_t *rw) {

  sem_wait(&rw->lock);

  rw->readers--;

  if (rw->readers == 0) // last reader lets it go

    sem_post(&rw->writelock);

  sem_post(&rw->lock);

}



void rwlock_acquire_writelock(rwlock_t *rw) {

  sem_wait(&rw->writelock);

}



void rwlock_release_writelock(rwlock_t *rw) {

  sem_post(&rw->writelock);

}

Explanation

The code is pretty simple. If some thread wants to update the data structure in question, it should call the new pair of synchronization operations: rwlock_acquire_writelock(), to acquire a write lock, and rwlock_release_writelock(), to release it. Internally, these simply use the writelock semaphore to ensure that only a single writer can acquire the lock and thus enter the critical section to update the data structure in question.

More interesting is the pair of routines to acquire and release read locks. When acquiring a read lock, the reader first acquires lock and then increments the readers variable to track how many readers are currently inside the data structure. The important step then taken within rwlock_acquire_readlock()occurs when the first reader acquires the lock; in that case, the reader also acquires the write lock by calling sem_wait() on the writelock semaphore and then releasing the lock by calling sem_post().

Thus, once a reader has acquired a read lock, more readers will be allowed to acquire the read lock too; however, any thread that wishes to acquire the write lock will have to wait until all readers are finished; the last one to exit the critical section calls sem_post() on “writelock” and thus enables a waiting writer to acquire the lock.

Drawbacks

This approach works (as desired), but does have some negatives, especially when it comes to fairness. In particular, it would be relatively easy for readers to starve writers. More sophisticated solutions to this problem exist; perhaps you can think of a better implementation? Hint: think about what you would need to do to prevent more readers from entering the lock once a writer is waiting.

Finally, it should be noted that reader-writer locks should be used with some caution. They often add more overhead (especially with more sophisticated implementations), and thus do not end up speeding up performance as compared to just using simple and fast locking primitives“Real-world Concurrency” by Bryan Cantrill, Jeff Bonwick. ACM Queue. Volume 6, No. 5. September 2008. A nice article by some kernel hackers from a company formerly known as Sun on the real problems faced in concurrent code.. Either way, they showcase once again how we can use semaphores in an interesting and useful way.

TIP: SIMPLE AND DUMB CAN BE BETTER (HILL’S LAW)

You should never underestimate the notion that the simple and dumb approach can be the best one. With locking, sometimes a simple spin lock works best because it is easy to implement and fast. Although something like reader/writer locks sounds cool, they are complex, and complex can mean slow. Thus, always try the simple and dumb approach first.

This idea, of appealing to simplicity, is found in many places. One early source is Mark Hill’s dissertation“Aspects of Cache Memory and Instruction Buffer Performance” by Mark D. Hill. Ph.D. Dissertation, U.C. Berkeley, 1987. Hill’s dissertation work, for those obsessed with caching in early systems. A great example of a quantitative dissertation., which studied how to design caches for CPUs. Hill found that simple direct-mapped caches worked better than fancy set-associative designs (one reason is that in caching, simpler designs enable faster lookups). As Hill succinctly summarized his work: “Big and dumb is better.” And thus we call this similar advice Hill’s Law.

You can run the given implementation of the reader-writer lock in the code widget below:

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <unistd.h>

#include "common.h"
#include "common_threads.h"
#include <semaphore.h>


typedef struct _rwlock_t {
    sem_t writelock;
    sem_t lock;
    int readers;
} rwlock_t;

void rwlock_init(rwlock_t *lock) {
    lock->readers = 0;
    Sem_init(&lock->lock, 1); 
    Sem_init(&lock->writelock, 1); 
}

void rwlock_acquire_readlock(rwlock_t *lock) {
    Sem_wait(&lock->lock);
    lock->readers++;
    if (lock->readers == 1)
        Sem_wait(&lock->writelock);
    Sem_post(&lock->lock);
}

void rwlock_release_readlock(rwlock_t *lock) {
    Sem_wait(&lock->lock);
    lock->readers--;
    if (lock->readers == 0)
        Sem_post(&lock->writelock);
    Sem_post(&lock->lock);
}

void rwlock_acquire_writelock(rwlock_t *lock) {
    Sem_wait(&lock->writelock);
}

void rwlock_release_writelock(rwlock_t *lock) {
    Sem_post(&lock->writelock);
}

int read_loops;
int write_loops;
int counter = 0;

rwlock_t mutex;

void *reader(void *arg) {
    int i;
    int local = 0;
    for (i = 0; i < read_loops; i++) {
        rwlock_acquire_readlock(&mutex);
        local = counter;
        rwlock_release_readlock(&mutex);
        printf("read %d\n", local);
    }
    printf("read done: %d\n", local);
    return NULL;
}

void *writer(void *arg) {
    int i;
    for (i = 0; i < write_loops; i++) {
        rwlock_acquire_writelock(&mutex);
        counter++;
        rwlock_release_writelock(&mutex);
    }
    printf("write done\n");
    return NULL;
}

int main(int argc, char *argv[]) {
    if (argc != 3) {
        fprintf(stderr, "usage: rwlock readloops writeloops\n");
        exit(1);
    }
    read_loops = atoi(argv[1]);
    write_loops = atoi(argv[2]);
    printf("write loops: %d", write_loops);
    printf("read loops: %d", read_loops);
    rwlock_init(&mutex); 
    pthread_t c1, c2;
    Pthread_create(&c1, NULL, reader, NULL);
    Pthread_create(&c2, NULL, writer, NULL);
    Pthread_join(c1, NULL);
    Pthread_join(c2, NULL);
    printf("all done\n");
    return 0;
}

Get hands-on with 1400+ tech skills courses.