pthread RWLock and Reader-Writer Synchronization¶

Overview¶

Reader-writer lock (rwlock) is a synchronization primitive that allows:

multiple concurrent readers
one exclusive writer

Compared with a normal mutex:

mutex allows only one owner
rwlock separates synchronization into reader phase and writer phase

This improves read-side concurrency for read-heavy workloads.

Reader-Writer Synchronization Model¶

Reader Phase¶

Multiple readers may enter the critical section simultaneously.

Example:

reader A -> acquired
reader B -> acquired
reader C -> acquired

All readers may safely execute concurrently.

Writer Phase¶

Writer requires exclusive ownership.

Rules:

no readers allowed
no other writers allowed

Example:

writer -> acquired

Only one writer may enter the critical section.

Basic RWLock Semantics¶

Access Type	Allowed
reader + reader	Yes
reader + writer	No
writer + writer	No

Why RWLock Is More Complicated Than Mutex¶

Mutex only manages:

locked / unlocked

RWLock must additionally manage:

reader count
writer ownership
waiting writers
fairness policy
reader/writer phase transition

The real difficulty is not reader counting itself.

The real challenge is:

ownership transition correctness

especially:

reader phase ↔ writer phase transition

Reader-Writer Phase Transition¶

RWLock internally behaves like a synchronization state machine.

Example states:

reader phase
writer waiting
writer phase

Incorrect state transition may allow:

reader and writer simultaneously entering critical section

which breaks synchronization correctness.

Mini RWLock Design¶

A simplified rwlock may use:

struct mini_rwlock {
    atomic_int reader_count;
    atomic_int writer;
};

Writer State Machine¶

Example writer states:

WRITER_FREE
WRITER_WAIT_QUEUE
WRITER_ACQUIRED

Meaning:

State	Description
WRITER_FREE	no writer
WRITER_WAIT_QUEUE	writer waiting
WRITER_ACQUIRED	writer owns lock

Reader Acquire Flow¶

Simplified reader flow:

wait until writer policy allows acquire
reader_count++
re-check writer state
rollback if writer acquired concurrently

Reader Re-check Mechanism¶

Very important correctness logic:

reader_count++
re-check writer state
rollback if needed

Without re-check:

reader sees writer free
<context switch>
writer acquires ownership
<context switch>
reader increments reader_count

Result:

reader and writer simultaneously enter critical section

The rollback mechanism prevents this race.

Writer Acquire Flow¶

Simplified writer flow:

CAS(writer: FREE -> WAIT_QUEUE)
wait until reader_count == 0
writer becomes ACQUIRED

The writer must wait until all readers leave the critical section.

CAS-Based Ownership Claim¶

Writer ownership acquisition typically requires:

atomic_compare_exchange_xxx()

because:

check + ownership claim must be atomic

Simple load/store is not sufficient in concurrent environments.

Busy Spin RWLock¶

The simplified implementation used:

sched_yield()

for waiting.

This creates:

busy spinning
scheduler overhead
high CPU usage

Example:

while (condition)
    sched_yield();

This style is commonly called:

spin rwlock

Sleeping RWLock¶

Production rwlocks usually avoid busy spinning.

Typical design:

uncontended fast path handled in userspace
contention path enters kernel sleep queue

Linux userspace synchronization commonly uses:

futex

for sleep/wakeup operations.

Futex Slow Path¶

Observed using:

strace -f -e futex ./rwlock_demo

Observed operations:

FUTEX_WAIT
FUTEX_WAKE
EAGAIN retry behavior

This confirms:

rwlock fast path operates in userspace
rwlock slow path uses futex wait/wake

Memory Ordering¶

Synchronization correctness also depends on memory visibility.

Important concepts:

Operation	Ordering
lock acquire	acquire
unlock	release

Common ordering types:

memory_order_acquire
memory_order_release

Acquire Ordering¶

Acquire ordering prevents later memory accesses from moving before lock acquisition.

Used when entering critical section.

Release Ordering¶

Release ordering ensures protected writes become visible before unlock.

Used when leaving critical section.

RWLock Scalability Problems¶

RWLock improves read concurrency, but also introduces scalability problems.

Examples:

fairness tradeoff
writer starvation
busy spinning
cacheline contention

Especially:

reader_count

may become highly contended under heavy read workloads.

Motivation for Advanced Synchronization¶

RWLock limitations motivated more advanced synchronization mechanisms:

seqlock
RCU
lock-free synchronization

These mechanisms improve scalability for read-heavy systems.

Summary¶

RWLock is fundamentally a synchronization state machine.

The real complexity comes from:

ownership transition
fairness policy
reader/writer coordination
synchronization correctness

not simply maintaining a reader counter.

Understanding rwlock internals forms the foundation for learning:

futex-based synchronization
seqlock
RCU
lock-free data structures