Abstract The current trend in industrial applications is evolving towards heterogeneous platforms that integrate multiple processors and specialized accelerators within a single MPSoC (MultiProcessor System on Chip). Simultaneously, many of these applications have stringent timing requirements that must be met through the appropriate management of concurrency, synchronization, and the deployment of activities across the available computing elements in a distributed environment. In this context, Robot Operating System 2 (ROS 2) is gaining importance as a middleware for distributed systems in the automotive industry. This paper presents the real-time modeling and analysis of a smart mobility application running on a testbed based on MPSoC processors and ROS 2. While a comprehensive analysis of the use case under different configurations is presented, the main contribution is to provide the scientific community with a detailed generic model. This model serves as a benchmark for testing current and future techniques for the modeling, analysis, and optimization of real-time systems based on heterogeneous platforms while highlighting some challenges to be addressed.

The ever increasing computing demands in embedded systems is driving the adoption of hardware accelerators such as GPUs , which offer powerful platforms that can compute parallel workloads efficiently. Relevant critical applications that benefit from such platforms, for instance autonomous driving , usually impose additional real-time requirements that must be met to guarantee the correctness of the systems. In this paper, we propose exploiting readily available and extensively validated techniques to model and analyze real-time systems with GPUs . Specifically, we propose a methodology to employ the MAST model to characterize such systems, and different variants of the Offset-Based Response-Time Analysis techniques to validate the real-time requirements. We verify our approach with a real industrial application sourced from the railway industry . Through a comprehensive evaluation involving synthetic and real task-sets, we characterize the applicability of the approach, and we also show how estimated worst-case response times are aligned with real measurements up to 87.2%.

We present here the main features and lessons learned from the first edition of what has now become the ECRTS industrial challenge, together with the final description of the challenge and a comparative overview of the proposed solutions. This verification challenge, proposed by Thales, was first discussed in 2014 as part of a dedicated workshop (FMTV, a satellite event of the FM 2014 conference), and solutions were discussed for the first time at the WATERS 2015 workshop. The use case for the verification challenge is an aerial video tracking system. A specificity of this system lies in the fact that periods are constant but known with a limited precision only. The first part of the challenge focuses on the video frame processing system. It consists in computing maximum values of the end-to-end latency of the frames sent by the camera to the display, for two different buffer sizes, and then the minimum duration between two consecutive frame losses. The second challenge is about computing end-to-end latencies on the tracking and camera control for two different values of jitter. Solutions based on five different tools - Fiacre/Tina, CPAL (simulation and analysis), IMITATOR, UPPAAL and MAST - were submitted for discussion at WATERS 2015. While none of these solutions provided a full answer to the challenge, a combination of several of them did allow to draw some conclusions.

Scheduling models can be used to evaluate whether a particular system is able to meet its timing constrains. In many-core processors, with tens to hundreds of processors in the same chip, the analysis of the timing behavior needs to include the communications network used to exchange messages between the different processors. This paper presents a schedulability model for many-core systems based on a 2D mesh network-on-chip and store-and-forward switching with a limitation on the maximum link utilization rate that makes the analysis tractable. The model has been applied to the Epiphany many-core processor which has 16 cores connected by a 4 × 4 2D mesh. The analysis results have been tested on the real hardware by executing examples with synthetic task workloads. Those tasks are executed in a micro-kernel RTOS that we have developed. We also describe synchronization mechanisms to send messages between the tasks, and we analyze their timing behavior, so that they can be included in the analysis model.

This paper develops an offset-based response-time analysis technique for analyzing complex distributed real-time systems where processing and communication resources use the time-partitioning strategy to isolate the operation of separate software components. Time partitioning may be provided in the processors by an ARINC 653 compliant operating system, and in the networks via the TTP communication protocol. The software components executed by the system may themselves be distributed and complex, composed of many concurrent tasks and with one or more end-to-end flows that may have end-to-end timing requirements. The developed analysis supports hierarchical scheduling where a primary scheduler performs time partitioning into separate partitions, and secondary fixed-priority schedulers dispatch the different concurrent tasks inside each partition. It also supports end-to-end flows that are either synchronized with the partition schedule or not. This is the first time that this kind of analysis is developed. An evaluation of an improvement introduced in the analysis is discussed. Two representative case studies are described.

