Conference proceeding
A theory of rate-based execution
Proceedings 20th IEEE Real-Time Systems Symposium (Cat. No.99CB37054), pp.304-314
1999
DOI: 10.1109/REAL.1999.818858
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-bared execution (RBE), is a generalization of Mok's sporadic task model. 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 nonpreemptive 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.
Details
- Title: Subtitle
- A theory of rate-based execution
- Creators
- K Jeffay - University of North Carolina at Chapel HillS Goddard - University of North Carolina at Chapel Hill
- Resource Type
- Conference proceeding
- Publication Details
- Proceedings 20th IEEE Real-Time Systems Symposium (Cat. No.99CB37054), pp.304-314
- Publisher
- IEEE
- DOI
- 10.1109/REAL.1999.818858
- ISSN
- 1052-8725
- eISSN
- 2576-3172
- Language
- English
- Date published
- 1999
- Academic Unit
- Computer Science
- Record Identifier
- 9984259406202771
Metrics
12 Record Views