The readers-writers problem

The readers-writers problem is a classic synchronization issue that arises when multiple processes need to access shared data. There are two types of processes: readers, which only read the data, and writers, which both read and write the data. The problem is to ensure that while a writer is accessing the data, no other process (reader or writer) can access it simultaneously to avoid chaos. However, multiple readers can read the data concurrently without any issues.

Variations of the Readers-Writers Problem

1. First Readers-Writers Problem: No reader should wait for other readers to finish simply because a writer is waiting. This ensures that no reader is kept waiting unless a writer has already obtained permission to use the shared object.
2. Second Readers-Writers Problem: Once a writer is ready to write, it should be allowed to write as soon as possible. This means that if a writer is waiting, no new readers should start reading.

A solution to either problem may lead to starvation:

• In the first problem, writers may starve.
• In the second problem, readers may starve.

To address these issues, solutions must balance the needs of both readers and writers to prevent starvation.

Solution to the First Readers-Writers Problem

To solve the first readers-writers problem, we use the following data structures:

• semaphore rw_mutex = 1;
• semaphore mutex = 1;
• int read_count = 0;

Here’s how the semaphores and the read_count variable are used:

• rw_mutex ensures mutual exclusion for writers and is also used by the first or last reader entering or exiting the critical section.
• mutex ensures mutual exclusion when updating the read_count variable.
• read_count tracks the number of processes currently reading the data.

Writer Process

The writer process code ensures exclusive access while writing:

do {
    wait(rw_mutex);
    // Writing is performed
    signal(rw_mutex);
} while (true);

Reader Process

The reader process code ensures that multiple readers can read concurrently but prevents new readers if a writer is waiting:

do {
    wait(mutex);
    read_count++;
    if (read_count == 1)
        wait(rw_mutex);
    signal(mutex);

    // Reading is performed

    wait(mutex);
    read_count--;
    if (read_count == 0)
        signal(rw_mutex);
    signal(mutex);
} while (true);

In this solution:

• If a writer is in the critical section and readers are waiting, one reader is queued on rw_mutex, and others are queued on mutex.
• When a writer signals rw_mutex, either waiting readers or a single waiting writer will resume, as determined by the scheduler.

Reader-Writer Locks

Reader-writer locks are a generalization of the readers-writers problem. They allow a process to request a lock in either read or write mode:

• Multiple processes can acquire a reader-writer lock in read mode concurrently.
• Only one process can acquire the lock in write mode, ensuring exclusive access.

Reader-writer locks are particularly useful:

1. When it’s easy to distinguish between read-only and write processes.
2. In applications with more readers than writers, as the increased concurrency for readers compensates for the overhead of managing reader-writer locks.

The readers-writers problem and its solutions are foundational for understanding process synchronization and are implemented in many systems to manage concurrent access to shared resources.