A Configurable State Class Method for Temporal Analysis of Time Petri Nets

摘要

A task' s end-to-end delay in its execution is a key requirement to real-time systems. This paper presents a configurable state class method based on time Petri nets for their quantitative analysis. The proposed method has a flexible state class structure. A firing domain is separated into a kernel domain that supports the basic evolution of state classes, and a configurable domain that is used to evaluate end-to-end delays. Since both domains adopt a uniform representation for time constraints, end-to-end delays can be computed synchronously with the evolution of state classes via the same firing rules. Firing rules are decomposed into basic timing operations. This treatment not only makes the calculation of end-to-end delays more flexible, but also provides a scalable way to add new timing operations into a time Petri net model. The proposed method computes arbitrary end-to-end delays along a trace with time ${rm O}(ml^{2})$ and space ${rm O}(l^{2})$, where $m$ is the number of firing transitions along the trace and $l$ is the maximum number of transitions in configurable and kernel domains. Compared with the existing state class methods, it has better performance and flexibility in on-the-fly computation of end-to-end delays.