Common Concurrency Patterns - Learning Module

Loading content...

0/227

Reader-Writer Pattern

When Sharing Is Complicated: The Reader-Writer Problem

Consider a busy reference library. Many patrons can simultaneously read the same encyclopedia—reading doesn't modify the book, so concurrent reading is perfectly safe. But when a librarian needs to update a reference volume (perhaps inserting new pages), all readers must step away. The update requires exclusive access; no one should read partially-updated information.

This real-world scenario maps directly to one of the most important concurrency patterns in computer science: the reader-writer problem. Unlike producer-consumer (where all operations modify shared state), the reader-writer pattern distinguishes between two types of operations with fundamentally different access requirements.

What You Will Learn

By the end of this page, you will understand the reader-writer pattern deeply: the asymmetric access requirements that define it, multiple solution variants with different fairness guarantees, implementation using both semaphores and reader-writer locks, the starvation problems that arise, and how this pattern manifests in databases, caches, and file systems throughout computing.

Problem Definition and Requirements

The reader-writer problem arises when multiple threads access shared data with different access patterns. The key insight is that read operations are non-destructive—multiple concurrent reads produce identical results and don't interfere with each other.

Formal Definition:

The reader-writer problem involves:

Readers: Threads that only read shared data (non-modifying operations)
Writers: Threads that modify shared data (potentially destructive operations)
Shared Resource: Data structure accessed by both readers and writers

Access Requirements:

Reader-Writer Access Matrix
Current State	Reader Wants Access	Writer Wants Access
No active readers or writers	✅ Allowed	✅ Allowed
Active reader(s), no writer	✅ Allowed (concurrent)	❌ Must wait
Active writer	❌ Must wait	❌ Must wait

Key Properties:

Multiple Simultaneous Readers: Any number of readers can access the resource concurrently
Exclusive Writer Access: When a writer accesses the resource, no other thread (reader or writer) may access it
No Simultaneous Read/Write: A reader and writer can never access the resource at the same time

Why Not Just Use a Mutex?

A simple mutex would work correctly but sacrifices concurrency:

naive_mutex_solution.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
// Works correctly, but unnecessarily serializes readers
pthread_mutex_t resource_mutex = PTHREAD_MUTEX_INITIALIZER;
SharedData shared_data;
 
void read_data() {
    pthread_mutex_lock(&resource_mutex);
    // Only ONE reader at a time - wasteful!
    // If 100 threads want to read, they queue up unnecessarily
    int value = shared_data.value;
    pthread_mutex_unlock(&resource_mutex);
    return value;
}
 
void write_data(int value) {
    pthread_mutex_lock(&resource_mutex);
    shared_data.value = value;
    pthread_mutex_unlock(&resource_mutex);
}
 
// Problem: In read-heavy workloads (common case!), 
// throughput is artificially limited.
// If read takes 10ms and we have 10 concurrent readers:
//   With mutex: 100ms total (serialized)
//   With proper RW lock: ~10ms total (concurrent)

Read-Heavy Workloads Are Common

Most real-world data access is read-heavy. Consider a database: reads typically outnumber writes 10:1, 100:1, or more. A cache might see 1000 reads per write. Using a simple mutex in these scenarios throws away concurrency that the reader-writer pattern preserves, often resulting in 10x or 100x throughput improvements.

First Solution: Readers Preference

The first readers-writers problem (also called readers preference) specifies that no reader should wait unless a writer already has access. In other words, readers have priority—a waiting writer doesn't block new readers from starting.

Key Properties:

If a writer is waiting, arriving readers can still start reading
Writers only gain access when no readers are present
Risk: Writer starvation if readers continuously arrive

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
#include <pthread.h>
#include <semaphore.h>
#include <stdio.h>
 
// Shared data
int shared_data = 0;
 
// Synchronization primitives
int reader_count = 0;                    // Number of active readers
pthread_mutex_t reader_count_mutex = PTHREAD_MUTEX_INITIALIZER;
sem_t resource_access;                    // Controls access to shared resource
 
void init() {
    sem_init(&resource_access, 0, 1);
}
 
void reader() {
    // ========== ENTRY SECTION ==========
    pthread_mutex_lock(&reader_count_mutex);
    reader_count++;
    if (reader_count == 1) {
        // First reader locks out writers
        sem_wait(&resource_access);
    }
    pthread_mutex_unlock(&reader_count_mutex);
    
    // ========== CRITICAL SECTION (READING) ==========
    printf("Reader %ld: reading value %d\n", pthread_self(), shared_data);
    // Simulate read operation
    usleep(100000);  // 100ms
    
    // ========== EXIT SECTION ==========
    pthread_mutex_lock(&reader_count_mutex);
    reader_count--;
    if (reader_count == 0) {
        // Last reader releases resource for writers
        sem_post(&resource_access);
    }
    pthread_mutex_unlock(&reader_count_mutex);
}
 
void writer() {
    // Writer needs exclusive access
    sem_wait(&resource_access);
    
    // ========== CRITICAL SECTION (WRITING) ==========
    shared_data++;
    printf("Writer %ld: wrote value %d\n", pthread_self(), shared_data);
    usleep(100000);  // 100ms
    
    sem_post(&resource_access);
}

