SKEDSOFT

REAL-TIME PERFORMANCE FOR JOBS WITH SOFT TIMING CONSTRAINTS: For many applications, occasional missed deadlines are acceptable; their sporadic jobs have soft deadlines. This section discusses the performance of the algorithms described in previous sections when used to schedule this type of jobs. In the remainder of this section, except where it is stated otherwise, by a sporadic job, we mean one whose deadline is soft.

Traffic Models: You recall that each sporadic task is a stream of sporadic jobs that have the same interreleasetime and execution-time distributions and the same real-time performance requirements. The real-time performance experienced by each sporadic task is typically measured in terms of such criteria as the maximum tardiness and miss rate of jobs in it. (These terms were defined in Section 3.8.) In a system that provides each sporadic task with some kind of performance guarantee, the system subjects each new sporadic task to an acceptance test. Once a sporadic task is admitted into the system, the scheduler accepts and schedules every job in it.

Specifically, when requesting admission into the system, each sporadic task presents to the scheduler its traffic parameters. (These parameters are collectively called the flow specification of the task in communications literature.) These parameters define the constraints on the interarrival times and execution times of jobs in the task. The performance guarantee provided by the system to each task is conditional, meaning that the system delivers the guaranteed performance conditioned on the fact that the task meets the constraints defined by its traffic parameters. The flip side is that if the task misbehaves (i.e., its actual parameters deviate from its traffic parameters), the performance experienced by it may deteriorate. Different traffic models use different traffic parameters to specify the behavior of a sporadic task. In addition the periodic task and sporadic task models, there are also the Ferrari and Verma (FeVe) model [FeVe], the (λ, β) model [Cruz], and the leaky bucket model. These models are commonly used to characterize real-time traffic in communication networks.

FeVe and (λ, β) Models. According to the FeVe model, each sporadic task is characterized by a 4-tuple (e, p, p, I ): e is the maximum execution time of all jobs in the task; p is the minimum interarrival time of the jobs; p is their average interarrival time, and this average is taken over a time interval of length I . Each job may model the transmission of a message (or packet) and each sporadic task the transmission of a message stream. It is also a good model of other types of sporadic tasks (e.g., computations) when the execution times of jobs in each task are roughly the same but their interarrival times may vary widely. The (λ, β) model, characterizes each sporadic task by a rate parameter λ and a burst parameter β. The total execution time of all jobs that are released in any time interval of length x is no more than β λx.

Leaky BucketModel. To define the leaky bucket model, we first introduce the notion of a (, E) leaky bucket filter. Such a filter is specified by its (input) rate  and size E: The filter can hold at most E tokens at any time and it is being filled with tokens at a constant rate of  tokens per unit time. A token is lost if it arrives at the filter when the filter already contains E tokens.
We can think of a sporadic task that meets the (, E) leaky bucket constraint as if its jobs were generated by the filter in the following manner. The filter may release a job with execution time e when it has at least e tokens. Upon the release of this job, e tokens are removed from the filter. No job can be released when the filter has no token. Therefore, no job in a sporadic task that satisfies the (, E) leaky bucket constraint has execution time larger than E. Indeed, the total execution time of all jobs that are released within any time interval of length E/ is surely less than 2E. A periodic task with period equal to or larger than E/ and execution time equal to or less than E satisfies the (, E) leaky bucket constraint. A sporadic task S = (1, p, p, I ) that fits the FeVe model satisfies this constraint if p = 1/ and E = (1 − p/p)I /p.

Figure 7–22 shows an example. The arrows above the time line indicate the release times of jobs of a sporadic task in a time interval of length 70. The execution times of the jobs are given by the numbers above the boxes symbolizing the jobs, and their relative deadlines are all equal to 15.

• Of course, we can model the task as a periodic task (5, 2, 15) since the minimum interrelease time is 5 and the maximum execution time of all instances is 2. However, this

is not an accurate characterization; the utilization of this periodic task is 0.4, which is many times larger than its average utilization of 0.11.

• Following the sporadic task model, we can characterize the task by the sequence of instantaneous utilizations of its jobs: 0.19, 0.133, 0.075, 0.24, 0.055, and so on. The maximum instantaneous utilization of the stream is 0.24.
• This task satisfies the (0.2, 2.0)-leaky bucket constraint. The diagram at the bottom of the figure shows the number of token remaining in a (0.2, 2.0)-leaky bucket filter as a function of time. The bucket is full at time 0. In fact, the task satisfies this constraint provided the size of the leaky bucket is no less than 2.0 and its rate is no less than 0.19.