Linux has become a viable operating system for many real-time workloads. However, the black-box approach adopted by cyclictest, the tool used to evaluate the main real-time metric of the kernel, the scheduling latency, along with the absence of a theoretically-sound description of the in-kernel behavior, sheds some doubts about Linux meriting the real-time adjective. Aiming at clarifying the PREEMPT_RT Linux scheduling latency, this paper leverages the Thread Synchronization Model of Linux to derive a set of properties and rules defining the Linux kernel behavior from a scheduling perspective. These rules are then leveraged to derive a sound bound to the scheduling latency, considering all the sources of delays occurring in all possible sequences of synchronization events in the kernel. This paper also presents a tracing method, efficient in time and memory overheads, to observe the kernel events needed to define the variables used in the analysis. This results in an easy-to-use tool for deriving reliable scheduling latency bounds that can be used in practice. Finally, an experimental analysis compares the cyclictest and the proposed tool, showing that the proposed method can find sound bounds faster with acceptable overheads.

Measurement-Based Probabilistic Timing Analysis (MBPTA) produces Probabilistic Worst-Case Execution Times (pWCETs), i.e., WCET estimates associated with known low exceedance probabilities. Despite applicability and goodness-of-fit tests being used within MBPTA, any method based on the sampling of a population is subject to a degree of uncertainty. The acceptance of MBPTA in industrial engineering processes depends on obtaining enough evidence that the produced pWCETs are indeed reliable. In this paper we propose a statistical hypothesis test to check the reliability of pWCET estimates, done at a specified significance level. We assume as null hypothesis that the pWCET estimate is reliable, and as alternative hypothesis that it is optimistic. Both Type I and Type II errors are considered. The reliability test is based on a binomial experiment and it is complementary to applicability and goodness-of-fit tests. We evaluated the test using multiple synthetic and real-hardware execution time samples, and applied it on 20 pWCET estimates generated for each of them. The combined use of the proposed reliability test with applicability and goodness-of-fit tests could detect most of the knowingly unreliable estimates on synthetic samples. Similar behaviour was observed for real-hardware samples, evidencing the test's usefulness for selecting pWCET estimates with increased confidence.

This article proposes an automata-based model for describing and validating the behavior of threads in the Linux PREEMPT_RT kernel, on a single-core system. The automata model defines the events and how they influence the timeline of threads' execution, comprising the preemption control, interrupt handlers, interrupt control, scheduling and locking. This article also presents the extension of the Linux trace features that enable the trace of the kernel events used in the modeling. The model and the tracing tool are used, initially, to validate the model, but preliminary results were enough to point to two problems in the Linux kernel. Finally, the analysis of the events involved in the activation of the highest priority thread is presented in terms of necessary and sufficient conditions, describing the delays occurred in this operation in the same granularity used by kernel developers, showing how it is possible to take advantage of the model for analyzing the thread wake-up latency, without any need for watching the corresponding kernel code.

Like a Software Defined Network (SDN), a Protection, Automation and Control system, or PAC, could become a software defined PAC, or SDPAC. This article presents a case study and provides the time characterization of a PAC system compliant to the IEC 61850 standard that is applied to an electrical power system bay protection problem, or BAY61850, completely defined by software in a virtualized environment, or Cloud IEC 61850. The main question is whether the time requirements of such application can be met by the underlying infrastructure time behavior, from Guest-OS and Virtual Machine to the network. The software defined solution of the BAY61850 application follows a layer architecture proposed before in the literature, based on three main components: communication middleware; Guest-OS; and hypervisor. The DDS standard from OMG is the middleware solution adopted, using the OpenDDS implementation. The experiments consider two test scenarios, local host and distributed, with 15 test cases defined for 3 different simulation or sampling times. The results obtained are discussed in the paper. The main contribution is the technical information available to automation engineers and researchers assessing the use of virtualization in PAC projects. In a nutshell, a SDPAC system as proposed in this article could be the foundation or reference for the expected digital transformation in PAC system projects.

