May-Happen-in-Parallel Based Deadlock Analysis for Concurrent Objects

Abstract : We present a novel deadlock analysis for concurrent objects based on the results inferred by a points-to analysis and a may-happen-in-parallel (MHP) analysis. Similarly to other analysis, we build a dependency graph such that the absence of cycles in the graph ensures deadlock freeness. An MHP analysis provides an over-approximation of the pairs of program points that may be running in parallel. The crux of the method is that the analysis integrates the MHP information within the dependency graph in order to discard unfeasible cycles that otherwise would lead to false positives. We argue that our analysis is more precise and/or efficient than previous proposals for deadlock analysis of concurrent objects. As regards accuracy, we are able to handle cases that other analyses have pointed out as challenges. As regards efficiency, the complexity of our deadlock analysis is polynomial.
Document type :
Conference papers
Dirk Beyer; Michele Boreale. 15th International Conference on Formal Methods for Open Object-Based Distributed Systems (FMOOODS) / 33th International Conference on Formal Techniques for Networked and Distributed Systems (FORTE), Jun 2013, Florence, Italy. Springer, Lecture Notes in Computer Science, LNCS-7892, pp.273-288, 2013, Formal Techniques for Distributed Systems. 〈10.1007/978-3-642-38592-6_19〉
Liste complète des métadonnées

Cited literature [15 references]  Display  Hide  Download

https://hal.inria.fr/hal-01515247
Contributor : Hal Ifip <>
Submitted on : Thursday, April 27, 2017 - 10:46:51 AM
Last modification on : Wednesday, June 13, 2018 - 3:40:02 PM
Document(s) archivé(s) le : Friday, July 28, 2017 - 12:42:13 PM

File

978-3-642-38592-6_19_Chapter.p...
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

Antonio Flores-Montoya, Elvira Albert, Samir Genaim. May-Happen-in-Parallel Based Deadlock Analysis for Concurrent Objects. Dirk Beyer; Michele Boreale. 15th International Conference on Formal Methods for Open Object-Based Distributed Systems (FMOOODS) / 33th International Conference on Formal Techniques for Networked and Distributed Systems (FORTE), Jun 2013, Florence, Italy. Springer, Lecture Notes in Computer Science, LNCS-7892, pp.273-288, 2013, Formal Techniques for Distributed Systems. 〈10.1007/978-3-642-38592-6_19〉. 〈hal-01515247〉

Share

Metrics

Record views

98

Files downloads

42