Reader–Writer Locks

So far, we've mostly thought about the critical section problem in terms of mutual exclusion: we want to ensure that only one thread can access a shared resource at a time. But sometimes we want to allow multiple threads to access a shared resource simultaneously.

A classic example is the asymmetry between reading data (and not changing it at all) and writing data (which changes it).

For reading, there is no problem with multiple threads reading the same data at the same time.
For writing, we want to ensure that only one thread can write to the data at a time, and while that is happening, there can't be any readers either.

A reader–writer lock is a synchronization primitive that allows multiple threads to read data simultaneously, but only one thread to write data at a time. These locks are also known as shared-exclusive locks, since read access is shared among multiple threads, while write access is exclusive. The operations would be

Operation	Description
`rwlock_create`	Create a new reader–writer lock.
`rwlock_destroy`	Destroy a reader–writer lock.
`rwlock_readlock`	Acquire the lock in shared mode.
`rwlock_writelock`	Acquire the lock in exclusive mode.
`rwlock_unlock`	Release the lock.

A Concern

We don't want the writer to starve!
Exactly, if readers keep coming, the writer might never get a chance to write. We need to be careful to ensure that the writer doesn't starve.

The Correct Rule

In summary, we need to ensure

Writers do not starve.
Readers do not starve.

The typical suggestion is to use the writer-preference rule:

If a writer is waiting to write, no new readers can start reading.

I'm a bit confused, can we go over it all again? With more of an example?
Certainly!

The Problem Illustrated

This program creates

Readers who read the value of a shared variable.
Writers who increment the value of the shared variable.

The program is reasonably chatty about lock acquisition and release so you can see how the locks are working.

#include <stdio.h>
#include <pthread.h>
#include <unistd.h>
#include <stdlib.h>
#include <assert.h>
#include "synch.h"
#include "rwlock.h"

#define NUM_READERS 5
#define NUM_WRITERS 2
#define NUM_ITERATIONS 10

static const char *reader_names[] = {
    "Robin", "Riley", "Raven", "Reese", "Renee",
    "Reena", "River", "Rohan", "Ronan", "Rania"
};

static const char *writer_names[] = {
    "Wendy", "Wayne", "Wyatt", "Wilma", "Wylie",
    "Wanda", "Wells", "Warda", "Woody", "Walid",
};

struct shared_data {
        int value;
        struct rwlock *rw_lock;
};

struct shared_data data;

void *
reader(void *arg)
{
        const char *id = (char *) arg;

        for (int i = 0; i < NUM_ITERATIONS; i++) {
                printf("Reader %s tries to acquire lock\n", id);
                rwlock_readlock(data.rw_lock);
                printf("Reader %s acquires lock, reads value: %d\n", id,
                       data.value);
                usleep(10000 + rand() % 90000); // Sleep for 10-100ms
                rwlock_unlock(data.rw_lock);
                printf("Reader %s releases lock\n", id);
                usleep(10000 + rand() % 90000); // Sleep for 10-100ms
        }

        return NULL;
}

void *
writer(void *arg)
{
        const char *id = (char *) arg;

        for (int i = 0; i < NUM_ITERATIONS; i++) {
                printf("Writer %s tries to acquire lock\n", id);
                rwlock_writelock(data.rw_lock);
                data.value++;
                printf("Writer %s acquires lock, updates value to: %d\n", id,
                       data.value);
                usleep(10000 + rand() % 90000); // Sleep for 10-100ms
                rwlock_unlock(data.rw_lock);
                printf("Writer %s releases lock\n", id);
                usleep(10000 + rand() % 90000); // Sleep for 10-100ms
        }

        return NULL;
}

#define ARRAY_SIZE(a) (sizeof(a) / sizeof(a[0]))

