Reader Writer Problem

Tags: comp-arch

Is a problem in multi-threaded systems where we want to allow multiple threads read-access to a data-store (example a HashMap) but we want to only allow one thread to write to the store and block other threads from reading while it's being written to.

int writers; // Number writer threads that want to enter the critical section (some or all of these may be blocked)
int writing; // Number of threads that are actually writing inside the critical section (can only be zero or one)
int reading; // Number of threads that are actually reading inside the critical section
// if writing !=0 then reading must be zero (and vice versa)

reader() {
    lock(&m);
    // Block until any thread waiting to write has written.
    // This gets around starvation by preventing any reads while writes are pending.
    while (writers)
	cond_wait(&turn, &m);
    reading++;
    unlock(&m);

    // perform reading here
    // We have to unlock the lock so multiple threads can read simultaneously
    // although only one can modify `reading' at any time.

    lock(&m);
    reading--;
    cond_broadcast(&turn); // Wake up all the sleeping threads.
    unlock(&m);
}

writer() {
    lock(&m);
    writers++;
    // Block while data's being read or we're already writing something.
    while (reading || writing)
	cond_wait(&turn, &m);
    writing++;
    unlock(&m);

    // perform writing here

    lock(&m);
    writing--;
    writers--;
    cond_broadcast(&turn); // Wake up all the sleeping threads.
    unlock(&m);
}

Code Snippet 1: Implementation of a concurrent reader-writer access pattern. Uses separate variables for threads wanting to write and those actually writing to get around the starvation issue.

Links to this note

Starvation