Technical Reports
HPL-2009-201
Click here for full text:
The Application of Supervisory Control to Deadlock Avoidance in Concurrent Software
Wang, Yin; Kelly, Terence; Kudlur, Manjunath; Mahlke, Scott; Lafortune, Stephane;
HP Laboratories
HPL-2009-201
Keyword(s): deadlock avoidance, discrete control theory, multithreaded software, concurrent programming
Abstract: Ensuring deadlock-free execution of concurrent programs is a notoriously difficult problem, but an increasingly important one as multicore processors compel performance conscious software developers to parallelize applications. We propose and validate a novel methodology for dynamically controlling the execution of concurrent software in order to provably avoid deadlocks. The methodology is based on supervisory control of discrete event systems modeled by Petri nets. Specifically, we synthesize feedback controllers for concurrent programs based on the theory of supervision based on place invariants and implement the controllers online to guarantee deadlock avoidance. We describe a full implementation of this methodology and report initial experimental results demonstrating its effectiveness and scalability.
6 Pages
Additional Publication Information: Published in Workshop on Discrete Event Systems, Goteburg, Sweden. May 2008.
External Posting Date: August 21, 2009 [Fulltext]. Approved for External Publication
Internal Posting Date: August 21, 2009 [Fulltext]