How It Works:

Reader Entry:

Acquire reader_count_mutex to safely modify reader_count
Increment reader_count
If this is the first reader (count became 1), acquire resource_access to block writers
Release reader_count_mutex and proceed to read

Reader Exit:

Acquire reader_count_mutex
Decrement reader_count
If this was the last reader (count became 0), release resource_access to allow writers
Release reader_count_mutex

Writer Entry/Exit:

Simply acquire and release resource_access
Writers are blocked while any reader is active

The Starvation Problem:

Writer Starvation

In readers preference, writers can starve indefinitely. If readers arrive continuously, reader_count never reaches zero, so resource_access is never released for writers. Imagine a web cache: if read requests arrive faster than the read duration, a cache update (write) might wait forever. This is unacceptable for systems requiring timely updates.

Analyzing the Solution:

Mutual Exclusion for Writes: ✅ Writers hold resource_access exclusively

Concurrent Reads: ✅ After first reader acquires resource_access, subsequent readers proceed without acquiring it

No Reader-Writer Overlap: ✅ Writers can't acquire resource_access while any reader holds it

Writer Progress: ❌ Not guaranteed—writers can starve under continuous read load

Second Solution: Writers Preference

The second readers-writers problem (also called writers preference) specifies that once a writer is waiting, no new readers may start—they must wait for the writer to complete. This prevents writer starvation but introduces the opposite risk.

Key Properties:

Waiting writers block new readers from starting
Active readers complete, but no new ones begin
Risk: Reader starvation if writers continuously arrive

writers_preference.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <pthread.h>
#include <semaphore.h>
 
// Shared data
int shared_data = 0;
 
// Synchronization primitives
int reader_count = 0;
int writer_count = 0;
 
pthread_mutex_t reader_count_mutex = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t writer_count_mutex = PTHREAD_MUTEX_INITIALIZER;
 
sem_t resource_access;    // Controls access to shared resource
sem_t reader_entry;       // Controls whether readers may enter
sem_t reader_try;         // Limits reader entry attempts
 
void init() {
    sem_init(&resource_access, 0, 1);
    sem_init(&reader_entry, 0, 1);
    sem_init(&reader_try, 0, 1);
}
 
void reader() {
    // ========== ENTRY SECTION ==========
    sem_wait(&reader_try);        // Might be blocked by waiting writer
    sem_wait(&reader_entry);      // Serialize reader entry
    
    pthread_mutex_lock(&reader_count_mutex);
    reader_count++;
    if (reader_count == 1) {
        sem_wait(&resource_access);  // First reader locks resource
    }
    pthread_mutex_unlock(&reader_count_mutex);
    
    sem_post(&reader_entry);
    sem_post(&reader_try);
    
    // ========== CRITICAL SECTION (READING) ==========
    printf("Reader: value = %d\n", shared_data);
    
    // ========== EXIT SECTION ==========
    pthread_mutex_lock(&reader_count_mutex);
    reader_count--;
    if (reader_count == 0) {
        sem_post(&resource_access);  // Last reader releases resource
    }
    pthread_mutex_unlock(&reader_count_mutex);
}
 
void writer() {
    // ========== ENTRY SECTION ==========
    pthread_mutex_lock(&writer_count_mutex);
    writer_count++;
    if (writer_count == 1) {
        sem_wait(&reader_try);  // Block new readers from trying
    }
    pthread_mutex_unlock(&writer_count_mutex);
    
    sem_wait(&resource_access);  // Wait for exclusive access
    
    // ========== CRITICAL SECTION (WRITING) ==========
    shared_data++;
    printf("Writer: wrote %d\n", shared_data);
    
    // ========== EXIT SECTION ==========
    sem_post(&resource_access);
    
    pthread_mutex_lock(&writer_count_mutex);
    writer_count--;
    if (writer_count == 0) {
        sem_post(&reader_try);  // Allow readers to try again
    }
    pthread_mutex_unlock(&writer_count_mutex);
}

How Writers Block New Readers:

The key addition is reader_try semaphore:

When the first writer arrives, it acquires reader_try
This blocks any new readers at sem_wait(&reader_try) in their entry section
Active readers continue and complete normally
When no readers remain, writer acquires resource_access and writes
When the last writer exits, it releases reader_try, allowing readers to proceed

The Symmetry Problem:

Writers preference solves writer starvation but creates reader starvation. Under continuous write load, readers may wait indefinitely. This is problematic for read-heavy workloads where reader latency matters.

Comparison of Reader-Writer Solutions
Aspect	Readers Preference	Writers Preference
New readers proceed when writer waiting	✅ Yes	❌ No
Writers can starve	❌ Yes	✅ No
Readers can starve	✅ No	❌ Yes
Best for	Read-heavy, stale data acceptable	Write latency critical
Example use case	DNS cache	Real-time data feeds

Choosing Between Solutions

Choose readers preference when data freshness is less critical than read throughput (caches, reference data). Choose writers preference when update latency matters more than read latency (real-time systems, financial data). For balanced requirements, use a fair solution (next section).

Fair Reader-Writer Solution

The third readers-writers problem (also called fair or starve-free solution) ensures neither readers nor writers can be indefinitely postponed. Access is granted in approximately FIFO order—whoever arrives first proceeds first (modulo concurrent reads).

