MAST: A Comprehensive Tool Suite for Real-Time Systems Analysis and Optimization

Real-time systems are special embedded systems that must respond to external events within a strict timeframe. They are the backbone of many critical applications, from industrial automation and automotive systems, to avionics and medical devices. In these domains, a delayed response can have serious consequences, ranging from production downtime to life-threatening situations.

The most crucial aspect of a real-time system is its predictability: it must guarantee that tasks will be completed within their deadlines, even under worst-case scenarios. This requires careful analysis and design, considering factors such as task execution times, scheduling policies, and resource constraints. Consequently, the design of a real-time system must always be supported by a mathematical framework that ensures temporal correctness, in addition to the necessary testing to verify functional correctness as in any other computing system.

MAST is an open-source suite of tools that provides such type of mathematical framework for analyzing and optimizing schedulability of real-time systems at the design stage. It offers a range of functionalities, from assessing the timing behavior of individual tasks to evaluating the overall system’s ability to meet deadlines. By providing insights into potential bottlenecks and performance issues, MAST empowers developers to make informed design decisions and ensure the reliability of their real-time applications.

MAST comprises two main aspects:

• A System Model to describe real-time systems
• The MAST Analysis Tool that ingests such system descriptions, and executes the analytical tools on them, for example to determine the temporal correctness of the system.

The following figure illustrates the workflow of the MAST Analysis tool. Initially, the tool receives a system description as input, which it parses and validates for consistency and restrictions. Optionally, it is possible to automatically assign scheduling parameters such as priorities, followed by the calculation of blocking times. The tool then performs a schedulability analysis based on the assigned parameters and calculated blocking times. From this analysis, the tool can determine if all the deadlines will be met in the worst-case scenario. Finally, analytical results are printed, and the user has the option to generate a result file and a new system description incorporating the updated scheduling parameters.

The following sections provide a deeper description of the MAST model and analysis tool.

MAST System Description

At the heart of the MAST tool suite is the MAST model, which describes the timing behavior of real-time applications. The first version of this model, MAST-1, is the one currently supported by the MAST Analysis Tool. We are now evolving into MAST-2, the second version of our model, which leverages the Eclipse Modeling Framework. The following description pertains to MAST-1. Details about the MAST-2 model and its interaction with MAST-1 are provided in the separate “Model-Driven Support” section.

MAST allows modeling both single-processor and complex distributed systems. It is an event-driven model which separates the system into several views, to ease composition of models and systems:

• Platform view, including processors, networks and their schedulers
• Schedulable Entities view, including scheduling servers (i.e., threads) and message streams
• Software Modules view, which models the code that is being executed, including the access to shared resources, and the contents of the messages being transmitted.
• Real-time Situation view, which includes the schedulable entities called Activities (i.e., Tasks), that involve the execution of an operation by a scheduling server. Activities are triggered by the arrival of an event, which could be external, or sent by another activity (internal event). This setup allows forming transactions (i.e., end-to-end flows) of activities. Internal events can be assigned a Timing Requirement (e.g., a deadline). The following figure shows a diagram of a transaction composed of 5 activities.

The MAST model includes the possibility of having multipath transactions where an end-to-end flow can be divided into several paths with fork (multicast) or branch (delivery or query server) elements. Paths may be joined with join (barrier) or merge (concentrator) elements.

The MAST-1 System Description and Results files are specified through an ASCII description that serves as the input and output respectively of the MAST Analysis Tool. Two ASCII formats are defined: a custom textual format and an XML-based format. The XML format provides the designer with capabilities to use free standard XML tools to validate, parse, analyze, and display the model files. MAST provides a converter tool to automatically translate between both formats.

While MAST-1 models can be programatically created, MAST also provides a visual editor to create and edit system descriptions.

MAST Analysis Tool

The MAST Analysis Tool includes worst-case Response Time Analysis (RTA) techniques for single-processor and distributed systems. It checks whether the worst-case behavior always meets the hard real-time requirements. MAST provides several RTA techniques, with varying degrees of precision, computational complexity and system characteristics support.

For systems scheduled by Fixed Priorities (FP), the following RTA techniques are supported for each type of system (checkmarks redirect to the source material):

	Single-Processor	Multi-Processor	Simple Transaction	Linear Transaction	Multipath Transaction
Classic Rate Monotonic	✅		✅
Varying Priorities		✅	✅
Holistic	✅	✅	✅	✅	✅
Offset Based	✅	✅	✅	✅	✅
Offset Based Slanted	✅	✅	✅	✅	✅
Offset Based w/Precedences	✅	✅	✅	✅
Offset Based Brute-force	✅	✅	✅	✅	✅

For systems scheduled by Earliest Deadline First (EDF), the following response-time analysis techniques are supported for each type of system (checkmarks redirect to the source material):

	Single-Processor	Multi-Processor	Simple Transaction	Linear Transaction	Multipath Transaction
