Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

C or C++ programs relying on the pthreads interface for concurrency are required to use a specified set of functions to avoid data races, and to ensure memory visibility across threads. Although the detailed rules are not completely, it is not hard to refine them to a simple set of clear and uncontroversial rules for at least a subset of the C language that excludes structures (and hence bit-fields).

We precisely address the question of how locks in this subset must be implemented, and particularly when other memory operations can be reordered with respect to locks. This impacts the memory fences required in lock implementations, and hence has significant performance impact. Along the way, we show that a significant class of common compiler transformations are actually safe in the presence of pthreads, something which appears to have received minimal attention in the past.

We show that, surprisingly to us, the reordering constraints are not symmetric for the lock and unlock operations. In particular, it is not always safe to move memory operations into a locked region by delaying them past a pthread_mutex_lock() call, but it is safe to move them into such a region by advancing them to before a pthread_mutex_unlock() call. We believe that this was not previously recognized, and there is evidence that it is under-appreciated among implementors of thread libraries.

Although our precise arguments are expressed in terms of statement reordering within a small subset language, we believe that our results capture the situation for a full C/C++ implementation. We also argue that our results are insensitive to the details of our literal (and reasonable, though possibly unintended) interpretation of the pthread standard. We believe that they accurately reflect hardware memory ordering constraints in addition to compiler constraints. And they appear to have implications beyond pthread environments.

REFERENCES

• 1: Sarita Vikram Adve, Designing memory consistency models for shared-memory multiprocessors, University of Wisconsin at Madison, Madison, WI, 1993
• 2: Sarita V. Adve , Kourosh Gharachorloo, Shared Memory Consistency Models: A Tutorial, Computer, v.29 n.12, p.66-76, December 1996 [doi>10.1109/2.546611]
• 3: Sarita V. Adve , Mark D. Hill, Weak ordering—a new definition, Proceedings of the 17th annual international symposium on Computer Architecture, p.2-14, May 28-31, 1990, Seattle, Washington, United States
• 4: A. Alexandrescu, H.-J. Boehm, K. Henney, B. Hutchings, D. Lea, and B. Pugh. Memory model for multithreaded C++: Issues. C++ standards committee paper WG21/N1777, http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2005/n1777.pdf, March 2005.
• 5: A. Alexandrescu, H.-J. Boehm, K. Henney, D. Lea, and B. Pugh. Memory model for multithreaded C++. C++ standards committee paper WG21/N1680, http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2004/n1680.pdf, September 2004.
• 6: David F. Bacon , Ravi Konuru , Chet Murthy , Mauricio Serrano, Thin locks: featherweight synchronization for Java, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.258-268, June 17-19, 1998, Montreal, Quebec, Canada
• 7: H. Boehm, D. Lea, and B. Pugh. Memory model for multithreaded C++: August 2005 status update. C++ standards committee paper WG21/N1876, http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2005/n1876.pdf, September 2005.
• 8: H.-J. Boehm. Fast multiprocessor memory allocation and garbage collection. Technical Report HPL-2000-165, HP Laboratories, December 2000.
• 9: H.-J. Boehm. The atomic_ops atomic operations package. http://www.hpl.hp.com/research/linux/atomic_ops/, 2005.
• 10: Hans-J. Boehm, Threads cannot be implemented as a library, Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation, June 12-15, 2005, Chicago, IL, USA
• 11: G. Colvin, B. Dawes, D. Adler, and P. Dimov. The Boost shared_ptr class template. http://www.boost.org/libs/smart_ptr/shared_ptr.htm, August 2005.
• 12: Kourosh Gharachorloo, Retrospective: memory consistency and event ordering in scalable shared-memory multiprocessors, 25 years of the international symposia on Computer architecture (selected papers), p.67-70, June 27-July 02, 1998, Barcelona, Spain [doi>10.1145/285930.285957]
• 13: IEEE and The Open Group. IEEE Standard 1003.1-2001. IEEE, 2001.
• 14: JSR 133 Expert Group. Jsr-133: Java memory model and thread specification. http://www.cs.umd.edu/~pugh/java/memoryModel/jsr133.pdf, August 2004.
• 15: Arvind Krishnamurthy , Katherine Yelick, Optimizing parallel programs with explicit synchronization, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.196-204, June 18-21, 1995, La Jolla, California, United States
• 16: L. Lamport. How to make a multiprocessor computer that correctly executes multiprocess programs. IEEE Transactions on Computers, C-28(9):690--691, 1979.
• 17: D. Lea. The JSR-133 cookbook for compiler writers. http://gee.cs.oswego.edu/dl/jmm/cookbook.html.
• 18: Jaejin Lee , David A. Padua , Samuel P. Midkiff, Basic compiler algorithms for parallel programs, Proceedings of the seventh ACM SIGPLAN symposium on Principles and practice of parallel programming, p.1-12, May 04-06, 1999, Atlanta, Georgia, United States
• 19: G. libstc++ developers. GNU standard C++ library: libstdc++-v3. http://gcc.gnu.org/viewcvs/tags/gcc_4_1_0_release/libstdc++-v3.
• 20: J. Manson, W. Pugh, and S. Adve. The Java memory model (expanded version). http://www.cs.umd.edu/users/jmanson/java/journal.pdf.
• 21: Jeremy Manson , William Pugh , Sarita V. Adve, The Java memory model, Proceedings of the 32nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.378-391, January 12-14, 2005, Long Beach, California, USA
• 22: Paul E. Mckenney , Jonathan Walpole, Exploiting deferred destruction: an analysis of read-copy-update techniques in operating system kernels, 2004
• 23: C. Nelson and H. Boehm. Sequencing and the concurrency memory model. C++ standards committee paper WG21/N2052, http://www.openstd.org/JTC1/SC22/WG21/docs/papers/2006/n2052.htm, September 2006.
• 24: B. Pugh. The Java memory model. http://www.cs.umd.edu/~pugh/java/memoryModel/.
• 25: Michael L. Scott , William N. Scherer, Scalable queue-based spin locks with timeout, Proceedings of the eighth ACM SIGPLAN symposium on Principles and practices of parallel programming, p.44-52, June 2001, Snowbird, Utah, United States
• 26: Dennis Shasha , Marc Snir, Efficient and correct execution of parallel programs that share memory, ACM Transactions on Programming Languages and Systems (TOPLAS), v.10 n.2, p.282-312, April 1988 [doi>10.1145/42190.42277]
• 27: The Open Group and IEEE. The single UNIX specification, version 3 (IEEE standard 1003.1-2001). http://unix.org/version3/, see "Base Definitions", 4.10.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Concurrent programming structures

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization

General Terms:
Languages, Performance

Keywords:
code reordering, data race, locks, memory barriers, memory fences, optimization, pthreads, threads