Readers Writers Problem - Learning Module

Loading content...

0/227

Semaphore Solutions

The Complete Implementation Guide

We've examined three distinct approaches to the Readers-Writers Problem: Readers Preference maximizing read throughput, Writers Preference ensuring write timeliness, and Fair solutions eliminating starvation. Now we bring these together into a practical implementation guide.

This page serves as your reference for implementing reader-writer synchronization with semaphores. We'll present production-ready code templates, compare solutions side-by-side, discuss debugging strategies, and provide decision frameworks for choosing the right approach for your system.

What You Will Learn

By the end of this page, you will have: complete, production-ready implementations of all three solutions; a decision matrix for choosing solutions; strategies for debugging race conditions; performance tuning guidelines; patterns for upgradable locks; and best practices for production deployment.

Side-by-Side Implementation Comparison

Let's present all three solutions in a unified format for easy comparison. Each implementation includes complete entry and exit protocols for both readers and writers.

readers_preference_complete.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
/*
 * READERS PREFERENCE SOLUTION
 * 
 * Semaphores: 2 (mutex, rw_mutex)
 * Properties: Maximum reader concurrency, writers may starve
 */
 
#include <semaphore.h>
#include <pthread.h>
 
typedef struct {
    int read_count;           // Active readers
    sem_t mutex;              // Protects read_count
    sem_t rw_mutex;           // Reader-writer exclusion
} RWLock_ReaderPref;
 
void rwlock_init_rp(RWLock_ReaderPref* lock) {
    lock->read_count = 0;
    sem_init(&lock->mutex, 0, 1);
    sem_init(&lock->rw_mutex, 0, 1);
}
 
void read_lock_rp(RWLock_ReaderPref* lock) {
    sem_wait(&lock->mutex);
    lock->read_count++;
    if (lock->read_count == 1) {
        sem_wait(&lock->rw_mutex);  // First reader blocks writers
    }
    sem_post(&lock->mutex);
}
 
void read_unlock_rp(RWLock_ReaderPref* lock) {
    sem_wait(&lock->mutex);
    lock->read_count--;
    if (lock->read_count == 0) {
        sem_post(&lock->rw_mutex);  // Last reader allows writers
    }
    sem_post(&lock->mutex);
}
 
void write_lock_rp(RWLock_ReaderPref* lock) {
    sem_wait(&lock->rw_mutex);  // Exclusive access
}
 
void write_unlock_rp(RWLock_ReaderPref* lock) {
    sem_post(&lock->rw_mutex);
}
 
void rwlock_destroy_rp(RWLock_ReaderPref* lock) {
    sem_destroy(&lock->mutex);
    sem_destroy(&lock->rw_mutex);
}

Comparative Analysis

The following tables provide a comprehensive comparison across multiple dimensions to aid in solution selection.

Structural Comparison
Property	Readers Pref	Writers Pref	Fair
Semaphore Count	2	4	3
Shared Variables	1 (read_count)	2 (read_count, write_count)	1 (read_count)
Reader Entry Ops	2 wait, 2 signal	3 wait, 3 signal	3 wait, 3 signal
Writer Entry Ops	1 wait	3 wait, 1 signal	2 wait
Code Complexity	Simple	Complex	Moderate

Behavioral Comparison
Property	Readers Pref	Writers Pref	Fair
Reader Concurrency	Maximum	Lower (gate serialization)	Medium (turnstile)
Writer Starvation	YES (indefinite)	No	No
Reader Starvation	No	YES (indefinite)	No
FIFO Ordering	No	No	Yes
Bounded Waiting	No (for writers)	No (for readers)	Yes (for all)
Deadlock Free	Yes	Yes	Yes

Performance Characteristics
Metric	Readers Pref	Writers Pref	Fair
Read Throughput (read-heavy)	Excellent	Good	Good
Write Throughput (write-heavy)	Poor (starvation)	Excellent	Good
Latency Predictability	Low (writers)	Low (readers)	High
Worst-case Wait Time	Unbounded (W)	Unbounded (R)	Bounded
Overhead per Operation	Lowest	Highest	Medium

Quick Selection Guide

