Scheduling and Allocation in Multiprocessor Systems
Scheduling and Allocation in Multiprocessor Systems
Loading...
Files
Publication or External Link
Date
1998-10-15
Authors
Cheng, Sheng-Tzong
Advisor
Citation
DRUM DOI
Abstract
The problem of allocation has always been one of the fundamental issues of
building applications in multiprocessor systems. For real-time applications,
the allocation problem should directly address the issues of task and
communication scheduling. In this context, the allocation of
tasks has to fully utilize the available processors and the scheduling
of tasks has to meet the specified timing constraints. Clearly,
the execution of tasks under the allocation and schedule has to satisfy
the precedence, resources, and synchronization constraints.
Traditionally time constraints for real-time tasks have been specified
in terms of ready time and deadlines. Many application tasks have relative
timing constraints in which the constraints for the execution of a task
are defined in terms of the actual execution instances of prior tasks.
In this dissertation we consider the allocation and scheduling problem of
the periodic tasks with relative timing requirements. We take a time-based
scheduling approach to generate a multiprocessor schedule for a set of
periodic tasks. A simulated annealing algorithm is developed as the
overall search algorithm for a feasible solution. Our results show that
the algorithm performs well and finds feasible allocation and scheduling.
We also investigate how to exploit the replication technique to increase
the schedulability and performance of the systems. In this dissertation,
we adopt the computation model in which each task may have more than one
copy and a task may start its execution after receiving necessary data
from a copy of each of its predecessors. Based on this model,
replication techniques are developed to increase the schedulability of the
applications in real-time systems and to reduce the execution cost of
the applications in non-real-time systems.