| Abstract | To prevent unwanted interactions in multithreaded programs, pro-grammers have traditionally employed pessimistic, blocking con-
currency 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 con-
currency primitives. Given a program that contains programmer-
specified atomic sections and thread creations, our mutex infer-
ence 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 al-
gorithm also attempts to reduce the number locks while preserving
parallelism, we show that minimizing the number of locks is NP-
hard.
|
