Most of the past research on the problem of deadlock avoidance for complex resource allocation systems (RAS) has acknowledged the fact that the computation of the maximally permissive (optimal) deadlock avoidance policy (DAP) possesses super-polynomial complexity for most RAS classes, and therefore, it has resorted to solutions that trade off maximal permissiveness for computational tractability. In this work, we distinguish between the off-line and the on-line computation that is required for the effective implementation of the maximally permissive DAP, and we seek to develop representations of this policy that will require minimal on-line computation. The particular representation that we adopt is that of a compact classifier that will effect the underlying dichotomy of the reachable state space into safe and unsafe subspaces.
Through a series of reductions of the derived classification problem, we are also able to attain extensive reductions in the computational complexity of the off-line task of the construction of the sought classifier.
In a first study of the aforementioned problem, we restrict our attention to a particular RAS class that is motivated by an ongoing project called Gadara. This particular RAS class accepts the separation of the safe and unsafe subspaces of its instantiations through a set of linear inequalities. We propose design procedures that will construct a classifier employing the minimum possible number of linear inequalities, and we formally establish their "completeness", i.e., their ability to provide an effective classifier for every instance of the considered RAS class. We also offer heuristics that, if necessary, can alleviate the computational effort that is necessary for the construction of the sought classifier.
We extend the aforementioned results to encompass more general RAS classes, where the sought dichotomy might not be represented by a set of linear inequalities. To this end, we propose new parametric and non-parametric classification schemes for this more complex case, and establish formally their completeness. We also provide effective and computationally efficient procedures for the synthesis of the sought classifiers.
A bottleneck in the developments described above is defined by the fact that they presuppose the availability of the enumerations of the RAS safe and unsafe subspaces. To address this obstacle, we propose a novel approach for the deployment of the maximally permissive DAP for RAS, that is based on the identification and the efficient storage of a critical subset of states of the underlying RAS state space. In particular, the proposed algorithm provides those critical states, while avoiding the complete enumeration of the RAS state space.
Furthermore, we extend the existing theory on maximally permissive deadlock avoidance, so that it can handle RAS with reader/writer (R/W) locks. A key challenge that is posed by this new RAS class stems from the fact that the underlying state space is not necessarily finite. We effectively address this obstacle by taking advantage of special structure that exists in the set of unsafe states and enables a finite representation of this set through its minimal elements.
Finally, we would like to mention that numerical experimentation demonstrates the efficacy of the proposed approaches, and establishes their ability to support the deployment of maximally permissive DAP for RAS with very large structure and state spaces. To the best of our knowledge, these experiments also establish the ability of the proposed methodology to effectively compute tractable implementations of the maximally permissive DAP for problem instances significantly beyond the capacity of any other approach currently available in the literature. Moreover, this is the first work to address the RAS with R/W locks.
| Identifer | oai:union.ndltd.org:GATECH/oai:smartech.gatech.edu:1853/45753 |
| Date | 27 July 2012 |
| Creators | Nazeem, Ahmed Mahmoud |
| Publisher | Georgia Institute of Technology |
| Source Sets | Georgia Tech Electronic Thesis and Dissertation Archive |
| Detected Language | English |
| Type | Dissertation |
Page generated in 0.0018 seconds