Reader Preference vs Writer Preference

Time →
R0:  [=====READING=====]
R1:       [====READING====]     ← joins immediately (no writer active)
R2:            [====READING====] ← joins immediately
R3:                 [====READING====] ← joins immediately
W1:                                    [==WRITE==] ← finally gets access
W2:                                               [==WRITE==]
 
Note: Writers W1 and W2 are delayed until ALL readers finish.
If readers keep arriving, writers may NEVER get access (starvation!).

Time →
R0:  [=====READING=====]
R1:       [====READING====]     ← joins (no writer waiting yet)
W1:                        [==WRITE==] ← gets priority once R0,R1 finish
R2:                                   [====READING====] ← now can proceed
R3:                                   [====READING====] ← concurrent with R2
W2:                                                    [==WRITE==]
 
Note: R2 and R3 must wait even though only readers are active
      because W1 was waiting. Writers get priority over later readers.

Time →
R0:  [=====READING=====]
R1:       [====READING====]     ← joins (arrived before W1)
W1:                        [==WRITE==] ← next in queue
R2:                                   [====READING====] ← waits turn
R3:                                   [====READING====] ← concurrent (same batch)
W2:                                                    [==WRITE==]
 
Note: Requests are served in order, but consecutive compatible
      requests (like R2+R3) can be batched together.

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

class ReaderPreferenceRWLock {
    private readers: number = 0;
    private writer: boolean = false;
    
    private mutex: Mutex = new Mutex();
    private readerCondition: ConditionVariable = new ConditionVariable();
    private writerCondition: ConditionVariable = new ConditionVariable();
 
    async readLock(): Promise<void> {
        await this.mutex.acquire();
        try {
            // Reader preference: only wait for ACTIVE writer
            // We DON'T check waitingWriters - readers always have priority
            while (this.writer) {
                await this.readerCondition.wait(this.mutex);
            }
            this.readers++;
        } finally {
            this.mutex.release();
        }
    }
 
    async readUnlock(): Promise<void> {
        await this.mutex.acquire();
        try {
            this.readers--;
            if (this.readers === 0) {
                // Last reader - wake up a waiting writer if any
                this.writerCondition.signal();
            }
        } finally {
            this.mutex.release();
        }
    }
 
    async writeLock(): Promise<void> {
        await this.mutex.acquire();
        try {
            // Writers must wait for all readers AND any active writer
            while (this.readers > 0 || this.writer) {
                await this.writerCondition.wait(this.mutex);
            }
            this.writer = true;
        } finally {
            this.mutex.release();
        }
    }
 
    async writeUnlock(): Promise<void> {
        await this.mutex.acquire();
        try {
            this.writer = false;
            // Wake up ALL waiting readers first (reader preference)
            this.readerCondition.broadcast();
            // Also signal a writer in case no readers are waiting
            this.writerCondition.signal();
        } finally {
            this.mutex.release();
        }
    }
}

Assumption: Readers arrive continuously, each holding the lock for 10ms
 
Time:     0ms    10ms   20ms   30ms   40ms   50ms   ...
R1:       [===]
R2:        [===]
R3:         [===]
R4:          [===]
...               (continuous reader arrivals)
 
Writer W: Attempts to acquire at t=5ms
          Waits for R1 (released at t=10ms)
          But R2 is still active (started at t=2ms, ends at t=12ms)
          And R3 is active (started at t=4ms, ends at t=14ms)
          And R4 arrives and starts immediately (t=6ms)
          ... pattern continues indefinitely
 
Result: Writer W NEVER acquires the lock!
 
This is called "writer starvation" - a liveness violation.

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

class WriterPreferenceRWLock {
    private readers: number = 0;
    private writer: boolean = false;
    private waitingWriters: number = 0;  // Key difference!
    
    // ... condition variables and mutex ...
 
    async readLock(): Promise<void> {
        await this.mutex.acquire();
        try {
            // Writer preference: readers wait for active writer
            // AND for any waiting writers
            while (this.writer || this.waitingWriters > 0) {
                await this.readCondition.wait(this.mutex);
            }
            this.readers++;
        } finally {
            this.mutex.release();
        }
    }
 
