Readers Writers Problem - Learning Module

Loading content...

0/227

Writers Preference

Guaranteeing Writer Access

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.

What You Will Learn

By the end of this page, you will understand: why writer priority requires additional synchronization primitives; the complete implementation with four semaphores; how the 'writer waiting' signal blocks new readers; proof of correctness including starvation properties; performance implications of writer priority; and scenarios where writer preference is the right choice.

Motivation for Writer Priority

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.

When Writer Priority Matters
Domain	Write Operations	Consequence of Delay
Security	Policy updates, revocations	Extended vulnerability window
Finance	Price updates, trades	Stale data causes losses
Configuration	Feature flags, settings	Inconsistent behavior
Inventory	Stock updates	Overselling, stockouts
Messaging	New messages	Delayed communication

The Tradeoff

Writer priority doesn't eliminate starvation—it redirects it. While writers are protected, readers can now starve under continuous write load. The solution is appropriate when write delays are more costly than read delays, not when starvation should be eliminated entirely.

Design Challenges

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:

naive_writer_priority.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// BROKEN: Naive writer priority attempt
bool writer_waiting = false;  // Flag to indicate waiting writer
 
void reader() {
    if (writer_waiting)       // Check if writer is waiting
        wait(???);            // Problem: what do we wait on?
    
    wait(mutex);
    read_count++;
    if (read_count == 1)
        wait(rw_mutex);
    signal(mutex);
    
    read_data();
    
    // ... exit section
}
 
void writer() {
    writer_waiting = true;    // Signal to readers
    wait(rw_mutex);           // Wait for exclusive access
    writer_waiting = false;   // No longer waiting
    write_data();
    signal(rw_mutex);
}

Why This Fails:

Race condition on flag: Multiple readers might check writer_waiting simultaneously with a writer setting it
What do blocked readers wait on? We need a synchronization primitive, not just a flag
How do readers know when to proceed? After the writer finishes, blocked readers must be woken
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.

Complexity Increase

The Writers Preference solution requires 3-4 semaphores (vs. 2 for Readers Preference) and careful coordination. This additional complexity is the price of preventing writer starvation. Always consider whether your system actually needs writer priority before implementing it.

Complete Solution Implementation

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

writers_preference.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
/*
 * Second Readers-Writers Problem: Writers Preference Solution
 * 
 * Invariants:
 *   - Multiple readers can access the resource simultaneously (if no writers waiting)
 *   - Writers have exclusive access
 *   - Once a writer is waiting, no new readers start
 *   - Writers don't starve
 * 
 * Shared Variables:
 *   - read_count: Number of readers currently in critical section
 *   - write_count: Number of writers currently waiting or writing
 *   - mutex: Protects read_count
 *   - write_mutex: Protects write_count
 *   - rw_mutex: Mutual exclusion between readers and writers
 *   - read_try: Controls reader access (blocked when writer waiting)
 */
 
#include <semaphore.h>
 
// Reader tracking
int read_count = 0;           // Active readers
semaphore mutex = 1;          // Protects read_count
 
// Writer tracking
int write_count = 0;          // Waiting + active writers
semaphore write_mutex = 1;    // Protects write_count
 
// Access control
semaphore rw_mutex = 1;       // Resource access control
semaphore read_try = 1;       // Reader entry gate
 
/*
 * READER PROTOCOL (Writers Preference)
 * 
 * Entry: Must pass through read_try gate (blocked if writers waiting)
 * Exit: Last reader releases rw_mutex
 */
void reader(int id) {
    while (true) {
        // ========== ENTRY SECTION ==========
        
        /*
         * Step 1: Acquire read_try
         * This gate is held by waiting writers.
         * If a writer is waiting, readers block here.
         */
        wait(read_try);           // Gate: may block if writer waiting
        
        wait(mutex);              // Step 2: Lock read_count
        read_count++;             // Step 3: Increment reader count
        
        if (read_count == 1) {    // Step 4: First reader?
            wait(rw_mutex);       // Step 5: Block writers from resource
        }
        
        signal(mutex);            // Step 6: Unlock read_count
        signal(read_try);         // Step 7: Release gate for other readers
        
        // ========== CRITICAL SECTION ==========
        
        read_data(id);            // Actually read the resource
        
        // ========== EXIT SECTION ==========
        
        wait(mutex);              // Step 8: Lock read_count
        read_count--;             // Step 9: Decrement reader count
        
        if (read_count == 0) {    // Step 10: Last reader?
            signal(rw_mutex);     // Step 11: Allow writers to proceed
        }
        
        signal(mutex);            // Step 12: Unlock read_count
        
        // ========== REMAINDER SECTION ==========
        
        process_data(id);
    }
}
 