Key Insight:

We use a turnstile (service queue) to serialize access requests. Writers and readers wait in the same queue, ensuring that a waiting writer eventually gets served even if readers keep arriving.

fair_rw_solution.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
#include <pthread.h>
#include <semaphore.h>
 
int shared_data = 0;
int reader_count = 0;
 
pthread_mutex_t reader_count_mutex = PTHREAD_MUTEX_INITIALIZER;
sem_t resource_access;
sem_t service_queue;  // FIFO queue for all accessors (the "turnstile")
 
void init() {
    sem_init(&resource_access, 0, 1);
    sem_init(&service_queue, 0, 1);
}
 
void reader() {
    // ========== ENTRY SECTION ==========
    sem_wait(&service_queue);  // Wait in line (FIFO)
    
    pthread_mutex_lock(&reader_count_mutex);
    reader_count++;
    if (reader_count == 1) {
        sem_wait(&resource_access);
    }
    pthread_mutex_unlock(&reader_count_mutex);
    
    sem_post(&service_queue);  // Let next in line proceed
    
    // ========== CRITICAL SECTION (READING) ==========
    printf("Reader: value = %d\n", shared_data);
    
    // ========== EXIT SECTION ==========
    pthread_mutex_lock(&reader_count_mutex);
    reader_count--;
    if (reader_count == 0) {
        sem_post(&resource_access);
    }
    pthread_mutex_unlock(&reader_count_mutex);
}
 
void writer() {
    // ========== ENTRY SECTION ==========
    sem_wait(&service_queue);  // Wait in line (FIFO)
    sem_wait(&resource_access); // Acquire exclusive access
    
    // ========== CRITICAL SECTION (WRITING) ==========
    shared_data++;
    printf("Writer: wrote %d\n", shared_data);
    
    // ========== EXIT SECTION ==========
    sem_post(&service_queue);  // Let next in line proceed
    sem_post(&resource_access);
}

How Fairness Works:

The Turnstile Concept:

Both readers and writers first wait on service_queue. This creates a FIFO ordering of access requests. The key behavior:

Reader arrives, no writer queued: Reader proceeds, releases service_queue quickly for next accessor
Writer arrives, readers active: Writer waits on service_queue, then resource_access. While waiting on resource_access, it holds service_queue, blocking new readers
New reader arrives, writer waiting: Reader blocks on service_queue behind the writer
Active readers finish: Writer gets resource_access, writes, then releases both
Queued readers proceed: Readers behind writer now proceed concurrently

Bounded Waiting:

Since service_queue enforces FIFO, no accessor waits longer than the time for all ahead of it to be served. Starvation is impossible.

Throughput vs Fairness Tradeoff

The fair solution sacrifices some throughput for bounded waiting. When a writer arrives, subsequent readers queue behind it even if they could have safely read concurrently with active readers. This is the fairness tax. For systems where predictable latency matters more than peak throughput, this tradeoff is worthwhile.

Comparison of All Three Solutions:

Reader-Writer Solution Properties
Property	Readers Pref	Writers Pref	Fair
Reader starvation possible	No	Yes	No
Writer starvation possible	Yes	No	No
Read throughput	Highest	Lower	Medium
Write latency	Unbounded	Bounded	Bounded
Read latency	Bounded	Unbounded	Bounded
Implementation complexity	Simple	Medium	Simple

POSIX Reader-Writer Locks

Modern operating systems provide built-in reader-writer lock primitives that encapsulate the synchronization complexity. POSIX provides pthread_rwlock_t, which is the standard way to implement reader-writer synchronization in production code.

POSIX rwlock API:

posix_rwlock_example.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
#include <pthread.h>
#include <stdio.h>
 
// Shared data protected by reader-writer lock
typedef struct {
    int value;
    char name[64];
    pthread_rwlock_t rwlock;
} SharedResource;
 
SharedResource shared;
 
void init_shared() {
    shared.value = 0;
    strcpy(shared.name, "initial");
    
    // Initialize reader-writer lock with default attributes
    pthread_rwlock_init(&shared.rwlock, NULL);
    
    // Or with specific attributes (e.g., writer preference)
    pthread_rwlockattr_t attr;
    pthread_rwlockattr_init(&attr);
    // PTHREAD_RWLOCK_PREFER_READER_NP or PTHREAD_RWLOCK_PREFER_WRITER_NP
    // (NP = non-portable, Linux-specific)
    pthread_rwlockattr_setkind_np(&attr, PTHREAD_RWLOCK_PREFER_WRITER_NP);
    pthread_rwlock_init(&shared.rwlock, &attr);
}
 
void reader() {
    // Acquire read lock - blocks if writer is active or waiting
    // Multiple readers can hold this simultaneously
    pthread_rwlock_rdlock(&shared.rwlock);
    
    // Read operations
    printf("Reader: value=%d, name=%s\n", shared.value, shared.name);
    
    // Release read lock
    pthread_rwlock_unlock(&shared.rwlock);
}
 