Earliest Deadline First (EDF) is the most widely studied optimal dynamic scheduling algorithm for uniprocessor real-time systems. For realistic programs, tasks must be allowed to exchange data and use other forms of resources that must be accessed under mutual exclusion. With EDF scheduled systems, access to such resources is usually controlled by the use of Baker’s Stack Resource Protocol (SRP). In this paper we propose an alternative scheme based on deadline inheritance. Shared resources are assigned a relative deadline equal to the minimum (floor) of the relative deadlines of all tasks that use the resource. On entry to the resource a task’s current absolute deadline is subject to an immediately reduction to reflect the resource’s deadline floor. On exit the original deadline for the task is restored. We show that the worst-case behaviour of the new protocol (termed DFP—Deadline Floor inheritance Protocol) is the same as SRP. Indeed it leads to the same blocking term in the scheduling analysis. We argue that the new scheme is however more intuitive, removes the need to support preemption levels and we demonstrate that it can be implemented more efficiently.

Real-time distributed systems contain end-to-end flows, which are distributed actions composed of sequences of tasks activated through messages. Such flows usually have an end-to-end deadline but the internal tasks and messages do not have specific timing requirements. However, if EDF schedulers are used, it is necessary to assign scheduling deadlines to tasks and messages, which is usually done by distributing the end-to-end deadline among them. Distributed systems may have synchronized global clocks or non-synchronized local clocks. This work studies the influence of the clocks, global or local, on the deadline-assignment algorithms. A study on the poor performance observed for EDF schedulers with local clocks is presented. Then, a significant optimization of the assignment algorithms is shown, in which an amount of end-to-end deadline larger than the established timing requirement is distributed among tasks and messages. With this technique, two new algorithms for deadline-assignment are proposed, showing that they outperform the existing ones by up to 23 percent of processor utilization in the case of local clocks. Finally, the influence of release jitter in this kind of EDF systems and the positive effects of eliminating it are also studied.

The CAN bus is one of the most used networks in distributed real-time systems. The CAN bus can be divided by means of bridges in order to distribute the network load among different segments and contribute positively to the schedulability of the system. On the other hand, CAN supports the fragmentation of a message in multiple packets when it does not fit into one single CAN frame. The schedulability analysis of CAN has been extensively studied in the literature. Although the proposed methods analyze non-segmented CAN buses, they can be applied to segmented networks. However, the techniques from the related literature obtain quite pessimistic results in the analysis of segmented CAN networks with multi-packet messages. This paper proposes a less pessimistic CAN schedulability analysis method for the mentioned kind of networks. Moreover, this optimized technique can be integrated with methods oriented to the holistic schedulability analysis of a complete distributed real-time system.

The increasing acceptance of the Earliest Deadline First (EDF) scheduling algorithm in industrial environments, together with the continued usage of Fixed Priority (FP) scheduling is leading to heterogeneous systems with different scheduling policies in the same distributed system. Schedulability analysis techniques usually consider the entire system as a whole (holistic approach), with only one preestablished scheduling policy in all the resources. In this work, composition mechanisms will be presented that enable us to combine different FP and EDF response-time analysis techniques for checking the schedulability of heterogeneous systems. Additionally, priority and scheduling deadline assignment techniques will be combined into a new algorithm called HOSPA (Heuristic Optimized Scheduling Parameters Assignment), for optimizing the assignment of priorities and scheduling deadlines to tasks and messages in heterogeneous distributed hard real-time systems.

The specification of the sporadic server real-time scheduling policy in the IEEE POSIX standard is defective, and needs to be corrected. Via experiments using a POSIX sporadic server implementation under Linux, as well as simulations, we have shown and confirmed previously unreported defects. We propose and demonstrate a corrected sporadic server formulation that eliminates these defects without changes to the syntax of the API or any significant increase in implementation complexity.

