DikuSTM: A Transactional Memory Library for C++ and C++0x

M.Sc. Thesis by Jesper Alf Dam


As multicore processors become increasingly common, robust concurrent programming techniques are getting increasingly important. Locking mechanisms such as mutexes and monitors are commonly used, but are hard to use correctly, and do little to prevent common error situations such as race conditions, deadlocks and livelocks. Code written using these techniques also prevent programmers from abstracting away the implementation details of their code, as individually thread-safe pieces of code cannot be safely composed into larger thread-safe components.

Software Transactional Memory (STM) is an alternative concurrency model, which uses transactions as the basic synchronization mechanism; any code within a transaction is executed in isolation from other transactions and commits its changes atomically, providing semantics very similar to those known from database management systems.

In this work, strategies for designing and implementing an STM system in C++, and the upcoming language revision informally known as C++0x, are explored. With an emphasis on correctness and simplicity of use, generic programming techniques are used to design an elegant and general interface for library users, preserving compile-time type safety and minimizing the scope for programmer errors, while also avoiding the performance penalty of run-time polymorphism.

We also develop a double-buffered deferred update scheme, eliminating many of the problems typically associated with deferred update systems. As all transactional data is allocated in-place, we also avoid the extensive dynamic allocations and pointer indirections typically associated with indirection-based systems.

The following files are available for download: