Abstract: Concurrent programming often forces a trade-off between performance and correctness. While Software Transactional Memory (STM) simplifies atomicity, it struggles with high-contention resources. This paper introduces "Resource Nets," a hybrid model that uses Petri nets to manage high-contention critical resources while leveraging STM for low-contention data. By treating Petri net transitions as atomic transactions, the framework enables formal verification of concurrency logic while maintaining the flexibility of transactional memory.
1. Introduction
Concurrent programming is plagued by the "Dilemma of Concurrency": the tension between high-performance parallelism and the risk of deadlocks or race conditions inherent in manual lock management. Software Transactional Memory (STM) offers a higher-level abstraction by allowing blocks of code to execute atomically. However, STM performance degrades significantly under high contention, as frequent transaction conflicts lead to excessive aborts and retries. This paper proposes a middle ground: using Petri nets to specify concurrency patterns clearly and verify them formally before execution.
2. The Resource Net Framework
To address these challenges, the authors introduce Resource Nets, a specialized form of Colored Petri Nets. This model categorizes shared data into two distinct types:
- Critical Resources: High-contention objects whose access is strictly governed by the Petri net's topology (places and tokens).
- Non-critical Resources: Low-contention objects managed by a standard STM system.
By explicitly modeling critical resources in the net, developers can enforce mutual exclusion through the program's structure rather than relying solely on runtime synchronization. As shown in Figure 1, the "forks" in the Dining Philosophers problem are represented as tokens, ensuring that philosophers cannot even attempt to grab the same fork simultaneously.
3. Transitions as Transactions
The core innovation of this model is the redefinition of Petri net firing semantics. In a standard Petri net, a transition fires instantaneously. In a Resource Net, firing a transition initiates a transaction. The transition "holds" the tokens until the transaction either commits or aborts.
As illustrated in Figure 2, a transition $\tau$ is "desugared" into a sequence of states:
- $\tau_{enter}$: The transition attempts to consume tokens and start a transaction.
- $\rho_\tau$: An intermediate state where the transaction is active.
- $\tau_{commit}$: If the transaction succeeds, tokens are produced in the output places.
- $\tau_{rollback}$: If a conflict occurs in the STM-managed data, the transaction aborts, and tokens are returned to their original places.
This mapping ensures that the consumption of Petri net tokens is atomically tied to the success of the underlying memory transaction.
4. Case Study and Results
The authors demonstrate the utility of Resource Nets using the classic Dining Philosophers problem. In a naive STM implementation, philosophers might frequently conflict when trying to access shared memory representing forks. In the Resource Net approach, structural constraints prevent conflicts before they occur at the memory level, significantly reducing the abort rate.
The paper is primarily a system and framework proposal. The authors successfully defined formal execution semantics and implemented a prototype visual IDE and a modified Java compiler (based on GJC) that supports global, resource, and petrinet modifiers. A key advantage is that Resource Nets can be mathematically reduced to standard Petri nets, allowing developers to use established formal verification tools (like the INA tool) to prove properties like deadlock-freedom.
5. Conclusion and Future Work
The "Transitions as Transactions" model provides a promising path toward verifiable, high-performance parallel software. While the current implementation runs on a standard JVM and lacks extensive performance benchmarks, it establishes a sound theoretical basis for hybrid concurrency. Future work will focus on optimizing the runtime environment and developing methodologies to help programmers effectively distinguish between critical and non-critical resources.
Summary updated