• Readers Preference: Default choice for read-heavy workloads (>90% reads) where writer latency is non-critical. • Writers Preference: Choose when data freshness is critical and writes must complete promptly. • Fair: Use when SLAs require bounded latency for all requests, or starvation is unacceptable.

Production-Ready Implementation

Production implementations require additional features beyond the basic algorithm: error handling, timeouts, statistics, and debug support.

production_rwlock.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
/*
 * Production-Ready Reader-Writer Lock
 * Based on Fair solution with added features
 */
 
#include <semaphore.h>
#include <pthread.h>
#include <errno.h>
#include <time.h>
#include <stdatomic.h>
 
typedef struct {
    // Core synchronization
    int read_count;
    sem_t read_mutex;
    sem_t resource;
    sem_t service_queue;
    
    // Statistics
    atomic_uint64_t total_reads;
    atomic_uint64_t total_writes;
    atomic_uint64_t read_wait_ns;
    atomic_uint64_t write_wait_ns;
    atomic_uint32_t current_readers;
    atomic_bool writer_active;
    
    // Debug support
    pthread_t write_holder;
    const char* last_write_location;
} RWLock_Production;
 
typedef enum {
    RW_SUCCESS = 0,
    RW_TIMEOUT = -1,
    RW_ERROR = -2,
    RW_WOULD_BLOCK = -3
} RWLockResult;
 
// Initialization with error checking
int rwlock_init(RWLock_Production* lock) {
    lock->read_count = 0;
    atomic_store(&lock->current_readers, 0);
    atomic_store(&lock->writer_active, false);
    atomic_store(&lock->total_reads, 0);
    atomic_store(&lock->total_writes, 0);
    atomic_store(&lock->read_wait_ns, 0);
    atomic_store(&lock->write_wait_ns, 0);
    lock->write_holder = 0;
    lock->last_write_location = NULL;
    
    if (sem_init(&lock->read_mutex, 0, 1) != 0) return -1;
    if (sem_init(&lock->resource, 0, 1) != 0) return -1;
    if (sem_init(&lock->service_queue, 0, 1) != 0) return -1;
    
    return 0;
}
 
// Helper: Get current time in nanoseconds
static uint64_t get_time_ns() {
    struct timespec ts;
    clock_gettime(CLOCK_MONOTONIC, &ts);
    return ts.tv_sec * 1000000000ULL + ts.tv_nsec;
}
 
// Timed read lock
RWLockResult read_lock_timed(RWLock_Production* lock, int timeout_ms) {
    uint64_t start = get_time_ns();
    struct timespec deadline;
    clock_gettime(CLOCK_REALTIME, &deadline);
    deadline.tv_sec += timeout_ms / 1000;
    deadline.tv_nsec += (timeout_ms % 1000) * 1000000;
    if (deadline.tv_nsec >= 1000000000) {
        deadline.tv_sec++;
        deadline.tv_nsec -= 1000000000;
    }
    
    // Wait on service queue with timeout
    if (sem_timedwait(&lock->service_queue, &deadline) != 0) {
        if (errno == ETIMEDOUT) return RW_TIMEOUT;
        return RW_ERROR;
    }
    
    sem_wait(&lock->read_mutex);
    lock->read_count++;
    atomic_fetch_add(&lock->current_readers, 1);
    
    if (lock->read_count == 1) {
        if (sem_timedwait(&lock->resource, &deadline) != 0) {
            // Timeout waiting for resource - rollback
            lock->read_count--;
            atomic_fetch_sub(&lock->current_readers, 1);
            sem_post(&lock->read_mutex);
            sem_post(&lock->service_queue);
            if (errno == ETIMEDOUT) return RW_TIMEOUT;
            return RW_ERROR;
        }
    }
    
    sem_post(&lock->read_mutex);
    sem_post(&lock->service_queue);
    
    // Update statistics
    uint64_t wait_time = get_time_ns() - start;
    atomic_fetch_add(&lock->read_wait_ns, wait_time);
    atomic_fetch_add(&lock->total_reads, 1);
    
    return RW_SUCCESS;
}
 