In order to support the computational demand of Real-Time Systems' (RTSs`) applications, the use of complex hardware will be fundamental. This fact makes analysis of software to derive Worst-Case Execution Time (WCET) an increasingly harder challenge. State-of-the-art WCET analysis techniques are hampered by the ever-growing cost and complexity of obtaining accurate knowledge of the internal operation of advanced processors, and by difficulties in reliably associating variable execution times with tasks' worst-case behaviour through measurement-based techniques. In this work, we performed an empirical assessment of the adequacy of Measurement-Based Probabilistic Timing Analysis (MBPTA) to estimate the pWCET - through Extreme Value Theory (EVT) - of a task executed on a complex computer architecture with Linux. The proposed evaluation has the objective of detecting whether EVT can be deemed suitable for determining pWCET estimates for tasks executed on complex computers.

As computer architectures evolve, guaranteeing that Real-Time Systems’ (RTSs’) timing requirements are met through Worst Case Execution Time (WCET) upper bounds becomes increasingly difficult. Techniques such as Measurement-Based Probabilistic Timing Analysis (MBPTA) have emerged that estimate WCET bounds exceeded only with arbitrarily low probabilities (i.e., pWCETs) through Extreme Value Theory (EVT). The Peaks Over Threshold (POT) approach for applying EVT involves adjusting a tail-shaped distribution, e.g., Generalized Pareto (GP) or Exponential, to the values that exceed a carefully selected high threshold. Several works suggest that GP should be used within POT for best representing different tail shapes, while others consider the Exponential model more adequate for providing upper bounds with increased reliability. This work presents empirical reliability and tightness evaluations of the pWCET estimates yielded by the GP and Exponential models while applying MBPTA through the POT approach. It mainly provides counter-evidence to the GP model reliability and evidence of the Exponential model adequacy in this context.

This paper presents a methodology to model and check the behavior of a part of the Linux kernel by applying automaton theory and in-kernel tracing from real execution. It is possible to check that the state transitions of the kernel during a real execution match with the allowed ones, according to the formal model. The scope of the paper is limited to the IRQ/NMI subsystem of the Linux kernel.

The technique known as Measurement-Based Probabilistic Timing Analysis (MBPTA) promises producing Worst-Case Execution Time (WCET) bounds for real-time systems' tasks based on the analysis of execution time measurements through Extreme Value Theory (EVT), a statistical framework designed to estimate the probability of extreme events. For that MBPTA requires the analysed tasks' maximum observed execution times to adhere to an extreme value distribution, such as Gumbel or Generalized Extreme Value (GEV), and allows determining execution time values expected to be exceeded only with arbitrarily small probabilities. Several works on the area assume that the Gumbel model should be employed in such analysis, while others consider GEV, which generalizes Weibull, Gumbel and Fréchet models, would be more adequate. In this work we perform an empirical assessment on the reliability and tightness of the WCET bounds determined through the GEV and Gumbel models. We do so by comparing the yielded estimates and their associated confidence intervals against the maximum values observed on large samples (e.g. of size 100 million), of both real and synthetic nature, as the modelling sample size is increased.

Till nowadays, the Controller Area Network (CAN) has been a de facto standard for communication in automotive applications. To meet the requirements of new high-end vehicular systems, new communication protocols such as the FlexRay Communication System and the CAN with Flexible Data-rate (CAN-FD) has been developed. In the near future, it is expected the coexistence of those protocols in the same vehicle, with electronic control units (ECUs) connected to different network buses exchanging information through gateways. In this paper we investigate the following problem: “how to schedule the communication in a vehicular system, considering that a message is transmitted through a network that is composed of CAN-FD, FlexRay and CAN segments interconnected by gateways.” We propose a method for the schedulability analysis of such systems, focusing on the case where a message is generated in a ECU connected to a CAN-FD segment is used by an ECU connected to a CAN bus.

Summary In the theory of real‐time scheduling, tasks are described by mathematical variables, which are used in analytical models in order to prove schedulability of the system. On real‐time Linux, tasks are computer programs, and Linux developers try to lower the latencies caused by the Linux kernel, trying to achieve faster response for the highest‐priority task. Although both seek temporal correctness, they use different abstractions, which end up separating these efforts in two different worlds, making it hard for the Linux practitioners to understand and apply the formally proved models to the Linux kernel and for theoretical researchers to apply the restrictions imposed by Linux for the theoretical models. This paper traces a parallel between the theory of response‐time analysis and the abstractions used in the Linux kernel. The contribution of this paper is threefold. We first identify the PREEMPT RT Linux kernel mechanisms that impact the timing of real‐time tasks and map these impacts to the main abstractions used by the real‐time scheduling theory. Then, we describe a customized trace tool, based on the existing trace infrastructure of the Linux kernel, that allows the measurement of the delays associated with the main abstractions of the real‐time scheduling theory. Finally, we use this customized trace tool to characterize the timing lines resulting from the behavior of the PREEMPT RT Linux kernel. Copyright © 2015 John Wiley & Sons, Ltd.

