Lambda-star Reasoning Frameworks

 

What is Lambda-star?

Lambda-star is a suite of performance reasoning frameworks founded on the principles of General Rate Monotonic Analysis (GRMA) [1] for predicting the average and worst-case latency of periodic and stochastic tasks in what is typified as embedded, real-time control systems.

Developed first, the Lambda_ABA reasoning framework focused on control systems in which all tasks are periodic, composed of components with varying priorities, and optionally including asynchronous interactions among them.

The Lambda_SS reasoning framework (the second performance reasoning framework) supports predicting average-case latency of tasks having softer deadlines with stochastic (non-periodic) event interarrivals. These stochastic tasks can be part of control systems with periodic hard deadlines because their invasivness on the hard real-time part of the system is bounded by the use of the sporadic server algorithm [2] .

The Lambda_WBA reasoning framework (latest in the series) predicts worst-case latency on hard real-time control systems with tasks composed of components with varying priorities, and optionally including asynchronous interactions among them.

The latest work of the PACC performance team has been addressing the predictability of systems with a mix of hard and soft real-time tasks. Whereas missing a deadline in the former can result in catastrophic failures, missing a deadling in the latter only results in a degraded quality of service (QoS). We are currently developing a reasoning framework based on Real-Time Queueing Theory (RTQT) [3] to predict latency in this class of systems.

Using Lambda-star

Lambda-star can be applied to many different, non-distributed, uniprocessor, control systems (e.g., avionic, automotive, robotic) having a mix of tasks with hard and soft deadlines with periodic and stochastic event interarrivals. Lambda-star is intended for use with a development approach that is based on prediction-enabled component technology (PECT).

Automation is central to the theme of using PECT, and the Lambda-star reasoning framework holds true to that theme. From automated interpretation to generate model representations of well-formed assemblies to automated evaluation procedures using simulations and numeric solvers, the validated Lambda-star reasoning frameworks produce predictions that can be objectively trusted.

Additional Information

Want to know more? Read about our latest work and uses of the Lambda-star reasoning frameworks.

• Lambda_WBA  in an industrial setting
• Certifying worst case execution time estimates
• Worst-case latency prediction with Lambda_WBA
• A reasoning framework for mixed hard and soft real-time tasks
• Use of Lambda_ABA in substation automation systems
• Application of Lambda_SS on industrial robot control

References

[1] Klein, M.; Ralya, T.; Pollak, B.; Obenza, R.; & Gonzalez 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.

[2] Sprunt, B. Scheduling Sporadic and Aperiodic Events in a Hard Real-Time System (CMU/SEI-89-TR-011, ADA211344). Pittsburgh, PA. Software Engineering Institute, Carnegie Mellon University, 1989.

[3] Doytchinov, B.; Lehoczky, J. P.; & Shreve S. "Real-Time Queues in Heavy Traffic with Earliest-Deadline-First Queue Discipline." Annals of Applied Probability 11, 2 (May 2001): 332-378.