/*
 * WRITER PROTOCOL (Writers Preference)
 * 
 * Entry: First waiting writer acquires read_try to block new readers
 * Exit: Last writer releases read_try
 */
void writer(int id) {
    while (true) {
        // ========== ENTRY SECTION ==========
        
        wait(write_mutex);        // Step 1: Lock write_count
        write_count++;            // Step 2: Register as waiting writer
        
        if (write_count == 1) {   // Step 3: First writer?
            wait(read_try);       // Step 4: Block new readers
        }
        
        signal(write_mutex);      // Step 5: Unlock write_count
        
        wait(rw_mutex);           // Step 6: Wait for exclusive access
        
        // ========== CRITICAL SECTION ==========
        
        write_data(id);           // Exclusively modify resource
        
        // ========== EXIT SECTION ==========
        
        signal(rw_mutex);         // Step 7: Release exclusive access
        
        wait(write_mutex);        // Step 8: Lock write_count
        write_count--;            // Step 9: Deregister writer
        
        if (write_count == 0) {   // Step 10: Last writer?
            signal(read_try);     // Step 11: Allow readers again
        }
        
        signal(write_mutex);      // Step 12: Unlock write_count
        
        // ========== REMAINDER SECTION ==========
        
        prepare_next_write(id);
    }
}

Understanding the Synchronization Primitives:

Semaphore	Purpose	Initial Value
`mutex`	Protects `read_count`	1
`write_mutex`	Protects `write_count`	1
`rw_mutex`	Mutual exclusion for resource	1
`read_try`	Gate controlling reader entry	1

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.

Execution Trace Analysis

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

Scenario 1: Writer Arrives While Reader Active

trace_writer_priority.txt
Initial: read_count=0, write_count=0, all semaphores=1
 
Time 0: Reader R1 enters
  R1: wait(read_try) ✓     [read_try=0]
  R1: wait(mutex) ✓        [mutex=0]
  R1: read_count++ → 1
  R1: read_count==1: wait(rw_mutex) ✓  [rw_mutex=0]
  R1: signal(mutex)        [mutex=1]
  R1: signal(read_try)     [read_try=1]
  R1: ** READING **
 
Time 1: Writer W1 arrives (while R1 reading)
  W1: wait(write_mutex) ✓  [write_mutex=0]
  W1: write_count++ → 1
  W1: write_count==1: wait(read_try) ✓  [read_try=0]  ← Blocks new readers!
  W1: signal(write_mutex)  [write_mutex=1]
  W1: wait(rw_mutex) BLOCKS [rw_mutex=0, held by R1]
 
Time 2: Reader R2 arrives (while R1 reading, W1 waiting)
  R2: wait(read_try) BLOCKS [read_try=0]  ← R2 cannot start!
  
Time 3: R1 finishes reading
  R1: wait(mutex) ✓
  R1: read_count-- → 0
  R1: read_count==0: signal(rw_mutex)  [rw_mutex=1]
  R1: signal(mutex)
  
Time 3 (continued): W1 unblocks
  W1: wait(rw_mutex) ✓     [rw_mutex=0]
  W1: ** WRITING **
 
Time 4: W1 finishes
  W1: signal(rw_mutex)     [rw_mutex=1]  
  W1: wait(write_mutex) ✓
  W1: write_count-- → 0
  W1: write_count==0: signal(read_try)  [read_try=1]  ← Readers unblock!
  W1: signal(write_mutex)
 
Time 4 (continued): R2 unblocks
  R2: wait(read_try) ✓     [read_try=0]
  R2: proceeds to read...

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

trace_multiple_writers.txt
Assume R1 is reading, W1 waiting on rw_mutex, readers blocked on read_try
 
Time 5: Writer W2 arrives
  W2: wait(write_mutex) ✓
  W2: write_count++ → 2
  W2: write_count==1? NO (skip wait(read_try))  ← Read_try already held
  W2: signal(write_mutex)
  W2: wait(rw_mutex) BLOCKS  ← Behind W1
 