Single Processor	✅		✅
EDF Within Priorities	✅		✅
Holistic Local	✅	✅	✅	✅	✅
Holistic Global	✅	✅	✅	✅	✅
Offset Based Local	✅	✅	✅	✅
Offset Based Global	✅	✅	✅	✅
Offset Based w/Precedences Local	✅	✅	✅	✅

The MAST Analysis tool also provides a set of Scheduling Parameters Assignment techniques to assign fixed priorities or scheduling deadlines for systems scheduled by the EDF scheduling policy. The following table provides an overview of these techniques and the types of systems they support (checkmarks redirect to the source material):

	Single-Processor	Distributed/Multi-Processor
Deadline Monotonic	✅ (D<T)
Audsley’s OPA	✅ (D>T)
PD	✅ (FP and EDF)	✅ (FP and EDF)
NPD	✅ (FP and EDF)	✅ (FP and EDF)
Simulated Annealing	✅ (FP)	✅ (FP)
HOSPA	✅ (FP and EDF)	✅ (FP and EDF)

Beyond being able to determine whether a system is schedulable or not, MAST is also able to perform a sensitivity analysis to measure how far a system is from being schedulable, or how much capacity is available until the system becomes unschedulable. It does so by calculating slacks, which are defined as the percentage by which we can increase the execution times of some operations while keeping the system schedulable (for positive slacks) or the percentage by which we have to decrease the execution times to make the system schedulable (for negative slacks).

Additionally, MAST implements the calculation of blocking times for local mutual exclusion resources, remote blockings for global resources, and the assignment of optimum priority ceilings and preemption levels.

Model-driven support

While the MAST Analysis Tool natively supports the MAST-1 file format, we are in the process of defining the next iteration of the model, called MAST-2. MAST-2 is built within the Eclipse Modeling Framework (EMF), which provides a rich ecosystem of modeling tools and allows for a greater interoperability with existing third party system descriptions.

MAST-2 offers a similar structure to that offered by MAST-1, with the main difference being an alignment with the OMG MARTE standard, specifically its Schedulabiltity Analysis Modeling (SAM) profile. This alignment results mainly in the renaming of certain modeling components. For instance, the Activity has been renamed to Step, the Scheduling Server is now a Schedulable Resource, and the Transaction is now called an End-to-End Flow. Additionally, MAST-2 also includes new specific modeling elements, such as AFDX switches, or native support for ARINC-like time partitioning.

Building MAST-2 with Eclipse EMF facilitates an easier integration of the MAST Analysis Tool with existing third-party models. The following figure illustrates a typical workflow enabled by MAST-2. The workflow begins with a description of a real-time system using an existing third-party metamodel, such as Amalthea from the APP4MC project. Within the Eclipse Modeling Framework, formal model-to-model transformations can be defined to automatically generate MAST-2 models from these initial third-party models. Subsequently, MAST provides the necessary automatic transformation from MAST-2 to MAST-1, which can then be used as input for the MAST Analysis Tool. The MAST analytical results can be automatically transformed back to the third-party metamodel. Consequently, the MAST Analysis Tool can be transparently used with any third-party model defined within Eclipse EMF.

This transformation-based workflow has been successfully employed to operate with Thales’ TEMPO metamodel, or with the Amalthea metamodel developed by BOSCH, to analyze AUTOSAR compliant systems for the automotive sector.

Contributing to MAST

MAST is an open-source project distributed under the General Public License (GPL), ensuring that it remains freely available for anyone to use, modify, and distribute. The source code for MAST is readily accessible on the official website and also on GitHub, where developers can collaborate, report issues, and contribute to the project’s ongoing improvement. The official website also provides readily available binary distributions for Windows and Linux.

MAST is actively under development. Our current focus includes extending support for modern computing architectures. This involves incorporating more detailed modeling of the memory hierarchy in multi-core systems, which is crucial for accurately modeling and analyzing the performance and behavior of contemporary processors. Additionally, we are working to support the analysis of Graphics Processing Units (GPUs), which are a crucial component in state-of-the-art applications such as driving assistance or autonomous driving . These applications are becoming increasingly relevant in the field of real-time systems.

Beyond technical enhancements, there is a continuous effort to validate MAST with realistic industrial examples. This validation is essential to ensure that the tool remains relevant and effective in solving real-world problems faced by industry professionals. We actively seek collaboration with industrial partners to test and refine MAST using actual use cases, thereby improving its accuracy, reliability, and overall utility.

By focusing on both advanced technical development and practical validation, MAST aims to be a robust tool that meets the evolving needs of both academic research and industrial applications. We welcome contributions from the community and encourage those interested in the tool to get involved through our website and GitHub repository. Your feedback and participation are invaluable in driving MAST forward.

Authors

Present and Past members of the Software Engineering and Real-Time Group at the University of Cantabria, Spain: M. González Harbour, J.J. Gutiérrez Garcia, J.C. Palencia, José M. Drake, J.L. Medina, Patricia López Martínez, and Juan M. Rivas.

Disclaimer: Any views or opinions represented in this blog are personal, belong solely to the blog post authors and do not represent those of ACM SIGBED or its parent organization, ACM.