// Blocking read lock
RWLockResult read_lock(RWLock_Production* lock) {
    return read_lock_timed(lock, 30000);  // 30 second default
}
 
// Read unlock
void read_unlock(RWLock_Production* lock) {
    sem_wait(&lock->read_mutex);
    lock->read_count--;
    atomic_fetch_sub(&lock->current_readers, 1);
    
    if (lock->read_count == 0) {
        sem_post(&lock->resource);
    }
    
    sem_post(&lock->read_mutex);
}
 
// Timed write lock with debug info
RWLockResult write_lock_debug(RWLock_Production* lock, 
                               int timeout_ms,
                               const char* file, int line) {
    uint64_t start = get_time_ns();
    struct timespec deadline;
    clock_gettime(CLOCK_REALTIME, &deadline);
    deadline.tv_sec += timeout_ms / 1000;
    deadline.tv_nsec += (timeout_ms % 1000) * 1000000;
    if (deadline.tv_nsec >= 1000000000) {
        deadline.tv_sec++;
        deadline.tv_nsec -= 1000000000;
    }
    
    if (sem_timedwait(&lock->service_queue, &deadline) != 0) {
        if (errno == ETIMEDOUT) return RW_TIMEOUT;
        return RW_ERROR;
    }
    
    if (sem_timedwait(&lock->resource, &deadline) != 0) {
        sem_post(&lock->service_queue);
        if (errno == ETIMEDOUT) return RW_TIMEOUT;
        return RW_ERROR;
    }
    
    // Track holder for debugging
    atomic_store(&lock->writer_active, true);
    lock->write_holder = pthread_self();
    // Store location as static string (file:line)
    static _Thread_local char loc_buf[256];
    snprintf(loc_buf, sizeof(loc_buf), "%s:%d", file, line);
    lock->last_write_location = loc_buf;
    
    // Statistics
    uint64_t wait_time = get_time_ns() - start;
    atomic_fetch_add(&lock->write_wait_ns, wait_time);
    atomic_fetch_add(&lock->total_writes, 1);
    
    return RW_SUCCESS;
}
 
#define write_lock(lock, timeout) \
    write_lock_debug(lock, timeout, __FILE__, __LINE__)
 
void write_unlock(RWLock_Production* lock) {
    atomic_store(&lock->writer_active, false);
    lock->write_holder = 0;
    lock->last_write_location = NULL;
    
    sem_post(&lock->resource);
    sem_post(&lock->service_queue);
}
 
// Statistics helpers
void rwlock_get_stats(RWLock_Production* lock,
                       uint64_t* reads, uint64_t* writes,
                       uint64_t* read_wait, uint64_t* write_wait) {
    *reads = atomic_load(&lock->total_reads);
    *writes = atomic_load(&lock->total_writes);
    *read_wait = atomic_load(&lock->read_wait_ns);
    *write_wait = atomic_load(&lock->write_wait_ns);
}

Production Checklist

✅ Timeout support to prevent hangs ✅ Statistics for monitoring ✅ Debug tracking (who holds lock, where acquired) ✅ Error handling with rollback ✅ Proper initialization and cleanup

Upgradable Read Locks

A common pattern requires a thread to read data, make a decision, then write. The naive approach—unlock read, lock write—has a race condition: another thread might modify data between unlock and lock.

Upgradable locks solve this by allowing a single reader to atomically upgrade to write access without releasing read protection.

upgradable_rwlock.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
/*
 * Upgradable Reader-Writer Lock
 * 
 * Supports three lock types:
 *   - Read: Standard shared access
 *   - Upgradable Read: Shared access with option to upgrade
 *   - Write: Exclusive access
 * 
 * Only ONE thread can hold upgradable-read at a time.
 * Upgradable holder can atomically upgrade to write.
 */
 
#include <semaphore.h>
#include <pthread.h>
 
typedef struct {
    int read_count;
    sem_t read_mutex;
    sem_t resource;
    sem_t service_queue;
    sem_t upgrade_mutex;        // Only one upgradable reader
    pthread_t upgrade_holder;   // Who holds upgradable lock
    int has_upgrade_intent;     // Upgrade in progress
} RWLock_Upgradable;
 
