Readers-Writers Problem: Starvation Analysis with Semaphores

1. Defining the Readers-Writers Problem

Imagine a shared database or file. We have two types of processes:

• Readers: These processes only read the data. They don't modify it.
• Writers: These processes modify or update the data.

The synchronization constraints are:

1. Multiple readers are allowed to read the shared data at the same time.
2. A writer must have exclusive access. When a writer is accessing the data, no other process (reader or writer) can be in the critical section.

To understand why this is a synchronization challenge, let's watch a short video that clearly outlines the scenarios we need to manage.

As the video explained, the problematic cases are Read-Write, Write-Read, and Write-Write. Our goal is to design a system that prevents these while allowing the Read-Read scenario to happen concurrently.

2. A Semaphore Solution: The Reader's Preference Model

A common way to solve this problem is by using semaphores. This solution requires one integer variable and two binary semaphores:

• readcount: An integer to keep track of how many readers are currently in the critical section. Initialized to 0.
• mutex: A binary semaphore to ensure mutual exclusion when updating readcount. Initialized to 1.
• wrt: A binary semaphore that writers use to gain exclusive access. It's also used by the first reader to lock out any writers. Initialized to 1.

Here is the pseudocode for the reader and writer processes. This structure is fundamental and frequently appears in GATE questions.

Writer Process:

while (true) {
    wait(wrt);
    
    // ... Critical Section: Writing is performed ...
    
    signal(wrt);
}

Reader Process:

while (true) {
    // --- Entry Section ---
    wait(mutex);
    readcount++;
    if (readcount == 1) {
        wait(wrt); // First reader in locks out writers
    }
    signal(mutex);
    
    // ... Critical Section: Reading is performed ...
    
    // --- Exit Section ---
    wait(mutex);
    readcount--;
    if (readcount == 0) {
        signal(wrt); // Last reader out allows writers in
    }
    signal(mutex);
}

Let's break down the logic:

• Writer: The writer's logic is simple. It must acquire the wrt lock before writing. This single semaphore ensures that only one writer can be in the critical section and that no readers can enter while a writer is active (as we'll see below).
• Reader (Entry): The first reader to arrive (readcount == 1) is responsible for locking the wrt semaphore. This blocks any waiting writers. Subsequent readers increment readcount but don't need to touch wrt, as it's already locked. The mutex semaphore is crucial here to prevent a race condition on the readcount variable itself.
• Reader (Exit): The last reader to leave (readcount == 0) is responsible for releasing the wrt lock, which allows a waiting writer to finally enter its critical section.

To see this logic in action, let's trace through the execution step-by-step.

3. The Flaw in the "Reader's Preference" Solution: Starvation

This solution works correctly in terms of preventing data inconsistency. However, it has a significant fairness problem. Notice that as long as at least one reader is in the critical section, new readers can keep entering, but no writer can get in. This can lead to starvation.

To understand what this means, let's explore a scenario where a writer is blocked indefinitely.

In summary, the solution we've analyzed gives preference to readers. If there is a constant stream of incoming readers, a writer might have to wait forever. This is a crucial point of analysis for the GATE exam, where questions often ask you to evaluate the properties (like fairness or freedom from starvation) of a given synchronization algorithm.

Test your understanding!

Analyze the code in the image below, which represents the standard Reader's Preference solution. Is this solution susceptible to starvation? If so, which process type (reader or writer) is at risk of starvation, and under what conditions?

Show answer

Yes, this solution is susceptible to starvation.

The writer process is at risk of starvation.

This happens if there is a continuous stream of reader processes arriving. For example:

1. Reader R1 enters. readcount becomes 1. R1 executes wait(wrt), acquiring the lock.
2. A Writer W1 arrives. It executes wait(wrt) and blocks.
3. Reader R2 arrives. It passes the wrt check because readcount is already greater than 0. It enters the critical section. readcount is now 2.
4. Reader R1 leaves. readcount becomes 1. Since readcount is not 0, signal(wrt) is not called.
5. Reader R3 arrives before R2 leaves. It enters, and readcount goes back to 2.

As long as there is always at least one reader in the critical section, readcount will never become 0. Consequently, the signal(wrt) call in the reader's exit section will never be executed, and the waiting writer W1 will be starved.

4. Applying the Concepts to a GATE Problem

Now, let's put your understanding to the test with a real GATE question. This question presents the code structure and asks you to fill in the missing semaphore operations. This is a very common format that tests your deep understanding of the logic flow.

Conclusion

In this lesson, we dissected the Readers-Writers problem, a more complex synchronization scenario than the Producer-Consumer problem. We analyzed the standard "reader's preference" solution and, most importantly, identified its critical flaw: the potential for writer starvation.

Key Takeaways:

• The Readers-Writers problem allows concurrent access for readers but requires exclusive access for writers.
• The standard semaphore solution uses a readcount variable, a mutex to protect it, and a wrt semaphore for writer exclusion.
• The first reader to enter the critical section locks out writers, and the last reader to leave allows them in.
• This reader-preference model is not fair and can lead to writer starvation if readers continuously occupy the critical section.

We've now seen how improper semaphore usage can lead to deadlock (in the Producer-Consumer problem) or starvation (in the Readers-Writers problem). In our next lesson, we will begin a new module dedicated to Deadlock. We will formally define the four necessary conditions for deadlock to occur and learn how to model and detect it using Resource Allocation Graphs.