Implement Reader-Writer Lock from Scratch

Topic Overview

Many Readers, One Writer

Reader-writer locks optimize read-heavy workloads: concurrent readers proceed in parallel, writers take exclusive access. The lock must track active reader count and block writers until readers drain.

State Machine

Common implementation fields:

• reader_count guarded by an internal mutex
• writer_waiting flag to prevent writer starvation
• write_locked boolean for exclusive phase

For example, with 8 threads parsing a config file, all 8 may hold the read lock simultaneously; a writer updating the file waits until reader_count drops to 0.

Why This Matters in Production

POSIX's pthread_rwlock_t and Java's ReentrantReadWriteLock exist because read-mostly workloads like configuration caches and in-memory databases waste enormous throughput serializing readers behind a plain mutex. The writer-starvation problem you're asked to prevent here is a real, documented pitfall: naive Linux glibc rwlock implementations historically favored readers so heavily that writers could starve indefinitely under sustained read load.

Debugging Checklist

Before you call the implementation done, walk failure modes on purpose. Test empty structures, single-element edge cases, maximum concurrency, and errno paths that must not crash the program. OS code usually fails in production when happy-path tests pass but invariants break under contention or memory pressure.

Implementation Notes

Keep structures small and name fields after kernel counterparts when possible. That lets you read man pages and kernel source side by side while you work. Print observable events during development; remove noisy logs once tests pass reliably.

For This Exercise

You will build rwlock_rdlock, rwlock_wrlock, and unlock paths from pthread-style primitives or your mutex. This exercise requires a test where readers overlap and a writer serializes updates without data races.

Your Task

Implement a reader-writer lock: many readers at once, or one writer alone. The interesting part is the policy for choosing who goes next when both kinds are waiting. Reader preference can starve writers, writer preference can starve readers, and a FIFO policy trades throughput for fairness. Drive the lock with an explicit sequence of operations and show every grant.

Input

cCopy
Loading…

Rules

Immediate grant (for a new request):

Otherwise the thread joins the FIFO queue, and a try-operation returns EBUSY instead.

On release (a wunlock, or the last runlock), hand the lock over:

• fair: if the head of the queue is a writer, grant it. Otherwise grant the run of consecutive readers at the head.
• writer: if any writer waits, grant the first one. Otherwise grant every waiting reader.
• reader: if any reader waits, grant every waiting reader. Otherwise grant the first writer.

Errors:

• Requesting while already holding or waiting: EDEADLK (already reading|writing|waiting).
• A reader asking for the write lock: EDEADLK (upgrading a read lock is not supported).
• Unlocking what you do not hold: EPERM (not reading|writing).
• policy: lock in use.
• : unknown operation.

Output

cCopy
Loading…

The policy names are reader-preferring, writer-preferring and fair (FIFO). A release that grants nothing prints just the release line. state lists readers in order of first appearance. The last line is always the maximum number of concurrent readers.

Example

Input:

cCopy
Loading…

Output:

cCopy
Loading…

Requirements

1. Keep a reader count, the writer (if any), and one FIFO of waiters tagged r or w. The three policies differ only in the grant tests and the hand-over rule.
2. Grant readers in batches. When readers are chosen, every eligible waiting reader gets in at once.

Hidden tests cover writer starvation under the reader policy, reader starvation under the writer policy, alternating batches under the fair policy, try-operations, upgrade attempts, double requests, unlocking without holding, and changing the policy while the lock is in use.