Fair Solution — Readers-Writers Problem | OneNoughtOne

0/105

Operating SystemsReaders-Writers Problem

Readers-Writers Problem

LevelIntermediate

Duration75 mins

TopicReaders-Writers Problem

4 / 5

Fair Solution

Eliminating Starvation Entirely

Both Readers Preference and Writers Preference solutions suffer from starvation—they merely choose which class of threads to sacrifice. For many systems, this tradeoff is unacceptable. A web server cannot tell users "your request may never complete because writers are busy." A database cannot tell applications "your transaction may wait indefinitely." The Fair Solution, also known as the Third Readers-Writers Problem or Starve-Free Solution, eliminates starvation for both readers and writers. It guarantees that every thread eventually accesses the resource, regardless of workload conditions. No thread can be bypassed indefinitely by later arrivals.

What You Will Learn

By the end of this page, you will understand: the formal definition of fairness in synchronization; how FIFO ordering prevents starvation; multiple implementation strategies for fair reader-writer locks; the performance cost of fairness guarantees; hybrid approaches that balance fairness and throughput; and when to choose fair solutions over preference-based ones.

Defining Fairness

Before implementing a fair solution, we need to precisely define what "fair" means in the context of reader-writer synchronization. Bounded Waiting Property: A solution provides bounded waiting if there exists a bound on the number of times other threads can bypass a waiting thread. More formally: For any thread T that requests access at time t, there exists a finite number N such that at most N other threads can complete their access before T gains access. This is distinct from simple progress (eventually getting access) because it guarantees a bound on waiting, not just eventual success. FIFO Fairness: The strongest fairness guarantee is First-In, First-Out (FIFO) ordering: Threads gain access in the order they requested it. With FIFO fairness, the bound N equals the number of threads ahead in the queue when the request was made. This is the most intuitive notion of fairness and what we'll primarily implement.

Fairness Spectrum
Fairness Level	Guarantee	Starvation?	Implementation Complexity
None (Reader Pref)	Readers never wait for readers	Writers can starve	Low
None (Writer Pref)	Writers don't wait for new readers	Readers can starve	Medium
Weak (Progress)	Every thread eventually proceeds	Probabilistically no	Medium
Bounded Waiting	Limited bypass count	Never	Higher
FIFO (Strict)	Order-preserving access	Never	Highest

Fairness vs. Throughput Tension

Strict fairness limits concurrency. In FIFO ordering, if a writer is next in queue after active readers, no additional readers can start—even though they could safely proceed. This reduces reader concurrency. Fairness has a cost; we're trading throughput for predictability.

The FIFO Queue Approach

The conceptually simplest fair solution uses an explicit queue. All arriving threads (readers and writers) join a single queue. Access is granted in queue order, with the constraint that consecutive readers can proceed together. Algorithm Sketch: Arriving thread joins the back of the queue When a thread reaches the front: If it's a writer: wait for active readers to finish, then get exclusive access If it's a reader: if no writer is active, proceed (along with consecutive readers behind) When a thread finishes: signal the next thread(s) in queue The Challenge: Implementing this with semaphores is non-trivial because: We need to wake "all consecutive readers" atomically Writers must know when all active readers finish The queue structure itself needs synchronization

fair_conceptual.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
/*
 * Fair Solution: Conceptual Pseudocode
 * 
 * This shows the logical structure; actual implementation needs
 * careful semaphore placement to avoid races.
 */
 
typedef struct {
    ThreadType type;     // READER or WRITER
    semaphore wait_sem;  // Individual semaphore for this thread
} QueueEntry;
 
Queue waiting_queue;
semaphore queue_mutex = 1;
int active_readers = 0;
bool writer_active = false;
 
void reader_entry() {
    wait(queue_mutex);
    
    if (waiting_queue.empty() && !writer_active) {
        // No one waiting, no writer active: proceed immediately
        active_readers++;
        signal(queue_mutex);
    } else {
        // Must wait in queue
        QueueEntry* me = create_entry(READER);
        waiting_queue.enqueue(me);
        signal(queue_mutex);
        
        wait(me->wait_sem);  // Block until signaled
        // When we wake, we're allowed to proceed
        active_readers++;  // This needs protection too!
    }
}
 
void reader_exit() {
    wait(queue_mutex);
    active_readers--;
    
    if (active_readers == 0 && !waiting_queue.empty()) {
        // Last reader: wake next in queue
        wake_next_entry();
    }
    
    signal(queue_mutex);
}
 
void wake_next_entry() {
    QueueEntry* next = waiting_queue.peek();
    
    if (next->type == WRITER) {
        waiting_queue.dequeue();
        signal(next->wait_sem);
    } else {
        // Wake all consecutive readers
        while (!waiting_queue.empty() && 
               waiting_queue.peek()->type == READER) {
            QueueEntry* reader = waiting_queue.dequeue();
            signal(reader->wait_sem);
        }
    }
}

