Application and experimental evaluation of state space reduction methods for deadlock analysis in Ada
Authors:
Open Access
- 1 October 1994
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Software Engineering and Methodology
- Vol. 3 (4) , 340-380
Abstract
An emerging challenge for software engineering is the development of the methods and tools to aid design and analysis of concurrent and distributed software. Over the past few years, a number of analysis methods that focus on Ada tasking have been developed. Many of these methods are based on some form of reachability analysis, which has the advantage of being conceptually simple, but the disadvantage of being computationally expensive. We explore the effectiveness of various Petri net-based techniques for the automated deadlock analysis of Ada programs. Our experiments consider a variety of state space reduction methods both individually and in various combinations. The experiments are applied to a number of classical concurrent programs as well as a set of “real-world” programs. The results indicate that Petri net reduction and reduced state space generation are mutually beneficial techniques, and that combined approaches based on Petri net models are quite effective, compared to alternative analysis approaches.Keywords
This publication has 16 references indexed in Scilit:
- Analysis of real-time programs with simple time Petri nets1994
- Coverage Preserving Reduction Strategies for Reachability Analysis1992
- Automated analysis of concurrent systems with the constrained expression toolsetIEEE Transactions on Software Engineering, 1991
- Design and implementation of a Petri net based toolkit for Ada tasking analysisIEEE Transactions on Parallel and Distributed Systems, 1990
- Starvation and critical race analyzers for AdaIEEE Transactions on Software Engineering, 1990
- Integrated concurrency analysis in a software development enviornmentACM SIGSOFT Software Engineering Notes, 1989
- A practical algorithm for static analysis of parallel programsJournal of Parallel and Distributed Computing, 1989
- Petri nets: Properties, analysis and applicationsProceedings of the IEEE, 1989
- Detection of Ada static deadlocks using Petri net invariantsIEEE Transactions on Software Engineering, 1989
- A general-purpose algorithm for analyzing concurrent programsCommunications of the ACM, 1983