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.
