The Real-Time Computing Laboratory, Web QoS Group

Aperiodic Real-Time Scheduling Theory

Sponsor: NSF

Real-time scheduling theory is perhaps one of the most studied and well understood aspects of real-time computing. However, the current state of the art is far from being complete. One of the big gaps in the theoretical underpinnings lie in our inability to relate aggregate performance metrics (such as utilization) to per-task temporal metrics (such as response time) except in some restricted special cases (such as that of scheduling periodic tasks). Unfortunately, the periodicity restrictions are severe enough to prevent the application of known results (such as the Liu and Layland bound) in a vast majority of application scenarios where task arrival patterns are unknown.

In this research effort we are concerned with bridging the gap between per-task performance and aggregate performance in an environment where nothing is known about the task arrival pattern. With theoretical tools to infer the former from the latter we can determine acceptable ranges for aggregate performance and use these to control the aggregate performance such that the desired temporal behavior is produced for individual clients. The result is per-client real-time performance guarantees without detailed knowledge of per-client execution parameters.

Most scheduling problems are NP-complete, which typically calls for heuristic solutions. We demonstrate that computationally tractable ``optimal'' solutions to the general problem of distributed resource constrained communicating task allocation and scheduling are also possible if the search space is appropriately defined and the search algorithm has certain desirable properties. This is reported in the papers below.
Last modified: Wed Aug 1 08:12:15 2001