Readers Writers Problem - Learning Module

Loading content...

0/240

Readers Preference

Maximizing Reader Concurrency

The Readers Preference solution, also known as the First Readers-Writers Problem, embodies a fundamental design choice: maximize read throughput by never making readers wait for other readers. This approach treats writers as second-class citizens—they must wait for all active readers to finish, and continuous reader arrivals can indefinitely delay writers.

This sounds unfair, and it is. But for many real-world systems, it's exactly the right tradeoff. Read-heavy workloads dominate computing: web servers handling thousands of GET requests per second, databases processing analytics queries, caches serving repeated lookups. In these scenarios, reader concurrency directly translates to system throughput.

What You Will Learn

By the end of this page, you will understand: the complete Readers Preference solution with semaphores; why the solution requires two synchronization primitives; how the first reader/last reader pattern works; a rigorous proof of correctness; analysis of the writer starvation problem; and guidance on when this solution is appropriate.

Solution Strategy Overview

The Readers Preference solution is built on a key insight: only the first reader and last reader need to interact with the writer-exclusion mechanism. Readers in between can simply proceed without additional synchronization overhead.

Core Strategy:

Track the number of active readers with a counter (read_count)
When the first reader arrives (count goes from 0 to 1), block writers
Subsequent readers simply increment the count and proceed
When readers finish, they decrement the count
When the last reader exits (count goes from 1 to 0), unblock writers
Writers wait until no readers are present, then acquire exclusive access

This strategy requires two synchronization mechanisms:

A semaphore for writer exclusion (rw_mutex): Controls access to the shared resource
A semaphore/mutex for reader counting (mutex): Protects the read_count variable

The elegance of this solution lies in its asymmetry: readers pay a small synchronization cost (protecting the counter), while writers pay the full cost of exclusive access.

The First/Last Reader Pattern

The 'first reader locks, last reader unlocks' pattern appears throughout systems programming. It's how reader-writer locks work internally, how reference counting manages shared resources, and how connection pools track active connections. Mastering this pattern pays dividends across many domains.

Complete Solution Implementation

Let's develop the complete Readers Preference solution, with detailed annotations explaining every aspect of the synchronization logic.

readers_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
/*
 * First Readers-Writers Problem: Readers Preference Solution
 * 
 * Invariants:
 *   - Multiple readers can access the resource simultaneously
 *   - A writer has exclusive access (no other readers or writers)
 *   - No reader waits unless a writer is currently writing
 * 
 * Shared Variables:
 *   - read_count: Number of readers currently in critical section
 *   - mutex: Protects read_count (binary semaphore)
 *   - rw_mutex: Ensures mutual exclusion between readers/writers
 */
 
#include <semaphore.h>
 
// Shared state
int read_count = 0;              // Number of active readers
semaphore mutex = 1;             // Protects read_count
semaphore rw_mutex = 1;          // Controls access to resource
 
/*
 * READER PROTOCOL
 * 
 * Entry: First reader acquires rw_mutex to block writers
 * Exit:  Last reader releases rw_mutex to allow writers
 */
void reader(int id) {
    while (true) {
        // ========== ENTRY SECTION ==========
        
        wait(mutex);                // Step 1: Lock read_count
        read_count++;               // Step 2: Increment reader count
        
        if (read_count == 1) {      // Step 3: First reader?
            wait(rw_mutex);         // Step 4: Block writers
        }
        
        signal(mutex);              // Step 5: Unlock read_count
        
        // ========== CRITICAL SECTION ==========
        
        read_data(id);              // Actually read the resource
        
        // ========== EXIT SECTION ==========
        
        wait(mutex);                // Step 6: Lock read_count
        read_count--;               // Step 7: Decrement reader count
        
        if (read_count == 0) {      // Step 8: Last reader?
            signal(rw_mutex);       // Step 9: Allow writers
        }
        
        signal(mutex);              // Step 10: Unlock read_count
        
        // ========== REMAINDER SECTION ==========
        
        process_data(id);           // Use the data read
    }
}
 
/*
 * WRITER PROTOCOL
 * 
 * Simple exclusive access: wait for rw_mutex, write, release
 */
void writer(int id) {
    while (true) {
        // ========== ENTRY SECTION ==========
        
        wait(rw_mutex);             // Wait until no readers or writers
        
        // ========== CRITICAL SECTION ==========
        
        write_data(id);             // Exclusively modify resource
        
        // ========== EXIT SECTION ==========
        
        signal(rw_mutex);           // Release exclusive access
        
        // ========== REMAINDER SECTION ==========
        
        prepare_next_write(id);     // Prepare next update
    }
}

Understanding the Reader Protocol:

The reader protocol is more complex than the writer protocol because readers must coordinate with each other to determine first/last status.

Entry Section (Steps 1-5):

Acquire mutex to safely access read_count
Increment read_count to register this reader
Check if this is the first reader
If first, acquire rw_mutex to block writers. This step might block if a writer is active.
Release mutex so other readers can proceed

Exit Section (Steps 6-10): 6. Acquire mutex to safely access read_count 7. Decrement read_count to deregister this reader 8. Check if this was the last reader 9. If last, release rw_mutex to allow waiting writers 10. Release mutex

Critical Observation: Between steps 5 and 6, multiple readers can be in the critical section simultaneously. The mutex only protects the read_count variable, not the actual reading.

Step-by-Step Execution Analysis

Let's trace through several execution scenarios to build intuition for how the solution behaves.

Scenario 1: Single Reader

