SKEDSOFT
CONSTANT UTILIZATION, TOTAL BANDWIDTH, AND WEIGHTED FAIR-QUEUEING SERVERS
We now describe three bandwidth preserving server algorithms that offer a simple way to schedule aperiodic jobs in deadline-driven systems. They are constant utilization [DeLS], total bandwidth [SpBu], and weighted fair-queueing [DeKS] algorithms. These algorithms belong to a class of algorithms that more or less emulate the Generalized Processor Sharing (GPS) algorithm. GPS, sometimes called fluid-flow processor sharing, is an idealized weighted roundrobin algorithm; it gives each backlogged server in each round an infinitesmally small time slice of length proportional to the server size.
Clearly, infinitesmally fine-grain time slicing cannot be implemented in practice. The algorithms which we are about to describe behave like the GPS algorithm to different degrees. In particular, each server maintained and scheduled according to any of these algorithms offers timing isolation to the task(s) executed by it; by this statement, we mean that the worstcase response times of jobs in the task are independent the processor-time demands of tasks executed by other servers. While such a server works in a way that is similar to sporadic servers, its correctness relies on a different principle. Before we describe the rules governing the operations of such a server, we digress briefly to describe a schedulability condition of sporadic jobs scheduled on the EDF basis. The correctness of these algorithms follows from the condition.
Schedulability of Sporadic Jobs in Deadline-Driven Systems: We know that a system of independent, preemptable periodic tasks whose relative deadlines are equal to or larger than their respective periods is schedulable according to the EDF algorithm if the total utilization of the tasks is equal to or less than 1. We also argued that if the execution times of some jobs in some task are smaller than the execution time of the task and the interrelease times between some jobs are larger than its period, the system is schedulable if it is schedulable according to this criterion. We now carry this point further to a more general sufficient schedulability condition for independent, preemptable sporadic jobs. This schedulability condition is in terms of densities of sporadic jobs. The density of a sporadic job Ji that has release time ri , maximum execution time ei and deadline di is the ratio ei /(di − ri ). A sporadic job is said to be active in its feasible interval (ri , di ]; it is not active outside of this interval.
THEOREM . A system of independent, preemptable sporadic jobs is schedulable according to the EDF algorithm if the total density of all active jobs in the system is no greater than 1 at all times.
Proof. We prove the theorem by contradiction. Suppose that a job misses its deadline at time t , and there is no missed deadline before t. Let t−1 be the latest time instant before t at which either the system idles or some job with a deadline after t executes. Suppose that k jobs execute in the time interval (t−1, t ].We call these jobs J1, J2, . . . , Jk and order them in increasing order of their deadlines. (Ties in deadlines are broken arbitrarily.) Jk is the job that misses its deadline at t . Because the processor remains busy in (t−1, t ] executing jobs of equal or higher priorities than Jk and Jk misses its deadline at time t , we must have 
.
We let the number of job releases and completions during the time interval (t−1, t) be l, and ti be the time instant when the ith such event occurs. In terms of this notation, t−1 = t1 and, for the sake of convenience, we also use tl 1 to denote t . These time instants partition the interval (t−1, t ] into l disjoint subintervals, (t1, t2], (t3, t3], . . . , (tl , tl 1]. The active jobs in the system and their total density remain unchanged in each of these subintervals. Let Xi denote the subset containing all the jobs that are active during the subinterval (ti , ti 1] for 1 ≤ i ≤ l and i denote the total density of the jobs in Xi .
The total time demanded by all the jobs that execute in the time interval (t−1, t ] is 
. We can rewrite the sum as
Since Δ j ≤ 1 for all j = 1, 2, . . . , l − 1, we have
This leads to a contradiction.
The condition stated in Theorem 7.4 is not necessary: Sporadic jobs may be schedulable on the EDF basis when this condition is not satisfied. As an example, we consider three sporadic jobs each of which has a relative deadline of 2 and execution time of 1. They are released at time instants 0, 0.5, and 1.0. The total density of jobs is 1.5 in (1, 2], yet they are schedulable on the EDF basis.
You recall that a sporadic task Si is a stream of sporadic jobs. Let Si, j denote the j th job in the task Si (i.e., the release time of Si, j is later than the release times of Si,1, Si,2, . . . , Si, j−1). Let ei, j denote the execution time of Si, j, and pi, j denote the length of time between the release times of Si, j and Si, j 1. At the risk of abusing the term, we call pi, j the period of the sporadic job Si, j and the ratio ei, j /pi, j the instantaneous utilization of the job. The instantaneous utilization ˜ ui of a sporadic task is the maximum of the instantaneous utilizations of all the jobs in this task (i.e., ˜ ui = maxj (ei, j /pi, j )). As with execution times and periods of periodic tasks, we assume that the instantaneous utilization of a sporadic task is a known parameter of the task.
In a system of n sporadic tasks whose total instantaneous utilization is equal to or less than one, the total density of all active jobs is equal to or less than 1 at all times. Consequently, the following sufficient schedulability condition of sporadic tasks scheduled according to the EDF algorithm follows straightforwardly from Theorem .