System level performance analysis plays a fundamental role in the design process of real-time embedded systems. Several different approaches have been presented so far to address the problem of accurate performance analysis of distributed embedded systems in early design stages. The existing formal analysis methods are based on essentially different concepts of abstraction. However, the influence of these different models on the accuracy of the system analysis is widely unknown, as a direct comparison of performance analysis methods has not been considered so far. We define a set of benchmarks aimed at the evaluation of performance analysis techniques for distributed systems. We apply different analysis methods to the benchmarks and compare the results obtained in terms of accuracy and analysis times, highlighting the specific effects of the various abstractions. We also point out several pitfalls for the analysis accuracy of single approaches and investigate the reasons for pessimistic performance predictions.

In this paper we overview the integration of a framework that generically manages the system resources in the form of contracts, namely the FRESCOR framework, with a flexible network resource. We describe how a network resource, namely FTT-SE, supports the FRESCOR framework services and, likewise, how the network services are made available to the application through the contracting framework. In a designer perspective, we also describe how a typical distributed application can be easily deployed using such a framework.

Offset-based response time analysis of tasks scheduled with fixed priorities has demonstrated to be a powerful tool to analyze many task models with different kinds of timing constraints, like regular periodic tasks, suspending tasks, distributed systems, tasks with varying priorities, multi frame models, etc. Offset-based analysis techniques are capable of performing a global schedulability analysis in distributed systems, as opposed to the less efficient techniques that consider each processing or communication resource as independent. In this paper we extend the offset-based schedulability analysis techniques to system with EDF (earliest deadline first) scheduling, using analytical techniques that are similar to those developed for fixed priority scheduling. With this new analysis, we now have a complete set of techniques to perform the analysis of different task models in distributed heterogeneous systems, i.e., processors and communication networks having either fixed priority or EDF schedulers.

The ongoing revision of the POSIX.13 standard - real-time profiles for portable operating system interfaces - proposes adding services to the minimum real-time system profile that are considered useful to the small embedded applications to which this profile is targeted. Concerns have been raised that these services may introduce too much overhead or may be difficult to implement. In this paper, we evaluate the implementation of some of these services in our MaRTE operating system. The implemented services are the monotonic clock, a high resolution sleep operation with specifiable clock, execution-time clock and timers, the sporadic server scheduling policy, and the timed mutex lock operation. We show that the complexity of these implementations is small, and the overheads introduced by the new services are fully acceptable.

Hierarchical schedulers are getting increased attention in many research projects because they bring in flexibility, they can take advantage of the best features of different scheduling policies, and allow the composability of applications developed under different scheduling strategies. Most commercial real-time operating systems have an underlying fixed priority schedule, and for this reason it is necessary to be able to analyze hierarchically-scheduled applications in which the underlying scheduler is of that kind. In this paper we extend the classic response time analysis techniques to analyze applications which can have a mixture of tasks scheduled either with fixed priorities, or with an earliest deadline first (EDF) scheduler running on top of an underlying fixed priority scheduler. We show that the complexity of this analysis is similar to that of existing response time analysis for EDF tasks.

Presents an application program interface (API) that enables applications to use application-defined scheduling algorithms in a way compatible with the scheduling model defined in POSIX. Several application-defined schedulers, implemented as special user threads, can coexist in the system in a predictable way. This API is currently implemented on our operating system MaRTE OS. We plan to propose it for a future revision of the POSIX standard.

This paper describes a model for representing the temporal and logical elements of real-time applications, called MAST. This model allows a very rich description of the system, including the effects of event or message-based synchronization, multiprocessor and distributed architectures as well as shared resource synchronization. The model is directly obtainable from a description of the system design using a UML tool. A system representation using this model is analyzable through a set of tools that has been developed within the MAST suite, including worst-case schedulability analysis for hard timing requirements, and discrete-event simulation for soft timing requirements. Although the current model only includes fixed priority systems, it is conceived as an open model and is easily extensible to accommodate other kinds of systems.

This paper describes a methodology and a framework for building an analyzable real-time model of an object oriented system that is developed using a UML CASE tool. The real-time model is formulated by a new UML view named "MAST RT View". This view allows the designer to gradually build the real-time model according to the phase of the development process, to feed data into the analysis tools, and to bring the relevant timing responses back into the model. The MAST RT View has three models: the processing capacity of the hardware/software platform; the timing behavior of the application logical components; and the workload and the timing requirements of each real-time situation to be analyzed. This view is analyzable by the MAST set of tools, which includes worst-case schedulability analysis and discrete event simulation for hard and soft timing requirements.

