Monitor Based Solutions - Learning Module

Loading content...

0/240

Readers-Writers with Monitors

Asymmetric Concurrency: Readers vs. Writers

The readers-writers problem represents one of the most fascinating and practically relevant synchronization challenges in concurrent programming. Unlike the bounded buffer where all threads perform symmetric operations (insert or remove), the readers-writers problem features fundamentally asymmetric access patterns: readers can safely share access with other readers, but writers require exclusive access.

This asymmetry appears throughout computing systems—databases allow concurrent reads but serialize writes; caches permit parallel lookups but exclusive updates; configuration files support multiple readers but single writers. Understanding how to implement efficient, correct, and fair readers-writers solutions with monitors is essential for building high-performance concurrent systems.

Learning Objectives

By the end of this page, you will:

• Understand the readers-writers problem and its key constraints • Implement reader-preference solutions using monitors • Implement writer-preference solutions using monitors • Design fair (no-starvation) solutions using monitors • Analyze the correctness and fairness properties of each variant • Apply these patterns to real-world concurrency scenarios

Problem Definition and Constraints

The readers-writers problem involves a shared resource (such as a file, database, or data structure) accessed by two types of threads:

1. Readers: Threads that only read the shared resource, never modifying it 2. Writers: Threads that modify the shared resource

Fundamental Constraints:

Reader-Reader Compatibility: Multiple readers can access the resource simultaneously without conflict (reads are non-destructive)
Writer Exclusivity: A writer must have exclusive access—no other readers or writers may access the resource during a write
Safety: No data corruption or undefined behavior may occur

The Core Challenge:

The challenge lies in maximizing concurrency (allowing multiple simultaneous readers) while maintaining safety (exclusive writer access). Simple mutual exclusion would work but is inefficient—it would prevent concurrent reads.

Access Compatibility Matrix
Current Holder	Reader Wants Access	Writer Wants Access
None	✅ Granted	✅ Granted
One Reader	✅ Granted (shared)	❌ Must wait
Multiple Readers	✅ Granted (shared)	❌ Must wait
One Writer	❌ Must wait	❌ Must wait

Solution Variants:

There are three classical variants of the readers-writers problem, each with different fairness properties:

First Readers-Writers Problem (Reader Preference): Readers are given priority; no reader waits unless a writer already holds the resource. This can lead to writer starvation.
Second Readers-Writers Problem (Writer Preference): Writers are given priority; once a writer is waiting, no new readers are admitted. This can lead to reader starvation.
Third Readers-Writers Problem (Fair/No Starvation): Neither readers nor writers may starve; requests are served in a fair order (typically FIFO by arrival time).

We will implement all three variants using monitors, analyzing the tradeoffs of each.

Why Three Variants?

Each variant optimizes for different scenarios:

• Reader preference: Best when reads vastly outnumber writes and occasional write delay is acceptable • Writer preference: Best when writes are urgent (e.g., critical updates) and some read delay is acceptable • Fair solution: Best when predictable response times for all threads are required

Monitor State Design

Before implementing any specific variant, let's design the monitor state that can support all three solutions. The key insight is that we need to track:

Current state of resource access: Who holds the resource?
Waiting threads: Who is waiting, and in what category?
Priority/ordering information: For fair solutions, arrival order

Essential State Variables:

int readers_active;      // Number of readers currently reading
bool writer_active;      // Whether a writer is currently writing
int readers_waiting;     // Number of readers waiting to read
int writers_waiting;     // Number of writers waiting to write

Condition Variables:

The choice of condition variables depends on the variant:

Variant	Condition Variables	Purpose
Reader Preference	`can_read`, `can_write`	Separate conditions for readers and writers
Writer Preference	`can_read`, `can_write`	Same, but with different signaling policy
Fair	Single `turn` or arrival-ordered queue	All waiters in a single ordered queue

Invariants:

All solutions must maintain these invariants:

writer_active → readers_active == 0 (if writing, no readers)
readers_active > 0 → !writer_active (if reading, no writer)
writer_active is at most 1 (boolean, so implicit)

rw_monitor_design.pseudo
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
monitor ReadersWriters {
    private:
        // Active access tracking
        int readers_active = 0;      // Count of active readers
        bool writer_active = false;   // Is a writer active?
        
        // Waiting tracking (for priority decisions)
        int readers_waiting = 0;      // Readers waiting to enter
        int writers_waiting = 0;      // Writers waiting to enter
        
        // Condition variables
        condition can_read;           // Signaled when readers may proceed
        condition can_write;          // Signaled when a writer may proceed
        
        // Invariants:
        // INV1: writer_active → readers_active == 0
        // INV2: readers_active > 0 → !writer_active
        // INV3: At most one writer active (implicit from boolean)
    
    public:
        procedure start_read() { ... }   // Reader entry
        procedure end_read() { ... }     // Reader exit
        procedure start_write() { ... }  // Writer entry
        procedure end_write() { ... }    // Writer exit
}

The Four Operations Model

Readers-writers solutions always expose four operations: start_read, end_read, start_write, end_write. This explicit entry/exit model allows tracking of active readers and enables proper signaling. This is more flexible than a single 'execute with read lock' approach.

Reader Preference Implementation

In the reader preference (first readers-writers problem) solution, readers are given priority. A reader only waits if a writer is currently active. New readers can join even if writers are waiting—this maximizes read concurrency but can starve writers.

Entry and Exit Logic:

Reader Entry (start_read):

Wait while a writer is active
Increment readers_active
Proceed to read

Reader Exit (end_read):

Decrement readers_active
If last reader (readers_active == 0), signal can_write

Writer Entry (start_write):

Wait while any readers are active OR a writer is active
Set writer_active = true
Proceed to write

Writer Exit (end_write):

Set writer_active = false
Signal waiting readers AND writers (readers have priority, so signal readers first)

readers_writers_reader_pref.c
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
#include <pthread.h>
#include <stdbool.h>
 
typedef struct {
    int readers_active;
    bool writer_active;
    
    pthread_mutex_t mutex;
    pthread_cond_t can_read;
    pthread_cond_t can_write;
} RWLock_ReaderPref;
 
