On the optimality of randomized deadlock avoidance policies (Q1412282)

The paper revisits the problem of selecting an optimal deadlock resolution strategy when the selection criterion is the maximization of the system throughput and the system is Markovian in terms of its timing and routing characteristics. This problem was addressed in previous work of the authors that (i) provided an analytical formulation for it, (ii) introduced the notion of randomized deadlock avoidance as a generalization of the more traditional approaches of deadlock prevention/avoidance, and detection and recovery, and (iii) provided a methodology for selecting the optimal randomized deadlock avoidance policy for a given resource allocation system (RAS) configuration. An issue that remained open was whether the proposed policy randomization is essential, i.e. whether there exist any RAS configurations for which a randomized deadlock avoidance policy is superior to any other policy that does not employ randomization. The present paper establishes that for the basic problem formulation where the only concern is the (unconstrained) maximization of the system throughput -- or the other typical performance objectives of minimizing the system work-in-process and mean sojourn time -- randomization of the deadlock resolution strategy is not essential. However, it is also shown that, sometimes, it can offer an effective mechanism for accommodating additional operational constraints, like the requirement for production according to a specified product mix.