Skip to content

Reader-Writer Lock Fairness and Starvation

Overview

Reader-writer lock fairness policy directly affects:

  • reader throughput
  • writer latency
  • starvation behavior
  • synchronization scalability

The most important fairness question is:

Should new readers be allowed while a writer is waiting?

Different answers create different rwlock policies.

Reader Preference

Concept

Reader-preference rwlock allows new readers to acquire lock even when a writer is already waiting.

Example:

reader -> acquired
writer -> waiting
new reader -> acquired

Reader Preference Policy Example

Example condition:

#define READER_ACQUIRE_POLICY WRITER_WAIT_QUEUE

Meaning:

Writer State Reader Allowed
WRITER_FREE Yes
WRITER_WAIT_QUEUE Yes
WRITER_ACQUIRED No

Advantages of Reader Preference

Benefits:

  • high reader throughput
  • high read-side concurrency
  • low reader latency

Useful for:

  • read-heavy workloads
  • frequently accessed shared data
  • cache lookup systems

Disadvantages of Reader Preference

Main problem:

writer starvation

Because:

reader_count may never become zero

Writer may wait for very long time.

Observed behavior:

writer waits while readers continuously re-enter

Writer Starvation

Starvation Definition

Starvation means:

a thread may wait indefinitely
without making progress

In reader-preference rwlock:

  • readers continuously acquire lock
  • writer cannot obtain exclusive ownership

Observed Starvation Behavior

Experimental observation:

writer wait time exceeded 40 seconds

while readers continuously acquired and released read lock.

This demonstrates classic rwlock starvation tendency.

Writer Preference

Concept

Writer-preference rwlock blocks new readers once a writer begins waiting.

Example:

reader -> acquired
writer -> waiting
new reader -> blocked

Writer Preference Policy Example

Example condition:

#define READER_ACQUIRE_POLICY WRITER_FREE

Meaning:

Writer State Reader Allowed
WRITER_FREE Yes
WRITER_WAIT_QUEUE No
WRITER_ACQUIRED No

Advantages of Writer Preference

Benefits:

  • lower writer latency
  • reduced starvation risk
  • more predictable writer progress

Useful for:

  • write-sensitive systems
  • latency-sensitive updates
  • systems requiring stronger fairness

Disadvantages of Writer Preference

Main tradeoff:

reduced reader throughput

Because:

  • readers blocked earlier
  • read concurrency reduced
  • more synchronization stalls

Fairness Tradeoff

RWLock fairness always involves tradeoffs.

Policy Reader Throughput Writer Latency Starvation Risk
Reader Preference High High High
Writer Preference Lower Lower Lower

There is no perfect policy.

The correct design depends on workload characteristics.

RWLock Fairness Is a Policy Decision

The most important observation:

Whether waiting writers block new readers
defines rwlock fairness policy.

This single design decision heavily affects:

  • scalability
  • throughput
  • latency
  • starvation behavior

Busy Spinning and Fairness

Simplified spin rwlocks commonly use:

sched_yield()

for waiting.

Problems:

  • busy spinning
  • scheduler overhead
  • CPU waste

Fairness problems become more visible under heavy contention.

Cacheline Contention

RWLocks also introduce shared-state contention.

Example:

reader_count

All readers continuously modify the same atomic counter.

This creates:

  • cacheline bouncing
  • inter-core synchronization traffic
  • scalability bottlenecks

Especially problematic on multi-core systems.

Why RWLock Design Is Difficult

RWLock complexity comes from:

  • reader/writer coordination
  • ownership transition
  • fairness policy
  • starvation prevention
  • scalability tradeoffs

The problem is much more complicated than simple locking.

Motivation for Advanced Synchronization

RWLock limitations motivated more scalable synchronization mechanisms.

Examples:

  • seqlock
  • RCU
  • lock-free synchronization

These mechanisms reduce:

  • reader overhead
  • cacheline contention
  • fairness bottlenecks

especially for read-heavy workloads.

Reader Preference vs Writer Preference Summary

Reader Preference

higher reader throughput
possible writer starvation

Writer Preference

better writer progress
lower reader concurrency

Summary

RWLock fairness policy is one of the most important synchronization design decisions.

The core tradeoff is:

reader throughput
vs
writer latency

Understanding fairness and starvation behavior is essential for designing scalable synchronization systems.