We address the problem of scheduling periodic implicit-deadline real-time tasks on m uniform processors. We introduce PCG^*, an optimal TL-plane algorithm based on PCG [Chen and Hsueh, 2008], which guarantees at most 2(m - 1) preemptions per TL-plane, matching the best-known theoretical bound for uniform platforms. The proposed algorithm advances the state of the art by offering an optimal real-time scheduling solution with a tight preemption bound within TL-planes. The numerical experiments presented in this work provide strong evidence that PCG^* yields a substantial reduction in the number of preemptions relative to PCG. When applied to identical processor platforms, PCG^* is also a best-possible polynomial time algorithm in terms of preemptions in a TL-plane, matching the (m-1) preemption bound achieved by LRE-TL [Funk, 2010].

This paper introduces unfair-PCG, the first unfair optimal scheduling algorithm for periodic implicit-deadline tasks on uniform multiprocessor platforms. The approach leverages the TL-plane scheduling method, allowing tasks to execute beyond their local execution time if processing resources are available. The algorithm ensures optimal resource utilisation while meeting task deadlines, thereby enhancing response times and enabling power-saving mechanisms.

We demonstrate that, for periodic systems with offsets (tasks or flows of messages within a time-triggered network), the simulation cycle can be confined to the range of [0, hyperperiod) only under the condition that an idle point exists at the hyper-period. Furthermore, we establish that ensuring both (1) contention-freedom and (2) that no offset exceeds the value of the period minus duration, is a sufficient condition to guarantee the presence of an idle point at the hyper-period. Most contemporary methods aiming to eliminate latency are implicitly based on these properties and fail to propose a schedule if the input system does not allow a contention-free solution. Consequently, we propose a heuristic approach to scheduling periodic flows of frames within time-triggered networks. Our method focuses on minimizing latency, without necessitating a solution where every frame at every output port is contention-free, and it effectively manages the cyclicity problem.

Autonomous vehicles, such as drones, are gaining great popularity due to their usability and versatility. Nowadays, a significant number of them operate using open source software, such as Robot Operating System (ROS) and the de facto standard MAVLink communication protocol, as they are free and many of them are reusable enough that they can be deployed in various different vehicles. Although these technologies offer a wide variety of resources, using them requires a reasonable background of programming and system engineering. Often, this is not achievable by common drone end-users in the short-term, as they would need to acquire a considerably large amount of know-how before working on specific domains. However, a graphical Domain Specific Modelling Language (DSML) might provide a shortcut to design drone missions using already known concepts to the end-users (or, at least, ones easier to learn). Pursuing this shortcut, RoBMEX is presented as a top-down methodology based on a set of domain specific languages able to enhance the autonomy of ROS-based systems, by allowing the creation of missions graphically, and then generating automatically executable source codes conforming to the designed missions.

In the domain of autonomous unmanned vehicles, some design patterns emerge from various distinct software designs. These patterns are the result of the search for modularity and, in consequence, customisation. They point to the possibility of a more general architecture and design process that are able to comply to at least most of design requirements made for unmanned vehicles, including regulatory ones. This paper explores the possibility of proposing this modular and customisable architecture as a simpler approach to responding to design requirements.

The seminal work on the global real-time scheduling of periodic tasks on unrelated multiprocessor platforms is based on a two-step method. First, the workload of each task is distributed over the processors and it is proved that this first step success ensures the existence of a feasible schedule. Then, using this workload assignment as an input, a template schedule construction method is presented. In this work, we review the seminal work and show by using a counter-example that this second step is incomplete. Thus, we propose and prove correct a novel and efficient algorithm to build the template schedule.

In safety-critical real-time systems domain, obtaining the appropriate operational model which meets the temporal (e.g. deadlines) and business (e.g. redundancy) requirements while being optimal in terms of several metrics is a primordial process in the design life-cycle. Recently, several researches have proposed to explore cross-domain trade-offs for a higher behaviour performance. Indeed, this process represents the first step in the deployment phase, which is very sensitive because it could be error-prone and time consuming.This paper is a work in progress proposing an approach aiming to help real-time system architects to take benefit from existing works, overcome their limits, and capitalize the efforts. Furthermore, the approach is based on the model-driven engineering paradigm and suggests to ease the usage of methods and tools thanks to repositories gathering them as a sort of a shared knowledge.