Implementation Complexity

The conceptual algorithm above has subtle issues: active_readers modifications need synchronization with the wakeup logic; the queue access patterns create races; and memory management for queue entries is tricky. Let's develop a more rigorous implementation.

Semaphore-Based Fair Implementation

A practical fair solution uses a turnstile or service order semaphore. This approach doesn't explicitly maintain a queue but achieves FIFO ordering through semaphore semantics. The Turnstile Technique: A turnstile is a semaphore that each thread must pass through sequentially. Like a physical turnstile at a subway entrance, it ensures threads proceed one at a time in arrival order.

fair_turnstile.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
/*
 * Fair Readers-Writers Solution (Turnstile/Service Order)
 * 
 * Key insight: All threads (readers AND writers) pass through
 * the same turnstile, ensuring FIFO ordering at that point.
 * 
 * Once through the turnstile:
 *   - Readers can proceed concurrently (if no writer active)
 *   - Writers get exclusive access
 */
 
#include <semaphore.h>
 
// Reader coordination
int read_count = 0;
semaphore read_mutex = 1;    // Protects read_count
 
// Resource access
semaphore resource = 1;       // Actual resource access
 
// Fairness mechanism
semaphore service_queue = 1;  // The "turnstile" - FIFO ordering
 
/*
 * FAIR READER PROTOCOL
 * 
 * The service_queue ensures readers don't bypass waiting writers.
 * Each reader must "take a ticket" by passing through service_queue.
 */
void fair_reader(int id) {
    while (true) {
        // ========== ENTRY SECTION ==========
        
        /*
         * Step 1: Enter the service queue (turnstile)
         * This blocks if a writer is holding service_queue
         * FIFO semantics ensure we proceed in arrival order
         */
        wait(service_queue);   // Enter turnstile (may block behind writer)
        
        wait(read_mutex);      // Step 2: Lock read_count
        read_count++;          // Step 3: Register reader
        
        if (read_count == 1) {
            wait(resource);    // Step 4: First reader blocks writers
        }
        
        signal(read_mutex);    // Step 5: Unlock read_count
        signal(service_queue); // Step 6: Exit turnstile - let next through
        
        // ========== CRITICAL SECTION ==========
        
        read_data(id);
        
        // ========== EXIT SECTION ==========
        
        wait(read_mutex);      // Step 7: Lock read_count
        read_count--;          // Step 8: Deregister reader
        
        if (read_count == 0) {
            signal(resource);  // Step 9: Last reader allows writers
        }
        
        signal(read_mutex);    // Step 10: Unlock read_count
    }
}
 
/*
 * FAIR WRITER PROTOCOL
 * 
 * Writer acquires service_queue and HOLDS IT until done.
 * This blocks all new arrivals (readers OR writers).
 */
void fair_writer(int id) {
    while (true) {
        // ========== ENTRY SECTION ==========
        
        /*
         * Step 1: Acquire service_queue
         * This blocks new readers from starting
         * HOLDS service_queue until writing complete
         */
        wait(service_queue);   // Acquire turnstile (block new arrivals)
        wait(resource);        // Step 2: Wait for resource (active readers)
        
        // ========== CRITICAL SECTION ==========
        
        write_data(id);
        
        // ========== EXIT SECTION ==========
        
        signal(resource);      // Step 3: Release resource
        signal(service_queue); // Step 4: Release turnstile
    }
}

How Fairness is Achieved: Readers don't bypass writers: When a writer holds service_queue, arriving readers block at wait(service_queue) . They cannot start until the writer finishes. Writers don't bypass readers: When readers hold service_queue (briefly, one at a time), a writer waits its turn. The FIFO nature of semaphore wait queues preserves order. Readers can still be concurrent: Between acquiring and releasing service_queue, a reader only does O(1) work. Multiple readers can pass through quickly and all be in the critical section. The Key Insight: Readers acquire and immediately release service_queue, while writers hold service_queue throughout their critical section. This asymmetry allows: Readers to flow through when no writer is waiting Writers to block new readers while waiting for active readers

Execution Trace Analysis

Let's trace through scenarios to see how the fair solution prevents starvation. Scenario: Writer Arrives During Reader Activity

fair_trace_1.txt
Initial: read_count=0, service_queue=1, resource=1
 
Time 0: R1 arrives
  R1: wait(service_queue) ✓  [service_queue=0]
  R1: wait(read_mutex) ✓
  R1: read_count++ → 1
  R1: read_count==1: wait(resource) ✓ [resource=0]
  R1: signal(read_mutex)
  R1: signal(service_queue)  [service_queue=1]  ← R1 releases turnstile!
  R1: ** READING **
 
Time 1: W1 arrives (while R1 reading)
  W1: wait(service_queue) ✓  [service_queue=0]  ← W1 holds turnstile
  W1: wait(resource) BLOCKS  [resource=0, held by readers]
 
