Writer-Preferring Reader-Writer Lock with Mutexes and Condition Variables

The Reader-Writer Problem

Imagine a shared data structure that many threads need to access. If most of these threads only need to read the data, using a single mutex is inefficient. A mutex forces all access to be exclusive, meaning even multiple readers, which don't interfere with each other, are forced to access the data one by one.

The Reader-Writer Lock (RWLock) is a more specialized tool designed for this scenario. It operates on these rules:

1. Multiple "reader" threads can hold the lock and access the data concurrently.
2. Only one "writer" thread can hold the lock at any given time, and it must have exclusive access. No readers or other writers are allowed.

This concept is visualized well in the following sequence diagram. Notice how a 'Parent' thread (writer) must wait until a 'Child' thread (reader) releases its lock before it can proceed.

Writer Preference vs. Reader Preference

When readers and writers are competing for the lock, we need a policy to decide who gets it next.

• Reader Preference: If readers are present, new readers are allowed in, even if a writer is waiting. This can lead to writer starvation if there's a constant stream of readers.
• Writer Preference: If a writer is waiting, no new readers are allowed to acquire the lock. Existing readers are allowed to finish, and then the writer gets priority. This policy is often chosen to ensure that updates are processed in a timely manner, though it can starve readers in write-heavy scenarios.

Our goal today is to implement an RWLock with writer preference.

Building Blocks for Our Writer-Preference RWLock

To build our custom lock, we'll need a few components:

• A state structure to track the lock's status.
• One mutex to protect this state structure. All logic will operate inside this mutex's critical section.
• Two condition variables: one for waiting readers to block on, and another for waiting writers.

The state we need to track is:

• active_readers: The number of threads currently holding a read lock.
• active_writers: The number of threads currently holding a write lock (will only ever be 0 or 1).
• waiting_writers: The number of threads waiting to acquire a write lock. This is the crucial variable for implementing writer preference.

Let's organize this into a struct:

typedef struct {
    // State variables
    int active_readers;
    int active_writers;
    int waiting_writers;

    // Primitives
    pthread_mutex_t mutex;
    pthread_cond_t readers_cond;
    pthread_cond_t writers_cond;
} rwlock_t;

Deconstructing the Logic

We will now design the four core functions for our lock: read_lock, read_unlock, write_lock, and write_unlock. We will analyze the logic for each before studying a complete implementation.

write_lock() — Acquiring a Write Lock

1. Lock the central mutex to access the state variables.
2. Increment waiting_writers to signal your intent to write. This acts as a reservation, preventing new readers from jumping ahead.
3. Enter a while loop and wait as long as the resource is occupied: while (active_readers > 0 || active_writers > 0). The thread calls pthread_cond_wait(&writers_cond, &mutex), putting it to sleep until it is signaled.
4. Once woken up and the condition is false, the thread can proceed. It decrements waiting_writers and increments active_writers to 1.
5. Unlock the central mutex. The writer now has exclusive access.

read_lock() — Acquiring a Read Lock

1. Lock the central mutex.
2. Enter a while loop and wait if any writers are active OR waiting: while (active_writers > 0 || waiting_writers > 0). This is the core of the writer-preference policy. A waiting writer prevents new readers from acquiring the lock.
3. Once the condition is false, the thread can proceed. It increments active_readers.
4. Unlock the central mutex. The reader now shares access with other readers.

write_unlock() — Releasing a Write Lock

1. Lock the central mutex.
2. Decrement active_writers to 0.
3. Now, who to wake up? We must decide based on our policy.
   • Check if there are any waiting_writers. If so, signal one of them with pthread_cond_signal(&writers_cond). This maintains writer priority.
   • If there are no waiting writers, wake up all waiting readers with pthread_cond_broadcast(&readers_cond). We use broadcast because all of them can proceed concurrently.
4. Unlock the central mutex.

read_unlock() — Releasing a Read Lock

1. Lock the central mutex.
2. Decrement active_readers.
3. Check if you were the last reader: if (active_readers == 0).
4. If so, and if there's a writer waiting, you must signal it. A simple pthread_cond_signal(&writers_cond) will wake up one of the waiting writers.
5. Unlock the central mutex.

Studying a Complete Implementation

The logic we've just designed is complex, and seeing it in action is the best way to solidify your understanding. The following resource provides a full, annotated C program that implements the reader-writer problem with both reader and writer preference.

After studying the code, you should see a direct mapping between our four logical functions (read_lock, read_unlock, etc.) and the "ACQUIRE" and "RELEASE" sections within the reader and writer thread functions in the example. The example code integrates the "do work" part between the acquire and release logic, but the synchronization principles are identical.

You will also notice the use of assert() statements. In your own code, this is a powerful technique to verify that your state machine is behaving as expected. For instance, assert(writer_count == 0) in the reader's critical section is a great sanity check.

Conclusion

In this lesson, you've learned how to design and implement a sophisticated, custom synchronization primitive from scratch. Building a writer-preference reader-writer lock is a significant step up from using basic mutexes and demonstrates a deep understanding of stateful concurrency control with condition variables.

Key Takeaways:

• Reader-writer locks optimize for scenarios with frequent reads and infrequent writes by allowing concurrent readers.
• Implementing a "writer preference" policy requires an explicit waiting_writers counter. This counter is checked by incoming readers, forcing them to wait if a writer has already declared an intent to write.
• The logic is implemented using one mutex to guard the state and two condition variables to manage separate queues of waiting readers and writers.
• The choice between pthread_cond_signal and pthread_cond_broadcast is critical:
  • broadcast is used to release all waiting readers, as they can proceed in parallel.
  • signal is used to release a single writer, as only one can be active.

Preview of the Next Lesson:
We've just seen how complex interactions between threads can be carefully managed. However, sometimes interactions between threads and the OS scheduler can cause unexpected problems. In our next lesson, we will explore one such problem: Explain the concept of priority inversion and how priority inheritance can solve it. This will delve into how thread priorities and locks can combine to create subtle but serious performance issues.