Real-time systems are used in many critical domains such as automotive, avionics and nuclear, therefore their temporal behavior needs to be checked rigorously. Many scheduling theory-based analysis tests have been proposed to validate the design of real-time systems. Since each given test is based on a set of assumptions, only the constrained system which satisfies these assumptions can be reliably verified by such a test. These assumptions do not depend on any design language but their interpretation does. Currently, these assumptions are often drowned in scientific paper discussions and expressed in natural languages. In this paper, we aim to make possible to define formally assumptions by real-time systems analysts without being expert of design languages. Indeed, we propose a domain specific language named IRL (Identification Rule Language). We show the benefit of such a language to capitalize efforts. That is, IRL allows to define analysis supports to help the timing verification community to share its knowledge and enables systems designers to use this knowledge easily.

Architecture Analysis and Design Language (AADL) is a standard in avionics system design. However, the communication patterns provided by AADL are not sufficient to the current context of Real-Time Embedded System (RTES) in which some multi-periodic communication patterns may occur. We propose an extension of a precedence model between tasks of different periods (multiperiodic communication). This relies on the Semaphore Precedence Constraint (SPC) model that is inspired from the concept of Semaphore, and more specifically on the m-n producer/consumer paradigm. We reinforce the SPC semantics by allowing cycles in the SPC precedence graph. We also present another viewpoint on the periodicity of tasks system using SPC based on a graph apart from the encoding technique presented in the SPC seminal work. An implementation of SPC in AADL and its associated analysis tool are also provided to study the temporal behaviour of systems using SPC.

Real-Time Systems are subject to temporal requirements. To check if these latter are met, performance analysis tests are required. However, the performance analysis through model-based process is still difficult due to (i) the complexity of real-time systems (ii) and the lack of methodologies enabling to leverage performance tests to be applied easily to design models.In this paper, we focus on the temporal scheduling analysis of distributed systems with real-time networks. We present an extension of a pivot scheduling analysis aware methodology in order to explicit the analysis models. That is, we propose a modeling viewpoint dedicated to distributed real-time systems in order to bridge the semantic gap between system design and analysis techniques of real-time networks.Our proposed extension has been implemented and integrated in a modeling framework dedicated to the schedulability analysis. The paper also contains a case study that stresses the contribution and shows its usefulness.

This paper presents a study on different methods of modeling the network reconfiguration problem to take into account load variation during a period of time. This work aims to determine if the optimization process needs to take into account this fact in order to be used by a real distribution network operator. It presents a way to optimize an integral objective function. Two types of optimization are presented, a Mixed Integer Quadratic Constrained Program (MIQCP) and a Mixed Integer Non-Linear Program (MINLP). Three different processes of optimization on a defined period are presented, two avoiding the use of power flow calculation and one using it. Methods are computed using three different load scenarios on the well known Baran & Wu test case. Results tend to show that it is not useful to take into account load variation and worst case optimization is the best method.

In this paper a network reconfiguration model aimed to be used in an industrial context is presented. It is based on a min-cost flow problem (MCFP) and a simplified power flow calculation. Mixed Integer Quadratic Constrained Programming (MIQCP) and Mixed Integer Non linear Programming (MINLP) are used and compared to compute the network reconfiguration with off-the-shelf optimization solvers. Two test cases are presented, a small academic network and a real case study. The paper shows experimentally that simplification on model level can be more efficient than simplification on the solving level for real world problems.

Amongst real-time scheduling community, several methods aim at enhencing the performance of the control. Subtask scheduling is one of the embedded convenient methods that reduce the input-output latency in the control loops. The predictive-Delay control is a new method based on input-output latency prediction in order to reduce the impact of this artefact on the quality of the control. Combining both subtask scheduling and predictive delay methods can be of a great help in combatting the impairments induced by this scheduling artifact.

