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.

In general computing systems, a job (process/task) may suspend itself whilst it is waiting for some activity to complete, e.g., an accelerator to return data. In real-time systems, such self-suspension can cause substantial performance/schedulability degradation. This observation, first made in 1988, has led to the investigation of the impact of self-suspension on timing predictability, and many relevant results have been published since. Unfortunately, as it has recently come to light, a number of the existing results are flawed. To provide a correct platform on which future research can be built, this paper reviews the state of the art in the design and analysis of scheduling algorithms and schedulability tests for self-suspending tasks in real-time systems. We provide (1) a systematic description of how self-suspending tasks can be handled in both soft and hard real-time systems; (2) an explanation of the existing misconceptions and their potential remedies; (3) an assessment of the influence of such flawed analyses on partitioned multiprocessor fixed-priority scheduling when tasks synchronize access to shared resources; and (4) a discussion of the computational complexity of analyses for different self-suspension task models.

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.

Packet switched networks and message multiplexing have been a major upgrade for industrial systems communications. In the avionics domain, this evolution was brought by the introduction of avionics full duplex switched ethernet (AFDX). Guaranteed upper bounds of end-to-end delays for messages transmitted over an AFDX network are mandatory for certification reasons. In this article, we present the forward end-to-end delay analysis (FA), which is scalable to both large and heavily loaded configurations. A formal proof of FA is detailed and the approach is compared with alternative methods (network calculus and the trajectory approach) on two types of AFDX configurations (including a real industrial architecture).

Avionics Full DupleX Switched Ethernet (AFDX) switches, used in major civilian aircraft, have flow differentiation capability via multiple levels of Fixed Priority (FP) traffic classes. Inside a class, frames are handled in a First In First Out (FIFO) manner. End-to-end (ETE) delays, in such a network, have to be determined and an upper-bound is mandatory for certification purpose. Several methods, such as Network Calculus (NC) and Trajectory Approach (TA), can compute worst-case ETE delays in both FIFO and FP/FIFO contexts. The Forward end-to-end delay Analysis (FA) has been formerly developed for FIFO scheduling, and in this paper, we extend it to cover also FP/FIFO. We apply to the approach an optimization related to flow serialization, which has already proven to be effective for other methods and other servicing strategies. Finally, we apply FA on a sample configuration and compare the results to the two aforementioned approaches (TA and NC).

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.

The AFDX (Avionics Full DupleX Switched Ethernet) is the backbone network of most modern civilian aircraft. For certification reasons, a guaranteed upper bound has to be determined on the end-to-end delay for all transmitted flows. Several approaches have been designed in order to analyze such delays. In this paper, we focus on the Forward End-to-End delays Analysis (FA). This method is based on real-time scheduling results. Our goal is to propose an improvement, that reduces the pessimism of the computed bounds, compared to earlier versions of the method. The improvement relies on the way the serialization of packets sharing a common link is taken into account. We also propose a comparative analysis on a simple configuration with two other methods (Network Calculus and the Trajectory approach).

We consider the computational complexity problems of scheduling hard real-time tasks subjected to cache-related preemption delays upon uniprocessor platforms. Several schedulability analyses have been proposed in the literature to explicitly take into account preemption delays due to loss of cache affinity. But, these previous results do not study the complexity of taking scheduling decisions under preemption delay constraints and only focus on classical real-time schedulers (e.g., Rate Monotonic, Earliest Deadline First). In this paper, we focus on the computational complexity of taking scheduling decisions to meet task deadlines while minimizing cache-related preemption delay effects. We design two basic cache-related scheduling problems that are the most simple NP-hard problems to cover the largest set of intractable real-world cache-related scheduling problems. We establish several NP-hardness results for preemptive systems. These results prove that tighter timing analysis leads in practice to harder real-time scheduling problems. These two basic NP-hard scheduling problems are the following: (i) scheduling with cache-related preemption delays and (ii) scheduling with information about the cache state and the sequence of requested memory blocks for every task. We also prove for the first problem that neither fixed-task nor fixed-job priority-based scheduling algorithms can be optimal.

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.

AFDX (Avionics Full Duplex Switched Ethernet) is a network designed for safety-critical applications in avionics systems. The flow analysis is mandatory for the certification. The end-to-end (ETE) delay upper bound has to be computed and hence guaranteed. Different approaches have been proposed to compute ETE delay upper bound such as the Network Calculus and the trajectory method. Both methods are deemed to introduce some pessimism in the computations. We only focus next on the trajectory approach. This paper shows that the original trajectory approach is flawed and can compute an optimistic ETE. We present a counter-example and discuss the sources of optimism that must be considered to revise the trajectory method.

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.

