Probabilistic analysis and scheduling of critical soft real-time systems
Jane W. Liu, Mark K. Gardner · 1999
In addition to correctness requirements, a real-time system must also meet its temporal constraints, often expressed as deadlines. We call safety or mission critical real-time systems which may miss some deadlines critical soft real-time systems to distinguish them from hard real-time systems, where all deadlines must be met, and from soft real-time systems which are not safety or mission critical. The performance of a critical soft real-time system is acceptable as long as the deadline miss rate is below an application specific threshold. Architectural features of computer systems, such as caches and branch prediction hardware, are designed to improve average performance. Deterministic real-time design and analysis approaches require that such features be disabled to increase predictability. Alternatively, allowances must be made for their effects by designing for the worst case. Either approach leads to a decrease in average performance. Since critical soft real-time systems do not require that all deadlines be met, average performance can be improved by adopting a probabilistic approach. In order to allow a trade-off between deadlines met and average performance, we have developed a probabilistic analysis technique, call Stochastic Time Demand Analysis, for determining a lower bound on the rate at which deadlines are met in fixed priority systems. Allowing a real-time system to miss some deadlines in exchange for better average performance increases the possibility of overload. While overload in real-time systems has been studied, the emphasis has been on hard real-time systems in which overload is an exception whose occurrence is to be minimized. In contrast, critical soft real-time systems can be repeatedly overloaded during normal operation. Therefore, we have evaluated the performance of various real-time scheduling algorithms for critical soft real-time systems, including two new classes of algorithms, on workloads with execution and inter-release time variations, both with and without dependencies.