void writer(int new_value, const char* new_name) {
    // Acquire write lock - blocks if any reader or writer is active
    // Exclusive access guaranteed
    pthread_rwlock_wrlock(&shared.rwlock);
    
    // Write operations
    shared.value = new_value;
    strcpy(shared.name, new_name);
    printf("Writer: set value=%d, name=%s\n", shared.value, shared.name);
    
    // Release write lock
    pthread_rwlock_unlock(&shared.rwlock);
}
 
// Non-blocking variants
int try_read() {
    if (pthread_rwlock_tryrdlock(&shared.rwlock) == 0) {
        int val = shared.value;
        pthread_rwlock_unlock(&shared.rwlock);
        return val;
    }
    return -1;  // Lock not available
}
 
int try_write(int value) {
    if (pthread_rwlock_trywrlock(&shared.rwlock) == 0) {
        shared.value = value;
        pthread_rwlock_unlock(&shared.rwlock);
        return 0;  // Success
    }
    return -1;  // Lock not available
}
 
// Timed variants
int timed_read(int timeout_ms) {
    struct timespec ts;
    clock_gettime(CLOCK_REALTIME, &ts);
    ts.tv_nsec += timeout_ms * 1000000;
    
    if (pthread_rwlock_timedrdlock(&shared.rwlock, &ts) == 0) {
        int val = shared.value;
        pthread_rwlock_unlock(&shared.rwlock);
        return val;
    }
    return -1;  // Timeout
}

POSIX rwlock Functions
Function	Purpose	Blocking Behavior
`pthread_rwlock_init`	Initialize rwlock	N/A
`pthread_rwlock_destroy`	Destroy rwlock	N/A
`pthread_rwlock_rdlock`	Acquire read lock	Blocks if writer active/waiting
`pthread_rwlock_wrlock`	Acquire write lock	Blocks if any accessor active
`pthread_rwlock_unlock`	Release lock (read or write)	N/A
`pthread_rwlock_tryrdlock`	Non-blocking read lock	Returns immediately
`pthread_rwlock_trywrlock`	Non-blocking write lock	Returns immediately
`pthread_rwlock_timedrdlock`	Read lock with timeout	Blocks up to timeout
`pthread_rwlock_timedwrlock`	Write lock with timeout	Blocks up to timeout

rwlock Caveats

Never upgrade a read lock to write lock (deadlock). 2) Recursive read locking behavior is implementation-defined. 3) Default preference (readers vs writers) varies by implementation. 4) For short critical sections, a simple mutex may outperform rwlock due to overhead. Profile before assuming rwlock is faster.

Reader-Writer Locks Across Languages

The reader-writer pattern is so fundamental that most modern languages provide built-in support. Understanding the idioms in different languages helps you apply the pattern regardless of technology stack.

JavaReadWriteLock.java
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
import java.util.concurrent.locks.*;
 
public class SharedCache {
    private final ReadWriteLock rwLock = new ReentrantReadWriteLock();
    private final Lock readLock = rwLock.readLock();
    private final Lock writeLock = rwLock.writeLock();
    
    private Map<String, String> cache = new HashMap<>();
    
    public String get(String key) {
        readLock.lock();
        try {
            return cache.get(key);
        } finally {
            readLock.unlock();
        }
    }
    
    public void put(String key, String value) {
        writeLock.lock();
        try {
            cache.put(key, value);
        } finally {
            writeLock.unlock();
        }
    }
    
    // Lock downgrade example (write -> read)
    public String computeIfAbsent(String key, Function<String, String> compute) {
        readLock.lock();
        try {
            String value = cache.get(key);
            if (value != null) return value;
        } finally {
            readLock.unlock();
        }
        
        writeLock.lock();
        try {
            // Re-check under write lock
            String value = cache.get(key);
            if (value != null) return value;
            
            value = compute.apply(key);
            cache.put(key, value);
            return value;
        } finally {
            writeLock.unlock();
        }
    }
}

Language-Specific Considerations

Java's ReentrantReadWriteLock supports lock downgrade (write→read) but not upgrade. Go's RWMutex is simple and writer-preferring. Rust's RwLock integrates with ownership for compile-time safety. Python's GIL affects threading, but RWLock is still useful for I/O-bound operations with concurrent access.

Real-World Applications

The reader-writer pattern appears throughout computing wherever read-heavy workloads access shared data. Understanding these applications helps you recognize when to apply the pattern.

Database Systems

•Row-Level Locking: Databases use reader-writer locks at row level. SELECT queries acquire shared (read) locks; UPDATE/DELETE acquire exclusive (write) locks. Multiple transactions can read the same row concurrently.
•Table-Level Locking: Coarser granularity for DDL operations. ALTER TABLE requires exclusive access; normal queries use shared access.
•MVCC Alternative: Modern databases often use Multi-Version Concurrency Control instead, maintaining multiple versions to allow readers to see consistent snapshots without blocking writers.

Caching Systems

•In-Memory Caches: Application caches (e.g., Guava Cache, Caffeine) use reader-writer locks for thread-safe access. Reads vastly outnumber writes, making RW locks essential for performance.
•Configuration Caches: System configuration loaded once, read constantly. Reader-writer locks enable near-zero-overhead reads during normal operation.
•DNS Caches: DNS resolution results are cached and read frequently; TTL expiration triggers writes. Perfect reader-writer scenario.

File Systems

