The constant utilization server and total bandwidth server are used to assign some fraction of processor capacity to an aperiodic task. During assignment of task, there is an issue of fairness and starvation i.e. the fairness cannot maintained in case of total bandwidth and constant utilization server approach. A scheduling algorithms is fair with in any particular time interval if fraction of processor time in the interval attained by each backlogged server is proportional to size of server.
In such system not only all the task meet their deadlines, but they all make a continuous process according to their share of processor and there is no starvation. The waited fair queuing algorithms are used to share processor time between sever and designed to ensure fairness is allocation among multiple servers.
It consumes budget when it executed. Replenishment Rule:
- Its budget is replenishment when it first becomes backlogged after being idle.
- As long as it is backlogged, its budget is replenished each time it completes a job.
- At each replenished time, the server budget is set to the execution time of the job at the head of queue.
Slack Stealing in Deadline Driven System:
- The slack stealer is a periodic server to execute aperiodic job using slack time.
- The slack stealer is ready for execution whenever the aperiodic job queue is nonempty and is suspended when the queue is empty.
- The scheduler monitors the periodic tasks in order to keep track of amount of available slack.
- Whenever the slack stealer executes, it executes the aperiodic job at the head of aperiodic job queue.
- This kind of slack stealing algorithms is said to be greedy and non-optimal.
- The available slack is always used if there is an aperiodic job ready to be executed.
- 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
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.
- Initially, the slack stealer is suspended because the aperiodic job queue is empty. When A1 arrives at 2.8, the slack stealer resumes. Because the execution of the last 0.7 units of J1, 1 can be postponed until time 8 (i.e., 5.5−0.7) and T2 has no ready job at the time, the system has 2 units of slack. The slack stealer is given the highest priority. It preempts J1, 1 and starts to execute A1. As it executes, the slack of the system is consumed at the rate of 1 per unit time.
- At time 4.5, A1 the slack stealer is suspended. The job J1, 1 resumes and executes to completion on time.
- At time 5.5, A2 arrives, and the slack stealer becomes ready again. At this time, the execution of the second job J1, 2 of T1 can be postponed until time 5, and the second job J2, 2 of T2 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 A2.
- At time 7.5, all the slack consumed, the slack stealer is given the lowest priority. J1, 2 preempts the slack stealer and starts to execute.
- At time 9, J1, 2 completes, and the system again has slack. The slack stealer now has the highest It continues to execute A2.
- When A2 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.