void rwlock_init_up(RWLock_Upgradable* lock) {
    lock->read_count = 0;
    lock->upgrade_holder = 0;
    lock->has_upgrade_intent = 0;
    sem_init(&lock->read_mutex, 0, 1);
    sem_init(&lock->resource, 0, 1);
    sem_init(&lock->service_queue, 0, 1);
    sem_init(&lock->upgrade_mutex, 0, 1);
}
 
// Standard read lock (same as fair solution)
void read_lock_up(RWLock_Upgradable* lock) {
    sem_wait(&lock->service_queue);
    sem_wait(&lock->read_mutex);
    lock->read_count++;
    if (lock->read_count == 1) {
        sem_wait(&lock->resource);
    }
    sem_post(&lock->read_mutex);
    sem_post(&lock->service_queue);
}
 
void read_unlock_up(RWLock_Upgradable* lock) {
    sem_wait(&lock->read_mutex);
    lock->read_count--;
    if (lock->read_count == 0) {
        sem_post(&lock->resource);
    }
    sem_post(&lock->read_mutex);
}
 
// Upgradable read lock
int upgradable_read_lock(RWLock_Upgradable* lock) {
    // Only one upgradable reader allowed
    if (sem_trywait(&lock->upgrade_mutex) != 0) {
        return -1;  // Another thread has upgradable lock
    }
    
    // Get read access (same as normal read)
    sem_wait(&lock->service_queue);
    sem_wait(&lock->read_mutex);
    lock->read_count++;
    if (lock->read_count == 1) {
        sem_wait(&lock->resource);
    }
    sem_post(&lock->read_mutex);
    sem_post(&lock->service_queue);
    
    lock->upgrade_holder = pthread_self();
    return 0;
}
 
// Upgrade from upgradable-read to write
int upgrade_to_write(RWLock_Upgradable* lock) {
    // Verify we hold the upgradable lock
    if (lock->upgrade_holder != pthread_self()) {
        return -1;  // Don't hold upgradable lock
    }
    
    lock->has_upgrade_intent = 1;
    
    // Release our read count and wait for others
    sem_wait(&lock->read_mutex);
    lock->read_count--;
    
    if (lock->read_count == 0) {
        // We were the only reader, proceed immediately
        sem_post(&lock->read_mutex);
        // We already "own" the resource logically
    } else {
        // Other readers present - wait for them
        sem_post(&lock->read_mutex);
        
        // Wait for resource (last reader will signal)
        sem_wait(&lock->resource);
    }
    
    lock->has_upgrade_intent = 0;
    return 0;
}
 
// Release write lock acquired via upgrade
void upgrade_write_unlock(RWLock_Upgradable* lock) {
    lock->upgrade_holder = 0;
    sem_post(&lock->upgrade_mutex);  // Release upgradable privilege
    sem_post(&lock->resource);        // Release resource
}
 
// Release upgradable read without upgrading
void upgradable_read_unlock(RWLock_Upgradable* lock) {
    lock->upgrade_holder = 0;
    sem_post(&lock->upgrade_mutex);
    read_unlock_up(lock);  // Normal read unlock
}

Upgrade Deadlock Risk

If two threads try to upgrade simultaneously (having acquired regular read locks, not upgradable), both will deadlock waiting for the other to release. This is why only ONE upgradable lock is allowed at a time. Design patterns should ensure only one code path uses upgradable locks, or use try-upgrade with fallback.

Debugging Race Conditions

Reader-writer lock bugs are notoriously difficult to diagnose. They often manifest only under specific timing conditions. Here are strategies for finding and fixing them.

Common Bug Patterns

•Unbalanced lock/unlock: Forgetting to unlock on error paths leaves the lock permanently held
•Wrong unlock function: Calling read_unlock after write_lock corrupts internal state
•Recursive locking: Attempting to acquire write lock while holding read lock causes self-deadlock
•Counter corruption: Race on read_count due to missing mutex protection
•Signal without wait: Signaling a semaphore without corresponding wait breaks invariants

debug_rwlock.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
/*
 * Debug-Instrumented Reader-Writer Lock
 * For development/testing use - too slow for production
 */
 
