First, we study hard real-time scheduling problems where each task is defined
by a four tuple (r, c, p, d): r being its release time, c computation time, p
period, and d deadline. The question is whether all tasks can meet their
deadlines on one processor. If not, how many processors are needed?
For the one-processor problem, we prove two sufficient conditions for a
(restricted) periodic task set to meet deadlines. The two conditions can be
applied to both preemptive and non-preemptive scheduling, in sharp contrast
to earlier results. If a periodic task set can meet deadlines under any algorithm
which does not idle the processor as long as there are tasks ready to execute, it
must satisfy our second condition. We also prove a necessary condition for a
periodic task set to meet deadlines under any scheduling algorithm.
We present a method for transforming a sporadic task to an equivalent
periodic task. The transformation method is optimal with respect to non-preemptive
scheduling. With this method, all results on scheduling periodic
task sets can be applied to sets of both periodic and sporadic tasks.
For the scheduling problem in distributed memory systems, we propose
various heuristic algorithms which try to use as few processors as possible to
meet deadlines. Although our algorithms are non-preemptive, our simulation
results show that they can outperform the heuristic algorithms based on the
famous preemptive rate monotonic algorithm in terms of the number of used
processors and processor utilization rate.
Second, we describe a hard real-time software development environment,
called HaRTS, which consists of a design tool and a scheduling tool. The design
tool supports a hierarchical design diagram which combines the control and
data flow of a hard real-time application. The design diagram is quite intuitive,
and yet it can be automatically translated into Ada��� code and analyzed for
scheduleability. The scheduling tool schedules precedence-constrained
periodic task sets and simulates the task execution with highly animated user
interfaces, which goes beyond the traditional way of examining a schedule as
a static Gantt chart. / Graduation date: 1994
| Identifer | oai:union.ndltd.org:ORGSU/oai:ir.library.oregonstate.edu:1957/35686 |
| Date | 16 November 1993 |
| Creators | Zhu, Jiang |
| Contributors | Lewis, Theodore G. |
| Source Sets | Oregon State University |
| Language | en_US |
| Detected Language | English |
| Type | Thesis/Dissertation |
Page generated in 0.002 seconds