Hardware Reference
In-Depth Information
When the load is controlled by job rejection, a reclaiming mechanism can be used to
take advantage of those tasks that complete before their worst-case finishing time. To
reclaim the spare time, rejected tasks will not be removed, but temporarily parked in a
queue, from which they can be possibly recovered whenever a task completes before
its worst-case finishing time.
In the real-time literature, several scheduling algorithms have been proposed to deal
with transient overloads in event triggered systems. Ramamritham and Stankovic
[RS84] used EDF to dynamically guarantee incoming work via on-line planning.
Locke [Loc86] proposed a best effort algorithm using EDF with a rejection policy
based on tasks value density. Biyabani et. al. [BSR88] extended the work of Ra-
mamritham and Stankovic to tasks with different values, and various policies were
studied to decide which tasks should be dropped when a newly arriving task could not
be guaranteed. Haritsa, Livny, and Carey [HLC91] presented the use of a feedback-
based EDF algorithm for real-time database systems.
In real-time Mach [TWW87] tasks were ordered by EDF and overload was predicted
using a statistical guess. If overload was predicted, tasks with least value were dropped.
Other general results on overload in real-time systems were also derived. For ex-
ample, Sha [SLR88] showed that the Rate-Monotonic algorithm has poor properties
in overload. Thambidurai and Trivedi [TT89] studied transient overloads in fault-
tolerant real-time systems, building and analyzing a stochastic model for such sys-
tems. Schwan and Zhou [SZ92] did online guarantees based on keeping a slot list and
searching for free-time intervals between slots. Once schedulability is determined in
this fashion, tasks are actually dispatched using EDF. If a new task cannot be guaran-
teed, it is discarded.
Zlokapa, Stankovic, and Ramamritham [Zlo93] proposed an approach called
well-
time scheduling
, which focuses on reducing the guarantee overhead in heavily loaded
systems by delaying the guarantee. Various properties of the approach were developed
via queueing theoretic arguments, and the results were a multilevel queue (based on
an analytical derivation), similar to that found by Haritsa et al. [HLC91] (based on
simulation).
In the following sections we present two specific examples of scheduling algorithms
for handling overload situations and then compare their performance for different peak
load conditions.
Search WWH ::
Custom Search