Algorithms for Scheduling Aperiodic Jobs
There are two types of aperiodic job scheduling algorithms. They are bandwidth-preserving algorithms and slack-stealing algorithms.
Bandwidth-Preserving Algorithms. According to a bandwidth-preserving algorithm, aperiodic jobs are executed by one or more servers; each bandwidth-preserving server emulates one or more periodic tasks or a sporadic task. Bandwidth-preserving algorithms can tolerate release-time jitters of periodic tasks. Many of them are simple to implement. Deferrable Server. The budget of a deferrable server (ps , es) is set to es at time instants kps, for k = 0, 1, 2, . . . . The server consumes its budget only when it executes. Such a server emulates a periodic task whose execution may be suspended and deferred.
Sporadic Server. Such a server emulates several periodic tasks when its budget is broken up into chunks to be replenished at different times.We ncan account for the effect of a sporadic server on schedulability of periodic tasks by treating the server as a periodic task or several periodic tasks with period ps and total execution time es .
Constant Utilization and Total Bandwidth Servers. A constant utilization server emulates a sporadic task that has a constant instantaneous utilization. It can be used only in deadline-driven systems. A total bandwidth server is an enhanced constant utilization server that is allowed to claim the background time not used by periodic tasks. The total size of all the constant utilization and total bandwidth servers in a system of independent, preemptable periodic tasks whose total density is must be no greater than 1 − . When this condition is satisfied, the worst-case response times of jobs executed by such a server depend only on the size of the server and can be determined independent of the workload executed by other servers in the system.
Weighted Fair-Queueing Server. For many applications, it is important that the scheduling algorithm be fair. The total bandwidth server algorithm is not fair; a server can be starved for an arbitrary amount of time. The weighted fair-queueing algorithm does not have this problem and can achieve the same worst-case response time as the total bandwidth server algorithm. The nonpreemptive version of this algorithm is also called packet-by-packet generalized processor sharing algorithm and is for scheduling transmissions of packets in switched networks.
Slack-Stealing Algorithms. In a system that does slack stealing, the scheduler schedules aperiodic jobs whenever the periodic tasks and sporadic jobs in the system have slack, that is, their execution can be safely postponed without causing them to miss their deadlines.
The scheduling overhead of slack-stealing is primarily the time spent to do slack computations: the work that the scheduler must do to determine how much slack the system has at each scheduling decision time. This overhead is O(N), where N is the number of periodic jobs in a busy interval or hyperperiod, when the scheduler does slack computations dynamically without making use of precomputed slack information. In a system of n periodic tasks, the overhead can be reduced to O(n) if the scheduler uses static computation, that is, it computes the current slack from the precomputed initial slack. The limitation of static slack-stealing algorithms is that they can be used only when the release-time jitters of periodic tasks are negligible.When they can be used, however, the slack-stealing algorithms typically offer better performance than bandwidth-preserving algorithms, especially when the total utilization of periodic tasks is large (e.g., 75% or larger).