Time 2: R2 arrives (while R1 reading, W1 waiting)
  R2: wait(service_queue) BLOCKS  [service_queue=0]  ← R2 CANNOT start!
      (Behind W1 in turnstile queue)
 
Time 3: R1 finishes
  R1: wait(read_mutex) ✓
  R1: read_count-- → 0
  R1: read_count==0: signal(resource)  [resource=1]
  R1: signal(read_mutex)
 
Time 3 (continued): W1 unblocks
  W1: wait(resource) ✓  [resource=0]
  W1: ** WRITING **
 
Time 4: W1 finishes
  W1: signal(resource)  [resource=1]
  W1: signal(service_queue)  [service_queue=1]
 
Time 4 (continued): R2 unblocks
  R2: wait(service_queue) ✓  [service_queue=0]
  R2: proceeds to read...

Key Observation: R2 arrived BEFORE W1 finished, but R2 was correctly blocked behind W1. No starvation for W1. R2 proceeds after W1, maintaining FIFO order. Scenario: Multiple Threads, FIFO Ordering

fair_trace_2.txt
Arrival order: R1, R2, W1, R3, R4, W2
 
Execution order will be:
1. R1 starts immediately
2. R2 passes through turnstile quickly, joins R1 in reading
3. W1 acquires turnstile, waits for R1,R2 to finish
4. R3 queues behind W1 in turnstile
5. R4 queues behind R3 in turnstile
6. W2 queues behind R4 in turnstile
7. R1, R2 finish → W1 writes
8. W1 finishes → R3 passes through, R4 follows quickly
9. R3, R4 reading concurrently
10. R3, R4 finish → W2 writes
 
Actual concurrent access:
- R1, R2 concurrent (both readers, no intervening writer)
- W1 exclusive
- R3, R4 concurrent (both readers, no intervening writer)
- W2 exclusive
 
Notice: R3 and R4 are "batched" even though W2 is behind them

Reader Batching Still Occurs

Consecutive readers in the queue still execute concurrently. The fairness mechanism doesn't force strict one-at-a-time access—it only ensures writers aren't bypassed. This preserves much of the reader concurrency benefit.

Proof of Fairness Properties

We now prove that the turnstile solution provides the desired fairness guarantees. Theorem 1: No Writer Starvation Statement: Every waiting writer eventually gains access. Proof: Writers wait on service_queue (at most) and then resource service_queue has FIFO wait semantics When a reader releases service_queue, the next waiter (if a writer) acquires it Once a writer holds service_queue, no new readers can start Active readers eventually finish (bounded critical sections) The last active reader signals resource The writer acquires resource and proceeds ∴ Writers cannot starve ∎

Theorem 2: No Reader Starvation Statement: Every waiting reader eventually gains access. Proof: Readers wait on service_queue (at most) service_queue has FIFO wait semantics Writers hold service_queue for a finite time (bounded critical sections) When a writer releases service_queue, the next waiter (reader or writer) acquires it If the next waiter is a reader, it passes through quickly and proceeds ∴ Readers cannot starve ∎ Theorem 3: Bounded Waiting Statement: There exists a bound on how many threads can bypass a waiting thread. Proof: Let T be a thread that calls wait(service_queue) at time t Let N be the number of threads already waiting on service_queue FIFO semantics guarantee T acquires service_queue after at most N others Once T holds service_queue, it either: (Reader) quickly proceeds and releases (Writer) waits for at most read_count readers (those currently active) Active readers at time t is bounded (finite read_count) ∴ T's wait is bounded by N + max_active_readers ∎

Semaphore Fairness Requirement

These proofs assume FIFO semaphore wait queues. POSIX semaphores don't guarantee FIFO ordering—threads may be woken in any order. For strict fairness guarantees, use fair mutexes (like pthread_mutexattr_setprotocol with PTHREAD_PRIO_INHERIT) or implement explicit FIFO queues.

Alternative Fair Implementations

The turnstile approach isn't the only way to achieve fairness. Let's examine alternative strategies. Approach 2: Ticket-Based Ordering Inspired by ticket locks, each thread takes a number and waits for its turn:

ticket_fair.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
/*
 * Ticket-Based Fair Readers-Writers Lock
 * 
 * Each thread takes a ticket; access granted when ticket is called.
 * Consecutive readers with adjacent tickets can proceed together.
 */
 
atomic_uint next_ticket = 0;
atomic_uint now_serving = 0;
int active_readers = 0;
uint current_batch_end = 0;  // Last ticket in current reader batch
 
