Writers Preference

The Readers Preference solution's Achilles' heel is writer starvation. In systems where writes carry time-sensitive information—stock prices, security patches, configuration updates—indefinite writer delays are unacceptable. The Writers Preference solution, also known as the Second Readers-Writers Problem, inverts the priority: writers take precedence over waiting readers.

This approach fundamentally changes the synchronization dynamics. When a writer is waiting, no new readers may start. Readers currently in the critical section finish, but all newly arriving readers must wait behind the writer. This guarantees that writers eventually access the resource, but at the cost of potentially starving readers under write-heavy workloads.

The need for writer priority arises in scenarios where write delays have consequences beyond simple latency.

Scenario 1: Security Updates

Consider a security system where a critical patch must be applied to a shared policy table. Until the patch is applied, the system remains vulnerable. If readers (policy checks) continuously arrive, the security update starves—the vulnerability persists indefinitely. Writer priority ensures security updates complete promptly.

Scenario 2: Real-Time Data Feeds

A stock trading system receives price updates (writes) and serves price queries (reads). Stale prices can lead to incorrect trades. If a price update waits behind thousands of queries, trades execute on outdated information. Losses accumulate. Writer priority ensures price updates propagate immediately.

Scenario 3: Consistency Requirements

Some systems require writes to complete before related reads can proceed. If a write creates a new resource, subsequent reads must see it. Writer starvation breaks this semantic—reads keep returning 'not found' because the creating write never executes.

Implementing writer priority is more complex than reader priority. The challenge is allowing current readers to finish while blocking new readers when a writer waits.

The Core Question:

How do we communicate to arriving readers that a writer is waiting, so they should block even though other readers are still in the critical section?

Attempted Solution: Simple Flag

A naive approach adds a writer_waiting flag:

Why This Fails:

1. Race condition on flag: Multiple readers might check writer_waiting simultaneously with a writer setting it
2. What do blocked readers wait on? We need a synchronization primitive, not just a flag
3. How do readers know when to proceed? After the writer finishes, blocked readers must be woken
4. Multiple writers: If multiple writers wait, we need ordered wakeup

Required Additional State:

The Writers Preference solution needs:

• A count of waiting/active writers (not just readers)
• A mechanism to block new readers when writers wait
• Coordination between writers and the reader-blocking mechanism

This requires additional semaphores beyond those in the Readers Preference solution.

The Writers Preference solution uses four synchronization primitives. Let's develop it systematically with detailed annotations.

Understanding the Synchronization Primitives:

The Key Insight: read_try as a Gate

The read_try semaphore is the crucial addition. When no writers are waiting, read_try == 1 and readers pass through immediately. When the first writer arrives, it acquires read_try, setting it to 0. All subsequent readers block at wait(read_try) until all writers finish.

This creates a "velvet rope" effect: readers currently inside can finish, but new readers must wait behind the writer.

Let's trace through execution scenarios to understand how writer priority works.

Scenario 1: Writer Arrives While Reader Active

Key Observation: R2 arrived before W1 finished, but R2 was blocked. W1 proceeded before R2 even though R2 was waiting. The writer jumped ahead of the reader. This is writer priority in action.

Scenario 2: Multiple Writers Queue

We now prove that the Writers Preference solution satisfies the required safety properties.

Theorem 1: Reader-Writer Mutual Exclusion Statement: Readers and writers are never in the critical section simultaneously.

Proof:

• Writers hold rw_mutex during their critical section
• The first reader acquires rw_mutex before entering
• If a writer holds rw_mutex, the first reader blocks at wait(rw_mutex)
• If readers hold rw_mutex, writers block at wait(rw_mutex)
• ∴ rw_mutex enforces mutual exclusion between readers and writers ∎

Theorem 2: Writer-Writer Mutual Exclusion Statement: At most one writer is in the critical section at a time.

Proof:

• Each writer must acquire rw_mutex before entering critical section
• rw_mutex is a binary semaphore
• Only one thread can hold a binary semaphore
• ∴ Only one writer can be in the critical section ∎

Theorem 3: Reader Concurrency Statement: Multiple readers can be in the critical section simultaneously.

Proof:

• Only the first reader acquires rw_mutex
• Subsequent readers check read_count > 1 and skip wait(rw_mutex)
• The read_try semaphore is acquired and immediately released by each reader
• Multiple readers can pass through read_try sequentially and all enter the critical section
• mutex only serializes access to read_count, not to the resource
• ∴ Multiple readers coexist in the critical section ∎

Theorem 4: Writer Priority (No Writer Starvation) Statement: A waiting writer eventually enters the critical section.

Proof:

• When a writer calls wait(write_mutex); write_count++, it's registered as waiting
• The first waiting writer acquires read_try
• With read_try held, no new readers can start (they block on wait(read_try))
• Active readers eventually finish (assuming no infinite loops in read)
• The last active reader signals rw_mutex
• The waiting writer acquires rw_mutex and enters
• ∴ Writers don't starve (assuming bounded reader critical sections) ∎

While the Writers Preference solution prevents writer starvation, it introduces the symmetric problem: reader starvation.

The Starvation Mechanism:

Starvation Condition:

Readers starve when: after blocking on wait(read_try), there exists an infinite execution trace where write_count never becomes 0.

This occurs when:

• Writers continuously arrive (faster than they complete)
• Each arriving writer finds write_count ≥ 1
• read_try is never signaled
• Readers wait indefinitely

Probability of Starvation:

Starvation probability depends on:

• Writer arrival rate vs. write completion rate
• Whether writers batch or spread over time
• System policies for scheduling writers

The Writers Preference solution has different performance characteristics than Readers Preference.

Overhead Analysis:

Critical Observations:

1. Reader entry is more expensive: Readers must acquire read_try (which may block), then mutex, potentially rw_mutex, then release mutex and read_try. This is 3-5 semaphore operations vs. 2-3 in Readers Preference.

2. read_try becomes a bottleneck: Unlike Readers Preference where readers only contend on mutex, here all readers serialize through read_try at entry AND exit. This reduces reader concurrency even when no writers are waiting.

3. Writer latency is bounded: Writers wait at most for active readers to finish. They're guaranteed to proceed after current readers exit.

Throughput Impact:

For read-heavy workloads, Writers Preference has lower throughput than Readers Preference because:

• Extra semaphore operations per reader
• Partial serialization through read_try
• Writers interrupt reader batches

However, for write-heavy workloads, Writers Preference may have better throughput because writers don't starve—they proceed efficiently.