•File Locking: fcntl() and flock() support shared (read) and exclusive (write) locks. Multiple processes can read a file simultaneously.
•Directory Operations: Reading directory contents allows concurrent access; modifications (create/delete files) require exclusive access to parent directory.
•Inode Caches: File system metadata is read-frequently, updated rarely. Reader-writer semantics optimize access to cached inode information.

When NOT to Use Reader-Writer Locks

RW locks have overhead. For very short critical sections, a simple mutex may outperform. If writes are as frequent as reads, RW locks add complexity without benefit. If the resource is inherently non-shareable (e.g., a counter being incremented), use a mutex. Profile before optimizing.

Summary: The Reader-Writer Pattern

The reader-writer pattern addresses a fundamental asymmetry in data access: reads are non-destructive and can proceed concurrently, while writes require exclusive access. Let's consolidate the key insights:

Key Takeaways

•Asymmetric Access: Multiple readers can access concurrently; writers need exclusive access. This asymmetry enables significant concurrency gains in read-heavy workloads.
•Three Classic Solutions: Readers preference (writers may starve), writers preference (readers may starve), and fair solution (no starvation, bounded waiting).
•Starvation is the Core Challenge: Any solution must address whether continuous arrivals of one type can indefinitely postpone the other type.
•POSIX rwlock: Production code should use pthread_rwlock_t rather than manual implementation. Consider the preference attribute for your use case.
•Measure Before Optimizing: For short critical sections, mutex may outperform rwlock. The pattern shines for read-heavy workloads with non-trivial read operations.
•Ubiquitous Pattern: Databases, caches, file systems, configuration management—reader-writer semantics appear throughout systems programming.

What's Next:

Having explored producer-consumer and reader-writer patterns, we'll next examine the pipeline pattern—a powerful approach for structuring concurrent computation as a sequence of processing stages. Pipelines enable parallelism, modularity, and natural back-pressure in data processing systems.

Page Complete

You now deeply understand the reader-writer pattern—from the access asymmetry that defines it through three solution variants to production implementations across languages. This pattern is essential for optimizing read-heavy concurrent systems. Next, we'll explore the pipeline pattern for streaming data processing.

Reader-Writer Pattern

When Sharing Is Complicated: The Reader-Writer Problem

What You Will Learn

Problem Definition and Requirements

Formal Definition:

The reader-writer problem involves:

Readers: Threads that only read shared data (non-modifying operations)
Writers: Threads that modify shared data (potentially destructive operations)
Shared Resource: Data structure accessed by both readers and writers

Access Requirements:

Reader-Writer Access Matrix
Current State	Reader Wants Access	Writer Wants Access
No active readers or writers	✅ Allowed	✅ Allowed
Active reader(s), no writer	✅ Allowed (concurrent)	❌ Must wait
Active writer	❌ Must wait	❌ Must wait

Key Properties:

Multiple Simultaneous Readers: Any number of readers can access the resource concurrently
Exclusive Writer Access: When a writer accesses the resource, no other thread (reader or writer) may access it
No Simultaneous Read/Write: A reader and writer can never access the resource at the same time

Why Not Just Use a Mutex?

A simple mutex would work correctly but sacrifices concurrency:

naive_mutex_solution.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
// Works correctly, but unnecessarily serializes readers
pthread_mutex_t resource_mutex = PTHREAD_MUTEX_INITIALIZER;
SharedData shared_data;
 
void read_data() {
    pthread_mutex_lock(&resource_mutex);
    // Only ONE reader at a time - wasteful!
    // If 100 threads want to read, they queue up unnecessarily
    int value = shared_data.value;
    pthread_mutex_unlock(&resource_mutex);
    return value;
}
 
void write_data(int value) {
    pthread_mutex_lock(&resource_mutex);
    shared_data.value = value;
    pthread_mutex_unlock(&resource_mutex);
}
 
// Problem: In read-heavy workloads (common case!), 
// throughput is artificially limited.
// If read takes 10ms and we have 10 concurrent readers:
//   With mutex: 100ms total (serialized)
//   With proper RW lock: ~10ms total (concurrent)

Read-Heavy Workloads Are Common

First Solution: Readers Preference

Key Properties:

If a writer is waiting, arriving readers can still start reading
Writers only gain access when no readers are present
Risk: Writer starvation if readers continuously arrive

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
#include <pthread.h>
#include <semaphore.h>
#include <stdio.h>
 
// Shared data
int shared_data = 0;
 
// Synchronization primitives
int reader_count = 0;                    // Number of active readers
pthread_mutex_t reader_count_mutex = PTHREAD_MUTEX_INITIALIZER;
sem_t resource_access;                    // Controls access to shared resource
 
void init() {
    sem_init(&resource_access, 0, 1);
}
 
void reader() {
    // ========== ENTRY SECTION ==========
    pthread_mutex_lock(&reader_count_mutex);
    reader_count++;
    if (reader_count == 1) {
        // First reader locks out writers
        sem_wait(&resource_access);
    }
    pthread_mutex_unlock(&reader_count_mutex);
    
    // ========== CRITICAL SECTION (READING) ==========
    printf("Reader %ld: reading value %d\n", pthread_self(), shared_data);
    // Simulate read operation
    usleep(100000);  // 100ms
    
    // ========== EXIT SECTION ==========
    pthread_mutex_lock(&reader_count_mutex);
    reader_count--;
    if (reader_count == 0) {
        // Last reader releases resource for writers
        sem_post(&resource_access);
    }
    pthread_mutex_unlock(&reader_count_mutex);
}
 
