M.Sc. Thesis by Kasper Egdų
An increasing number of cores (or CPUs) per computer is creating a need for good programming tools for exploiting these cores. Locks are traditionally used but issues with deadlocks and race conditions easily arise and choosing the correct granularity for locking is often not trivial. In addition, the use of locks does not generally enable the programmer to compose existing correct lock-based program pieces into a new larger correct lock-based piece.
An alternative to locks is Software Transactional Memory (STM) which is a concurrency approach that does not use locks as its primary method. Instead STM is an optimistic concurrency control mechanism; using memory transactions similar to transactions used in database systems. Programs built with STM avoid deadlocks and race conditions and enables composition of program pieces from existing pieces.
This work explores design criteria for building a STM system for C++ and for building Standard Template Library containers on top of such a system. We emphasize correctness over performance, generic programming and direct reuse of existing algorithms and data types with our implementation. Using an indirection-based approach for our STM implementation enables us to guarantee strong exception safety for all operations on our data structures. We also develop a new method for nesting STM-based data structures within each other, such that we avoid unnecessary conflicts and copying.
Using compile-time polymorphism we develop a new method for laying out shared data in memory, thereby allowing us to reduce the number of cache misses that are otherwise the primary disadvantage of indirection-based STM implementations. For large datasets with low contention the throughput in our benchmarks is increased by up to 33 percent when using our layout technique.
The following files are available for download: