Readers-Writers Problem

We have a shared memory area where multiple read and write actions occur. This memory area is shared by several threads, which are of two types: readers (perform read actions from the memory area) and writers (perform write actions to the memory area).

In this context, we have some constraints:

A writer can write to the memory area only if there are no readers currently reading from the same area and if there is no other writer writing to the same memory area simultaneously.
A reader can read from the memory area only if there is no writer currently writing to the memory area; however, multiple readers can read in parallel from the same memory area.

For this problem, there are two solutions:

Using mutual exclusion with reader priority.
Using conditional synchronization with writer priority.

Solution with Mutual Exclusion

In this solution, a reader will not wait for other readers to finish reading the memory area, even if there is a waiting writer. A writer may have to wait for a long time if there are many writers, which can lead to a phenomenon called writer's starvation.

Additionally, a writer cannot enter while there is already a writer writing to the shared memory area.

Pseudocode:

// Number of readers reading from the common resource simultaneously
int readers = 0;

// Mutex (or semaphore) used to modify the number of readers
mutex mutexNumberOfReaders; // or semaphore mutexNumberOfReaders(1);

// Semaphore (or mutex) used to protect the common resource
semaphore readWrite(1); // or mutex readWrite

reader(int id) {
    while (true)
        mutexNumberOfReaders.lock();
        readers = readers + 1;
        // If it's the first reader, reserve the memory area to prevent any writers from entering
        if (readers == 1) {
            readWrite.acquire();
        }
        mutexNumberOfReaders.unlock();

        // Read from the common resource;

        mutexNumberOfReaders.lock();
        readers = readers - 1;
        // If it's the last reader, release the memory area that was read
        if (readers == 0) {
            readWrite.release();
        }
        mutexNumberOfReaders.unlock();
    }
}

writer(int id) {
    while (true) {
        // The writer enters the common resource
        readWrite.acquire();

        // Write to the common resource;

        // The writer releases the resource
        readWrite.release();
    }
}

Solution with Conditional Synchronization

Using this solution, no reader will enter the shared memory area as long as there is a writer writing in the memory area. Additionally, no other writer can enter while there is already a writer inside the shared memory area.

Pseudocode:

// Readers who are reading from the memory area
int readers = 0;

// Writers who are writing to the memory area
// (there will be only one, multiple writers cannot write simultaneously)
int writers = 0;

int waiting_readers = 0; // Readers waiting to enter the memory area
int waiting_writers = 0; // Writers waiting to enter the memory area

// Semaphore used to put writers on hold if there is a writer
// or one or more readers in the memory area (critical section)
semaphore sem_writer(0);

// Semaphore used to put readers on hold if there is a writer writing to the memory area
// or if there are writers waiting (because they have priority over readers)
semaphore sem_reader(0);

// Semaphore used as a mutex to protect the memory area (critical section)
semaphore enter(1);

reader(int id) {
    while (true) {
        enter.acquire();

        // If we have at least one writer writing to the common resource
        // or if we have a writer waiting, the reader waits
        if (writers > 0 || waiting_writers > 0) {
            waiting_readers++;
            enter.release();
            sem_reader.acquire();
        }

        readers++;

        if (waiting_readers > 0) {
            // Another reader has entered the common resource,
            // exiting the waiting state
            waiting_readers--;
            sem_reader.release();
        } else if (waiting_readers == 0) {
            enter.release();
        }

        // Read from the shared memory area
        enter.acquire();
        readers--;

        if (readers == 0 && waiting_writers > 0) {
            waiting_writers--;
            sem_writer.release();
        } else if (readers > 0 || waiting_writers == 0) {
            enter.release();
        }
    }
}

writer(int id) {
    while (true) {
        enter.acquire();

        if (readers > 0 || writers > 0) {
            waiting_writers++;
            enter.release();
            sem_writer.acquire();
        }

        writers++;

        enter.release();

        // Write to the shared memory area

        enter.acquire();

        writers--;

        if (waiting_readers > 0 && waiting_writers == 0) {
            waiting_readers--;
            sem_reader.release();
        } else if (waiting_writers > 0) {
            waiting_writers--;
            sem_writer.release();
        } else if (waiting_readers == 0 && waiting_writers == 0) {
            enter.release();
        }
    }
}

Solution with Mutual Exclusion​

Solution with Conditional Synchronization​

Solution with Mutual Exclusion

Solution with Conditional Synchronization