PNTM Integration of Petri Nets and Transactional Memory

Weiyi Wu, Yao Zhang, Shengyuan Wang, Yuan DongPNSE 2011

Introduction

Concurrent programming remains a significant challenge in software engineering. Developers often face a trade-off between high-level formal models, which are difficult to implement, and low-level synchronization primitives like locks, which are prone to deadlocks and race conditions. Software Transactional Memory (STM) offers a middle ground by allowing code blocks to execute atomically. However, STM frequently suffers from high conflict rates when multiple transactions compete for the same data simultaneously, leading to frequent aborts and restarts.

PNTM (Petri Net Transactional Memory) addresses these issues by integrating the formal modeling power of Petri nets with the practical execution of STM. By using Petri nets to explicitly manage transaction firing, PNTM provides a structured approach to concurrency that reduces memory conflicts and ensures execution correctness.

The PNTM Architecture

The PNTM environment is a full-stack solution comprising three primary components: an IDE, a specialized compiler, and a runtime virtual machine.

Visual Modeling and Mapping

The PNTM Editor, based on the Petri Net Kernel (PNK), allows developers to visually design Petri nets that represent the system's logic. In this model, standard Petri net elements are mapped directly to software constructs to bridge the gap between formalism and practice.

Mapping Petri net components to code elements

As shown in the mapping table, transitions correspond to specific functions, while places represent resource variables. Arcs define the flow and requirements of these resources, providing a clear visual representation of the program's concurrency constraints.

The PNTM Compiler

To bridge the gap between high-level models and executable code, the authors developed a modified version of the Generic Java Compiler (GJC). This compiler introduces three new keywords: petrinet, resource, and global.

A key feature of the compiler is its ability to handle "Automated Boilerplate." Using STM libraries typically requires verbose code to make objects transactional. The PNTM compiler automates this by transforming simple declarations into complex transactional interfaces.

Transformation of global variables into transactional interfaces

For instance, a declaration like global int a; is automatically expanded into an @atomic interface with appropriate getters, setters, and factory methods, significantly reducing the manual effort required from the developer.

Runtime Execution

The PNTM Virtual Machine, built on the DSTM2 library, treats the Petri net as an execution blueprint. Each transition is assigned its own thread. The runtime ensures atomicity through a "check-and-consume" phase protected by a global lock. If a transition fires but the underlying STM transaction fails, the system reverts the state and returns the consumed resources to their respective places.

Key Insights and Results

The integration of Petri nets and STM yields several advantages:

  • Static Correctness: The editor performs static checks to ensure logical consistency, such as verifying that input arcs to a single transition do not share resources, preventing conflicts at the model level before they reach the CPU.
  • Resource-Driven Scheduling: Instead of threads competing blindly, the Petri net acts as a scheduler. Transitions only attempt to run when their required resources (tokens) are available, naturally throttling execution to minimize memory collisions.
  • Implementation Success: The framework successfully implements a 5-point API (AddTransition, AddPlace, AddArc, Start, Join) and enforces semantic constraints to ensure model stability.

Limitations and Future Work

While PNTM provides a robust framework for structured concurrency, it currently lacks empirical performance benchmarks comparing it to traditional locking or raw STM. Additionally, the reliance on a global lock for resource manipulation may present a bottleneck in high-throughput scenarios. Future research will focus on performance evaluation and more granular resource management strategies.

Summary updated

BibTeX
@inproceedings{wu2011pntm,
  author = {Weiyi Wu and Yao Zhang and Shengyuan Wang and Yuan Dong},
  title = {{PNTM Integration of Petri Nets and Transactional Memory}},
  booktitle = {PNSE},
  year = {2011},
}
Figure