Dynamic Time-Based Scheduling for Hard Real-Time Systems
Dynamic Time-Based Scheduling for Hard Real-Time Systems
Files
Publication or External Link
Date
1998-10-15
Authors
Choi, Seonho
Advisor
Citation
DRUM DOI
Abstract
In traditional time-based scheduling schemes for real-time systems
time line is explicitly managed to obtain a feasible
schedule that satisfies all timing constraints.
In the schedule the task attributes, such as task start time,
are statically decided off-line and used without modification
throughout system operation time.
However, for dynamic real-time systems, in which new tasks may arrive
during the operation, or tasks may have relative constraints
based on information only known at run-time, such static schemes
may lack the ability to accommodate dynamic changes.
Clearly a solution of dynamic real-time scheduling has to reflect
the knowledge about tasks and their execution characteristics.
In this dissertation we present a {\em dynamic time-based scheduling
scheme} and show its applicability for three problem domains.
In dynamic time-based scheduling scheme attributes
of task instances in the schedule may be represented as
functions parameterized with information available
at task dispatching time. These functions are called {\em attribute
functions} and may denote any attribute of a task instance, such as
lower and upper bound of its start time, its execution mode, etc.
Flexible resource management becomes possible in this scheme
by utilizing the freedom provided by the scheme.
First, we study the problem of dynamic dispatching of tasks, reflecting
relative timing constraints among tasks. The relative
constraints may be defined across the boundary of two consecutive scheduling
windows as well as within one scheduling window.
We present the solution approach with which we are not only able to
test the schedulability of a task set, but also able to obtain
maximum slack time by postponing static task executions at run-time.
Second, new framework is formulated for designing real-time control systems
in which the assumption of fixed sampling period is relaxed.
That is, sampling time instants are found adaptively based on physical
system state such that a new cost function value is minimized
which incorporates computational costs.
We show, for linear time-invariant control systems, that the computation
requirement can be reduced while maintaining the quality of control.
Third, acceptance tests are found for dynamically arriving aperiodic tasks,
and for dynamically arriving sporadic tasks, respectively, under the
assumption that an Earliest Deadline First scheduling policy
is used for resolving resource contention between
dynamic and static(dynamic) tasks.
Dynamic time-based scheduling scheme can be applied as solution approaches
for these problems as will be shown in this dissertation, and its
effectiveness will be demonstrated.
Also cross-referenced as UMIACS-TR-97-81