Time 6: R1 finishes, W1 proceeds
  W1: signal(rw_mutex)     [rw_mutex=1]
  W1: wait(rw_mutex) ✓     [rw_mutex=0]  ← W1 now writing
 
Time 7: W1 finishes
  W1: signal(rw_mutex)     [rw_mutex=1]
  W1: wait(write_mutex)
  W1: write_count-- → 1
  W1: write_count==0? NO (don't signal read_try)  ← W2 still waiting!
  W1: signal(write_mutex)
  
Time 7 (continued): W2 acquires rw_mutex
  W2: wait(rw_mutex) ✓     [rw_mutex=0]
  W2: ** WRITING **
  
Time 8: W2 finishes
  W2: signal(rw_mutex)
  W2: wait(write_mutex)
  W2: write_count-- → 0
  W2: write_count==0? YES: signal(read_try)  ← NOW readers can proceed
  W2: signal(write_mutex)

Reader Starvation Visible

In scenario 2, readers remained blocked while two writers executed consecutively. If writers continuously arrive, read_try never gets signaled, and readers starve. This is the symmetric starvation problem to the Readers Preference solution.

Proof of Correctness

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) ∎

Bounded Critical Sections Assumption

The 'no writer starvation' proof requires that readers eventually exit the critical section. If a reader can hold the resource indefinitely (deadlock, infinite loop, or blocking call), the writer waiting on rw_mutex might wait forever. This is a general requirement, not specific to this solution.

Reader Starvation Analysis

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

The Starvation Mechanism:

reader_starvation.txt
Timeline: Continuous writers, readers waiting
 
Time:    0    1    2    3    4    5    6    7    8    ...
         |----|----|----|----|----|----|----|----|----| ...
 
W1:      [====]                                           Writer 1
W2:           [====]                                      Writer 2  
W3:                [====]                                 Writer 3
W4:                     [====]                            Writer 4
...
 
write_count:  1    1    1    1    1    1    1    1    ... (never 0!)
read_try:     0    0    0    0    0    0    0    0    ... (always held)
 