void ticket_reader(int id) {
    // Take a ticket
    uint my_ticket = atomic_fetch_add(&next_ticket, 1);
    
    // Wait for our turn (or to join current reader batch)
    while (true) {
        uint serving = atomic_load(&now_serving);
        
        // Can proceed if: our ticket is being served, 
        // OR we're in a reader batch and current is a reader batch
        if (my_ticket == serving) {
            // We're being served
            break;
        }
        if (my_ticket <= current_batch_end && active_readers > 0) {
            // We're part of current reader batch
            break;
        }
        
        // Not our turn yet - yield
        sched_yield();  // Or use condition variable for efficiency
    }
    
    // Entering - extend batch if consecutive readers behind us
    active_readers++;
    extend_batch_if_readers_follow(my_ticket);
    
    // === READING ===
    read_data(id);
    
    // Exiting
    active_readers--;
    if (active_readers == 0) {
        // Last in batch: advance to next ticket
        atomic_store(&now_serving, current_batch_end + 1);
        current_batch_end = 0;
    }
}

Approach 3: Phase-Based Fairness This approach alternates between "reader phases" and "writer phases":

phase_fair.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
/*
 * Phase-Based Fair Readers-Writers Lock
 * 
 * System alternates: all waiting readers, then all waiting writers,
 * then all waiting readers, etc.
 * 
 * Simpler than pure FIFO but still provides bounded waiting.
 */
 
enum Phase { READER_PHASE, WRITER_PHASE };
 
Phase current_phase = READER_PHASE;
int readers_in_phase = 0;
int writers_in_phase = 0;
int waiting_readers = 0;
int waiting_writers = 0;
semaphore mutex = 1;
semaphore reader_gate = 1;
semaphore writer_gate = 0;
 
void phase_reader(int id) {
    wait(mutex);
    
    if (current_phase == WRITER_PHASE || writers_in_phase > 0) {
        // Writer phase active - wait
        waiting_readers++;
        signal(mutex);
        wait(reader_gate);
        wait(mutex);
        waiting_readers--;  // Decremented in switch_to_reader_phase
    }
    
    readers_in_phase++;
    signal(mutex);
    
    // === READING ===
    read_data(id);
    
    wait(mutex);
    readers_in_phase--;
    
    if (readers_in_phase == 0 && waiting_writers > 0) {
        switch_to_writer_phase();
    }
    signal(mutex);
}
 
void switch_to_writer_phase() {
    current_phase = WRITER_PHASE;
    // Wake one writer
    signal(writer_gate);
}
 
void switch_to_reader_phase() {
    current_phase = READER_PHASE;
    // Wake ALL waiting readers
    for (int i = 0; i < waiting_readers; i++) {
        signal(reader_gate);
    }
}

Comparison of Fair Implementations
Approach	Fairness Level	Complexity	Reader Concurrency	Overhead
Turnstile	FIFO	Low-Medium	Consecutive readers batch	Low
Ticket-Based	Strict FIFO	Higher	Full batching	Medium (spinning)
Phase-Based	Bounded (phase-level)	Medium	Full phase batching	Medium
Explicit Queue	Strict FIFO	Highest	Full batching	Higher (memory)

Performance Analysis

Fair solutions trade some throughput for starvation freedom. Let's quantify this tradeoff. Overhead Sources: Serialization Point: All threads pass through service_queue (turnstile approach). This serialization adds latency. Reduced Batching: In preference solutions, new readers can join ongoing reader sessions freely. In fair solutions, new readers after a waiting writer must wait. Wakeup Overhead: Signaling and context-switching between phases costs CPU cycles. Throughput Comparison: Consider a workload with 90% readers, 10% writers, processing times R_time and W_time:

Throughput Under Different Policies (Relative)
Scenario	Readers Pref	Writers Pref	Fair (Turnstile)
Read-heavy (95/5)	1.0x (baseline)	0.8x	0.85x
Balanced (70/30)	0.9x	0.85x	0.82x
Write-heavy (30/70)	Variable (starvation)	0.9x	0.85x
Bursty writers	Variable	0.95x	0.9x
Uniform random	0.95x	0.87x	0.83x

Latency Characteristics:

Metric	Readers Pref	Writers Pref	Fair
Avg Reader Latency	Lowest	Medium	Medium
Max Reader Latency	Low	Unbounded	Bounded
Avg Writer Latency	Medium-High	Low	Medium
Max Writer Latency	Unbounded	Low	Bounded
Tail Latency (p99)	Variable	Variable	Predictable

The Fairness Tax: Fair solutions typically see: 10-20% throughput reduction vs. optimal preference policy More predictable latency distribution Elimination of worst-case scenarios For many systems, the predictability is worth the throughput cost. Unbounded latency is often worse than consistently slightly elevated latency.

When Predictability Matters

SLA-bound systems (99th percentile latency requirements), user-facing services, and real-time systems often prefer fair locks despite lower peak throughput. The absence of catastrophic outliers is worth more than marginally higher average performance.

Operating SystemsReaders-Writers Problem

Readers-Writers Problem

LevelIntermediate

Duration75 mins

TopicReaders-Writers Problem

4 / 5

Fair Solution

Eliminating Starvation Entirely