    async writeLock(): Promise<void> {
        await this.mutex.acquire();
        try {
            // Increment BEFORE waiting - blocks new readers
            this.waitingWriters++;
            
            while (this.readers > 0 || this.writer) {
                await this.writeCondition.wait(this.mutex);
            }
            
            this.waitingWriters--;
            this.writer = true;
        } finally {
            this.mutex.release();
        }
    }
 
    async writeUnlock(): Promise<void> {
        await this.mutex.acquire();
        try {
            this.writer = false;
            
            // Writer preference: wake another writer first if waiting
            if (this.waitingWriters > 0) {
                this.writeCondition.signal();
            } else {
                // No writers waiting - readers can proceed
                this.readCondition.broadcast();
            }
        } finally {
            this.mutex.release();
        }
    }
}

Assumption: Writers arrive continuously, each holding lock for 10ms
 
Time:     0ms    10ms   20ms   30ms   40ms   50ms   ...
W1:       [===]
W2:       wait   [===]
W3:       wait   wait   [===]
W4:       wait   wait   wait   [===]
...               (continuous writer arrivals)
 
Reader R: Attempts to acquire at t=5ms
          waitingWriters > 0, so R waits
          W1 finishes at t=10ms
          But waitingWriters is still > 0 (W2, W3, W4...)
          R continues waiting indefinitely
 
Result: Reader R NEVER acquires the lock!
 
This is "reader starvation" - symmetric to writer starvation.

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

interface QueueEntry {
    type: 'read' | 'write';
    condition: ConditionVariable;
    granted: boolean;
}
 
class FairReadWriteLock {
    private readers: number = 0;
    private writer: boolean = false;
    private queue: QueueEntry[] = [];
    
    private mutex: Mutex = new Mutex();
 
    async readLock(): Promise<void> {
        await this.mutex.acquire();
        try {
            // If lock is free and queue is empty, proceed immediately
            if (!this.writer && this.queue.length === 0) {
                this.readers++;
                return;
            }
            
            // Otherwise, join the queue and wait
            const entry: QueueEntry = {
                type: 'read',
                condition: new ConditionVariable(),
                granted: false,
            };
            this.queue.push(entry);
            
            while (!entry.granted) {
                await entry.condition.wait(this.mutex);
            }
            
            this.readers++;
        } finally {
            this.mutex.release();
        }
    }
 
    async readUnlock(): Promise<void> {
        await this.mutex.acquire();
        try {
            this.readers--;
            
            if (this.readers === 0) {
                this.wakeNext();
            }
        } finally {
            this.mutex.release();
        }
    }
 
    async writeLock(): Promise<void> {
        await this.mutex.acquire();
        try {
            // If lock is free and queue is empty, proceed immediately
            if (!this.writer && this.readers === 0 && this.queue.length === 0) {
                this.writer = true;
                return;
            }
            
            // Otherwise, join the queue and wait
            const entry: QueueEntry = {
                type: 'write',
                condition: new ConditionVariable(),
                granted: false,
            };
            this.queue.push(entry);
            
            while (!entry.granted) {
                await entry.condition.wait(this.mutex);
            }
            
            this.writer = true;
        } finally {
            this.mutex.release();
        }
    }
 
    async writeUnlock(): Promise<void> {
        await this.mutex.acquire();
        try {
            this.writer = false;
            this.wakeNext();
        } finally {
            this.mutex.release();
        }
    }
 
    private wakeNext(): void {
        if (this.queue.length === 0) {
            return;
        }
        
        // Peek at next request
        const next = this.queue[0];
        
        if (next.type === 'write') {
            // Writer: grant exclusive access
            this.queue.shift();
            next.granted = true;
            next.condition.signal();
        } else {
            // Reader: grant to all consecutive readers at front of queue
            while (this.queue.length > 0 && this.queue[0].type === 'read') {
                const reader = this.queue.shift()!;
                reader.granted = true;
                reader.condition.signal();
            }
        }
    }
}

Initial: readers=0, writer=false, queue=[]
 
R0 readLock():
  - Lock free, queue empty → immediate grant
  - readers=1
 
State: readers=1, writer=false, queue=[]
 
R1 readLock():
  - No writer active, queue empty → immediate grant (can join existing readers)
  - readers=2
 
State: readers=2, writer=false, queue=[]
 
W1 writeLock():
  - readers > 0, must wait
  - Joins queue: [{type:'write', ...}]
  - Waits on condition
 
