Designing optimal deadlock avoidance policies for sequential resource allocation systems through classification theory: existence results and customized algorithms

A recent line of work has sought the implementation of the maximally permissive deadlock avoidance policy (DAP) for a broad class of complex resource allocation systems (RAS) as a classifier that gives effective and parsimonious representation to the dichotomy of the underlying behavioral space into the admissible and inadmissible subspaces defined by that policy. The work presented in this paper complements the past developments in this area by providing (i) succinct conditions regarding the possibility of expressing the aforementioned classifier as a set of linear inequalities in the RAS state variables, and (ii) an efficient customized algorithm for the synthesis of pertinent non-linear classifiers that implement the target DAP with minimum run-time computational overhead, in the case that a linear-classifier-based representation of this policy is not possible.