void rwlock_init(RWLock_ReaderPref *rw) {
    rw->readers_active = 0;
    rw->writer_active = false;
    pthread_mutex_init(&rw->mutex, NULL);
    pthread_cond_init(&rw->can_read, NULL);
    pthread_cond_init(&rw->can_write, NULL);
}
 
// ============ READER OPERATIONS ============
 
void start_read(RWLock_ReaderPref *rw) {
    pthread_mutex_lock(&rw->mutex);
    
    // Reader preference: only wait if writer is ACTIVE
    // (NOT if writers are waiting!)
    while (rw->writer_active) {
        pthread_cond_wait(&rw->can_read, &rw->mutex);
    }
    
    // Enter reading state
    rw->readers_active++;
    
    // Allow other waiting readers to also enter
    // (They're all compatible with us)
    pthread_cond_broadcast(&rw->can_read);
    
    pthread_mutex_unlock(&rw->mutex);
}
 
void end_read(RWLock_ReaderPref *rw) {
    pthread_mutex_lock(&rw->mutex);
    
    rw->readers_active--;
    
    // If we're the last reader, a writer might be able to proceed
    if (rw->readers_active == 0) {
        pthread_cond_signal(&rw->can_write);
    }
    
    pthread_mutex_unlock(&rw->mutex);
}
 
// ============ WRITER OPERATIONS ============
 
void start_write(RWLock_ReaderPref *rw) {
    pthread_mutex_lock(&rw->mutex);
    
    // Must wait for NO active readers AND no active writer
    while (rw->readers_active > 0 || rw->writer_active) {
        pthread_cond_wait(&rw->can_write, &rw->mutex);
    }
    
    // Enter writing state
    rw->writer_active = true;
    
    pthread_mutex_unlock(&rw->mutex);
}
 
void end_write(RWLock_ReaderPref *rw) {
    pthread_mutex_lock(&rw->mutex);
    
    rw->writer_active = false;
    
    // Reader preference: wake readers first
    // If readers are waiting, they have priority
    pthread_cond_broadcast(&rw->can_read);
    
    // Also signal a writer (in case no readers are waiting)
    pthread_cond_signal(&rw->can_write);
    
    pthread_mutex_unlock(&rw->mutex);
}
 
void rwlock_destroy(RWLock_ReaderPref *rw) {
    pthread_cond_destroy(&rw->can_write);
    pthread_cond_destroy(&rw->can_read);
    pthread_mutex_destroy(&rw->mutex);
}

Writer Starvation Risk

With reader preference, a steady stream of readers can indefinitely starve writers. Each new reader that arrives while readers are active can immediately enter, even if writers have been waiting since before those readers arrived. This is acceptable only when writes are infrequent or non-time-critical.

Why Broadcast in start_read()?

When a reader is admitted, all other waiting readers can also be admitted (readers are compatible). Using broadcast wakes all waiting readers simultaneously, allowing maximum read parallelism.

Why Broadcast in end_write()?

When a writer finishes, multiple readers might be waiting. Broadcasting to can_read wakes all of them. We also signal can_write in case no readers are waiting—if all threads are writers, one can proceed.

Writer Preference Implementation

In the writer preference (second readers-writers problem) solution, writers are given priority. Once a writer is waiting, no new readers are admitted—they must wait until all writers have completed. This ensures writers get timely access but can starve readers.

Key Difference from Reader Preference:

Readers now check writers_waiting > 0 in addition to writer_active. If writers are waiting, new readers defer to them.

Entry Logic Changes:

Reader Entry (start_read):

Wait while a writer is active OR writers are waiting
Increment readers_active

Writer Entry (start_write):

Increment writers_waiting
Wait while readers are active OR a writer is active
Decrement writers_waiting
Set writer_active = true

readers_writers_writer_pref.c
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
#include <pthread.h>
#include <stdbool.h>
 
typedef struct {
    int readers_active;
    int writers_waiting;    // Track waiting writers
    bool writer_active;
    
    pthread_mutex_t mutex;
    pthread_cond_t can_read;
    pthread_cond_t can_write;
} RWLock_WriterPref;
 
void rwlock_init(RWLock_WriterPref *rw) {
    rw->readers_active = 0;
    rw->writers_waiting = 0;
    rw->writer_active = false;
    pthread_mutex_init(&rw->mutex, NULL);
    pthread_cond_init(&rw->can_read, NULL);
    pthread_cond_init(&rw->can_write, NULL);
}
 
// ============ READER OPERATIONS ============
 
void start_read(RWLock_WriterPref *rw) {
    pthread_mutex_lock(&rw->mutex);
    
    // Writer preference: wait if writer active OR writers waiting
    // This gives writers priority over new readers
    while (rw->writer_active || rw->writers_waiting > 0) {
        pthread_cond_wait(&rw->can_read, &rw->mutex);
    }
    
    rw->readers_active++;
    
    // Wake other readers too (all compatible)
    pthread_cond_broadcast(&rw->can_read);
    
    pthread_mutex_unlock(&rw->mutex);
}
 
void end_read(RWLock_WriterPref *rw) {
    pthread_mutex_lock(&rw->mutex);
    
    rw->readers_active--;
    
    if (rw->readers_active == 0) {
        // Prefer writers: signal writers first
        pthread_cond_signal(&rw->can_write);
    }
    // Note: no broadcast to readers here (writers have preference)
    
    pthread_mutex_unlock(&rw->mutex);
}
 
// ============ WRITER OPERATIONS ============
 
void start_write(RWLock_WriterPref *rw) {
    pthread_mutex_lock(&rw->mutex);
    
    // Announce our intention to write BEFORE waiting
    // This prevents new readers from entering
    rw->writers_waiting++;
    
    while (rw->readers_active > 0 || rw->writer_active) {
        pthread_cond_wait(&rw->can_write, &rw->mutex);
    }
    
    // We're no longer waiting, we're active
    rw->writers_waiting--;
    rw->writer_active = true;
    
    pthread_mutex_unlock(&rw->mutex);
}
 