Single Reader Execution Trace
Step	Reader R1 Action	read_count	mutex	rw_mutex
Initial	—	0	1	1
1	wait(mutex) succeeds	0	0	1
2	read_count++	1	0	1
3	read_count == 1? YES	1	0	1
4	wait(rw_mutex) succeeds	1	0	0
5	signal(mutex)	1	1	0
—	READING	1	1	0
6	wait(mutex) succeeds	1	0	0
7	read_count--	0	0	0
8	read_count == 0? YES	0	0	0
9	signal(rw_mutex)	0	0	1
10	signal(mutex)	0	1	1

The single reader successfully acquires rw_mutex, reads, and releases it.

Scenario 2: Multiple Concurrent Readers

Now consider two readers arriving nearly simultaneously:

Two Concurrent Readers
Step	R1 Action	R2 Action	read_count	mutex	rw_mutex
Initial	—	—	0	1	1
1	wait(mutex) ✓	—	0	0	1
2	read_count++	—	1	0	1
3-4	wait(rw_mutex) ✓	—	1	0	0
5	signal(mutex)	—	1	1	0
6	READING	wait(mutex) ✓	1	0	0
7	READING	read_count++	2	0	0
8	READING	read_count==1? NO	2	0	0
9	READING	signal(mutex)	2	1	0
10	READING	READING	2	1	0

Key observation: R2 does NOT call wait(rw_mutex) because read_count is already 1 when R2 checks. R2 immediately proceeds to read. This is the concurrency benefit—only the first reader waits for exclusive access.

Scenario 3: Reader-Writer Interaction

What happens when a writer arrives while readers are active?

Writer Blocked by Readers
Step	R1 Action	W1 Action	read_count	mutex	rw_mutex
1-5	Enters critical section	—	1	1	0
6	READING	wait(rw_mutex) BLOCKS	1	1	0
7-9	Exits, signals rw_mutex	—	0	1	1
10	—	wait(rw_mutex) succeeds!	0	1	0
11	—	WRITING	0	1	0

The writer blocks at wait(rw_mutex) because R1 holds it. Only when R1 exits and signals rw_mutex does the writer proceed.

Critical Insight: While W1 is blocked waiting for rw_mutex, new readers can still enter! R2 arriving during step 6 would see read_count > 0, skip the wait(rw_mutex), and proceed to read. W1 continues to wait. This is how writer starvation occurs.

The Starvation Window

Between when a reader acquires rw_mutex and the last reader releases it, ANY number of additional readers can enter without waiting for the blocked writer. A continuous stream of readers keeps rw_mutex locked forever, and the writer starves.

Proof of Safety Properties

We now rigorously prove that the Readers Preference solution satisfies the safety requirements.

Theorem 1: Reader-Reader Compatibility Statement: Multiple readers can be in the critical section simultaneously.

Proof:

Readers only wait on rw_mutex when read_count == 1 (just becoming 1)
Once the first reader holds rw_mutex, subsequent readers find read_count ≥ 1
These subsequent readers skip wait(rw_mutex) and proceed directly
The mutex semaphore only serializes access to read_count, not to the resource itself
Multiple readers between their respective signal(mutex) in entry and wait(mutex) in exit are all in the critical section
∴ Multiple readers access the resource concurrently ∎

Theorem 2: Writer Exclusivity Statement: When a writer is in the critical section, no other thread is present.

Proof:

A writer is in the critical section iff it has successfully called wait(rw_mutex) and not yet called signal(rw_mutex)
This means rw_mutex == 0
For another writer to enter: must call wait(rw_mutex), which blocks on rw_mutex == 0
For a reader to enter: the first reader must call wait(rw_mutex), which blocks on rw_mutex == 0
∴ No other thread can enter while a writer is present ∎

Theorem 3: Reader-Writer Exclusivity Statement: Readers and writers are never in the critical section simultaneously.

Proof:

When readers are present: read_count ≥ 1 and rw_mutex == 0 (held by first reader)
For a writer to enter while readers are present: must call wait(rw_mutex), but rw_mutex == 0, so writer blocks
When a writer is present: rw_mutex == 0 (held by writer)
For a reader to enter while writer is present: first reader calls wait(rw_mutex), but rw_mutex == 0, so reader blocks
∴ Readers and writers never coexist in the critical section ∎

Theorem 4: No Deadlock Statement: The solution is deadlock-free.

Proof by examination of wait-for graph:

mutex is always released before entering the critical section and re-acquired only in the exit section
No thread holds mutex while waiting on rw_mutex
Wait sequence is always: mutex → release → (potentially) rw_mutex → release
No circular wait is possible because rw_mutex holders never wait for mutex holders who are waiting for rw_mutex
∴ No deadlock can occur ∎

The Role of mutex

The mutex semaphore is critical for correctness but subtle in its purpose. It does NOT provide mutual exclusion for the resource—it provides mutual exclusion for the read_count variable. Without it, two readers incrementing simultaneously could both think they're the first reader, leading to both calling wait(rw_mutex) with catastrophic results.

Writer Starvation Analysis

The Readers Preference solution has a critical liveness flaw: writers can starve indefinitely. Let's analyze this precisely.

The Starvation Mechanism:

Consider a continuous stream of readers where each new reader arrives before all previous readers have finished:

starvation_timeline.txt
Time:    0    1    2    3    4    5    6    7    8    ...
         |----|----|----|----|----|----|----|----|----| ...
 