Presents a schedulability analysis technique for distributed hard real-time systems in which responses to different events may synchronize with each other. This technique uses a representation model for distributed systems that allows us to describe not only the task synchronization due to resource sharing, but also the activation due to combinations of events or the generation of several events by a single task. The model is representative of a large number of systems and is suitable for the treatment of message-passing systems or the client-server architecture. The analysis technique is based on the existing rate monotonic analysis (RMA) techniques for analyzing distributed real-time systems; it allows obtaining upper bounds for the worst-case response times of the system, thus allowing us to make guarantees about the fulfillment of the timing requirements that have been imposed.

In this paper we present improved techniques for the schedulability analysis of tasks with precedence relations in multiprocessor and distributed systems scheduled under a pre-emptive fixed priority scheduler. Recently developed techniques, based on the analysis of tasks with dynamic offsets, take into account the precedence relations between tasks only indirectly, through terms iteratively estimated from the response times of the tasks. With the techniques presented in this paper, we exploit the precedence relations in a more accurate way, and we also take advantage of the priority structure of the different tasks. These considerations permit a significant improvement of the results of the analysis applied to distributed and multiprocessor systems.

We present an improvement of the schedulability analysis technique for distributed hard real time systems that allows us to increase the maximum schedulable resource utilization. Since the improvement affects only the analysis technique, there is no additional implementation cost for the application itself. The improvement in the analysis consists of calculating a lower bound for the best case response time of tasks and messages, in order to reduce the estimated jitter in the activation of subsequent tasks and messages. This reduction of jitter implies reduced worst case bounds for the response times, and thus allows us to increase the maximum schedulable utilization. The paper explores two different ways to calculate a lower bound on the best case execution times. The paper also shows the results of simulations that we have carried out, in which we found that we could increase the maximum schedulable limit of the different resources by approximately 5% more utilization.

In this paper we present an extension to current schedulability analysis techniques for periodic task with offsets, scheduled under a preemptive fixed priority scheduler. Previous techniques allowed only static offsets restricted to being smaller than the task periods. With the extension presented in this paper, we eliminate this restriction and we allow both static and dynamic offsets. The most significant application of this extension is in the analysis of multiprocessor and distributed systems. We show that we can achieve a significant increase of the maximum schedulable utilization by using the new technique, as opposed to using previously known worst-case analysis techniques for distributed systems.

We propose a methodology for programming multiprocessor event-driven systems. This methodology is based on two programming levels: the task level, which involves programming the basic actions that may be executed in the system as units with a single control thread; and the job level, on which parallel programs to be executed by the complete multiprocessor system are developed. We also present the structure and implementation of an operating system designed as the programming support for software development under the proposed methodology. The model that has been chosen for the representation of the system software is based on an extended Petri net, which provides a well-established conceptual model for the development of the tasks, thus allowing a totally independent and generic development. This model also facilitates job-level programming, since the Petri net is a very powerful description tool for the parallel program.>

This paper presents a timing analysis for a quite general hard real-time periodic task set on a uniprocessor using fixed-priority methods. Periodic tasks are composed of serially executed subtasks, where each subtask is characterized by an execution time, a fixed priority and a deadline. A method for determining the schedulability of each task and subtask is presented along with its theoretical underpinnings. This method can be used to analyze the schedulability of any task set on a uniprocessor whose priority structure can be modeled as serially executed subtasks, which can lead to a very complex priority structure. Important examples include task sets that involve interrupts, certain synchronization protocols, certain precedence constraints, nonpreemptible sections, and some message-passing systems. The method is illustrated by a robotics example.>

The problem of fixed priority scheduling of periodic tasks where each task's execution priority may vary is considered. Periodic tasks are decomposed into serially executed subtasks, where each subtask is characterized by an execution time and a fixed priority and is permitted to have a deadline. A method for determining the schedulability of each task is presented along with its theoretical underpinnings. This method can be used to analyze the schedulability of complex task sets which involve interrupts, certain synchronization protocols, nonpreemptible sections and, in general, any mechanism that contributes to a complex priority structure. The authors introduce a simple but realistic real-time robotics application and illustrate how one uses the schedulability equations presented.>