Reader–Writer Locks

1. The Reader–Writer Problem

In many shared data structures, not all operations are the same:

• Readers: Only read data (e.g., searching a list)

• Writers: Modify data (e.g., inserting or deleting nodes)

Why a Simple Lock Is Not Enough

Using a single mutex forces:

• Only one thread at a time, even if all threads are just reading

• This is correct but inefficient

Key Observation

• Multiple readers can safely run together

• Writers need exclusive access

• Readers and writers must not overlap

---

2. What Is a Reader–Writer Lock?

A reader–writer lock is a synchronization mechanism that allows:

Situation	Allowed?
Multiple readers	✅ Yes
One writer	✅ Yes
Reader + Writer	❌ No
Multiple writers	❌ No

This improves concurrency when reads are frequent.

---

3. Data Structures Used

typedef struct _rwlock_t {
    sem_t lock;        // protects readers count
    sem_t writelock;   // ensures exclusive writing
    int readers;       // number of active readers
} rwlock_t;

Role of Each Component

• lock: A binary semaphore protecting readers

• writelock: Ensures only one writer OR many readers

• readers: Tracks how many readers are inside

---

4. Initializing the Reader–Writer Lock

void rwlock_init(rwlock_t *rw) {
    rw->readers = 0;
    sem_init(&rw->lock, 0, 1);
    sem_init(&rw->writelock, 0, 1);
}

• Both semaphores start at 1

• No readers initially

---

5. Acquiring a Read Lock

void rwlock_acquire_readlock(rwlock_t *rw) {
    sem_wait(&rw->lock);
    rw->readers++;
    if (rw->readers == 1)
        sem_wait(&rw->writelock);
    sem_post(&rw->lock);
}

What Happens Step by Step

1. Reader acquires lock to safely update readers

2. Increments readers

3. First reader locks out writers

4. Releases lock

Key Insight

• The first reader blocks writers

• Additional readers enter freely

---

6. Releasing a Read Lock

void rwlock_release_readlock(rwlock_t *rw) {
    sem_wait(&rw->lock);
    rw->readers--;
    if (rw->readers == 0)
        sem_post(&rw->writelock);
    sem_post(&rw->lock);
}

Explanation

• Reader updates readers safely

• Last reader releases the writer lock

• Writers may now proceed

---

7. Acquiring and Releasing a Write Lock

void rwlock_acquire_writelock(rwlock_t *rw) {
    sem_wait(&rw->writelock);
}

void rwlock_release_writelock(rwlock_t *rw) {
    sem_post(&rw->writelock);
}

Writer Behavior

• Writers acquire writelock

• Blocks all readers and writers

• Ensures exclusive access

---

8. Why This Solution Works

✔ Multiple readers allowed concurrently
✔ Writers get exclusive access
✔ No reader–writer overlap
✔ Correct synchronization using semaphores

---

9. The Fairness Problem (Starvation)

Problem

• Readers can starve writers

• If readers keep arriving, a writer may wait forever

Why This Happens

• New readers are allowed in even when a writer is waiting

Hint for Improvement 

Prevent new readers from entering once a writer is waiting

More advanced implementations introduce:

• Writer-priority locks

• Turnstiles

• Queue-based fairness mechanisms

---

10. Practical Considerations

Reader–writer locks:

• Add extra overhead

• Often slower than simple mutexes

• Best when:

  • Reads dominate writes

  • Critical sections are large

---

11. Key Takeaways for Students ⭐

• Reader–writer locks increase concurrency

• Implemented using semaphores + counters

• Simple solution is not fair

• Use with care in real systems