Affiliations: Department of Electrical Engineering and Computer
Sciences, University of California, Berkeley, CA 94720, USA.
congliu@eecs.berkeley.edu | Cadence Berkeley Labs, Berkeley, CA 94704, USA.
{kalex, watanabe}@cadence.com | Lehrstuhl für Angewandte Informatik, Katholische
Universität Eichstätt-Ingolstadt, Ostenstr. 28, 85071 Eichstätt,
Germany. joerg.desel@ku-eichstaett.de | University of California, Berkeley, CA 94720, USA.
alberto@eecs.berkeley.edu
Note: [] Address for correspondence: Department of Electrical Engineering
and Computer Sciences, University of California, Berkeley, 253 Cory Hall
#1772, Berkeley, CA 94720-1772, USA
Abstract: A schedule of a Petri Net (PN) represents a set of firing sequences
that can be infinitely repeated within a bounded state space, regardless of the
outcomes of the nondeterministic choices. Schedulability analysis for a given
PN answers the question whether a schedule exists in the reachability space of
this net. This paper suggests a novel approach for schedulability analysis
based solely on PN structure. It shows that unschedulability can be caused by a
structural relation among transitions modelling nondeterministic choices. A
method based on linear programming for checking this relation is proposed. This
paper also presents a necessary condition for schedulability based on the rank
of the incidence matrix of the underlying PN. These results shed a light on the
sources of unschedulability often found in PN models of embedded multimedia
systems.
Keywords: Petri net, structural property, quasi-static scheduling
