Thursday, August 21, 2014

A simple read-write lock implementation

Here is a simple read-write lock I implemented in quick succession as just to understand how pthred_rwlocks would have been implemented. I have not dug deep into the pthread code yet but believe would be having some similar mechanism. This implementation functions as per definition of read-write locks. Note that this is just very basic implementation I coded to satisfy my inquisitiveness. There are problems though with this implementation which I will be documenting further.

How does it work?

i)  The structure consists of mutex, codition variable and reader count.
ii) As soon as reader grabs the lock, the reader count is atomically incremented.
iii) Note that the lock is common for both reader and writer.
iv) If a thread wants to acquire write lock, then it first atomically checks if reader count is zero. If yes, it safely can acquire the lock
v) If there are readers pending, the write lock blocks on condition variable
vi) Once all readers are done with reading, the condition variable woken up signalling the waiting writer thread

Bugs:

If readers take same amount as writers, then writers are severely starved and may not even get a chance to hold the lock. I will simulate this in next write.


For brevity, error checks are offloaded to readers and users!

Here is the code then. Execute, test and enjoy! You are open to provide comments on improvements.

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

typedef struct my_rwlock {
    pthread_cond_t   rw_cond;
    pthread_mutex_t  rw_mutex;
    int              num_readers;
} my_rwlock_t;

#define MY_RWLOCK_INITIALIZER {PTHREAD_COND_INITIALIZER, PTHREAD_MUTEX_INITIALIZER, 0}

my_rwlock_t g_rw_lock = MY_RWLOCK_INITIALIZER;

void
my_rwlock_init (my_rwlock_t *rw_lock)
{
    if (!rw_lock) {
        return;
    }

    memset(rw_lock, 0, sizeof(my_rwlock_t));
}

void
my_rwlock_read_lock (my_rwlock_t *rw_lock)
{
    if (!rw_lock) {
        return;
    }

    pthread_mutex_lock(&rw_lock->rw_mutex);
    rw_lock->num_readers++;
    pthread_mutex_unlock(&rw_lock->rw_mutex);
}

void
my_rwlock_read_unlock (my_rwlock_t *rw_lock)
{
    if (!rw_lock) {
        return;
    }

    pthread_mutex_lock(&rw_lock->rw_mutex);
    if (rw_lock->num_readers) {
        rw_lock->num_readers--;
        if (!rw_lock->num_readers) {
            pthread_cond_signal(&rw_lock->rw_cond);
        }
    }
    pthread_mutex_unlock(&rw_lock->rw_mutex);
}

void
my_rwlock_write_lock (my_rwlock_t *rw_lock)
{
    if (!rw_lock) {
        return;
    }

    pthread_mutex_lock(&rw_lock->rw_mutex);
    if (rw_lock->num_readers) {
        pthread_cond_wait(&rw_lock->rw_cond, &rw_lock->rw_mutex);
    }
}

void
my_rwlock_write_unlock (my_rwlock_t *rw_lock)
{
    if (!rw_lock) {
        return;
    }

    pthread_mutex_unlock(&rw_lock->rw_mutex);
}

void*
thread_routine1 (void *arg)
{
    for (;;) {
        my_rwlock_read_lock(&g_rw_lock);
        printf("Grabbed read-lock -- 1\n");
        sleep(5);
        my_rwlock_read_unlock(&g_rw_lock);
        sleep(5);
    }
}

void*
thread_routine2 (void *arg)
{
    for (;;) {
        my_rwlock_read_lock(&g_rw_lock);
        printf("Grabbed read-lock -- 2\n");
        sleep(8);
        my_rwlock_read_unlock(&g_rw_lock);
        sleep(5);
    }
}

void*
thread_routine3 (void *arg)
{
    for (;;) {
        my_rwlock_write_lock(&g_rw_lock);
        printf("Grabbed write-lock -- 1\n");
        sleep(5);
        my_rwlock_write_unlock(&g_rw_lock);
        sleep(5);
    }
}

void*
thread_routine4 (void *arg)
{
    for (;;) {
        my_rwlock_write_lock(&g_rw_lock);
        printf("Grabbed write-lock -- 2\n");
        sleep(8);
        my_rwlock_write_unlock(&g_rw_lock);
        sleep(5);
    }
}

int
main (int argc, char *argv[])
{
    pthread_t tid[4];

    pthread_create(&tid[0], NULL, thread_routine1, NULL);
    pthread_create(&tid[1], NULL, thread_routine2, NULL);
    pthread_create(&tid[2], NULL, thread_routine3, NULL);
    pthread_create(&tid[3], NULL, thread_routine4, NULL);

    for (;;) {
        sleep(10);
    }
}