Slack Stealing in Deadline Driven System

Slack stealing in deadline driven system

Consider, a system of two periodic tasks, T1 = (2.0, 3.5, 1.5) and T2 = (6.5, 0.5). In addition to the aperiodic job that has execution time 1.7 and is released at 2.8, suppose another aperiodic job with execution time 2.5 is released at time 5.5. These jobs are A1 and A2, respectively. The figure below shows the operation of a slack stealer.

1. Initially, the slack stealer is suspended because the aperiodic job queue is empty. When A₁ arrives at 2.8, the slack stealer resumes. Because the execution of the last 0.7 units of J_1,1 can be postponed until time 4.8 (i.e., 5.5−0.7) and T₂ has no ready job at the time, the system has 2 units of slack. The slack stealer is given the highest priority. It preempts J_1,1 and starts to execute A₁. As it executes, the slack of the system is consumed at the rate of 1 per unit time.
2. At time 4.5, A₁ The slack stealer is suspended. The job J_1,1 resumes and executes to completion on time.
3. At time 5.5, A₂ arrives, and the slack stealer becomes ready again. At this time, the execution of the second job J_1,2 of T₁ can be postponed until time 7.5, and the second job J_2,2 of T₂ can be postponed until 12.5.Hence, the system as a whole has 2.0 units of slack. The slack stealer has the highest priority starting from this time. It executes A₂.
4. At time 7.5, all the slack consumed, the slack stealer is given the lowest priority. J_1,2 preempts the slack stealer and starts to execute.
5. At time 9, J_1,2 completes, and the system again has slack. The slack stealer now has the highest priority. It continues to execute A₂.
6. When A₂ completes, the slack stealer is suspended again. For as long as there is no job in the aperiodic job queue, the periodic tasks execute on the EDF basis.

In principle, slack stealing in a priority-driven system is almost as straightforward as in a clock-driven system as shown by the figure. The key step in slack stealing is the computation to determine whether the system has any slack or not. While this is a simple step in a clock-driven system, it is considerably more complex in a priority-driven system. The remainder of this section and most of the following section are devoted to algorithms for computing the amount of available slack. These algorithms are called slack computation algorithms.

A slack computation algorithm is correct if it never says that the system has slack when the system does not, since doing so may cause a periodic job to complete too late. An optimal slack computation algorithm gives the exact amount of slack the system has at the time of the computation. Therefore, it is correct. A correct slack computation algorithm that is not optimal gives a lower bound to the available slack. (Liu 233-235)

Slack Stealing in Fixed priority System

In principle, slack stealing in a fixed-priority system works in the same way as slack stealing in a deadline-driven system. However, the computation and the usage of the slack are both more complicated in fixed-priority systems.

Consider, the system contains three periodic tasks T₁ = (3, 1), T₂ = (4, 1), and T₃ = (6, 1).

The example points out the following:

1. No slack-stealing algorithm can minimize the response time of every aperiodic job in a fixed-priority system even when prior knowledge on the arrival times and execution times of aperiodic jobs is available.
2. The amount of slack a fixed-priority system has in a time interval may depend on when the slack is used. To minimize the response time of an aperiodic job, the decision on when to schedule the job must take into account the execution time of the job. (Liu 244)

Scheduling of Sporadic Jobs

Recall the sporadic job scheduling problem: –

• Based on the execution time and deadline of each newly arrived sporadic job, decide whether to accept or reject the job
• Accepting the job implies that the job will complete within its deadline, without causing any periodic task or previously accepted sporadic job to miss its deadline
• Do not accept a sporadic job if cannot guarantee it will meet its deadline

Model for Scheduling Sporadic Jobs

When sporadic jobs arrive, they are both accepted and scheduled in EDF order

• In a dynamic-priority system, this is the natural order of execution
• In a fixed-priority system, the sporadic jobs are executed by a bandwidth preserving server, which performs an acceptance test and runs the sporadic jobs in EDF order
• In both cases, no new scheduling algorithm is required

Definitions: –

• Sporadic jobs are denoted by Si(r_i, d_i, e_i) where r_i is the release time, d_i is the (absolute) deadline, and e_i is the maximum execution time
• The density of a sporadic job Δ_i =e_i/(d_i –r_i) • The total density of a system of n jobs is Δ =Δ₁ +Δ₂ + … +Δ_n
• The job is active during its feasible interval (r_i,d_i ]

Sporadic Jobs in Dynamic priority System

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 ≤ 1 at all times

• This is the standard schedulability test for EDF systems, but including both periodic and sporadic jobs
• This test uses the density since deadlines may not equal periods; hence it is a sufficient test, but not a necessary test

This means:

• If we can bound the frequency with which sporadic jobs appear to the running system, we can guarantee that none are missed
• Alternatively, when a sporadic job arrives, if we deduce that the total density would exceed 1 in its feasible interval, we reject the sporadic job (admission control)

Real time performance of jobs with soft timing constraints

Traffic Models

Specifically, when requesting admission into the system, each sporadic task presents to the scheduler its traffic parameters. And the collection of these parameters are called the flow specification of the task in communications literature. They define the constraints on the inter-arrival times and execution times of jobs in the task. The performance guarantee provided by the system to each task is conditional which means that the system delivers the guaranteed performance conditioned on the fact that the task meets the constraints defined by its traffic parameters. The flip side is that if the task misbehaves (that is, its actual parameters deviate from its traffic parameters), the performance experienced by it may deteriorate. Different traffic models use different traffic parameters to specify the behavior of a sporadic tasks.

Leaky bucket model

We first introduce the notion of a (Λ, E) leaky bucket filter, then define the leaky bucket model. This kind of fillter is specified by its input rate Λ and size E: The filter can hold at most E tokens at any time and it is filled with tokens at a constant input rate of Λ tokens per unit time. A token is lost if it arrives at the filter if the filter already contains E tokens. It can be assumed of 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. After the release of this job, the e tokens are removed from the filter. A job cannot be released when the filter has no token. Therefore, not any job in a sporadic task that satisfies the (Λ, E) leaky bucket constraint, has execution time larger than E. The total execution time of all the jobs which are released within any time interval of length E/Λ is 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 satisfies the constraint if p’ = 1/ Λ and E = (1− p/p’)I/p’.

References

Liu, Jane W. S. Real Time Systems. Integre Technical Publishing Co., Inc, January 10, 2000. Print.