Ordinary differential equation-based deadlock detection

Zuohua Ding, Mengchu Zhou, Shouguang Wang

Research output: Contribution to journalArticlepeer-review

12 Scopus citations

Abstract

Deadlock detection for concurrent systems via static analysis is in general difficult because of state-space explosion; indeed it is PSPACE compete. This paper presents a new method to detect the deadlocks. A concurrent system consisting of several processes that communicate using a resource sharing mechanism is represented by a set of ordinary differential equations of a restricted type. The equations describe the system state changes, and their solutions, also called state measures, indicate the extent to which the state can be reached in execution. Based on the solutions, the resource deadlock can be detected. By taking into account the computation errors of numerical solution for the differential equations, the detection can be performed via a MATLAB solver, as shown in the experiments. The complexity of the proposed method is polynomial.

Original languageEnglish (US)
Article number6783791
Pages (from-to)1435-1454
Number of pages20
JournalIEEE Transactions on Systems, Man, and Cybernetics: Systems
Volume44
Issue number10
DOIs
StatePublished - Oct 1 2014

All Science Journal Classification (ASJC) codes

  • Software
  • Control and Systems Engineering
  • Human-Computer Interaction
  • Computer Science Applications
  • Electrical and Electronic Engineering

Keywords

  • Concurrent program
  • concurrent system
  • continuous Petri net
  • deadlock detection
  • ordinary differential equation
  • state space explosion

Fingerprint

Dive into the research topics of 'Ordinary differential equation-based deadlock detection'. Together they form a unique fingerprint.

Cite this