Real-time Scheduling on Identical
Multiprocessors
The Challenge. As real-time
computer application systems become larger and more complex, it is
becoming imperative that such applications be implemented on
multi-processor platforms rather than on uniprocessor ones. We are
studying the fundamental scheduling-theoretic questions that arise in
the design & specification, implementation, and formal verification of
real-time applications upon multi-resource platforms.
The Approach. We are studying the
problem from several different perspectives:
- It is known that no on-line scheduling
algorithm can be optimal upon multiprocessors. We are studying these
inherent limitations, and are exploring techniques (such as resource augmentation) that can be used to bypass
these limitations to achieve acceptable performance.
- We are exploring the computational
complexity of determining whether real-time systems specified
in certain popular models (e.g., the periodic task model) can
be scheduled to meet all deadlines upon specified multiprocessor
platforms.
- The earliest deadline first scheduling algorithm (EDF) is very commonly used in uniprocessor
real-time systems. We are developing the algorithms and analysis
tools necessary to be able to apply EDF to multiprocessor
systems.
Associated Personnel.
Funding provided by: The National Science Foundation
Last updated on 2001/11/27 by SkB.