Lock Inference for Atomic Sections
In First ACM SIGPLAN Workshop on Languages, Compilers,
and Hardware Support for Transactional Computing (TRANSACT).
Ottawa, Canada. June 2006.
To prevent unwanted interactions in multithreaded programs, programmers have traditionally employed pessimistic, blocking concurrency primitives. Using such primitives correctly and efficiently is notoriously difficult. To simplify the problem, recent research proposes that programmers specify atomic sections of code whose executions should be atomic with respect to one another, without dictating exactly how atomicity enforced. Much work has explored using optimistic concurrency, or software transactions, as a means to implement atomic sections. This paper proposes to implement atomic sections using a static whole-program analysis to insert necessary uses of pessimistic concurrency primitives. Given a program that contains programmer-specified atomic sections and thread creations, our mutex inference algorithm efficiently infers a set of locks for each atomic section that should be acquired (released) upon entering (exiting) the atomic section. The key part of this algorithm is determining which memory locations in the program could be shared between threads, and using this information to generate the necessary locks. To determine sharing, our analysis uses the notion of continuation effects to track the locations accessed after each program point. As continuation effects are flow sensitive, a memory location may be thread-local before a thread creation and thread-shared afterward. We prove that our algorithm is correct, and provides parallelism according to the precision of the points-to analysis. While our algorithm also attempts to reduce the number locks while preserving parallelism, we show that minimizing the number of locks is NP-hard.
[ pdf ]