Nowadays, many real-time applications are very complex and as the complexity and the requirements of those systems become more demanding, more hardware processing capacity is necessary. Unfortunately, the correct functioning of real-time systems depends not only on the logically correct response but also on the time when it is produced. General-purpose processor design fails to deliver analyzability due to their nondeterministic behavior caused by the use of cache memories, dynamic branch prediction, speculative execution, and out-of-order pipelines. In this article, we investigate the pipeline performance of Very Long Instruction Word (VLIW) architectures for real-time systems with an in-order pipeline considering Worst-Case Execution Time (WCET) performance. Techniques on obtaining the WCET of VLIW machines are also considered and we make a quantification on how important are hardware techniques such as static branch prediction, predication, and pipeline speed of complex operations such as memory access and multiplication for high-performance real-time systems. The memory hierarchy is out of the scope of this article and we used a classic deterministic structure formed by a direct mapped instruction cache and a data scratchpad memory. A VLIW prototype was implemented in VHDL from scratch considering the HP VLIW ST231 ISA. We also show some compiler insights and we use a representative subset of the Mälardalen’s WCET benchmarks for validation and performance quantification.

The ARINC 653 specification defines a standard functional interface and temporal requirements for Operating Systems (OSs) used in aviation systems, and is based on temporally and spatially isolated partitions in which the application processes are executed. In this paper we present the key lessons learned from the development of an ARINC 653 compatible OS with educational and experimental purposes for BeagleBone, a popular and low-cost hardware platform.

This paper presents a method to determine the latency of memory instructions, aimed for use in WCET tools. We use a technique known as value analysis. Considering a processor with different data memory latencies, value analysis is used to determine the possible values of processor registers statically, allowing the recognition of memory addresses (main memory or ScratchPad Memory) in order to obtain tighter WCET upper bounds.

The correct functioning of real-time systems depends not only on the logically correct response, but also the time when it is given. This type of application is increasingly present today and the processing demand is such that complex processors are needed. Unfortunately general purpose processors are not well suitable for hard real-time applications due to their non-deterministic behavior caused by the use of cache memories, branch prediction, speculative execution and out-of-order pipelines. The goal of this work is to investigate pipeline performance of VLIW (Very Long Instruction Word) architectures for real-time systems with an in-order pipeline, a direct mapped instruction cache and a scratchpad memory to accelerate data memory. The prototype was implemented in VHDL considering the HP VLIW ST231 ISA. We present quantification of WCET and average-case performance and discuss some of the performance loss on using only pure deterministic design.

FlexRay is a communication system for automotive applications with high determinism, bandwidth, synchronization and reliability requirements, being a de facto standard for intra-vehicular communications in high-end vehicles. FlexRay media access control is based on a fixed-size communication cycle structured as a sequence of four segments: a Static Segment, a Dynamic Segment and two control segments. While the Static Segment is mainly used for transmissions related to time-triggered applications with hard real-time constraints, the Dynamic Segment is designed to accommodate transmissions from event-triggered applications with hard or soft real-time constraints, or from applications without real-time constraints. Some research works do consider a system model where message streams are sporadic with hard real-time constraints. To the best of our knowledge, there isn't in the literature research works addressing specifically the problems related to the transmission of messages from aperiodic streams in DN. In this work, we are proposing an arbitration mechanism to schedule aperiodic message streams on DN that avoids the indefinite postponement of low-priority streams. The proposed mechanism uses a probabilistic approach that takes advantage of the flexibility of aperiodic message streams regarding real-time constraints.

