Abstract
This paper extends the existing theory on maximally permissive liveness-enforcing supervision of resource allocation systems (RAS) 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 inadmissible states and enables a finite representation of this set through its minimal elements.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Notes
A comprehensive exposition of the Gadara project, including its goals and its current achievements, can be found at: http://gadara.eecs.umich.edu, . We should also notice, for completeness, that the very first studies on the problem of deadlock avoidance took place in the 1960’s / early 1970’s in the context of the computing technologies of that era (e.g., Dijkstra (1965); Coffman et al. (1971); Holt (1972)). But the connection of deadlock avoidance to DES theory took place primarily through the works mentioned above.
Maximal permissiveness and all other technical concepts appearing in this introductory discussion will be formally defined in the subsequent sections.
And, of course, it extends the original Gadara RAS model with the novel element of R/W-locks.
The acyclicity requirement for digraphs \(\mathcal {G}_{j}\) will be removed in Section 7.
We remind the reader that \(a^{+} \equiv \max \{a,0\}\) and \(a^{-} \equiv \min \{a,0\}\).
This claim is substantiated by the computational experiments that are presented in Section 6. Also, we notice that it is possible to skip the elimination of the reachable unsafe states in the construction of the list d e a d l o c k H T, without compromising the correctness of the resulting implementation of the maximally permissive DAP that was discussed in Section 2. However, the presence of the unreachable deadlock states in d e a d l o c k H T would have an adversarial impact on the complexity of the computation of the set \(\bar {S}_{r\bar {s}}\) that is discussed in Section 5, that is much more severe than the computational cost of their removal from that list.
We remind the reader that the out-degree of a node v in a digraph \(\mathcal {G}\) is equal to the number of edges that emanate from v.
This result is similar to a result that is established in the “ ⇐=” part of the proof for Theorem 1 in Liao et al. (2013b). Here we state and prove the result in the context of the representational formalisms for the R/W-RAS and their behavioral dynamics that are employed in this work.
It is interesting to notice that the preservation of the monotonicity of (un-)safety in the face of the underlying uncontrollable behavior has been accepted rather silently in the previous works on the Gadara RAS.
We remind the reader that two nodes \(v, {v}^{\prime }\) in a digraph \(\mathcal {G}=(V,E)\) are communicating if there are directed paths in \(\mathcal {G}\) that lead from each of these two nodes to the other one. Nodal communication defines an equivalence relationship on the node set V of \(\mathcal {G}\) and the corresponding equivalence classes are known as the communication classes of \(\mathcal {G}\). The condensation of \(\mathcal {G}\) that is induced by this relationship, is the digraph \(\hat {\mathcal {G}}\) that is obtained by collapsing each communication class to a single (macro-)node while retaining all edges that connect nodes in different communication classes. By its construction, \(\hat {\mathcal {G}}\) is an acyclic digraph.
For the sake of brevity, we refer to Nazeem and Reveliotis (2014) for the relevant details.
References
Banaszak ZA, Krogh BH (1990) Deadlock avoidance in flexible manufacturing systems with concurrently competing process flows. IEEE Trans Robot Autom 6:724–734
Cassandras CG, Lafortune S (2008) Introduction to discrete event systems, 2nd edn. Springer, NY
Chen HC, Chen CL (2009) On minimal elements of upward-closed sets. Theor Comput Sci 410:2442–2452
Coffman EG, Elphick MJ, Shoshani A (1971) System deadlocks. Comput Surv 3:67–78
Commer P, Sethi R (1977) The complexity of TRIE index construction. J ACM 24:428–440
Courtois P, Heymans F, Parnas D (1971) Concurrent control with “readers” and “writers”. Commun ACM 14(10):667–668
Dickson L (1913) Finiteness of the odd perfect and primitive abundant numbers with n distinct prime factors. Am J Math 35(4):413–422
Dijkstra EW (1965) Cooperating sequential processes. Tech. rep. Technological University, Eindhoven
Ezpeleta J, Colom JM, Martinez J (1995) A Petri net based deadlock prevention policy for flexible manufacturing systems. IEEE Trans Robot Autom 11:173–184
Fanti MP, Maione B, Mascolo S, Turchiano B (1997) Event-based feedback control for deadlock avoidance in flexible production systems. IEEE Trans Robot Autom 13:347–363
Holt RD (1972) Some deadlock properties of computer systems. ACM Comput Surv 4:179–196
Huang Y, Jeng M, Xie X, Chung D (2006) Siphon-based deadlock prevention policy for flexible manufacturing systems. IEEE Trans Syst Man Cybern Syst Hum 36(6):1248–1256
Li Z, Zhou M, Wu N (2008) A survey and comparison of Petri net-based deadlock prevention policies for flexible manufacturing systems. IEEE Trans Syst Man Cybern – Part C 38:173–188
Liao H, Lafortune S, Reveliotis S, Wang Y, Mahlke S (2013a) Optimal liveness-enforcing control of a class of Petri nets arising in multithreaded software. IEEE Trans Autom Control 58:1123–1138
Liao H, Wang Y, Cho HK, Stanley J, Kelly T, Lafortune S, Mahlke S, Reveliotis S (2013b) Concurrency bugs in multi-threaded software: modeling and analysis using Petri nets. Discrete Event Syst: Theory Appl 23:157–195
Liao H, Wang Y, Stanley J, Lafortune S, Reveliotis S, Kelly T, Mahlke S (2013c) Eliminating concurrency bugs in multithreaded software: a new approach based on discrete-event control. IEEE Trans Control Syst Technol 21:2067–2082
Nazeem A (2012) Designing parsimonious representations of the maximally permissive deadlock avoidance policy for complex resource allocation systems through classification theory. PhD thesis. Georgia Institute of Technology, Atlanta
Nazeem A, Reveliotis S (2011) A practical approach for maximally permissive liveness-enforcing supervision of complex resource allocation systems. IEEE Trans Autom Sci Eng 8:766–779
Nazeem A, Reveliotis S (2012) Designing maximally permissive deadlock avoidance policies for sequential resource allocation systems through classification theory: the non-linear case. IEEE Trans Autom Control 57(7):1670–1684
Nazeem A, Reveliotis S (2014) An efficient algorithm for the enumeration of the minimal unsafe states in complex resource allocation systems. IEEE Trans Autom Sci Eng 11:111–124
Nazeem A, Reveliotis S, Wang Y, Lafortune S (2011) Designing maximally permissive deadlock avoidance policies for sequential resource allocation systems through classification theory: the linear case. IEEE Trans Autom Control 56:1818–1833
Park J (2004) A deadlock and livelock free protocol for decentralized internet resource coallocation. IEEE Trans Syst Man Cybern Part A 34:123–131
Peterson JL (1981) Operating System Concepts. Addison-Wesley, Boston
Reveliotis S, Roszkowska E (2011) Conflict resolution in free-ranging multi-vehicle systems: a resource allocation paradigm. IEEE Trans Robot 27:283–296
Reveliotis SA (1996) Structural analysis & control of flexible manufacturing systems with a performance perspective. PhD thesis. University of Illinois, Urbana
Reveliotis SA (2000) Conflict resolution in AGV systems. IIE Trans 32(7):647–659
Reveliotis SA (2005) Real-time Management of resource allocation systems: a discrete event systems approach. Springer, NY
Reveliotis SA, Ferreira PM (1996) Deadlock avoidance policies for automated manufacturing cells. IEEE Trans Robot Autom 12:845–857
Roszkowska E, Reveliotis S (2008) On the liveness of guidepath-based, zoned-controlled, dynamically routed, closed traffic systems. IEEE Trans Autom Control 53:1689–1695
Valk R, Jantzen M (1985) The residue of vector sets with applications to decidability problems in Petri nets. Acta Informatica 21(6):643–674
Viswanadham N, Narahari Y, Johnson TL (1990) Deadlock avoidance in flexible manufacturing systems using Petri net models. IEEE Trans Robot Autom 6:713–722
Wang Y, Liao H, Nazeem A, Reveliotis S, Kelly T, Mahlke S, Lafortune S (2009) Maximally permissive deadlock avoidance for multithreaded computer programs. In: Proceedings of the 5th IEEE conference on automation science and engineering, pp 37–41
Wang Y, Cho H, Liao H, Nazeem A, Kelly T, Lafortune S, Mahlke S, Reveliotis S (2010) Supervisory control of software execution for failure avoidance: experience from the Gadara project. In: Proceedings of the 10th international workshop on discrete event systems
Wu N, Zhou M (2007) Deadlock and blocking-free shortest routing of bi-directional automated guided vehicles. IEEE Trans Mechatronics 12:63–72
Zhou M, Fanti MP (2004) Deadlock resolution in computer-integrated systems. Marcel Dekker Inc., Singapore
Author information
Authors and Affiliations
Corresponding author
Additional information
This work was partially supported by NSF grant CMMI-MES-0928231.
Rights and permissions
About this article
Cite this article
Nazeem, A., Reveliotis, S. Maximally permissive deadlock avoidance for resource allocation systems with R/W-locks. Discrete Event Dyn Syst 25, 31–63 (2015). https://doi.org/10.1007/s10626-014-0202-x
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10626-014-0202-x