void end_write(RWLock_WriterPref *rw) {
    pthread_mutex_lock(&rw->mutex);
    
    rw->writer_active = false;
    
    // Writer preference: prioritize waiting writers
    if (rw->writers_waiting > 0) {
        // Another writer waiting - signal it first
        pthread_cond_signal(&rw->can_write);
    } else {
        // No waiting writers - readers can proceed
        pthread_cond_broadcast(&rw->can_read);
    }
    
    pthread_mutex_unlock(&rw->mutex);
}
 
void rwlock_destroy(RWLock_WriterPref *rw) {
    pthread_cond_destroy(&rw->can_write);
    pthread_cond_destroy(&rw->can_read);
    pthread_mutex_destroy(&rw->mutex);
}

Advantages

•Writers get timely access
•Prevents writer starvation
•Good for write-critical systems
•Ensures data freshness
•Bounded writer waiting

Disadvantages

•Readers can starve
•Reduced read parallelism
•Higher read latency under write load
•Readers blocked by waiting writers
•Not suitable for read-heavy workloads

The Key Insight: writers_waiting

The crucial difference is that readers check writers_waiting > 0. Incrementing this counter before waiting announces the writer's intention, blocking new readers from entering. This is the mechanism that gives writers priority.

Fair (No Starvation) Solution

The fair solution (third readers-writers problem) ensures that neither readers nor writers can starve. Requests are served in arrival order, with the constraint that consecutive readers can be batched together for parallelism.

Design Approaches:

Ticket-based ordering: Assign tickets on arrival, serve in ticket order
Turn variable: Alternate priority between readers and writers
Request queue: Maintain an explicit queue of pending requests

The most elegant approach uses a turn variable combined with proper signaling to ensure FIFO-like ordering while still allowing read parallelism.

The Trick for Fairness:

We use a waiting_writers_since_last_read counter. When a writer is waiting and the current batch of readers completes, we give that writer a turn before admitting more readers. Similarly, after a writer finishes, waiting readers get a turn.

readers_writers_fair.c
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
#include <pthread.h>
#include <stdbool.h>
 
// Fair readers-writers lock using FIFO ordering
// Uses arrival sequence numbers for strict ordering
 
typedef struct {
    int readers_active;
    bool writer_active;
    
    // For fair ordering
    unsigned long next_ticket;      // Next ticket to issue
    unsigned long now_serving;      // Currently served ticket
    int readers_with_ticket;        // Readers sharing current "batch" ticket
    
    pthread_mutex_t mutex;
    pthread_cond_t turn;            // Single condition - simplifies ordering
} RWLock_Fair;
 
void rwlock_init(RWLock_Fair *rw) {
    rw->readers_active = 0;
    rw->writer_active = false;
    rw->next_ticket = 0;
    rw->now_serving = 0;
    rw->readers_with_ticket = 0;
    pthread_mutex_init(&rw->mutex, NULL);
    pthread_cond_init(&rw->turn, NULL);
}
 
// ============ READER OPERATIONS ============
 
void start_read(RWLock_Fair *rw) {
    pthread_mutex_lock(&rw->mutex);
    
    // Get a ticket (atomic increment under mutex)
    unsigned long my_ticket = rw->next_ticket++;
    
    // Wait for my turn
    // We can enter if:
    // 1. It's our ticket's turn AND no writer is active
    // 2. OR readers are already active with the same group
    while (my_ticket != rw->now_serving || rw->writer_active) {
        // Special case: if readers are active and it's a "reader batch"
        // we can join them even if our ticket hasn't been served yet
        if (rw->readers_active > 0 && !rw->writer_active) {
            // Join the current reader batch
            break;
        }
        pthread_cond_wait(&rw->turn, &rw->mutex);
    }
    
    // First reader in a batch advances the now_serving
    if (rw->readers_active == 0) {
        rw->now_serving++;
    }
    rw->readers_active++;
    
    // Wake other threads - more readers might join our batch
    pthread_cond_broadcast(&rw->turn);
    
    pthread_mutex_unlock(&rw->mutex);
}
 
void end_read(RWLock_Fair *rw) {
    pthread_mutex_lock(&rw->mutex);
    
    rw->readers_active--;
    
    // If last reader, wake up next waiter (could be writer or reader)
    if (rw->readers_active == 0) {
        pthread_cond_broadcast(&rw->turn);
    }
    
    pthread_mutex_unlock(&rw->mutex);
}
 
// ============ WRITER OPERATIONS ============
 
void start_write(RWLock_Fair *rw) {
    pthread_mutex_lock(&rw->mutex);
    
    // Get a ticket
    unsigned long my_ticket = rw->next_ticket++;
    
    // Wait until:
    // 1. It's my ticket's turn
    // 2. No readers active
    // 3. No writer active
    while (my_ticket != rw->now_serving || 
           rw->readers_active > 0 || 
           rw->writer_active) {
        pthread_cond_wait(&rw->turn, &rw->mutex);
    }
    
    rw->now_serving++;  // Advance to next ticket after we're served
    rw->writer_active = true;
    
    pthread_mutex_unlock(&rw->mutex);
}
 
void end_write(RWLock_Fair *rw) {
    pthread_mutex_lock(&rw->mutex);
    
    rw->writer_active = false;
    
    // Wake all waiters - next in line will proceed
    pthread_cond_broadcast(&rw->turn);
    
    pthread_mutex_unlock(&rw->mutex);
}
 
void rwlock_destroy(RWLock_Fair *rw) {
    pthread_cond_destroy(&rw->turn);
    pthread_mutex_destroy(&rw->mutex);
}

Alternative: Simpler Fair Implementation Using Reader/Writer Counts

A simpler approach that achieves practical fairness (though not strict FIFO) is to check if writers are waiting before allowing more readers to batched:

readers_writers_fair_simple.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
// Simplified fair RW lock
// Not strict FIFO, but prevents starvation
 
typedef struct {
    int readers_active;
    int readers_waiting;
    int writers_waiting;
    bool writer_active;
    
    pthread_mutex_t mutex;
    pthread_cond_t readers_ok;
    pthread_cond_t writers_ok;
} RWLock_Fair_Simple;
 