void writer() {
    // Writer needs exclusive access
    sem_wait(&resource_access);
    
    // ========== CRITICAL SECTION (WRITING) ==========
    shared_data++;
    printf("Writer %ld: wrote value %d\n", pthread_self(), shared_data);
    usleep(100000);  // 100ms
    
    sem_post(&resource_access);
}

How It Works:

Reader Entry:

Acquire reader_count_mutex to safely modify reader_count
Increment reader_count
If this is the first reader (count became 1), acquire resource_access to block writers
Release reader_count_mutex and proceed to read

Reader Exit:

Acquire reader_count_mutex
Decrement reader_count
If this was the last reader (count became 0), release resource_access to allow writers
Release reader_count_mutex

Writer Entry/Exit:

Simply acquire and release resource_access
Writers are blocked while any reader is active

The Starvation Problem:

Writer Starvation

Analyzing the Solution:

Mutual Exclusion for Writes: ✅ Writers hold resource_access exclusively

Concurrent Reads: ✅ After first reader acquires resource_access, subsequent readers proceed without acquiring it

No Reader-Writer Overlap: ✅ Writers can't acquire resource_access while any reader holds it

Writer Progress: ❌ Not guaranteed—writers can starve under continuous read load

Second Solution: Writers Preference

Key Properties:

Waiting writers block new readers from starting
Active readers complete, but no new ones begin
Risk: Reader starvation if writers continuously arrive

writers_preference.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <pthread.h>
#include <semaphore.h>
 
// Shared data
int shared_data = 0;
 
// Synchronization primitives
int reader_count = 0;
int writer_count = 0;
 
pthread_mutex_t reader_count_mutex = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t writer_count_mutex = PTHREAD_MUTEX_INITIALIZER;
 
sem_t resource_access;    // Controls access to shared resource
sem_t reader_entry;       // Controls whether readers may enter
sem_t reader_try;         // Limits reader entry attempts
 
void init() {
    sem_init(&resource_access, 0, 1);
    sem_init(&reader_entry, 0, 1);
    sem_init(&reader_try, 0, 1);
}
 
void reader() {
    // ========== ENTRY SECTION ==========
    sem_wait(&reader_try);        // Might be blocked by waiting writer
    sem_wait(&reader_entry);      // Serialize reader entry
    
    pthread_mutex_lock(&reader_count_mutex);
    reader_count++;
    if (reader_count == 1) {
        sem_wait(&resource_access);  // First reader locks resource
    }
    pthread_mutex_unlock(&reader_count_mutex);
    
    sem_post(&reader_entry);
    sem_post(&reader_try);
    
    // ========== CRITICAL SECTION (READING) ==========
    printf("Reader: value = %d\n", shared_data);
    
    // ========== EXIT SECTION ==========
    pthread_mutex_lock(&reader_count_mutex);
    reader_count--;
    if (reader_count == 0) {
        sem_post(&resource_access);  // Last reader releases resource
    }
    pthread_mutex_unlock(&reader_count_mutex);
}
 
void writer() {
    // ========== ENTRY SECTION ==========
    pthread_mutex_lock(&writer_count_mutex);
    writer_count++;
    if (writer_count == 1) {
        sem_wait(&reader_try);  // Block new readers from trying
    }
    pthread_mutex_unlock(&writer_count_mutex);
    
    sem_wait(&resource_access);  // Wait for exclusive access
    
    // ========== CRITICAL SECTION (WRITING) ==========
    shared_data++;
    printf("Writer: wrote %d\n", shared_data);
    
    // ========== EXIT SECTION ==========
    sem_post(&resource_access);
    
    pthread_mutex_lock(&writer_count_mutex);
    writer_count--;
    if (writer_count == 0) {
        sem_post(&reader_try);  // Allow readers to try again
    }
    pthread_mutex_unlock(&writer_count_mutex);
}

How Writers Block New Readers:

The key addition is reader_try semaphore:

When the first writer arrives, it acquires reader_try
This blocks any new readers at sem_wait(&reader_try) in their entry section
Active readers continue and complete normally
When no readers remain, writer acquires resource_access and writes
When the last writer exits, it releases reader_try, allowing readers to proceed

The Symmetry Problem:

Comparison of Reader-Writer Solutions
Aspect	Readers Preference	Writers Preference
New readers proceed when writer waiting	✅ Yes	❌ No
Writers can starve	❌ Yes	✅ No
Readers can starve	✅ No	❌ Yes
Best for	Read-heavy, stale data acceptable	Write latency critical
Example use case	DNS cache	Real-time data feeds

Choosing Between Solutions

Fair Reader-Writer Solution

Key Insight:

We use a turnstile (service queue) to serialize access requests. Writers and readers wait in the same queue, ensuring that a waiting writer eventually gets served even if readers keep arriving.

fair_rw_solution.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
#include <pthread.h>
#include <semaphore.h>
 
int shared_data = 0;
int reader_count = 0;
 