#include <assert.h>
#include <pthread.h>
 
typedef struct {
    // Normal lock state
    RWLock_Production base;
    
    // Debug tracking
    pthread_mutex_t debug_mutex;
    pthread_t readers[1000];
    int reader_count_debug;
    pthread_t writer_thread;
    const char* writer_location;
    
    // Validation
    int poisoned;  // Set on detected corruption
} RWLock_Debug;
 
void debug_read_lock(RWLock_Debug* lock, const char* file, int line) {
    pthread_t self = pthread_self();
    
    // Check for self-deadlock: writer trying to read
    pthread_mutex_lock(&lock->debug_mutex);
    assert(!lock->poisoned && "Lock is corrupted!");
    if (lock->writer_thread == self) {
        fprintf(stderr, "DEADLOCK: Thread %lu holds write lock at %s, "
                "attempting read lock at %s:%d\n",
                self, lock->writer_location, file, line);
        lock->poisoned = 1;
        abort();
    }
    
    // Check for recursive read (might be intentional, just warn)
    for (int i = 0; i < lock->reader_count_debug; i++) {
        if (lock->readers[i] == self) {
            fprintf(stderr, "WARNING: Recursive read lock by %lu at %s:%d\n",
                    self, file, line);
        }
    }
    pthread_mutex_unlock(&lock->debug_mutex);
    
    // Actual lock
    read_lock(&lock->base);
    
    // Track reader
    pthread_mutex_lock(&lock->debug_mutex);
    lock->readers[lock->reader_count_debug++] = self;
    pthread_mutex_unlock(&lock->debug_mutex);
}
 
void debug_read_unlock(RWLock_Debug* lock, const char* file, int line) {
    pthread_t self = pthread_self();
    
    // Verify we hold a read lock
    pthread_mutex_lock(&lock->debug_mutex);
    int found = 0;
    for (int i = 0; i < lock->reader_count_debug; i++) {
        if (lock->readers[i] == self) {
            // Remove from array
            lock->readers[i] = lock->readers[--lock->reader_count_debug];
            found = 1;
            break;
        }
    }
    if (!found) {
        fprintf(stderr, "ERROR: Thread %lu unlocking read without lock at %s:%d\n",
                self, file, line);
        lock->poisoned = 1;
        abort();
    }
    pthread_mutex_unlock(&lock->debug_mutex);
    
    read_unlock(&lock->base);
}
 
void debug_write_lock(RWLock_Debug* lock, const char* file, int line) {
    pthread_t self = pthread_self();
    
    // Check for self-deadlock: reader trying to write
    pthread_mutex_lock(&lock->debug_mutex);
    for (int i = 0; i < lock->reader_count_debug; i++) {
        if (lock->readers[i] == self) {
            fprintf(stderr, "DEADLOCK: Thread %lu holds read lock, "
                    "attempting write lock at %s:%d\n", self, file, line);
            lock->poisoned = 1;
            abort();
        }
    }
    pthread_mutex_unlock(&lock->debug_mutex);
    
    write_lock(&lock->base, 30000);
    
    pthread_mutex_lock(&lock->debug_mutex);
    lock->writer_thread = self;
    static _Thread_local char buf[256];
    snprintf(buf, sizeof(buf), "%s:%d", file, line);
    lock->writer_location = buf;
    pthread_mutex_unlock(&lock->debug_mutex);
}
 
// Macro wrappers to capture location
#define READ_LOCK(lock) debug_read_lock(lock, __FILE__, __LINE__)
#define READ_UNLOCK(lock) debug_read_unlock(lock, __FILE__, __LINE__)
#define WRITE_LOCK(lock) debug_write_lock(lock, __FILE__, __LINE__)

Use ThreadSanitizer

Compile with -fsanitize=thread (GCC/Clang) to detect data races at runtime. TSan intercepts synchronization primitives and memory accesses, detecting many bugs automatically. It's one of the most effective tools for concurrency debugging.

Testing Strategies

Concurrent code requires aggressive testing to expose timing-dependent bugs. Here are proven strategies for reader-writer lock testing.

rwlock_tests.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
/*
 * Comprehensive Reader-Writer Lock Test Suite
 */
 