void start_read(RWLock_Fair_Simple *rw) {
    pthread_mutex_lock(&rw->mutex);
    
    rw->readers_waiting++;
    
    // Wait if: writer active, OR 
    // (writers waiting AND readers currently active - let current batch finish)
    while (rw->writer_active || 
           (rw->writers_waiting > 0 && rw->readers_active > 0)) {
        // The second condition ensures alternation when writers are waiting
        pthread_cond_wait(&rw->readers_ok, &rw->mutex);
    }
    
    rw->readers_waiting--;
    rw->readers_active++;
    
    // Signal other waiting readers
    pthread_cond_broadcast(&rw->readers_ok);
    
    pthread_mutex_unlock(&rw->mutex);
}
 
void end_read(RWLock_Fair_Simple *rw) {
    pthread_mutex_lock(&rw->mutex);
    
    rw->readers_active--;
    
    if (rw->readers_active == 0 && rw->writers_waiting > 0) {
        // Prefer waiting writers when readers clear out
        pthread_cond_signal(&rw->writers_ok);
    }
    
    pthread_mutex_unlock(&rw->mutex);
}

Fairness Achieved

Both implementations prevent starvation. The ticket-based version provides strict FIFO ordering at the cost of complexity. The simpler version provides practical fairness (alternating batches) with cleaner code. Choose based on your strictness requirements.

Correctness Properties and Verification

Let's rigorously verify the correctness properties of our readers-writers implementations.

Safety Property 1: No Reader-Writer Conflict

Claim: A reader and writer are never simultaneously active.

Proof:

Readers wait while writer_active == true (all variants)
Writers wait while readers_active > 0 (all variants)
Both checks occur under mutex, ensuring atomic reads
Therefore, readers_active > 0 ∧ writer_active is never true

Safety Property 2: No Writer-Writer Conflict

Claim: At most one writer is ever active.

Proof:

Writers wait while writer_active == true
writer_active is set to true only upon entering the writing state
Set under mutex, so at most one thread sees writer_active == false and proceeds
Therefore, at most one writer is active at any time

Correctness Properties by Variant
Property	Reader Preference	Writer Preference	Fair
No R-W conflict	✅ Proven	✅ Proven	✅ Proven
No W-W conflict	✅ Proven	✅ Proven	✅ Proven
Multiple readers OK	✅ Yes	✅ Yes	✅ Yes
Reader starvation free	❌ No	❌ Possible	✅ Yes
Writer starvation free	❌ Possible	✅ Yes	✅ Yes
Deadlock free	✅ Yes	✅ Yes	✅ Yes

Liveness Property: Deadlock Freedom

Claim: The system never enters a deadlock state.

Proof (for all variants):

Deadlock requires a cycle of waiting threads
Readers wait only for writers; writers wait for both
If all threads are readers waiting, no writer is active, so readers can proceed
If some threads are writers waiting, they wait for readers to finish
Active readers will eventually call end_read(), signaling writers
Active writers will eventually call end_write(), signaling readers/writers
No cyclic dependencies exist; some thread can always make progress

Complexity Analysis:

Operation	Time Complexity	Notes
`start_read()`	O(1) amortized	O(wait) + O(1) state update
`end_read()`	O(1)	Constant time operations
`start_write()`	O(1) amortized	O(wait) + O(1) state update
`end_write()`	O(1)	Constant time operations

Space complexity is O(1) for all implementations (constant number of variables).

Testing Concurrent Correctness

Correctness proofs are essential but not sufficient. Concurrent code should also be tested with tools like ThreadSanitizer (TSan), Helgrind, or formal verification tools. Race conditions may only manifest under specific timing conditions.

Real-World Applications

The readers-writers pattern is ubiquitous in systems programming. Understanding when to apply each variant is crucial for building efficient systems.

Database Systems:

Databases use sophisticated variants of readers-writers locks for table and row-level locking:

Database	Lock Type	Notes
PostgreSQL	Multi-version (MVCC)	Readers don't block writers; uses snapshots
MySQL InnoDB	Readers-writers with priority options	Configurable priority
SQLite	Database-level RW lock	Simple writer preference

Operating System Kernels:

Linux: Uses rwlock_t extensively for protecting kernel data structures
Windows: SRWLOCK (Slim Reader/Writer Lock) provides lightweight RW synchronization
File Systems: Use RW locks for inode and superblock protection

Caching Systems:

Caches typically use reader preference because reads vastly outnumber writes:

Cache operations:
- get(key):   read lock — multiple concurrent lookups allowed
- put(key):   write lock — exclusive access for updates
- evict():    write lock — exclusive access for removal

concurrent_cache.cpp
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
#include <shared_mutex>
#include <unordered_map>
#include <optional>
 
template<typename K, typename V>
class ConcurrentCache {
private:
    mutable std::shared_mutex rw_mutex;  // C++17 shared_mutex
    std::unordered_map<K, V> cache;
    
public:
    // Read operation: allows multiple concurrent readers
    std::optional<V> get(const K& key) const {
        std::shared_lock<std::shared_mutex> read_lock(rw_mutex);
        
        auto it = cache.find(key);
        if (it != cache.end()) {
            return it->second;
        }
        return std::nullopt;
    }
    
    // Write operation: requires exclusive access
    void put(const K& key, const V& value) {
        std::unique_lock<std::shared_mutex> write_lock(rw_mutex);
        cache[key] = value;
    }
    
    // Write operation: exclusive access
    bool remove(const K& key) {
        std::unique_lock<std::shared_mutex> write_lock(rw_mutex);
        return cache.erase(key) > 0;
    }
    
    // Read operation: multiple readers
    size_t size() const {
        std::shared_lock<std::shared_mutex> read_lock(rw_mutex);
        return cache.size();
    }
    
    // Write operation: exclusive access
    void clear() {
        std::unique_lock<std::shared_mutex> write_lock(rw_mutex);
        cache.clear();
    }
};

Variant Selection Guidelines

