Lock removal for concurrent programs
View Patent ↗A system and method are disclosed for removing locks from a concurrent program. A set of behaviors associated with a concurrent program are modeled as causality constraints. The causality constraints which preserve the behaviors of the concurrent program are identified. Having identified the behavior preserving causality constraints, the corresponding lock and unlock statements in the concurrent program are identified which enforce the identified causality constraints. All identified lock and unlock statements are retained, while all other lock and unlock statements are discarded.
1. A method for removing locks from a concurrent program, comprising:
modeling a set of program behaviors associated with a concurrent program as causality constraints, wherein the set of program behaviors includes threads of the program which are feasible under the scheduling constraints imposed by the synchronization primitives set forth in the concurrent program, wherein the causality constraints are stored on a non-transitory computer readable storage medium;
identifying the causality constraints which preserve the behaviors of the concurrent program, wherein each visible state which is not reachable from at least one other visible state is identified by a constraint identifier, and wherein the causality constraints are embedded into a common framework; and
identifying lock and unlock statements in the concurrent program which enforce the identified causality constraints, wherein lock and unlock statements which are employed to preserve the identified causality constraints are maintained, and redundant locks are removed from the concurrent program.
2. The method of claim 1 , further comprising retaining the lock and unlock statements which enforce the identified causality constraints, and discarding any remaining lock and unlock statements.
3. The method of claim 1 , further comprising employing at least one lock acquisition history to isolate a subset of lock and unlock statements in the concurrent program that enforce the identified causality constraints which capture the set of behaviors associated with the concurrent program.
4. The method of claim 3 , wherein employing at least one lock acquisition history includes determining reachability between global control states by tracking lock access patterns locally in each individual thread of the concurrent program.
5. The method of claim 3 , wherein employing at least one lock acquisition history includes determining static reachability of a concurrent program with nested locks via thread-local reasoning.
6. The method of claim 3 , wherein isolating the subset of lock and unlock statements includes identifying reachability barriers between control states.
7. The method of claim 1 , wherein identifying the causality constraints includes indicating all possible interleavings of threads associated with the concurrent program that are feasible under scheduling constraints that are imposed by synchronization primitives in the concurrent program.
8. A computer readable storage medium comprising a computer readable program, wherein the computer readable program when executed on a computer causes the computer to perform the method recited in claim 1 .
9. A method for removing locks from a concurrent program, comprising:
modeling a set of program behaviors associated with a concurrent program as causality constraints, wherein the set of program behaviors includes threads of the program which are feasible under the scheduling constraints imposed by the synchronization primitives set forth in the concurrent program, wherein the causality constraints are stored on a non-transitory computer readable storage medium;
identifying the causality constraints which preserve the behaviors of the concurrent program using at least one lock acquisition history, wherein each visible state which is not reachable from at least one other visible state is identified by a constraint identifier, and wherein the causality constraints are embedded into a common framework;
identifying lock and unlock statements in the concurrent program which enforce the identified causality constraints using at least one lock acquisition history, wherein lock and unlock statements which are employed to preserve the identified causality constraints are maintained, and redundant locks are removed from the concurrent program;
retaining the lock and unlock statements which enforce the identified causality constraints; and
discarding the lock and unlock statements which do not enforce the identified causality constraints.
10. The method of claim 9 , wherein identifying lock and unlock statements includes employing the at least one lock acquisition history to isolate a subset of lock and unlock statements in the concurrent program that enforce the identified causality constraints which capture the set of behaviors associated with the concurrent program.
11. The method of claim 10 , wherein employing the at least one lock acquisition history includes determining reachability between global control states by tracking lock access patterns locally in each individual thread of the concurrent program.
12. The method of claim 10 , wherein employing at least one lock acquisition history includes determining static reachability of a concurrent program with nested locks via thread-local reasoning.
13. The method of claim 10 , wherein isolating the subset of lock and unlock statements includes identifying reachability barriers between control states.
14. A system for removing locks from a concurrent program, comprising:
a constraint modeler configured to specify a set of program behaviors associated with a concurrent program as causality constraints, wherein the set of program behaviors includes threads of the program which are feasible under the scheduling constraints imposed by the synchronization primitives set forth in the concurrent program, wherein the causality constraints are stored on a non-transitory computer readable storage medium;
a constraint identifier configured to identify the causality constraints which preserve a set of behaviors associated with the concurrent program, wherein each visible state which is not reachable from at least one other visible state is identified by a constraint identifier, and wherein the causality constraints are embedded into a common framework; and
a lock identifier configured to identify lock and unlock statements in the concurrent program which enforce the identified causality constraints, wherein lock and unlock statements which are employed to preserve the identified causality constraints are maintained, and redundant locks are removed from the concurrent program.
15. The system of claim 14 , wherein the system further comprises a lock remover configured to retain the lock and unlock statements which enforce the identified causality constraints, and discard any remaining lock and unlock statements.
16. The system of claim 14 , wherein the lock identifier includes at least one lock acquisition history to isolate a subset of lock and unlock statements in the concurrent program that enforce the causality constraints which capture the set of behaviors associated with the concurrent program.
17. The system of claim 16 , wherein the at least one lock acquisition history is employed to determine static reachability of a concurrent program with nested locks via thread-local reasoning.
18. The system of claim 16 , wherein the at least one lock acquisition history is employed to determine reachability between global control states by tracking lock access patterns locally in each individual thread.
19. The system of claim 16 , wherein isolating the subset of lock and unlock statements includes identifying reachability barriers between control states.
20. The system of claim 14 , wherein the causality constraints indicate all possible interleavings of threads associated with the concurrent program that are feasible under scheduling constraints that are imposed by synchronization primitives in the concurrent program.