The motivation and implementation of reader-writer semaphore.

Contents:

• Motivation
  • The Reader-Writer Problem
  • Why Semaphore?
• Algorithm
  • Down Read
  • Down Write
  • Up Read
  • Up Write
  • Atomicity Requirement
• Implementations
  • Linux

Motivation

The Reader-Writer Semaphore is a semaphore mechanism to resolve the reader-writer problem. We will discuss the basic of the reader-writer problem in _ and the semaphore mechanism in _.

The Reader-Writer Problem

The reader-writer problem is a common problem in computer science. Given multiple concurrent processes using shared data, how to ensure that

1. the newer readers read the latest update;
2. the updates are atomic.

One relaxation is the general locking, which allows only one process to access (read or write) the data. In the reader-writer problem, we should allow multiple readers to read concurrently for efficiency.

Therefore, the basic idea is that:

1. If a reader or writer has no competitors, it proceeds.
2. If a reader finds other concurrent readers, it proceeds because there is no writer.
3. If a reader finds another writer, it waits.
4. If a writer finds another reader or writer, it waits.

The algorithm and implementation detail vary significantly under different specifications. Semaphore is the mechanism we will focus on in this article.

Why Semaphore?

Semaphore is a locking mechanism. The basic idea is to maintain a wait queue and wake up the sleeping tasks when it is ready to serve.

Another locking mechanism is spinlock, which actively queries the status of the lock and never sleeps. Comparatively, semaphore saves more computation resources because the CPU can serve other tasks when waiting for the lock, while it may suffer from higher latency.

Semaphore also maintains a count value. Down() decrements the count and if the new count is non-negative, the task acquires the lock. Up() increments the count and releases the lock.

When the count = 1, this special type of semaphore is called Mutex to enforce mutual exclusion.

• Good for long tasks.
• Only in process context. Not available in interrupt context.
• OK if sleep when holding the lock.
• Cannot acquire a semaphore when holding a spinlock because spinlock does not allow sleep.

Algorithm

• Assumption: Read operations are more frequent than write operations.
• Concurrent readers are allowed and encouraged.

The data structure it maintains:

• A waitlist and its lock.
• Held by a writer?
• Held by readers? And the number of readers.
• Number of waiters.

Down Read

• If the lock is free, hold it.
• If the task was woken up from the wait queue, wake up other readers as well.
• If the lock is busy, put itself in the wait queue to avoid writer starvation.

Down Write

• If the lock is free, hold it.
• If the task was woken up from the wait queue, hold the lock.
• If the lock is busy, put itself in the wait queue.

Up Read

• If there are other readers, update the reader count.
• If there is no more reader, wake up the next task in the wait queue.

Up Write

• Wake up the next task in the wait queue.

Atomicity Requirement

The metadata of the semaphore should be read and updated atomically. One choice is to use a spinlock to protect it. Another choice is to encode the metadata into a word and use atomic instructions like compare and swap.

Implementations

Linux

In Linux, the metadata of a reader-writer semaphore is encoded as a count field so that it allows the lightweight atomic operations to maintain the semaphore’s state. On a 64-bit architecture, the count is encoded as the following:

 * Bit  0    - writer locked bit
 * Bit  1    - waiters present bit
 * Bit  2    - lock handoff bit
 * Bits 3-7  - reserved
 * Bits 8-62 - 55-bit reader count
 * Bit  63   - read fail bit

It is relatively complex and you may refer to the following links:

• Source code
• Explanation from Linux Insider