Reader-writer Problem

system design

The reader-writer problem is another synchronization problem of accessing a shared resource between two different roles. The only constraint is that when someone is writing, no others are allowed to either read or write. This indicates that at a time there can be only one active writer or multiple active readers.

Reader-preference

With multiple readers allowed to concurrently access the shared resource, only the first and last readers are required to synchronize with writers. Once the first reader starts reading (while writers are blocked), subsequent readers are able to read as well. A writer is not allowed to access the shared resource until the last reader releases the occupation of it. Apparently this is reader-preference since writers can be locked out and starved by a steam of readers.

As an implementation, we use one binary semaphore to synchronize the access to the shared resource. We use another binary semaphore to coordinate the counting of readers which tells the first and last readers.

semaphore resource = 1; // synchronize the access to the shared resource
semaphore rMutex = 1; // synchronize the counting of readers
int readerCount = 0;

Writer()
{
    Wait(resource);
    Write();
    Post(resource);
}

Reader()
{
    Wait(rMutex);
    readerCount++;
    if (readerCount == 1)
    {
        Wait(resource);
    }
    Post(rMutex);

    Read();

    Wait(rMutex);
    readerCount--;
    if (readerCount == 0)
    {
        Post(resource);
    }
    Post(rMutex);
}

Writer-preference

We can also have a writer-preference strategy. Specifically, we allow readers to access the shared resource only if the last writer releases the occupation of it. Moreover, whenever a writer comes in, it immediately possesses higher priority over all existing readers that are waiting for the access to the shared resource.

Upon the reader-preference implementation, similarly, we use another binary semaphore to coordinate the counting of writers which tells the first and last writers. We further introduce an additional binary semaphore to deprioritize readers once there are writers coming.

semaphore resource = 1; // synchronize the access to the shared resource
semaphore readTry = 1; // deprioritize readers when there are writers 
semaphore rMutex = 1; // synchronize the counting of readers
semaphore wMutex = 1; // synchronize the counting of writers
int readerCount = 0;
int writerCount = 0;

Writer()
{
    Wait(wMutex);
    writerCount++;
    if (writerCount == 1)
    {
       Wait(readTry); 
    }
    Post(wMutex);

    Wait(resource);
    Write();
    Post(resource);

    Wait(wMutex);
    writerCount--;
    if (writerCount == 0)
    {
       Post(readTry); 
    }
    Post(wMutex);
}

Reader()
{
    Wait(readTry);
    Wait(rMutex);
    readerCount++;
    if (readerCount == 1)
    {
        Wait(resource);
    }
    Post(rMutex);
    Post(readTry);

    Read();

    Wait(rMutex);
    readerCount--;
    if (readerCount == 0)
    {
        Post(resource);
    }
    Post(rMutex);
}

Reader-writer fairness

When fairness is desired, readers and writers should have equal chances of accessing the shared resource. In other words, they want to be served by FIFO (first in, first out). The reader-preference approach just follows the nature of readers and writers, upon which a fairness can be further achieved by enforcing an additional synchronization at the beginning to every process/thread without distinguishing between readers and writers.

semaphore resource = 1; // synchronize the access to the shared resource
semaphore service = 1; // synchronize every process/thread for fairness
semaphore rMutex = 1; // synchronize the counting of readers
int readerCount = 0;

Writer()
{
    Wait(service);
    Wait(resource);
    Post(service);
    Write();
    Post(resource);
}

Reader()
{
    Wait(service);
    Wait(rMutex);
    readerCount++;
    if (readerCount == 1)
    {
        Wait(resource);
    }
    Post(service);
    Post(rMutex);

    Read();

    Wait(rMutex);
    readerCount--;
    if (readerCount == 0)
    {
        Post(resource);
    }
    Post(rMutex);
}

Contents