Both Readers Preference and Writers Preference solutions suffer from starvation—they merely choose which class of threads to sacrifice. For many systems, this tradeoff is unacceptable. A web server cannot tell users "your request may never complete because writers are busy." A database cannot tell applications "your transaction may wait indefinitely." The Fair Solution, also known as the Third Readers-Writers Problem or Starve-Free Solution, eliminates starvation for both readers and writers. It guarantees that every thread eventually accesses the resource, regardless of workload conditions. No thread can be bypassed indefinitely by later arrivals.

What You Will Learn

By the end of this page, you will understand: the formal definition of fairness in synchronization; how FIFO ordering prevents starvation; multiple implementation strategies for fair reader-writer locks; the performance cost of fairness guarantees; hybrid approaches that balance fairness and throughput; and when to choose fair solutions over preference-based ones.

Defining Fairness

Before implementing a fair solution, we need to precisely define what "fair" means in the context of reader-writer synchronization. Bounded Waiting Property: A solution provides bounded waiting if there exists a bound on the number of times other threads can bypass a waiting thread. More formally: For any thread T that requests access at time t, there exists a finite number N such that at most N other threads can complete their access before T gains access. This is distinct from simple progress (eventually getting access) because it guarantees a bound on waiting, not just eventual success. FIFO Fairness: The strongest fairness guarantee is First-In, First-Out (FIFO) ordering: Threads gain access in the order they requested it. With FIFO fairness, the bound N equals the number of threads ahead in the queue when the request was made. This is the most intuitive notion of fairness and what we'll primarily implement.

Fairness Spectrum
Fairness Level	Guarantee	Starvation?	Implementation Complexity
None (Reader Pref)	Readers never wait for readers	Writers can starve	Low
None (Writer Pref)	Writers don't wait for new readers	Readers can starve	Medium
Weak (Progress)	Every thread eventually proceeds	Probabilistically no	Medium
Bounded Waiting	Limited bypass count	Never	Higher
FIFO (Strict)	Order-preserving access	Never	Highest

Fairness vs. Throughput Tension

Strict fairness limits concurrency. In FIFO ordering, if a writer is next in queue after active readers, no additional readers can start—even though they could safely proceed. This reduces reader concurrency. Fairness has a cost; we're trading throughput for predictability.

The FIFO Queue Approach

The conceptually simplest fair solution uses an explicit queue. All arriving threads (readers and writers) join a single queue. Access is granted in queue order, with the constraint that consecutive readers can proceed together. Algorithm Sketch: Arriving thread joins the back of the queue When a thread reaches the front: If it's a writer: wait for active readers to finish, then get exclusive access If it's a reader: if no writer is active, proceed (along with consecutive readers behind) When a thread finishes: signal the next thread(s) in queue The Challenge: Implementing this with semaphores is non-trivial because: We need to wake "all consecutive readers" atomically Writers must know when all active readers finish The queue structure itself needs synchronization

fair_conceptual.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
/*
 * Fair Solution: Conceptual Pseudocode
 * 
 * This shows the logical structure; actual implementation needs
 * careful semaphore placement to avoid races.
 */
 
typedef struct {
    ThreadType type;     // READER or WRITER
    semaphore wait_sem;  // Individual semaphore for this thread
} QueueEntry;
 
Queue waiting_queue;
semaphore queue_mutex = 1;
int active_readers = 0;
bool writer_active = false;
 
void reader_entry() {
    wait(queue_mutex);
    
    if (waiting_queue.empty() && !writer_active) {
        // No one waiting, no writer active: proceed immediately
        active_readers++;
        signal(queue_mutex);
    } else {
        // Must wait in queue
        QueueEntry* me = create_entry(READER);
        waiting_queue.enqueue(me);
        signal(queue_mutex);
        
        wait(me->wait_sem);  // Block until signaled
        // When we wake, we're allowed to proceed
        active_readers++;  // This needs protection too!
    }
}
 
void reader_exit() {
    wait(queue_mutex);
    active_readers--;
    
    if (active_readers == 0 && !waiting_queue.empty()) {
        // Last reader: wake next in queue
        wake_next_entry();
    }
    
    signal(queue_mutex);
}
 
void wake_next_entry() {
    QueueEntry* next = waiting_queue.peek();
    
    if (next->type == WRITER) {
        waiting_queue.dequeue();
        signal(next->wait_sem);
    } else {
        // Wake all consecutive readers
        while (!waiting_queue.empty() && 
               waiting_queue.peek()->type == READER) {
            QueueEntry* reader = waiting_queue.dequeue();
            signal(reader->wait_sem);
        }
    }
}

Implementation Complexity

The conceptual algorithm above has subtle issues: active_readers modifications need synchronization with the wakeup logic; the queue access patterns create races; and memory management for queue entries is tricky. Let's develop a more rigorous implementation.

Semaphore-Based Fair Implementation

