An efficient algorithm for the enumeration of the minimal unsafe states in complex resource allocation systems

摘要

In a recent work of ours, we proposed a novel approach for the deployment of the maximally permissive deadlock avoidance policy (DAP) for complex resource allocation systems, that is based on the identification and the efficient storage of a critical subset of states of the underlying RAS state space; the availability of this information enables an expedient one-step-lookahead scheme for the identification and blockage of transitions that will take the system behavior outside its safe region. This paper complements the aforementioned results by introducing a novel algorithm that provides those critical states while avoiding the complete enumeration of the RAS state space.