A Theory of Rate-Based Execution

K. Jeffay and S.M. Goddard
Proceedings of the 20th IEEE Real-Time Systems Symposium
Phoenix, AZ, December 1999
pages 304-314.

Abstract: We present a task model for the real-time execution of event-driven tasks in which no a priori characterization of the actual arrival rates of events is known; only the expected arrival rates of events is known. The model, called rate-based execution (RBE), is a generalization of Mok's sporadic task model [14]. The RBE model is motivated naturally by distributed multimedia and digital signal processing applications. We derive necessary and sufficient conditions for determining the feasibility of an RBE task set and demonstrate that earliest deadline first (EDF) scheduling is an optimal scheduling algorithm for both preemptive and non-preemptive execution environments, as well as hybrid environments wherein RBE tasks access shared resources.

Our analysis of RBE tasks demonstrates a fundamental distinction between deadline based scheduling methods and static priority based methods. We show that for deadline-based scheduling methods, feasibility is solely a function of the distribution of task deadlines in time. This is contrasted with static priority schedulers where feasibility is a function of the actual arrival rates of work for tasks. Thus whereas the feasibility of static priority schedulers is a function of the periodicity of tasks, the feasibility of deadline schedulers is independent of task arrival processes and hence deadline schedulers are more suitable for use in distributed, event-driven, real-time systems.

Get a PostScript - or - a PDF copy of this paper.

A copy of the slides for the talk presented at the conference is also available.

Back to Real-Time Systems Research at UNC page.