Jane W. S. Liu
Department of Computer Science,
University of Illinois
1304 West Springfield Avenue, Urbana, IL 61801
janeliu@cs.uiuc.edu,
http://pertsserver.cs.uiuc.edu/
New scheduling and resource management paradigms and open architectures can be used for mission-critical real-time applications only when we can validate and evaluate the timing properties of systems built on them. Unfortunately, existing validation technology is inadequate for future systems; new principles, theories and algorithms are critically needed.
Timing constraints of real-time applications may be specified in deterministic or probabilistic terms. The term validation refers to the process of demonstrating by some rigorous methods that all applications meet their timing constraints and guarantee the temporal quality of their services when integrated together and scheduled according to the algorithms used by the underlying operating system and networks. A validation algorithm is an efficient algorithm for this purpose. It is correct if it never declares that all timing constraints are met when some constraints may not be. A correct validation algorithm is good when it achieves a good balance in complexity, robustness and accuracy [1].
Existing validation algorithms have several serious limitations that prevent the algorithms and, therefore, the validation technology supported by them, unsuitable for future real-time systems. First, almost all of existing validation algorithms for event-driven systems are based on the periodic task model [2]. They are accurate only when variations in the time/resource demands of applications are small and the amounts of time/resource consumed by the underlying run-time environment are known. The algorithms are overly pessimistic when applied to sporadic applications that have widely varying time and resource demands.
Second, existing validation algorithms are only capable of dealing with deterministic timing constraints. Many existing algorithms for validating deterministic timing constraints can be extended in a natural way to deal with probabilistic time/resource demands and timing properties. (An example of such an extension can be found in [3].) However, the robustness of the probabilistic extensions remains to be determined.
Third, almost all existing algorithms for the validation of timing properties of multiprocessor and distributed systems are extensions of uniprocessor validation algorithms. They cannot be used to validate timing properties of dynamic multiprocessor and distributed systems. (In a dynamic system, tasks are not statically assigned and bound to processors. Instead, task instances ready for execution are placed in a common queue and are dispatched and scheduled on available processors in a priority-driven manner.)
Another critical problem to be addressed is concerned with the validation of dynamic systems. Almost all past work on schedulability conditions and validation focused on static systems in which tasks are assigned and bound to processors and are migrated among processors infrequently. Efficient and robust methods for validating dynamic, event-driven multiprocessor and distributed systems are not yet available. Because task execution times and release times may vary, the choice of the processor on which each task instance actually executes is nondeterministic. Numerous dynamic scheduling and load balancing algorithms are available and are likely to have better performance than static approaches. The lack of robust and accurate methods to validate timing properties of the resultant dynamic system has hindered their adoption for hard real-time applications. Some preliminary results in this problem area now exist [4], but most of the problems in validating dynamic event-driven systems remain to be solved.