A practical fair solution uses a turnstile or service order semaphore. This approach doesn't explicitly maintain a queue but achieves FIFO ordering through semaphore semantics. The Turnstile Technique: A turnstile is a semaphore that each thread must pass through sequentially. Like a physical turnstile at a subway entrance, it ensures threads proceed one at a time in arrival order.

fair_turnstile.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
/*
 * Fair Readers-Writers Solution (Turnstile/Service Order)
 * 
 * Key insight: All threads (readers AND writers) pass through
 * the same turnstile, ensuring FIFO ordering at that point.
 * 
 * Once through the turnstile:
 *   - Readers can proceed concurrently (if no writer active)
 *   - Writers get exclusive access
 */
 
#include <semaphore.h>
 
// Reader coordination
int read_count = 0;
semaphore read_mutex = 1;    // Protects read_count
 
// Resource access
semaphore resource = 1;       // Actual resource access
 
// Fairness mechanism
semaphore service_queue = 1;  // The "turnstile" - FIFO ordering
 
/*
 * FAIR READER PROTOCOL
 * 
 * The service_queue ensures readers don't bypass waiting writers.
 * Each reader must "take a ticket" by passing through service_queue.
 */
void fair_reader(int id) {
    while (true) {
        // ========== ENTRY SECTION ==========
        
        /*
         * Step 1: Enter the service queue (turnstile)
         * This blocks if a writer is holding service_queue
         * FIFO semantics ensure we proceed in arrival order
         */
        wait(service_queue);   // Enter turnstile (may block behind writer)
        
        wait(read_mutex);      // Step 2: Lock read_count
        read_count++;          // Step 3: Register reader
        
        if (read_count == 1) {
            wait(resource);    // Step 4: First reader blocks writers
        }
        
        signal(read_mutex);    // Step 5: Unlock read_count
        signal(service_queue); // Step 6: Exit turnstile - let next through
        
        // ========== CRITICAL SECTION ==========
        
        read_data(id);
        
        // ========== EXIT SECTION ==========
        
        wait(read_mutex);      // Step 7: Lock read_count
        read_count--;          // Step 8: Deregister reader
        
        if (read_count == 0) {
            signal(resource);  // Step 9: Last reader allows writers
        }
        
        signal(read_mutex);    // Step 10: Unlock read_count
    }
}
 
/*
 * FAIR WRITER PROTOCOL
 * 
 * Writer acquires service_queue and HOLDS IT until done.
 * This blocks all new arrivals (readers OR writers).
 */
void fair_writer(int id) {
    while (true) {
        // ========== ENTRY SECTION ==========
        
        /*
         * Step 1: Acquire service_queue
         * This blocks new readers from starting
         * HOLDS service_queue until writing complete
         */
        wait(service_queue);   // Acquire turnstile (block new arrivals)
        wait(resource);        // Step 2: Wait for resource (active readers)
        
        // ========== CRITICAL SECTION ==========
        
        write_data(id);
        
        // ========== EXIT SECTION ==========
        
        signal(resource);      // Step 3: Release resource
        signal(service_queue); // Step 4: Release turnstile
    }
}

How Fairness is Achieved: Readers don't bypass writers: When a writer holds service_queue, arriving readers block at wait(service_queue) . They cannot start until the writer finishes. Writers don't bypass readers: When readers hold service_queue (briefly, one at a time), a writer waits its turn. The FIFO nature of semaphore wait queues preserves order. Readers can still be concurrent: Between acquiring and releasing service_queue, a reader only does O(1) work. Multiple readers can pass through quickly and all be in the critical section. The Key Insight: Readers acquire and immediately release service_queue, while writers hold service_queue throughout their critical section. This asymmetry allows: Readers to flow through when no writer is waiting Writers to block new readers while waiting for active readers

Execution Trace Analysis

Let's trace through scenarios to see how the fair solution prevents starvation. Scenario: Writer Arrives During Reader Activity

fair_trace_1.txt
Initial: read_count=0, service_queue=1, resource=1
 
Time 0: R1 arrives
  R1: wait(service_queue) ✓  [service_queue=0]
  R1: wait(read_mutex) ✓
  R1: read_count++ → 1
  R1: read_count==1: wait(resource) ✓ [resource=0]
  R1: signal(read_mutex)
  R1: signal(service_queue)  [service_queue=1]  ← R1 releases turnstile!
  R1: ** READING **
 
Time 1: W1 arrives (while R1 reading)
  W1: wait(service_queue) ✓  [service_queue=0]  ← W1 holds turnstile
  W1: wait(resource) BLOCKS  [resource=0, held by readers]
 
Time 2: R2 arrives (while R1 reading, W1 waiting)
  R2: wait(service_queue) BLOCKS  [service_queue=0]  ← R2 CANNOT start!
      (Behind W1 in turnstile queue)
 
