Literature study and example implementations for Reader/Writer Locks

Main reference (actually this one is a takeaway from)
B. Reddy and R. Fields, “Techniques for Reader-Writer Lock Synchronization,” IJEEE, vol. 8, no. 4, pp. 63–73, Dec. 2020, doi: 10.18178/ijeee.8.4.63-73.¹

A second thought: this paper doesn’t seem carefully written… There are many typos and inconsistencies. So I’ll just use this as a primer and do literature research myself.

§ Taxonomy

Centralized Reader-Writer locks

• Preference Reader-Writer Lock: prioritize reader or writer, either unpreferred could starve. Allows for fairness within the preferred side.
• Phase-fair Reader-Writer lock (improv of preference lock)
• Task-Fair Reader-Writer Lock: readers and writers are given the same priority. Access to critical section is FIFO.

  [?] what does FIFO mean when concurrent readers are allowed?

  Worst case: interleaving reader and writer would behave like mutual exclusion instead of Reader/Writer lock
• rw locks with exponential back off
  • fair improvement w/ ticket lock

Queue based Reader-Writer locks

• MCS spin based Reader-Writer locks
• Kreiger et al. MCS improvement
• Hsieh and Weihl improvement
• CLH lock
• blased locking

NUMA aware rw locks (such are also either centralized or queue-based)

• Hierarchical Backoff Lock (HBO)
• HCLH (hierarchical CLH)
• lock cohorting
• augmented general locks

§ impl.

Baseline R/W Lock

R/W Lock in linux kernel