R1:      [BLOCKED on read_try-----------------------------→   Starving
R2:      [BLOCKED on read_try-----------------------------→   Starving

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

Reader Starvation Risk Assessment
Workload Pattern	Starvation Risk	Mitigation Strategy
Low writer rate	Low	None needed
Bursty writes with gaps	Low	Readers proceed during gaps
Steady moderate writes	Medium	Monitor reader latency
High sustained writes	High	Consider fair solution
Write-storm events	Very High	Rate limit or queue writes

Production Impact

Reader starvation can cause user-visible failures: timeouts on read requests, 'service unavailable' errors, and degraded application performance. Systems using writer priority must monitor reader latency and have fallback strategies for write-storm scenarios.

Performance Characteristics

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

Overhead Analysis:

Per-Operation Semaphore Overhead
Operation	Wait Operations	Signal Operations	Notes
Reader Entry	3 (read_try, mutex, possibly rw_mutex)	2 (mutex, read_try)	More overhead than RP
Reader Exit	1 (mutex)	1-2 (mutex, possibly rw_mutex)	Similar to RP
Writer Entry	2 (write_mutex, possibly read_try) + 1 (rw_mutex)	1 (write_mutex)	More overhead than RP
Writer Exit	1 (write_mutex)	2-3	More overhead than RP

Critical Observations:

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.
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.
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.

Strengths

•Writers never starve
•Bounded writer latency
•Write-sensitive data stays fresh
•Good for write-heavy workloads
•Predictable write performance

Weaknesses

•Reader starvation possible
•Higher synchronization overhead
•Reduced reader concurrency
•More complex implementation
•Lower read throughput

Comparison with Readers Preference

Understanding when to choose Writers Preference over Readers Preference requires careful analysis of requirements.

Head-to-Head Comparison:

Readers vs Writers Preference
Property	Readers Preference	Writers Preference
Semaphores Required	2 (mutex, rw_mutex)	4 (mutex, write_mutex, rw_mutex, read_try)
Reader Entry Overhead	Low (2-3 ops)	Higher (3-5 ops)
Writer Entry Overhead	1 wait	2-3 waits
Max Concurrent Readers	Unbounded	Still unbounded (but serialized entry)
Reader Starvation	No	Yes (under writer load)
Writer Starvation	Yes (under reader load)	No
Implementation Complexity	Simple	Moderate
Best Throughput For	Read-heavy	Balanced/Write-heavy

Decision Framework:

Choose Readers Preference when:

Reads outnumber writes by 10:1 or more
Write latency is not time-sensitive
Reader throughput is the primary metric
Stale data is acceptable during write contention

Choose Writers Preference when:

Data freshness is critical
Write latency directly impacts correctness or user experience
Writes carry time-sensitive updates (prices, security, config)
Writer starvation would cause system failures
Read/write ratio is more balanced

Consider Fair Solutions

If both reader and writer starvation are unacceptable, neither Readers Preference nor Writers Preference is appropriate. Consider Fair (FIFO) solutions that guarantee bounded waiting for all threads. We'll explore these in the next page.

Implementation Considerations

Implementing Writers Preference correctly requires attention to subtle details.

Avoiding Common Bugs:

common_bugs.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
// BUG 1: Forgetting to release read_try immediately
void reader_buggy() {
    wait(read_try);          // Acquire gate
    wait(mutex);
    read_count++;
    if (read_count == 1)
        wait(rw_mutex);
    signal(mutex);
    // BUG: Forgot signal(read_try) here!
    // Result: Only one reader can ever enter
    
    read_data();
    // ...
}
 
// BUG 2: Wrong order of operations in writer
void writer_buggy() {
    wait(rw_mutex);          // BUG: Get resource access first
    wait(write_mutex);       // Then update write_count
    write_count++;
    if (write_count == 1)
        wait(read_try);      // Too late! Already blocked readers elsewhere
    signal(write_mutex);
    
    // Result: Writers don't properly block readers
}
 
// BUG 3: Releasing read_try in reader exit
void reader_exit_buggy() {
    wait(mutex);
    read_count--;
    if (read_count == 0) {
        signal(rw_mutex);
        signal(read_try);    // BUG: Reader shouldn't touch read_try in exit
    }
    signal(mutex);
    // Result: read_try signaled when there are still waiting writers
}

Testing for Correctness:

The increased complexity of Writers Preference makes thorough testing essential:

writer_pref_tests.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
// Test: Writers actually get priority
void test_writer_priority() {
    // Start a reader that holds for a while
    pthread_create(&t1, NULL, long_reader, NULL);
    usleep(100);  // Ensure reader is active
    
    // Start a writer
    uint64_t writer_queue_time = get_time_ns();
    pthread_create(&t2, NULL, writer, NULL);
    usleep(50);  // Writer is now waiting
    
    // Start another reader
    atomic_bool reader2_started = false;
    pthread_create(&t3, NULL, reader_with_flag, &reader2_started);
    
    // Wait for first reader to finish
    pthread_join(t1, NULL);
    
    // Check: writer should complete before reader2 starts
    pthread_join(t2, NULL);
    uint64_t writer_done_time = get_time_ns();
    
    assert(!reader2_started || reader2_started_after(writer_done_time));
    printf("Writer priority verified\n");
}
 
// Test: No starvation under moderate load
void test_no_immediate_starvation() {
    atomic_bool writer_completed = false;
    
    // Start readers continuously for 100ms
    stop_readers = false;
    for (int i = 0; i < 10; i++)
        pthread_create(&readers[i], NULL, continuous_reader, NULL);
    
    usleep(10000);  // Let readers establish
    
    // Start a writer
    pthread_create(&writer_thread, NULL, timed_writer, &writer_completed);
    
    // Writer should complete within reasonable time
    // (unlike Readers Preference where it might never complete)
    usleep(500000);  // 500ms
    assert(writer_completed && "Writer should have completed!");
    
    stop_readers = true;
}

Deadlock Potential

If a thread that holds read access needs to upgrade to write access, it cannot do so directly in Writers Preference. The thread would block on rw_mutex (held by itself as a reader) waiting for itself to exit. Upgradable locks require special mechanisms not present in the basic solution.

Summary and Preview

We have thoroughly examined the Writers Preference (Second Readers-Writers Problem) solution. Let's consolidate the key concepts:

Key Takeaways

•Priority Inversion: Writers Preference inverts the priority of Readers Preference—writers now take precedence over waiting readers.
•The read_try Gate: A semaphore held by waiting writers blocks new readers while allowing active readers to finish.
•Four Semaphores: mutex, write_mutex, rw_mutex, and read_try coordinate readers and writers with proper priority.
•No Writer Starvation: Writers are guaranteed to eventually proceed once they start waiting.
•Reader Starvation Risk: Continuous writers can indefinitely block readers—the symmetric starvation problem.
•Higher Overhead: More semaphore operations and partial reader serialization reduce throughput.

What's Next:

Both Readers Preference and Writers Preference suffer from starvation—just of different classes. The Fair Solution (Third Readers-Writers Problem) eliminates starvation for both readers and writers by using FIFO ordering. The next page develops fair solutions that guarantee bounded waiting for all threads, exploring the tradeoffs this fairness requires.

Page Complete

You now have complete mastery of the Writers Preference solution: its motivation, implementation, correctness proofs, starvation characteristics, and comparison with Readers Preference. This prepares you for understanding fair solutions that eliminate starvation entirely.

Writers Preference

Guaranteeing Writer Access

What You Will Learn

Motivation for Writer Priority

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

Scenario 1: Security Updates

Scenario 2: Real-Time Data Feeds

Scenario 3: Consistency Requirements

When Writer Priority Matters
Domain	Write Operations	Consequence of Delay
Security	Policy updates, revocations	Extended vulnerability window
Finance	Price updates, trades	Stale data causes losses
Configuration	Feature flags, settings	Inconsistent behavior
Inventory	Stock updates	Overselling, stockouts
Messaging	New messages	Delayed communication

The Tradeoff

Design Challenges

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:

naive_writer_priority.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// BROKEN: Naive writer priority attempt
bool writer_waiting = false;  // Flag to indicate waiting writer
 
void reader() {
    if (writer_waiting)       // Check if writer is waiting
        wait(???);            // Problem: what do we wait on?
    
    wait(mutex);
    read_count++;
    if (read_count == 1)
        wait(rw_mutex);
    signal(mutex);
    
    read_data();
    
    // ... exit section
}
 
void writer() {
    writer_waiting = true;    // Signal to readers
    wait(rw_mutex);           // Wait for exclusive access
    writer_waiting = false;   // No longer waiting
    write_data();
    signal(rw_mutex);
}

Why This Fails:

Race condition on flag: Multiple readers might check writer_waiting simultaneously with a writer setting it
What do blocked readers wait on? We need a synchronization primitive, not just a flag
How do readers know when to proceed? After the writer finishes, blocked readers must be woken
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.

Complexity Increase

Complete Solution Implementation

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

writers_preference.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
/*
 * Second Readers-Writers Problem: Writers Preference Solution
 * 
 * Invariants:
 *   - Multiple readers can access the resource simultaneously (if no writers waiting)
 *   - Writers have exclusive access
 *   - Once a writer is waiting, no new readers start
 *   - Writers don't starve
 * 
 * Shared Variables:
 *   - read_count: Number of readers currently in critical section
 *   - write_count: Number of writers currently waiting or writing
 *   - mutex: Protects read_count
 *   - write_mutex: Protects write_count
 *   - rw_mutex: Mutual exclusion between readers and writers
 *   - read_try: Controls reader access (blocked when writer waiting)
 */
 
#include <semaphore.h>
 
// Reader tracking
int read_count = 0;           // Active readers
semaphore mutex = 1;          // Protects read_count
 
// Writer tracking
int write_count = 0;          // Waiting + active writers
semaphore write_mutex = 1;    // Protects write_count
 
// Access control
semaphore rw_mutex = 1;       // Resource access control
semaphore read_try = 1;       // Reader entry gate
 
/*
 * READER PROTOCOL (Writers Preference)
 * 
 * Entry: Must pass through read_try gate (blocked if writers waiting)
 * Exit: Last reader releases rw_mutex
 */
void reader(int id) {
    while (true) {
        // ========== ENTRY SECTION ==========
        
        /*
         * Step 1: Acquire read_try
         * This gate is held by waiting writers.
         * If a writer is waiting, readers block here.
         */
        wait(read_try);           // Gate: may block if writer waiting
        
        wait(mutex);              // Step 2: Lock read_count
        read_count++;             // Step 3: Increment reader count
        
        if (read_count == 1) {    // Step 4: First reader?
            wait(rw_mutex);       // Step 5: Block writers from resource
        }
        
        signal(mutex);            // Step 6: Unlock read_count
        signal(read_try);         // Step 7: Release gate for other readers
        
        // ========== CRITICAL SECTION ==========
        
        read_data(id);            // Actually read the resource
        
        // ========== EXIT SECTION ==========
        
        wait(mutex);              // Step 8: Lock read_count
        read_count--;             // Step 9: Decrement reader count
        
        if (read_count == 0) {    // Step 10: Last reader?
            signal(rw_mutex);     // Step 11: Allow writers to proceed
        }
        
        signal(mutex);            // Step 12: Unlock read_count
        
        // ========== REMAINDER SECTION ==========
        
        process_data(id);
    }
}
 
/*
 * WRITER PROTOCOL (Writers Preference)
 * 
 * Entry: First waiting writer acquires read_try to block new readers
 * Exit: Last writer releases read_try
 */
void writer(int id) {
    while (true) {
        // ========== ENTRY SECTION ==========
        
        wait(write_mutex);        // Step 1: Lock write_count
        write_count++;            // Step 2: Register as waiting writer
        
        if (write_count == 1) {   // Step 3: First writer?
            wait(read_try);       // Step 4: Block new readers
        }
        
        signal(write_mutex);      // Step 5: Unlock write_count
        
        wait(rw_mutex);           // Step 6: Wait for exclusive access
        
        // ========== CRITICAL SECTION ==========
        
        write_data(id);           // Exclusively modify resource
        
        // ========== EXIT SECTION ==========
        
        signal(rw_mutex);         // Step 7: Release exclusive access
        
        wait(write_mutex);        // Step 8: Lock write_count
        write_count--;            // Step 9: Deregister writer
        
        if (write_count == 0) {   // Step 10: Last writer?
            signal(read_try);     // Step 11: Allow readers again
        }
        
        signal(write_mutex);      // Step 12: Unlock write_count
        
        // ========== REMAINDER SECTION ==========
        
        prepare_next_write(id);
    }
}

Understanding the Synchronization Primitives:

Semaphore	Purpose	Initial Value
`mutex`	Protects `read_count`	1
`write_mutex`	Protects `write_count`	1
`rw_mutex`	Mutual exclusion for resource	1
`read_try`	Gate controlling reader entry	1

The Key Insight: read_try as a Gate

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

Execution Trace Analysis

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

Scenario 1: Writer Arrives While Reader Active

trace_writer_priority.txt
Initial: read_count=0, write_count=0, all semaphores=1
 
Time 0: Reader R1 enters
  R1: wait(read_try) ✓     [read_try=0]
  R1: wait(mutex) ✓        [mutex=0]
  R1: read_count++ → 1
  R1: read_count==1: wait(rw_mutex) ✓  [rw_mutex=0]
  R1: signal(mutex)        [mutex=1]
  R1: signal(read_try)     [read_try=1]
  R1: ** READING **
 
Time 1: Writer W1 arrives (while R1 reading)
  W1: wait(write_mutex) ✓  [write_mutex=0]
  W1: write_count++ → 1
  W1: write_count==1: wait(read_try) ✓  [read_try=0]  ← Blocks new readers!
  W1: signal(write_mutex)  [write_mutex=1]
  W1: wait(rw_mutex) BLOCKS [rw_mutex=0, held by R1]
 
Time 2: Reader R2 arrives (while R1 reading, W1 waiting)
  R2: wait(read_try) BLOCKS [read_try=0]  ← R2 cannot start!
  
Time 3: R1 finishes reading
  R1: wait(mutex) ✓
  R1: read_count-- → 0
  R1: read_count==0: signal(rw_mutex)  [rw_mutex=1]
  R1: signal(mutex)
  
Time 3 (continued): W1 unblocks
  W1: wait(rw_mutex) ✓     [rw_mutex=0]
  W1: ** WRITING **
 
Time 4: W1 finishes
  W1: signal(rw_mutex)     [rw_mutex=1]  
  W1: wait(write_mutex) ✓
  W1: write_count-- → 0
  W1: write_count==0: signal(read_try)  [read_try=1]  ← Readers unblock!
  W1: signal(write_mutex)
 
Time 4 (continued): R2 unblocks
  R2: wait(read_try) ✓     [read_try=0]
  R2: proceeds to read...

Scenario 2: Multiple Writers Queue

trace_multiple_writers.txt
Assume R1 is reading, W1 waiting on rw_mutex, readers blocked on read_try
 
Time 5: Writer W2 arrives
  W2: wait(write_mutex) ✓
  W2: write_count++ → 2
  W2: write_count==1? NO (skip wait(read_try))  ← Read_try already held
  W2: signal(write_mutex)
  W2: wait(rw_mutex) BLOCKS  ← Behind W1
 
Time 6: R1 finishes, W1 proceeds
  W1: signal(rw_mutex)     [rw_mutex=1]
  W1: wait(rw_mutex) ✓     [rw_mutex=0]  ← W1 now writing
 
Time 7: W1 finishes
  W1: signal(rw_mutex)     [rw_mutex=1]
  W1: wait(write_mutex)
  W1: write_count-- → 1
  W1: write_count==0? NO (don't signal read_try)  ← W2 still waiting!
  W1: signal(write_mutex)
  
Time 7 (continued): W2 acquires rw_mutex
  W2: wait(rw_mutex) ✓     [rw_mutex=0]
  W2: ** WRITING **
  
Time 8: W2 finishes
  W2: signal(rw_mutex)
  W2: wait(write_mutex)
  W2: write_count-- → 0
  W2: write_count==0? YES: signal(read_try)  ← NOW readers can proceed
  W2: signal(write_mutex)

Reader Starvation Visible

Proof of Correctness

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) ∎

Bounded Critical Sections Assumption

Reader Starvation Analysis

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

The Starvation Mechanism:

reader_starvation.txt
Timeline: Continuous writers, readers waiting
 
Time:    0    1    2    3    4    5    6    7    8    ...
         |----|----|----|----|----|----|----|----|----| ...
 
W1:      [====]                                           Writer 1
W2:           [====]                                      Writer 2  
W3:                [====]                                 Writer 3
W4:                     [====]                            Writer 4
...
 
write_count:  1    1    1    1    1    1    1    1    ... (never 0!)
read_try:     0    0    0    0    0    0    0    0    ... (always held)
 
R1:      [BLOCKED on read_try-----------------------------→   Starving
R2:      [BLOCKED on read_try-----------------------------→   Starving

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

Reader Starvation Risk Assessment
Workload Pattern	Starvation Risk	Mitigation Strategy
Low writer rate	Low	None needed
Bursty writes with gaps	Low	Readers proceed during gaps
Steady moderate writes	Medium	Monitor reader latency
High sustained writes	High	Consider fair solution
Write-storm events	Very High	Rate limit or queue writes

Production Impact

Performance Characteristics

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

Overhead Analysis:

Per-Operation Semaphore Overhead
Operation	Wait Operations	Signal Operations	Notes
Reader Entry	3 (read_try, mutex, possibly rw_mutex)	2 (mutex, read_try)	More overhead than RP
Reader Exit	1 (mutex)	1-2 (mutex, possibly rw_mutex)	Similar to RP
Writer Entry	2 (write_mutex, possibly read_try) + 1 (rw_mutex)	1 (write_mutex)	More overhead than RP
Writer Exit	1 (write_mutex)	2-3	More overhead than RP

Critical Observations:

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.
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.
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.

Strengths

•Writers never starve
•Bounded writer latency
•Write-sensitive data stays fresh
•Good for write-heavy workloads
•Predictable write performance

Weaknesses

•Reader starvation possible
•Higher synchronization overhead
•Reduced reader concurrency
•More complex implementation
•Lower read throughput

Comparison with Readers Preference

Understanding when to choose Writers Preference over Readers Preference requires careful analysis of requirements.

Head-to-Head Comparison:

Readers vs Writers Preference
Property	Readers Preference	Writers Preference
Semaphores Required	2 (mutex, rw_mutex)	4 (mutex, write_mutex, rw_mutex, read_try)
Reader Entry Overhead	Low (2-3 ops)	Higher (3-5 ops)
Writer Entry Overhead	1 wait	2-3 waits
Max Concurrent Readers	Unbounded	Still unbounded (but serialized entry)
Reader Starvation	No	Yes (under writer load)
Writer Starvation	Yes (under reader load)	No
Implementation Complexity	Simple	Moderate
Best Throughput For	Read-heavy	Balanced/Write-heavy

Decision Framework:

Choose Readers Preference when:

Reads outnumber writes by 10:1 or more
Write latency is not time-sensitive
Reader throughput is the primary metric
Stale data is acceptable during write contention

Choose Writers Preference when:

Data freshness is critical
Write latency directly impacts correctness or user experience
Writes carry time-sensitive updates (prices, security, config)
Writer starvation would cause system failures
Read/write ratio is more balanced

Consider Fair Solutions

Implementation Considerations

Implementing Writers Preference correctly requires attention to subtle details.

Avoiding Common Bugs:

common_bugs.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
// BUG 1: Forgetting to release read_try immediately
void reader_buggy() {
    wait(read_try);          // Acquire gate
    wait(mutex);
    read_count++;
    if (read_count == 1)
        wait(rw_mutex);
    signal(mutex);
    // BUG: Forgot signal(read_try) here!
    // Result: Only one reader can ever enter
    
    read_data();
    // ...
}
 
// BUG 2: Wrong order of operations in writer
void writer_buggy() {
    wait(rw_mutex);          // BUG: Get resource access first
    wait(write_mutex);       // Then update write_count
    write_count++;
    if (write_count == 1)
        wait(read_try);      // Too late! Already blocked readers elsewhere
    signal(write_mutex);
    
    // Result: Writers don't properly block readers
}
 
// BUG 3: Releasing read_try in reader exit
void reader_exit_buggy() {
    wait(mutex);
    read_count--;
    if (read_count == 0) {
        signal(rw_mutex);
        signal(read_try);    // BUG: Reader shouldn't touch read_try in exit
    }
    signal(mutex);
    // Result: read_try signaled when there are still waiting writers
}

Testing for Correctness:

The increased complexity of Writers Preference makes thorough testing essential:

writer_pref_tests.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
// Test: Writers actually get priority
void test_writer_priority() {
    // Start a reader that holds for a while
    pthread_create(&t1, NULL, long_reader, NULL);
    usleep(100);  // Ensure reader is active
    
    // Start a writer
    uint64_t writer_queue_time = get_time_ns();
    pthread_create(&t2, NULL, writer, NULL);
    usleep(50);  // Writer is now waiting
    
    // Start another reader
    atomic_bool reader2_started = false;
    pthread_create(&t3, NULL, reader_with_flag, &reader2_started);
    
    // Wait for first reader to finish
    pthread_join(t1, NULL);
    
    // Check: writer should complete before reader2 starts
    pthread_join(t2, NULL);
    uint64_t writer_done_time = get_time_ns();
    
    assert(!reader2_started || reader2_started_after(writer_done_time));
    printf("Writer priority verified\n");
}
 
// Test: No starvation under moderate load
void test_no_immediate_starvation() {
    atomic_bool writer_completed = false;
    
    // Start readers continuously for 100ms
    stop_readers = false;
    for (int i = 0; i < 10; i++)
        pthread_create(&readers[i], NULL, continuous_reader, NULL);
    
    usleep(10000);  // Let readers establish
    
    // Start a writer
    pthread_create(&writer_thread, NULL, timed_writer, &writer_completed);
    
    // Writer should complete within reasonable time
    // (unlike Readers Preference where it might never complete)
    usleep(500000);  // 500ms
    assert(writer_completed && "Writer should have completed!");
    
    stop_readers = true;
}

Deadlock Potential

Summary and Preview

We have thoroughly examined the Writers Preference (Second Readers-Writers Problem) solution. Let's consolidate the key concepts:

Key Takeaways

•Priority Inversion: Writers Preference inverts the priority of Readers Preference—writers now take precedence over waiting readers.
•The read_try Gate: A semaphore held by waiting writers blocks new readers while allowing active readers to finish.
•Four Semaphores: mutex, write_mutex, rw_mutex, and read_try coordinate readers and writers with proper priority.
•No Writer Starvation: Writers are guaranteed to eventually proceed once they start waiting.
•Reader Starvation Risk: Continuous writers can indefinitely block readers—the symmetric starvation problem.
•Higher Overhead: More semaphore operations and partial reader serialization reduce throughput.

What's Next:

Page Complete