Maximal Linear Deadlock Avoidance Policies for Complex Resource Allocation Systems
Michael Ibrahim, Spyros A. Reveliotis · 2018
The problem of maximally permissive deadlock avoidance for complex resource allocation systems (RAS) is a well-defined problem in the corresponding controls literature. In some of the prevailing approaches to this problem, the sought supervisor - also known as the maximally permissive deadlock avoidance policy (DAP) - is perceived as a classifier, and its design boils down to the development of an efficient representation of the classification logic that it effects on the underlying RAS states. A popular such representation is the “linear classifier”, where the admissibility of any given RAS state is resolved based on its ability to satisfy a given set of linear inequalities. However, linear classifiers cannot provide effective representation of the maximally permissive DAP for all RAS instantiations. Hence, this paper provides a methodology for synthesizing linear DAPs for any given RAS instance that might not be maximally permissive in the original sense of this term, but observe a more relaxed notion of “maximality”. The presented developments formally define this new DAP class, and provide effective computational algorithms for the synthesis of a maximal linear DAP for any given RAS instance.