Petri net models and collaborativeness for parallel processes with resource sharing and message passing

Guanjun Liu, Mengchu Zhou, Changjun Jiang

Research output: Contribution to journalArticlepeer-review

8 Scopus citations

Abstract

Petri nets are widely used to model and analyse concurrent systems. There exist two distinct classes of Petri nets that focus on different features of concurrent systems. The first one features multiple parallel processes sharing a group of common resources but not interacting/collaborating with each other. The second one allows multiple parallel processes to interact/collaborate with each other via message exchange but does not share any common resources. However, in many distributed environments, multiple processes both interact/collaborate with each other and share some common resources. To model and analyse such systems, this article defines a new class of Petri nets called Parallel Process Nets (P2Ns) that may be viewed as a generalization of the two mentioned above. We propose collaborativeness and close collaborativeness for P2Ns. The former guarantees that a modelled system is both deadlock-free and livelock-free, and the latter guarantees that it is deadlock-free, livelock-free, and starvation-free. These concepts and ideas are illustrated through some classical examples such as Producer-Consumer Problem and Dinning Philosophers Problem. Algorithms are developed to decide them. At last, P2Ns are applied to the modelling and analysis of two real systems: hospital information system and elevator scheduling system.

Original languageEnglish (US)
Article number113
JournalACM Transactions on Embedded Computing Systems
Volume16
Issue number4
DOIs
StatePublished - May 2017

All Science Journal Classification (ASJC) codes

  • Software
  • Hardware and Architecture

Keywords

  • Concurrent systems
  • Deadlock
  • Livelock
  • Petri nets
  • Starvation

Fingerprint

Dive into the research topics of 'Petri net models and collaborativeness for parallel processes with resource sharing and message passing'. Together they form a unique fingerprint.

Cite this