Since worst case response times must be determined repeatedly during the interactive design of real-time application systems, repeated exact computation of such response times would slow down the design process considerably. In this research, we identify three desirable properties of estimates of the exact response times: continuity with respect to system parameters, efficient computability, and approximability. We derive a technique possessing these properties for estimating the worst-case response time of sporadic task systems that are scheduled using fixed priorities upon a preemptive uniprocessor.

Feasibility analysis algorithms are based on particular metrics such as processor utilization, load factor, processor demand, response-times, etc. The design of efficient algorithms for computing these metrics is a major issue in real-time scheduling theory. In this paper we propose two FPTASs (fully-polynomial time approximation schemes) for checking feasibility of static-priority tasks subjected to release jitters executed upon a uniprocessor platform. We then use these FPTASs for computing two upper bounds of worst-case response-times. Lastly, we show that these bounds do not achieve constant error bounds in comparison with values computed by an exact worst-case response-time analysis (performed in pseudo-polynomial time), and we present numerical experiments.

In most real-time systems, tasks use remote operations that are executed upon dedicated processors. External operations introduce self-suspension delays in the behavior of tasks. This paper presents several negative results concerning scheduling independent hard real-time tasks with self-suspensions. Our main objective is to show that well-known scheduling policies such as fixed-priority or earliest deadline first are not efficient to schedule such task systems. We prove the scheduling problem to be NP-hard in the strong sense, even for synchronous task systems with implicit deadlines. We also show that scheduling anomalies can occur at run-time: reducing the execution requirement or the suspension delay of a task can lead the task system to be infeasible under EDF. Lastly, we present negative results on the worst-case performances of well-known scheduling algorithms (EDFy RM, DM, LLF, SRPTF) to maximize tasks completed by their deadlines.

Integrating practical factors in scheduling theory is a major issue. Efficient schedulability tests (polynomial time or pseudo-polynomial time algorithms) are known for preemptive, independent tasks. In this paper, tasks are allowed to self-suspend. In practice, the real-time kernel suspends a task when it requests an external blocking operation. We study feasibility analysis problems from the computational complexity point of view. The problem is proved NP-hard in the strong sense for periodic, preemptive or non-preemptive task sets. If we allow tasks to have several flows of control (multi-threaded tasks), then the corresponding feasibility problem is shown to be NP-hard in the strong sense in the case of unit execution time threads.

We consider real-time systems connected via several fieldbuses. Validating such systems consists of proving that tasks meet their end-to-end deadlines. Tasks are scheduled on processors by fixed-priority schedulers. We propose an automatic method for allocating tasks on processors and assigning priorities to tasks so that every deadline is met. Allocation and scheduling are simultaneously achieved. We do not limit the search space to a specific priority rule (such as rate monotonic or deadline monotonic). Feasible schedules are validated by a holistic analysis. Numerical results of the method are lastly presented on a real-size application. Our tool will be a beneficial help to design real-time distributed systems.

We consider the scheduling of periodic tasks running on distributed computers. Every execution of a task must meet its deadline. Response time analysis of the tasks is used to prove the schedulability of hard real-time distributed systems according to the on-line priority rules that schedule the processors and the network. Its main advantage is to take into account the precedence dependencies of the schedules of the tasks on the processors and the messages sent on the network(s). Past works have addressed the issue of tasks related by asynchronous communication constraints with the senders and the receivers working at the same rate. We study more general relations among tasks when the rates of dependent tasks are not equal. We call such relations generalized communication constraints. Usually distributed systems are scheduled using a synchronization protocol and an on-line scheduling algorithm by processor. We present a graph theoretical approach to this schedulability analysis. Our algorithm transforms complex communication relations into classical ones, so that the classical scheduling analysis can be fully applied. That transformation is independent of the architecture of the distributed systems and no assumption is made on the synchronization protocol considered.

We present in this paper an application of a continuous speech understanding system to the control of a sonar console by a human operator. This application is really useful since it does correspond to a practical need of the operator who has his eyes busy looking at the sonar screen. It presents three original features: - the acoustic-phonetic decoding part of the system is not based on a classical phoneme labeling process but it yields for each segment of speech a set of acoustic phonetic labels that describe this segment very precisely. This phonetic labeling is associated with a special procedure for lexical access; - the system is actually a man-machine dialog system and not only a system capable of understanding a single sentence as it is often the case. The history of the dialog is used as a special knowledge source during the understanding process. This point highly increases the overall performance of the system; - the understanding process, and particularly the emission of hypotheses, is based on the knowledge about the language (lexicon and syntax) but also on the context of the dialog ; pragmatic knowledge is thus intimately associated with the analysis of a sentence. The paper presents the architecture of the system and its various components. It also discusses experimental results obtained in a multispeaker mode.