For real-time tasks, cache behavior must be constrained via cache locking or predicted by WCET analysis. Since the former gives up energy efficiency for predictability, this paper proposes a novel code optimization that reduces the miss rate of unlocked instruction caches and, provenly, does not increase the WCET. We optimized the 37 programs from the Mälardalen WCET benchmark for 36 cache configurations and two technologies. By exploiting software prefetching on top of on-demand fetching, we reduced the memory's contribution to the energy consumption (by 11.2%), to the average case execution time (by 10.2%), and to the WCET (by 17.4%).

In this paper we propose and evaluate suspension-based variations of the Multiprocessor Priority Ceiling Protocol (MPCP). The variations are compared with existing protocols for the same system model, which is partitioned and static priority scheduling. We present variations of the MPCP that improve in some cases the system schedulability. Some variations are actually simplifications that favor the implementation in real systems.

Algorithms to determine the itinerary of agents are fundamental in the context of distributed applications based on mobile agents with timing requirements. To establish an agent's itinerary it is necessary to consider the trade-offs between achieving

Algorithms to determine the itinerary of intelligent agents are fundamental in the context of distributed applications based on mobile agents with time constraints. In order to establish the agent itinerary it is necessary to consider the trade-offs between high-quality of results and meeting the deadline. In this paper, we describe and evaluate adaptive heuristics able to choose the best behaviour to be used for decision making in the itinerary definition. This decision-making is based on a log of benefits collected by the mobile agent in past executions. The paper's objective is to propose a new heuristic able to realize the change in the environment and adapt itself dynamically, changing its behaviour in order to meet the deadline of the mission and to achieve the greatest possible benefit.

Software applications use hash tables for many different purposes. Hash tables have an excellent average-case behavior but, in the worst-case, it degrades to something like a chained list. Because of that, the use of hash tables in real-time systems is not usual, since those systems may be required to guarantee deadlines. This paper discusses the use of hash table in real-time systems, considering that when the probability of an undesirable behavior is low enough, it can be ignored. It also compares approaches simple and 2-choice for the table design.

In this work we propose an end-to-end deadline missing prediction mechanism called Available Remaining Slack (ARS) for distributed threads. Simulations show that the proposed prediction mechanism presents good results for improving the overall performance and availability of distributed real-time systems.

This paper discusses the use of mobile agents with timing requirements in a distributed system. The goal of this paper is to propose and to evaluate heuristics for imprecise mobile agents that should execute a mission while meeting firm deadlines. These heuristics are used to determine the itinerary of the mobile agents. They choose a behavior considering previous benefits collected by the mobile agent in past executions. The agent uses adaptation at the departure. Once chosen the behavior for a particular mission, the agent keeps this behavior until the end of the mission. In order to choose the behavior it is used conditional probability based on the characteristics of the environment and on the last events. The algorithms proposed here were evaluated through simulations.

In some applications, as part of a mobile agent mission, there may be the necessity of meeting a firm end-to-end deadline, although with some itinerary flexibility due to optional resources. This paper proposes an execution model based on the concept

The development process of complex systems needs to take in account differents domains and aspects. SysML (Systems Modeling Language) is a new modeling language that allows a system description with various integrated diagrams (as structure, behavior and requirements diagrams), but SysML lacks formality for the requirement verification. The aim of this paper is to propose an approach to verify complex systems using SysML as a language which describes the system structure and requirements. Petri nets and temporal logic LTL are used respectively to formalize the system behavior and requirements. The benefit of such formalization is to allow an automatic formal verification. In order to demonstrate this methodology, it will be used a factory automation system, modeled by SysML and Petri nets, and verified by the TINA toolbox.

Distributed real-time threads are schedulable entities with an end-to-end deadline that traverse nodes, carrying their scheduling context. In each node, the thread will be locally scheduled and predictions about deadline missing allow that actions are carried out to improve system performance. This paper presents a task model and deadline partitioning algorithms that consider the possibility of a distributed thread to follow different paths. The future execution flow of the distributed thread is only probabilistic known before its execution. End-to-end deadline missing prediction mechanisms can be carried out through definition of estimated local deadlines. Simulations show that the proposed prediction mechanism presents good results in overloaded systems.

