Readers Preference — Readers-Writers Problem | OneNoughtOne

0/105

Operating SystemsReaders-Writers Problem

Readers-Writers Problem

LevelIntermediate

Duration75 mins

TopicReaders-Writers Problem

2 / 5

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 \geq 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 \geq 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 \to release \to (potentially) rw_mutex \to 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.

Operating SystemsReaders-Writers Problem

Readers-Writers Problem

LevelIntermediate

Duration75 mins

TopicReaders-Writers Problem

2 / 5

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 \geq 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 \geq 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 \to release \to (potentially) rw_mutex \to 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.

Readers Preference

Maximizing Reader Concurrency

Solution Strategy Overview

Complete Solution Implementation

Step-by-Step Execution Analysis

Proof of Safety Properties

Writer Starvation Analysis

Performance Characteristics

Implementation Variations

There’s more to understand.

Readers Preference

Maximizing Reader Concurrency

Solution Strategy Overview

Complete Solution Implementation

Step-by-Step Execution Analysis

Proof of Safety Properties

Writer Starvation Analysis

Performance Characteristics

Implementation Variations

There’s more to understand.