Maurice Herlihy
Victor Luchangco
ABSTRACT
We propose a new form of software transactional memory (STM) designed to support dynamic-sized data structures, and we describe a novel non-blocking implementation. The non-blocking property we consider is obstruction-freedom. Obstruction-freedom is weaker than lock-freedom; as a result, it admits substantially simpler and more efficient implementations. A novel feature of our obstruction-free STM implementation is its use of modular contention managers to ensure progress in practice. We illustrate the utility of our dynamic STM with a straightforward implementation of an obstruction-free red-black tree, thereby demonstrating a sophisticated non-blocking dynamic data structure that would be difficult to implement by other means. We also present the results of simple preliminary performance experiments that demonstrate that an "early release" feature of our STM is useful for reducing contention, and that our STM lends itself to the effective use of modular contention managers.
- Java Specification Request for Concurrent Utilities (JSR166). http://jcp.org.Google Scholar
- Sun Microsystems Laboratories Scalable Synchronization Research Group publications page. http://research.sun.com/scalable/pubs.Google Scholar
- Y. Afek, D. Dauber, and D. Touitou. Wait-free made fast. In Proceedings of the 27th Annual ACM Symposium on Theory of Computing, pages 538--547, 1995. Google ScholarDigital Library
- G. Barnes. A method for implementing lock-free shared data structures. In Proceedings of the Fifth Annual ACM Symposium on Parallel Algorithms and Architectures, pages 261--270, 1993. Google ScholarDigital Library
- R. Bayer and M. Schkolnick. Concurrency of operations on B-trees. Acta Informatica, 9:1--21, 1977.Google ScholarDigital Library
- T. H. Cormen, C. E. Leiserson, and R. L. Rivest. Introduction to Algorithms. McGraw-Hill, 1990. Google ScholarDigital Library
- M. Herlihy, V. Luchangco, and M. Moir. Obstruction-free synchronization: Double-ended queues as an example. In Proceedings of the 23rd International Conference on Distributed Computing Systems, 2003. Google ScholarDigital Library
- M. Herlihy and J. Moss. Transactional memory: Architectural support for lock-free data structures. In Proceedings of the 20th International Symposium in Computer Architecture, pages 289--300, 1993. Google ScholarDigital Library
- M. Herlihy and J. Wing. Linearizability: A correctness condition for concurrent objects. ACM Transactions on Programming Languages and Systems, 12(3):463--492, 1990. Google ScholarDigital Library
- A. Israeli and L. Rappoport. Disjoint-access-parallel implementations of strong shared memory primitives. In Proceedings of the 13th Annual ACM Symposium on Principles of Distributed Computing, pages 151--160, 1994. Google ScholarDigital Library
- V. Luchangco, M. Moir, and N. Shavit. Nonblocking k-compare-single-swap. In Proceedings of the 15th Annual ACM Sympoium on Parallel Architecures and Algorithms, 2003. Google ScholarDigital Library
- M. Michael and M. Scott. Nonblocking algorithms and preemption-safe locking on multiprogrammed shared memory multiprocessors. Journal of Parallel and Distributed Computing, 51(1):1--26, 1998. Google ScholarDigital Library
- M. Moir. Transparent support for wait-free transactions. In Proceedings of the 11th International Workshop on Distributed Algorithms, pages 305--319, 1997. Google ScholarDigital Library
- N. Shavit and D. Touitou. Software transactional memory. Distributed Computing, Special Issue(10):99--116, 1997.Google Scholar
- J. Turek, D. Shasha, and S. Prakash. Locking without blocking: making lock based concurrent data structure algorithms nonblocking. In Proceedings of the eleventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, pages 212--222, 1992. Google ScholarDigital Library
Index Terms
- Software transactional memory for dynamic-sized data structures
Recommendations
Time-Based Software Transactional Memory
Software transactional memory (STM) is a concurrency control mechanism that is widely considered to be easier to use by programmers than other mechanisms such as locking. The first generations of STMs have either relied on visible read designs, which ...
An efficient software transactional memory using commit-time invalidation
CGO '10: Proceedings of the 8th annual IEEE/ACM international symposium on Code generation and optimizationTo improve the performance of transactional memory (TM), researchers have found many eager and lazy optimizations for conflict detection, the process of determining if transactions can commit. Despite these optimizations, nearly all TMs perform one ...
Open nesting in software transactional memory
PPoPP '07: Proceedings of the 12th ACM SIGPLAN symposium on Principles and practice of parallel programmingTransactional memory (TM) promises to simplify concurrent programming while providing scalability competitive to fine-grained locking. Language-based constructs allow programmers to denote atomic regions declaratively and to rely on the underlying ...
Comments