Reader-Writer Problem

Reader-Writer Problem

Problem Description
The Reader-Writer Problem is a classic concurrency synchronization problem in operating systems. It simulates a scenario where multiple processes (or threads) concurrently access a shared data area (such as a file, database, etc.). These processes are divided into two categories:

Reader: Only reads data and does not modify it.
Writer: Writes (modifies) data.

The core of the problem lies in ensuring synchronization to meet the following requirements:

Correctness Requirements:
1. Write-Write Mutual Exclusion: Any two writers cannot access the shared data simultaneously.
2. Read-Write Mutual Exclusion: A writer and a reader also cannot access the shared data simultaneously.
Performance Requirements:
1. Read-Read Concurrency: Multiple readers can access the shared data simultaneously, as this does not lead to data inconsistency.
2. Fairness: Should prevent "starvation" of readers or writers. For example, if new readers keep arriving, it might cause writers to be unable to execute for a long time.

Solution Process (Evolution of Solutions)

We will start with the simplest solution and gradually optimize it to finally achieve a fair solution.

Step 1: The First Reader-Writer Problem (Readers-Priority)

This scheme prioritizes reader concurrency but may lead to writer starvation.

Core Idea:
- Use a mutex (mutex) to protect a counter (read_count).
- Use a write lock (wrt) to implement write-write and read-write mutual exclusion.
- The counter read_count is used to record the number of readers currently reading.
Required Variables:
- int read_count = 0; (number of active readers)
- semaphore mutex = 1; (mutex lock to protect read_count)
- semaphore wrt = 1; (mutex lock for writers and between readers & writers)

Algorithm Flow:

Writer Process:

do {
    wait(wrt);   // Acquire write lock
    // ... Perform write operation ...
    signal(wrt); // Release write lock
} while (true);

The writer is simple; it must exclusively hold the wrt lock before writing. As long as it holds this lock, other writers and readers cannot enter the critical section.

Reader Process:

do {
    wait(mutex);           // Request permission to modify read_count
    read_count++;          // Increment reader count
    if (read_count == 1) { // If I am the first reader
        wait(wrt);         // I need to acquire the write lock to block writers
    }
    signal(mutex);         // Release permission to modify read_count, allowing other readers to modify the count

    // ... Perform read operation ...   // Multiple readers can read here simultaneously

    wait(mutex);           // Request permission to modify read_count
    read_count--;          // Decrement reader count
    if (read_count == 0) { // If I am the last reader leaving
        signal(wrt);       // Release the write lock, allowing writers to enter
    }
    signal(mutex);         // Release permission to modify read_count
} while (true);

Working Principle Analysis:
- First Reader: When the first reader arrives, it acquires the wrt lock. All writers arriving after this will be blocked on wait(wrt).
- Subsequent Readers: Subsequent readers arriving after the first one only increment read_count and do not attempt to acquire the wrt lock (because the condition if (read_count == 1) is false), so they can start reading immediately. This achieves "read-read concurrency".
- Reader Departure: Each departing reader decrements the count. Only when the last reader leaves is the wrt lock released.
- Writer Starvation: If readers keep arriving continuously (i.e., new readers always arrive before the previous group of readers have all left), then read_count will never drop to 0, the wrt lock will never be released, causing writers to wait indefinitely (starvation).

Step 2: The Second Reader-Writer Problem (Writers-Priority)

This scheme aims to increase writer priority to avoid writer starvation. When a writer is waiting, newly arriving readers must wait.

Core Idea:
- Based on "Readers-Priority," add a semaphore (read_try) and a counter (write_count) along with its protection lock.
- The read_try semaphore implements the "writers-priority" rule: when a writer is ready to write, it blocks new readers from entering the queue.
Required Variables (added on top of Step 1):
- int write_count = 0; (number of writers waiting or writing)
- semaphore mutex2 = 1; (used to protect write_count)
- semaphore read_try = 1; (key semaphore for implementing "writers-priority")

Algorithm Flow:

Writer Process:

do {
    wait(mutex2);          // Protect write_count
    write_count++;
    if (write_count == 1) {
        wait(read_try);    // First writer blocks new readers
    }
    signal(mutex2);

    wait(wrt);            // Acquire write lock
    // ... Perform write operation ...
    signal(wrt);          // Release write lock

    wait(mutex2);
    write_count--;
    if (write_count == 0) {
        signal(read_try); // No writers left, allow new readers
    }
    signal(mutex2);
} while (true);

Reader Process:

do {
    wait(read_try);       // Try to read, but may be blocked by writers
    wait(mutex);
    read_count++;
    if (read_count == 1) {
        wait(wrt);
    }
    signal(mutex);
    signal(read_try);     // Once in ready-to-read state, release read_try

    // ... Perform read operation ...

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

Working Principle Analysis:
- Writer Arrival: The first writer acquires the read_try lock. New readers arriving after this will be blocked on wait(read_try), unable to join the queue, thus achieving writers-priority.
- Existing Readers: Readers who started reading before the writer arrived, or readers who have already passed wait(read_try), can continue. But new readers must wait.
- This solves writer starvation but may lead to reader starvation (if writers keep arriving continuously).

Step 3: Fair Reader-Writer Problem

The fairest solution follows the "First-Come, First-Served" principle, regardless of whether it's a reader or writer. This can be achieved using an additional mutual exclusion semaphore.

Core Idea:
- Use a global queueing semaphore (queue). All processes (readers and writers) must queue on this semaphore before attempting to access the shared data.
- This semaphore doesn't care if you are a reader or writer; it only guarantees the order of requests.
Required Variables:
- semaphore queue = 1; (global queueing lock)
- semaphore wrt = 1; (write lock)
- int read_count = 0;
- semaphore mutex = 1; (protects read_count)

Algorithm Flow:

Writer Process:

do {
    wait(queue);   // Enter global queue
    wait(wrt);     // Acquire write lock
    signal(queue); // Release queue lock, allowing others to queue

    // ... Perform write operation ...

    signal(wrt);   // Release write lock
} while (true);

Reader Process:

do {
    wait(queue);   // Enter global queue

    wait(mutex);
    read_count++;
    if (read_count == 1) {
        wait(wrt); // First reader acquires write lock
    }
    signal(mutex);

    signal(queue); // Release queue lock, allowing others to queue

    // ... Perform read operation ...

    wait(mutex);
    read_count--;
    if (read_count == 0) {
        signal(wrt); // Last reader releases write lock
    }
    signal(mutex);
} while (true);

Working Principle Analysis:
- Fairness: The queue semaphore forms a "corridor." Both readers and writers must queue in this "corridor" first. This guarantees strict first-come, first-served service.
- For example, if the execution order is Reader A -> Writer B -> Reader C:
  1. Reader A first acquires the queue lock, then acquires the wrt lock, then releases the queue lock and starts reading.
  2. Writer B arrives, acquires the released queue lock, but when it tries to acquire the wrt lock, it gets blocked (because Reader A holds it), so Writer B waits after the queue lock.
  3. Reader C arrives, tries to acquire the queue lock, but the lock is held by Writer B, so Reader C is blocked on queue.
  4. Reader A finishes reading, releases the wrt lock.
  5. The blocked Writer B acquires the wrt lock, performs the write operation, and after finishing, releases the wrt and queue locks.
  6. Reader C finally acquires the queue lock and begins its process.
- This method effectively prevents starvation for any party and achieves fair access.