Generalized Multiframe Tasks - fourier.networks.imdea.org.pdfVIP

The International Journal of Time-Critical Computing Systems, 17, 5–22 (1999) c 1999 Kluwer Academic Publishers, Boston. Manufactured in The Netherlands. Generalized Multiframe Tasks SANJOY BARUAH The University of Vermont DEJI CHEN The University of Texas at Austin SERGEY GORINSKY New Jersey Institute of Technology ALOYSIUS MOK The University of Texas at Austin Abstract. A new model for sporadic task systems is introduced. This model—the generalized multiframe task model—further generalizes both the conventional sporadic-tasks model, and the more recent multiframe model of Mok and Chen. A framework for determining feasibility for a wide variety of task systems is established; this framework is applied to this task model to obtain a feasibility-testing algorithm that runs in time pseudo-polynomial in the size of the input for all systems of such tasks whose densities are bounded by a constant less than one. Keywords: recurring multiframe tasks, preemptive uniprocessor scheduling, hard deadlines, feasibility analysis 1. Introduction Multiframe tasks were introduced by Mok and Chen (1996), as a generalization to the well- known periodic task model of Liu and Layland (1973). A multiframe task is represented by a tuple E P , where E [Eo E 1 E N 1] is a vector of execution times, and P is the minimum separation time. The task generates an infinite succession offrames ; the ready times of consecutive frames are at least P time units apart, the execution requirement of the i ’th frame (i 0) is E i mod N , and the deadline of each frame is P time units after its ready time. Feasibility conditions were presented by Mok and Chen for the uniprocessor static-priority scheduling of systems of such multiframe tasks. In this paper, we study a natural generalization of the multiframe task mode