State: readers=2, writer=false, queue=[W1]
 
R2 readLock():
  - Queue not empty! Cannot bypass W1
  - Joins queue: [{W1}, {type:'read', ...}]
  - Waits on condition
 
State: readers=2, writer=false, queue=[W1, R2]
 
R3 readLock():
  - Queue not empty, must wait
  - Joins queue: [W1, R2, R3]
 
State: readers=2, writer=false, queue=[W1, R2, R3]
 
R0, R1 both call readUnlock():
  - readers=0
  - wakeNext() called
  - Next is W1 (write) → grant exclusive access
  - W1 wakes up, writer=true
 
State: readers=0, writer=true, queue=[R2, R3]
 
W1 writeUnlock():
  - writer=false
  - wakeNext() called
  - Next is R2 (read), followed by R3 (read)
  - Grant both: they can run concurrently
  - R2 and R3 both wake up
 
State: readers=2, writer=false, queue=[]
 
Result: Everyone gets access in order, no starvation!

START: What are your latency requirements?
 
├── "I need bounded latency for ALL operations"
│   └── Use FAIR lock
│       └── Trade off: ~15-20% lower throughput
│
├── "Write latency is critical, read latency is flexible"
│   └── Use WRITER PREFERENCE
│       └── Caution: Monitor read p99 during write bursts
│
├── "Read latency is critical, writes can wait"
│   │
│   └── "How rare are writes?"
│       │
│       ├── "< 0.1% of operations AND writes have no deadline"
│       │   └── Consider READER PREFERENCE
│       │       └── Caution: Implement timeout for writes
│       │
│       └── "Writes are uncommon but have deadlines"
│           └── Use WRITER PREFERENCE or FAIR
│
└── "Not sure / General purpose"
    └── Use WRITER PREFERENCE (most common default)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

// Java: Using a fair read-write lock
import java.util.concurrent.locks.ReentrantReadWriteLock;
 
// The 'true' argument makes it fair (FIFO ordering)
ReadWriteLock fairLock = new ReentrantReadWriteLock(true);
 
// Usage is identical to unfair lock
fairLock.readLock().lock();
try {
    // read operations
} finally {
    fairLock.readLock().unlock();
}
 
// Note: Fair locks have ~10-20% overhead due to queue management
// Use only when you need bounded latency guarantees

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

// Lock downgrade example (Java)
ReentrantReadWriteLock rwLock = new ReentrantReadWriteLock();
 
void updateAndVerify(String key, String newValue) {
    rwLock.writeLock().lock();
    try {
        // Perform the write
        data.put(key, newValue);
        
        // Now I want to verify, but don't need exclusive access
        // Downgrade: acquire read lock while holding write lock
        rwLock.readLock().lock();
    } finally {
        // Release write lock - still holding read lock
        rwLock.writeLock().unlock();
    }
    
    try {
        // Now holding only read lock - other readers can join
        // Verify the write
        Object written = data.get(key);
        assert written.equals(newValue);
    } finally {
        rwLock.readLock().unlock();
    }
}

Thread 1                      Thread 2
─────────                     ─────────
readLock()                    readLock()
// Now 2 readers active       // Now 2 readers active
 
// Want to write              // Want to write
writeLock()                   writeLock()
// Waits for Thread 2         // Waits for Thread 1
// to release read lock       // to release read lock
 
// DEADLOCK! Neither can proceed.
 
Both threads hold read locks and are waiting for the other
to release before they can upgrade to write. Neither will
ever release because they're both blocked waiting.

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

// C# ReaderWriterLockSlim supports upgradeable read locks
ReaderWriterLockSlim rwLock = new ReaderWriterLockSlim();
 
void ReadThenMaybeWrite(string key, string newValue)
{
    // Upgradeable read lock: only ONE thread can hold this at a time
    // This prevents the deadlock scenario above
    rwLock.EnterUpgradeableReadLock();
    try
    {
        var existing = data[key];
        
        if (existing != newValue)
        {
            // Upgrade to write lock
            rwLock.EnterWriteLock();
            try
            {
                data[key] = newValue;
            }
            finally
            {
                rwLock.ExitWriteLock();
            }
        }
    }
    finally
    {
        rwLock.ExitUpgradeableReadLock();
    }
}