Scheduling Optional Computations for Adaptive Real-Time Systems

At present, the critical computations of real-time systems are guaranteed before run-time by performing a worst-case analysis of the system's timing and resource requirements. The result is that real-time systems are engineered to have spare capacity, under normal operation. A challenge of current research is to make use of this spare capacity, in order to satisfy requirements for adaptivity in the system. Adaptivity can be implemented by optional computations with firm deadlines, which can be guaranteed at run-time by the use of flexible scheduling. This report assumes that the algorithms which attempt to guarantee optional computations at run-time, actually run on the same processor as the optional and critical computations themselves. The report starts with a brief survey of the complex requirements for adaptivity within real-time systems. Such requirements can include task hierarchies composed of interdependent subtasks each with its own utility. Evidence is cited which indicates that the run-time support for a computational model which supports all such requirements, would incur overheads so large, that little spare capacity would remain for the optional computations themselves. Following this, the report presents a constrained computational model, which, it is claimed, could be cost-effectively supported at run-time. The model is nevertheless general enough to satisfy many of the requirements for adaptivity. The constrained model uses Best Effort Admissions Policy to arbitrate between three categories of optional computation, each with its own utility level. The viability of the constrained model is demonstrated by simulation studies which compare the performance of the model to that of First-Come-First-Served Admissions Policy.