pthread_mutex_t reader_count_mutex = PTHREAD_MUTEX_INITIALIZER;
sem_t resource_access;
sem_t service_queue;  // FIFO queue for all accessors (the "turnstile")
 
void init() {
    sem_init(&resource_access, 0, 1);
    sem_init(&service_queue, 0, 1);
}
 
void reader() {
    // ========== ENTRY SECTION ==========
    sem_wait(&service_queue);  // Wait in line (FIFO)
    
    pthread_mutex_lock(&reader_count_mutex);
    reader_count++;
    if (reader_count == 1) {
        sem_wait(&resource_access);
    }
    pthread_mutex_unlock(&reader_count_mutex);
    
    sem_post(&service_queue);  // Let next in line proceed
    
    // ========== CRITICAL SECTION (READING) ==========
    printf("Reader: value = %d\n", shared_data);
    
    // ========== EXIT SECTION ==========
    pthread_mutex_lock(&reader_count_mutex);
    reader_count--;
    if (reader_count == 0) {
        sem_post(&resource_access);
    }
    pthread_mutex_unlock(&reader_count_mutex);
}
 
void writer() {
    // ========== ENTRY SECTION ==========
    sem_wait(&service_queue);  // Wait in line (FIFO)
    sem_wait(&resource_access); // Acquire exclusive access
    
    // ========== CRITICAL SECTION (WRITING) ==========
    shared_data++;
    printf("Writer: wrote %d\n", shared_data);
    
    // ========== EXIT SECTION ==========
    sem_post(&service_queue);  // Let next in line proceed
    sem_post(&resource_access);
}

How Fairness Works:

The Turnstile Concept:

Both readers and writers first wait on service_queue. This creates a FIFO ordering of access requests. The key behavior:

Reader arrives, no writer queued: Reader proceeds, releases service_queue quickly for next accessor
Writer arrives, readers active: Writer waits on service_queue, then resource_access. While waiting on resource_access, it holds service_queue, blocking new readers
New reader arrives, writer waiting: Reader blocks on service_queue behind the writer
Active readers finish: Writer gets resource_access, writes, then releases both
Queued readers proceed: Readers behind writer now proceed concurrently

Bounded Waiting:

Since service_queue enforces FIFO, no accessor waits longer than the time for all ahead of it to be served. Starvation is impossible.

Throughput vs Fairness Tradeoff

Comparison of All Three Solutions:

Reader-Writer Solution Properties
Property	Readers Pref	Writers Pref	Fair
Reader starvation possible	No	Yes	No
Writer starvation possible	Yes	No	No
Read throughput	Highest	Lower	Medium
Write latency	Unbounded	Bounded	Bounded
Read latency	Bounded	Unbounded	Bounded
Implementation complexity	Simple	Medium	Simple

POSIX Reader-Writer Locks

POSIX rwlock API:

posix_rwlock_example.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
#include <pthread.h>
#include <stdio.h>
 
// Shared data protected by reader-writer lock
typedef struct {
    int value;
    char name[64];
    pthread_rwlock_t rwlock;
} SharedResource;
 
SharedResource shared;
 
void init_shared() {
    shared.value = 0;
    strcpy(shared.name, "initial");
    
    // Initialize reader-writer lock with default attributes
    pthread_rwlock_init(&shared.rwlock, NULL);
    
    // Or with specific attributes (e.g., writer preference)
    pthread_rwlockattr_t attr;
    pthread_rwlockattr_init(&attr);
    // PTHREAD_RWLOCK_PREFER_READER_NP or PTHREAD_RWLOCK_PREFER_WRITER_NP
    // (NP = non-portable, Linux-specific)
    pthread_rwlockattr_setkind_np(&attr, PTHREAD_RWLOCK_PREFER_WRITER_NP);
    pthread_rwlock_init(&shared.rwlock, &attr);
}
 
void reader() {
    // Acquire read lock - blocks if writer is active or waiting
    // Multiple readers can hold this simultaneously
    pthread_rwlock_rdlock(&shared.rwlock);
    
    // Read operations
    printf("Reader: value=%d, name=%s\n", shared.value, shared.name);
    
    // Release read lock
    pthread_rwlock_unlock(&shared.rwlock);
}
 
void writer(int new_value, const char* new_name) {
    // Acquire write lock - blocks if any reader or writer is active
    // Exclusive access guaranteed
    pthread_rwlock_wrlock(&shared.rwlock);
    
    // Write operations
    shared.value = new_value;
    strcpy(shared.name, new_name);
    printf("Writer: set value=%d, name=%s\n", shared.value, shared.name);
    
    // Release write lock
    pthread_rwlock_unlock(&shared.rwlock);
}
 
// Non-blocking variants
int try_read() {
    if (pthread_rwlock_tryrdlock(&shared.rwlock) == 0) {
        int val = shared.value;
        pthread_rwlock_unlock(&shared.rwlock);
        return val;
    }
    return -1;  // Lock not available
}
 
int try_write(int value) {
    if (pthread_rwlock_trywrlock(&shared.rwlock) == 0) {
        shared.value = value;
        pthread_rwlock_unlock(&shared.rwlock);
        return 0;  // Success
    }
    return -1;  // Lock not available
}
 
