30-07-2012, 03:41 PM
Scheduling Slack Time in Fixed Priority Pre-emptive Systems
[attachment=29560]
Abstract
This paper addresses the problem of jointly scheduling
tasks with both hard and soft time constraints. We present
a new analysis which builds upon previous research into
slack stealing algorithms. Our analysis determines the
maximum processing time which may be stolen from hard
deadline periodic or sporadic tasks, without jeopardising
their timing constraints. It extends to tasks with
characteristics such as synchronisation, release jitter and
stochastic execution times, as well as forming the basis for
a family of optimal and approximate slack stealing
algorithms.
Introduction
In a recent paper [7], Lehoczky and Ramos-Thuel
presented a new approach to servicing aperiodic requests
within the context of a hard real-time system. Their
method, known as the Slack Stealer is applicable to
systems scheduled using a fixed priority pre-emptive
dispatcher, with priorities assigned according to a policy
such as the Rate Monotonic algorithm [11]. The Slack
Stealer addresses the problem of minimising the response
times of soft aperiodic tasks whilst guaranteeing that the
deadlines of hard periodics are met. In this paper, we
present new analysis which forms the basis of other more
generally applicable slack stealing algorithms.
Computational model and assumptions
In this paper, we consider the scheduling of n hard
deadline tasks on a single processor. The analysis given, is
however, equally applicable to multiprocessor systems
with a static allocation of tasks. Each task has a base
priority i where 1 £ i £ n, thus 1 is the highest priority
level and n the lowest. We use hp (i ) to denote the set of
tasks with a higher base priority than i and lp (i ) to denote
the tasks with base priority i or lower. Each task gives
rise to an infinite sequence of invocation requests,
separated by a minimal inter-arrival time Ti . Each
invocation of task i performs an amount of computation
between 0 and Ci (its bounded worst case execution time)
and has a deadline Di measured relative to the time of the
request.
Schedulability Analysis
In this section, we determine the maximum amount of
processing time which may be stolen from an invocation
of a hard deadline task without causing its deadline to be
missed.
For clarity, we initially assume that the task set
exhibits no synchronisation or release jitter and that each
invocation takes its worst case execution time. Further,
we assume that the deadline of each task is less than or
equal to its minimum inter-arrival time. In section 4, we
relax these assumptions.
[attachment=29560]
Abstract
This paper addresses the problem of jointly scheduling
tasks with both hard and soft time constraints. We present
a new analysis which builds upon previous research into
slack stealing algorithms. Our analysis determines the
maximum processing time which may be stolen from hard
deadline periodic or sporadic tasks, without jeopardising
their timing constraints. It extends to tasks with
characteristics such as synchronisation, release jitter and
stochastic execution times, as well as forming the basis for
a family of optimal and approximate slack stealing
algorithms.
Introduction
In a recent paper [7], Lehoczky and Ramos-Thuel
presented a new approach to servicing aperiodic requests
within the context of a hard real-time system. Their
method, known as the Slack Stealer is applicable to
systems scheduled using a fixed priority pre-emptive
dispatcher, with priorities assigned according to a policy
such as the Rate Monotonic algorithm [11]. The Slack
Stealer addresses the problem of minimising the response
times of soft aperiodic tasks whilst guaranteeing that the
deadlines of hard periodics are met. In this paper, we
present new analysis which forms the basis of other more
generally applicable slack stealing algorithms.
Computational model and assumptions
In this paper, we consider the scheduling of n hard
deadline tasks on a single processor. The analysis given, is
however, equally applicable to multiprocessor systems
with a static allocation of tasks. Each task has a base
priority i where 1 £ i £ n, thus 1 is the highest priority
level and n the lowest. We use hp (i ) to denote the set of
tasks with a higher base priority than i and lp (i ) to denote
the tasks with base priority i or lower. Each task gives
rise to an infinite sequence of invocation requests,
separated by a minimal inter-arrival time Ti . Each
invocation of task i performs an amount of computation
between 0 and Ci (its bounded worst case execution time)
and has a deadline Di measured relative to the time of the
request.
Schedulability Analysis
In this section, we determine the maximum amount of
processing time which may be stolen from an invocation
of a hard deadline task without causing its deadline to be
missed.
For clarity, we initially assume that the task set
exhibits no synchronisation or release jitter and that each
invocation takes its worst case execution time. Further,
we assume that the deadline of each task is less than or
equal to its minimum inter-arrival time. In section 4, we
relax these assumptions.