Reordering constraints for pthread-style locks
- 14 March 2007
- conference paper
- conference paper
- Published by Association for Computing Machinery (ACM) in Proceedings of the 12th ACM SIGPLAN symposium on Principles and practice of parallel programming - PPoPP '07
- p. 173-182
- https://doi.org/10.1145/1229428.1229470
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.Keywords
This publication has 11 references indexed in Scilit:
- Threads cannot be implemented as a libraryPublished by Association for Computing Machinery (ACM) ,2005
- The Java memory modelPublished by Association for Computing Machinery (ACM) ,2005
- Scalable queue-based spin locks with timeoutPublished by Association for Computing Machinery (ACM) ,2001
- Basic compiler algorithms for parallel programsPublished by Association for Computing Machinery (ACM) ,1999
- Retrospective: memory consistency and event ordering in scalable shared-memory multiprocessorsPublished by Association for Computing Machinery (ACM) ,1998
- Thin locksPublished by Association for Computing Machinery (ACM) ,1998
- Shared memory consistency models: a tutorialComputer, 1996
- Weak ordering---a new definitionPublished by Association for Computing Machinery (ACM) ,1990
- Efficient and correct execution of parallel programs that share memoryACM Transactions on Programming Languages and Systems, 1988
- How to Make a Multiprocessor Computer That Correctly Executes Multiprocess ProgramsIEEE Transactions on Computers, 1979