// Timed variants
int timed_read(int timeout_ms) {
    struct timespec ts;
    clock_gettime(CLOCK_REALTIME, &ts);
    ts.tv_nsec += timeout_ms * 1000000;
    
    if (pthread_rwlock_timedrdlock(&shared.rwlock, &ts) == 0) {
        int val = shared.value;
        pthread_rwlock_unlock(&shared.rwlock);
        return val;
    }
    return -1;  // Timeout
}

POSIX rwlock Functions
Function	Purpose	Blocking Behavior
`pthread_rwlock_init`	Initialize rwlock	N/A
`pthread_rwlock_destroy`	Destroy rwlock	N/A
`pthread_rwlock_rdlock`	Acquire read lock	Blocks if writer active/waiting
`pthread_rwlock_wrlock`	Acquire write lock	Blocks if any accessor active
`pthread_rwlock_unlock`	Release lock (read or write)	N/A
`pthread_rwlock_tryrdlock`	Non-blocking read lock	Returns immediately
`pthread_rwlock_trywrlock`	Non-blocking write lock	Returns immediately
`pthread_rwlock_timedrdlock`	Read lock with timeout	Blocks up to timeout
`pthread_rwlock_timedwrlock`	Write lock with timeout	Blocks up to timeout

rwlock Caveats

Never upgrade a read lock to write lock (deadlock). 2) Recursive read locking behavior is implementation-defined. 3) Default preference (readers vs writers) varies by implementation. 4) For short critical sections, a simple mutex may outperform rwlock due to overhead. Profile before assuming rwlock is faster.

Reader-Writer Locks Across Languages

JavaReadWriteLock.java
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
import java.util.concurrent.locks.*;
 
public class SharedCache {
    private final ReadWriteLock rwLock = new ReentrantReadWriteLock();
    private final Lock readLock = rwLock.readLock();
    private final Lock writeLock = rwLock.writeLock();
    
    private Map<String, String> cache = new HashMap<>();
    
    public String get(String key) {
        readLock.lock();
        try {
            return cache.get(key);
        } finally {
            readLock.unlock();
        }
    }
    
    public void put(String key, String value) {
        writeLock.lock();
        try {
            cache.put(key, value);
        } finally {
            writeLock.unlock();
        }
    }
    
    // Lock downgrade example (write -> read)
    public String computeIfAbsent(String key, Function<String, String> compute) {
        readLock.lock();
        try {
            String value = cache.get(key);
            if (value != null) return value;
        } finally {
            readLock.unlock();
        }
        
        writeLock.lock();
        try {
            // Re-check under write lock
            String value = cache.get(key);
            if (value != null) return value;
            
            value = compute.apply(key);
            cache.put(key, value);
            return value;
        } finally {
            writeLock.unlock();
        }
    }
}

Language-Specific Considerations

Real-World Applications

The reader-writer pattern appears throughout computing wherever read-heavy workloads access shared data. Understanding these applications helps you recognize when to apply the pattern.

Database Systems

•Row-Level Locking: Databases use reader-writer locks at row level. SELECT queries acquire shared (read) locks; UPDATE/DELETE acquire exclusive (write) locks. Multiple transactions can read the same row concurrently.
•Table-Level Locking: Coarser granularity for DDL operations. ALTER TABLE requires exclusive access; normal queries use shared access.
•MVCC Alternative: Modern databases often use Multi-Version Concurrency Control instead, maintaining multiple versions to allow readers to see consistent snapshots without blocking writers.

Caching Systems

•In-Memory Caches: Application caches (e.g., Guava Cache, Caffeine) use reader-writer locks for thread-safe access. Reads vastly outnumber writes, making RW locks essential for performance.
•Configuration Caches: System configuration loaded once, read constantly. Reader-writer locks enable near-zero-overhead reads during normal operation.
•DNS Caches: DNS resolution results are cached and read frequently; TTL expiration triggers writes. Perfect reader-writer scenario.

File Systems

•File Locking: fcntl() and flock() support shared (read) and exclusive (write) locks. Multiple processes can read a file simultaneously.
•Directory Operations: Reading directory contents allows concurrent access; modifications (create/delete files) require exclusive access to parent directory.
•Inode Caches: File system metadata is read-frequently, updated rarely. Reader-writer semantics optimize access to cached inode information.

When NOT to Use Reader-Writer Locks

Summary: The Reader-Writer Pattern

Key Takeaways

•Asymmetric Access: Multiple readers can access concurrently; writers need exclusive access. This asymmetry enables significant concurrency gains in read-heavy workloads.
•Three Classic Solutions: Readers preference (writers may starve), writers preference (readers may starve), and fair solution (no starvation, bounded waiting).
•Starvation is the Core Challenge: Any solution must address whether continuous arrivals of one type can indefinitely postpone the other type.
•POSIX rwlock: Production code should use pthread_rwlock_t rather than manual implementation. Consider the preference attribute for your use case.
•Measure Before Optimizing: For short critical sections, mutex may outperform rwlock. The pattern shines for read-heavy workloads with non-trivial read operations.
•Ubiquitous Pattern: Databases, caches, file systems, configuration management—reader-writer semantics appear throughout systems programming.

What's Next:

Page Complete