#include <pthread.h>
#include <stdatomic.h>
#include <assert.h>
 
// Test 1: Safety Property - No data corruption
atomic_int shared_data = 0;
atomic_bool corruption_detected = false;
 
void* safety_reader(void* arg) {
    RWLock_Production* lock = arg;
    for (int i = 0; i < 10000; i++) {
        read_lock(lock);
        
        // Read must see consistent data
        int val = atomic_load(&shared_data);
        if (val != 0 && val != 42) {
            // Value should only be 0 (init) or 42 (written)
            corruption_detected = true;
        }
        
        read_unlock(lock);
    }
    return NULL;
}
 
void* safety_writer(void* arg) {
    RWLock_Production* lock = arg;
    for (int i = 0; i < 1000; i++) {
        write_lock(lock, 30000);
        
        // Non-atomic multi-step write
        atomic_store(&shared_data, 0);   // Clear
        for (volatile int j = 0; j < 100; j++);  // Delay
        atomic_store(&shared_data, 42);  // Set final value
        
        write_unlock(lock);
    }
    return NULL;
}
 
void test_safety() {
    RWLock_Production lock;
    rwlock_init(&lock);
    
    pthread_t readers[20], writers[5];
    for (int i = 0; i < 20; i++)
        pthread_create(&readers[i], NULL, safety_reader, &lock);
    for (int i = 0; i < 5; i++)
        pthread_create(&writers[i], NULL, safety_writer, &lock);
    
    for (int i = 0; i < 20; i++)
        pthread_join(readers[i], NULL);
    for (int i = 0; i < 5; i++)
        pthread_join(writers[i], NULL);
    
    assert(!corruption_detected && "Data corruption detected!");
    printf("Safety test passed\n");
}
 
// Test 2: Exclusivity - Writers are exclusive
atomic_int active_readers = 0;
atomic_int active_writers = 0;
atomic_bool exclusivity_violation = false;
 
void* exclusivity_reader(void* arg) {
    RWLock_Production* lock = arg;
    for (int i = 0; i < 5000; i++) {
        read_lock(lock);
        atomic_fetch_add(&active_readers, 1);
        
        // Check: no writer should be active
        if (atomic_load(&active_writers) > 0) {
            exclusivity_violation = true;
        }
        
        // Simulate work
        for (volatile int j = 0; j < 50; j++);
        
        atomic_fetch_sub(&active_readers, 1);
        read_unlock(lock);
    }
    return NULL;
}
 
void* exclusivity_writer(void* arg) {
    RWLock_Production* lock = arg;
    for (int i = 0; i < 500; i++) {
        write_lock(lock, 30000);
        atomic_fetch_add(&active_writers, 1);
        
        // Check: no readers or other writers
        if (atomic_load(&active_readers) > 0 ||
            atomic_load(&active_writers) > 1) {
            exclusivity_violation = true;
        }
        
        for (volatile int j = 0; j < 100; j++);
        
        atomic_fetch_sub(&active_writers, 1);
        write_unlock(lock);
    }
    return NULL;
}
 
// Test 3: Starvation Detection (for Fair locks)
atomic_bool writer_completed = false;
 
void* continuous_reader(void* arg) {
    RWLock_Production* lock = arg;
    while (!atomic_load(&writer_completed)) {
        read_lock(lock);
        for (volatile int j = 0; j < 10; j++);  // Brief work
        read_unlock(lock);
    }
    return NULL;
}
 
void* monitored_writer(void* arg) {
    RWLock_Production* lock = arg;
    
    write_lock(lock, 5000);  // 5 second timeout
    // If we get here, writer wasn't starved
    atomic_store(&writer_completed, true);
    write_unlock(lock);
    
    return NULL;
}
 
void test_no_writer_starvation() {
    RWLock_Production lock;
    rwlock_init(&lock);
    
    // Start aggressive readers
    pthread_t readers[50];
    for (int i = 0; i < 50; i++)
        pthread_create(&readers[i], NULL, continuous_reader, &lock);
    
    usleep(100000);  // Let readers establish
    
    // Start writer
    pthread_t writer;
    pthread_create(&writer, NULL, monitored_writer, &lock);
    
    // Writer should complete within reasonable time for fair locks
    pthread_join(writer, NULL);
    
    assert(writer_completed && "Writer starvation detected!");
    printf("Starvation test passed\n");
    
    for (int i = 0; i < 50; i++)
        pthread_join(readers[i], NULL);
}

