Computer Laboratory Home Page Search A-Z Directory Help
University of Cambridge Home Computer Laboratory
January 30th 2003
Computer Laboratory > Research > Systems Research Group > NetOS > Seminars > January 30th 2003

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.