Readers–Writers Problem & Semaphore Solution – Study Notes

Chapter 1 – Introduction: Revisiting Classic Synchronisation Problems

• Recap of previous lecture: Bounded‐Buffer/Producer–Consumer problem solved with semaphores.

• Today’s focus: Readers–Writers problem – another classic synchronisation scenario.

• Scenario Definition
– A shared database is concurrently accessed by several processes.
– Two distinct classes of processes:
1. Readers → only perform read (no modification).
2. Writers → perform both read and write (update) operations.

• Key Observations
– Concurrent reads by multiple readers cause no side-effects; i.e. data remain unchanged.
– Any overlap that involves at least one writer (writer + reader, or writer + writer) can corrupt data or yield inconsistent views ("chaos").
– Requirement: Writers must obtain exclusive access to the database when modifying.

• Why classified as a synchronisation problem?
– We must coordinate concurrent processes so that safety (no simultaneous conflicting access) and liveness (everyone eventually proceeds) are upheld.

Chapter 2 – Problem Restatement & Synchronisation Goals

• Formal statement: "Allow multiple readers to read simultaneously unless a writer is writing. Only one writer may write at a time, and writers must not write while any reader is active."

• Variants
– Reader-priority, Writer-priority, Fair (no starvation). Current lecture uses reader-priority implementation.

• General Rules enforced:

  1. Readers may share the database with other readers.

  2. A Writer requires exclusive (mutual-exclusion) access.

• Solution Ingredients
– Two binary semaphores.
– One ordinary integer variable.

  1. \text{mutex}
    Initial value = 1.
    Purpose : Protect the critical section in which \text{readCount} is updated (ensures atomicity of increment/decrement operations).

  2. \text{WRT} (pronounced "write")
    Initial value = 1.
    Shared by both readers and writers; provides mutual exclusion for actual database access by writers (and by first/last reader, as we shall see).

  3. \text{readCount} (integer)
    Initial value = 0.
    Tracks the current number of readers inside the critical section.

• Remember: \text{mutex} and \text{WRT} are semaphores (binary), whereas \text{readCount} is a plain variable.

Chapter 3 – Writer Algorithm Walk-through

Pseudo-code skeleton (reader-priority flavour):

do {
    wait(WRT);          // request exclusive access
    /*  critical section: perform WRITE  */
    signal(WRT);        // release exclusive access
    /* remainder section */
} while (true);

Explanation & Trace

  1. wait(WRT) – If no other reader/writer holds \text{WRT} the writer enters, else it blocks.

  2. In the critical section the writer updates the database.

  3. signal(WRT) – Releases the semaphore; now either another writer or readers may acquire it.

Key property: During ownership of \text{WRT}, all other entities (writers or first/last reader) are excluded, guaranteeing single-writer safety.

Chapter 4 – Reader Algorithm Walk-through

Pseudo-code skeleton:

do {
    /* Entry section */
    wait(mutex);
        readCount++;
        if (readCount == 1)
            wait(WRT);   // first reader locks writers out
    signal(mutex);

    /*  critical section: perform READ  */

    /* Exit section */
    wait(mutex);
        readCount--;
        if (readCount == 0)
            signal(WRT); // last reader unlocks writers
    signal(mutex);
    /* remainder section */
} while (true);

Detailed Explanation

  1. Entry – locking \text{mutex} ensures modifications of \text{readCount} are atomic.

  2. Increment \text{readCount}; the arriving reader announces its presence.

  3. First Reader Rule – If \text{readCount} = 1, this is the first active reader, so it performs wait(WRT).
    – Consequence: Writers are blocked while any reader is present.

  4. signal(mutex) – Releases protection so further readers may concurrently modify \text{readCount} (one at a time) and proceed.

  5. Critical Section – Reader accesses database concurrently with other readers.

  6. Exit — wait(mutex) again to safely decrement \text{readCount}.

  7. Last Reader Rule – When \text{readCount} = 0 after decrement, the last reader performs signal(WRT), re-enabling writers.

  8. Release \text{mutex}.

Concurrency Insight
• Multiple readers may be inside simultaneously because after first reader released \text{mutex}, further readers can fast-path into the DB.
• Writers must wait until all readers exit because \text{WRT} remains held until \text{readCount} drops to 0.

Chapter 5 – Correctness Arguments & Properties

Safety Conditions Satisfied

  1. Mutual exclusion for writers – \text{WRT} is binary; only one writer can hold it at a time.

  2. No reader–writer overlap – First reader locks \text{WRT}; writers cannot proceed while readers present.

  3. Readers can coexist – \text{WRT} is not re-acquired by subsequent readers; only \text{mutex} (quick) is used, allowing parallel reads.

Progress & Priority
• Reader-priority: If readers continually arrive, writers may starve (because \text{readCount} may never become zero). Alternative variants adjust to give writers priority or fairness.

Deadlock Freedom
• Semaphore acquisition ordering is consistent (each reader locks \text{mutex} before possibly \text{WRT}; writer locks only \text{WRT}). No circular wait -> no deadlock.

Chapter 6 – Illustrative Example Trace

Suppose the following timeline:

  1. Reader R1 arrives (readCount = 0).
    – Locks \text{mutex}, sets readCount = 1, locks \text{WRT}, releases \text{mutex}.

  2. Concurrently, Reader R2 arrives.
    – Waits for \text{mutex}, increments readCount = 2, (skip wait(WRT) because not first), releases \text{mutex}.

  3. Writer W1 arrives.
    – Attempts wait(WRT) but blocks (held by R1).

  4. R1 finishes: in exit, locks \text{mutex}, readCount = 1, no signal(WRT)$, releases \text{mutex}.

  5. R2 finishes: exit decrements readCount = 0, signals \text{WRT} (unblocks W1).

  6. W1 enters, performs write, then signals \text{WRT}, permitting next readers/writers.

Data integrity is preserved throughout.

Chapter 7 – Connections & Broader Context

• Relates to critical section problem, mutual exclusion, semaphore primitives introduced earlier.

• Real-world analogies
– Database management systems (locking modes: shared vs. exclusive).
– File systems (read locks vs. write locks).
– Version-control tools (checkout vs. commit).

• System Design Implications
– Need to balance throughput (many readers) against fairness (writers not starving).
– Potential performance bottleneck when read-to-write ratio is extreme.

• Ethical/Practical Considerations
– Incorrect locking can yield data loss, inconsistent user views, financial errors.
– Starvation must be mitigated in production systems to maintain QoS agreements.

Chapter 8 – Key Takeaways & Formulae Recap

Variables & Initialisations

mutex = 1,\qquad WRT = 1,\qquad readCount = 0

Essential Rules Summarised

  1. First reader performs wait(WRT); last reader performs signal(WRT).

  2. Every reader change to readCount is bracketed by wait(mutex) / signal(mutex).

  3. Writer simply performs wait(WRT) / signal(WRT)$$ around its critical section.

Benefits of Semaphore Solution
• Simple, portable.
• Avoids busy waiting when semaphores are blocking primitives.

Limitations
• Reader-priority variant can starve writers.
• Requires careful ordering to avoid deadlock (variant implementations may complicate ordering).

Practice Questions

  1. Modify the algorithm to give writer-priority; what changes to semaphore ordering are needed?

  2. Analyse starvation risk with varying arrival rates of readers/writers; propose mitigation strategies.

End of study notes.