Testing Best Practices

•Run tests many times: Races may only manifest 1 in 1000 runs. Automate repeated execution.
•Vary thread counts: Test with 2, 10, 100, and 1000 threads to stress different code paths.
•Add artificial delays: Insert random usleeps to vary timing and expose races.
•Test on multi-core systems: Single-core machines hide many concurrency bugs.
•Use stress testing tools: Tools like stress-ng can create CPU contention that exposes races.

Performance Tuning

Once correctness is verified, optimize performance for your specific workload.

Tuning Strategies:

Optimization Techniques

•Reduce critical section time: Move computation outside lock. Only access shared data while holding lock.
•Use read-mostly optimizations: If writes are rare, consider RCU-style algorithms that let readers proceed without locks.
•Avoid lock contention: Shard data across multiple locks if access patterns allow.
•Consider spinlocks for short holds: If critical sections are very brief and you're on multi-core, spinning may beat sleeping.
•Profile before optimizing: Use perf, DTrace, or similar to identify actual bottlenecks.

performance_tips.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
// BEFORE: Long critical section
void update_slow(RWLock* lock, Data* new_data) {
    write_lock(lock);
    
    // DON'T: Expensive computation while holding lock
    Data* processed = expensive_transform(new_data);  // Blocks all readers!
    memcpy(shared_data, processed, sizeof(Data));
    
    write_unlock(lock);
}
 
// AFTER: Minimize critical section
void update_fast(RWLock* lock, Data* new_data) {
    // DO: Prepare everything before acquiring lock
    Data* processed = expensive_transform(new_data);
    
    write_lock(lock);
    memcpy(shared_data, processed, sizeof(Data));  // Quick copy only
    write_unlock(lock);
    
    free(processed);
}
 
// Lock sharding for reduced contention
#define SHARD_COUNT 16
 
typedef struct {
    RWLock locks[SHARD_COUNT];
    Data shards[SHARD_COUNT];
} ShardedData;
 
void sharded_read(ShardedData* sd, int key) {
    int shard = key % SHARD_COUNT;
    read_lock(&sd->locks[shard]);
    Data result = sd->shards[shard];
    read_unlock(&sd->locks[shard]);
    return result;
}

Performance Impact of Optimizations
Optimization	Typical Improvement	Applicable When
Reduce critical section	2-10x	Long computation under lock
Lock sharding	Near-linear with shard count	Independent data subsets
Read-mostly optimization (RCU)	100x+ for reads	Extremely rare writes
Spin-then-block hybrid	10-50%	Short holds, multi-core
Batch updates	Varies	Many small writes can combine

Platform-Specific Implementations

Production systems typically use platform-provided reader-writer locks rather than building from semaphores. Here's how to use common implementations:

posix_rwlock.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
#include <pthread.h>
 
pthread_rwlock_t rwlock;
pthread_rwlockattr_t attr;
 
// Initialize with writer preference
pthread_rwlockattr_init(&attr);
pthread_rwlockattr_setkind_np(&attr, 
    PTHREAD_RWLOCK_PREFER_WRITER_NONRECURSIVE_NP);
pthread_rwlock_init(&rwlock, &attr);
 
// Read lock
pthread_rwlock_rdlock(&rwlock);
// ... read ...
pthread_rwlock_unlock(&rwlock);
 
// Write lock
pthread_rwlock_wrlock(&rwlock);
// ... write ...
pthread_rwlock_unlock(&rwlock);
 
// Timed operations
struct timespec deadline;
clock_gettime(CLOCK_REALTIME, &deadline);
deadline.tv_sec += 5;  // 5 second timeout
 
if (pthread_rwlock_timedrdlock(&rwlock, &deadline) == ETIMEDOUT) {
    // Handle timeout
}

Use Platform Primitives

