A Theory of Rate-Based Execution

At talk given by S.M. Goddard at the 20th IEEE Real-Time Systems Symposium,
Phoenix, AZ, December 1999

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 MokUs 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.

Get the slides for this talk.

Back to Tutorials, short courses, conference presentations, and colloquiums page.