Ensuring deadlock-free execution of concurrent programs is an increasingly important problem as multi-core processors compel performance-conscious software developers to parallelize applications. A novel methodology for dynamically controlling the execution of concurrent software in order to provably avoid deadlocks is proposed. It addresses today's dominant concurrent programming paradigm, multi-threaded programs that employ locks. In this approach, the responsibilities for deadlock avoidance are placed upon a feedback controller that is automatically synthesized from application software source code. A model of the source code will automatically be constructed from a whole-program control flow graph obtained at compile time. The feedback controller will be synthesized offline from the model using techniques from discrete control theory and used to instrument the code. At run-time, the controller will operate by carefully managing lock acquisition and release to ensure that potential deadlock states are never entered. The research plan of this proposal presents a systematic approach for the development, implementation, performance evaluation, and classroom deployment of this novel methodology. By allowing deadlock-free execution of programs via automated feedback control, the full value of unmodified legacy code will be preserved and programmers will be empowered to write code with increased safety, confidence, and productivity.

Agency
National Science Foundation (NSF)
Institute
Division of Computer and Communication Foundations (CCF)
Type
Standard Grant (Standard)
Application #
0819882
Program Officer
Sol J. Greenspan
Project Start
Project End
Budget Start
2008-08-01
Budget End
2012-07-31
Support Year
Fiscal Year
2008
Total Cost
$507,998
Indirect Cost
Name
University of Michigan Ann Arbor
Department
Type
DUNS #
City
Ann Arbor
State
MI
Country
United States
Zip Code
48109