Maximal Linear Deadlock Avoidance Policies for Sequential Resource Allocation Systems: Characterization, Computation, and Approximation

• 成果类型: Article
• 署名作者: Ibrahim, Michael; Reveliotis, Spyros; Nazeem, Ahmed
• 署名单位: Egyptian Knowledge Bank (EKB); Cairo University; University System of Georgia; Georgia Institute of Technology; Facebook Inc
• 刊物名称: IEEE TRANSACTIONS ON AUTOMATIC CONTROL
• ISSN/ISSBN: 0018-9286
• DOI: 10.1109/TAC.2020.3024480
• 发表日期: 2021
• 页码: 3906-3921
• 关键词: Resource management; System recovery; Supervisory control; PROCESS CONTROL; ELECTRONIC MAIL; Aerospace electronics; systematics; Algebraic deadlock avoidance policies; liveness-enforcing supervision; sequential resource allocation systems

摘要

The problem of maximally permissive deadlock avoidance for sequential resource allocation systems (RAS) is a well-defined problem in the current controls literature. The corresponding supervisor is known as the maximally permissive deadlock avoidance policy (DAP), and it can be perceived as a classifier effecting the dichotomy of the underlying state space into its safe and unsafe subspaces. In the deployment of the maximally permissive DAP, an important issue is the selection of an effective and computationally efficient representation of the aforementioned dichotomy. A popular such representation is the linear classifier, where the admissibility of any given RAS state is resolved based on its ability to satisfy a given set of linear inequalities. However, linear classifiers cannot provide effective representation of the maximally permissive DAP for all RAS instantiations. Hence, this article provides a methodology for synthesizing linear DAPs for any given RAS instance that might not be maximally permissive in the original sense of this term, but observe a more relaxed notion of maximality that is defined within the particular space of the DAPs that admit a linear representation. The presented developments formally define this new DAP class, and provide the necessary algorithms for the synthesis or the systematic approximation of maximal linear DAPs for any given RAS instance.