Practical Lock-Free Programming using Software Transactional Memory
Keir Fraser
Lock-free data structures promise to aid concurrent programming by
sidestepping many of the well-known problems associated with mutual
exclusion including deadlock, overzealous synchronisation, and lack of
fault tolerance. Unfortunately the reality is that most lock-free
algorithms are hard to understand, and inefficient or impossible to
execute on current hardware.
Software Transactional Memory (STM) is a convenient programming
abstraction which provides strongly-consistent transactional semantics
for reads and writes to shared memory. In this talk I present an
efficient lock-free STM design which is suitable for deployment on any
modern multiprocessing architecture. I also introduce an STM-based
red-black tree design which is both simpler and more efficient than
state-of-the-art algorithms based on reader-writer locks.
|