This paper proposes a new task model for expressing timing constraints that do not naturally admit expression in terms of deadlines and periods. In our task model, jobs are divided into segments A, B and C which must execute following this order. Segment A is responsible for performing its computations and compute a time-interval wherein segment B should execute to fulfill some application constraints. Segment C is released after segment B has finished. We consider the execution of B as valid if performed inside that time-interval, otherwise, its contribution may be considered valueless to its task. The model uses benefit functions to express when a given action should be performed for the maximum benefit. We adapt some scheduling approaches from the literature and present a feasibility test for our scheduling problem.

This paper describes an extension to the component-based programming model to support real-time dynamic guarantee for distributed applications. The extended model aims to include an acceptance tests to component-based servers at bind time. We present the mapping of our model to the CORBA Component Model, the architecture to support the dynamic guarantee in component-based middleware, the implementation of this architecture in CIAO (Component Integrated ACE ORB) and the result of experiments run to evaluate the cost of the mechanisms used

Industrial automation systems may include people, hardware, software and other elements necessary to produce the desirable results. The SysML modeling language is being proposed, by OMG and INCOSE, as a language that allows the system description correctly and consistently among various participants of the same project (software, mechanical, electrical and others engineers). The objective of this work is to evaluate the SysML proposal as a description language for industrial systems through the modeling of an industrial automation unit. A brief system description of the case study is included, the SysML diagrams will be presented during the system modeling and finally comments and considerations about the models and the modeling task are presented.

In some applications, as part of a mobile agent mission, there may be the necessity of meeting a firm end-to-end deadline, although with some itinerary flexibility due to optional resources. In this paper it is considered an execution model where agents do not previously know their itineraries. The objective is to propose and to evaluate heuristics to be used by pairs of imprecise mobile agents that must accomplish a mission within a firm deadline.

The complexity increase and variety of equipments controlled by embedded computers generate the need of a multidisciplinary approach for the process of development of those equipments, involving the areas of software, mechanics, electric and electronic engineering. System engineering uses different techniques to concurrently integrate these different views. In this sense, it is being specified by OMG a modeling language, denominated SysML (System Modeling Language). It intends to include in a single specification an integrated view of the system, one that includes hardware, software and electro-mechanics parts. The objective of this paper is to do an empirical evaluation of the modeling language SysML, in the sense of identifying its capacities and its limitations for the modeling of embedded systems. For that purpose, an electronic fuel injection system developed by Department of Automation and Systems at our university will be used.

In this paper we propose a system architecture that supports end-to-end scheduling of the distributed real-time thread abstraction. The real-time specification for Java (RTSJ) is used for the implementation of distributed real-time threads. By using simulations, we conclude that the proposed architecture is flexible enough to accommodate different scheduling algorithms

This work describes the proposal of a set of mechanisms to be applied in distributed component-based systems to allow the development of real-time applications capable of offering dynamic guarantee for clients. The proposal aims to make the application server able to provide service completion according to all clients imposed timing constraints or the immediate request rejection. To implement these mechanisms, we use an acceptance test at bind time to filter services requests. The acceptance test determines which service request will be executed, based on the system capacity and current load, providing therefore, dynamic guarantee for all the provided services

The imprecise computation technique has been proposed as an approach to the construction of real time systems that are able to provide both guarantee and flexibility. The paper analyzes the utilization of imprecise computation in the scheduling of distributed real time applications. First we discuss the main problems associated with that goal, and we define a task model suitable for distributed environments. Then, the paper presents an approach to the scheduling of distributed imprecise tasks. Finally, we describe specific scheduling algorithms to be used within the proposed approach.

The complexity of some real-time applications demands high performance computer architectures. Multicomputer architectures have a potential for high performance and reliability because of their expressive number of processors and communication channels. Therefore, they are natural candidates for supporting complex real-time computing. This paper presents a performance evaluation of real-time scheduling in a parallel/distributed environment which is based on a multicomputer architecture.

CORBA is an emerging middleware infrastructure with open standardization that is receiving a good acceptance since it allows easier programming of distributed objects. CORBA is being extended through the specification of interfaces and necessary abstractions to support applications with real time constraints. These new abstractions will enable a variety of programming models for real time applications. The paper presents an adaptive programming model for distributed real time applications using CORBA concepts. The model combines the time polymorphic invocation technique with the (m,k)-firm guarantee.