Quantifying the Effect of Rare Timing Events with Settling-Time and Overshoot

Pratyush Kumar and Lothar Thiele.
In Proceedings of the 33rd Real-Time Systems Symposium, RTSS 2012, San Juan, Puerto Rico, December 2012. IEEE.
For hard real-time systems, worst-case timing models are employed to validate whether timeliness properties, such as meeting deadlines, are always satised. We argue that such a deadline interface should be generalised in view of two separate motivations: (a) applications can tolerate bounded non-satisfaction of timeliness properties due to inherent ro- bustness or relaxed quality requirements, and (b) worst-case timing models do not expose the occurrence of certain rare yet predictable events. As a more expressive interface, we propose the Rare-Event with Settling-Time (REST) model wherein, during rare events nominal timing models can be violated up to a known bound. Such a violation may lead to non-satisfaction of the timeliness properties up to a certain bound. We characterise this bound in terms of (a) the longest interval when the deadlines are not met, which we call the settling-time, and (b) the maximum number of jobs that can miss deadlines during the settling-time called the overshoot. We propose two models of rare events, characterised on an interval domain. For a single stream of jobs, we provide methods to tightly compute the settling-time and overshoot. For multiple streams of jobs on a single processor, we show that amongst schedulers agnostic to the occurrence of the rare event, the EDF scheduler optimally minimises the settling-time. In contrast, RM is not optimal within the class of xed priority schedulers.