In production code, prefer platform-provided locks over hand-rolled semaphore solutions. They're optimized for the platform, well-tested, and maintained. Only build custom solutions when platform locks don't meet specific requirements (e.g., custom fairness, priority inheritance).

Decision Framework

Use this framework to select the appropriate reader-writer solution for your system.

decision_tree.txt
            ┌─────────────────────────────────────┐
            │  Is starvation of any thread       │
            │  unacceptable?                     │
            └──────────────┬──────────────────────┘
                           │
              ┌────────────┴────────────┐
              │                         │
             YES                        NO
              │                         │
              ▼                         ▼
    ┌─────────────────┐      ┌─────────────────────────────┐
    │   FAIR SOLUTION │      │  What is the read/write     │
    │   (No starvation│      │  ratio?                     │
    │    guaranteed)  │      └──────────────┬──────────────┘
    └─────────────────┘                     │
                               ┌────────────┴────────────┐
                               │                         │
                         Reads >> Writes           Writes critical
                         (10:1 or higher)          (time-sensitive)
                               │                         │
                               ▼                         ▼
                    ┌─────────────────┐      ┌─────────────────┐
                    │    READERS      │      │    WRITERS      │
                    │   PREFERENCE    │      │   PREFERENCE    │
                    │ (Max read       │      │ (Writers don't  │
                    │  throughput)    │      │  starve)        │
                    └─────────────────┘      └─────────────────┘

Quick Reference: Solution Selection
If Your System Needs...	Use This Solution
Maximum read throughput, writes can wait	Readers Preference
Data freshness, writes must complete quickly	Writers Preference
SLA guarantees, predictable latency	Fair (FIFO)
Balance throughput and fairness	Fair or Adaptive Hybrid
Extreme read performance (1000:1 ratio)	Consider RCU
Simple implementation, moderate workload	Use platform pthread_rwlock

When in Doubt, Choose Fair

If you're unsure about workload characteristics, the Fair solution is usually the safest default. It prevents catastrophic starvation scenarios and provides predictable latency. You can always optimize to a preference solution later if profiling shows it's beneficial.

Summary and Module Completion

We have completed a comprehensive exploration of the Readers-Writers Problem and its semaphore-based solutions. Let's consolidate everything we've learned across all five pages:

Module Key Takeaways

•The Problem: Readers can safely access shared resources concurrently; writers need exclusive access. This asymmetry enables higher concurrency than simple mutual exclusion.
•Three Solutions: Readers Preference maximizes read throughput (writers may starve), Writers Preference ensures write timeliness (readers may starve), Fair solutions eliminate starvation (slight throughput cost).
•First/Last Pattern: The key implementation technique—only the first reader acquires the writer-exclusion lock; only the last reader releases it.
•Starvation is Real: Production systems experience starvation under sustained load. Choose solutions based on which starvation is more acceptable (or choose Fair to prevent both).
•Implementation Matters: Use timeouts, statistics, and debug tracking in production. Prefer platform-provided locks when appropriate.
•Testing is Essential: Concurrency bugs hide until specific timing occurs. Stress test with many threads, varied delays, and tools like ThreadSanitizer.

Complete Solution Summary
Solution	Semaphores	Starves?	Best For
Readers Preference	2	Writers	Read-heavy, write-tolerant
Writers Preference	4	Readers	Write-critical, real-time data
Fair (FIFO)	3	Neither	SLA-bound, predictable systems

Connecting to Broader OS Concepts:

The Readers-Writers Problem is a foundational synchronization pattern that you'll encounter throughout operating systems:

File systems: File locking for shared/exclusive access
Databases: Row/table-level locks with read/write modes
Kernels: Protecting data structures accessed by many readers (processes) and few writers (system calls)
Distributed systems: Quorum-based read/write consensus

Mastering this problem prepares you for understanding increasingly sophisticated concurrency mechanisms in modern systems.

Module Complete

Congratulations! You have completed the Readers-Writers Problem module. You now possess deep understanding of this classic synchronization problem: its formal definition, three canonical solutions, implementation techniques, and practical deployment considerations. This knowledge is essential for designing concurrent systems that are both correct and efficient.