Time 3: R1 finishes
  R1: wait(read_mutex) ✓
  R1: read_count-- → 0
  R1: read_count==0: signal(resource)  [resource=1]
  R1: signal(read_mutex)
 
Time 3 (continued): W1 unblocks
  W1: wait(resource) ✓  [resource=0]
  W1: ** WRITING **
 
Time 4: W1 finishes
  W1: signal(resource)  [resource=1]
  W1: signal(service_queue)  [service_queue=1]
 
Time 4 (continued): R2 unblocks
  R2: wait(service_queue) ✓  [service_queue=0]
  R2: proceeds to read...

Key Observation: R2 arrived BEFORE W1 finished, but R2 was correctly blocked behind W1. No starvation for W1. R2 proceeds after W1, maintaining FIFO order. Scenario: Multiple Threads, FIFO Ordering

fair_trace_2.txt
Arrival order: R1, R2, W1, R3, R4, W2
 
Execution order will be:
1. R1 starts immediately
2. R2 passes through turnstile quickly, joins R1 in reading
3. W1 acquires turnstile, waits for R1,R2 to finish
4. R3 queues behind W1 in turnstile
5. R4 queues behind R3 in turnstile
6. W2 queues behind R4 in turnstile
7. R1, R2 finish → W1 writes
8. W1 finishes → R3 passes through, R4 follows quickly
9. R3, R4 reading concurrently
10. R3, R4 finish → W2 writes
 
Actual concurrent access:
- R1, R2 concurrent (both readers, no intervening writer)
- W1 exclusive
- R3, R4 concurrent (both readers, no intervening writer)
- W2 exclusive
 
Notice: R3 and R4 are "batched" even though W2 is behind them

Reader Batching Still Occurs

Consecutive readers in the queue still execute concurrently. The fairness mechanism doesn't force strict one-at-a-time access—it only ensures writers aren't bypassed. This preserves much of the reader concurrency benefit.

Proof of Fairness Properties

We now prove that the turnstile solution provides the desired fairness guarantees. Theorem 1: No Writer Starvation Statement: Every waiting writer eventually gains access. Proof: Writers wait on service_queue (at most) and then resource service_queue has FIFO wait semantics When a reader releases service_queue, the next waiter (if a writer) acquires it Once a writer holds service_queue, no new readers can start Active readers eventually finish (bounded critical sections) The last active reader signals resource The writer acquires resource and proceeds ∴ Writers cannot starve ∎

Theorem 2: No Reader Starvation Statement: Every waiting reader eventually gains access. Proof: Readers wait on service_queue (at most) service_queue has FIFO wait semantics Writers hold service_queue for a finite time (bounded critical sections) When a writer releases service_queue, the next waiter (reader or writer) acquires it If the next waiter is a reader, it passes through quickly and proceeds ∴ Readers cannot starve ∎ Theorem 3: Bounded Waiting Statement: There exists a bound on how many threads can bypass a waiting thread. Proof: Let T be a thread that calls wait(service_queue) at time t Let N be the number of threads already waiting on service_queue FIFO semantics guarantee T acquires service_queue after at most N others Once T holds service_queue, it either: (Reader) quickly proceeds and releases (Writer) waits for at most read_count readers (those currently active) Active readers at time t is bounded (finite read_count) ∴ T's wait is bounded by N + max_active_readers ∎

Semaphore Fairness Requirement

These proofs assume FIFO semaphore wait queues. POSIX semaphores don't guarantee FIFO ordering—threads may be woken in any order. For strict fairness guarantees, use fair mutexes (like pthread_mutexattr_setprotocol with PTHREAD_PRIO_INHERIT) or implement explicit FIFO queues.

Alternative Fair Implementations

The turnstile approach isn't the only way to achieve fairness. Let's examine alternative strategies. Approach 2: Ticket-Based Ordering Inspired by ticket locks, each thread takes a number and waits for its turn:

ticket_fair.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
/*
 * Ticket-Based Fair Readers-Writers Lock
 * 
 * Each thread takes a ticket; access granted when ticket is called.
 * Consecutive readers with adjacent tickets can proceed together.
 */
 
atomic_uint next_ticket = 0;
atomic_uint now_serving = 0;
int active_readers = 0;
uint current_batch_end = 0;  // Last ticket in current reader batch
 
void ticket_reader(int id) {
    // Take a ticket
    uint my_ticket = atomic_fetch_add(&next_ticket, 1);
    
    // Wait for our turn (or to join current reader batch)
    while (true) {
        uint serving = atomic_load(&now_serving);
        
        // Can proceed if: our ticket is being served, 
        // OR we're in a reader batch and current is a reader batch
        if (my_ticket == serving) {
            // We're being served
            break;
        }
        if (my_ticket <= current_batch_end && active_readers > 0) {
            // We're part of current reader batch
            break;
        }
        
        // Not our turn yet - yield
        sched_yield();  // Or use condition variable for efficiency
    }
    
    // Entering - extend batch if consecutive readers behind us
    active_readers++;
    extend_batch_if_readers_follow(my_ticket);
    
    // === READING ===
    read_data(id);
    
    // Exiting
    active_readers--;
    if (active_readers == 0) {
        // Last in batch: advance to next ticket
        atomic_store(&now_serving, current_batch_end + 1);
        current_batch_end = 0;
    }
}

