• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文学位 >Designing parsimonious representations of the maximally permissive deadlock avoidance policy for complex resource allocation systems through classification theory.
【24h】

Designing parsimonious representations of the maximally permissive deadlock avoidance policy for complex resource allocation systems through classification theory.

机译：通过分类理论设计复杂资源分配系统的最大允许死锁避免策略的简约表示。

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

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.
机译：过去有关复杂资源分配系统（RAS）死锁避免问题的大多数研究都承认以下事实：对于大多数RAS类，最大允许（最佳）死锁避免策略（DAP）的计算具有超多项式复杂度，并且因此，它采用了权衡最大允许性的解决方案来实现计算可处理性。在这项工作中，我们区分了有效实施最大许可DAP所需的脱机计算和联机计算，并且我们力图开发出此策略的表示形式，该策略将需要最少的联机计算。我们采用的特定表示形式是紧凑分类器，它将影响可到达状态空间的基础二分法为安全和不安全子空间。通过对派生分类问题的一系列简化，我们还能够大幅度降低所寻求分类器构造的离线任务的计算复杂性。在对上述问题的首次研究中，我们限制了我们注意正在进行的名为Gadara的项目所激发的特定RAS类。这个特定的RAS类通过一组线性不等式接受实例化的安全子空间和不安全子空间的分离。我们提出了设计程序，该程序将使用尽可能少的线性不等式构建分类器，并正式确定它们的“完整性”，即它们为所考虑的RAS类的每个实例提供有效分类器的能力。我们还提供了启发式方法，如果有必要，可以减轻构建寻找的分类器所需的计算量。;我们将上述结果扩展到涵盖更通用的RAS类，其中寻找的二分法可能不会由一组线性不等式。为此，我们针对这种更复杂的情况提出了新的参数和非参数分类方案，并正式确定了它们的完整性。我们还为合成所需的分类器提供了有效的和计算有效的程序。上述发展的瓶颈是由于它们以RAS安全和不安全子空间的枚举的可用性为前提的。为了解决这一障碍，我们提出了一种用于RAS的最大允许DAP部署的新颖方法，该方法基于对基本RAS状态空间的状态的关键状态子集的识别和有效存储。尤其是在避免RAS状态空间的完整枚举的同时，提供了这些临界状态;此外，我们扩展了关于最大允许死锁避免的现有理论，以便它可以使用读取器/写入器（R / W）处理RAS。 ）锁。这种新的RAS类提出的一个关键挑战来自以下事实：基础状态空间不一定是有限的。我们利用存在于不安全状态集合中的特殊结构有效地解决了这一障碍，并通过其最小元素实现了该集合的有限表示。最后，我们想提及的是，数值实验证明了所提出方法的有效性，并建立了它们支持具有极大结构和状态空间的RAS的最大允许DAP部署的能力。据我们所知，这些实验还建立了所提出方法的能力，可以有效地计算问题实例的最大允许DAP的可实施方案，其能力大大超出了文献中当前提供的任何其他方法的能力。而且，这是用R / W锁解决RAS的第一项工作。

著录项

  • 作者

    Nazeem, Ahmed.;

  • 作者单位

    Georgia Institute of Technology.;

  • 授予单位 Georgia Institute of Technology.;
  • 学科 Engineering Industrial.;Computer Science.
  • 学位 Ph.D.
  • 年度 2012
  • 页码 228 p.
  • 总页数 228
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类
  • 关键词

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号