notes/docs/lectures/osc/08_concurrency6.md

23/10/20

The readers-writers Problem

• Reading a record (or a variable) can happen in parallel without problems, writing needs synchronisation (or exclusive access).

• Different solutions exist:

  • Solution 1: naive implementation with limited parallelism
  • Solution 2: readers receive priority. No reader is kept waiting unless a writer already has access (writers may starve).
  • Solution 3: writing is performed as soon as possible (readers may starve).

Solution 1: No parallelism

void * reader(void * arg)
{
	while(1)
    {
        pthread_mutex_lock(&sync);
        printf("reading record\n");
        pthread_mutex_unlock(&sync);
    }
}
void * writer(void * writer)
{
    while(1)
    {
        pthread_mutex_lock(&sync);
        printf("writing\n");
        pthread_mutex_unlock(&sync);
    }
}

This prevents parallel reading.

Solution 2: Allows parallel reading

A correct implementation requires:

iReadCount: an integer tracking the number of readers

• if iReadCount > 0: writers are blocked sem_wait(rwSync)
• if iReadCount == 0: writers are released sem_post(rwSync)
• if already writing, readers must wait

sync: a mutex for mutual exclusion of iReadCount.

rwSync : a semaphore that synchronises the readers and writers, set by the first/last reader.

sync is used to mutex_lock and mutex_unlock when the iReadCount is being modified.

When iReadCount == 1, the sem_wait(&rwSync) is used to block the writer from writing. Further down in the code when iReadCount == 0, the sem_post(&rwSync) is called to 'wake up' the writer, so that it can write.

When we say 'send process to sleep' or 'wake up a process' we actually mean: move that process from the blocked queue to the ready queue (or visa versa).

If the iReadCount == 1 is run when the writer is writing. The sem_wait(&rwSync) will go from 0 -> -1, forcing the reader to go to sleep. As soon as the writer is done, the sem_post(&rwSync) is run meaning it goes from -1 -> 0, which wakes the reader up.

Unless iReadCount reaches 0, writing will not happen. This means writers can easily starve if there are multiple readers.

Solution 3: Gives priority to the writer

Solution 3 uses:

• iReadCount and iWriteCount: to keep track of the number of readers and writers.
• sRead/sWrite: to synchronise the reader/writer's critical section.
• sReadTry: to stop readers when there is a writer waiting.
• sResource: to synchronise the resource for reading/writing.

[explanation time stamp 43:35]

sRead and sWrite are used whenever iReadCount and iWriteCount are used respectively. Unlike the mutex in the last example it is important that the same semaphore variable isn't used for both iReadCount and iWriteCount.

There is no reason the read and write count cannot be changed at the same time. If you were to use the same semaphore then you would be limiting the parallelism of your code (slowing run time).

In the case iWriteCount == 1 the sReadTry is set from 1 -> 0, meaning that no new readers can attempt to read. For the writer to begin writing, it must wait for the readers to finish reading (due to the sResource semaphore.

So when iReadCount --, the reader checks if it is the last reader by iReadCount == 0, and if it is it unlocks sResource (-1->0) so that the writers can write. If more readers show up, they cannot enter as sReadTry == -1.

The last writer does the same thing, but instead of unlocking the resource it unlocks the sReadTry semaphore.