Consistency, Isolation, and Irrevocability in Software Transactional Memory
Annette Bieniusa · FreiDok plus (Universitätsbibliothek Freiburg) · 2011
Software transactional memory (STM) is a promising paradigm for the development of concurrent software. It coordinates the potentially conflicting effects of concurrent threads on shared memory by running their critical regions isolated from each other in transactions in an “all-or-nothing” manner. When encountering a conflicting access to shared memory, a conflict resolution strategy decides which transaction has to revert its changes and is restarted. However, this automatic coordination is sometimes too restrictive: non-revertible operations such as I/O operations are disallowed in a transaction and some transactions fail for minor conflicts that could easily be resolved. In addition, most STM schemes focus on shared-memory architectures where costly memory updates impede scalability. This thesis tackles these limitations by exploring extensions to the standard STM schemes. It discusses two novel STM algorithms which broaden the scope for applicability of STM and provide insights into the strength and limitations of transactional programming. Twilight STM proposes to extend STM with non-revertible actions and inconsis- tency repair. It separates a transaction into a functional transactional phase, and an imperative irrevocable phase, which supports a safe embedding of I/O operations as well as a repair facility to resolve minor conflicts. In contrast to other implementations of irrevocable transactions, twilight code may run concurrently with other transactions including their twilight code without data races. Twilight STM further allows the implementation of application-specific conflict resolution strategies. To analyze their influence on the semantics of the transactions, a formal framework for investigating consistency and isolation properties is developed and applied to different repair operations. Decent STM transfers the STM paradigm to a distributed setting. It is a fully decentralized object-based STM algorithm with versioning. It relies on mostly immutable data structures, which are well-suited for replication and migration. A randomized consensus protocol guarantees consistency of shared memory. Transactions may proceed tentatively before consensus has been reached. Object versioning ensures that transactions read from a consistent memory snapshot, and the consensus protocol determines which transactions can merge in their effects and which transactions need to restart. Hence, delayed communication, e.g. caused by retransmissions in the transport layer, can only affect performance, not consistency. Both STM algorithms have been implemented in functional, object-oriented, and imperative languages, on multi-core and distributed architectures. This comprehensive study points out the need for an enhanced STM interface for more flexibility and higher programming convenience. Benchmarks featuring various workloads show the scalability and competitiveness with state-of-the-art systems.