•Reader Preference: High read-to-write ratio (10:1+), write latency tolerance acceptable (caches, read-mostly configs)
•Writer Preference: Writes must be timely (real-time updates, critical state changes), readers can tolerate delays
•Fair Solution: Predictable latency required (SLA-bound systems), fairness mandated (multi-tenant systems)
•MVCC/Snapshots: Highest performance, complex implementation (databases, advanced caches)

Use Standard Library Implementations

Production code should use platform-provided RW locks when possible:

• C++17: std::shared_mutex • POSIX: pthread_rwlock_t • Windows: SRWLOCK • Java: ReentrantReadWriteLock

These are highly optimized and battle-tested. Roll your own only for learning or when custom semantics are needed.

Summary: Readers-Writers with Monitors

The readers-writers problem showcases the power of monitors for handling asymmetric synchronization requirements. We've explored three solution variants, each with distinct tradeoffs.

Key Takeaways

•Asymmetric access: Readers share; writers require exclusion—different from mutual exclusion
•Three variants: Reader preference, writer preference, and fair—each optimizes for different workloads
•Starvation risks: Preference solutions can starve the non-preferred type; fair solutions prevent this
•State tracking: Monitor tracks readers_active, writer_active, and optionally waiting counts
•Condition variables: Use can_read and can_write (or unified turn for fair) to coordinate
•Signaling strategy: Broadcast to readers (batch compatible); signal to writers (one at a time)
•Real applications: Databases, caches, kernel data structures all use RW synchronization

What's Next:

Having mastered the readers-writers pattern, we'll tackle the most philosophically interesting synchronization problem: the dining philosophers. This problem introduces resource ordering, deadlock potential with multiple resources, and elegant solutions using monitors.

Page Complete

You now understand how to implement the readers-writers problem using monitors, including three distinct variants with different fairness properties. This pattern is foundational for building shared data structures, caches, and database-like systems where read/write asymmetry can be exploited for performance.

Readers-Writers with Monitors

Asymmetric Concurrency: Readers vs. Writers

Learning Objectives

By the end of this page, you will:

Problem Definition and Constraints

The readers-writers problem involves a shared resource (such as a file, database, or data structure) accessed by two types of threads:

1. Readers: Threads that only read the shared resource, never modifying it 2. Writers: Threads that modify the shared resource

Fundamental Constraints:

Reader-Reader Compatibility: Multiple readers can access the resource simultaneously without conflict (reads are non-destructive)
Writer Exclusivity: A writer must have exclusive access—no other readers or writers may access the resource during a write
Safety: No data corruption or undefined behavior may occur

The Core Challenge:

Access Compatibility Matrix
Current Holder	Reader Wants Access	Writer Wants Access
None	✅ Granted	✅ Granted
One Reader	✅ Granted (shared)	❌ Must wait
Multiple Readers	✅ Granted (shared)	❌ Must wait
One Writer	❌ Must wait	❌ Must wait

Solution Variants:

There are three classical variants of the readers-writers problem, each with different fairness properties:

First Readers-Writers Problem (Reader Preference): Readers are given priority; no reader waits unless a writer already holds the resource. This can lead to writer starvation.
Second Readers-Writers Problem (Writer Preference): Writers are given priority; once a writer is waiting, no new readers are admitted. This can lead to reader starvation.
Third Readers-Writers Problem (Fair/No Starvation): Neither readers nor writers may starve; requests are served in a fair order (typically FIFO by arrival time).

We will implement all three variants using monitors, analyzing the tradeoffs of each.

Why Three Variants?

Each variant optimizes for different scenarios:

Monitor State Design

Before implementing any specific variant, let's design the monitor state that can support all three solutions. The key insight is that we need to track:

Current state of resource access: Who holds the resource?
Waiting threads: Who is waiting, and in what category?
Priority/ordering information: For fair solutions, arrival order

Essential State Variables:

int readers_active;      // Number of readers currently reading
bool writer_active;      // Whether a writer is currently writing
int readers_waiting;     // Number of readers waiting to read
int writers_waiting;     // Number of writers waiting to write

Condition Variables:

The choice of condition variables depends on the variant:

Variant	Condition Variables	Purpose
Reader Preference	`can_read`, `can_write`	Separate conditions for readers and writers
Writer Preference	`can_read`, `can_write`	Same, but with different signaling policy
Fair	Single `turn` or arrival-ordered queue	All waiters in a single ordered queue

Invariants:

All solutions must maintain these invariants:

writer_active → readers_active == 0 (if writing, no readers)
readers_active > 0 → !writer_active (if reading, no writer)
writer_active is at most 1 (boolean, so implicit)

rw_monitor_design.pseudo
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
monitor ReadersWriters {
    private:
        // Active access tracking
        int readers_active = 0;      // Count of active readers
        bool writer_active = false;   // Is a writer active?
        
        // Waiting tracking (for priority decisions)
        int readers_waiting = 0;      // Readers waiting to enter
        int writers_waiting = 0;      // Writers waiting to enter
        
        // Condition variables
        condition can_read;           // Signaled when readers may proceed
        condition can_write;          // Signaled when a writer may proceed
        
        // Invariants:
        // INV1: writer_active → readers_active == 0
        // INV2: readers_active > 0 → !writer_active
        // INV3: At most one writer active (implicit from boolean)
    
    public:
        procedure start_read() { ... }   // Reader entry
        procedure end_read() { ... }     // Reader exit
        procedure start_write() { ... }  // Writer entry
        procedure end_write() { ... }    // Writer exit
}

The Four Operations Model

Reader Preference Implementation

Entry and Exit Logic:

Reader Entry (start_read):

Wait while a writer is active
Increment readers_active
Proceed to read

Reader Exit (end_read):

Decrement readers_active
If last reader (readers_active == 0), signal can_write

Writer Entry (start_write):

Wait while any readers are active OR a writer is active
Set writer_active = true
Proceed to write

Writer Exit (end_write):

Set writer_active = false
Signal waiting readers AND writers (readers have priority, so signal readers first)

readers_writers_reader_pref.c
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
#include <pthread.h>
#include <stdbool.h>
 
typedef struct {
    int readers_active;
    bool writer_active;
    
    pthread_mutex_t mutex;
    pthread_cond_t can_read;
    pthread_cond_t can_write;
} RWLock_ReaderPref;
 
void rwlock_init(RWLock_ReaderPref *rw) {
    rw->readers_active = 0;
    rw->writer_active = false;
    pthread_mutex_init(&rw->mutex, NULL);
    pthread_cond_init(&rw->can_read, NULL);
    pthread_cond_init(&rw->can_write, NULL);
}
 
// ============ READER OPERATIONS ============
 
void start_read(RWLock_ReaderPref *rw) {
    pthread_mutex_lock(&rw->mutex);
    
    // Reader preference: only wait if writer is ACTIVE
    // (NOT if writers are waiting!)
    while (rw->writer_active) {
        pthread_cond_wait(&rw->can_read, &rw->mutex);
    }
    
    // Enter reading state
    rw->readers_active++;
    
    // Allow other waiting readers to also enter
    // (They're all compatible with us)
    pthread_cond_broadcast(&rw->can_read);
    
    pthread_mutex_unlock(&rw->mutex);
}
 
void end_read(RWLock_ReaderPref *rw) {
    pthread_mutex_lock(&rw->mutex);
    
    rw->readers_active--;
    
    // If we're the last reader, a writer might be able to proceed
    if (rw->readers_active == 0) {
        pthread_cond_signal(&rw->can_write);
    }
    
    pthread_mutex_unlock(&rw->mutex);
}
 
// ============ WRITER OPERATIONS ============
 
void start_write(RWLock_ReaderPref *rw) {
    pthread_mutex_lock(&rw->mutex);
    
    // Must wait for NO active readers AND no active writer
    while (rw->readers_active > 0 || rw->writer_active) {
        pthread_cond_wait(&rw->can_write, &rw->mutex);
    }
    
    // Enter writing state
    rw->writer_active = true;
    
    pthread_mutex_unlock(&rw->mutex);
}
 
void end_write(RWLock_ReaderPref *rw) {
    pthread_mutex_lock(&rw->mutex);
    
    rw->writer_active = false;
    
    // Reader preference: wake readers first
    // If readers are waiting, they have priority
    pthread_cond_broadcast(&rw->can_read);
    
    // Also signal a writer (in case no readers are waiting)
    pthread_cond_signal(&rw->can_write);
    
    pthread_mutex_unlock(&rw->mutex);
}
 
void rwlock_destroy(RWLock_ReaderPref *rw) {
    pthread_cond_destroy(&rw->can_write);
    pthread_cond_destroy(&rw->can_read);
    pthread_mutex_destroy(&rw->mutex);
}

Writer Starvation Risk

Why Broadcast in start_read()?

When a reader is admitted, all other waiting readers can also be admitted (readers are compatible). Using broadcast wakes all waiting readers simultaneously, allowing maximum read parallelism.

Why Broadcast in end_write()?

Writer Preference Implementation

Key Difference from Reader Preference:

Readers now check writers_waiting > 0 in addition to writer_active. If writers are waiting, new readers defer to them.

Entry Logic Changes:

Reader Entry (start_read):

Wait while a writer is active OR writers are waiting
Increment readers_active

Writer Entry (start_write):

Increment writers_waiting
Wait while readers are active OR a writer is active
Decrement writers_waiting
Set writer_active = true

readers_writers_writer_pref.c
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
#include <pthread.h>
#include <stdbool.h>
 
typedef struct {
    int readers_active;
    int writers_waiting;    // Track waiting writers
    bool writer_active;
    
    pthread_mutex_t mutex;
    pthread_cond_t can_read;
    pthread_cond_t can_write;
} RWLock_WriterPref;
 
void rwlock_init(RWLock_WriterPref *rw) {
    rw->readers_active = 0;
    rw->writers_waiting = 0;
    rw->writer_active = false;
    pthread_mutex_init(&rw->mutex, NULL);
    pthread_cond_init(&rw->can_read, NULL);
    pthread_cond_init(&rw->can_write, NULL);
}
 
// ============ READER OPERATIONS ============
 
void start_read(RWLock_WriterPref *rw) {
    pthread_mutex_lock(&rw->mutex);
    
    // Writer preference: wait if writer active OR writers waiting
    // This gives writers priority over new readers
    while (rw->writer_active || rw->writers_waiting > 0) {
        pthread_cond_wait(&rw->can_read, &rw->mutex);
    }
    
    rw->readers_active++;
    
    // Wake other readers too (all compatible)
    pthread_cond_broadcast(&rw->can_read);
    
    pthread_mutex_unlock(&rw->mutex);
}
 
void end_read(RWLock_WriterPref *rw) {
    pthread_mutex_lock(&rw->mutex);
    
    rw->readers_active--;
    
    if (rw->readers_active == 0) {
        // Prefer writers: signal writers first
        pthread_cond_signal(&rw->can_write);
    }
    // Note: no broadcast to readers here (writers have preference)
    
    pthread_mutex_unlock(&rw->mutex);
}
 
// ============ WRITER OPERATIONS ============
 
void start_write(RWLock_WriterPref *rw) {
    pthread_mutex_lock(&rw->mutex);
    
    // Announce our intention to write BEFORE waiting
    // This prevents new readers from entering
    rw->writers_waiting++;
    
    while (rw->readers_active > 0 || rw->writer_active) {
        pthread_cond_wait(&rw->can_write, &rw->mutex);
    }
    
    // We're no longer waiting, we're active
    rw->writers_waiting--;
    rw->writer_active = true;
    
    pthread_mutex_unlock(&rw->mutex);
}
 
void end_write(RWLock_WriterPref *rw) {
    pthread_mutex_lock(&rw->mutex);
    
    rw->writer_active = false;
    
    // Writer preference: prioritize waiting writers
    if (rw->writers_waiting > 0) {
        // Another writer waiting - signal it first
        pthread_cond_signal(&rw->can_write);
    } else {
        // No waiting writers - readers can proceed
        pthread_cond_broadcast(&rw->can_read);
    }
    
    pthread_mutex_unlock(&rw->mutex);
}
 
void rwlock_destroy(RWLock_WriterPref *rw) {
    pthread_cond_destroy(&rw->can_write);
    pthread_cond_destroy(&rw->can_read);
    pthread_mutex_destroy(&rw->mutex);
}

Advantages

•Writers get timely access
•Prevents writer starvation
•Good for write-critical systems
•Ensures data freshness
•Bounded writer waiting

Disadvantages

•Readers can starve
•Reduced read parallelism
•Higher read latency under write load
•Readers blocked by waiting writers
•Not suitable for read-heavy workloads

The Key Insight: writers_waiting

Fair (No Starvation) Solution

Design Approaches:

Ticket-based ordering: Assign tickets on arrival, serve in ticket order
Turn variable: Alternate priority between readers and writers
Request queue: Maintain an explicit queue of pending requests

The most elegant approach uses a turn variable combined with proper signaling to ensure FIFO-like ordering while still allowing read parallelism.

The Trick for Fairness:

readers_writers_fair.c
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
#include <pthread.h>
#include <stdbool.h>
 
// Fair readers-writers lock using FIFO ordering
// Uses arrival sequence numbers for strict ordering
 
typedef struct {
    int readers_active;
    bool writer_active;
    
    // For fair ordering
    unsigned long next_ticket;      // Next ticket to issue
    unsigned long now_serving;      // Currently served ticket
    int readers_with_ticket;        // Readers sharing current "batch" ticket
    
    pthread_mutex_t mutex;
    pthread_cond_t turn;            // Single condition - simplifies ordering
} RWLock_Fair;
 
void rwlock_init(RWLock_Fair *rw) {
    rw->readers_active = 0;
    rw->writer_active = false;
    rw->next_ticket = 0;
    rw->now_serving = 0;
    rw->readers_with_ticket = 0;
    pthread_mutex_init(&rw->mutex, NULL);
    pthread_cond_init(&rw->turn, NULL);
}
 
// ============ READER OPERATIONS ============
 
void start_read(RWLock_Fair *rw) {
    pthread_mutex_lock(&rw->mutex);
    
    // Get a ticket (atomic increment under mutex)
    unsigned long my_ticket = rw->next_ticket++;
    
    // Wait for my turn
    // We can enter if:
    // 1. It's our ticket's turn AND no writer is active
    // 2. OR readers are already active with the same group
    while (my_ticket != rw->now_serving || rw->writer_active) {
        // Special case: if readers are active and it's a "reader batch"
        // we can join them even if our ticket hasn't been served yet
        if (rw->readers_active > 0 && !rw->writer_active) {
            // Join the current reader batch
            break;
        }
        pthread_cond_wait(&rw->turn, &rw->mutex);
    }
    
    // First reader in a batch advances the now_serving
    if (rw->readers_active == 0) {
        rw->now_serving++;
    }
    rw->readers_active++;
    
    // Wake other threads - more readers might join our batch
    pthread_cond_broadcast(&rw->turn);
    
    pthread_mutex_unlock(&rw->mutex);
}
 
void end_read(RWLock_Fair *rw) {
    pthread_mutex_lock(&rw->mutex);
    
    rw->readers_active--;
    
    // If last reader, wake up next waiter (could be writer or reader)
    if (rw->readers_active == 0) {
        pthread_cond_broadcast(&rw->turn);
    }
    
    pthread_mutex_unlock(&rw->mutex);
}
 
// ============ WRITER OPERATIONS ============
 
void start_write(RWLock_Fair *rw) {
    pthread_mutex_lock(&rw->mutex);
    
    // Get a ticket
    unsigned long my_ticket = rw->next_ticket++;
    
    // Wait until:
    // 1. It's my ticket's turn
    // 2. No readers active
    // 3. No writer active
    while (my_ticket != rw->now_serving || 
           rw->readers_active > 0 || 
           rw->writer_active) {
        pthread_cond_wait(&rw->turn, &rw->mutex);
    }
    
    rw->now_serving++;  // Advance to next ticket after we're served
    rw->writer_active = true;
    
    pthread_mutex_unlock(&rw->mutex);
}
 
void end_write(RWLock_Fair *rw) {
    pthread_mutex_lock(&rw->mutex);
    
    rw->writer_active = false;
    
    // Wake all waiters - next in line will proceed
    pthread_cond_broadcast(&rw->turn);
    
    pthread_mutex_unlock(&rw->mutex);
}
 
void rwlock_destroy(RWLock_Fair *rw) {
    pthread_cond_destroy(&rw->turn);
    pthread_mutex_destroy(&rw->mutex);
}

Alternative: Simpler Fair Implementation Using Reader/Writer Counts

A simpler approach that achieves practical fairness (though not strict FIFO) is to check if writers are waiting before allowing more readers to batched:

readers_writers_fair_simple.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
// Simplified fair RW lock
// Not strict FIFO, but prevents starvation
 
typedef struct {
    int readers_active;
    int readers_waiting;
    int writers_waiting;
    bool writer_active;
    
    pthread_mutex_t mutex;
    pthread_cond_t readers_ok;
    pthread_cond_t writers_ok;
} RWLock_Fair_Simple;
 
void start_read(RWLock_Fair_Simple *rw) {
    pthread_mutex_lock(&rw->mutex);
    
    rw->readers_waiting++;
    
    // Wait if: writer active, OR 
    // (writers waiting AND readers currently active - let current batch finish)
    while (rw->writer_active || 
           (rw->writers_waiting > 0 && rw->readers_active > 0)) {
        // The second condition ensures alternation when writers are waiting
        pthread_cond_wait(&rw->readers_ok, &rw->mutex);
    }
    
    rw->readers_waiting--;
    rw->readers_active++;
    
    // Signal other waiting readers
    pthread_cond_broadcast(&rw->readers_ok);
    
    pthread_mutex_unlock(&rw->mutex);
}
 
void end_read(RWLock_Fair_Simple *rw) {
    pthread_mutex_lock(&rw->mutex);
    
    rw->readers_active--;
    
    if (rw->readers_active == 0 && rw->writers_waiting > 0) {
        // Prefer waiting writers when readers clear out
        pthread_cond_signal(&rw->writers_ok);
    }
    
    pthread_mutex_unlock(&rw->mutex);
}

