TI An Integrated Approach to Dynamic Task and Resource Management 
                 in Multiprocessor Real-Time Systems 

LT COINS TR 92-65  
AU Chia Shen 
YR 1992 
MN September 
OR UMASS 
AB An Integrated Approach to Dynamic Task and Resource Management 
in Multiprocessor Real-Time Systems Keywords:  deadlines, dynamic
real-time systems, multiprocessor  scheduling, resource
constraints, resource reclaiming,  worst case execution  times.
In a dynamic real-time environment, predictability needs to be
provided in the face of unpredictable dynamic task arrivals and 
asynchronous concurrent sharing of system resources.
Consequently,  the underlying computer system for dynamic
real-time systems needs  to manage time explicitly as a resource
in order to support  applications' timing constraints. Such time
management requires that  the system be time conscious, time
conscientious, and time conserving. These three properties
encompass the complexity, correctness and  performance issues of
algorithms designed for a dynamic real-time system. In this
thesis, we present an integrated approach to attack the problems
of algorithm design for dynamic multiprocessor real-time  systems
that require these three pperties in the context of ON-LINE 
SCHEDULING, DISPATCHING,and RESOURCE RECLAIMING. Real-time
scheduling algorithms require the use of worst case execution
times of tasks. However, the worst case execution time is  an
upper bound, and the actual execution time of a task at run time 
varies between some minimum value and this upper bound due to the 
variabilities inherent in both the computer architecture and the 
software. The problem of on-line resource reclaiming in a multi-
processor real-time system has not been addressed previously. The 
research presented in this dissertation represents an INITIATIVE
effort in characterizing and solving this dynamic resource
reclaiming  problem. We analyze the worst case run time anomalies
that can occur in a multiprocessor schedule where real-time tasks
have both resource  and processor constraints. We have developed
two resource reclaiming  algorithms that are correct ---
guaranteed not to cause run time  anomalies, and have bounded
complexity. The effectiveness of te algorithms has been
demonstrated via simulation and implementation on  a
multiprocessor kernel. Predictable integration of multiple
functional components is a challenge unique to real-time systems.
This challenge is exacerbated  by the difficulties brought about
by the concurrent and asynchronous  nature of multiprocessor
systems. We demonstrate that, for a dynamic  real-time system, it
is not sufficient to simply analyze and prove the static
properties of an on-line algorithm in isolation of the rest of 
the system components. The sharing and contention of resources,
such  as memory, shared system bus, and more importantly time,
require the  algorithm designer to take an integrated view of the
system as a whole, considering the interrelationships of all the
system components (be it software, or hardware) that have an
effect on the dynamic timing  properties of the algorithm at
hand. We discuss a predictable  integration of
scheduling,dispatching, and resource reclamation for a 
distributed memory real-tim mltiprocessor system. ______________
This work is funded in part by the Office of Naval Research under
contracts N00014-85-K-0398 and N00014-92-J-1048, and by the
National  Science Foundation under equipment grants DCR-8500332
and CCR-8716858.