int
main(void)
{
        assert(ARRAY_SIZE(reader_names) >= NUM_READERS);
        assert(ARRAY_SIZE(writer_names) >= NUM_WRITERS);
        pthread_t readers[NUM_READERS];
        pthread_t writers[NUM_WRITERS];

        data.value = 0;
        data.rw_lock = rwlock_create("shared_data_lock");

        if (data.rw_lock == NULL) {
                fprintf(stderr, "Failed to create reader-writer lock\n");
                return 1;
        }

        // Create reader threads
        for (int i = 0; i < NUM_READERS; i++) {
                if (pthread_create(&readers[i], NULL, reader,
                                   (void *) reader_names[i]) != 0) {
                        fprintf(stderr, "Failed to create reader thread\n");
                        return 1;
                }
        }

        // Create writer threads
        for (int i = 0; i < NUM_WRITERS; i++) {
                if (pthread_create(&writers[i], NULL, writer,
                                   (void *) writer_names[i]) != 0) {
                        fprintf(stderr, "Failed to create writer thread\n");
                        return 1;
                }
        }

        // Wait for all threads to complete
        for (int i = 0; i < NUM_READERS; i++) {
                pthread_join(readers[i], NULL);
        }
        for (int i = 0; i < NUM_WRITERS; i++) {
                pthread_join(writers[i], NULL);
        }

        rwlock_destroy(data.rw_lock);

        printf("Final value: %d\n", data.value);

        return 0;
}

A Flawed Implementation of Reader–Writer Locks

Here's a implementation of reader–writer locks that provides both shared and exclusive access, but doesn't protect against writer starvation.

#include <assert.h>
#include <stdlib.h>
#include "synch.h"
#include "rwlock.h"

struct rwlock {
        struct lock *lock;
        struct cv *read_cv;
        struct cv *write_cv;
        int readers;
        int writers;
};

/*
 * rwlock_create: Creates and initializes a new reader-writer lock.
 *
 * The lock starts in an unlocked state with no active readers or writers.
 */
struct rwlock *
rwlock_create(const char *name)
{
        struct rwlock *rw = malloc(sizeof(struct rwlock));
        if (rw == NULL) {
                return NULL;
        }

        rw->lock = lock_create("rwlock_internal");
        rw->read_cv = cv_create("rwlock_read_cv");
        rw->write_cv = cv_create("rwlock_write_cv");

        if (rw->lock == NULL || rw->read_cv == NULL || rw->write_cv == NULL) {
                rwlock_destroy(rw);
                return NULL;
        }

        rw->readers = 0;
        rw->writers = 0;

        return rw;
}

/*
 * rwlock_destroy: Cleans up and frees all resources associated with the lock.
 *
 * Should only be called when no threads are using or waiting on the lock.
 */
void
rwlock_destroy(struct rwlock *rw)
{
        if (rw != NULL) {
                if (rw->lock != NULL)
                        lock_destroy(rw->lock);
                if (rw->read_cv != NULL)
                        cv_destroy(rw->read_cv);
                if (rw->write_cv != NULL)
                        cv_destroy(rw->write_cv);
                free(rw);
        }
}

/*
 * rwlock_readlock: Acquires the lock in read mode.
 *
 * Readers wait if there are active writers.
 */
void
rwlock_readlock(struct rwlock *rw)
{
        lock_acquire(rw->lock);

        while (rw->writers > 0) {
                cv_wait(rw->read_cv, rw->lock);
        }

        rw->readers++;

        lock_release(rw->lock);
}

/*
 * rwlock_writelock: Acquires the lock in write mode.
 *
 * Writers wait if there are active readers or writers.
 */
void
rwlock_writelock(struct rwlock *rw)
{
        lock_acquire(rw->lock);

        while (rw->readers > 0 || rw->writers > 0) {
                cv_wait(rw->write_cv, rw->lock);
        }

        rw->writers++;

        lock_release(rw->lock);
}

/*
 * rwlock_unlock: Releases the lock, whether held in read or write mode.
 */
void
rwlock_unlock(struct rwlock *rw)
{
        lock_acquire(rw->lock);
        assert(rw->readers > 0 || rw->writers > 0);

        if (rw->writers > 0) {
                rw->writers--;
        } else if (rw->readers > 0) {
                rw->readers--;
        }

        cv_broadcast(rw->read_cv, rw->lock);
        if (rw->readers == 0) {
                cv_signal(rw->write_cv, rw->lock);
        }

        lock_release(rw->lock);
}

Try this code in Online GDB

You can fork the code and then increase the number of readers and see what happens. (Also, remember that Online GDB has tabs for each file; you'll want to look at main.c and rw-lock.c.)

The writers are starving! We need to fix that.
We need to keep track of how many writers are waiting, and then modify the functions to ensure that writers don't starve. Specifically, we need to ensure that no new readers can start reading if a writer is waiting to write.
That's right! We'll see how to do that in the next section.

Implementing the Writer-Preference Rule

This version of the code implements the writer-preference rule to ensure that writers don't starve.

#include <assert.h>
#include <stdlib.h>
#include "synch.h"
#include "rwlock.h"

struct rwlock {
        struct lock *lock;
        struct cv *read_cv;
        struct cv *write_cv;
        int readers;
        int writers;
        int waiting_writers;
};

/*
 * rwlock_create: Creates and initializes a new reader-writer lock.
 *
 * The lock starts in an unlocked state with no active readers or writers.
 */
struct rwlock *
rwlock_create(const char *name)
{
        struct rwlock *rw = malloc(sizeof(struct rwlock));
        if (rw == NULL) {
                return NULL;
        }

        rw->lock = lock_create("rwlock_internal");
        rw->read_cv = cv_create("rwlock_read_cv");
        rw->write_cv = cv_create("rwlock_write_cv");

        if (rw->lock == NULL || rw->read_cv == NULL || rw->write_cv == NULL) {
                rwlock_destroy(rw);
                return NULL;
        }

        rw->readers = 0;
        rw->writers = 0;
        rw->waiting_writers = 0;

        return rw;
}

/*
 * rwlock_destroy: Cleans up and frees all resources associated with the lock.
 *
 * Should only be called when no threads are using or waiting on the lock.
 */
void
rwlock_destroy(struct rwlock *rw)
{
        if (rw != NULL) {
                if (rw->lock != NULL)
                        lock_destroy(rw->lock);
                if (rw->read_cv != NULL)
                        cv_destroy(rw->read_cv);
                if (rw->write_cv != NULL)
                        cv_destroy(rw->write_cv);
                free(rw);
        }
}

/*
 * rwlock_readlock: Acquires the lock in read mode.
 *
 * Multiple readers can hold the lock simultaneously, but not while a writer
 * is waiting. This prevents writer starvation.
 */
void
rwlock_readlock(struct rwlock *rw)
{
        lock_acquire(rw->lock);

        /* 
         * Lock out readers not only when there are active writers, but also
         * when there are writers waiting. This prevents writer starvation.
         */
        while (rw->writers > 0 || rw->waiting_writers > 0) {
                cv_wait(rw->read_cv, rw->lock);
        }

        rw->readers++;

        lock_release(rw->lock);
}

/*
 * rwlock_writelock: Acquires the lock in write mode.
 *
 * Only one writer can hold the lock, and no readers can be active.
 */
void
rwlock_writelock(struct rwlock *rw)
{
        lock_acquire(rw->lock);

        rw->waiting_writers++;

        while (rw->readers > 0 || rw->writers > 0) {
                cv_wait(rw->write_cv, rw->lock);
        }

        rw->waiting_writers--;
        rw->writers++;

        lock_release(rw->lock);
}

/*
 * rwlock_unlock: Releases the lock, whether held in read or write mode.
 *
 * If writers are waiting, they get priority. Otherwise, all waiting readers
 * are released.
 */
void
rwlock_unlock(struct rwlock *rw)
{
        lock_acquire(rw->lock);
        assert(rw->readers > 0 || rw->writers > 0);

        if (rw->writers > 0) {
                rw->writers--;
        } else if (rw->readers > 0) {
                rw->readers--;
        }

        if (rw->readers == 0 && rw->writers == 0) {
                if (rw->waiting_writers > 0) {
                        /* Give priority to a waiting writer */
                        cv_signal(rw->write_cv, rw->lock);
                } else {
                        /* No writers waiting, wake up all readers */
                        cv_broadcast(rw->read_cv, rw->lock);
                }
        }

        lock_release(rw->lock);
}

Try this code in Online GDB

Yay! No more starving writers!
I tried changing the number of writers to 10 and… uh… well, now the readers are starving. I guess we need to be careful about that, too.
Oh no!
You've identified an important issue. Strangely, the code above is often presented as being entirely sufficient and correct. But it's not! If we have a lot of writers, the readers can starve. We need to be careful to ensure that the readers don't starve either. We'll see how to do that in the next section.
Meh. Worse is better, right? So let's just leave it as is.

A More Balanced Approach

Here's an updated version of the code that balances access between readers and writers more fairly.

We aren't showing the code here, as you can look at it in Online GDB and we describe it in English below. You don't have to read the code at all.

Try this code in Online GDB

This version adds a gate mechanism to manage access fairly between readers and writers. Here are the key points:

Gate States: The enum rwlock_gate introduces three states: ALLOW_ALL, PREFER_WRITER, and PREFER_READER. These states give us fine-grained control over who gets access next.
Reader Locking: Readers now check both for active writers and for the gate state. If the gate is set to PREFER_WRITER and writers are waiting, readers have to wait, preventing writer starvation, otherwise, readers can proceed even if writers are waiting.
Gate changes on unlock: The rwlock_unlock function now manages the gate state.
- After a write operation, it sets the gate to PREFER_READER to give readers a chance.
- After a read operation, it sets the gate to PREFER_WRITER if writers are waiting, or ALLOW_ALL if not.
Signaling: The rwlock_unlock function uses the gate state to decide whether to wake up readers, and always signals a writer if any are waiting.

This implementation provides a more balanced approach to the reader–writer problem:

It prevents indefinite writer starvation by allowing writers to “close the gate” to new readers when they're waiting.
It still allows for high concurrency among readers when no writers are waiting.
It provides a mechanism to alternate between periods of reading and writing, ensuring some degree of fairness.

Yay! No one starves now!
I get it, but… uh… I don't think I could have come up with that solution on my own.
Like a lot of coding, it comes down to patterns and experience. When you've seen a few solutions, you begin to get a sense of the tricks you can use. When you're completely green, it can indeed be quite hard to know where to start. That's why we have examples like this one—to give you a sense of what's possible.
And, FWIW, both Linux and macOS do seem to take this much care with their reader–writer locks. You can try their built-in reader–writer locks here and see how they behave.
Meh. No thanks, I just want to be done with the lesson.

Fun fact, the macOS implementation is vastly more complex than the code we've seen here. It has both user-space and kernel-space components, and prevents starvation using a scheme that includes sequence numbers to ensure that later lockers can't jump ahead of earlier lockers.

In Linux, the design is also more complex, and described in a comment in the source. The thread library also provides pthread_rwlockattr_setkind_np and pthread_rwlockattr_getkind_np functions to allow the user to set the lock to be either reader-preferring or writer-preferring.

So, what you're saying is that as hard to follow as our final code is, the actual code in real-world operating systems is worse? Gah!
Worse is better!
I don't think that means what you think it means.

Takeaways

Reader–writer locks allow multiple readers to access a shared resource simultaneously, but only one writer at a time.
Writer starvation is a concern with reader–writer locks, and the writer-preference rule can help prevent it.
Reader starvation is another concern, and a more balanced approach can help prevent it.
Lock and condition variables can be used as a building block to implement reader–writer locks (in fact, they can also be used to implement other higher-level synchronization primitives as needed), but some thought has to go into the design of any new primitives we create.

You know, I think actually some of this stuff actually helps with Homework 3, the cats-and-mice problem. It kinda feels similar.
Who would have thought it…
Meh. It's not exactly the same, so I still have to think about it.

(When logged in, completion status appears here.)

Previous Page Next Page

CS 134

Warning: Missing Prerequisites