Skip to content

Day 62 - pthread RWLock Internals and Fairness

Overview

This lab explores how pthread_rwlock works internally and why reader-writer synchronization is more complicated than a normal mutex.

Topics covered:

  • multiple-reader concurrency
  • writer exclusivity
  • rwlock fairness policy
  • writer starvation
  • futex slow path
  • mini spin rwlock implementation
  • acquire/release memory ordering

Learning Objectives

  • Understand reader-writer synchronization semantics
  • Observe multiple concurrent readers
  • Observe writer exclusivity
  • Compare reader-preference vs writer-preference
  • Observe writer starvation behavior
  • Implement a simplified rwlock using atomics
  • Understand rwlock ownership transition
  • Observe futex wait/wake behavior

Lab1 - Multi-reader Parallelism

Goal

Verify that multiple readers may enter the critical section concurrently.

Test Design

  • create multiple reader threads
  • each reader acquires read lock
  • each reader sleeps inside critical section
  • observe concurrent access

Expected Result

Multiple readers should acquire the lock simultaneously.

Example:

[READER-1] acquired
[READER-2] acquired
[READER-3] acquired

Lab2 - Writer Waiting Behavior

Goal

Observe writer blocking behavior while readers hold the lock.

Test Design

  • readers continuously acquire/release read lock
  • writer attempts write lock acquisition
  • observe whether writer waits

Expected Result

Writer cannot enter until all readers leave the critical section.

Example:

[WRITER] waiting
...
[READER-x] unlocked
...
[WRITER] acquired

Lab3 - Reader Preference and Writer Starvation

Goal

Observe starvation tendency caused by reader-preference policy.

Reader Preference Policy

Readers may still acquire lock while writer is waiting.

Example policy:

#define READER_ACQUIRE_POLICY WRITER_WAIT_QUEUE

Meaning:

Writer State Reader Allowed
WRITER_FREE Yes
WRITER_WAIT_QUEUE Yes
WRITER_ACQUIRED No

Observation

Writer wait time may become extremely long because:

reader_count may never become zero

Observed writer wait time exceeded 40 seconds during testing.

Lab4 - Writer Preference Policy

Goal

Compare writer-preference behavior against reader-preference.

Writer Preference Policy

New readers blocked once writer enters waiting state.

Example policy:

#define READER_ACQUIRE_POLICY WRITER_FREE

Meaning:

Writer State Reader Allowed
WRITER_FREE Yes
WRITER_WAIT_QUEUE No
WRITER_ACQUIRED No

Observation

Writer acquires lock much faster because new readers are blocked.

Tradeoff:

  • lower writer latency
  • lower reader throughput

Lab5 - Mini Spin RWLock Implementation

Goal

Implement a simplified rwlock using atomic operations.

Writer State Machine

Implemented writer states:

WRITER_FREE
WRITER_WAIT_QUEUE
WRITER_ACQUIRED

Core Structure

struct mini_rwlock {
    atomic_int reader_count;
    atomic_int writer;
};

Reader Acquire Flow

Reader flow:

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

Writer Acquire Flow

Writer flow:

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

Reader Rollback Mechanism

Important correctness logic:

reader_count++
re-check writer state
rollback if needed

This prevents:

reader and writer simultaneously entering critical section

Busy Spin Limitation

Current implementation uses:

sched_yield()

for waiting.

This creates:

  • busy spinning
  • scheduler overhead
  • high CPU usage

This motivates futex-based sleeping synchronization.

Lab6 - Futex Trace Observation

Goal

Observe rwlock slow path using futex system calls.

Command

strace -f -e futex ./rwlock_demo

Observed Behavior

Observed:

  • FUTEX_WAIT
  • FUTEX_WAKE
  • EAGAIN retry behavior

This confirms:

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

Memory Ordering Discussion

Started exploring:

  • memory_order_acquire
  • memory_order_release

Important concepts:

Operation Ordering
lock acquire acquire
unlock release

Understanding memory visibility is critical for synchronization correctness.

Summary

This lab demonstrated:

  • reader-writer synchronization semantics
  • rwlock fairness policy
  • writer starvation behavior
  • rwlock ownership transition
  • CAS-based synchronization
  • busy-spin limitations
  • futex slow path behavior

The mini rwlock implementation provided practical understanding of:

  • synchronization state machines
  • fairness tradeoffs
  • concurrent ownership transition
  • memory ordering concepts

This forms the foundation for understanding more advanced synchronization mechanisms such as:

  • seqlock
  • RCU
  • futex-based rwlock
  • lock-free synchronization