Approach 3: Phase-Based Fairness This approach alternates between "reader phases" and "writer phases":

phase_fair.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
/*
 * Phase-Based Fair Readers-Writers Lock
 * 
 * System alternates: all waiting readers, then all waiting writers,
 * then all waiting readers, etc.
 * 
 * Simpler than pure FIFO but still provides bounded waiting.
 */
 
enum Phase { READER_PHASE, WRITER_PHASE };
 
Phase current_phase = READER_PHASE;
int readers_in_phase = 0;
int writers_in_phase = 0;
int waiting_readers = 0;
int waiting_writers = 0;
semaphore mutex = 1;
semaphore reader_gate = 1;
semaphore writer_gate = 0;
 
void phase_reader(int id) {
    wait(mutex);
    
    if (current_phase == WRITER_PHASE || writers_in_phase > 0) {
        // Writer phase active - wait
        waiting_readers++;
        signal(mutex);
        wait(reader_gate);
        wait(mutex);
        waiting_readers--;  // Decremented in switch_to_reader_phase
    }
    
    readers_in_phase++;
    signal(mutex);
    
    // === READING ===
    read_data(id);
    
    wait(mutex);
    readers_in_phase--;
    
    if (readers_in_phase == 0 && waiting_writers > 0) {
        switch_to_writer_phase();
    }
    signal(mutex);
}
 
void switch_to_writer_phase() {
    current_phase = WRITER_PHASE;
    // Wake one writer
    signal(writer_gate);
}
 
void switch_to_reader_phase() {
    current_phase = READER_PHASE;
    // Wake ALL waiting readers
    for (int i = 0; i < waiting_readers; i++) {
        signal(reader_gate);
    }
}

Comparison of Fair Implementations
Approach	Fairness Level	Complexity	Reader Concurrency	Overhead
Turnstile	FIFO	Low-Medium	Consecutive readers batch	Low
Ticket-Based	Strict FIFO	Higher	Full batching	Medium (spinning)
Phase-Based	Bounded (phase-level)	Medium	Full phase batching	Medium
Explicit Queue	Strict FIFO	Highest	Full batching	Higher (memory)

Performance Analysis

Fair solutions trade some throughput for starvation freedom. Let's quantify this tradeoff. Overhead Sources: Serialization Point: All threads pass through service_queue (turnstile approach). This serialization adds latency. Reduced Batching: In preference solutions, new readers can join ongoing reader sessions freely. In fair solutions, new readers after a waiting writer must wait. Wakeup Overhead: Signaling and context-switching between phases costs CPU cycles. Throughput Comparison: Consider a workload with 90% readers, 10% writers, processing times R_time and W_time:

Throughput Under Different Policies (Relative)
Scenario	Readers Pref	Writers Pref	Fair (Turnstile)
Read-heavy (95/5)	1.0x (baseline)	0.8x	0.85x
Balanced (70/30)	0.9x	0.85x	0.82x
Write-heavy (30/70)	Variable (starvation)	0.9x	0.85x
Bursty writers	Variable	0.95x	0.9x
Uniform random	0.95x	0.87x	0.83x

Latency Characteristics:

Metric	Readers Pref	Writers Pref	Fair
Avg Reader Latency	Lowest	Medium	Medium
Max Reader Latency	Low	Unbounded	Bounded
Avg Writer Latency	Medium-High	Low	Medium
Max Writer Latency	Unbounded	Low	Bounded
Tail Latency (p99)	Variable	Variable	Predictable

The Fairness Tax: Fair solutions typically see: 10-20% throughput reduction vs. optimal preference policy More predictable latency distribution Elimination of worst-case scenarios For many systems, the predictability is worth the throughput cost. Unbounded latency is often worse than consistently slightly elevated latency.

When Predictability Matters

SLA-bound systems (99th percentile latency requirements), user-facing services, and real-time systems often prefer fair locks despite lower peak throughput. The absence of catastrophic outliers is worth more than marginally higher average performance.

Fair Solution

Eliminating Starvation Entirely

Defining Fairness

The FIFO Queue Approach

Semaphore-Based Fair Implementation

Execution Trace Analysis

Proof of Fairness Properties

Alternative Fair Implementations

Performance Analysis

There’s more to understand.

Fair Solution

Eliminating Starvation Entirely

Defining Fairness

The FIFO Queue Approach

Semaphore-Based Fair Implementation

Execution Trace Analysis

Proof of Fairness Properties

Alternative Fair Implementations

Performance Analysis

There’s more to understand.