Design tradeoffs in modern software transactional memory systems

ABSTRACT

Software Transactional Memory (STM) is a generic non-blocking synchronization construct that enables automatic conversion of correct sequential objects into correct concurrent objects. Because it is nonblocking, STM avoids traditional 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 transactions, in which the set of objects to be modified is not known in advance. We highlight aspects of these systems that lead to performance tradeoffs for various concurrent data structures. More specifically, we consider object ownership acquisition semantics, concurrent object referencing style, the overhead of ordering and bookkeeping, contention management versus helping semantics, and transaction validation. We demonstrate for each system simple benchmarks on which it outperforms the other by a significant margin. This in turn provides us with a preliminary characterization of the applications for which each system is best suited.

REFERENCES

• 1: James H. Anderson , Mark Moir, Universal Constructions for Large Objects, Proceedings of the 9th International Workshop on Distributed Algorithms, p.168-182, September 13-15, 1995
• 2: James H. Anderson , Mark Moir, Universal constructions for multi-object operations, Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, p.184-193, August 20-23, 1995, Ottowa, Ontario, Canada [doi>10.1145/224964.224985]
• 3: Greg Barnes, A method for implementing lock-free shared-data structures, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.261-270, June 30-July 02, 1993, Velen, Germany [doi>10.1145/165231.165265]
• 4: C. Cole and M. P. Herlihy. Snapshots and Software Transactional Memory. In Proceedings of Workshop on Concurrency and Synchronization in Java Programs, 2004.
• 5: K. Fraser. Practical Lock-Freedom. Technical Report UCAM-CL-TR-579, Cambridge University Computer Laboratory, February 2004.
• 6: K. Fraser and T. Harris. Concurrent Programming without Locks. Submitted for publication.
• 7: Tim Harris , Keir Fraser, Language support for lightweight transactions, Proceedings of the 18th annual ACM SIGPLAN conference on Object-oriented programing, systems, languages, and applications, October 26-30, 2003, Anaheim, California, USA
• 8: Maurice Herlihy , Victor Luchangco , Mark Moir, Obstruction-Free Synchronization: Double-Ended Queues as an Example, Proceedings of the 23rd International Conference on Distributed Computing Systems, p.522, May 19-22, 2003
• 9: Maurice Herlihy , Victor Luchangco , Mark Moir , William N. Scherer, III, Software transactional memory for dynamic-sized data structures, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.92-101, July 13-16, 2003, Boston, Massachusetts [doi>10.1145/872035.872048]
• 10: Maurice Herlihy , J. Eliot B. Moss, Transactional memory: architectural support for lock-free data structures, Proceedings of the 20th annual international symposium on Computer architecture, p.289-300, May 16-19, 1993, San Diego, California, United States
• 11: Maurice P. Herlihy , Jeannette M. Wing, Linearizability: a correctness condition for concurrent objects, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.3, p.463-492, July 1990 [doi>10.1145/78969.78972]
• 12: Amos Israeli , Lihu Rappoport, Disjoint-access-parallel implementations of strong shared memory primitives, Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.151-160, August 14-17, 1994, Los Angeles, California, United States [doi>10.1145/197917.198079]
• 13: D. Lea. Concurrency JSR-166 Interest Site. http://gee.cs.oswego.edu/dl/concurrency-interest/.
• 14: V. J. Marathe and M. L. Scott. A Qualitative Survey of Modern Software Transactional Memory Systems. Technical Report TR 839, Department of Computer Science, University of Rochester, June 2004.
• 15: W. N. Scherer III and M. L. Scott. Contention Management in Dynamic Software Transactional Memory. In Proceedings of Workshop on Concurrency and Synchronization in Java Programs, pages 70--79, 2004.
• 16: Nir Shavit , Dan Touitou, Software transactional memory, Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, p.204-213, August 20-23, 1995, Ottowa, Ontario, Canada [doi>10.1145/224964.224987]
• 17: Janice M. Stone , Harold S. Stone , Philip Heidelberger , John Turek, Multiple Reservations and the Oklahoma Update, IEEE Parallel & Distributed Technology: Systems & Technology, v.1 n.4, p.58-71, November 1993 [doi>10.1109/88.260295]
• 18: John Turek , Dennis Shasha , Sundeep Prakash, Locking without blocking: making lock based concurrent data structure algorithms nonblocking, Proceedings of the eleventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.212-222, June 02-05, 1992, San Diego, California, United States [doi>10.1145/137097.137873]