Lock Al l o cati on ∗

We introduce lock allocation, an automatic technique that takes a multi-threaded program annotated with atomic sections (that must be executed atomically), and infers a lock assignment from global variables to locks and a lock instrumentation that determines where each lock should be acquired and released such that the result-ing instrumented program is guaranteed to preserve atomicity and deadlock freedom (provided all shared state is accessed only within atomic sections). Our algorithm works in the presence of pointers and procedures, and sets up the lock allocation problem as a 0-1 ILP which minimizes the conflict cost between atomic sections while simultaneously minimizing the number of locks. We have imple-mented our algorithm for both C with pthreads and Java, and have applied it to infer locks in 15K lines of AOLserver code. Our auto-matic allocation produces the same results as hand annotations for most of this code, while solving the optimization instances within a second for most programs. Categories and Subject Descriptors D. 3. 3 [ P r ogr ammi ng L a n