CERT-SEI

Worst-Case Latency Prediction

Although analysis theories for worst-case analysis have existed for many years, they are not widely used because of the resources and expertise required to create, maintain, and evaluate the analysis models. Consequently, developers usually rely on testing to verify the satisfaction of timing requirements, incurring expensive overruns when they are not met. Combining analysis theories, interpretation from designs to analysis models, and automated model evaluation, a reasoning framework [1] can ease the adoption of sound analysis theories by making their use simpler and more cost-effective.

Thus far, the PBC team had focused its efforts for performance prediction capability on average-case latency. The LambdaABA [2] and LambdaSS [3] reasoning frameworks were developed to predict average response time of periodic tasks, and aperiodic tasks scheduled by a sporadic server respectively. The latest work in PBC extended the suite of performance reasoning frameworks to include worst-case latency prediction with Rate Monotonic Analysis (RMA) [4].

The LambdaWBA reasoning framework has an automated interpretation that transforms a component-based design into a performance model suitable for analysis with RMA, and an automated evaluation procedure that makes use of MAST [5], a tool that implements the RMA technique for tasks with varying priorities [4]. RMA needs responses to events to be modeled as linear sequences of subtasks that execute one after the other. However, the response to an event in component-based designs is usually implemented by an assembly of components connected synchronously or asynchronously, resulting in constructs that are not linear sequences in the component and connector view of the design. This mismatch is addressed by the automated interpretation. By exploiting the knowledge of priority assignments and the connectors’ semantics, the interpretation can transform these non-linear responses into linear ones that can then be analyzed with RMA.

The LambdaWBA reasoning framework was implemented as part of the PACC Starter Kit (PSK), and is easily accessible to users through a wizard dialog that allows them to select some analysis options. The PSK performs the interpretation to a generic performance model, generates a description of the model in modeling syntax of MAST, and then launches MAST to carry out the analysis. The results computed by MAST include the best- and worst-case latency for each task (or response to an event), and whether the deadlines were met or not.

Validation

An important step in the process of developing a reasoning framework is its validation. The validation measures how good the predictions of a reasoning framework are by comparing them against measurements obtained from the actual execution of the application. In addition, the validation process produces an estimate of the prediction accuracy in future uses of the reasoning framework. This information is summarized for the consumers of a reasoning framework in a statistical label [6]. The validation process and its instantiation for LambdaABA are described in [2]. For LambdaWBA, the same steps were followed, albeit the implementation of some of them had to address peculiarities of worst-case analysis (see discussion about component WCET certification).

The validation goal was defined as being able to successfully predict 95% of the assemblies on which the reasoning framework is used, where an assembly is successfully predicted if the worst observed latency of each of its tasks does not exceed the predicted worst-case latency. In the LambdaABA validation, predicted average latency was compared with observed average latency and the magnitude of relative error (MRE) was used as a measure of accuracy of the prediction. In worst-case validation, MRE cannot be used in the same way because RMA computes an upper bound for the worst-case, a worst-case that could happen only if several factors exhibited their worst behavior simultaneously (e.g., worst task phasing and worst case execution time for several components). Since that situation may not be possible in some systems, it is possible that the observed worst-case latency never reaches the predicted upper bound. For this reason, a binary pass/fail outcome was used instead of the continuous MRE. Nevertheless, the measurement procedure was defined in a way that would make the actual execution of the system to show some of the conditions required for the theoretical upper bound. First, the components in the validation assemblies were designed to always take the same execution time. 

Barring a small relative error mostly due background host operating system processing1, there is no considerable difference between average and worst execution for the validation components. In that way, the components execute close to the worst-case by design. Second, and most importantly, all the tasks were aligned so that they started as close as the runtime environment permits it, creating a situation close to the worst phasing. Another important part of the measurement procedure is determining for how long the assembly needs to be measured. Given that the worst phasing was created, the RMA formulas were used to compute the longest busy period for the assembly, and taking into account that the worst case must happen in a busy period that starts at a critical instant (i.e., a instant in which jobs for all the tasks are initiated simultaneously), it was sufficient to measure the assembly for the length of the longest busy period.

The rest of the validation process was followed as described in [2], although the tools used had to be adapted or rewritten to accommodate the new runtime environment.

1Although the Pin/RTOS runs as a single Win32 process executing at REALTIME_PRIORITY_CLASS, it is still perturbed by host OS processing. Future work will look at reducing this interference.

References

[1] Bass, L., Ivers, J., Klein, M, and Merson, P. Reasoning Frameworks. CMU/SEI-2005-TR-007, Software Engineering Institute, Pittsburgh, PA, 2005.

[2] Hissam, S.; Hudak, J.; Ivers, J.; Klein, M.; Larsson, M.; Moreno, G.; Northrop, L.; Plakosh, D.; Stafford, J.; Wallnau, K.; & Wood, W. Predictable Assembly of Substation Automation Systems: An Experiment Report, Second Edition (CMU/SEI-2002-TR-031, ADA418441). Pittsburgh, PA: Software Engineering Institute, Carnegie Mellon University, 2003. 

[3] Hissam, S.; Klein, M.; Lehoczky, J.; Merson, P.; Moreno, G.; & Wallnau, K. Performance Property Theories for Predictable Assembly from Certifiable Components (PACC) (CMU/SEI-2004-TR-017). Pittsburgh, PA: Software Engineering Institute, Carnegie Mellon University, 2004. 

[4] Klein, M.; Ralya, T.; Pollak, B.; Obenza, R.; & González Harbour, M. A Practitioner's Handbook for Real-Time Analysis: Guide to Rate Monotonic Analysis for Real-Time Systems. Boston, MA: Kluwer Academic Publishers, 1993.

[5] M. Gonzalez Harbour, J.J. Gutierrez Garcia, J.C. Palencia Gutierrez, J.M. Drake Moyano, MAST: Modeling and Analysis Suite for Real Time Applications, ECRTS, p. 0125, 13th Euromicro Conference on Real-Time Systems (ECRTS'01), 2001. 

[6] Moreno, G.; Hissam, S.; & Wallnau, K. Statistical Models for Empirical Component Properties and Assembly-Level Property Predictions: Toward Standard Labeling. Proceedings of the 5th International Workshop on Component-Based Software Engineering, in conjunction with the 24th International Conference on Software Engineering (ICSE2002). Orlando, Florida, May 19-20, 2002. 

SEI Blog