Tim Harris
Simon Marlow
Simon Peyton-Jones
Maurice Herlihy
ABSTRACT
Writing concurrent programs is notoriously difficult, and is of increasing practical importance. A particular source of concern is that even correctly-implemented concurrency abstractions cannot be composed together to form larger abstractions. In this paper we present a new concurrency model, based on transactional memory, that offers far richer composition. All the usual benefits of transactional memory are present (e.g. freedom from deadlock), but in addition we describe new modular forms of blocking and choice that have been inaccessible in earlier work.
- Benton, N., Cardelli, L., and Fournet, C. Modern concurrency abstractions for C#. In Proceedings of European Conference on Object-Oriented Programming (June 2002), vol. 2374 of Lecture Notes in Computer Science, pp. 415--425. Google Scholar
Digital Library
- Clarke, D. G., Potter, J. M., and Noble, J. Ownership types for flexible alias protection. In OOPSLA '98: Proceedings of the 13th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications (1998), pp. 48--64. Google ScholarDigital Library
- Daume III, H. Yet Another Haskell Tutorial. 2004. Available at http://www.isi.edu/~hdaume/htut/ or via http://www.haskell.org/.Google Scholar
- Ennals, R. Feris: a functional environment for retargetable interactive systems. Batchelors thesis, University of Cambridge Computer Laboratory, 2000.Google Scholar
- Flatt, M., and Findler, R. B. Kill-safe synchronization abstractions. In PLDI '04: Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation (2004), pp. 47--58. Google ScholarDigital Library
- Fraser, K. Practical lock-freedom. PhD thesis, University of Cambridge Computer Laboratory, Feb. 2004. Also published as UCAM-CL-TR-579.Google Scholar
- Gray, J., and Reuter, A. Transaction Processing: Concepts and Techniques. Morgan Kaufmann Publishers Inc., 1992. Google ScholarDigital Library
- Hammond, L., Carlstrom, B. D., Wong, V., Hertzberg, B., Chen, M., Kozyrakis, C., and Olukotun, K. Programming with transactional coherence and consistency (TCC). In Proceedings of the 11th international conference on Architectural support for programming languages and operating systems (2004), pp. 1--13. Google ScholarDigital Library
- Harris, T., and Fraser, K. Language support for lightweight transactions. In Proc ACM SIGPLAN conference on Object-oriented programing, systems, languages, and applications (OOPSLA) (2003), pp. 388--402. Google ScholarDigital Library
- Herlihy, M., Luchangco, V., Moir, M., and Scherer, III, W. N. Software transactional memory for dynamic-sized data structures. In Proceedings of the twenty-second annual symposium on Principles of distributed computing (2003), pp. 92--101. Google ScholarDigital Library
- Herlihy, M., and Moss, J. E. B. Transactional memory: architectural support for lock-free data structures. In Proceedings of the 20th annual international symposium on Computer architecture (1993), pp. 289--300. Google ScholarDigital Library
- Israeli, A., and Rappoport, L. Disjoint-access-parallel implementations of strong shared memory primitives. In Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing (1994), pp. 151--160. Google ScholarDigital Library
- Jordan, M., and Atkinson, M. Orthogonal persistence for Java --- a mid-term report. In Proceedings of the 3rd International Workshop on Persistence and Java (Sept. 1998), pp. 335--352. Google ScholarDigital Library
- Kelsey, R., Rees, J., and Sperber, M. The incomplete scheme 48 reference manual for release 1.1. July 2004.Google Scholar
- Lamb, C., Landis, G., Orenstein, J., and Weinreb, D. The ObjectStore database system. Commun. ACM 34, 10 (1991), 50--63. Google ScholarDigital Library
- Liskov, B. Distributed programming in Argus. Commun. ACM 31, 3 (1988), 300--312. Google ScholarDigital Library
- Marlow, S., Peyton-Jones, S., Moran, A., and Reppy, J. Asynchronous exceptions in Haskell. In ACM Conference on Programming Languages Design and Implementation (PLDI'01), ACM, pp. 274--285. Google ScholarDigital Library
- Martinez, J. F., and Torrellas, J. Speculative synchronization: applying thread-level speculation to explicitly parallel applications. In Proceedings of the 10th international conference on architectural support for programming languages and operating systems (ASPLOS-X) (2002), pp. 18--29. Google ScholarDigital Library
- Moss, E. B. Nested transactions: An approach to reliable distributed computing. Tech. rep., Massachusetts Institute of Technology, 1981. Google ScholarDigital Library
- Oplinger, J., and Lam, M. S. Enhancing software reliability with speculative threads. In Proceedings of the 10th international conference on architectural support for programming languages and operating systems (ASPLOS-X) (2002), pp. 184--196. Google ScholarDigital Library
- Peyton Jones, S. Tackling the awkward squad: monadic input/output, concurrency, exceptions, and foreign-language calls in Haskell. In Engineering theories of software construction, Marktoberdorf Summer School 2000, C. Hoare, M. Broy, and R. Steinbrueggen, Eds., NATO ASI Series, IOS Press, pp. 47--96.Google Scholar
- Peyton Jones, S., Gordon, A., and Finne, S. Concurrent Haskell. In 23rd ACM Symposium on Principles of Programming Languages (POPL'96), pp.295--308. Google ScholarDigital Library
- Peyton-Jones, S., and Wadler, P. Imperative functional programming. In 20th ACM Symposium on Principles of Programming Languages(POPL'93), pp. 71--84. Google ScholarDigital Library
- Rajwar, R., and Goodman, J. R. Transactional lock-free execution of lock-based programs. In Proceedings of the 10th international conference on architectural support for programming languages and operating systems (ASPLOS-X) (2002), pp. 5--17. Google ScholarDigital Library
- Reppy, J. Concurrent programming in ML. Cambridge University Press, 1999. Google ScholarDigital Library
- Satyanarayanan, M., Mashburn, H. H., Kumar, P., Steere, D. C., and Kistler, J. J. Lightweight recoverable virtual memory. ACM Transactions on Computer Systems 12, 1 (1994), 33--57. Google ScholarDigital Library
- Shavit, N., and Touitou, D. Software transactional memory. In Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing (1995), pp. 204--213. Google ScholarDigital Library
- Shinnar, A., Tarditi, D., Plesko, M., and Steensgaard, B. Integrating support for undo with exception handling. Tech. Rep. MSR-TR-2004-140, Microsoft Research, Dec. 2004.Google Scholar
- Stone, J. M., Stone, H. S., Heidelberger, P., and Turek, J. Multiple reservations and the Oklahoma update. IEEE Parallel and Distributed Technology 1, 4 (Nov. 1993), 58--71. Google ScholarDigital Library
- Welc, A., Hosking, A. L., and Jagannathan, S. Preemption-based avoidance of priority inversion for java. In Proceedings of the 2004 International Conference on Parallel Processing (ICPP) (Aug. 2004), pp. 529--538. Google ScholarDigital Library
- Welc, A., Jagannathan, S., and Hosking, A. Transactional monitors for concurrent objects. In Proceedings of the European Conference on Object-Oriented Programming (June 2004).Google ScholarCross Ref
Index Terms
- Composable memory transactions
Recommendations
Versioned boxes as the basis for memory transactions
Special issue: Synchronization and concurrency in object-oriented languagesIn this paper, we propose the use of Versioned Boxes, which keep a history of values, as the basis for language-level memory transactions. Unlike previous work on software transactional memory, in our proposal read-only transactions never conflict with ...
Composable, nestable, pessimistic atomic statements
OOPSLA '11: Proceedings of the 2011 ACM international conference on Object oriented programming systems languages and applicationsIn this paper we introduce a new method for pessimistically implementing composable, nestable atomic statements. Our mechanism, called shelters, is inspired by the synchronization strategy used in the Jade programming language. Unlike previous lock-...
Unbounded page-based transactional memory
Proceedings of the 2006 ASPLOS ConferenceExploiting thread level parallelism is paramount in the multicore era. Transactions enable programmers to expose such parallelism by greatly simplifying the multi-threaded programming model. Virtualized transactions (unbounded in space and time) are ...
Comments