Document Type

Report

Date

9-1990

Embargo Period

5-1-2012

Keywords

Ada tasking, concurrent programs, deadlock detection, Petri net applications, race conditions, software testing, static analysis

Language

English

Disciplines

Computer Sciences

Description/Abstract

We propose an approach for detecting deadlocks and race conditions in Ada tasking software. It is based on an extension to Petri net-based techniques, where a concurrent program is modeled as a Petri net and a reachability graph is then derived and analyzed for desired information. In this approach, Predicate-Action subnets representing Ada programming constructs are described, where predicates and actions are attached to transitions. Predicates are those found in decision statements. Actions involve updating the status of the variables that affect the tasking behavior of the program and updating the Read and Write sets of shared variables. The shared variables are those occurring in sections of the program, called concurrency zones, related to the transitions. Modeling of a tasking program is accomplished by using the basic subnets as building blocks in translating only tasking-related statements and connecting them to produce the total Predicate-Action net model augmented with sets of shared variables. An augmented reachability graph is then derived by executing the net model. Deadlocks and race conditions are detected by searching the nodes of this graph. The main advantage offered by this approach is that the Predicate-Action extension of the net leads to pruning infeasible paths in the reachability graph and, thus, reducing the spurious error reports encountered in previous approaches. Also, this approach enables a partial handling of loops in a practical way. Implementation issues are also discussed in the paper.

Additional Information

School of Computer and Information Science, Syracuse University, SU-CIS-90-33

Source

local

Share

COinS
 
 

To view the content in your browser, please download Adobe Reader or, alternately,
you may Download the file to your hard drive.

NOTE: The latest versions of Adobe Reader do not support viewing PDF files within Firefox on Mac OS and if you are using a modern (Intel) Mac, there is no official plugin for viewing PDF files within the browser window.