Invalidating Transactions: Optimizations, Theory, Guarantees, and Unification

Transactional memory (TM) is a modern concurrency control paradigm that reduces the difficulty of parallel programming. TM also reduces some unnecessary program serialization by allowing operations from different critical sections, called transactions, to execute concurrently. Although allowing transactions to execute concurrently can increase throughput, care is needed to avoid memory access conflicts between transactions that can lead to incorrect program states. To prevent such incorrect program states, TM systems identify conflicts between transactions before such illegal states become part of the visible program state. To do this, when two or more transactions conflict, the TM stalls or rolls back some number of transactions to ensure the program state remains serializable, the main correctness criterion for TM systems. The process of identifying when transactions conflict is called conflict detection and is a significant source of overhead. To improve the performance of TM, researchers have found optimizations that reduce the cost of conflict detection. However, many of these TMs perform one aspect of conflict detection in the same manner. That is, they perform commit-time validation, where a transaction is analyzed for conflicts with previously committed transactions during its commit phase. While commit-time validation has certain benefits, it also has drawbacks that make it a suboptimal conflict detection strategy for certain environments. In this work we present a conflict detection strategy called full invalidation where the TM resolves all conflicts between a given transaction and all other active transactions before the given transaction commits. Full invalidation has a number of advantages over validation such as improved performance, enforceable execution guarantees, reduced conflict speculation, reduced conflict analysis space and time overhead, and simplified integration of optimistic and pessimistic concurrency control. We analyze full invalidation in the following ways. First, we compare and contrast InvalSTM, a software transactional memory (STM) that implements full invalidation, against TL2, a state-of-the-art STM that uses commit-time validation. Next we present a new theoretical model for TM systems and use the model to prove that histories accepted by a full invalidation system are both conflict and view serializable. We then demonstrate that a full invalidation STM is notably more efficient (by upwards of 100x) than a commit-time validation STM for programs where transactional priority must be respected. Last, we show that a full invalidation STM can reduce the TM implementation complexity and the TM operational overhead when using optimistic (transactions) and pessimistic (locks) critical sections in the same program