Read-Write Locks

Overview

Mutexes and semaphores allow us to lock access to critical sections, but they do not differentiate between reading and writing.

This can be important since we can read data from multiple threads at the same time, but can't write at the same time as a read or write.

If we protect a piece of data with a mutex, it will not allow multiple reads in parallel.

Linked List Example

This can be an issue with data structures that can be modified, such as lists and trees.

The following example shows a linked list that is used across multiple threads. In this example, there are reader threads which print a linked list, and writer threads which modify the list.


/* a linked list node */
struct node_t {
    int data;
    struct node_t* next;
};

/* add an element at front of list */
void list_insert(struct node_t** head, int data) {
    struct node_t* new = malloc(sizeof(struct node_t));
    new->data = data;
    new->next = *head;
    *head = new;
}

/* remove the first instance of an element from a list */
void list_remove(struct node_t** head, int data) {
    struct node_t* previous = NULL;
    struct node_t* current = *head;
    while (current) {
        if (current->data == data) {
            if (previous) {
                previous->next = current->next;
            } else {
                *head = current->next;
            }
            free(current);
            return;
        }
        current = current->next;
    }
}

/* print a linked list to the screen */
void list_print(struct node_t* head) {
    struct node_t* current = head;
    while (current) {
        printf("%d ", current->data);
        current = current->next;
    }
    printf("\n");
}

/* our list is global */
struct node_t* head = NULL;

/* thread function which inserts and removes elements */
void* writer(void* idp) {
    /* continually insert and remove items */
    while (1) {
        list_insert(&head, rand() % 100);
        list_remove(&head, rand() % 100);
        list_remove(&head, rand() % 100);
        list_remove(&head, rand() % 100);
    }

    return NULL;
}

/* thread function which prints the list */
void* reader(void* idp) {
    /* continually print the list */
    while (1) {
        list_print(head);
    }

    return NULL;
}

Read-Write Contention

This example may cause crashes or leave our linked list in an incorrect state. If the "list_remove" function frees a node that the "list_print" function accesses, for example.

Some runs may work fine, others may get this:

[finlayson@cs pthreads]$ a.out 256
*** glibc detected *** a.out: double free or corruption (fasttop): 0x00007f2d5c0024b0 ***
======= Backtrace: =========
/lib/libc.so.6(+0x78cc6)[0x7f2d7b8e5cc6]
/lib/libc.so.6(cfree+0x73)[0x7f2d7b8ec303]
a.out[0x40085a]
a.out[0x400999]
/lib/libpthread.so.0(+0x69ca)[0x7f2d7bbfc9ca]
/lib/libc.so.6(clone+0x6d)[0x7f2d7b95884d]

Mutex Solution

We could prevent this with a mutex. In this case, we would put a lock/unlock around every access to the linked list.

That looks like this:


/* a mutex */
pthread_mutex_t lock;

/* thread function which inserts and removes elements */
void* writer(void* idp) {
    /* continually insert and remove items */
    while (1) {
        pthread_mutex_lock(&lock);
        list_insert(&head, rand() % 100);
        list_remove(&head, rand() % 100);
        list_remove(&head, rand() % 100);
        list_remove(&head, rand() % 100);
        pthread_mutex_unlock(&lock);
    }

    return NULL;
}

/* thread function which tests if elements are in the list */
void* reader(void* idp) {
    /* continually print the list */
    while (1) {
        pthread_mutex_lock(&lock);
        list_print(head);
        pthread_mutex_unlock(&lock);
    }

    return NULL;
}

This will correct the program, but it is not as efficient as it could be. It prevents multiple threads from calling list_print - which is perfectly OK!

Read-Write Locks

To address this issue, pthreads has another kind of lock, a read-write lock. These are declared as:


pthread_rwlock_t lock;

Initialized as:


pthread_rwlock_init(&lock, NULL);

They provide two lock functions, one for read-write access, and one for just reading:


pthread_rwlock_rdlock(&lock);
pthread_rwlock_wrlock(&lock);

There is only one unlock function:


pthread_rwlock_unlock(&lock);

If a thread calls "wrlock", it will wait until all other threads unlock before continuing.

However, if a thread calls "rdlock", it will only wait until any other writing threads unlock. Multiple threads can proceed past "rdlock" calls at the same time.

Linked List Example

We can replace the mutexes with read-write locks, as in this example:


/* a read-write lock */
pthread_rwlock_t lock;

/* thread function which inserts and removes elements */
void* writer(void* idp) {
    /* continually insert and remove items */
    while (1) {
        pthread_rwlock_wrlock(&lock);
        list_insert(&head, rand() % 100);
        list_remove(&head, rand() % 100);
        list_remove(&head, rand() % 100);
        list_remove(&head, rand() % 100);
        pthread_rwlock_unlock(&lock);
    }

    return NULL;
}

/* thread function which tests if elements are in the list */
void* reader(void* idp) {
    /* continually print the list */
    while (1) {
        pthread_rwlock_rdlock(&lock);
        list_print(head);
        pthread_rwlock_unlock(&lock);
    }

    return NULL;
}

This still protects the linked list from being invalidated, but now allows multiple threads to print it at the same time.

In real-life examples, this can make a big difference for structures that are read much more often than they are written.

Read-Write Lock Implementation

The operation of a mutex is relatively simple. The mutex can either be locked or unlocked. When lock is called, the thread checks the mutex and either waits or proceeds.

A read-write lock is slightly more complex. When rdlock is called, the lock can be in one of three states:

The lock is locked for writing
In this case, the thread must wait for it to be unlocked, as in a regular mutex.
The lock is not locked for writing, and no threads are attempting to lock it for writing
In this case, the thread can proceed to lock the mutex for reading, whether it is already locked for reading or not.
The lock is not locked for writing, but at least one thread is waiting to lock it for writing
In this case, the thread could in theory continue and lock the mutex for reading, but instead read-write lock implementations will have the thread wait for the waiting write thread to go first.

The reason for this is to prevent the writing thread from being starved. Starvation in multi-threading refers to a situation in which one or more threads are prevented from executing while the rest do.

Because locking a read-write lock is more complicated, and because it involves operating system calls, they are slightly slower than mutexes. As such, they should normally only be used when there are many more readers than writers. Otherwise, regular mutexes should be preferred.

Performance Comparison

To demonstrate there is a performance impact, we can look at the following example, which spawns threads to write to the linked list, and also threads to read from it. To avoid printing being the limiting factor, the read threads now look for values in the list instead of printing.

The program has flags defined at the top which define the number of readers and writers, the size of the linked list, and whether the locking should be done with a mutex or a read-write lock. By running the program with different values, you can see that the read-write locks will generally be faster than mutexes when there are more readers than writers.

The difference is less when the readers work in the lock is less. This can be seen by increasing the LOOPS variable and decreasing the DATA_SIZE variable. In the extreme case, the mutex version will even be faster.

The code can be seen here.

The read-write version should be at least slightly faster.