Transaction Safe Nonblocking Data Structures

This paper addresses interoperability of software transactions and ad hoc nonblocking algorithms. Specifically, we explain how to modify arbitrary nonblocking methods so that (1) they can be used both inside and outside transactions, (2) external uses serialize with transactions, and (3) internal uses succeed if, only if, and when the surrounding transaction commits. Interoperability has two important benefits. First, it allows nonblocking methods to play the role of fast, closed nested transactions, with potentially significant performance benefits. Second, it allows programmers to safely mix transactions and nonblocking methods, e.g., to update legacy code, call nonblocking libraries, or atomically compose nonblocking methods. We demonstrate our ideas in the context of the Java-based ASTM system on several lock-free data structures. Our findings are encouraging: Although performance of transaction-safe nonblocking objects does not match that of the original nonblocking objects, the degradation is not unacceptably high (particularly after application of an optimization we call lazy logging). It is, moreover, significantly better than that of analogous transactional objects. We conclude that transaction safe nonblocking objects can be a significant enhancement to software transactional memory