A Structural Approach to Quasi-Static Schedulability Analysis of Communicating Concurrent Programs∗

We describe a system as a set of communicating concurrent programs. Quasi-static scheduling compiles the concurrent programs into a sequential one. It uses a Petri net as an intermediate model of the system. However, Petri nets gen-erated from many interesting applications are not schedu-lable. In this paper, we show the underlying mechanism which causes unschedulability in terms of the structure of a Petri net. We introduce a Petri net structural property and prove unschedulability if the property holds. We propose a linear programming based algorithm to check the prop-erty, and prove the algorithm is valid. Our approach prove unschedulability typically within a second for Petri nets gen-erated from industrial JPEG and MPEG codecs, while the scheduler fails to terminate within 24 hours. Categories and Subject Descriptor