Response time analysis is required both for on-line admission of applications in dynamic systems and as an integral part of design tools for complex distributed real-time systems. We consider sporadic tasks with fixed-priorities and arbitrary deadlines to be executed upon a uniprocessor platform. Pseudo-polynomial time algorithms are known for computing exact worst-case response times for this task model. Nevertheless, the problem is known NP-hard and there cannot exist a constant approximation algorithm for response time computation, unless P=NP. We propose a fully polynomial time approximation scheme (FPTAS) for computing response time upper bounds under resource augmentation. The resource augmentation is defined as the processor speedup factor bounded by (1 + 1/k), where kdef[1 = ε]-1 for any constant ε ∈ (0;1), the FPTAS accuracy parameter. This algorithm is best possible in the sense that resource augmentation is indeed necessary for an efficient response time calculation.

To fill the gap between the modeling of real-time systems and the scheduling analysis, we propose a framework that supports seamlessly the two aspects: (1) modeling a system using a methodology, in our case study, the Architecture Analysis and Design Language (AADL), and (2) helping to easily check temporal requirements (schedulability analysis, worst-case response time, sensitivity analysis, etc.). We introduce the usefulness of an intermediate framework called MoSaRT, which supports a rich semantic concerning temporal analysis. We show with a case study how the input model is transformed into a MoSaRT model, and how our framework is able to generate the proper models as inputs to several classic temporal analysis tools.

In this paper we propose parametric approximation algorithm (Fully Polynomial Time Approximation Scheme - FPTAS) that defines a compromise on the precision of computed worst-case response time upper bounds and the amount of extra processor speed required to achieve exact worst-case response times. Such a result fills the remaining gap between our previously published work [11] and also extends them to tasks with arbitrary relative deadlines. The method has been implemented and numerical results monitoring speedup factors are presented.

The software architecture of a critical embedded control system generally consists of a set of multi-periodic communicating tasks. In order to be able to describe such a system, we define the notion of semaphore precedence constraint, which supports multi-rate communications that follow regular repetitive patterns. We propose a feasibility test for EDF and we study three implementations, for periodic task sets related by such extended precedences on monoprocessor architectures.

This article studies the scheduling of critical embedded systems, which consist of a set of communicating periodic tasks with constrained deadlines. Currently, tasks are usually sequenced manually, partly because available scheduling policies do not ensure the determinism of task communications. Ensuring this determinism requires scheduling policies supporting task precedence constraints (which we call dependent tasks), which are used to force the order in which communicating tasks execute. We propose fixed priority scheduling policies for different classes of dependent tasks: with simultaneous or arbitrary release times, with simple precedences (between tasks of the same period) or extended precedences (between tasks of different periods). We only consider policies that do not require synchronization mechanisms (like semaphores). This completely prevents deadlocks or scheduling anomalies without requiring further proofs.

This article presents some results about schedulability analysis of tasks with offsets also known as transactions, in the particular case of monotonic transactions. The impact of a transaction on the response time of a lower priority task under analysis is computed with the interference implied by the transaction. In the general context of tasks with offsets (general transactions), only exponential methods are known to calculate the exact worst-case response time of a task. However, in this case, Maki-Turja and Nolin have proposed an efficient approximation method. A monotonic pattern in a transaction (regarding the priority of the task under analysis), occurs when, by rotation of the higher priority tasks in a transaction, it is possible to find a pattern of tasks such that the processor demand of the transaction is monotically decreasing during a period of the transaction. We have shown in our previous work that if a task under analysis is such that all the interfering transactions are monotonic, then it is possible to evaluate its exact response time in a pseudo-polynomial time. This article presents in detail how to apply this method. Then, it compares our results to the multiframe model proposed by Mok and Chen in (1996) (AM "accumulatively monotonic" pattern). We show that the multiframe model is a particular instance of tasks with offsets but the results presented for AM multiframe cannot be applied on monotonic transactions. Finally, we show that the approximation method proposed by Maki-Turja and Nolin computes an exact response time in the case of monotonic transactions, even if its complexity is higher than the one of the test that we proposed.

This article introduces the concept of monotonic transactions. A monotonic transaction is a particular case of transactions for which the load arrival pattern is (or can be by rotation) localized at the beginning of the transaction. In the general context of tasks with offsets (general transactions) only exponential methods are known to calculate the worst-case response time. The pseudo-polynomial methods known give an upper bound of the worst-case response time. The method of analysis suggested in this article gives the real worst-case response time: moreover; this method has a complexity lower than that of the existing methods of approximation. There are two main steps in the application of this method: grouping the tasks of the transaction in a normal form and seeking a monotonic pattern