ABSTRACT
The movement to multi-core processors increases the need for simpler, more robust parallel programming models. Atomic sections have been widely recognized for their ease of use. They are simpler and safer to use than manual locking and they increase modularity. But existing proposals have several practical problems, including high overhead and poor interaction with I/O. We present pessimistic atomic sections, a fresh approach that retains many of the advantages of optimistic atomic sections as seen in "transactional memory" without sacrificing performance or compatibility. Pessimistic atomic sections employ the locking mechanisms familiar to programmers while relieving them of most burdens of lock-based programming, including deadlocks. Significantly, pessimistic atomic sections separate correctness from performance: they allow programmers to extract more parallelism via finer-grained locking without fear of introducing bugs. We believe this property is crucial for exploiting multi-core processor designs.We describe a tool, Autolocker, that automatically converts pessimistic atomic sections into standard lock-based code. Autolocker relies extensively on program analysis to determine a correct locking policy free of deadlocks and race conditions. We evaluate the expressiveness of Autolocker by modifying a 50,000 line high-performance web server to use atomic sections while retaining the original locking policy. We analyze Autolocker's performance using microbenchmarks, where Autolocker outperforms software transactional memory by more than a factor of 3.
- Rakesh Agrawal, Michael J. Carey, and Miron Livny. Concurrency control performance modeling: Alternatives and implications. ACM Trans. Database Syst., 12(4):609--654, 1987. Google ScholarDigital Library
- C. Scott Ananian, Krste Asanovic, Bradley C. Kuszmaul, Charles E. Leiserson, and Sean Lie. Unbounded transactional memory. In HPCA '05, pages 316--327. Feb 2005. Google ScholarDigital Library
- Chandrasekhar Boyapati. SafeJava: A Unified Type System for Safe Programming. PhD thesis, Massachusetts Institute of Technology, 2004. Google ScholarDigital Library
- M. Christiaens and K. de Bosschere. TRaDE: A topological approach to on-the-fly race detection in java programs. In Proc. of the Java Virtual Machine Research and Technology Symposium, April 2001. Google ScholarDigital Library
- Robert Ennals. Software transactional memory should not be obstruction-free. http://www.cambridge.intel-research.net/~rennals/faststm.html.Google Scholar
- Cormac Flanagan and Stephen N. Freund. Type-based race detection for java. In PLDI '00, pages 219--232, 2000. Google ScholarDigital Library
- Cormac Flanagan and Stephen N. Freund. Atomizer: a dynamic atomicity checker for multithreaded programs. In POPL '04, pages 256--267, 2004. Google ScholarDigital Library
- Cormac Flanagan and Stephen N. Freund. Type Inference Against Races. In SAS'04, pages 116--132, 2004.Google Scholar
- Cormac Flanagan and Stephen N. Freund. Automatic Synchronization Correction. In Synchronization and Concurrency in Object-Oriented Languages (SCOOL), 2005.Google Scholar
- Cormac Flanagan, Stephen N. Freund, and Marina Lifshin. Type Inference for Atomicity. In TLDI '05, pages 47--58, 2005. Google ScholarDigital Library
- Cormac Flanagan and Shaz Qadeer. A type and effect system for atomicity. In PLDI '03, pages 338--349, 2003. Google ScholarDigital Library
- Keir Fraser. Practical lock freedom. PhD thesis, Cambridge University Computer Laboratory, 2003. Also available as Technical Report UCAM-CL-TR-579.Google Scholar
- Keir Fraser and Tim Harris. Concurrent programming without locks. http://www.cl.cam.ac.uk/Research/SRG/netos/lock-free.Google Scholar
- J. N. Gray, R. A. Lorie, G. R. Putzolu, and I. L. Traiger. Granularity of locks and degrees of consistency in a shared data base. Technical report, IBM Research Laboratory, 1975. Report RJ 1654.Google Scholar
- Tim Harris. Exceptions and side-effects in atomic blocks. In Proceedings of the 2004 Workshop on Concurrency and Synchronization in Java programs, pages 46--53, Jul 2004. Proceedings published as Memorial University of Newfoundland CS Technical Report 2004-01.Google Scholar
- Tim Harris and Keir Fraser. Language support for lightweight transactions. In OOPSLA '03, pages 388--402. Oct 2003. Google ScholarDigital Library
- Tim Harris and Keir Fraser. Revocable locks for non-blocking programming. In PPoPP '05. Jun 2005. Google ScholarDigital Library
- Tim Harris, Simon Marlow, Simon~Peyton Jones, and Maurice Herlihy. Composable memory transactions. In PPoPP '05. Jun 2005. Google ScholarDigital Library
- Maurice Herlihy, Victor Luchangco, Mark Moir, and William N. Scherer III. Software transactional memory for dynamic-sized data structures. In PODC '03, pages 92--101. Jul 2003. Google ScholarDigital Library
- Maurice Herlihy and J. Eliot B. Moss. Transactional memory: Architectural support for lock-free data structures. In ISCA '93, pages 289--300. May 1993. Google ScholarDigital Library
- Barbara Liskov and Robert Scheifler. Guardians and Actions: Linguistic Support for Robust, Distributed Programs. ACM Transactions on Programming Languages and Systems, 5(3):381--404, 1983. Google ScholarDigital Library
- D. B. Lomet. Process Structuring, Synchronization, and Recovery using Atomic actions. In Proceedings of an ACM Conference on Language Design for Reliable Software, pages 128--137, 1977. Google ScholarDigital Library
- Maged M. Michael and Michael L. Scott. Simple, fast, and practical non-blocking and blocking concurrent queue algorithms. In PODC '96, pages 267--275, 1996. Google ScholarDigital Library
- Kevin E. Moore, Mark D. Hill, and David A. Wood. Thread-level transactional memory. Technical report, University of Wisconsin, Mar 2005. CS-TR-2005-1524.Google Scholar
- George C. Necula, Scott McPeak, Shree Prakash Rahul, and Westley Weimer. CIL: Intermediate language and tools for analysis and= transformation of C programs. In CC '02, pages 213--228, 2002. Google ScholarDigital Library
- C. Praun and T. Gross. Object race detection. In OOPSLA '01, pages 70--82, 2001. Google ScholarDigital Library
- Ravi Rajwar and James R. Goodman. Transactional lock-free execution of lock-based programs. In ASPLOS '02, pages 5--17. Oct 2002. Google ScholarDigital Library
- Ravi Rajwar, Maurice Herlihy, and Konrad Lai. Virtualizing transactional memory. In ISCA '05, pages 494--505. Jun 2005. Google ScholarDigital Library
- Raghu Ramakrishnan and Johannes Gehrke. Database Management Systems. McGraw-Hill Science/Engineering/Math, 2002. Google ScholarDigital Library
- Alexandru Salcianu and Martin Rinard. Pointer and escape analysis for multithreaded programs. In PPoPP '01. Jun 2001. Google ScholarDigital Library
- Amit Sasturkar, Rahul Agarwal, Liqiang Wang, and Scott D. Stoller. Automated Type-Based Analysis of Data Races and Atomicity. In PPoPP '05, pages 83--94, 2005. Google ScholarDigital Library
- S. Savage, M. Burrows, G. Nelson, P. Sobalvarro, and T. Anderson. Eraser: A dynamic data race detector for multi-threaded programs. ACM Transactions on Computer Systems, 15(4):391--411, 1997. Google ScholarDigital Library
- E. Schonberg. On-the-fly detection of access anomalies. In PLDI '89, pages 285--297, 1989. Google ScholarDigital Library
- Y. Yu, T. L. Rodeheffer, and W. Chen. RaceTrack: Efficient detection of data race conditions via adaptive tracking. Technical report, Microsoft Research, 2005. MSR-TR-2005-54.Google Scholar
Index Terms
- Autolocker: synchronization inference for atomic sections
Recommendations
Autolocker: synchronization inference for atomic sections
Proceedings of the 2006 POPL ConferenceThe movement to multi-core processors increases the need for simpler, more robust parallel programming models. Atomic sections have been widely recognized for their ease of use. They are simpler and safer to use than manual locking and they increase ...
Eliminating synchronization-related atomic operations with biased locking and bulk rebiasing
OOPSLA '06: Proceedings of the 21st annual ACM SIGPLAN conference on Object-oriented programming systems, languages, and applicationsThe Java™ programming language contains built-in synchronization primitives for use in constructing multithreaded programs. Efficient implementation of these synchronization primitives is necessary in order to achieve high performance.Recent research [9,...
Eliminating synchronization-related atomic operations with biased locking and bulk rebiasing
Proceedings of the 2006 OOPSLA ConferenceThe Java™ programming language contains built-in synchronization primitives for use in constructing multithreaded programs. Efficient implementation of these synchronization primitives is necessary in order to achieve high performance.Recent research [9,...
Comments