Design Tradeos in Modern Software Transactional Memory Systems

Software Transactional Memory (STM) is a generic non-blocking synchronization construct that enables automatic conversion of correct sequential objects into correct concur-rent objects. Because it is nonblocking, STM avoids tradi-tional performance and correctness problems due to thread failure, preemption, page faults, and priority inversion. In this paper we compare and analyze two recent object-based STM systems, the DSTM of Herlihy et al. and the FSTM of Fraser, both of which support dynamic transac-tions, in which the set of objects to be modied is not known in advance. We highlight aspects of these systems that lead to performance tradeos for various concurrent data structures. More specically, we consider object own-ership acquisition semantics, concurrent object referencing style, the overhead of ordering and bookkeeping, contention management versus helping semantics, and transaction vali-dation. We demonstrate for each system simple benchmarks on which it outperforms the other by a signicant margin. This in turn provides us with a preliminary characterization of the applications for which each system is best suited. 1