Title :
A theory of rate-based execution
Author :
Jeffay, Kevin ; Goddard, Steve
Author_Institution :
Dept. of Comput. Sci., North Carolina Univ., Chapel Hill, NC, USA
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
Keywords :
multimedia systems; processor scheduling; real-time systems; signal processing; a priori characterization; digital signal processing; distributed multimedia; earliest deadline first scheduling; event-driven tasks; hybrid environments; optimal scheduling algorithm; rate-based execution theory; real-time systems; sporadic task model; static priority schedulers; task model; Computer science; Digital signal processing; Hardware; Multimedia systems; Optimal scheduling; Processor scheduling; Real time systems; Scheduling algorithm; Signal processing algorithms; Sufficient conditions;
Conference_Titel :
Real-Time Systems Symposium, 1999. Proceedings. The 20th IEEE
Conference_Location :
Phoenix, AZ
Print_ISBN :
0-7695-0475-2
DOI :
10.1109/REAL.1999.818858