R1:      [==========]                                     Reader 1
R2:           [==========]                                Reader 2
R3:                [==========]                           Reader 3
R4:                     [==========]                      Reader 4
...
 
read_count:  1    2    2    2    2    2    2    2    2    ...
             ↑    ↑    ↓↑   ↓↑   ↓↑   ↓↑   ↓↑   ↓↑        
            (never reaches 0!)
 
W1:      [BLOCKED on rw_mutex------------------------→   Writer STARVING

In this scenario:

R1 arrives at time 0, acquires rw_mutex, read_count = 1
R2 arrives at time 1, sees read_count = 1, skips wait(rw_mutex), read_count = 2
W1 arrives at time 2, calls wait(rw_mutex), BLOCKS (rw_mutex held by readers)
R1 exits at time 2, read_count = 1, NOT zero, so rw_mutex not signaled
R3 arrives at time 2, sees read_count = 1, proceeds immediately
Pattern continues: read_count oscillates but never reaches 0
W1 never acquires rw_mutex, starves indefinitely

Formal Starvation Condition:

A writer starves iff: after calling wait(rw_mutex), there exists an infinite execution trace where read_count never becomes 0.

This condition is satisfied when: arrival_rate(readers) > departure_rate(readers) during any period when a writer is waiting.

Starvation Risk by Workload Characteristics
Workload Pattern	Starvation Risk	Reason
Low reader rate	Low	Gaps allow writers through
Bursty readers with gaps	Low	Writers proceed during gaps
Steady moderate readers	Medium	Depends on timing
High sustained reader rate	High	read_count rarely reaches 0
Readers with long hold times	Very High	Overlapping readers maintain lock

Production Impact

Writer starvation isn't just theoretical. Database systems using reader-preference locking have experienced cases where background maintenance (writes) never completed because read queries continuously arrived. The solution: switch to a writers-preference or fair policy for those operations.

Performance Characteristics

Understanding the performance characteristics of the Readers Preference solution helps determine when it's appropriate.

Overhead Analysis:

Per-Operation Overhead
Operation	Semaphore Ops	Potential Blocking	Contention Point
Reader Entry	2-3 waits, 1-2 signals	On mutex (brief), On rw_mutex (first only)	mutex
Reader Exit	1 wait, 1-2 signals	On mutex (brief)	mutex
Writer Entry	1 wait	On rw_mutex (potentially long)	rw_mutex
Writer Exit	1 signal	None	None

Contention Analysis:

The mutex semaphore is a potential contention point because ALL readers must acquire it during entry and exit. With N concurrent readers:

Each reader holds mutex for O(1) operations (increment/decrement and test)
Total serialization time: O(N) for N readers to enter, O(N) for N readers to exit

However, the actual reading happens in parallel, so if read time >> mutex time, this overhead is negligible.

Throughput Modeling:

Let:

μ_enter = mutex overhead for entry
μ_exit = mutex overhead for exit
R = actual read time
N = number of concurrent readers

Effective throughput: N / (R + μ_enter + μ_exit)

For large R, throughput approaches N/R, the theoretical maximum for a reader-writer workload.

Writer Latency:

Writer latency is highly variable:

Best case: No readers present, latency = 1 semaphore operation
Average case: Wait for active readers to finish
Worst case: Unbounded (starvation scenario)

Strengths

•Maximum reader concurrency
•Readers never wait for other readers
•Simple implementation
•Low per-operation overhead
•Ideal for read-dominated workloads

Weaknesses

•Writer starvation under load
•Unbounded writer latency
•mutex becomes bottleneck at scale
•Not suitable for time-sensitive writes
•No fairness guarantees

Implementation Variations

The basic Readers Preference solution can be enhanced in several ways to address specific requirements.

Variation 1: Bounded Reader Count

Limit the maximum number of concurrent readers to prevent resource exhaustion:

bounded_readers.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
#define MAX_READERS 100
 
semaphore reader_slots = MAX_READERS;  // Counting semaphore
semaphore mutex = 1;
semaphore rw_mutex = 1;
int read_count = 0;
 
void reader() {
    wait(reader_slots);      // Acquire a reader slot (may block)
    
    wait(mutex);
    read_count++;
    if (read_count == 1)
        wait(rw_mutex);
    signal(mutex);
    
    read_data();
    
    wait(mutex);
    read_count--;
    if (read_count == 0)
        signal(rw_mutex);
    signal(mutex);
    
    signal(reader_slots);    // Release the reader slot
}

This variation prevents too many readers from consuming all system resources (memory, file handles, etc.) while still allowing up to MAX_READERS concurrent accesses.

Variation 2: Reader Timeout

Avoid indefinite waiting when acquiring read access:

timed_reader.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
#include <semaphore.h>
#include <time.h>
#include <errno.h>
 
int try_read_with_timeout(int timeout_ms) {
    struct timespec ts;
    clock_gettime(CLOCK_REALTIME, &ts);
    ts.tv_sec += timeout_ms / 1000;
    ts.tv_nsec += (timeout_ms % 1000) * 1000000;
    
    // Try to acquire mutex with timeout
    if (sem_timedwait(&mutex, &ts) != 0) {
        if (errno == ETIMEDOUT)
            return -1;  // Timeout acquiring mutex
        return -2;      // Other error
    }
    
    read_count++;
    if (read_count == 1) {
        // First reader: try to acquire rw_mutex with remaining timeout
        if (sem_timedwait(&rw_mutex, &ts) != 0) {
            read_count--;
            sem_post(&mutex);
            return -1;  // Timeout waiting for writer to finish
        }
    }
    
    sem_post(&mutex);
    return 0;  // Success
}

Variation 3: Statistics Tracking

Production systems often need visibility into lock contention:

instrumented_rw.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
// Instrumented reader-writer lock
typedef struct {
    semaphore mutex;
    semaphore rw_mutex;
    int read_count;
    
    // Statistics
    atomic_uint64_t total_reads;
    atomic_uint64_t total_writes;
    atomic_uint64_t reader_wait_time_ns;
    atomic_uint64_t writer_wait_time_ns;
    atomic_uint32_t current_readers;
    atomic_uint32_t waiting_writers;
} instrumented_rwlock_t;
 
void reader_entry(instrumented_rwlock_t* lock) {
    uint64_t start = get_time_ns();
    
    wait(lock->mutex);
    lock->read_count++;
    lock->current_readers++;
    
    if (lock->read_count == 1)
        wait(lock->rw_mutex);
    
    signal(lock->mutex);
    
    atomic_fetch_add(&lock->reader_wait_time_ns, get_time_ns() - start);
}

Instrumentation in Production

Adding instrumentation to reader-writer locks is essential for diagnosing production issues. Track: wait times, current reader/writer counts, starvation indicators (writers waiting while readers continuously process), and throughput metrics. This data drives informed decisions about lock policy.

When to Use Readers Preference

The Readers Preference solution is appropriate in specific scenarios. Understanding these scenarios prevents misapplication.

Ideal Use Cases:

Use Readers Preference When

•Read/Write ratio > 10:1 — Writes are rare enough that writer latency is acceptable
•Write latency is not time-sensitive — Background updates can wait without user impact
•Read latency is critical — User-facing reads must have minimal delays
•Writers are periodic batch operations — Scheduled updates during low-traffic periods
•Stale reads are acceptable briefly — Eventual consistency is sufficient

Suitability Assessment
Application Type	Suitable?	Reason
Analytics dashboard	✅ Yes	Reads dominate; occasional refresh acceptable
Configuration cache	✅ Yes	Config rarely changes; reads constant
DNS resolver cache	✅ Yes	Lookups vastly outnumber updates
Stock trading system	❌ No	Stale prices cause costly errors
Chat application	❌ No	Message writes must be timely
Real-time leaderboard	⚠️ Maybe	Depends on update frequency requirements
Session store	✅ Yes	Sessions mostly read; writes infrequent

Avoid Readers Preference When

Do not use Readers Preference for: real-time systems where write latency matters; workloads with sustained high read rates; applications where writer starvation causes correctness issues; systems requiring bounded writer latency. In these cases, consider Writers Preference or Fair solutions.

Testing and Verification

Proper testing of reader-writer implementations requires systematic approaches that expose concurrency bugs.

Unit Tests for Correctness:

rw_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
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
#include <pthread.h>
#include <assert.h>
#include <stdatomic.h>
 
// Shared state for testing
atomic_int current_readers = 0;
atomic_int current_writers = 0;
atomic_int max_concurrent_readers = 0;
atomic_bool safety_violation = false;
 
void* test_reader(void* arg) {
    for (int i = 0; i < 1000; i++) {
        reader_entry();
        
        // Check invariants
        int readers = atomic_fetch_add(&current_readers, 1) + 1;
        int writers = atomic_load(&current_writers);
        
        if (writers > 0) {
            safety_violation = true;  // Reader overlapped with writer!
        }
        
        // Track max concurrency
        int max = atomic_load(&max_concurrent_readers);
        while (readers > max) {
            atomic_compare_exchange_weak(&max_concurrent_readers, &max, readers);
        }
        
        // Simulate work
        usleep(100 + rand() % 100);
        
        atomic_fetch_sub(&current_readers, 1);
        
        reader_exit();
    }
    return NULL;
}
 
void* test_writer(void* arg) {
    for (int i = 0; i < 100; i++) {
        writer_entry();
        
        int writers = atomic_fetch_add(&current_writers, 1) + 1;
        int readers = atomic_load(&current_readers);
        
        if (readers > 0 || writers > 1) {
            safety_violation = true;  // Violated exclusivity!
        }
        
        usleep(50);
        
        atomic_fetch_sub(&current_writers, 1);
        
        writer_exit();
    }
    return NULL;
}
 
void test_safety() {
    pthread_t readers[10], writers[2];
    
    for (int i = 0; i < 10; i++)
        pthread_create(&readers[i], NULL, test_reader, NULL);
    for (int i = 0; i < 2; i++)
        pthread_create(&writers[i], NULL, test_writer, NULL);
    
    for (int i = 0; i < 10; i++)
        pthread_join(readers[i], NULL);
    for (int i = 0; i < 2; i++)
        pthread_join(writers[i], NULL);
    
    assert(!safety_violation && "Safety property violated!");
    printf("Max concurrent readers: %d
", max_concurrent_readers);
    printf("Test passed - safety properties hold
");
}

Starvation Detection:

To detect potential starvation, track writer wait times:

starvation_test.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
void test_starvation() {
    atomic_bool writer_completed = false;
    
    // Start continuous readers
    for (int i = 0; i < 20; i++) {
        pthread_create(&readers[i], NULL, continuous_reader, NULL);
    }
    
    // Start a writer after brief delay
    usleep(1000);
    uint64_t writer_start = get_time_ns();
    pthread_t writer;
    pthread_create(&writer, NULL, single_write, &writer_completed);
    
    // Check if writer completes within reasonable time
    usleep(5000000);  // 5 seconds
    
    if (!writer_completed) {
        printf("WARNING: Writer starvation detected!
");
        printf("Writer waiting for: %.2f seconds
", 
               (get_time_ns() - writer_start) / 1e9);
    }
    
    // Signal readers to stop
    stop_readers = true;
}

Stress Testing is Essential

Concurrency bugs often only manifest under specific timing conditions. Use stress testing with many threads, vary timing with random sleeps, run tests under CPU contention (other processes), and use tools like ThreadSanitizer (TSan) to detect data races.

Summary and Preview

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

Key Takeaways

•First/Last Reader Pattern: Only the first reader acquires the writer-exclusion lock; only the last reader releases it. This enables reader concurrency.
•Two Semaphores Required: mutex protects the reader count; rw_mutex provides reader-writer exclusion.
•Provably Safe: The solution guarantees reader-reader compatibility, writer exclusivity, and reader-writer exclusivity with no deadlock.
•Writer Starvation: Continuous reader arrivals can indefinitely block writers. This is a fundamental limitation, not a bug.
•Appropriate for Read-Heavy Workloads: When reads vastly outnumber writes and writer latency is acceptable, this solution maximizes throughput.
•Instrumentation Matters: Production implementations should track wait times and concurrency metrics to detect starvation.

What's Next:

The Readers Preference solution's writer starvation problem motivates the Writers Preference (Second Readers-Writers Problem) solution. The next page develops this alternative, which guarantees writers won't starve but at the cost of potentially starving readers. We'll see how to implement this priority inversion and analyze when it's the right choice.

Page Complete

You now have complete mastery of the Readers Preference solution: its implementation, correctness proofs, starvation characteristics, and appropriate use cases. This foundation prepares you for understanding alternative solutions that make different priority tradeoffs.

Readers Preference

Maximizing Reader Concurrency

What You Will Learn

Solution Strategy Overview

Core Strategy:

Track the number of active readers with a counter (read_count)
When the first reader arrives (count goes from 0 to 1), block writers
Subsequent readers simply increment the count and proceed
When readers finish, they decrement the count
When the last reader exits (count goes from 1 to 0), unblock writers
Writers wait until no readers are present, then acquire exclusive access

This strategy requires two synchronization mechanisms:

A semaphore for writer exclusion (rw_mutex): Controls access to the shared resource
A semaphore/mutex for reader counting (mutex): Protects the read_count variable

The elegance of this solution lies in its asymmetry: readers pay a small synchronization cost (protecting the counter), while writers pay the full cost of exclusive access.

The First/Last Reader Pattern

Complete Solution Implementation

Let's develop the complete Readers Preference solution, with detailed annotations explaining every aspect of the synchronization logic.

readers_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
/*
 * First Readers-Writers Problem: Readers Preference Solution
 * 
 * Invariants:
 *   - Multiple readers can access the resource simultaneously
 *   - A writer has exclusive access (no other readers or writers)
 *   - No reader waits unless a writer is currently writing
 * 
 * Shared Variables:
 *   - read_count: Number of readers currently in critical section
 *   - mutex: Protects read_count (binary semaphore)
 *   - rw_mutex: Ensures mutual exclusion between readers/writers
 */
 
#include <semaphore.h>
 
// Shared state
int read_count = 0;              // Number of active readers
semaphore mutex = 1;             // Protects read_count
semaphore rw_mutex = 1;          // Controls access to resource
 
/*
 * READER PROTOCOL
 * 
 * Entry: First reader acquires rw_mutex to block writers
 * Exit:  Last reader releases rw_mutex to allow writers
 */
void reader(int id) {
    while (true) {
        // ========== ENTRY SECTION ==========
        
        wait(mutex);                // Step 1: Lock read_count
        read_count++;               // Step 2: Increment reader count
        
        if (read_count == 1) {      // Step 3: First reader?
            wait(rw_mutex);         // Step 4: Block writers
        }
        
        signal(mutex);              // Step 5: Unlock read_count
        
        // ========== CRITICAL SECTION ==========
        
        read_data(id);              // Actually read the resource
        
        // ========== EXIT SECTION ==========
        
        wait(mutex);                // Step 6: Lock read_count
        read_count--;               // Step 7: Decrement reader count
        
        if (read_count == 0) {      // Step 8: Last reader?
            signal(rw_mutex);       // Step 9: Allow writers
        }
        
        signal(mutex);              // Step 10: Unlock read_count
        
        // ========== REMAINDER SECTION ==========
        
        process_data(id);           // Use the data read
    }
}
 
/*
 * WRITER PROTOCOL
 * 
 * Simple exclusive access: wait for rw_mutex, write, release
 */
void writer(int id) {
    while (true) {
        // ========== ENTRY SECTION ==========
        
        wait(rw_mutex);             // Wait until no readers or writers
        
        // ========== CRITICAL SECTION ==========
        
        write_data(id);             // Exclusively modify resource
        
        // ========== EXIT SECTION ==========
        
        signal(rw_mutex);           // Release exclusive access
        
        // ========== REMAINDER SECTION ==========
        
        prepare_next_write(id);     // Prepare next update
    }
}

Understanding the Reader Protocol:

The reader protocol is more complex than the writer protocol because readers must coordinate with each other to determine first/last status.

Entry Section (Steps 1-5):

Acquire mutex to safely access read_count
Increment read_count to register this reader
Check if this is the first reader
If first, acquire rw_mutex to block writers. This step might block if a writer is active.
Release mutex so other readers can proceed

Critical Observation: Between steps 5 and 6, multiple readers can be in the critical section simultaneously. The mutex only protects the read_count variable, not the actual reading.

Step-by-Step Execution Analysis

Let's trace through several execution scenarios to build intuition for how the solution behaves.

Scenario 1: Single Reader

Single Reader Execution Trace
Step	Reader R1 Action	read_count	mutex	rw_mutex
Initial	—	0	1	1
1	wait(mutex) succeeds	0	0	1
2	read_count++	1	0	1
3	read_count == 1? YES	1	0	1
4	wait(rw_mutex) succeeds	1	0	0
5	signal(mutex)	1	1	0
—	READING	1	1	0
6	wait(mutex) succeeds	1	0	0
7	read_count--	0	0	0
8	read_count == 0? YES	0	0	0
9	signal(rw_mutex)	0	0	1
10	signal(mutex)	0	1	1

The single reader successfully acquires rw_mutex, reads, and releases it.

Scenario 2: Multiple Concurrent Readers

Now consider two readers arriving nearly simultaneously:

Two Concurrent Readers
Step	R1 Action	R2 Action	read_count	mutex	rw_mutex
Initial	—	—	0	1	1
1	wait(mutex) ✓	—	0	0	1
2	read_count++	—	1	0	1
3-4	wait(rw_mutex) ✓	—	1	0	0
5	signal(mutex)	—	1	1	0
6	READING	wait(mutex) ✓	1	0	0
7	READING	read_count++	2	0	0
8	READING	read_count==1? NO	2	0	0
9	READING	signal(mutex)	2	1	0
10	READING	READING	2	1	0

Scenario 3: Reader-Writer Interaction

What happens when a writer arrives while readers are active?

Writer Blocked by Readers
Step	R1 Action	W1 Action	read_count	mutex	rw_mutex
1-5	Enters critical section	—	1	1	0
6	READING	wait(rw_mutex) BLOCKS	1	1	0
7-9	Exits, signals rw_mutex	—	0	1	1
10	—	wait(rw_mutex) succeeds!	0	1	0
11	—	WRITING	0	1	0

The writer blocks at wait(rw_mutex) because R1 holds it. Only when R1 exits and signals rw_mutex does the writer proceed.

The Starvation Window

Proof of Safety Properties

We now rigorously prove that the Readers Preference solution satisfies the safety requirements.

Theorem 1: Reader-Reader Compatibility Statement: Multiple readers can be in the critical section simultaneously.

Proof:

Readers only wait on rw_mutex when read_count == 1 (just becoming 1)
Once the first reader holds rw_mutex, subsequent readers find read_count ≥ 1
These subsequent readers skip wait(rw_mutex) and proceed directly
The mutex semaphore only serializes access to read_count, not to the resource itself
Multiple readers between their respective signal(mutex) in entry and wait(mutex) in exit are all in the critical section
∴ Multiple readers access the resource concurrently ∎

Theorem 2: Writer Exclusivity Statement: When a writer is in the critical section, no other thread is present.

Proof:

A writer is in the critical section iff it has successfully called wait(rw_mutex) and not yet called signal(rw_mutex)
This means rw_mutex == 0
For another writer to enter: must call wait(rw_mutex), which blocks on rw_mutex == 0
For a reader to enter: the first reader must call wait(rw_mutex), which blocks on rw_mutex == 0
∴ No other thread can enter while a writer is present ∎

Theorem 3: Reader-Writer Exclusivity Statement: Readers and writers are never in the critical section simultaneously.

Proof:

When readers are present: read_count ≥ 1 and rw_mutex == 0 (held by first reader)
For a writer to enter while readers are present: must call wait(rw_mutex), but rw_mutex == 0, so writer blocks
When a writer is present: rw_mutex == 0 (held by writer)
For a reader to enter while writer is present: first reader calls wait(rw_mutex), but rw_mutex == 0, so reader blocks
∴ Readers and writers never coexist in the critical section ∎

Theorem 4: No Deadlock Statement: The solution is deadlock-free.

Proof by examination of wait-for graph:

mutex is always released before entering the critical section and re-acquired only in the exit section
No thread holds mutex while waiting on rw_mutex
Wait sequence is always: mutex → release → (potentially) rw_mutex → release
No circular wait is possible because rw_mutex holders never wait for mutex holders who are waiting for rw_mutex
∴ No deadlock can occur ∎

The Role of mutex

Writer Starvation Analysis

The Readers Preference solution has a critical liveness flaw: writers can starve indefinitely. Let's analyze this precisely.

The Starvation Mechanism:

Consider a continuous stream of readers where each new reader arrives before all previous readers have finished:

starvation_timeline.txt
Time:    0    1    2    3    4    5    6    7    8    ...
         |----|----|----|----|----|----|----|----|----| ...
 
R1:      [==========]                                     Reader 1
R2:           [==========]                                Reader 2
R3:                [==========]                           Reader 3
R4:                     [==========]                      Reader 4
...
 
read_count:  1    2    2    2    2    2    2    2    2    ...
             ↑    ↑    ↓↑   ↓↑   ↓↑   ↓↑   ↓↑   ↓↑        
            (never reaches 0!)
 
W1:      [BLOCKED on rw_mutex------------------------→   Writer STARVING

In this scenario:

R1 arrives at time 0, acquires rw_mutex, read_count = 1
R2 arrives at time 1, sees read_count = 1, skips wait(rw_mutex), read_count = 2
W1 arrives at time 2, calls wait(rw_mutex), BLOCKS (rw_mutex held by readers)
R1 exits at time 2, read_count = 1, NOT zero, so rw_mutex not signaled
R3 arrives at time 2, sees read_count = 1, proceeds immediately
Pattern continues: read_count oscillates but never reaches 0
W1 never acquires rw_mutex, starves indefinitely

Formal Starvation Condition:

A writer starves iff: after calling wait(rw_mutex), there exists an infinite execution trace where read_count never becomes 0.

This condition is satisfied when: arrival_rate(readers) > departure_rate(readers) during any period when a writer is waiting.

Starvation Risk by Workload Characteristics
Workload Pattern	Starvation Risk	Reason
Low reader rate	Low	Gaps allow writers through
Bursty readers with gaps	Low	Writers proceed during gaps
Steady moderate readers	Medium	Depends on timing
High sustained reader rate	High	read_count rarely reaches 0
Readers with long hold times	Very High	Overlapping readers maintain lock

Production Impact

Performance Characteristics

Understanding the performance characteristics of the Readers Preference solution helps determine when it's appropriate.

Overhead Analysis:

Per-Operation Overhead
Operation	Semaphore Ops	Potential Blocking	Contention Point
Reader Entry	2-3 waits, 1-2 signals	On mutex (brief), On rw_mutex (first only)	mutex
Reader Exit	1 wait, 1-2 signals	On mutex (brief)	mutex
Writer Entry	1 wait	On rw_mutex (potentially long)	rw_mutex
Writer Exit	1 signal	None	None

Contention Analysis:

The mutex semaphore is a potential contention point because ALL readers must acquire it during entry and exit. With N concurrent readers:

Each reader holds mutex for O(1) operations (increment/decrement and test)
Total serialization time: O(N) for N readers to enter, O(N) for N readers to exit

However, the actual reading happens in parallel, so if read time >> mutex time, this overhead is negligible.

Throughput Modeling:

Let:

μ_enter = mutex overhead for entry
μ_exit = mutex overhead for exit
R = actual read time
N = number of concurrent readers

Effective throughput: N / (R + μ_enter + μ_exit)

For large R, throughput approaches N/R, the theoretical maximum for a reader-writer workload.

Writer Latency:

Writer latency is highly variable:

Best case: No readers present, latency = 1 semaphore operation
Average case: Wait for active readers to finish
Worst case: Unbounded (starvation scenario)

Strengths

•Maximum reader concurrency
•Readers never wait for other readers
•Simple implementation
•Low per-operation overhead
•Ideal for read-dominated workloads

Weaknesses

•Writer starvation under load
•Unbounded writer latency
•mutex becomes bottleneck at scale
•Not suitable for time-sensitive writes
•No fairness guarantees

Implementation Variations

The basic Readers Preference solution can be enhanced in several ways to address specific requirements.

Variation 1: Bounded Reader Count

Limit the maximum number of concurrent readers to prevent resource exhaustion:

bounded_readers.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
#define MAX_READERS 100
 
semaphore reader_slots = MAX_READERS;  // Counting semaphore
semaphore mutex = 1;
semaphore rw_mutex = 1;
int read_count = 0;
 
void reader() {
    wait(reader_slots);      // Acquire a reader slot (may block)
    
    wait(mutex);
    read_count++;
    if (read_count == 1)
        wait(rw_mutex);
    signal(mutex);
    
    read_data();
    
    wait(mutex);
    read_count--;
    if (read_count == 0)
        signal(rw_mutex);
    signal(mutex);
    
    signal(reader_slots);    // Release the reader slot
}

This variation prevents too many readers from consuming all system resources (memory, file handles, etc.) while still allowing up to MAX_READERS concurrent accesses.

Variation 2: Reader Timeout

Avoid indefinite waiting when acquiring read access:

timed_reader.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
#include <semaphore.h>
#include <time.h>
#include <errno.h>
 
int try_read_with_timeout(int timeout_ms) {
    struct timespec ts;
    clock_gettime(CLOCK_REALTIME, &ts);
    ts.tv_sec += timeout_ms / 1000;
    ts.tv_nsec += (timeout_ms % 1000) * 1000000;
    
    // Try to acquire mutex with timeout
    if (sem_timedwait(&mutex, &ts) != 0) {
        if (errno == ETIMEDOUT)
            return -1;  // Timeout acquiring mutex
        return -2;      // Other error
    }
    
    read_count++;
    if (read_count == 1) {
        // First reader: try to acquire rw_mutex with remaining timeout
        if (sem_timedwait(&rw_mutex, &ts) != 0) {
            read_count--;
            sem_post(&mutex);
            return -1;  // Timeout waiting for writer to finish
        }
    }
    
    sem_post(&mutex);
    return 0;  // Success
}

Variation 3: Statistics Tracking

Production systems often need visibility into lock contention:

instrumented_rw.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
// Instrumented reader-writer lock
typedef struct {
    semaphore mutex;
    semaphore rw_mutex;
    int read_count;
    
    // Statistics
    atomic_uint64_t total_reads;
    atomic_uint64_t total_writes;
    atomic_uint64_t reader_wait_time_ns;
    atomic_uint64_t writer_wait_time_ns;
    atomic_uint32_t current_readers;
    atomic_uint32_t waiting_writers;
} instrumented_rwlock_t;
 
void reader_entry(instrumented_rwlock_t* lock) {
    uint64_t start = get_time_ns();
    
    wait(lock->mutex);
    lock->read_count++;
    lock->current_readers++;
    
    if (lock->read_count == 1)
        wait(lock->rw_mutex);
    
    signal(lock->mutex);
    
    atomic_fetch_add(&lock->reader_wait_time_ns, get_time_ns() - start);
}

Instrumentation in Production

When to Use Readers Preference

The Readers Preference solution is appropriate in specific scenarios. Understanding these scenarios prevents misapplication.

Ideal Use Cases:

Use Readers Preference When

•Read/Write ratio > 10:1 — Writes are rare enough that writer latency is acceptable
•Write latency is not time-sensitive — Background updates can wait without user impact
•Read latency is critical — User-facing reads must have minimal delays
•Writers are periodic batch operations — Scheduled updates during low-traffic periods
•Stale reads are acceptable briefly — Eventual consistency is sufficient

Suitability Assessment
Application Type	Suitable?	Reason
Analytics dashboard	✅ Yes	Reads dominate; occasional refresh acceptable
Configuration cache	✅ Yes	Config rarely changes; reads constant
DNS resolver cache	✅ Yes	Lookups vastly outnumber updates
Stock trading system	❌ No	Stale prices cause costly errors
Chat application	❌ No	Message writes must be timely
Real-time leaderboard	⚠️ Maybe	Depends on update frequency requirements
Session store	✅ Yes	Sessions mostly read; writes infrequent

Avoid Readers Preference When

Testing and Verification

Proper testing of reader-writer implementations requires systematic approaches that expose concurrency bugs.

Unit Tests for Correctness:

rw_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
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
#include <pthread.h>
#include <assert.h>
#include <stdatomic.h>
 
// Shared state for testing
atomic_int current_readers = 0;
atomic_int current_writers = 0;
atomic_int max_concurrent_readers = 0;
atomic_bool safety_violation = false;
 
void* test_reader(void* arg) {
    for (int i = 0; i < 1000; i++) {
        reader_entry();
        
        // Check invariants
        int readers = atomic_fetch_add(&current_readers, 1) + 1;
        int writers = atomic_load(&current_writers);
        
        if (writers > 0) {
            safety_violation = true;  // Reader overlapped with writer!
        }
        
        // Track max concurrency
        int max = atomic_load(&max_concurrent_readers);
        while (readers > max) {
            atomic_compare_exchange_weak(&max_concurrent_readers, &max, readers);
        }
        
        // Simulate work
        usleep(100 + rand() % 100);
        
        atomic_fetch_sub(&current_readers, 1);
        
        reader_exit();
    }
    return NULL;
}
 
void* test_writer(void* arg) {
    for (int i = 0; i < 100; i++) {
        writer_entry();
        
        int writers = atomic_fetch_add(&current_writers, 1) + 1;
        int readers = atomic_load(&current_readers);
        
        if (readers > 0 || writers > 1) {
            safety_violation = true;  // Violated exclusivity!
        }
        
        usleep(50);
        
        atomic_fetch_sub(&current_writers, 1);
        
        writer_exit();
    }
    return NULL;
}
 
void test_safety() {
    pthread_t readers[10], writers[2];
    
    for (int i = 0; i < 10; i++)
        pthread_create(&readers[i], NULL, test_reader, NULL);
    for (int i = 0; i < 2; i++)
        pthread_create(&writers[i], NULL, test_writer, NULL);
    
    for (int i = 0; i < 10; i++)
        pthread_join(readers[i], NULL);
    for (int i = 0; i < 2; i++)
        pthread_join(writers[i], NULL);
    
    assert(!safety_violation && "Safety property violated!");
    printf("Max concurrent readers: %d
", max_concurrent_readers);
    printf("Test passed - safety properties hold
");
}

Starvation Detection:

To detect potential starvation, track writer wait times:

starvation_test.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
void test_starvation() {
    atomic_bool writer_completed = false;
    
    // Start continuous readers
    for (int i = 0; i < 20; i++) {
        pthread_create(&readers[i], NULL, continuous_reader, NULL);
    }
    
    // Start a writer after brief delay
    usleep(1000);
    uint64_t writer_start = get_time_ns();
    pthread_t writer;
    pthread_create(&writer, NULL, single_write, &writer_completed);
    
    // Check if writer completes within reasonable time
    usleep(5000000);  // 5 seconds
    
    if (!writer_completed) {
        printf("WARNING: Writer starvation detected!
");
        printf("Writer waiting for: %.2f seconds
", 
               (get_time_ns() - writer_start) / 1e9);
    }
    
    // Signal readers to stop
    stop_readers = true;
}

Stress Testing is Essential

Summary and Preview

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

Key Takeaways

•First/Last Reader Pattern: Only the first reader acquires the writer-exclusion lock; only the last reader releases it. This enables reader concurrency.
•Two Semaphores Required: mutex protects the reader count; rw_mutex provides reader-writer exclusion.
•Provably Safe: The solution guarantees reader-reader compatibility, writer exclusivity, and reader-writer exclusivity with no deadlock.
•Writer Starvation: Continuous reader arrivals can indefinitely block writers. This is a fundamental limitation, not a bug.
•Appropriate for Read-Heavy Workloads: When reads vastly outnumber writes and writer latency is acceptable, this solution maximizes throughput.
•Instrumentation Matters: Production implementations should track wait times and concurrency metrics to detect starvation.

What's Next:

Page Complete