Fairness Achieved

Correctness Properties and Verification

Let's rigorously verify the correctness properties of our readers-writers implementations.

Safety Property 1: No Reader-Writer Conflict

Claim: A reader and writer are never simultaneously active.

Proof:

Readers wait while writer_active == true (all variants)
Writers wait while readers_active > 0 (all variants)
Both checks occur under mutex, ensuring atomic reads
Therefore, readers_active > 0 ∧ writer_active is never true

Safety Property 2: No Writer-Writer Conflict

Claim: At most one writer is ever active.

Proof:

Writers wait while writer_active == true
writer_active is set to true only upon entering the writing state
Set under mutex, so at most one thread sees writer_active == false and proceeds
Therefore, at most one writer is active at any time

Correctness Properties by Variant
Property	Reader Preference	Writer Preference	Fair
No R-W conflict	✅ Proven	✅ Proven	✅ Proven
No W-W conflict	✅ Proven	✅ Proven	✅ Proven
Multiple readers OK	✅ Yes	✅ Yes	✅ Yes
Reader starvation free	❌ No	❌ Possible	✅ Yes
Writer starvation free	❌ Possible	✅ Yes	✅ Yes
Deadlock free	✅ Yes	✅ Yes	✅ Yes

Liveness Property: Deadlock Freedom

Claim: The system never enters a deadlock state.

Proof (for all variants):

Deadlock requires a cycle of waiting threads
Readers wait only for writers; writers wait for both
If all threads are readers waiting, no writer is active, so readers can proceed
If some threads are writers waiting, they wait for readers to finish
Active readers will eventually call end_read(), signaling writers
Active writers will eventually call end_write(), signaling readers/writers
No cyclic dependencies exist; some thread can always make progress

Complexity Analysis:

Operation	Time Complexity	Notes
`start_read()`	O(1) amortized	O(wait) + O(1) state update
`end_read()`	O(1)	Constant time operations
`start_write()`	O(1) amortized	O(wait) + O(1) state update
`end_write()`	O(1)	Constant time operations

Space complexity is O(1) for all implementations (constant number of variables).

Testing Concurrent Correctness

Real-World Applications

The readers-writers pattern is ubiquitous in systems programming. Understanding when to apply each variant is crucial for building efficient systems.

Database Systems:

Databases use sophisticated variants of readers-writers locks for table and row-level locking:

Database	Lock Type	Notes
PostgreSQL	Multi-version (MVCC)	Readers don't block writers; uses snapshots
MySQL InnoDB	Readers-writers with priority options	Configurable priority
SQLite	Database-level RW lock	Simple writer preference

Operating System Kernels:

Linux: Uses rwlock_t extensively for protecting kernel data structures
Windows: SRWLOCK (Slim Reader/Writer Lock) provides lightweight RW synchronization
File Systems: Use RW locks for inode and superblock protection

Caching Systems:

Caches typically use reader preference because reads vastly outnumber writes:

Cache operations:
- get(key):   read lock — multiple concurrent lookups allowed
- put(key):   write lock — exclusive access for updates
- evict():    write lock — exclusive access for removal

concurrent_cache.cpp
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
#include <shared_mutex>
#include <unordered_map>
#include <optional>
 
template<typename K, typename V>
class ConcurrentCache {
private:
    mutable std::shared_mutex rw_mutex;  // C++17 shared_mutex
    std::unordered_map<K, V> cache;
    
public:
    // Read operation: allows multiple concurrent readers
    std::optional<V> get(const K& key) const {
        std::shared_lock<std::shared_mutex> read_lock(rw_mutex);
        
        auto it = cache.find(key);
        if (it != cache.end()) {
            return it->second;
        }
        return std::nullopt;
    }
    
    // Write operation: requires exclusive access
    void put(const K& key, const V& value) {
        std::unique_lock<std::shared_mutex> write_lock(rw_mutex);
        cache[key] = value;
    }
    
    // Write operation: exclusive access
    bool remove(const K& key) {
        std::unique_lock<std::shared_mutex> write_lock(rw_mutex);
        return cache.erase(key) > 0;
    }
    
    // Read operation: multiple readers
    size_t size() const {
        std::shared_lock<std::shared_mutex> read_lock(rw_mutex);
        return cache.size();
    }
    
    // Write operation: exclusive access
    void clear() {
        std::unique_lock<std::shared_mutex> write_lock(rw_mutex);
        cache.clear();
    }
};

Variant Selection Guidelines

•Reader Preference: High read-to-write ratio (10:1+), write latency tolerance acceptable (caches, read-mostly configs)
•Writer Preference: Writes must be timely (real-time updates, critical state changes), readers can tolerate delays
•Fair Solution: Predictable latency required (SLA-bound systems), fairness mandated (multi-tenant systems)
•MVCC/Snapshots: Highest performance, complex implementation (databases, advanced caches)

Use Standard Library Implementations

Production code should use platform-provided RW locks when possible:

• C++17: std::shared_mutex • POSIX: pthread_rwlock_t • Windows: SRWLOCK • Java: ReentrantReadWriteLock

These are highly optimized and battle-tested. Roll your own only for learning or when custom semantics are needed.

Summary: Readers-Writers with Monitors

The readers-writers problem showcases the power of monitors for handling asymmetric synchronization requirements. We've explored three solution variants, each with distinct tradeoffs.

Key Takeaways

•Asymmetric access: Readers share; writers require exclusion—different from mutual exclusion
•Three variants: Reader preference, writer preference, and fair—each optimizes for different workloads
•Starvation risks: Preference solutions can starve the non-preferred type; fair solutions prevent this
•State tracking: Monitor tracks readers_active, writer_active, and optionally waiting counts
•Condition variables: Use can_read and can_write (or unified turn for fair) to coordinate
•Signaling strategy: Broadcast to readers (batch compatible); signal to writers (one at a time)
•Real applications: Databases, caches, kernel data structures all use RW synchronization

What's Next:

Page Complete