Lock-free algorithms

From dankwiki
Revision as of 07:47, 29 January 2010 by Dank (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Herlihy, Luchangco and Moir's 2003 paper, "Obstruction-Free Synchronization: Double-Ended Queues as an Example" pretty much revolutionized the field and is mandatory reading. Techniques like speculative lock elision (SLE) can abrogate much of the cost of uncontested locks, and threading implementations like NPTL handle uncontested mutexes entirely in userspace.


  • lock-free - guaranteed system-wide progress
  • wait-free - guaranteed per-thread progress

Architectural Primitives

See Also