The Rate-Based Execution Model

We present a new 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. We call this new task model rate-based execution (RBE), and it is a generalization of the common sporadic task model. The RBE model is motivated naturally by distributed multimedia and digital signal processing applications. We identify necessary and sufficient conditions for determining the feasibility of an RBE task set, and an optimal scheduling algorithm (based on preemptive earliest-deadline-first (EDF) scheduling) for scheduling the execution of an RBE task set. With respect to the class of work-conserving scheduling algorithms (i.e., the class of scheduling algorithms that schedule without inserting idle time in the schedule), we present necessary and sufficient feasibility conditions and optimal algorithms for non-preemptive scheduling and preemptive scheduling with shared resources