4.1 Trajectories of W p8q and average of the first idle time for ū " 0.838 and x " 4.85. . . .

List of symbols

Maximum deviation of level i on κ τ i,j j-th job of τ i C i,j

Execution time of τ i,j A i,j

Arrival time of τ i,j T i,j

Inter-arrival time between τ i,j´1 and τ i,j R i,j

Response time of τ i,j R p8q i,j Heavy-traffic is the first job of τ 2 and is released at time 0. Its response time is equal to 8. It starts executing at 1, its blocking time is 1 as it is blocked by the job τ 1,1 also released at time 0. It is preempted by τ 1,2 at time 3, and τ 1,3 at time 6. . . . . . . . . . . . . . . . . . . . .

2.3

Example of a schedule with the discarding policy and without. The down-arrow represents the deadline of a task. The black circle means that the task has finished its execution. The gray-squared areas indicates that a task awaits for processing resources . . . . . . . . .

2.4

Two tasks with implicit deadline using the RM policy . . . . . . . .

3.1 Level 3 demand of 1 000 instances of the Diaz and Kim (DK) model, the heavy-traffic demand process and the classical deterministic worstcase analysis (WCET) considering only the maximal execution time for each task, for ū " 0.838 and ūmax " 1.208 and hyper-period T , for Γ defined in Table 3

Context

A real-time system is a computer system in interaction with an environment and users [START_REF] Harel | On the development of reactive systems[END_REF]. Sensors and programs are typically triggered periodically in order for the system to constantly interact with its environment. In order to make this interaction possible, it must satisfy temporal constraints. These temporal constraints can be more or less strict, depending on what functionality is asked from the system. We say that programs of a real-time system must meet their deadlines. We can classify deadlines according to the importance of functionalities associated to their associated programs:

(i) hard deadlines for programs such that a deadline miss consequence is not acceptable for either economic, human or ecological reasons, e.g., the braking system of a car.

(ii) soft deadlines for programs such that a deadline miss consequence is a delayed output of a program also known as a task, e.g., a sensor adjusting the temperature of a room.

Real-time systems consist in both hard and soft time constrained programs, and the analysis of their interference due to shared resources is a challenging open problem. Designing such system ensures that all programs meet their deadlines at a given rate. In practice, certification processes expect failure rates, e.g., 10 ´12frequency associated to failures within one hour of functioning-, for hard deadlines and less restrictive rates for soft deadlines [Gumzej and Halang, 2010, Fault Forecasting, p. 64]. For this reason, in this thesis we use the concept of deadlines with a permitted failure rate and make no formal difference between hard and soft.

There is a wide range of research areas related to real-time systems and we present below those that we consider the most relevant:

to continue operating, even when one or more of its components fail. Faulttolerance is achieved by creating redundancy in the system's components, programs, and data, so that if one component fails, the system can still operate.

Fault-tolerance also includes the ability to detect and respond quickly and effectively to a failure. This ensures that the system can continue to meet its real-time requirements, even when a failure occurs.

(vi) real-time networks: they are networks designed to transmit data with strict timing requirements. These types of networks are used in a variety of applications where the timely delivery of data is critical, such as in industrial automation, avionics, and automotive systems. In Time Sensitive Network (TSN) for example, the transmission of data is synchronized to a common clock, and the network is designed to minimize the amount of delay and other types of variability in the transmission of data. TSNs may use a variety of technologies and protocols to ensure the timely delivery of data, including deterministic Ethernet.

(vii) real-time oriented machine learning: recently, there has been an increasing use of machine learning methods, e.g., in the automotive industry, particularly for tasks such as autonomous driving, predictive maintenance, and traffic prediction. These methods often involve solving optimization problems with timing constraints, which are requirements that specify how long a task or operation is allowed to take. By incorporating these constraints into the optimization problem, it is possible to ensure that the system meets its timing requirements and performs reliably under all operating conditions.

In order to be safe, programs must meet their timing constraints. Real-time scheduling theory provides methods that orders the execution of programs over a finite or periodic number of time instances. A set of programs is considered schedulable for a given processing unit if it can be proven that each instance of a program has enough time to execute before its deadline. Scheduling is therefore mainly an optimization problem involving the allocation of limited resources, There are sources of uncertainties in every aspect of a real-time system, as it is by definition an object in continuous interaction with an unpredictable environment and users. One of the main goal of a real-time design is to minimize the impact of those uncertainties by construction and to ensure that the system is resilient to its environment. The purpose of using probability theory in real-time systems is to quantify those uncertainties. Solving this problem involves being able to adapt the system's decisions and, quantify and predict deadline misses.

Motivation

In a real-time system, it is common to deliberately over-dimension the system to ensure its ability to be reactive. However, this may lead to a large amount of wasted computing resource. The variability of the execution times is the degree to which the execution time of a task varies over time. There are several factors that can contribute to the variability of execution times in a real-time system, including:

(i) resource contention: if multiple programs are competing for the same resource (e.g., memory, pipelines, I/O devices), the execution time of each task may be affected.

(ii) unpredictable environment: sensors provide the input data for the system's programs. The execution time of these programs depends on values of input data that may trigger different branches of a program.

This variability can have serious consequences in a real-time system, as it may impact the ability of the system to meet its deadlines and fulfill its realtime requirements.

For embedded systems with low energy and computing resources, designing real-time systems means associating a suited micro-controller architecture to a set of programs. A key part of this design is to chose the appropriate processing unit (such as a CPU) for a given task set. To ensure that every task is executed within their specified timing constraints, the CPU and other computing resources are allocated to different programs, for example, according to their priority. During the run-time, each instance of programs competes for processing time. Timing correctness of realtime systems is traditionally guaranteed by a separate schedulability analysis and a WCET analysis. Classical techniques for WCET analyses aim at finding an upperbound on execution times. The time taken by a program to respond to an input and provide the output or display the updated information is known as the response time. After determining the WCET, the Worst-Case Response Time (WCRT) is calculated by aggregating the WCET of programs in the worst-case scenario, i.e., the scenario that produces the longest response times. However, this method [the worst-case reasoning] is sufficient to make schedulable task sets and it forces designers to over-estimate the quantity of processing unit necessary to run a task set.

In order to decrease the pessimism associated to this over-estimation, a significant amount of research in real-time systems focuses on statistical analyses (as discussed in Section 1.3.2).

State-of-the-art

In this section, we present existing work relevant for this thesis, to the best of our knowledge. That is to say, applied probabilities on real-time scheduling algorithms, timing analysis and shared resources modeling, and results on real-time multiprocessor scheduling. There are multiple sources of inter-core interference for a given architecture: shared caches, shared buses, memory and scheduling policies.

Existing results mainly address issues related to the system stability, computational algorithm designs, optimal scheduling, allocation, or performance analysis. This first Section 1.3.1 contains a brief presentation of the two most known preemptive scheduling algorithms. We provide then a review of existing results on the use of stochastic processes in real-time systems and a brief review of static-priority preemptive scheduling on multiprocessor systems.

Definition 1.1. Static priority algorithms are such that for any couple of tasks, whenever both are activated simultaneously, the same task always have priority.

Finally, we conclude this section by discussing the link between Mixed-Criticality (MC) systems and probabilistic approaches.

Deterministic analyses

We understand by testing the schedulability of a system that we assert that by construction the system cannot fail. Several schedulability tests are based on the utilization of the system, which is the sum of the ratios between the units of time required by the programs to execute and the time separating two instances of this same program. Other schedulability tests are based on the worst-case reasoning, i.e., finding the scenario producing the largest response times for every program. In the remainder of this thesis, a program is called a task and a job is an instance of a task.

We say that a scheduling policy is work-conserving, i.e., does not idle when there is work to do. Moreover, we say that a scheduling policy is preemptive, i.e., a job may be preempted before the end of its complete execution, and its execution can be resumed with no cost.

Single processor scheduling: Rate Monotonic and Earliest Deadline First

The Rate Monotonic (RM) scheduling policy is a static-priority scheduling algorithm, i.e., it assigns priorities by task. RM assigns to each task a priority relatively to its rate of occurrence -the larger the rate, the higher the priority.

Theorem 1.1 (Theorem 2 [START_REF] Liu | Scheduling algorithms for multiprogramming in a hard-real-time environment[END_REF]). RM is optimal for single processor systems with implicit deadlines in the domain of static-priority preemptive scheduling policies.

The Earliest Deadline First (EDF) algorithm is a deadline-driven scheduling policy, giving a priority to each job relatively to its absolute deadline -the smaller the absolute deadline, the higher the priority. We call dynamic any scheduling policy giving priorities at job boundaries. Once the priority is assigned to one job it does not change until the completion of this job.

Both RM and EDF are the most used scheduling algorithms of their own (static and dynamic) class because of their efficiency. Hence, we chose to restrict the state-of-the-art section to those two algorithms. In [START_REF] Liu | Scheduling algorithms for multiprogramming in a hard-real-time environment[END_REF], authors prove that in single processor preemptive scheduling, the worst-case scenario occurs in a critical instant, which is the simultaneous activation of all tasks. This reasoning leads to the results in [START_REF] Joseph | Finding response times in a real-time system[END_REF], where the response times are proven to satisfy a fixed-point equation. However, those two reasoning hold only for single processor preemptive scheduling.

Other schedulability tests focus on Time Demand Analysis (TDA) of the critical instant, which is the analysis of the workload sequence of jobs that produces the largest response time, i.e., the time between the activation and the end of a job.

This worst-case reasoning is based on the fact that a system is schedulable if the worst-case is schedulable. This property is called sustainability [START_REF] Baruah | Sustainable scheduling analysis[END_REF] (or predictability [START_REF] Ha | Validating timing constraints in multiprocessor and distributed real-time systems[END_REF]).

Definition 1.2 (Sustainability [START_REF] Baruah | Sustainable scheduling analysis[END_REF]). A schedulability test for a scheduling policy is sustainable if any system deemed schedulable by the schedulability test remains schedulable when the parameters of one or more individual jobs are changed in any, some, or all of the following ways: decreased execution requirements; later arrival times; and larger relative deadlines.

Multiprocessor scheduling

The problem of priority-driven scheduling on multiprocessor systems consists in two decision problems: the allocation and the priority assignment of tasks.

(i) Allocation: Jobs are allocated to processors. The allocation decision is a loadbalancing problem in which jobs are distributed among multiple processors.

(ii) Priority assignment: Priorities are assigned to tasks or jobs.

To the best of our knowledge, there are few results using probabilistic methods in multiprocessor scheduling. The main results using stochastic analysis are focused on shared resources quantification in multiprocessor systems, which is not what we focus on in this thesis. We present these results in the following, as well as deterministic results that we either extend or use as a baseline for a stochastic analysis.

Homogeneous and heterogeneous multiprocessor systems

We divide multiprocessor systems into three different categories based on the speeds of the individual processors.

• homogeneous multiprocessor systems: all processor speeds are the same across all processors. Usually the speed is set to one cycle per unit of time.

• uniform heterogeneous multiprocessor systems: the processing speed depends on the processor. Each processor has its own constant speed. Each processor in an uniform multiprocessor system is characterized by a speed or computing capacity, with the interpretation that a job executing on a processor with speed s for t units of time completes s ˆt cycles.

• unrelated heterogeneous multiprocessor systems: processing units have dedicated speeds according to the tasks to be scheduled. We do not cover this case in this thesis.

We cover in this thesis uniform heterogeneous multiprocessor systems that we call for more readability uniform multiprocessor systems.

Multiprocessor static-priority online scheduling Offline scheduling algorithms determine decisions before the system starts its execution. These scheduling algorithms select jobs to execute according to predetermined priorities. Usually, schedules are repeated after a specific time period [START_REF] Cucu | Feasibility intervals for multiprocessor fixed-priority scheduling of arbitrary deadline periodic systems[END_REF],

and the specificity of offline scheduling is that one should be able to tell a priori from what time this repetition begins.

Online scheduling algorithms select jobs by examining properties of active jobs.

They can be more flexible than offline algorithms since they can adapt their decision depending on the state at instant t of the system. For example, the system must use an online scheduling algorithm if the set of tasks includes tasks with unpredictable inter-arrival times that join and leave the system at undetermined times.

For a given class of multiprocessor scheduling algorithms, some are optimal in the sense that if they do not satisfy all deadlines, then no algorithm from this class can. However, satisfying deadlines in theory is not always the main goal in practice.

For instance, preemptions have a cost and one may want to optimize this cost.

An important result of online multiprocessor scheduling algorithm is provided in the seminal paper of [START_REF] Hong | On-line scheduling of real-time tasks[END_REF].

Theorem 1.2 (Theorem 1 in [START_REF] Hong | On-line scheduling of real-time tasks[END_REF]). There is no optimal online multiprocessor scheduling algorithm for real-time systems with two or more distinct deadlines.

While optimal algorithms can be built for the multiprocessor scheduling problem under certain conditions, there cannot be one optimal scheduling algorithm for EDF are for the single processor case. However, there are some important results that we discuss below. Several multiprocessor scheduling algorithms have been proposed [START_REF] Funk | U-llref: An optimal scheduling algorithm for uniform multiprocessors[END_REF],Funk and Nanadur, 2009,Baruah et al., 1993,Levin et al., 2010,Srinivasan and Anderson, 2005,Anderson et al., 2008,Baruah and Fisher, 2005, Brandenburg and Gül, 2016, Fan and Quan, 2012, Hobbs et al., 2019, Anderson et al., 2016, Kato and Yamasaki, 2009, Bastoni et al., 2011, Anderson et al., 2008].

An important layer of complexity are the migrations and preemptions of jobs between processors. With different levels of migrations (full, restricted or none), we define three main classes of multiprocessor scheduling algorithms [START_REF] Carpenter | A categorization of real-time multiprocessor scheduling problems and algorithms[END_REF]]:

• full migration: the scheduling algorithm is global. In global scheduling each task can be executed on any processor in the system. This type of process migration can maximize system utilization and provide an effective load balance. The main problem that global scheduling encounters is the cost of migrations and preemptions. For instance, in [START_REF] Andersson | Multiprocessor scheduling with few preemptions[END_REF] the authors focus on global scheduling with the goal of minimizing preemptions, see Figure 1 .2 and[START_REF] Bertogna | Schedulability analysis of global scheduling algorithms on multiprocessor platforms[END_REF]Cirinei, 2007].

• no migrations: the system is partitioned, i.e., each task is assigned to a processor. Partitioned scheduling divides the available computing resources into distinct partitions and assigns tasks to the appropriate partition. While this approach can be useful for organizing workloads, it does not always use the computing resources of a system in an efficient manner. For example, if the workloads assigned to each partition are not evenly balanced, then one partition may become overloaded while other partitions remain idle.

Additionally, if a task requires more resources than what is available in its assigned partition, then the task may not be able to complete in a timely manner. Partitioned scheduling also does not allow dynamic load balancing, meaning that the system cannot adjust to variable workloads or resource availability, see Figure 1.3 and [Andersson andJonsson, 2000,Andersson et al., 2003].

• restricted migrations: tasks are dynamically assigned to processor during runtime. With restricted scheduling each task can be executed on any processor, but each of its jobs has to finish executing its workload on this same processor.

Restricted migration can provide a more efficient load balancing while still allowing for some degree of task migration, see Figure 1.4 and [START_REF] Baruah | Multiprocessor fixed-priority scheduling with restricted interprocessor migrations[END_REF], Anderson et al., 2008, Goossens et al., 2012, Brandenburg and Gül, 2016].

Stochastic analyses

As discussed in the previous section, the sustainability [START_REF] Baruah | Sustainable scheduling analysis[END_REF] permits to extend directly deterministic single processor results to the probabilistic approach, because what is valid for the worst-case scenario is proven valid for all scenarios. We list and discuss in this section some of the results using statistics and probabilities for the analysis of single and multiprocessor systems. Some of the challenges of the stochastic analysis of real-time systems are detailed in [START_REF] Quinton | Challenges and new trends in probabilistic timing analysis[END_REF].

Single processor scheduling

Statistical timing analysis For a task and a given processor, we call timing analyses, the methods determining the largest workload required for the execution of this task on that processor. In [START_REF] Davis | A survey of probabilistic timing analysis techniques for real-time systems[END_REF], one can find a survey that details probabilistic timing analyses developed until 2018.

In [START_REF] Edgar | Statistical analysis of WCET for scheduling[END_REF], the authors present Extreme Value Theory (EVT) as a candidate for estimating WCET and WCRT with random variables (also known as probabilistic WCET and probabilistic WCRT), followed by [START_REF] Lu | A new way about using statistical analysis of worst-case execution times[END_REF], Cucu-Grosjean et al., 2012, Lima et al., 2016, Cazorla et al., 2013, Santinelli et al., 2014,Wartel et al., 2013,Lu et al., 2012], finding the best-fitted parameters for extreme value distributions [Basrak, 2011,Hansen et al., 2009], computing maximum likelihood estimators and non-parametric tests to do so, and finally compute the Deadline Miss Probability (DMP). The EVT method is called a measurement-based method, as it infers knowledge on execution times. One may find a complete survey of these results in [START_REF] Davis | A survey of probabilistic timing analysis techniques for real-time systems[END_REF], while open problems are underlined in [START_REF] Gil | Open challenges for probabilistic measurement-based worst-case execution time[END_REF]. According to these authors, deterministic WCET estimation of a task is often pessimistic, i.e., unlikely to occur and often larger than most execution times of that task. In fact, EVT has been used in several papers [START_REF] Lu | A statistical response-time analysis of real-time embedded systems[END_REF], Wartel et al., 2013, Liu et al., 2013, Lima et al., 2016, Lima and Bate, 2017].

In [Maxim et al., 2017a] the authors discuss the reproducibility of a measurement protocol and the representativity of the data used to estimate WCETs. Nevertheless, EVT has some limitations as it is too sensitive to outliers of the provided data.

Some other limitations are pointed in [START_REF] De | [END_REF]. A comparison with the deterministic approach is provided in [START_REF] Abella | On the comparison of deterministic and probabilistic WCET estimation techniques[END_REF].

Probabilistic schedulability tests of single processor systems One of the important part of a processor is the order in which it runs the tasks. There are several ways to schedule a task set. Some scheduling algorithms can be developed in order to schedule large sets of tasks, others can be energy optimized.

One may look at [START_REF] Davis | A survey of hard realtime scheduling for multiprocessor systems[END_REF] for an exhaustive survey on the scheduling problem on multiprocessor processors. It reviews the first notions to know when we speak about task scheduling as allocation or priority problems. It also explains all the different notions needed to understand real-time scheduling, as schedulability, comparability, predictability and sustainability, and presents the main results from the late 1960's until 2009.

In [START_REF] Díaz | Stochastic analysis of periodic real-time systems[END_REF],Kim et al., 2005], the authors calculate the exact distribution of response times of periodic tasks with probabilistic execution times. They also prove that the backlog, i.e., the remaining workload at each beginning of each hyperperiod, can be modeled with a Markov chain, and they are the first to consider the computation of the exact deadline miss probabilities from a set of execution time distributions. Finally they prove that the backlog of periodic systems converge to some steady-state distribution and they approximate this distribution. This method can be used to quantify deadline miss probabilities for a given task set in periodic systems. However, the complexity of this proposed solution is exponential, even if some studies solve partially the issue [START_REF] Marković | On the Convolution Efficiency for Probabilistic Analysis of Real-Time Systems[END_REF], Maxim et al., 2012] by subsampling the execution times distributions. This is where analytical approximations make their entry.

Analytical methods for measuring deadline miss probabilities have been studied

recently. In [START_REF] Von Der Brüggen | Efficiently Approximating the Probability of Deadline Misses in Real-Time Systems[END_REF], the authors are interested in the DMP and overload probability introduced in [START_REF] Chen | Probabilistic schedulability tests for uniprocessor fixed-priority scheduling under soft errors[END_REF], and provide both analytical and combinatorial descriptions of how to compute them. Their contribution relies on what they call the multinomial approach to compute deadline miss probabilities more efficiently. This work is then extended for EDF in [START_REF] Von Der Brüggen | Efficiently approximating the worst-case deadline failure probability under edf[END_REF]. In [START_REF] Palopoli | An analytical bound for probabilistic deadlines[END_REF], Palopoli et al., 2015, Abeni et al., 2017], authors bring the idea of what they call probabilistic deadlines (also known as DMP). Around this concept, they build the backlog analysis introduced in [START_REF] Díaz | Stochastic analysis of periodic real-time systems[END_REF], Kim et al., 2005] with a Birth-Death process, and quantify the deadline miss probabilities for a reservation based schedule algorithm for periodic systems. In [Villalba Frias, 2018], the author implemented in his thesis the PROSIT tool, a simulation framework computing deadline miss probabilities for a given task set, with independent and non independent execution times, using the backlog as a Birth-Death process, and an Hidden Markov Model to model the dependencies between execution times.

Scheduling theory is mathematically not that far from queuing theory. In [Lehoczky, 1996, Lehoczky, 1997a], the authors add to queuing theory timing constraints. They use a Markov process to model the lead-time profile of all the jobs in the queue. The main result provided in [START_REF] Lehoczky | Using real-time queueing theory to control lateness in real-time systems[END_REF] is that the multivariate queue length process converges to a Brownian network, assuming the heavy-traffic condition. In [START_REF] Doytchinov | Realtime queues in heavy traffic with earliest-deadline-first queue discipline[END_REF], the authors apply real-time queueing networks to EDF.

Multiprocessor scheduling

A current trend in real-time systems is the application of statistical learning methods in order to find optimal schedules [Plassart, 2020, Mao et al., 2019[START_REF] Islam | Hybrid dvfs scheduling for real-time systems based on reinforcement learning[END_REF], Lee et al., 1997, Kadaba et al., 1991]. In scheduling theory, the inference of scheduling knowledge [START_REF] Shaw | Intelligent scheduling with machine learning capabilities: The induction of scheduling knowledge[END_REF]] is a natural step into the application of the parametric method provided in this thesis. new parameters such as deadlines can improve scheduling decisions, see [START_REF] Aytug | A review of machine learning in scheduling[END_REF] for a review in this field.

In [START_REF] Manolache | Schedulability analysis of multiprocessor real-time applications with stochastic task execution times[END_REF], the authors speak about the heavy-traffic assumption, saying that it fails yet to handle systems where a task has more than one immediate successor task and hence leads to high deadline miss ratio, which is unacceptable for critical real-time systems. They use Coxian distributions to model execution times, and use Stochastic Petri Networks to describe the dynamic of multiprocessor scheduling. They prove that under the Coxian distribution assumption, there exists a system steady-state.

In [START_REF] Kim | Execution time analysis of communicating tasks in distributed systems[END_REF], the authors provide a model for execution time distribution including communication between sub-tasks with a queuing model and Markov chains, taking account of blocking time between sub-tasks induced by the parallelism of multiprocessor systems using the First-In-First-Out (FIFO)

policy. It provides a closed Markov chain representing step-by-step the number of sub-tasks being computed at the same time, with m `1 states, state 0 being the communicating/synchronization state, m being the number of cores available.

Shared cache interference

Shared cache interference (see Figure 1.5) is one of the reasons why migrations and preemptions are important metrics in scheduling algorithms performances, as they quickly add overheads into the process. Those overheads are usually ignored, but in multiprocessor scheduling they are crucial.

In [START_REF] Davis | Static probabilistic timing analysis for multicore processors with shared cache[END_REF], the authors list different problems encountered in multiprocessor systems with shared caches. They provide a static probabilistic timing analysis method on evict-on-miss random replacement cache policy singlecore systems, based on geometric distribution with a missing rate, and give some clues on how to model cache miss latency and memory use in multiprocessor architectures, but with no actual results. It is actually based on the analysis provided in [Altmeyer et al., 2015a], where the authors provide an analysis of how cache misses occur with a random replacement policy in a cache dedicated to one CPU, and express execution times as a sequence of cache accesses, missed or not.

WCET are then computed by adding all the delays induced by cache hit/misses.

In [START_REF] Jalle | Bus designs for time-probabilistic multicore processors[END_REF],Fernandez et al., 2014], the authors go further in the analysis of cache misses and focus on the bus contention. The goal of both papers is to provide a probability of cache miss due to shared hardware. In contrast to [Altmeyer et al., 2015a], where the authors provide an analysis of how cache misses occur with a random replacement policy in a cache dedicated to one processing unit.

The authors points have already been partially answered in [START_REF] Yan | WCET analysis for multicore processors with shared l2 instruction caches[END_REF] where a non-preemptive model is provided to describe access interference between instructions in a second-level shared cache but deterministic.

However, we do not model the shared cache interference in this thesis. Nevertheless, the number of preemptions have an important cost when resources are shared [START_REF] Phavorin | Cacherelated preemption delays and real-time scheduling: A survey for uniprocessor systems[END_REF]. This cost is a metric used in the simulations presented in Chapter 6, and migrations are restricted within the heuristics proposed for the same reason.

Machine learning in multiprocessor scheduling

Techniques that address the multiprocessor scheduling problem are developed in papers like [START_REF] Nakasuka | Dynamic scheduling system utilizing machine learning as a knowledge acquisition tool[END_REF], Kadaba et al., 1991, Lee et al., 1997, Ahmad and Dhodhi, 1996, Gupta et al., 2010, Padmajothi et al., 2022]. There are not many studies from real-time researchers using stochastic analysis, nor analytical approximations of the DMP in multiprocessor scheduling allowing inference, and, as we discuss in the last chapter, machine learning.

In Chapter 6 we focus on restricted multiprocessor scheduling algorithms.

Mixed-Criticality

Different values of execution times may correspond to various modes of a realtime system. Detecting modes changes in critical systems can be crucial and contribute to soften timing constraints. Such detection serves a higher-level objective:

characterizing a functional mode that may be a normal, exceptional or degraded, in order to increase the reactivity of these systems and to predict mode transitions [START_REF] Real | Mode change protocols for real-time systems: A survey and a new proposal[END_REF]. Indeed, by adapting the reaction of the system with respect to a given mode, an optimized utilization of resources is possible, which becomes another commercial trend within the time critical systems industry. Sometime the mode is obvious, such as a drone in a take-off mode for example, but tasks often depend of unobserved latent variables such as environmental variables. The MC model considers worst-case scenarios per mode [Vestal, 2007]. MC models have been widely studied recently [START_REF] Altmeyer | WCET and Mixed-Criticality: What does Confidence in WCET Estimations Depend Uponl[END_REF], Guo et al., 2017, Baruah et al., 2011, Gettings et al., 2015, Baruah et al., 2012, Guo et al., 2015, Burns, 2014]. One may see a review of MC systems in [START_REF] Burns | A survey of research into mixed criticality systems[END_REF]. We do not use the MC model in this thesis. However, we emphasize the link between probabilistic approaches and MC models as discussed in [START_REF]Probabilistic analysis for mixed criticality systems using fixed priority preemptive scheduling[END_REF], von der Brüggen et al., 2022[START_REF] Abdeddaïm | Probabilistic schedulability analysis for fixed priority mixed criticality real-time systems[END_REF], and how probabilistic approaches can contribute to better define and understand how MC models can be used in practice.

The introduction of MC systems in [Vestal, 2007] is concluded in those terms:

An interesting theoretical question we encountered was: What is a good multi-criticality utilization metric? We considered computing a vector of utilizations (one per design assurance level), computing a utilization using for each task the compute time associated with its own criticality, and computing a utilization using the compute time associated with the highest criticality of any task of equal or lower priority. A vaguely troublesome property of all these metrics is that some workloads may be feasibly scheduled at higher than 100% utilization. This is exactly the problem probabilistic approaches solve: what can we say when the maximal utilization is higher than 100% ? The MC model is a theoretical

Reader guidelines

model that is based on several levels of criticality (e.g., high or low), which are different modes of the system that can provide different execution times of tasks.

According to those modes, different quantities such as response times or deadline miss probabilities are computed. In [START_REF] Draskovic | Schedulability of probabilistic mixed-criticality systems[END_REF] for example, authors provide the deadline miss probabilities for the MC model with the probabilistic approach and show the link there can be between the MC model [Vestal, 2007] and the stochastic analysis of real-time systems. However, as discussed in [START_REF] Esper | How realistic is the mixed-criticality real-time system model[END_REF], certifications of real-time systems look for levels of confidence, that is to say a quantification of the failure rate of a given function (i.e., the real-time task, the sensors it uses and the actuators it may communicate with) of a system.

Furthermore, computing deadline miss probabilities is necessary, but to the best of our knowledge, the state-of-the-art results do not provide the appropriate granularity, as the certification requirements are placed at functionalities level. Sensors and actuators (the hardware part) is often not taken into account. In this perspective, a model allowing the inference of data from sensors and actuator to consider a level of confidence of the functionality of a system would be an improvement. In that regard, probabilities may play a crucial role but the lack of probabilistic models allowing such inference makes it not yet possible. Numerous papers try to generalize deterministic results to the probabilistic approach without succeeding to redefine the domain of application of such methods, which prevents the industry to actually trust such analyses. We use the MC model as our main motivation to define properly the domain of applicability of stochastic analyses.

Reader guidelines

In this thesis, we aim to approximate response times of real-time systems and provide statistical analyses for adaptive scheduling decisions. We propose a method for estimating the response time distribution and its a priori distribution. Finally, we apply this method by introducing a new class of allocation algorithms that we refer to as DMP-driven. The manuscript is composed of three main parts: The dependencies between chapters are illustrated in Figure 1.6.

Publications

The contributions presented in this thesis are published or under submission within the following four papers:

(i)

Software

Numerical evaluations are implemented within three frameworks:

(i) Probabilistic SimSo: an adapted version of SimSo using probabilistic execution times [START_REF] Zagalo | Simso with probabilistic execution times[END_REF].

(ii) rInverseGaussian: a Python library for the re-parameterized inverse Gaussian distribution [START_REF] Zagalo | rinversegaussian[END_REF].

(iii) Hypoexponential: a Python library for the hypoexponential distribution [Zagalo, 2022].

quantifying the probability that timing constraints may not be satisfied: the goal being to soften the description of timing variables as considering worst-case values may lead to an over-dimensioning of the processor. This over-dimensioning brings pessimism that may be measured as defined in [START_REF] Díaz | Pessimism in the stochastic analysis of real-time systems: Concept and applications[END_REF].

Utilization-based conditions of schedulability are well known. Indeed, the seminal work of Liu and Layland [START_REF] Liu | Scheduling algorithms for multiprogramming in a hard-real-time environment[END_REF] introduces a sufficient condition for the feasibility of a real-time system using its maximal utilization. However, in probabilistic real-time systems, each value of execution times and inter-arrival times are weighted by a probability. Furthermore, the deterministic critical instant defined in [START_REF] Liu | Scheduling algorithms for multiprogramming in a hard-real-time environment[END_REF], i.e., the worst-case scenario in single processor, cannot be extended to the probabilistic case directly [START_REF] Chen | Critical instant for probabilistic timing guarantees: Refuted and revisited[END_REF].

In this chapter, we introduce a new type of real-time tasks that we call stationary.

Probabilistic Real-Time Systems

In this first section we formalize the use of the probability theory in real-time systems and define the theoretical notions used by many studies.

Environment and probability space

Let Q be the set of possible states of the hardware, I the set of all possible input values of tasks. As explained in [START_REF] Axer | Building timing predictable embedded systems[END_REF], Q and I are usually unknown and/or too large, thus Timing predictability [. . . ] is incomputable for most systems. So, it is not possible to construct a general procedure that, given a system, computes its predictability exactly. [. . . ] However, it is possible to develop procedures that compute approximations, that is, upper and/or lower bounds on a system's predictability.

We call the product space Ω 0 " Q ˆI the environment space, representing all possible values of all inputs of the tasks, the exact state of the processor, or any information that varies during the execution of tasks, the physical properties in which the system interacts. We suppose Ω 0 finite, i.e., |Ω 0 | ă 8. For example, let Cpq, iq be the execution time of a task computed in an environment pq, iq P Ω 0 . In a perfect world, by knowing all possible states of a system, the system would be time predictable, in the sense that we can in fact predict the worst-case environment in Ω 0 for a given task. In [START_REF] Axer | Building timing predictable embedded systems[END_REF], authors define the timing predictability of a task with PrpΩ 0 q " min

q 1 ,q 2 PQ min i 1 ,i 2 PI Cpq 1 , i 1 q Cpq 2 , i 2 q (2.1)
which measures the ratio between the minimum and the maximum execution time of this task. A concept similar to the timing predictability can be measured by enumerating the subsets of Ω 0 that satisfy the occurrence of specific events. Let us call any subset A Ă Ω 0 an event, and A the set of all possible events, such that the empty space H P A and Ω 0 P A.

Finally, let P be a probability measure on the environment space Ω 0 , i.e., a function mapping A to r0, 1s such that (i) PpΩ 0 q " 1, (ii) P is σ-additive, i.e., for any collection pA n q n of pairwise disjoint events in A,

P p Ť n A n q " ř n PpA n q.
The uniform probability P of an event A P A is the frequency of occurrence of this events in Ω defined by

PpAq " |A| |Ω 0 | (2.2)
For example, let c P N. If A " tpq, iq P Ω 0 : Cpq, iq " cu its associated probability according to P is the frequency of occurrence of the equality Cpq, iq " c in Ω 0 , i.e., PpAq "

ř qPQ ř iPI 1 tcu pCpq,iqq |Q|ˆ|I|
where

1 A pxq " $ & % 1 if x P A 0 otherwise.

Definition 2.1 (Probability space).

Let Ω 0 be an environment space, A the sets of all events of Ω 0 and P the uniform probability measure on A defined in Eq. (2.2).

We call pΩ 0 , A, Pq a probability space.

In the remainder of this thesis, Q and I are considered unknown.

Definition 2.2. Let pΩ 0 , A, Pq be a probability space and A P A. We say A holds if PpAq " 1.

The application of this definition is as follow: every equality X " Y (resp.

inequality X ď Y ) is defined by P pX " Y q " 1 (resp. PpX ď Y q " 1).

Timing variables

A task is instantiated at a given time, for a given sequence of environments. In this section we provide a formal definition of the instance of a task, and its associated execution time, inter-arrival time and deadline.

Tasks and jobs

We call task a tuple of timing variables τ " pX 1 , . . . , X n q mapping the environment set Ω 0 to the product space J Ă R n `. We call job an instance of a task τ associated to an environment ω 0 denoted τ pω 0 q, such that a task τ is the function τ : ω 0 P Ω 0 Ñ τ pω 0 q P J where J is the set of all jobs. We say that a job is released when its associated task is activated. When a job is released, several variables are released with it.

Let Γ " tτ 1 , τ 2 , . . . u be a task set.

Let X be a mapping from Ω 0 to R `, and X ´1 be the inverse image of X in Ω 0 .

Let B X " tX ´1pAq : A P Au. We define the probability distribution of X P X pAq " P ˝X´1 pAq " P `X´1 pAq " Ppω 0 P Ω 0 : Xpω 0 q P Aq for A P B X .

Lemma 2.1. pR `, B X , P X q is a probability space.

Proof. First, X ´1pR `q P B X , and P X pR `q " 1. Let pB p q p be a sequence of pairwise distinct elements of B X . Let p ‰ q and ω 0 P X ´1pB p q X X ´1pB q q. Then Xpω 0 q P B p X B q " H. Hence the pX ´1pB p qq p are pairwise disjoints events of R `, and thus P X pY p B p q " PpY p X ´1pB p qq " ř p P X pB p q.

We call timing variables the variables characterizing tasks.

Definition 2.3 (Timing variable).

A timing variable on pΩ 0 , Aq is a mapping X : pΩ 0 , Aq Ñ pR `, Bq such that for each B P B there exist A P A such that B " XpAq.

Let X be a timing variable. We define the distribution function of X as F X pxq " P X pp´8, xsq " Ppω 0 P Ω 0 : Xpω 0 q ď xq also called cumulative distribution function and is such that F X p`8q " 1 and

F X p´8q " 0. The function 1 ´FX is called the exceedence function of X.

Execution times

The execution time of a job is the amount of workload (or processor cycles) it needs to finish. For a given environment ω 0 P Ω 0 , and a task τ i P Γ. Let C i be a timing variable such that the job τ i pω 0 q has an execution time C i pω 0 q. We consider through this work that execution times are bounded, i.e., for all τ i P Γ, there exist c min i and c max i such that

@ω 0 P Ω 0 , C i pω 0 q P " c min i , c max i ‰
We denote by F i the distribution function of C i , and its mean value by ErC i s and its second order moment E rC 2 i s.

Inter-arrival times

For a given environment ω 0 P Ω 0 , let T i be a timing variable such that the interarrival time T i pω 0 q is the elapsed time between the release (or activation) of the job τ i pω 0 q and the release of the previous one. We denote by G i the distribution function of T i . We call λ i " ErT i s ´1 the rate of τ i .

Deadlines

For a given environment ω 0 P Ω 0 , Let D i be a timing variable such that the relative deadline D i pω 0 q is the time given to the job τ i pω 0 q to execute. We say that the relative deadline D i is

• constrained if any job of τ i must complete its execution before the release of the next job of the same task in a deterministic fashion, i.e., there exists 0 ă d i such that @ω 0 P Ω 0 , D i pω 0 q " d i ď T i pω 0 q,

• implicit if it is equal to the inter-arrival time between a job and its next job of the same task,

• arbitrary if there is no relation with inter-arrival times.

Properties of timing variables

The expectation operator E of a probability measure P is defined by

ErgpXqs " ż Ω 0 gpXpω 0 qqPpdω 0 q (2.3)
for any function g : R `Ñ R. In order to estimate the distribution of a timing variable, we need to express (2.3) in terms of its possible values instead of the possible values in the hardware states in Q and inputs in I.

Lemma 2.2 (Transfer theorem). Let X be a timing variable and g : R `Ñ R. Then

ErgpXqs " ż R `gpxqP X pdxq
Proof. Take x " Xpω 0 q in Eq. ( 2.3), thus dω 0 " X ´1pdxq. Furthermore, by definition XpΩ 0 q P B X because Ω 0 P A.

We use the notation P X pdxq " dF X pxq. A consequence of this last lemma is that for any A P B X ,

P X pAq " ż R `1A pxqP X pdxq
Definition 2.4 (Independence). Let X and Y be two timing variables. We say that X and Y are independent if and only if @B 1 P B X , @B 2 P B Y , Ppω 0 P Ω 0 : Xpω 0 q P B 1 , Y pω 0 q P B 2 q " P X pB 1 qP Y pB 2 q Definition 2.5 (Identically distributed

F Z pzq " ż F X pz ´yqdF Y pyq " ż F Y pz ´xqdF X pxq

Common distributions

We define in this section the distributions used in the remainder of this thesis. here Φ is defined in (2.4).

The inverse Gaussian family is a natural choice for a statistical modelling of positive and right-skewed distributions, see [START_REF] Folks | [END_REF]Chhikara, 1978, Tweedie, 1957]. It is used in many fields, such as industrial degradation modelling [START_REF] Ye | The inverse gaussian process as a degradation model[END_REF], psychology [Schwarz, 2001, Palmer et al., 2011], and many others like hydrology, market research, biology, ecology, and so on c.f., [Seshadri, 2012].

The tuple pC i , T i , D i q varies depending on which environments τ i is activated.

This means that when a job τ i pω 0 q is released, it is after T i pω 0 q units of time after the previous job of τ i . Its execution time is C i pω 0 q and it should be over before D i pω 0 q units of time.

In the remainder of this thesis, we consider implicit deadlines.

Server distribution G 1 distribution G 2 distribution G n distribution F 1 F 2 , ..., F n priority Figure 2.1: Scheme of a ř i G i { ř i G i {1{SP system.
The sorted queue (by priority) is the queue wrapped with dots

Kendall's notation

In queueing theory, Kendall's notation [Kendall, 1953] is the standard notation to describe a queueing system, i.e., arrival and service times, processing units and scheduling policies. In our case, jobs arrive at a certain rate, and leave the system after the processor treats their execution time. So the general standard model for single processor scheduling is written G{G{1 and when written like this, the first G stands for general inter-arrival time distributions, the second G for general execution time distribution, the 1 refers to the single processor and implicitly we suppose that FIFO is used to schedule jobs. In the remainder of this thesis,

• D stands for deterministic,

• G for general,

• M for memoryless.

For example, a D{D{1 queue is a periodic system with only one value of execution time. It corresponds to the periodic worst-case analysis widely studied in real-time systems.

Each task generates its own queue. As we work under the assumption of memoryless inter-arrival times, each task is associated to a M {G{1 queue. Furthermore, as we work under a static-priority scheduling policy, and exponential inter-arrival distributions with several tasks (or priority classes), we write the model

ř i M i { ř i G i {1{SP
, which is described on Figure 2.1.

Stationarity

Let T ą 0 and 0 " t 0 ă t 1 ă t 2 ă ¨¨¨ă t k " T and the finite sequence of environments ω " pω t 0 , . . . , ω t k q. More generally, we define the space Ω T " pΩ 0 q r0,T s as the space of all functions mapping the interval of time r0, T s to the environment space Ω 0 , such that ω P Ω T can be written ω " pω t , t P r0, T sq. When T goes to infinity, we denote Ω " pΩ 0 q R `.

We call canonical process the operator θ t : Ω Ñ Ω 0 such that

θ t pωq " ω t
is the projection of a sequence of environments to the associated environment at time t ą 0. It makes the link between processes evaluated on sequences of environments and timing variables evaluated on given environments.

Task model

We consider a finite task set Γ " tτ 1 , . . . , τ n u of n tasks. A task τ i is characterized by:

• C i ą 0 its execution time,

• O i ě 0 its offset, the time of its first activation,

• T i ą 0 its inter-arrival time,

• D i ą 0, its relative deadline,

• α i P r0, 1q, its permitted failure rate.

C i , O i , T i and D i have their distributions, as α i is deterministic. The task set Γ is ordered by decreasing priority order, i.e., τ i has priority over τ i`1 .

Arrival times Let τ i P Γ and ω piq " pω piq 0 , ω piq t 1 , . . . q P Ω be a sequence of environments. We call arrival time of the j-th activation of τ i the variable defined by

A i,j pω piq q " O i pω piq 0 q `j´1 ÿ k"1 T i pω piq t k q (2.6)
such that A i,1 pω piq q " O i pω piq 0 q is the first activation of τ i . Arrival times have the property of satisfying the relation A i,j pω piq q ´Ai,j´1 pω piq q " T i pω piq t j q.

Job sequences The j-th job of the task τ i is denoted τ i,j and defined by τ i,j " τ i ˝θA i,j such that the job τ i,j is mapping Ω to J . Its execution time is

C i,j " C i ˝θA i,j
and the inter-arrival time between the jobs τ i,j´1 and τ i,j is

T i,j " T i ˝θA i,j´1
There are two types of inter-arrival times:

(i) stationary: A task τ i P Γ is said stationary if the sequence T i,j , j P N is identically distributed with distribution function G i . There are three subclasses widely studied of stationary inter-arrival times:

• periodic: A task τ i P Γ is said periodic if T i is deterministic, i.e., there exists t i ą 0 such that G i pxq " 1 rt i 8q . In that case, we call T i the period of the task τ i . A periodic task is stationary. In real-time systems, it models time-triggered programs, i.e., each t i units of time, the task τ i is activated.

• memoryless: Let T be an inter-arrival time. T is said memoryless if PpT ą t `s | T ą sq " PpT ą tq, which can be rewritten as the differential equation f pt `sq " f ptqf psq, @t, s ą 0. The solution to this equation belongs to the family of exponential functions. In this case,

G i ptq " 1 ´e´λ i t .
• sporadic: A stationary task τ i is said sporadic if there exists a bound t min i such the inter-arrival time T i,j , j P N is greater than t min i . We call

λ max i " 1{t min i the maximum rate of τ i .
(ii) non-stationary: A task τ i P Γ is said non-stationary if there exists a positive function Λ such that a job released at the instant t ą 0 is released with a rate Λptq. Thus, the sequence T i,j , j P N is not identically distributed and their distributions depend on the release time of their associated jobs. There are two sub-classes of non-stationary inter-arrival times:

• sporadic: A non-stationary task τ i is said sporadic if there exists a bound t min i such the inter-arrival time T i,j , j P N are greater than t min i .

Without more information on the individual distributions of T i,j , j P N, the analyses of sporadic non-stationary tasks can be done only in the worst-case where they are bounded by periodic inter-arrival times of rate λ max i . This leads to suppose periodic inter-arrival times with G max i ptq "

1 rt min i ,8q ptq.
• aperiodic: If inter-arrival times of a given task are non-stationary and not sporadic.

Equivalently, we may write Eq. (2.6)

as A i,j " O i ˝θ0 `řj´1 k"1 T i,k .
Finally, the relative deadline of the job τ i,j is the inter-arrival time between τ i,j and τ i,j`1 i.e.,

D i,j " T i,j`1
because we consider that deadlines are implicit. A consequence of this is that the

deadline D i is with distribution function G i .
The canonical process tθ t u t permits to write timing variables for any sequence of environments, without specifying the environment they are evaluated on.

Renewal theory

Let A i,j , i " 1, . . . , n, j P N be a sequence of arrival times of the tasks in Γ as previously defined, i.e., with O i " A i,1 called its offset and A i,j`1 ´Ai,j " dG i for all j ě 1. We define the renewal process N i

N i ptq " 8 ÿ j"1 1 r0,ts pA i,j q (2.7)
as the number of jobs of τ i released before the instant t. We call

λ i " ErN i p1qs
the intensity of N i .

Definition 2.13 (Stationary renewal process).

A renewal process N is said stationary if N pt `sq ´N psq pdq " N ptq for any t, s ą 0.

Theorem 2.1 (Section 1.4 [Sigman, 2009], [Sigman, 2006]). A renewal process N with an inter-arrival time distribution G of mean λ ´1 is stationary when its offset

O is distributed with G 0 pxq " λ ż x 0 p1 ´Gpyqqdy (2.8)
where G 0 is called the recurrence distribution of the renewal process N .

Definition 2.14 (Stationary queueing model). We call a

ř i G i { ř i G i {1{SP queueing model stationary when its offsets O i , i " 1, . . . , n satisfy (2.8).
Corollary 2.1 (Periodic arrivals). In the deterministic case, i.e., PpT i " λ ´1 i q " 1, if O i has a uniform distribution between 0 and λ ´1 i , i.e., G 0 i pxq " λ i minpx, λ ´1 i q, N i is stationary.

Proof. According to Theorem 2.1, in order for N i to be stationary, is that the

distritbution of O i is G 0 i pxq " λ i ş x 0 p1
´Gi pyqqdy. In a periodic system, we have 1 ´Gi pxq " 1 r0,λ ´1 i q pyq. However,

G 0 i pxq " λ i ż x 0 1 r0,λ ´1 i s pyqdy " $ & % λ i ş x 0 1dy if x ď λ ´1 i λ i ş λ ´1 i 0 1dy `λi ş x λ ´1 i 0dy if x ą λ ´1 i " $ & % λ i x if x ď λ ´1 i 1 if x ą λ ´1 i " λ i minpx, λ ´1 i q
which is the uniform distribution function according to Definition 2.8

Theorem 2.2 (p.394 [START_REF] Stirzaker | Probability and random processes[END_REF]). Let N be a stationary renewal process of intensity λ. Then,

N ptq t Ñ tÑ8 λ (2.9)

Poisson process

The increments N pt `sq ´N psq of a stationary renewal process N only depend on the value of t ą 0, where t ą s ą 0. However, any inter-arrival time is dependent on the history of the process, i.e., all the information about past arrival times. Only one family of renewal processes is memoryless, i.e., not dependent on the past: the Poisson processes. Proof. According to Theorem 2.1, in order for a renewal process N of inter-arrival distribution G to be stationary, the distritbution of its offset is G 0 pxq " λ ş x 0 p1 Ǵpyqqdy.

However in the case of a Poisson process of intensity λ, Gpxq " 1 ´e´λx , hence G 0 pxq " λ ż x 0 e ´λy dy " 1 ´e´λx which means that the offset is distributed as all inter-arrival times.

Remark. Poisson point processes are the only memoryless renewal processes,

i.e., the probability that at a time t, the next arrival is at time t `s only depends on s. In other words, the arrival times probabilities do not depend on the past at any instant t. We classify exponential inter-arrival in the stationary context as memoryless inter-arrival times. Indeed, the exponential distribution is the only distribution having the property of not depending on the arrival times of jobs: for any renewal process, the probability that the inter-arrival time T of a job exceeds a value t `s given that an interval of time of length s as past since the arrival of this job, i.e., PpT ą t `s | T ą sq depends on t and s, except of the exponential distribution where PpT ą t `s | T ą sq " PpT ą sq. This is why this property is called memoryless: it does not need to know anything from the past. In general, this is not the case, and we discuss the general case in the end of the next chapter.

Poisson processes are renewal processes with many interesting properties that we use throughout this thesis.

Theorem 2.3 (Superposition, Section 1.4.2 [START_REF] Baccelli | Elements of queueing theory: Palm Martingale calculus and stochastic recurrences[END_REF]). Let N 1 and N 2 be two independent Poisson point processes of respective intensities λ 1 and

λ 2 . Then N 1 `N2 is a Poisson process of intensity λ 1 `λ2 .
Proof. Since N 1 and N 2 are both stationary, the stationarity of N 1 `N2 comes from the fact that its jumps are also i.i.d. For this, we need to show that minpO 1 , O 2 q is exponentially distributed with parameter λ 1 `λ2 . We have

PpminpO 1 , O 2 q ą tq " PpO 1 ą t, O 2 ą tq " PpO 1 ą tqPpO 2 ą tq (O i 's are independent)
" e ´λ1 t e ´λ2 t then we conclude with Corollary 2.2,i.e., the fact that O i pdq " T i .

Lemma 2.3 (Marked Poisson process). Let N be a Poisson point process counting

the arrivals of the jobs of n different tasks respectively arriving at a rate λ 1 , . . . , λ n .

Let Īk,l be the index of the task of the l-th job of level k, i.e., the job of arrival time Āk,l " inftt ą 0 :

ř k i"1 N i ptq " lu. Then Pp Īk,l " iq " λ i ř k i"1 λ i (2.10)
In other words, the probability that this job is from task τ i , i " 1, . . . , n is

λ i { ř k i"1 λ i .
Proof. The Īk,l are independent from the C k,l , T k,l and a fortiori of A k,l . Hence, we can use [Baccelli and Brémaud, 2013, Remark 1.4.2.] for each level of priority k which gives us immediately (2.10).

Definition 2.16 (Poisson arrival).

Let Γ be a stationary task set. We say that Γ has Poisson arrivals if the inter-arrival times of tasks are exponentially distributed.

Definition 2.17 (Stationary Real-time System). Let pΩ, A, Pq a probability space, and tθ t u be a sequence of projections on pΩ, A, Pq. Let Γ be a task set such that all the couples pC i,j , T i,j q, j P N are independent and identically distributed (i.i.d.), and pO i , i " 1, . . . , nq satify (2.8). We call pΩ, P, Γ, tθ t uq a stationary real-time system.

We say that such system is deterministic if the timing variables in Γ do not depend on the sequence of environments in Ω.

Demand process

Let N be a stationary renewal processes of intensity λ, and X 1 , X 2 , . . . an i.i.d.

sequence of bounded execution times of a task τ P Γ. We define the demand process of the task τ as

W ptq " N ptq ÿ j"1 X j (2.11)
the accumulation of execution times required by the task τ until the instant t ą 0.

Lemma 2.4 (Wald's lemma [Wald, 1944]). Let N be a positive integer-valued variable independent from the i.i.d. timing variables X, X 1 , X 2 , . . . . Then for any

t ą 0, E « N ÿ j"1 X j ff " ErN sErXs Lemma 2.5 (Law of large numbers). Let X 1 , X 2 , .
. . be an i.i.d. sequence of timing variables such that Er|X 1 |s ă 8. Then

1 n n ÿ i"1 X i Ñ nÑ8 ErX 1 s
Theorem 2.4. Let W be defined as in (2.11). Then ř N ptq j"1 X j Ñ ErXs since the X j 's are i.i.d. and bounded, we have Er|X|s ă 8.

W ptq t Ñ λErXs (2.12) Proof. We have W ptq t " N ptq t 1 N ptq ř N ptq j"1 X j . Theorem 2.
Until Chapter 6, we consider the stationary real-time system pΩ, P, Γ, tθ t uq.

Time demand analysis

Due to the static-priority policy, the response times of a task τ k depend only those of higher priority tasks. We call job of level k any job of a task of higher or equal priority than τ k , i.e., any job τ i,j , 1 ď i ď k, j P N. We suppose that priorities are distinct. Let ūk "

k ÿ i"1 λ i ErC i s
be the k-level mean utilization of Γ, the total mean utilization ū " ū|Γ| , and the

maximum utilization of level k, ūmax k " k ÿ i"1 λ i c max i
Definition 2.18. Let pΩ, P, Γ, tθ t uq be a stationary real-time system with total mean utilization ū. Γ is said stable if ū ă 1.

Many schedulability tests rely on the utilization of the system, that is, sufficient conditions that ensure that the system is indeed schedulable. However, those schedulability tests are not suited for probabilistic real-time systems, as they do not take advantage of the entire distributions of execution times and inter-arrival times. Hence, the domain of feasibility of probabilistic real-time systems is yet to be defined and is an active topic as presented in Section 1.3.2. In Chapter 3, we prove that systems such that ū ą 1 are not feasible.

In the remainder of this thesis, all variables written with a bar, i.e., x refer to a priority level.

Let us define the three following stochastic processes:

(i) N k ptq "
ř 8 l"1 1 r0,ts pA k,l q as the number of jobs of τ k released before t ą 0, (ii) the k-level demand Wk ptq as the accumulation of the execution times required by jobs of priority higher or equal than τ k , regardless of potential deadline misses, released before the instant t to complete, Wk ptq "

k ÿ i"1 N i ptq ÿ j"1 C i,j
(iii) the k-level backlog β k ptq as the remaining workload of level k at t ě 0, defined by

β k ptq " Wk ptq ´ż t 0 1 tβ k psqą0u ds
The demand represents the workload required by the jobs arriving over time.

The goal of schedulability tests is then to check in which proportion of Ω this demands fits the processor time (otherwise called budget) given to those jobs.

Pessimism

In probabilistic systems, some authors like Diaz [START_REF] Díaz | Pessimism in the stochastic analysis of real-time systems: Concept and applications[END_REF] introduced the concept of pessimism for probabilistic systems in a formal way, which is itself called stochastic dominance in the probability field.

Definition 2.19 (Pessimism [START_REF] Díaz | Pessimism in the stochastic analysis of real-time systems: Concept and applications[END_REF]). We say that X is more pessimistic than Y if and only if PpY ą tq ď PpX ą tq for all t ą 0, and we write Y ď st X.

This property is also called stochastic dominance. Pessimism is a weaker kind of dominance than the usual inequality operator, as shown in the following lemma.

Lemma 2.6. Let X and Y be two timing variables. If X ď Y , then X ď st Y .

Proof. First of all, since X ď Y , we get for all t ą 0 that PpY ą t | X ą tq " 1 which implies that

@t ą 0, PpX ą t, Y ą tq " PpX ą tq (2.13) Then PpX ą t | Y ą tq " PpX ą t, Y ą tq PpY ą tq " PpX ą tq PpY ą tq (according to (2.13))
Hence @t ą 0, PpXątq PpY ątq ď 1 and we have the result.

Blocking time

We denote C i,N i ptq the execution time of the last job released before the instant t ą 0. Depending on the discarding policy, jobs wait a certain amount of time between their release and their actual execution. For a task τ i , we call blocking time the process defined for all t ą 0 by

$ & % B 0 ptq " 0 B k ptq " ř k i"1 minpβ i ptq ´Bi´1 ptq, C i,N i ptq q
as the amount of time the most recent job before t ą 0 τ i,N i ptq has to wait before its execution. In Figure 2.3 for example, the dotted area represents the blocking time of τ 2 .

In opposition to the backlog, the blocking time takes into account the discarding policy. Note that the following inequality allows us to bound the blocking time, which we do in the next chapter.

Proposition 2.1. For all t ą 0,

B k ptq ď min ˜βk ptq, k ÿ i"1 C i,N i ptq ¸(2.14)
Proof. First of all, since B 0 ptq " 0, we have B 1 ptq " minpβ 1 ptq, C 1,N 1 ptq q. Then, by induction, suppose that (2.14) holds. B k`1 ptq is such that

B k`1 ptq " B k ptq `minpβ k`1 ptq ´Bk ptq, C k`1,N k`1 ptq q ď min `βk`1 ptq, B k ptq `Ck`1,N k`1 ptq ď min ˜βk`1 ptq, k`1 ÿ i"1 C i,N i ptq ţhus we have (2.14)
Hence we have the two following variable that are more pessimistic than B i ptq thanks to the following proposition.

Corollary 2.3. For all t ą 0, B k ptq ď st β k ptq.

Proof. Apply Lemma 2.1 and Lemma 2.6.

Corollary 2.4. For all t ą 0, B k ptq ď

ř k i"1 c max i .
Proof. Apply Lemma 2.1 and the fact that the execution time C i is bounded by

c max i .

Response times

Due to the static-priority policy, the response time of task τ i depends on those of higher priority tasks.

Definition 2.20 (Response time).

The response time R k,l of a job τ k,l is the size of the smallest interval after its arrival time A k,l where the blocking time of level i

is zero, i.e., R k,l " inf tt ą 0 : B k pA k,l `tq " 0u (2.15)
Example 2.1. Consider a task set tτ 1 , τ 2 u, and that τ 2 is activated at t " 0, i.e., O 2 " 0, and

C 2,1 " y " 3. Let PpC 1 " 1q " 1{2, PpC 1 " 2q " 1{2, PpT 1 " 2q " 1{2, PpT 1 " 4q " 1{2, and suppose B 1 p0q " x `y " 8, C 1,1 " 1, 0 2 4 6 8 10 τ 1 τ 2 Figure 2.2: τ 2,1
is the first job of τ 2 and is released at time 0. Its response time is equal to 8. It starts executing at 1, its blocking time is 1 as it is blocked by the job τ 1,1 also released at time 0. It is preempted by τ 1,2 at time 3, and τ 1,3 at time 6.

C 1,2 " 2, C 1,3 " 2, and O 1 " 2, A 1,2 " 6, A 1,3 " 10 and A 1,4 " 14. Then the response time R 2,1 is the first instant t when B 1 ptq " 0:

B 1 p1q " W 1 p0q " x `y B 1 p3q " W 1 p0q `C1,1 ´3 " x `y ´2 B 1 p7q " W 1 p0q `C1,1 `C1,2 ´7 " x `y ´4 B 1 p11q " W 1 p0q `C1,1 `C1,2 `C1,3 ´11 " x `y ´6 B 1 p13q " W 1 p0q `C1,1 `C1,2 `C1,3 ´13 " x `y ´8 " 0 Hence R 2,1 " 13. This is illustrated in Figure 4.2. To build all possible values of R 2,1 , one must do the same for all combinations of possible values of pA 1,1 , A 1,2 , A 1,3 , A 1,4 q and pC 1,1 , C 1,2 , C 1,3 , C 1,4 q.
The discarding policy of a scheduling policy is the decision taken when a deadline is missed. When firm deadlines are missed, jobs are instantly discarded. Thus, for example, a job can be discarded when it misses its deadline. This is the most common discarding policy. However, others can be imagined: no discarding from a certain amount of time, discard the next job, etc. This is illustrated in

0 2 4 6 τ 1 τ 2 (a) The job of τ 1 is discarded. 0 2 4 6 τ 1 τ 2 (b)
The job of τ 1 is not discarded. Theorem 2.5 (Theorem 1 in [START_REF] López | Stochastic analysis of real-time systems under preemptive priority-driven scheduling[END_REF]). Let R be the response time of a job with blocking time b and R 1 be the response time of this same job with blocking

time b 1 . Then if b 1 ě b, R ď st R 1 ,i.e., R 1 is more pessimistic than R. Proof. We have R " b `X and R 1 " b 1 `X. If b 1 ě b, we get R ď R 1 , hence
applying Lemma 2.6 gives us the result.

Corollary 2.5. Response time analyses considering a non-discarding policy are more pessimistic than any other discarding policy.

Proof. Direct application of Theorem 2.5, since non-discarding schedule provide the largest possible blocking times when no job discarding is applied.

Pessimist response time analysis

As introduced in [START_REF] Joseph | Finding response times in a real-time system[END_REF], the response time R k,l of a job τ k,l is the smallest instant after its arrival time A k,l lower than the time it is given to run the level k demand. The point of the following theorem is to provide a more pessimistic variable than R k,l . A formal translation of this definition couples with Corollary 2.5 gives us the following results.

Theorem 2.6 (Response time bound). Let pΩ, P, Γ, tθ t uq follow a

ř i M i { ř i G i {1{SP queueing model. The response time R k,l is such that R k,l ď st inftt P p0, T k q : β k pA k,l q `W k ptq ´W k p0q ď tu (2.16)
Proof. First of all, B k ptq ď β k ptq for all t ą 0 according to Proposition 2.1. Hence according to Definition 2.20,

R k,l ď inftt P p0, T k,l`1 q : β k pA k,l `tq " 0u
Then for any a ą 0,

β k pt `aq " Wk pt `aq ´W k paq `W k paq ´ż a 0 1 tβ k psqą0u ds ´ż a`t a 1 tβ k psqą0u ds " β k paq `W k pt `aq ´W k paq ´ż a`t a 1 tβ k psqą0u ds
thus according to Definition 2.20, R k,l can be stochastically dominated by inf

# t P p0, T k,l`1 q : β k pA k,l q `W k pA k,l `tq ´W k pA k,l q ď ż A k,l `t A k,l 1 tβ k psqą0u ds + (2.17) since R k,l
is the first instant after A k,l that the backlog β k,l is null, it means that on the interval s P rA k,l , A k,l `Rk,l s we have 1 tβ k psqą0u " 1, which allows to rewrite (2.17) as

R k,l " inftt ą 0 : β k pA k,l q `W k pA k,l `tq ´W k pA k,l q ď pA k,l `t ´Ak,l qu (2.18) Furthermore, Wk pa `tq ´W k paq " k ÿ i"1 N k pt`aq ÿ j"N k paq`1 C i,j
and since the N i 's are renewal processes and the pC i,j q j are i.i.d., we get

Wk pa `tq ´W k paq pdq " Wk ptq ´W k p0q (2.19)
Finally with (2.18), (2.19) and the fact that

T k,l`1 is independent from A k,l , β k and
W k , and is with the same distribution as T k we get the result.

This last theorem allows to consider the simultaneous activation of tasks as the worst-case as we see in the following.

Theorem 2.7 (WCRT). Consider a stationary real-time system and let R max k

" inftt P p0, T k q : ř k´1 i"1 c max i `W k ptq ď tu. Then, @l P N, R k,l ď st R max k
Proof. With the discarding policy, the blocking time of level i is always bounded by

ř i k"1 c max k
. Hence applying Theorem 2.6 with β i pA i,j q "

ř i k"1 c max k gives the result.
This method is called TDA. TDA holds for any static-priority preemptive singleprocessor model with the discarding policy discussed in Section 2.3.3, thanks to the following theorem.

Theorem 2.8 (Theorem 3 in [START_REF] Burns | Sustainability in realtime scheduling[END_REF]). Deterministic TDA of static-priority preemptive single processor systems with independent tasks is sustainable.

This last theorem is the reason why the probabilistic analysis is possible for real-time systems and that TDA works on stationary real-time systems just like any periodic deterministic real-time system.

Deadline miss probabilities

The DMP of a job τ k,l is the probability that its response time is greater than its deadline on any possible sequence of environments. In order to compute it, we is finite and such that all tasks τ i P Γ satisfy

p max i " P pR max i ą D i q ď α i (2.21)
In those terms, checking if a task is schedulable is checking if the WCRT R max i is finite and p max i ď α i for all tasks τ i P Γ is the goal of Chapters 3 and 4.

Processor model

A uniform multiprocessor system is a set of processors Π " tκ 1 , . . . , κ m u composed of processors κ P Π of respective speed spκq P r1, s max s, i.e., κ can process spκq workload units in one unit of time. We consider Π ordered by decreasing speeds, i.e., spκ i q ą spκ j q if i ă j. Let κ P Π be a processor at a given state in time and a task τ i P Γ.

We denote the local mean utilization of the task τ i on the processor κ by

u i pκq " λ i ErC i s spκq (2.22)
and suppose for all 1 ď i ď n and 1 ď j ď m that u i pκ j q ă 1. We define Γ ì pκq (resp. Γ í pκq) to be the set of tasks of priority higher (resp. lower) or equal to the priority of τ i active on the processor κ at a given time, and let ūi pκq " ÿ

τ j PΓ ì pκq u i pκq (2.23)
be the local mean utilization of level i in the processor κ and, respectively, let vi pκq "

1 spκq ¨ÿ τ j PΓ ì pκq λ j ErC 2 j s '1 {2
be the local deviation of level i on the processor κ, that is the sum of the utilization (resp. deviation) of the tasks in Γ ì pκq. Let the local maximum deviation of level i in κ. Definition 2.22 (Stationary Multiprocessor system). Let pΩ, P, Γ, tθ t uq be a stationary real-time system as defined in Definition 2.17, and Π be a multiprocessor system. We call pΩ, P, Γ, Π, tθ t uq a stationary multiprocessor system. Without any loss of generality, we refer to it as a stationary real-time system.

Rate Monotonic

Real-time scheduling is the decision process deciding which job should be executed.

Online priority-driven scheduling algorithms are typically implemented as follows:

at each time instant, they allocate an available processor to the highest-priority job. Static-priority algorithms satisfy the property that for two tasks τ i and τ j , whenever τ i and τ j are both have active, it is always the case that the jobs of one task have priority over the other. With dynamic priority algorithms in the other hand, it is possible that some tasks τ i and τ j both have active jobs simultaneously, but in some case the job of τ i has a higher priority than the job of τ 2 and in other cases the opposite. Scheduling algorithms that allow such "switching" of priorities between jobs are known as dynamic-priority algorithms. We cover in this thesis only static-priority policies.

The two famous and widely used scheduling policies RM and EDF are proven optimal in some well defined models. RM is a scheduling algorithm used to prioritize the scheduling of processes based on their relative rate in the case of periodic systems. The algorithm assigns higher priority to a tasks that are given higher maximum rates, meaning that the most important processes are scheduled more often than lower rate processes. Meaning that τ i has priority over τ j if λ i ą λ j . This type of scheduling algorithm is useful for ensuring that the most important tasks are completed on time and with minimal delays. EDF is used for its dynamic computation of priorities : each instance of a program has its own priority as a function of its deadline. It is also shown optimal in the non preemptive single processor case for example, and many of its variants are studied in [START_REF] Liu | Scheduling algorithms for multiprogramming in a hard-real-time environment[END_REF], Baruah and Baker, 2008, Baruah and Goossens, 2008]. Theorem 2.9 (Hyperbolic bound [START_REF] Bini | Rate monotonic analysis: the hyperbolic bound[END_REF]). In the case of a single processor preemptive RM scheduling, with periodic inter-arrival times and implicit deadlines, if

n ź i"1 pλ i c max i `1q ď 2 (2.24)
the system is schedulable with a permitted failure rate equal to zero.

In the case of multiprocessor scheduling, i.e., m ě 2, the RM policy is verified schedulable for identical multiprocessor systems global scheduling when

ūmax n ď m 2 3m ´1 ; @τ i P Γ, λ i c max i ď m 3m ´2 (2.25)
and by allocating jobs to any available processor, all tasks are schedulable with a permitted failure rate equal to zero [START_REF] Andersson | Staticpriority scheduling on multiprocessors[END_REF]. In [START_REF] Baruah | Ratemonotonic scheduling on uniform multiprocessors[END_REF] authors extend this result to uniform heterogeneous multiprocessor systems. The system is schedulable with permitted failure rates equal to zero when

ūmax n ď 1 2 ˜ÿ κPΠ spκq ´p1 `Λq max τ i PΓ tλ i c max i u ¸(2.26)
where Λ " max κ j PΠ 1 spκ j q ř m i"j`1 spκ i q measures the degree by which Π differs from an identical multiprocessor system.

Finally, for the restricted migration the utilization bound of RM on a multiproces-sor system with identical processors of speed s is proven [START_REF] Goossens | Job partitioning strategies for multiprocessor scheduling of real-time periodic tasks with restricted migrations[END_REF] Utilization-based schedulability conditions for single-core static-priority preemptive scheduling policies are widely studied [START_REF] Davis | A review of priority assignment in real-time systems[END_REF]. The seminal work of [START_REF] Liu | Scheduling algorithms for multiprogramming in a hard-real-time environment[END_REF] introduces a sufficient condition for the feasibility of a real-time system using its maximal utilization. Nevertheless, a real-time system not satisfying this sufficient condition may remain schedulable with a given probability (see Eq. ( 2.21) in Section 2). Moreover, while probabilistic methods have been focused towards fitting in this sufficient condition by providing less pessimistic analyses, their domain of feasibility needs to be defined as well. In this thesis, we build necessary feasibility conditions for static-priority scheduling policies based on the mean utilization of the real-time system. We demonstrate that a mean utilization smaller than 1 is mandatory for response times to be finite, c.f., Propositions 4.2 and 4.4. We call systems with a mean utilization smaller than 1, stable real-time systems.

Stochastic analysis background

The elements presented in this chapter are widely inspired from the books of François Baccelli and Pierre Brémaud, Elements of queueing theory, [START_REF] Baccelli | Elements of queueing theory: Palm Martingale calculus and stochastic recurrences[END_REF] and, Hong Chen and David D. Yao, Fundamentals of queueing networks: Performance, asymptotics, and optimization, [START_REF] Chen | Fundamentals of queueing networks: Performance, asymptotics, and optimization[END_REF].

Brownian motions

In order to statistically describe the behavior of real-time systems we use a process called Brownian Motion. It allows to provide theorems similar to the central limit theorem for stochastic processes. All definitions and results presented in this section can be found in [ Le Gall, 2016].

Definition 3.1 (Standard Brownian motion). A standard Brownian Motion is a process B " pBptq, t ą 0q such that • Bp0q " 0, • Bpt `sq ´Bpsq " Φ 0,t , for t, s ą 0, • Bptq ´Bpsq is independent of Bpuq ´Bpvq for t ą s ą u ą v ą 0,
• B is continuous. for all t ą 0. For each t ą 0, the distribution function of W ptq ´W p0q is Φ ut,v 2 t .

Theorem 3.1 (First-passage time of a Brownian motion, [Abundo, 2016]). Let W be a Brownian motion of drift u ą 0 and deviation v ą 0. Let Ipxq be the first-passage time of W on 0 when W p0q " x ą 0, i.e.,

Ipxq " inftt ą 0 : W ptq " 0u

Then Ipxq has an inverse Gaussian distribution of mean x{u and shape px{vq 2 .

Definition 3.3 (Reflected Brownian motion, Theorem 6.1 [START_REF] Chen | Fundamentals of queueing networks: Performance, asymptotics, and optimization[END_REF]).

A process β is called a reflected Brownian motion of drift u and deviation v ą 0 if there exists a Brownian motion W of drift u and deviation v ą 0 such that for all t ą 0, βptq " W ptq `sup sPr0,ts p´W psqq Theorem 3.2 (Theorem 6.2 [START_REF] Chen | Fundamentals of queueing networks: Performance, asymptotics, and optimization[END_REF]). Let β be a reflected Brownian motion of drift u and deviation v ą 0. If u ă 0, then the distribution of lim tÑ8 βptq is an exponential distribution of parameter

η " ´2u v 2
and is called the steady-state distribution of β.

Backlog process

We now consider the evolution of the execution of tasks and the demand. Let W be a demand process. We introduce the backlog process as the remaining demand at a given instant

βptq " W ptq ´ż t 0 1 tβpsqą0u ds (3.2)
describing the remaining demand at the instant t ą 0, after having been executed at most t units of time. The term ş t 0 1 tβpsqą0u ds is stochastic and represents the amount of time the system is not idle considering the work-conserving assumption. This backlog process satisfies the relation βpa n`1 q " pβpa n q `cn`1 ´tn`1 q `, @n P N (3.3)

where the pa n q, pc n q, pt n q are respectively sequences of arrival times, execution times and inter-arrival times. Eq. (3.3) is at the basis of the shrink and convolve method used by many, e.g., [START_REF] Díaz | Pessimism in the stochastic analysis of real-time systems: Concept and applications[END_REF], Kim et al., 2005, Palopoli et al., 2012, Villalba Frias, 2018, von der Brüggen et al., 2021]. Under some conditions, this backlog process has asymptotic properties according to the following theorem.

Theorem 3.3 (Steady-state backlog [Loynes, 1962]). Let β be the backlog process of a M {G{1 queueing model as defined in (3.2). If Erc 0 s ă Ert 0 s, the limit β " lim tÑ8 βptq exists, is finite and is equal to

β " ˜sup n n ÿ j"1 c j ´tj
¸Ìn the next section, we use this backlog process at priority levels, i.e., by considering the demand of not only a task but also of higher priority tasks. This allows to model the arrival of jobs of a static-priority scheduling policy. Indeed, at priority level, we know that while there is workload from higher priority, it is sufficient to check the workload of priority level k and the time that passed between

Memoryless backlog

In this chapter, we present an analytical approximation of the demand of probabilistic real-time systems, using a fluid model associated to the actual demand of the system.

Fluid models are widely used in queueing theory [START_REF] Baccelli | Elements of queueing theory: Palm Martingale calculus and stochastic recurrences[END_REF] in order to determine asymptotic results. In real-time systems, a famous example is the DP-FAIR scheduling algorithm [START_REF] Levin | Dp-fair: A simple model for understanding optimal multiprocessor scheduling[END_REF], that uses the fluid model of the backlogs to determine scheduling decisions for homogeneous multiprocessor systems.

Let pΩ, P, Γ, tθ t uq be a stationary real-time system following the queueing model

ř i M i { ř i G i {1{SP
, such that Γ is ordered by decreasing priority order, i.e., τ i has priority over τ i`1 . Let us remind the three following stochastic processes:

(i) N k ptq "
ř 8 l"1 1 r0,ts pA k,l q as the number of jobs of τ k released before t ą 0, of mean ErN k ptqs " λ k t, see Definition 2.15. N k is right-continuous with left limit (RCLL) and integer-valued.

(ii) the k-level demand Wk ptq as the workload required by jobs of priority higher 3.1 or equal than τ k , regardless of potential deadline misses, released before the instant t to complete, Wk p0q ě 0, Wk ptq " [Janssen and Manca, 2006, (6.53)]. Wk is RCLL and positive.

k ÿ i"1 N i ptq ÿ j"1 C i,j of mean Er Wk ptqs " ř k i"1 ErN i ptqsErC i s " ūk t, see
(iii) the k-level backlog β k ptq as the remaining workload of level k at t ě 0 when Γ is ordered in a decreasing priority order and scheduled with a preemptive static-priority scheduling policy, defined by

β k ptq " Wk ptq ´ż t 0 1 tβ k psqą0u ds (3.4)
where ş t 0 1 tβ k psqą0u ds is the total busy time of level k [Lehoczky, 1990, p. 2] before t ą 0. β k is RCLL and positive.

The backlog process β i is such that for t P rA i,j , sq and s ă inftA p,l : A p,l ą A i,j u, β k ptq " pβ k pA i,j q `Ci,j ´pt ´Ai,j qq ẁhich is known as Lindsley's equation [Lindley, 1952]. β k is not a Markovian process in general, but a stochastic recurrence [START_REF] Baccelli | Elements of queueing theory: Palm Martingale calculus and stochastic recurrences[END_REF].

Example 3.1 (Backlog). Let us consider the task set tτ 1 , τ 2 u, with PpC 1 " 1q " 1, PpT 1 " 2q " 1, PpC 2 " 1q " 1{2, PpC 2 " 2q " 1{2, PpT 2 " 3.1q " 1{2,
PpT 2 " 4q " 1{2. Suppose both tasks τ 1 and τ 2 are activated at time t " 0 and

T 2,2 " 3.1, C 2,1 " 2, C 2,2 " 1. Then, W2 p0q " 1 `2, β 2 p2q " W2 p2q ´ş2 0 1 tβ 2 psqą0u ds " p1 `2 `1q ´2 " 2 β 2 p3q " W2 p3q ´ş3 0 1 tβ 2 psqą0u ds " p1 `2 `1q ´3 " 1 β 2 p3.1q " W2 p3.1q ´ş3.1 0 1 tβ 2 psqą0u ds " p1 `2 `1 `1q ´3.1 " 1.9 β 2 p3.2q " W2 p3.2q ´ş3.2 0 1 tβ 2 psqą0u ds " p1 `2 `1 `1q ´3.2 " 1.8
At the instant t " 3.2, the backlog of level 2 is 1.8.

The process β k describes the remaining demand without considering deadline misses, i.e., while jobs are discarded their demand remains in the backlog analysis. Thus, the process β k is an upper-bound of the blocking time, see Eq. (4.4), i.e., the response time analysis that we provide in Chapter 4 is pessimistic as defined in [START_REF] Díaz | Pessimism in the stochastic analysis of real-time systems: Concept and applications[END_REF].

We express in the following the backlog process in a more convinient way. Lemma 3.2 (Theorem 6.1 [START_REF] Chen | Fundamentals of queueing networks: Performance, asymptotics, and optimization[END_REF]). For any right-continuous with left limits process X, there exists a unique pair of processes pZ, Y q such that (S1) Z " X `Y ě 0,

(S2) ş 8 0 ZptqdY ptq " 0, (S3) dY ptq ě 0, Y p0q " 0.
Furthermore, Y ptq " sup sPr0,ts p´Xpsqq `.

Lemma 3.2 solves a reflexion mapping problem called the One dimensional Skorokhod problem. We use is in the following to express the right limit of the backlog process.

Theorem 3.4 (Section 6.2 [START_REF] Chen | Fundamentals of queueing networks: Performance, asymptotics, and optimization[END_REF]). The backlog of level k is such that

β k ptq " Wk ptq ´t `sup sPr0,ts ps ´W k psqq `(3.5)
for all t ą 0.

Proof. Let Xptq " Wk ptq ´t and Y ptq " ş t 0 1 β k psq"0 ds. Clearly, β k ptq " Xptq `Y ptq. We call Y the idle time process. The following relations must hold: For all t ą 0,

(i) β k ě 0, (ii) ş 8 0 β k ptqdY ptq " 0, (iii) dY ptq ě 0, Y p0q " 0.
In other words, dY ptq ě 0 means that Y is nondecreasing, since the idle time process is measured as a cumulation of a positive quantity over time; and ş 8 0 β k ptqdY ptq " 0 reflects the fact that the idle time cannot cumulate when the backlog is positive.

From Lemma 3.2, we check the pS1q ´pS3q conditions, hence we know that Y ptq " sup sPr0,ts ps ´W k psqq `and we get Eq. (3.5).

The Loynes theorem

In this section, we define the domain of the steadiness, provide an expression of the instant when the system goes from transient to steady, and prove that this time instant exists and is finite under some conditions. Definition 3.4 (Steady-state backlog). For a stable real-time system Γ, the steadystate backlog is defined by βk " lim We use background results of queueing theory presented in 3.2.1 and 3.2.2, provide the exact formulation of the steady-state backlog distribution π k and illustrate this result in the deterministic inter-arrival case already studied by Diaz et al. [START_REF] Díaz | Stochastic analysis of periodic real-time systems[END_REF] in Section 3.3.

As the demand and backlog processes Wk and β k are well studied in queueing theory [START_REF] Baccelli | Elements of queueing theory: Palm Martingale calculus and stochastic recurrences[END_REF], Chen and Yao, 2001, Jeanblanc et al., 2009],

we provide the formula of the steady-state of the system, by adapting Theorem 3.1 for the

ř i M i { ř i G i {1{SP queueing model. Proposition 3.1. Let pΩ, P, Γ, tθ t uq follow a ř i M i { ř i G i {1{SP queueing model. Let
Āk,l " inftt ą 0 :

k ÿ i"1 N i ptq " lu
be the activation time of the l-th job of level k, and Īk,l the index of the task of the l-th job of level k, and let Ck,l " CĪ k,l ,N Īk,l p Āk,l q be the execution time of the l-th job of level k. Then,

• if ūk ă 1 the steady-state backlog βk exists, is finite and is equal to

βk " ˜sup n n ÿ l"1
Ck,l ´p Āk,l`1 ´Ā k,l q ¸`(3.6)

where x `" maxp0, xq, c.f., [Baccelli and Brémaud, 2013, Property 2.2.1] and Theorem 3.3. In addition, there is an infinite number of idle times, c.f., [Baccelli and Brémaud, 2013, Property 2.2.5],

• if ūk " 1, then the existence of a finite steady-state βk is uncertain,

• If ūk ą 1, there exists a finite number of idle times of level k and no finite steady-state, c.f., [Baccelli and Brémaud, 2013, Property (2.2.2)], backlogs are always transient.

Proof. First of all, the Example 3.1.3 [START_REF] Baccelli | Elements of queueing theory: Palm Martingale calculus and stochastic recurrences[END_REF] shows that a stationary point process with priority class jobs is still associated to a point process of intensity ūk . According to Theorem 2.3, the superposition of Poisson point processes is still a Poisson process, hence, the superposition of the arrival of all jobs of level k is a stationary point process. Let Āk,l " inftt ą 0 : ř k i"1 N i ptq " lu be the activation time of the l-th job of level k, and Īk,l the index of the task of the l-th job of level k, and let Ck,l " CĪ k,l ,N Īk,l p Āk,l q be the execution time of the l-th job of level k. In that way, the arrival of jobs of level k form a M {G{1 model. We use the property of marked Poisson processes shown in Lemma 2.3:

@l, Pp Īk,l " iq " λ i ř k i"1 λ i (3.7)
The Īk,l are independent from the C i,j , j ě 1 (not Ck,l !), T i,j , j ě 1 and a fortiori of A i,j , j ě 1. Then we have for any A Ă R ` Pp Ck,l P Aq "

k ÿ i"1 PpC i,N i p Āk,l q P A | Īk,l " iqPp Īk,l " iq " k ÿ i"1 PpC i P A | Īk,l " iqPp Īk,l " iq " 1 ř k i"1 λ i k ÿ i"1 λ i PpC i P Aq
Then we use Theorem 3.3 on this superposed process with the execution times Ck,l and inter-arrival times Āk,l`1 ´Ā k,l pdq " min i"1,...,k T i which is exponential of parameter ř k i"1 λ i , marked by the Īk,l . Ck,l and Āk,l`1 ´Ā k,l are dependent through the mark Īk,l , but this independence is not required in the proof of Theorem 3.3, c.f., Example 1.4.4 [START_REF] Baccelli | Elements of queueing theory: Palm Martingale calculus and stochastic recurrences[END_REF].

Our goal is to find the distribution of the steady-state backlog βk . However, given the generality of this model, we cannot provide an exact description of the process β k . The heavy-traffic assumptions allows us to find an approximation for the distribution of the steady-state backlog βk when the system utilization gets close to 1, c.f., Figure 3.2, i.e., we build a process β p8q k such that its steadystate approximates βk .

The heavy-traffic theorem

A first step in the approximation of the backlog process β k is the approximation of the demand process Wk . The following theorem provides a fluid model, that is a continuous version of the backlog process using asymptotic results. Fluid models are widely used in queueing theory [START_REF] Chen | Fundamentals of queueing networks: Performance, asymptotics, and optimization[END_REF] in order to determine asymptotic results. In real-time systems, a famous example is the DP-FAIR scheduling algorithm [START_REF] Levin | Dp-fair: A simple model for understanding optimal multiprocessor scheduling[END_REF], that uses the fluid model of the backlogs to determine optimal decisions for homogeneous multiprocessor systems that we discuss in more details in Chapter 6. The idea behind heavy-traffic, is that we look at the workload processes in the long time, i.e., we put the processes in a limit situation, and analyze this limit.

Let us define the sequence of re-scaled processes

$ & % W pnq k ptq " Wk p0q `n´1 Wk pntq `n´1{2 p Wk pntq ´ū k ntq β pnq k ptq " β k p0q `n´1 β k pntq `n´1{2 pβ k pntq ´pū k ´1qntq
(3.8)

and look for their limit.

ř k i"1 λ i ErC 2 i s. See Figure 3.1 for an illustration.
Proof. The proof is based on the Laplace transform of the demand process. Let N i be the associated Poisson process of arrivals of τ i . Let W i ptq " ř N i ptq j"1 C i,j where C i , C i,1 , . . . are the i.i.d. execution times of τ i , and its Laplace transform

Ere ξW i ptq s " E " e ξ¨ř N ptq j"1 C i,j ı " ÿ ně0 E " e ξ¨ř n j"1 C i,j |N i ptq " n ı PpN i ptq " nq
The Poisson processes N i and the execution times are independent, and N i ptq is a Poisson variable of parameter λ i t, i.e.,PpN i ptq " nq " e ´λi t pλ i tq n n! , which leads us to

Ere ξW i ptq s " ÿ ně0 E " e ξ¨ř n j"1 C i,j ı e ´λi t pλ i tq n n! " e ´λi t ÿ ně0 pλ i tq n n! n ź j"1
Ere ξC i,j s Finally, the variables C i , C i,1 , C i,2 . . . are identically distributed, hence ś n j"1 Ere ξC i,j s " Ere ξC i s n , which leads to

Ere ξW i ptq s " e ´λi t ÿ ně0 Ere ξC i s n pλ i tq n n!
" e λ i tpEre ξC i s´1q (3.9)

In order to find the variance of W i ptq we use the following lemma:

Lemma 3.3 (Eve's law [START_REF] Blitzstein | Introduction to probability[END_REF]). Let X and Y be variables with finite variance. Then,

VarpY q " ErVarpY | Xqs `VarpErY | Xsq
Applying this last lemma to Y " W i ptq and X " N i ptq gives us

VarpW i ptqq " ErVarpW i ptq | N i ptqqs `VarpErW i ptq | N i ptqsq " ErN i ptqVarpC i qs `VarpN i ptqErC i sq " VarpC i qErN i ptqs `ErC i s 2 VarpN i ptqq " VarpC i qλ i t `ErC i s 2 λ i t (Because N i ptq is a Poisson variable of mean λ i ) " λ i tErC 2 i s let u i " λ i ErC i s, v 2 i " λ i ErC 2 i s and Wi ptq " W i ptq´u i t ? tv 2 i
. By noticing that Ere ξ Wi ptq s " Ere ξW i ptq{ ?

tv 2 i se ´ξtu i { ? tv 2 i
The Taylor expansion on e ξC i when t Ñ tÑ8 8 is well defined as C i is bounded. Then

Ere C i ξ{ ? tv 2 i s " Er1 `ξ a tv 2 i C i `ξ2 2tv 2 i C 2 i `˝pξ 2 qs
which leads with Eq. (3.9) to the convergence Ere

ř k i"1 W p8q i
is the sum of k independent Brownian motions, which is also a Brownian motion. Finally we get that for each t ą 0, W p8q k ptq ´W

p8q k p0q " Φ ūk t,v 2 k t .
In [Lehoczky, 1996], the author uses the heavy-traffic approximation providing the distribution of the lateness of jobs in a system with exponential inter-arrival times.

To illustrate the heavy-traffic approximation, one can think of water continuously flowing into a sink at a rate λ i and the execution times as the rate 1{ErC i s the water leaves the sink. It is usually understood as true when the system is at full processor utilization, because the theorems of heavy-traffic theory are exact when ū Ñ 1.

However we use it as a way to build an upper-bound of the backlog process. Indeed, the heavy-traffic assumption should be seen as a bound, or more specifically, a way to suppose that the system utilization is at its maximum (i.e., ū " 1), providing upper-bounds that are exact when the processor utilization at 100%. In this section, we use the heavy-traffic assumption to find the steady-state backlog βk as an approximation upper-bounding the blocking time of the system in its steady-state, see Eq. (4.4). The approximation in Theorem 3.5 leads to the standard Brownian motion which is continuous. It means that instead of looking at the demand for a large amount of time, we consider a re-scaled version of the demand in order to build a good approximation. Theorem 3.5 can be written as

W p8q k ptq " Wk p0q `ū k t `v k Bptq (3.10)
where B is a standard Brownian motion, as defined in Eq. (3.1).

In order to find the steady-state backlog βk , we work with the heavy-traffic demand W pnq k .

Proposition 3.2. The rescaled backlog process of level k is defined by

β pnq k ptq " W pnq k ptq ´t `sup sPr0,ts ps ´W pnq k psqq `(3.11)
Proof. From its definition in Eq (3.8), we have

β pnq k ptq " Wk p0q `W k pntq n ´1 n ż nt 0 1 β k psqą0 ds `1 ? n ˆW k pntq ´ż nt 0 1 β k psqą0 ds ´pū k ´1qnt " Wk p0q `W k pntq n ´1 n ż nt 0 1 β k psqą0 ds `?n ˆW k pntq n ´ū k t ˙´1 ? n ż nt 0 1 β k psqą0 ds `?nt " W pnq k ptq ´1 n ˆnt ´ż nt 0 1 β k psq"0 ds ˙´1 ? n ˆnt ´ż nt 0 1 β k psq"0 ds ˙`? nt " W pnq k ptq ´t `p1 `1 ? n q 1 ? n ż nt 0 1 β k psq"0 ds (3.12)
Then let X pnq ptq " W pnq k ptq´t and Y pnq ptq " p1`1 ? n q 1

? n ş nt 0 1 β k psq"0 ds. β pnq k , X pnq and Y pnq should satisfy pS1q ´pS3q, thus by applying Lemma 3.2 to X pnq wet get that the pair pβ pnq k , Y pnq q is unique and Y pnq ptq " sup sPr0,ts ps ´W We have

β p8q k ptq " lim nÑ8 W pnq k ptq ´t `lim nÑ8 p1 `1 ? n q 1 ? n ż nt 0 1 β k psq"0 ds (From Eq. (3.12)) " W p8q k ptq ´t `lim nÑ8 1 ? n ż nt 0 1 β k psq"0 ds Finally, let Y ptq " lim nÑ8 1 ? n ş nt 0 1 β k psq"0 ds. pβ p8q
k , Y q satisfy pS1q ´pS3q from Lemma 3.2, hence Y ptq " sup sPr0,ts ps ´W p8q k psqq `. W p8q k ptq ´t, t ě 0 being a Brownian motion of drift ūk ´1 and deviation vk , we conclude with Definition 3.3.

It is shown in [Chen and Yao, 2001, Remark 6.17, p. 148 Proof. Apply Theorem 3.2 and Theorem 3.6.

Periodic backlog

We consider in this section a stationary real-time system pΩ, P, Γ, tθ t uq following

the ř i D i { ř i G i {1{SP queueing model.
In opposition to memoryless scheduling, periodic systems use knowledge of the past to take scheduling decisions. In the previous section do not treat the periodic case, although we show in this section some exisiting results and build heuristics for the periodic case in the next chapter.

For the case where the tasks of the real-time system Γ are periodic and have deterministic deadlines, i.e., T k " λ ´1 k P N and G k pxq " 1 rλ ´1 k ,8q pxq for all τ k P Γ and x ą 0, also known as the Diaz and Kim (DK) model [START_REF] Díaz | Stochastic analysis of periodic real-time systems[END_REF], Kim et al., 2005, Díaz et al., 2004], the authors approximate the distribution function π k , resolving linear system equations and compute response times distributions with the help of convolutions.

The fastest computational complexity of convolutions is OpN log N q when N is the number of values that a probabilistic variable can take. Computing the exact values of π k quickly becomes an expensive operation when the number of tasks or the number of possible execution times gets larger, even with methods that soften those computations like Markovic et al. [START_REF] Marković | On the Convolution Efficiency for Probabilistic Analysis of Real-Time Systems[END_REF], Milutinovic et al. [START_REF] Milutinovic | Speeding up static probabilistic timing analysis[END_REF] or [START_REF] Maxim | Re-sampling for statistical timing analysis of real-time systems[END_REF] for example.

Moreover, the computation of response times has the same problem, as the number of possible values of βk quickly becomes large. With Eq. (3.16) we have an explicit formula of the distribution of βk , with Eq. (3.13) we know the error of the heavytraffic approximation, and with Theorem 3.1 we have an analytical expression of the backlog in the deterministic case. Indeed, let Tk " lcm `λ´1 1 , . . . , λ ´1 k ˘be the hyper-period of level k of Γ. In the DK model [START_REF] Díaz | Stochastic analysis of periodic real-time systems[END_REF], Kim et al., 2005], the authors consider the k-level backlog β k pt Tk q, t P N, i.e., the remaining demand of level k at the beginning of the t-th hyper-period. Diaz et al. [START_REF] Díaz | Stochastic analysis of periodic real-time systems[END_REF] have proven that the sequence `βk `t Tk ˘˘tPN is a stationary Markov chain when ūk ă 1. The sequence `βk pt Tk q ˘tPN is defined by Wk p0q ě 0 and

β k `pt `1q Tk ˘" `βk pt Tk q `W k p Tk q ´T k ˘for t P N.
Similarly to memorlyess systems, we get the asymptotic backlog as follows.

Proposition 3.4. Let pΩ, P, Γ, tθ t uq follow a

ř i D i { ř i G i {1{SP stationary queue- have ErW k,1 s " k ÿ i"1
ErN i p Tk qsErC i s (According to Lemma 2.4)

" k ÿ i"1 Ertλ i pO i `Tk qusErC i s ď k ÿ i"1 p 1 2 `λi Tk qErC i s (Because O i is uniform in r0, λ ´1 i s) " k 2 `ū k Tk
which leads to the condition k 2p1´ū k q ă Tk . We conclude with Theorem 3.3.

The representation in Eq. (3.16) is an efficient method to approximate the stationary distribution π k of the backlog process β k . Indeed, let us take an integer n ą 0, and generate a sample pW k,l q n l"1 independent and identically distributed sequence with the distribution of Wk `T k ˘. Eq. (3.16) provides the variable of distribution π k found in Diaz et al. [START_REF] Díaz | Stochastic analysis of periodic real-time systems[END_REF] and [START_REF] Kim | An exact stochastic analysis of priority-driven periodic real-time systems and its approximations[END_REF].

It also means that the variable max 1ďjďn ´řj l"1 `Wk,l ´T k ˘¯`i s an approximation of βk when n is large enough. This method is not expensive in complexity as it requires only to build the distribution function of Wk `T k ˘once.

In the periodic case, we are able to find a bound of deadline miss probabilities of the RM policy with the following.

Proposition 3.5 (Hoeffding DMP for periodic inter-arrival times with Rate Monotonic). Suppose that jobs of τ i arrive periodically with rate λ i . If ūk ă 1 and 1{λ k ą

ř k i"1 ErC i s 2p1´ū k q then PpR max k ą 1{λ k q ď exp ˆ´p1 ´ū k q 2 λ k vmax k ẇhere ūk " ř k i"1 λ i ErC i s is the mean utilization of level k and vmax k " ř k i"1 λ i pc max i ćmin i q 2
is the maximum deviation of level k.

Proof. Suppose the system is periodic with rate λ i . According to [von der Brüggen et al., 2018, Theorem 6], the Hoeffding inequality applied to a static-priority policy gives us

PpR max k ą 1{λ k q ď inf tPp0,1{λ k q tąEr Wk ptqs exp ˜´2 pt ´Er Wk ptqsq 2 ř k i"1 pc max i ´cmin i q 2 N i ptq ¸(3.17)
where N i ptq " rλ i ts is the number of jobs of the task τ j released before t ą 0 when all tasks are activated at t " 0, i.e., O i " 0, i " 1, . . . , k. According to Lemma 2.4 we have Er Wi ptqs " ř i j"1 ErN j ptqsErC j s. Since

λ i t ď ErN i ptqs ď λ i t `1 2 (3.18)
and ūk ă 1, we have the relation ūk t `1 2 ř k i"1 ErC i s ě Er Wk ptqs ě ūk t. Hence, t ą

ř k i"1 ErC i s 1´ū k implies t ą Er Wk ptqs. Suppose 1{λ k ą ř k i"1 ErC i s 2p1´ū k q
and t P p

ř k i"1 ErC i s
2p1´ū k q , 1{λ k q. With Eq. (3.18) we get

pt ´Er Wk ptqsq 2 ř k i"1 pc max i ´cmin i q 2 N i ptq ě tp1 ´ū k q 2 vmax k `t´1 ř k i"1 pc max i ´cmin i q 2 (3.19)
Finally the infinimum in Eq. (3.17) is reached for t " 1{λ i , and we are using the RM policy, thus we have λ i ď λ j for j ď i since we assume working under the RM policy, hence we get

vmax k `λk k ÿ i"1 pc max i ´cmin i q 2 ď 2v max k (3.20)
which gives us the result with Eq. (3.19).

Schedulability test

The difference between a non-discarding schedule and a discarding one is significant.

Indeed, the analysis provided in this chapter is agnostic from discarding jobs.

Schedulability test

However, the non-discarding and the discarding schedule of a schedulable task set Γ are the same, because all deadlines are satisfied a schedulable task set. Based on this fact, the appropriate way to test if there will be discarded jobs in steady-state is to check if the worst-case blocking time and the steady-state backlogs satisfy

@i, P ˜β i ď i ÿ j"1 c max j ¸ą 1 ´ε
for a small enough ε, which means that the discarding policy and the non-discarding policies are equivalent for all tasks.

Potential extensions

Extension to EDF and FIFO

The first step into dynamic scheduling, as for example EDF is to study the backlog processes considering that the priority is at the job level (in opposition to task level). Indeed, for static-priority policies, those variables are simply the backlog and demand of the lowest priority level. However, for EDF, levels of priority need to be defined not only for tasks but for jobs. In [START_REF] Díaz | Stochastic analysis of periodic real-time systems[END_REF], authors use the concept of ground jobs which are jobs released at an instant where the system is idle, and as shown in the Loynes theorem, when ū ă 1, idle times are finite.

This means that an analysis mixing the concept of ground jobs and idle times as defined in this thesis can provide an extension of our results for dynamic-priority scheduling. In [Lehoczky, 1996]

authors show that if ū ă 1, β p8q k is a reflected
Brownian motion of drift ´γ and deviation 2 ř i λ i where 0 ă γ ă 1 is such that for each n ą 0, the utilization of the process pβ k pntq{ ? nq t can be written 1 ´γ{ ? n,

for the EDF and FIFO policies. This means that even without showing the exact parameters of the first-passage time distributions, we can assume that response times belong in the same domain of distribution functions.

Extension to general stationary inter-arrival times

We studied two types of stationary task sets with static priorities: periodic and memoryless. However, considering renewal processes with other distributions than exponential for inter-arrival times is challenging. The main reason being that the superposition of stationary renewal processes are not renewal processes in general because inter-arrival times of each task become inter-dependent. We present in this section some theoretical background that could help generalize the results of this chapter. Let us recall that the stationary renewal process N i counts the number of jobs of τ i through time, and N " ř i N i counts all jobs regardless of which task those jobs are.

Palm-Khintchin theorem

The first property of renewal processes that could be use to generalize the results of this chapter is the equivalent of the central limit theorem for renewal processes.

Theorem 3.7 (Palm-Khintchine). Let N 1 , . . . , N n be n independent renewal processes with distinct inter-arrival rates λ i . Then the superposition N " ř n i"1 N i is asymptotically a Poisson process when n Ñ 8, if the following assumptions hold:

(i) ř n i"1 λ i ă 8 when n Ñ 8, (ii) λ i ď 1 n ř n i"1 λ i , @i
Then N converges to a Poisson process of inter-arrival rate λ " λ8 when n Ñ 8.

However this convergence can occur very slowly and might not be suited for all systems. This property is used in telecommunications and IoT, e.g., [START_REF] Metzger | Modeling of aggregated iot traffic and its application to an iot cloud[END_REF], and is the reason why Poisson processes are a widely used and studied renewal process.

Approximating the superposition with a stationary renewal processes

A result from 2001 [START_REF] Torab | On approximate renewal models for the superposition of renewal processes[END_REF] shows that approximating the superposition N of renewal processes by supposing that inter-arrival are indeed independent is possible and that there is a method that can minimize the error of such hypotheses. What we look for is preserve the stationarity of renewal processes when they are superposed. One property of renewal processes is that any renewal process can be modified to be stationary by adding a delay, or as we call it an offset, with a very specific distribution.

We denote by Ḡk the distribution function of the first arrival of the superposed process N . First of all, we know from [Baccelli and Brémaud, 2013, Example 1.4.1, p.35] and [Lawrance, 1973] that Ḡk pxq " 1 ´k ÿ

i"1

λ i λk p1 ´Gi pxqq ź j‰i p1 ´G0 j pxqqdx
where G 0 j pxq " λ j ş x 0 p1 ´Gj pxqqdx is the distribution of the offset of τ j as defined in (2.8). We call G 0 j the distribution of the recurrent time of the process N j , and suppose that the superposition is still stationary, hence characterizing the distribution of this first job arrival is enough to characterize all jobs arrivals.

The intensity used to approximate the distribution of N in [START_REF] Torab | On approximate renewal models for the superposition of renewal processes[END_REF] comes from the recurrent times instead of the inter-arrival times. By remarking that d dt G 0 j " λ j p1 ´Gj q, and setting g i " d dt G i we get the intensity

ν i " λ i 1 ´Gi 1 ´G0 j instead of µ i " g i 1´G i .
Finally, this new intensity is actually shown to minimize to quadratic error, and is of the form

ν ˚ptq " ř i ν i ptqpµ i ptq `řj‰i ν j ptqq ř i ν i ptq
The mean of the first arrival time is mk " Er Āk,1 s "

ż p1 ´Ḡ k ptqqdt " k ÿ i"1 λ i λk ż p1 ´Gi ptqq ź j‰i p1 ´G0 j ptqqdt
and by noticing that We test the hypotheses that we can actually use this same method in the following chapter. Probabilistic methods for the analysis of response times have many applications in real-time systems [START_REF] Davis | A survey of probabilistic timing analysis techniques for real-time systems[END_REF]. Two main directions have been explored: static methods for the exact computation and approximation of response time distributions [START_REF] Díaz | Stochastic analysis of periodic real-time systems[END_REF], Kim et al., 2005, Maxim and Cucu-Grosjean, 2013,Manolache et al., 2001] a priori, and the measurement-based application of the EVT method [START_REF] Liu | An EVT-based worst-case response time analysis of complex real-time systems[END_REF], Lu et al., 2012] approximating the distribution of the maximum values of response times a posteriori. Often, probabilities are considered for execution times and few papers consider probabilistic inter-arrival times and deadlines [START_REF] Maxim | Response time analysis for fixed-priority tasks with multiple probabilistic parameters[END_REF], Lehoczky, 1996[START_REF] Gaujal | Dynamic speed scaling minimizing expected energy consumption for real-time tasks[END_REF].

d dt Ḡk " k ÿ i"1 λ i λk p1 ´Gi q ź j‰i p1 ´G0 j q ˜gi 1 ´Gi `ÿ j‰i λ j 1 ´Gj 1 ´G0 j its variance is Varp Āk,1 q " ż px ´m k q 2 d Ḡk ptq " k ÿ i"1 λ i λk ż px ´m k q 2 p1

using fluid models

Moreover, the method introduced in [START_REF] Díaz | Stochastic analysis of periodic real-time systems[END_REF], Kim et al., 2005] requires a large amount of convolutions which have a high space and time complexity, and the analysis provided by Lehoczky [Lehoczky, 1996] is not suited to express response time distributions of static-priority scheduling.

The contributions of this chapter are based on queueing theory results [START_REF] Sparaggis | Optimal routing and scheduling of customers with deadlines[END_REF], Huang et al., 2015, Sethuraman and Squillante, 1999, Baccelli and Brémaud, 2013, Chen and Yao, 2001]. To the best of our knowledge, no result from the queueing theory is focused on general execution times and inter-arrival times, multi-class clients (i.e., different tasks) and the quantization of deadline misses of such systems. The only results based on queueing theory for real-time systems have been published within the thread of papers related to [Lehoczky, 1996],

where the author approximates the number of simultaneously activated jobs by a reflected at the origin Brownian motion. There is a proportional relation between the number of activated jobs and the workload of a system by applying the Little formula [Baccelli and Brémaud, 2013, Eq. (3.1.16)].

However, the author makes strong hypotheses restricting the model. The exponential distribution of inter-arrivals and execution times suggested in [Lehoczky, 1996] is a strong hypothesis. Furthermore, his model has another important limitation as it considers systems of jobs of only one task, which does not allow a response time analysis. To overcome this limitation, we consider a multi-class analysis describing tasks with parameters with different distributions. Thus, we extend the model proposed by [Lehoczky, 1996] and consider a more general case: all jobs are instances of various independent tasks scheduled with a static-priority policy.

Heavy-traffic approximation

In the following, we consider the conditional probability that the system starts with a level k demand x ě 0 and the job τ k,1 ,

P x k p¨q " Pp¨| Wk p0q " x, O k " 0q
Whenever we need to suppose Wk p0q " x, O k " 0, we say that we work under the probability P x k .

As previously defined, response times are idle times. We use this representation of response times to provide an approximation using the fluid model introduced in the previous chapter. The heavy-traffic response time does not take discarding into account, but as shown in the following, it bounds the response times of each M {G{1 queue of the rescaled sequence of queueing models.

Lemma 4.1 (Heavy-traffic response time bound). Let pR pnq k,l q n be the sequence of response times defined in Definition (4.1). Let pB pnq k,l q n be the associated sequence of blocking time processes. Then,

inftt ą 0 : B pnq pA k,l `tq " 0u ď st R pnq k,l
Now that we know that the sequence of response times considering the discarding policy are bounded by the heavy-traffic response time sequence, we look in the following at the limit of this sequence in order to use the Brownian approximation introduced in Chapter 3.

First idle time

We study in this section the first idle time of the limit demand process, i.e.,the first-passage to 0 of a Brownian motion. Definition 4.2 (Idle time). Let I k pxq be the first idle time of level k, i.e.,

I k pxq " inf ! t ą 0 : β p8q k ptq " 0 ) (4.1)
when the initial demand of level k is equal to x ą 0.

Lemma 4.2. The distribution of I k pxq is an inverse Gaussian distribution with probability function

ψ k pt, xq " ψ ˆt; x 1 ´ū k , x 2 v2 k ˙, t ą 0 (4.2)
where ψ is given in Definition 2.12, and exceedence function

Ψ k pt,
I k pxq " inf tt ą 0 : Bptq " tp1 ´ū k q{v k ´x{v k u
where B is a standard Brownian motion. When Wk p0q " x, the distribution of I k pxq is an inverse Gaussian distribution of mean x{p1 ´ū k q and shape x 2 {v 2 k according to Theorem 3.1. See Figure 4.1 and [Jeanblanc et al., 2009, p. 146], for more details.

Heavy-traffic time demand analysis

Response times depend on properties of real-time systems such as the scheduling policy, the preemptiveness, etc.. Our motivation is to exploit those properties leading response times to the domain of a certain probability distribution. In this section, the inverse Gaussian distribution is emphasized as the appropriate distribution for an approximation of response times in the context of static-priority scheduling policies, using asymptotic results of queueing theory, c.f., Propositions 4.7. We propose two different approximations, a worst-case approximation before the system is in its steady-state (c.f., Proposition 4.5, see Definition 3.4) and another one when the system is steady, c.f., Propositions 3.3 and 4.6.

Let pΩ, P, Γ, tθ t uq be a stationary real-time system, with Γ ordered by decreasing priority order, i.e., τ i has priority over τ i`1 .

According to Proposition 2.1, the blocking time is such that

B k ptq ď min ˜βk ptq, k ÿ i"1 C i,N i ptq ¸(4.4)
for all t ą 0, which makes our TDA build upper-bounds of response times according to Theorem 2.5. This property is used in Lemma 4.1 to provide a sequence of pessimistic response time analysis. We now look at the limit of those.

Proposition 4.1. For all x ą 0,

P ´Rpnq k,l ą t | β pnq k pA k,l q " x ¯Ñ nÑ8 PpI k pxq ą tq (4.5)
Proof. We have shown in Theorem 3.6 that β pnq converges in distribution to β p8q , thus we conclude that conditionnaly to Wk p0q " x and O k " 0,

R pnq k,1 " inftt ą 0 : β pnq k ptq " 0u
converges in distribution to I k pxq. Then from Eq. (4.8), any job τ k,l has a heavytraffic response time distribution that can be expressed from the response time

R p8q k,1 , P ´Rp8q k,l ą t | β p8q k pA k,l q " x ¯" P x k ´Rp8q k,1 ą t ¯(4.6)
Let us condition this probability for specific values of execution times. As stated in Eq. (4.6), the proper conditioning on backlogs provides the distribution of the response time of τ k,1 . Furthermore, when the backlog β p8q k pA k,l q " x, the response time R p8q k,l is the time it takes for all level k jobs to finish plus the time it takes for level k to stay idle for x instants in the interval rA k,l , A k,l `Rk,l s. It means that we can artificially set the initial demand to x and look at I k pxq, the first idle time of level k, as represented in Figure 4.2. In other words,

P x k ´Rp8q k,1 ą t ¯" P x k ˜sup sPr0,ts s ´W p8q k psq ă 0 ¸" P pI k pxq ą tq (4.7)
which is sufficient to conclude. The heavy-traffic demand

t β 1 ptq x `y A 1,1 A 1,2 C 1,2 A 1,3 R 2,1 " I 1 px `yq
W p8q k is a Brownian motion, hence W p8q k pt `Ak,l q Ẃ p8q k pA k,l q pdq " W p8q k ptq ´W p8q k p0q. Furthermore, W p8q
k is continuous. Thus we define the heavy-traffic response time of a job τ k,l as

R p8q k,l " inf ! t ą 0 : β p8q k pA k,l q `W p8q k ptq ´W p8q k p0q " t ) (4.8)
The Markovian property of Brownian motions allows to approximate the distribution of any response time R k,l in terms of the backlog β p8q k pA k,l q and the first response time R p8q k,1 , thus response times will be conditioned to backlogs and execution times, and represented as idle times following the inverse Gaussian distribution. In a second part, we provide an analytical expression of the heavy-traffic WCRT distribution, and in a third part we do the same for the steady-state heavy-traffic response time distribution. Finally, we explain how to simulate heavy-traffic response times of a task τ k from the distribution functions F k and G k .

Conditioning response times

In this section we use the Markovian property of stationary renewal processes and Brownian motions in order to characterize the distribution of R p8q k,l .

From Eq. (4.8) and Proposition 4.1 we establish a necessary condition of the feasibility of Γ. Proposition 4.2. A non-stable stationary real-time system with implicit deadlines is not feasible under a static-priority scheduling policy.

Proof. Let τ k P Γ be such that ūk ą 1. The Loynes theorem 3.1 states that there is a finite number of idle times of level k, which implies with Eq. (4.8) that heavy-traffic response times get infinite at some point, i.e.,for all t ą 0, P ´Rp8q k,l ą t ¯" 1 for an infinite number of jobs. In other words, there is no permitted failure rate α k P p0, 1q such that τ k is schedulable as defined in Eq. ( 2.21). As we consider a static-priority scheduling policy, then the lowest level backlog is larger than all k-level backlogs β k ptq at any time t ą 0.

Remark.

The probabilistic approach has some subtleties that need to be emphasized. Proposition 4.2 is a strong result. However, one can be tempted to build a counter example showing that with a mean utilization greater than 1, there are actually some jobs that are schedulable. The fact that jobs are discarded when they miss their deadline is confusing for the probabilistic approach, as some could say that if we discard, then we go back to a backlog equal to zero, hence the analysis restarts again just like any other jobs. This is wrong. In order to understand better what we mean here, we should consider the system without job discarding. Then the good translation of Proposition 4. 2

is as follow:

There is a strictly positive probability that only a finite number of jobs satisfy their deadlines if there is no discarding policy. While this probability exists, the system is not feasible. Now if we see schedulability as the measure of how far the discarding system is from the non discarding system as proposed in Section 3.4, we see that the probability Pp βk ď ř k i"1 c max i q is 0 when the mean utilization is greater than 1, because βk " 8 in that case.

In the rest of this thesis, the central quantity is the DMP of a task. We have seen that the backlog process is the main process to look at in our model for an end-to-end analysis. Conditioning response times to their associated backlog is the natural step in our analysis. We define

p k pxq " P x k ´Rp8q k,1 ą D k ¯(4.9)
as the DMP of τ k conditioned to an initial demand x ě 0.

Proposition 4.3. Let ūk ă 1, 0 ă vk ă 8 and γ k " ´v k 1´ū k ¯2. Then

p k pxq " 1 ´exp ˆ´x ? 1 `2λ k γ k ´1 γ k p1 ´ū k q ˙(4.10)
is the DMP of any job of τ k released with an initial demand of level k equal to x.

Proof. We have

p k pxq " P ˜sup tPp0,T k q t ´W p8q k ptq ď x ¸(with (4.7)) " ż PpI k pxq ą tqdG k ptq " ż Ψ k pt, xq λ k e ´λk t dt
Since ūk ă 1 for all x ą 0, we have

lim tÑ8 Ψ k pt, xq " P x k ´Rp8q k,1 " 8 ¯" 0 (4.11)
Furthermore, since 1 ´e´λ k t " 0 when t " 0, we get by integration by parts that we conclude with s " λ k .

ż Ψ k pt,
In Sections 4.1.4 and 4.1.5, we prove that the proper initialization of the system puts the system in two specific cases: the worst-case and the steady-state.

Worst-case response time

Before the system reaches its steady-state, we say it is transient. In that case we cannot provide the exact distribution of the backlog in an analytical formulation.

However, we can bound it by using the worst-case blocking time. We define the WCRT of the task τ i as the heavy-traffic response time R p8q i,1 initialized with the worst-case blocking time.

In the following we approximate the WCRT R max k by the heavy-traffic WCRT

I k ´řk i"1 c max i ¯.
Proposition 4.4. If ūk ă 1, for all l P N we have

inftt ą 0 : B k pA k,l q `W p8q i ptq ´W p8q p0q ď tu ď st I k ˜k ÿ i"1 c max i ¸(4.12)
Proof. First, let us consider ūk ă 1, as stated in Theorem 3.1 the backlog process converges to βk which is finite. Jobs are discarded if they miss their deadlines, and as we consider implicit deadlines, there can be at most one job per task activated simultaneously. Indeed, at any instant and for any task τ k , B k ptq ď

ř k i"1 c max i
. This leads into considering a job τ k,l with blocking time B k pA k,l q " ř k i"1 c max i as the maximum backlog of level k, c.f., Eq. ( 4.4), and use the property stated in Eq. (4.6)

with an initial demand Wk p0q " c max k . According to Theorem 2.6, the solution of inftt ą 0 :

β k pA k,l q `W k ptq ´W k p0q ď tu
is more pessimistic. Hence we set R max k as defined in (4.12) as the WCRT of τ k .

When ūk " 1, idle times of level k may or may not be finite, thus we cannot conclude anything on the distribution of response times, i.e., PpDl : β k pA k,l q " 8q ą 0.

When ūk ą 1, the largest response time does not come from the synchronous activation and is in fact 8. As we have already demonstrated in the proof of Proposition 4.2, response times of the task τ k increase to 8, due to the absence of idle times of level k. Then we conclude that the heavy-traffic WCRT is 8. In this case, a full example is detailed in [START_REF] Chen | Critical instant for probabilistic timing guarantees: Refuted and revisited[END_REF].

We set the heavy-traffic WCRT as the heavy-traffic response time with a backlog equal to

ř k´1 i"1 c max i
. Hence we get the approximation

PpR max k ą tq « H max k ptq
that we develop in the following proposition.

Proposition 4.5. Let τ k P Γ, ūk ă 1 and let Ψ k be as defined in (4.3). The exceedence function of the heavy-traffic WCRT of τ k is

H max k ptq " Ψ k ˜t, k´1 ÿ i"1 c max i ¸(4.13)
Proof. From Proposition 4.4 we know that when ūk ă 1, the heavy-traffic WCRT of

τ k P Γ is R p8q k,1 under P b k´1 k with b k´1 " ř k´1 i"1 c max i . Corollary 4.1. Let τ k P Γ, γ k " ´v k 1´ū k ¯2 and suppose ūk ă 1. The worst-case DMP of τ k is p max k " 1 ´exp ˜´k ÿ i"1 c max i ? 1 `2λ k γ k ´1 γ k p1 ´ū k q ¸(4.14) Proof. Direct consequence of p max k " p k ´řk i"1 c max i ¯and Proposition 4.5.

Steady-state response time

Let us denote the conditional probability that the distribution of the initial demand Wk p0q is the probability dµ and the first job released is τ k,1 ,

P µ k p¨q " Pp¨| Wk p0q " dµ, O k " 0q " ż P x k p¨qdµpxq
The backlog process of level k being stationary and with a stationary distribution π k , in the steady-state Eq. (4.6) becomes

P π k k ´Rp8q k,l ą t ¯" P π k k ´Rp8q k,1 ą t ¯(4.15)
for any l P N. Then if it holds for any l P N, it holds for the all response times after the convergence of the backlog process. This is why in the steadystate, the distribution of heavy-traffic response times is unique.

˙´1

Then with s " ?

1`2λ k γ k ´1 γ k p1´ū k q
and γ k η k p1 ´ū k q " 2v k we get the result.

Simulations

In Proposition 4.1 we prove that response times R k,l can be simulated from a sample of idle times of level k ´1, a sample of execution times and the proper initialization backlog sample, the steady-case or the worst-case.

The procedure is as follows:

• Generate a backlog b equal to

ř k i"1 c max i (resp. with the distribution function π k ),
• Generate the response time R k " I b k .

See

Stability

The first idle time is also a probabilistic variable, but we can build an instant t idle pε, xq such that for any ε ą 0 and all t ą t idle pε, xq, the probability that the first idle time of the lowest priority level is greater than t is less than ε. We call first ε-idle time the instant t idle pε, xq from which we can guarantee the system is steady with probability 1 ´ε and initial backlog x ą 0. We know that β p8q k is a reflected Brownian motion reflected. This means that until it reaches zero, i.e., an idle time, it is a simple Brownian motion. In fact, between two consecutive idle times the backlog process has the same dynamic. Thus, we define the stability of a real-time system according to its response times.

Definition 4.3 (Stability).

A real-time system is said steady when its response times are stationary, i.e., there exists a sequence of exceedence functions H k,l 1 , . . . , H k,l k repeating indefinitely for any task τ k P Γ.

The following proposition bounds with a given probability the first idle time and the instant the system gets stable.

Proposition 4.8. Let n " |Γ|, ε P p0, 1q and x ě 0. If ūn ă 1, the system of initial demand x is stable with probability at least 1 ´ε at the instant

t idle pε, xq " ¨q1´ε `cq 2 1´ε `4 ´1´ūn vn ¯x 2 ´1´ūn vn ¯‹ ‹ ' 2 (4.18)
where q 1´ε " Φ ´1p1 ´εq is the p1 ´εq-quantile of a standard normal distribution.

Proof. First of all, between two idle times of the same level, say I and I 1 , the backlog processes β p8q k , k " 1, . . . , n make excursions between passages to 0, i.e., idle times. As it is a reflected Brownian motion, those excursions between idle times are i.i.d., since the distribution only depends on the intial value, which is 0 at each idle time. Furthermore, there is a finite number of possible jobs realed in the interval rI, I 1 s. Hence, a finite number of reponse time distributions that repeat on every excursion. According to Definition 4.3, this makes the system stable when the backlog of each priority level reaches 0. According to static priority scheduling, I 1 pxq ď ¨¨¨ď I n pxq where I n pxq represents the first idle time of the lowest priority level initialized with a demand W p8q n p0q " x. Hence, after the instant I n pxq, all tasks have response times distributions that repeat according to the excursions of the backlog of their associated priority level. Let us now bound the probability that the idle time I n pxq exceeds a given value t ą 0. Note that see Figure 4.4. This is a second order polynomial equation, which admits no solution when ū ą 1, and, when ū ď 1 and ε P p0, 1q, the smallest solution of Eq. (4.20) is

Eq. (4.18).

Remark. Two important remarks:

(i) When ū ă 1, the excursions of the processes pβ p8q k pt `Ik pxqqq, t ą 0 between two passages at 0 are the longest excursions possible. Indeed, the trajectories of Brownian motions are continuous, which means that, with a intermediate value theorem argument, an excursion between two passages on x is necessarily smaller than the excursion of the same trajectory between passages through 0 .

(ii) To go deeper into the theory of excursions, Îto proves [Itô, 1972] that the sequences of idle times also forms a Poisson point process in certain conditions.

Note that for all x ě 0, lim εÑ0 t idle pε, xq " 8, lim εÑ1 t idle pε, xq " 0, and • ūn ă 1 ùñ t idle pε, xq ă 8,

• ūn " 1 ùñ t idle pε, xq " 8,

• ūn ą 1 ùñ t idle pε, xq is not defined.

Remark. We provide the analysis for the lowest priority level, but in fact each

priority level has its own first ε-idle time.

Finally we consider the maximum first ε-idle time t max idle pεq by considering a synchronous activation, i.e., Wn p0q "

ř τ i PΓ c max i
. See Proposition 4.4 for a more detailed explanation. The maximum first ε-idle time is then

t max idle pεq " t idle ˜ε, ÿ τ i PΓ c max i ¸(4.21)
We can now say that, with a level of confidence ε, that the system is steady at time t max idle pεq in the worst-case.

Experimental results

The purpose of this section is to illustrate that the response times generated from Proposition 4.7 provide a good approximation, by comparing distribution functions of simulations and its associated EVT estimation, and generated heavy-traffic response times distributions. Closer are the curves, better is the estimation. Those results are not exhaustive and are an illustration, we do not cover in this work the sensitivity of the model for different values of ū. We use the data generated by SimSo to apply EVT on response times (using the Scipy framework1 on Python). Finally we compare our results with SimSo simulations and EVT estimations. Without loss of generality the periods are deterministic in these simulations.

In order to illustrate the stability described in this thesis, we use the task set Γ provided in Table 3.1. The level 2 maximum utilization is smaller than 1, hence backlogs of level 2 converge quickly to 0, see Figure 3.3a. The level 3 maximum utilization is greater than 1 and the level 3 mean utilization is smaller than 1.

Thus, τ 3 is the task of interest, see In Figure 3.2 we observe that the demand W ptq follows the line ūt `x (its mean).

In Figure 3.2 and 3.3 we see what happens when the system mean utilization is smaller, close and greater than 1 : for smaller values of ū the system stays with zero backlog at some point, see Figure 3.2b, but for values greater than 1 the system explodes, see Figure 3.2d and 3.3d. In Figure 3.2c and 3.3c we see that even for ū close to 1, the system always admits finite idle times. Most importantly, we see in Figure 3.2b and 3.3b that when ū ă 1 and ūmax ą 1, the analysis holds and provides quantifiable response times.

In Figure 4.4, we see to what corresponds idle times and ε-idle times graphically.

In Figure 4.1 the average idle time corresponds to the point where the line t and ūt `x meet, and the distribution of the idle times correspond to the frequency the demand process meets the line t for each instant t ą 0.

Finally, in Figure 4.3a, we can see the simulations presented in Section 4.2 and a comparison with response times simulated via SimSo [START_REF] Chéramy | Simso: A simulation tool to evaluate real-time multiprocessor scheduling algorithms[END_REF]. The two ground truth samples are the two subsets SimSo-transient and SimSo-steady, which are composed respectively of simulated response time released before and after the maximum ε-idle time t max idle pεq " 154 where ε " 10 ´6. The maximum idle time t max idle pεq is computed via Monte-Carlo approximations with the representation in Eq. (4.21).

The EVT estimation (green curve) from these SimSo simulations and the steadystate and WCRTs suggested in this thesis are compared via their distribution functions in Figure 4.3b. In this case, where ū is not too close to 1 and ūmax greater than 1, we can see that the Worst-case response times, the EVT estimation and the steady-state response times are greater (in the stochastic sense [START_REF] Díaz | Pessimism in the stochastic analysis of real-time systems: Concept and applications[END_REF]) than the true response times simulated with SimSo. The heavytraffic Worst-case response time seems to be an upper-bound in practice, and the Steady-state response time is quite accurate.

Closer is the Steady-state to the SimSo-steady curve, more accurate the approximation is. We can see a big difference between the Worst-case curve and the Steady-state curve. However the proposed analysis does not permit to quantify analytically this difference.

Conclusion

We have seen that real-time systems can reach steadiness over a finite and quantifiable amount of time, and that a necessary condition to assure this stability is that the mean utilization is lower than 1. In practice, systems with a mean utilization ū ą 0.9 have many deadline misses, which requires from system designers to quantify deadline miss probabilities carefully by using the distributions of response times provided in this chapter.

No schedulability tests considering the steadiness of response times exist. This is a natural step in our opinion for the use of the analysis provided in this work.

For example, the approach we have presented in this chapter is well suited for an application of a Monte-Carlo response time analysis [START_REF] Bozhko | Monte carlo response-time analysis[END_REF] which has recently been proven efficient.

We have expressed the probability function of response times in a specific family of distributions and provided a method to generate them. However, the distribution functions of execution time are usually unknown. The methods built in this chapter could be used in empirical and measurement-based methods, for example using clustering methods [START_REF] Friebe | Identification and validation of markov models with continuous emission distributions for execution times[END_REF], Zagalo et al., 2020].

Yet these deadline miss probabilities depend on the Brownian approximation which converges slowly. A next step in this analysis would be to check the sensibility to the size of the task set. Concentration inequalities have been widely studied these last years to bound DMP [START_REF] Von Der Brüggen | Efficiently approximating the worst-case deadline failure probability under edf[END_REF],Palopoli et al., 2012,Chen et al., 2018]. Currently, the most efficient bound is the Hoeffding DMP [START_REF] Von Der Brüggen | Efficiently Approximating the Probability of Deadline Misses in Real-Time Systems[END_REF]. These bounds compute DMP only from the parameters of the studied task set. The method built in this chapter uses knowledge on the task set and infers response time data to compute the Maximum Likelihood Estimate (MLE).

t ū t ū t + q 1 -ε v √ t + vx
We justify in Chapter 4 that response times are first-passage times of Brownian motion, and hence the inverse Gaussian family is proposed as the appropriate family for response time approximations. Thus, the inverse Gaussian family is a natural choice for a statistical modelling of positive and right-skewed distributions, see [START_REF] Folks | [END_REF]Chhikara, 1978, Tweedie, 1957]. It is used in many research fields, such as industrial degradation modelling [START_REF] Ye | The inverse gaussian process as a degradation model[END_REF], psychology [Schwarz, 2001, Palmer et al., 2011], and many others like hydrology, market research, biology, ecology, and so on c.f., [Seshadri, 2012].

In this chapter, we propose a suited parameterization of the inverse Gaussian distribution in Section 5.1, using an adapted Expectation-Maximization (EM) algorithm, we estimate the parameters of a mixture of inverse Gaussian distributions.

This allows to estimate response times and allows parametric inference. Finally in Section 5.2.1 we illustrate the convergence of the EM algorithm and compare it to the Hoeffding DMP (see Lemma 3.5) with simulations, compare it to the classic EM algorithm in terms of computation time.

As we proved in the previous chapter, response times can be approximated with inverse Gaussian distributions as long as inter-arrival times are exponential.

In this chapter we test the assumption that bounds on response times may be approximated by inverse Gaussian distributions for periodic inter-arrival times.

Thus, we test this assumption in this chapter. Let pΩ, P, Γ, tθ t u t q be a stationary real-time system following a

ř i D i { ř i G i {1{SP queueing model.

Inverse Gaussian mixture model for response times

Let R i be the response time of ūi . Its distribution function is the mixture of the distribution functions of the response times R i,j . The distribution of R i is composed of k i components. Formally, this means that we approximate the probability density function of the response time R i with a variable R i of probability density function

h i px; π i , θ i q " k i ÿ k"1 π i,k ψ i px; θ i,k q (5.1)
where ψ i px, θq is the inverse Gaussian probability function of mean θ{p1 ´ū i q and shape θ 2 {v 2 i .

In real-time systems, the interest of the analytical approach is to measure the DMP p i with a closed expression. For example, a task τ i should not miss its deadline with a permitted failure rate α i , and the inequality in Eq. ( 2.21) is approximated with the mixture Eq. (5.1).

Re-parameterized inverse Gaussian distribution for response times

The purpose of this section is to provide the efficient distribution family for an approximation of response times and an adapted EM algorithm to estimate the parameters of this approximation. This adapted re-parameterization of the inverse Gaussian distribution reduces the number of parameters of the model. Furthermore, as underlined in [Punzo, 2019], the log-likelihood of the inverse Gaussian distribution has flat regions, thus the EM algorithm has tiny variations. Reducing the number of parameters addresses a part of this problem. A second reduction of this problem is the use of the Aitken acceleration procedure [Aitken, 1926].

In [Punzo, 2019], the author introduces a modified version of the inverse Gaussian distribution of parameters pξ, δq, using its mode

µ " ˆξ2 `9ξ 4 4δ 2 ˙1{2 ´3ξ 2 2δ
and its variability coefficient

γ " ξ 2 δ
instead of the mean and shape. This re-parameterized inverse Gaussian distribution of parameters pµ, γq is defined by the probability density function ψpx; µ, γq "

d µp3γ `µq 2πγx 3 exp # ´`x ´aµp3γ `µq ˘2 2γx + (5.2)
With the re-parameterized inverse Gaussian distribution applied to the form that takes the parameters of the distributions of response times, one can see that only the mode is sensitive to the mixture provided in Eq. (5.1). The variability coefficient of an inverse Gaussian distribution of mean θ{p1 ´ū i q and shape pθ{v i q 2 is γ i " v2 i p1 ´ū i q 2

(5.3) and its mode is

µ i pθq " d ˆθ 1 ´ū i ˙2 `9γ 2 i 4 ´3γ i 2 (5.4)
such that ψ i px; θq is the probability density function of a re-parameterized inverse Gaussian distribution of mode µ i pθq and variability γ i .

Maximum likelihood estimation of response time distributions

In this section we present an adaptation of the MLE proposed by [Punzo, 2019] for real-time systems. We have implemented both methods in the Python language in the library rInverseGaussian [START_REF] Zagalo | rinversegaussian[END_REF].

When k i " 1, we have the follwing proposition.

Proposition 5.1. Let pR i,j q j"1,...,N be a N -sample of response times of the task

τ γ P Γ. When k i " 1, π i,1 " 1 and we have the MLE θi " 1 ´ū i N N ÿ j"1 R i,j
(5.5)

Proof. See [START_REF] Folks | The inverse gaussian distribution and its statistical application-a review[END_REF] for the classical MLE of IG distributions. We know from [Folks and Chhikara, 1978, Eq. (10)] that the mean of an IG distribution is the empirical mean 1 N ř N j"1 R γ,j . Furthermore, we are looking for estimating the mean θ 1´uγ . Since we already know u γ , we get the result by estimating θ 1´uγ with

1 N ř N j"1 R γ,j .
The complete-likelihood of mixture models [START_REF] Mclachlan | Finite mixture models[END_REF], Bouveyron et al., 2019] can be written as

L c pZ i , π i , θ i q " n ź j"1 k i ź k"1 rπ i,k ψ i pr j ; θ i,k qs Z i,j,k (5.6) and the complete log-likelihood ℓ c " log L c is ℓ c pZ i , π i , θ i q " ℓ c 1 pZ i , π i q `ℓc 2 pZ i , θ i q (5.7)
where

ℓ c 1 pZ i , π i q " n ÿ j"1 k i ÿ k"1 Z i,j,k log π i,k (5.8) and ℓ c 2 pZ i , θ i q " n ÿ j"1 k i ÿ k"1
Z i,j,k log ψ i pr j ; θ i,k q (5.9) which leads to the following EM algorithm: E-step For the ps `1qth step of the EM algorithm,

z psq i the conditional expectation of Z i given pπ i , θ i q " ´πpsq i , θ psq i ¯is given by z psq i,j,k " π psq i,k ψ i ´rj ; θ psq i,k hi ´rj ; π psq i , θ psq i ¯(5.10)
M-step For the ps `1qth step of the EM algorithm, ℓ c 1 pz psq i , ¨q is maximized by

π ps`1q i,k " 1 n n ÿ j"1 z psq i,j,k , k " 1, . . . , k i (5.11)
and maximizing ℓ c 2 with respect to θ is maximizing each of the k i expressions n ÿ j"1 z psq i,j,k log ψ i pr j ; θ i,k q, k " 1, . . . , k i (5.12)

using Newton-like algorithms to solve ∇ℓ c " 0 (5.13) Then with B log ψ i Bθ px; θq " Bµ i Bθ pθq B log ψ Bµ px; µ i pθq, γ i q and the derivatives

B log ψ Bµ px; µ, γq " ´3 2x ´µ xγ `1 3γ`µ `3γ 2µp3γ`µq `?µ 2γ ? 3γ`µ `?3γ`µ 2γ ? µ Bµ i Bθ pθq " θ p1´ū i q 2 ˆ´θ 1´ū i ¯2 `9γ 2 i 4 ˙´1 {2 (5.14)
Eq. (5.13) is equivalently solved by Eq. ( 5.11) and the solutions of

n ÿ j"1 z psq i,j,k B log ψ i Bθ pr j ; θ k q " 0, @k " 1, . . . , k i (5.15)
In order to stop the algorithm, the author in [Punzo, 2019] proposes the Aitken acceleration. The Aitken acceleration at iteration s `1 is given by a ps`1q " ℓ ps`2q ´ℓps`1q ℓ ps`1q ´ℓpsq (5.16) where ℓ psq is the observed-data log-likelihood from iteration s. The limit ℓ 8 of the sequence of values of the log-likelihood is ℓ ps`2q 8 " ℓ ps`1q `ℓps`2q ´ℓps`1q 1 ´aps`1q

(5.17)

The EM algorithm is considered to have converged if

|ℓ ps`2q 8 ´ℓps`1q 8 | ă ε (5.18)
with a tolerance ε ą 0. Finally, we initialize the algorithm with a k-means clustering for θ p0q and π p0q " 1{n.

Bayesian information criteria

The Bayesian information criteria (BIC, [Schwarz, 1978]) is used to chose the number of components of the mixture, which has been proven consistent for mixture models [Raftery, 1995, Fraley and Raftery, 2002, Dasgupta and Raftery, 1998]. The number of parameters of a mixture of k components being 2k ´1, the number of components chosen is equal to

k i " argmax k 2ℓ n pπ i , θ i q ´p2k ´1q log n (5.19)
where ℓ n is the observed-data log-likelihood. The number of parameters being reduced from 3k i ´1 to 2k i ´1, the computation time of this EM algorithm is also reduced (see Figure 5.1).

Model validation

We use the relation of inverse Gaussian distributions with the χ 2 1 distribution to check the quality of the MLE. Indeed, if X is an inverse Gaussian variable of mean ξ and shape δ, then

δpX ´ξq 2 ξ 2 X
is distributed as a Chi-squared distribution of one degree of freedom [Tweedie, 1957].

Let P IG k be the probability conditionally that the response time R i is in the k-th component in the inverse Gaussian estimation, and

g i px; θq " ´x ´θ 1´ū i ¯2 γ i x , x ą 0 (5.20)
In our case, for each component k " 1, . . . , k i of the mixture Eq. (5.1), after classification we should have that

g i ´Ri ; θi,k ¯" χ 2 1
(5.21) under the probability P IG k . Therefore, we use Eq. (5.21) to validate the MLE, and provide the DMP we are looking for. The larger quantiles values are the ones that real-time designers are interested in to determine whether a task is schedulable or not, see Eq. (2.21). We use Eq. (5.21) to determine whether a task is schedulable in its transient state or not.

Deadline miss probability

Proposition 5.2. The deadline miss probability of the inverse Gaussian estimation is

p IG i " k i ÿ k"1 π i,k Ψp1{λ i , θ i,k ; ūi , vi q (5.22)
20% 30% 40% 50% 60% 70% 80% 90% Mean utilization Deadline miss probability

u max > 1 u max > log(2) (n) IG H Figure 5.2:
Utilizations ūi against the deadline miss probabilities of the inverse Gaussian estimation p IG i " ∆ IG pū i q, the Hoeffding DMP p H i " ∆ H pū i q and the empirical deadline miss probability p pnq i " ∆ pnq pū i q over a sample of n " 100 000 response times per task simulated on SimSo. In solid line the average value, and the colored area represents the values between the 25%-percentile and the 75%-percentile.

where

Ψpt, b; u, vq " Φ ˆ´p1 ´uqt ´b v ? t ˙´e ´2b 1´u v 2 Φ ˆ´p1 ´uqt `b v ? t ˙(5.23)
and Φ is the standard normal distribution function.

Proof. We have

p IG i " ř k i k"1 π i,k P IG k pR i ą D i
q and since g i p¨; θq is positive and, decreasing for x ď θ 1´ū i and increasing for x ą θ 1´ū i , we obtain the result.

One may see in Figure 5.2 a comparison between the empirical DMP, the inverse Gaussian method in Eq. (5.22) and the Hoeffding DMP.

In the following, we test by simulation if p IG i is a good estimation of p i and if the Hoeffding DMP is a safe bound of the inverse Gaussian estimation, i.e., p IG i ď p H i .

Experimental results

The seminal work of [START_REF] Liu | Scheduling algorithms for multiprogramming in a hard-real-time environment[END_REF] provides a sufficient condition for the schedulability of any system with finite supports of execution times using the maximal utilization ūmax

i , i ě 1. Whenever ūmax n ă np2 1{n ´1q (5.24)
the task set Γ is proven schedulable for α 1 " ¨¨¨" α n " 0 [Liu and Layland, 1973, Theorem 5]. Moreover, while ūmax n ă 1 there exists a dynamic-priority scheduling policy that can satisfy the schedulability of the system [START_REF] Liu | Scheduling algorithms for multiprogramming in a hard-real-time environment[END_REF].

Hence there are two phase transitions, one at ūmax n ą logp2q " lim n np2 1{n ´1q where deadline misses can happen, and one at ūmax n ą 1 where deadline misses must happen.

As proven in [Zagalo et al., 2022a], the necessary condition for the schedulability of a task ūi Eq. ( 2.21) is that ūi ă 1. Hence, there is a gap to fill in the theory between the necessary condition ūi ă 1 and the sufficient condition ūmax i ă logp2q.

In particular in the case where ūi ă 1 and ūmax i ą 1 as we see in Figure 5.2.

Simulations

In this section, we verify our method with simulated data. The simulated data are generated using SimSo [START_REF] Chéramy | Simso: A simulation tool to evaluate real-time multiprocessor scheduling algorithms[END_REF], a Python framework used to generate arrival times of jobs and scheduling policies. A modified version of SimSo [Cheramy, 2014] generates random inter-arrival times and random execution times [START_REF] Zagalo | Simso with probabilistic execution times[END_REF] 1 . We study the quality of the estimation as a function of utilization level. We show that the larger the utilization, the better the estimation. We also measure by how much the inverse Gaussian bound is larger than the empirical DMP,

p pnq i " 1 n n ÿ j"1 1 R i,j ąT i,j`1 (5.25) 20% 30% 40% 50% 60% 70% 80% 90% Mean utilization 0.0 0.2 0.4 0.6 0.8 1.0 L2 distance u max > 1 D/M/1 D/G/1 Figure 5.3: L2 distance
between the empirical distribution of the simulations and the MLE distribution, of 1000 instances of the schedule, for the task set shown in Table 5.1. In solid line the average value, and the colored area represents the values between the 25%-percentile and the 75%-percentile.

We consider a task set where the probability density functions pf i q i of the execution times pC i q i are known, see Figure 5.4. From SimSo we generate the response times of tasks with the RM scheduling policy from the probability functions pf i , i " 1, . . . , 28q. Their parameters are given in Table 5.1. The distributions of execution times used in the simulations are generated with UUnifast [START_REF] Bini | Measuring the performance of schedulability tests[END_REF], to emphasize the fact that f i can be any distribution (D{G{1 queue).

Two methods are used: one with a finite support where the maximal utilization ūmax i is finite, and another one with an infinite support with exponential distributions where the maximal utilization is not defined. This schedule is instantiated 100 times, thus in Figure 5.3(a), the box-plots of each task are based on 100 estimators. Also note in Figure 5.3 that the variability of the estimates decreases with the priority level. Because of the static-priority structure of RM, we can see in Figure 5.3 that the error of the estimation decreases with the priority level. The first task is never preempted, so its response time is always equal to its execution time. Therefore the estimation of its response time cannot be accurate in general.

In a second step, a task set with exponentially distributed execution times is simulated for comparison (D{M {1 queue), as it is a special case widely studied in queueing theory [Pack, 1977]. This is a baseline for determining the rate of convergence of the response times estimation as a function of priority levels. This baseline confirms that the rate of convergence depends on the type of distributions used for execution times, but that there is a phase transition at ūmax i ą 1, independent from the type of distribution used for execution times. The parameters of the task set are given in Table 5.1.

In Figure 5.2, we have the mean utilization pū i q i on the x-axis and pp pnq i , p H i , p IG i q i on the y-axis. We can see that when ūmax i ă logp2q, it is useless to compare the methods because they have already been proved schedulable in Eq. (5.24).

Moreover, all DMP increase when ūmax i ą 1. These programs generate response times shown in Figure 5.6, on which we use the mixture model proposed in Eq. (5.1) with the EM algorithm provided in Section 5.1.2, see [START_REF] Khazen | Work in progress: Kdbench -towards open source benchmarks for measurement-based multicore WCET estimators[END_REF] for a full description of the data. The QQplots in Figure 5.6 show that the estimation is good for the large quantiles, which is what is important to determine the schedulability of a system, c.f., Eq. ( 2.21).

We can identify in Figure 5.6 that for the cmdr and fmgr tasks the estimation is not good, which means that we do not have sufficient information about the programs interfere with them (operating system etc.), and that a schedulability test on this task would not be suitable with the method built in this chapter.

Nevertheless, for the other tasks the approximation is appropriate and can therefore be used for a schedulability analysis.

" m 2 3m´1 , m`1 2 ı ms ´pm ´1q max τ i PΓ λ i c max i " mp2 1 {m ´1q, m`1 1`2 1 m`1 ȷ uniform processors
Eq. ( 6.3) -ř m j"1 spκ j qn j p2 1 {nj ´1q sequencing problem. In this chapter, RM is applied.

The offline and online allocation differ in their complexity. Furthermore, in the case of a stationary system, offline and online allocation become significantly different. Offline allocation involves estimating or averaging arrival times, while online allocation uses the exact arrival time for each job.

Introduction

The RM scheduling policy is a static-priority scheduling algorithm which assigns each task a priority relatively to its periods -the smaller the period, the higher the priority. Let u max i " λ i c max i be the maximum utilization of the task τ i P Γ.

In the case of multiprocessor scheduling, i.e., m ě 2, the RM policy is extended in [START_REF] Andersson | Staticpriority scheduling on multiprocessors[END_REF] to identical multiprocessor systems global scheduling when

ūmax n ď m 2 3m ´1; @τ i P Γ, u max i ď m 3m ´2 (6.1)
and by allocating jobs to any available processor, all tasks are schedulable with a permitted failure rate equal to zero. In the case of restricted scheduling on identical processors of speed s, authors in [START_REF] Goossens | Job partitioning strategies for multiprocessor scheduling of real-time periodic tasks with restricted migrations[END_REF] prove that if ūmax n ď ms ´pm ´1q max

τ i PΓ u max i (6.2)
the system is schedulable with permitted failure rates equal to zero.

In [START_REF] Baruah | Ratemonotonic scheduling on uniform multiprocessors[END_REF] authors extend this result to uniform multiprocessor systems with global scheduling static-priority policies. The system is schedulable with permitted failure rates equal to zero when ūmax n ď 1 2 ˜ÿ κPΠ spκq ´p1 `Λq max

τ i PΓ u max i ¸(6.3)
where Λ " max κ j PΠ 1 spκ j q ř m i"j`1 spκ i q measures the degree by which Π differs from an identical multiprocessor systems. However, this bound Eq. ( 6.3) is not proven sustainable according execution times and inter-arrival times as discussed in this same paper.

Finally, for partitioned scheduling algorithms, the task set Γ should be partitioned into m tasks subsets of respectively n 1 , . . . , n m tasks such that for any κ j P Π, ūmax n pκ j q ď n j p2

1 {nj ´1q (6.4) However anomalies can be found in such partitioning, which can be corrected by giving priorities according to decreasing utilizations [START_REF] Andersson | Preemptive multiprocessor scheduling anomalies[END_REF],

i.e., τ i has priority over τ j on κ if u max i ą u max j . This priority assignment is not only the appropriate way to partition a static-priority task set, but it is also sustainable if execution times are decreased and inter-arrival times are increased, which is suited for stationary real-time system. For the sake of simplicity, we keep referring to it by RM.

No bound still exists for the uniform restricted case. However, we use the global uniform bound as a baseline, knowing that there exists deadlines misses, while the system is feasible. Quantifying the deadline misses probabilities is the purpose of the first section of this chapter.

Let pΩ, P, Γ, Π, tθ t uq be a stationary real-time system, with the uniform multiprocessor Π " tκ 1 , . . . , κ m u composed of the processors κ P Π of speed spκq P r1, s max s, i.e., κ can process spκq workload units in one unit of time. We consider Π ordered by decreasing speeds, i.e., spκ i q ą spκ j q if i ă j. We consider also the task set Γ " tτ 1 , . . . , τ n u with stationary inter-arrival times and implicit deadlines, ordered by decreasing utilization, i.e., τ i has priority over τ j if u max i ą u max j . We suppose for all 1 ď i ď n and 1 ď k ď m that λ i ErC i s ă spκ k q. We define Γ ì pκq (resp.

Γ í pκq) to be the set of tasks of priority higher (resp. lower) or equal to the priority of τ i active on the processor κ at a given time, and let ūi pκq " 1 spκq ÿ τ j PΓ ì pκq λ j ErC j s (6.5) be the local mean utilization of level i in the processor κ and, respectively, let vi pκq "

1 spκq ¨ÿ τ j PΓ ì pκq λ j ErC 2 j s '1 {2
be the local deviation of level i on the processor κ, that is the sum of the utilization the local maximum deviation of level i in κ. Finally, we suppose that ū ă ř m j"1 spκ j q and u i pκ j q ă 1 for all i " 1, . . . , n, j " 1, . . . , m. We remind that we say that a task τ i is schedulable if its DMP is lower than its permitted failure rate α i . We suppose the task set Γ " tτ 1 , . . . , τ n u is ordered such that u max 1 ą ¨¨¨ą u max n .

Bin-packing

The goal of bin-packing in multiprocessor scheduling is to assign a set of tasks to a set of processors online. It is used to solve one of the two sub-problems of multiprocessor scheduling listed above. The goal is to assign the tasks to the processors in a way that the utilization is either increased or decreased. In binpacking, each processor is viewed as a "bin" and the tasks are viewed as items that need to be placed into the bins. The problem is to find the optimal assignment of tasks to bins such that the total execution time is minimized. The choice of algorithm depends on the specific characteristics of the problem, such as the size of the task set and the number of processors available. In real-time systems, the three most used heuristic approaches are Reasonable Best-Fit (Algorithm 1), Reasonable Worst-Fit (Algorithm 2) and Reasonable First-Fit (Algorithm 3). In the Best-Fit algorithm, the tasks are iterated through and each task is assigned to the processor with the smallest amount of remaining capacity. In the Worst-Fit algorithm, the tasks are iterated through and each task is assigned to the processor with the most remaining capacity. In the Next-Fit algorithm, the tasks are iterated through and each task is assigned to the next available processor. The First-Fit algorithm differs from the Best-Fit and the Worst-Fit algorithms, in that it does not consider an optimization problem when making assignment decisions. The specific algorithm used to solve the bin-packing problem depends on the characteristics of the problem, such as the size of the task set and the number of processors available. A full review on utilization bounds RM and EDF combined with different bin-packing algorithms can be found in [START_REF] Davis | A survey of hard realtime scheduling for multiprocessor systems[END_REF].

Anomalies in multiprocessor scheduling and sustainability

In order to generalize results of the deterministic analysis of periodic real-time systems to a probabilistic approach, we assert that a variation on the execution times of jobs and their inter-arrival times does not affect the scheduling process. A scheduling algorithm not sustainable has scheduling anomalies [START_REF] Andersson | Preemptive multiprocessor scheduling anomalies[END_REF], e.g., Figure 6.1, i.e., scenarios where the optimality of the single processor algorithms does not hold in the multiprocessor scheduling. This phenomenon has to be taken into account in order to use a stochastic analysis and in general to propose a multiprocessor scheduling policy. Unfortunately, online restricted scheduling algorithms are not sustainable with respect to the execution times [Ha and Liu, 1994]. Hence our goal is to decrease as much as possible the number of anomalies leading to deadline misses. In order to use results on deterministic anomaly-free bin-packing algorithms, we provide a heuristic of a reasonable allocation algorithm. Definition 6.1 (From [START_REF] Lopez | Minimum and maximum utilization bounds for multiprocessor rate monotonic scheduling[END_REF]). A Reasonable Allocation Algorithm (RAA) is one which fails to allocate a task only when there is no processor in the system which can hold the task.

Since the restricted strategy proposed in this chapter is an online partitioning of the system, we can say that that a bin-packing strategy combined with the utilization-bound in Eq. ( 6.4) provides a restricted scheduling algorithm. There are bin-packing analyses providing solutions to the anomalies they can contain e.g., [Murgolo, 1988]. The specific case of the RM policy with First-Fit is studied in [START_REF] Andersson | Preemptive multiprocessor scheduling anomalies[END_REF]. The purpose of this chapter is to build such bin-packing algorithm based on DMP that is reasonable.

Problem statement

We suppose a task τ i is activated. When it is activated, it is potentially delayed by a backlog of distribution µ ij in each processor κ j , that is the workload of the Algorithm 1 Reasonable Best-Fit when the task τ i is activated q " 1 for κ P Π do n κ " |Γ ǹ pκq| Ź The current number of tasks activated on κ u

κ " ūmax n pκq `umax i {spκq if u κ ă pn κ `1qp2 1 nκ`1 ´1q and q ą 1 ´uκ then q Ð 1 ´uκ a Ð pτ i , κq if q " 1 then return H Ź Discard τ i else return a
Algorithm 2 Reasonable Worst-Fit when the task τ i is activated q " 0 for κ P Π do n κ " |Γ ǹ pκq| Ź The current number of tasks activated on κ u κ " ūmax n pκq `umax i {spκq if u κ ă pn κ `1qp2 1 nκ`1 ´1q and q ą u κ then q Ð u κ a Ð pτ i , κq if q " 0 then return H Ź Discard τ i else return a Algorithm 3 Reasonable First-Fit when the task τ i is activated

for κ P Π do n κ " |Γ ǹ pκq| Ź The current number of tasks activated on κ u κ " ūmax n pκq `umax i {spκq if u κ ă pn κ `1qp2 1 nκ`1 ´1q then return pτ i , κq return H Ź Discard τ i
unfinished jobs of higher priority tasks activated before τ i . We denote the action of allocation τ i on κ j as the couple a " pτ i , κ j q. For all j " 1, . . . , m, let tµ 1 kj u k be the sequence of backlog distribution of jobs of level k activated on the processor κ j induced by the allocation a. The goal of the allocation is then to focus not only the DMP p i pa, µ ij q of τ i conditionally to the backlog µ ij , but also the DMP tp k pa, µ 1 kj qu kąi of the tasks blocked by τ i induced by the choice of κ j for the task τ i . Thus the allocation problem is to find the processor κ ˚minimizing both the probability p i pa, µ ij q ś kąi p k pa, µ 1 kj q and a quantity q RAA paq of a given RAA that should be maximized, at each activation of the task τ i , i.e., κ ˚" argmax a"pτ i ,κq ´log p i pa, µ ij q ´ÿ kąi log p i pa, µ 1 kj q ´log q RAA paq (6.6) which does not mean that we minimize the DMP of a particular task, but overall the metric is the DMP to decrease the number of deadline misses as much as possible.

DMP-driven decisions are not based in fact on the quality of the estimation of DMP, but more in the order induced by those. As in the priority assignment problem, the allocation problem builds some kind of hierarchy to decide which processor to allocate to which task. This is important to understand, and this is how probabilities can play a central role even in critical applications.

Local TDA

In Chapter 4 we used queueing theory arguments that any set of tasks active on a processor with a local mean utilization greater than 1 is not schedulable with a static-priority scheduling algorithm. Similarly, we use the fact that ūn pκq ă spκq for every processor κ P Π at any time, is a necessary condition for the schedulability of any global static-priority scheduling policy, and develop a allocation policy using forward induction to allocate jobs to processors by minimizing their DMP. The problem is stated as follows: find an optimal allocation policy with RM priorities focused on the DMP in the worst-case scenario.

Let κ be a processor at given instant in time, β i pκq be the local backlog of level i allocated to κ and Ŵi ptq the demand of level i at this same time. Suppose a job τ i,j is allocated to a processor κ. According to Chapter 4, the TDA of this job is Ri,j " inf ! t ą 0 : β i´1 pκq `Ci,j `Ŵ j i´1 ptq ď spκqt

) (6.7)
where the Ŵ j i , j P N are independent copies of Ŵi , itself a Brownian motion of drift ūi and deviation vi , c.f., Chapter 3. This analysis is possible thanks to the following theorem. Theorem 6.1 (Theorem 1 in [START_REF] Andersson | Preemptive multiprocessor scheduling anomalies[END_REF]). The deterministic TDA of RM is sustainable according to execution times and periods if the local priority assignment is such that it orders tasks by decreasing local maximum utilization.

Just like in the single processor case, this last theorem is the reason TDA holds as a probabilistic analysis. Any non-sustainable analysis in the deterministic case cannot be extended to a stochastic version.

Remark. There are two differences with the single processor TDA:

(i) the time budget of the processor κ is t Ñ spκqt rather than t Ñ t, (ii) it is more pessimistic because considering the local demand Ŵi´1 as the interference of tasks of level i is equivalent to assume that all jobs of higher priority tasks are going to be allocated in κ. This is false, but it gives us a safe bound to work with. The online method that we build in the next section is non-clairvoyant, one cannot say when and where future jobs will run, i.e., jobs released after this activation of τ i . Hence, at this stage we cannot do better than over-estimate the local demand.

DMP-RAA bin-packing

The online allocation has the benefit over the offline method to be adaptive. However, as explained in the previous section, online allocation for restricted scheduling policies in not sustainable, in the sense that it generates anomalies with the variation of execution times. The goal of this section in to provide a penalty to a RAA such that not only the bin-packing decision is made according to RAA, but also adapting the decision to the induced DMP. We use this adaptive property to reward the good decisions of the scheduling algorithm with the forward induction method. Forward induction is a method of solving a decision problem by breaking it down into a sequence of decisions and working forward in time. This process begins with the first decision in the sequence and then continues to the next decision, considering the outcomes of the previous decision. The process ends when all decisions in the sequence have been evaluated. In order to do so, we define the good metric and provide a method to compute it. The DMP are our metric, although it does not mean that these decisions are optimal according to DMP. Although, we see that such decisions have the benefit of reducing the number of preemptions.

Forward induction

We suppose that we have a system with states µ " pµ 1 , . . . , µ n q P M, possible actions a P A, an immediate reward rpµ, aq of taking the action a in the state µ with a RAA. The goal of forward induction is to find a policy κ ˚: M Ñ A maximizing

n ÿ i"1 rpµ i , κ ˚pµ i qq (6.8)
where M is the set of possible states, and A the set of actions. This policy can be achieved online by satisfying the Bellman equation [Bellman, 1957]:

c i pµq " max aPA i
rpµ i , aq `ci`1 pg a pµqq (6.9) at each iteration, where A i is the set of available actions; rpµ, aq is the expected immediate reward of the action a taken on state µ, c i`1 pg a pµqq is the cost of getting to the state g a pµq " pµ 1 P 1 a , . . . , µ n P n a q on the next iteration, where µ k P k a is the next backlog distribution of level k if the action a is taken, with µP pxq " ż µpdyqP py, xq and P k a py, xq is the probability to transition from a level k backlog y to x when taking the action a.

The optimal decision κ chooses the action that maximizes both the immediate expected reward and the expected reward further in time, i.e., κ ˚pµq " argmax aPA i pµq rpµ i , aq `ci`1 pg a pµqq (6.10)

From the Bellman equation [Bellman, 1957], we know that satisfying Eq. (6.6) for all tasks minimizes all the DMP. In our case, the reward of a particular action (assigning a task to a specific processor) provides the asset to be optimized (DMP minimized). The allocation is the response to a specific state of backlogs distributed in several processors based on the DMP induced by the previous backlogs. In order to use forward induction, we formalize:

(i) A set of actions, (ii) A set of states, (iii) A reward function to evaluate the taken action at a specific state, (iv) A transition probability for each action.

As only one job per task can be allocated to a processor (because of the discarding policy), we refer only to tasks and not to jobs. The jobs are referred to as activated tasks at a given time on a given processor. Another abuse of notation we use in the following, is that every time we mention a processor κ P Π, we mean a processor at a given time. Since we are only interested in transitions of backlogs at a time t to the backlog induced by an allocation, there is no need to make all variables dependent on t ą 0 for the sake of simplicity, when in the end everything is characterized by transitions. Hence, we choose not to index every variable on time, and warn the reader that everything is presented conditionally to the state of processors at the activation dates of the tasks.

State space

The worst-case reasoning is the paradigm used in real-time systems in order to be safe, i.e., make decisions according the worst-case scenario. We call critical instant of level i the scenario providing the worst-case blocking time of the task τ i , i.e., the largest backlog that can interfere with a job of τ i . The scheduling policy is then adapted for this critical instant. We use in the following the result of the Chapter 4 on the critical instant of stationary real-time systems.

In single processor systems, the critical instant comes in the scenario of a simultaneous activation of all tasks. In multiprocessor systems however, the critical instant of level i is not always the simultaneous activation of all tasks [START_REF] Guan | Fixed-priority multiprocessor scheduling: Critical instant, response time and utilization bound[END_REF], because of the fact that tasks can be activated on different processors. and refer to them in a table online allows to bypass the complexity of this problem for online decisions.

Reward function

In order to build an allocation decision that based on the DMP, we use the representation We adapt this method for each processor by summing only the utilizations of the tasks that are allocated to a processor κ j . This representation permits in a two-step allocation to (i) approximate the local worst-case blocking time of a given processor, (ii) approximate the distribution of the future backlog, (iii) optimize the distribution of the future backlog of higher priority tasks allocated on the same processor by minimizing DMP, (iv) include the minimal DMP in the allocation of a bin-packing algorithm RAA.

As we want a policy minimizing DMP, conditionally to the worst-case blocking times of the system. We set the immediate expected reward function for the allocation a and backlog distribution µ P M as r i pµ i , aq " ´log p i pa, µ i q (6.13) where p i pa, µq is the DMP of τ i induced by the allocation a in the state µ, and q RAA paq P p0, 1s depends on the criteria of the bin-packing RAA to be minimized.

For the action a, the tasks τ k with k ď i are not considered, as they cannot be preempted or interfered by tasks with a lower priority.

Let µ pκq P M be the state of the backlog distributions at a time t ą 0. The immediate expected reward of an allocation a " pτ i , κq is r i pµ i pκq, aq and the cost of the allocation a " pτ i , κq on Γ í pκq is where W κ i´1 is a Brownian motion such that W κ i´1 p0q " 0, of drift ūi´1 pκq and deviation vi´1 pκq. Furthermore, we know from [Jeanblanc et al., 2009, p. 147] that for a given T ą 0, P ˆinf tPr0,T i s W i´1 ptq ´spκqt ą ´x˙" ż p κ i pt, xqdG i ptq (6.16)

c i`1 pg a pµpκqqq " ÿ τ k PΓ í pκq r k `µk pκqP k a ,
for any static-priority preemptive policy and any processor κ P Π.

Finally, the DMP is computed by integrating on x the backlog distribution function µ.

Action space

The global action space is A " Γ ˆΠ, i.e., an action is determined by a task and a processor. However, the system decides which task is allocated. The decision taken by the allocation is then to choose the right processor. As the state space, we reduce the action space by allowing only actions keeping the utilization of processors under one, and the DMP of each active task under its permitted failure rate. Hence, when a task τ i arrives, the set of possible actions is

A i " ␣ κ P Π :a " pτ i , κq P A, u max i spκq ă 1 ´ū max n pκq, @τ k P Γ í pκq, r k pµ k pκqP k a , aq ą ´log α k (
We note that the bound used to define the set of actions is an heuristic that we propose without proof but with extensive numerical evaluations against the stateof-the-art algorithms. The idea behind this bound is that as we ensure that there is no deadline misses with a maximum local utilization of κ lower than

`|Γ ǹ pκq| `1˘ˆ2 1 |Γ ǹ pκq|`1 ´1ȧ
nd that the system is feasible with a maximum local utilization lower than 1, then we quantify the number of deadline misses for an utilization between those two bounds.

Transition matrix

Transitions between states in M are driven by execution times distributions.

Whenever a task is allocated to a processor, regardless of the current backlog of this processor, the DMP induced by the allocation of a task takes its execution time distribution into account by convolving it to the current worst-case blocking time distribution.

Proposition 6.2. Let τ i be a pending task, κ P A i and a " pτ i , κq.

(i) If τ k P Γ ì pκq, the probability of transitioning from a backlog of level k equal to b, to b 1 by taking the action a is P k a pb, b 1 q " δ b pb 1 q (6.17)

P k a pb, b 1 q " f i pspκqpb 1 ´bqq (6.19)
where f i " dF i {dx is the probability function of C i .

Proof. Let τ i be activated on the processor κ.

• First, if τ k P Γ ì pκq, the allocation a " pτ i , κq does not affect the active job of τ k . Hence the backlog of level k denoted b remains the same and the only transition possible is from b to itself.

• Secondly, if τ k P Γ í pκq, the execution time of τ i is added to the backlog of level k on the processor κ. Hence, the transition probability from a backlog of level k denoted b and a backlog b 1 is Ppb 1 " C i {spκq `bq " f i pspκqpb 1 ´bqq.

Using analytical DMP

The DMP-driven algorithms takes any analysis providing a DMP for each tasks, and arranges jobs in a certain order based on the probability of missing a deadline.

This means that, any approximation of deadline miss probability could supposedly work, whatever the quality of the approximation or the the fact that it bounds or not the exact DMP. What is important is the order provided by those DMP. The analytical approximation of the DMP is useful as it is easy and fast to compute, and the error is not, necessarily, a problem. However, the DMP model chosen must have strong mathematical background and be sustainable to small variations in the task set parameters. This is provided by the Hoeffding bound that we use in this section. where v max i " pc max i ´cmin i q 2 {t min i is the maximum deviation of τ i . This is where analytical approximation of DMP shines: their complexity is Op1q, hence the scheduling policy is as simple as it can be. We adapt RM-DMP-RAA with the Hoeffding DMP in Algorithm 6.

In order to make this algorithm reasonable, we add a rule coming from this last theorem: for an allocation a " pτ i , κq, we require that τ i satisfies t should provide its own rules to be reasonable.

Simulations

The RM-DMP-RAA (Algorithm 5) algorithms are compared in the next section to other comparable scheduling policies. The task set used in these simulation is stationary, with parameters shown in Table 6.

DMP

We see in Figure 6.3 that, as the full DMP-First-Fit (q RAA paq " 1) method has a lower deadline miss ratio, at the end both algorithms provide equivalent metric.

This means that the using an approximation of DMP, such as the Hoeffding bound, is a good tradeoff in performance/complexity.

RM-DMP-RAA vs. others

We see in Figure 6.8 and Figure 6.9 that DMP-driven algorithms are not systematically the scheduling algorithms with less deadline misses. Indeed, LLREF [START_REF] Funk | U-llref: An optimal scheduling algorithm for uniform multiprocessors[END_REF], DP-WRAP [Baruah andCarpenter, 2005, Levin et al., 2010], U-EDF [START_REF] Baruah | The edf scheduling of sporadic task systems on uniform multiprocessors[END_REF] are proven optimal in some cases. For comparison we add global EDF and global RM. Those are global scheduling algorithms, hence the preemption and migration metric are not relevant for a comparison to a restricted migration scheduling. However, we see that RM-DMP has a good performance compared to global scheduling policies. Moreover, DP-WRAP (which is a Pfair-based algorithm) is optimal in the periodic case, see Figure 6.8. DP-WRAP is presented as a baseline.

The performances of DMP-driven bin-packing is quite limited. However, we provide it as a simple method to implement with not much overhead than a classical bin-packing algorithm, that slightly improves the metrics used in this thesis.

Potential extension to unrelated heterogeneous multiprocessor systems

Time demand analysis in the form presented in Eq. (4.8) is flexible and can easily adapt to speeds changing over time. Indeed, with the more general relation Ri,j " inf ! t ą 0 : βi´1 pA i,j q `Ci,j `W κ i´1 pt `Ai,j q ´W κ i´1 ptq ď s κ ptq

) (6.22)
where s κ is a non-linear function providing the speed of a processor κ P Π over time.

In that case, Brownian motion have many properties of reaching times that can be used to quantify such response time. It could also be modeled with Brownian motion evolving in random environments [START_REF] Karandikar | Second-order fluid flow models: reflected brownian motion in a random environment[END_REF]. One can also use s κ as a stochastic process, and Branching Brownian motions seem to be the appropriate object to use in that case.

Short-term

of finished jobs. In this section we use the parametric estimation of backlogs proposed in Chapter 5 to improve the scheduling decisions, see [START_REF] Aytug | A review of machine learning in scheduling[END_REF] for a review in this field.

An a priori distribution is the distribution of the parameters of a given variable.

For the response time R i of the task τ i running on a processor κ, i.e.,considering the allocation a " pτ i , κq we see in Chapter 5 that a suited approximation of the distribution of response time takes the form

h i prq " ż ψ ˆr; θ 1 ´ū i pκq , θ 2 v2
i pκq ˙pµ i´1 pκqP a qpθqdθ (7.1)

where we recognize the parameter θ to be the backlog referred to in Section 3.2, and ψpr; θ 1´u , θ 2 v 2 q " d dt Ψpθ, u, v, tq is the inverse Gaussian probability function of mean θ 1´u and shape θ 2 v 2 . The distribution µ i´1 pκq ˚Fi p¨ˆspκqq is the a priori distribution of the response times of τ i . An estimation of this distribution proposed in Chapter 5 ĥi pr; π i , θ i q " The shrink operator, used in several studies [START_REF] Díaz | Stochastic analysis of periodic real-time systems[END_REF]Shin, 1996], is used to describe the transition of the backlog distribution after an interval of time ∆. For example for a variable X of distribution µ and scalar ∆ ě 0, pµ ˚δ´∆ q `is the distribution of pX ´∆q `" maxp0, X ´∆q.

Lemma 7.1. After an interval of time ∆ with no allocation of level k or higher, the backlog distribution µ of level k is pµ ˚δ´∆ q

Proof. This is a consequence of the work-conserving property of processors. If no higher priority jobs arrives, then it must have executed some work of level k during the interval ∆. If the workload is less than ∆, then it is at zero. Proof. With Lemma 7.1, we should conclude by induction that the current backlog of level k is p. . . ppµ k pκq ˚δ´spκqw i 1 q `˚δ ´spκqw i 2 q `¨¨¨˚δ ´spκqw ip q However we know that spκq ř p k"1 w i k is necessarily lower than the workload of their associated jobs, otherwise it would not belong to Γ ì pκq. Now let us suppose we measure a response time R i of the lastly executed task τ i on κ and suppose the last taken action is a. Estimating its a priori parameter θ " argmax θ,πPtθ i,j ,π i,j u j ψ ˆRi ; θ 1 ´ū i´1 pκq , θ 2 v2 i´1 pκq ˙π (7.5)

provides the previous backlog of τ i . Hence, having the estimator θ provides an estimator of the current distribution of the backlog of level i ˆδθ P a ˚δ´ř τ k PΓ ì pκq spκqw k pκq ˙Ìn [Plassart, 2020, Gaujal et al., 2020a], the authors use statistical learning methods in order to find optimal speeds for a low-energy-oriented scheduling for Dynamic Voltage and Frequency Scaling (DVFS). A Markov Decision Process is built in order to adapt the processor speed (which is the action of the process) between

Mid-term

lists of potential instances of programs to run, in which the most energy efficient are chosen by the scheduler. The proposed method is similar to that approach.

Mid-term

Exploiting the data flow between sensors and tasks to make better predictions is not new [START_REF] Melani | Learning from probabilities: Dependences within real-time systems[END_REF]. However, it can be combined with the potential extension explained in Section 7.1. We discuss here without providing proofs how this information can be inferred into the estimation of execution times distributions.

We also introduce the formalization making this estimation well defined in the context of stationary real-time systems.

Let τ k P Γ. We look at variables C k p¨, iq, i P I. Let the projection operator ρ Q be the projection of Ω 0 to Q, such that for ω 0 " pq 0 , i 0 q P Ω 0 , we have ρ Q pω 0 q " q 0 . We can write C k pω 0 q " pC k p¨, i 0 q ˝ρQ qpω 0 q More generally, let us define P ˚the conditional probability over the inputs space I, i.e., P ˚" Pp¨| Iq where execution times C k p¨, i 0 q are well defined. This new probability P ˚is such that pQ, P ˚q is a probability space, depending only on hardware uncertainties. Inferring the data of sensors and other sources could be a new source of scheduling knowledge.

Long term

The multiprocessor scheduling problem of stationary real-time systems stays an open problem, and deterministic methods appear to fail in providing a simple and efficient solution. More generally, limit theorems in stochastic analysis offer a large panel of possibilities. Conditional probabilities are a powerful object that has not been explored yet in the real-time systems analysis. In the previous chapter, we give hints on how those conditional probabilities could be used in order to potentially improve DMP-driven bin packing. The relation between the mixed-criticality model and the probabilistic approach has been discussed often in this thesis, and is more explicit as the probabilistic approach provides answers that deterministic approaches cannot provide. It also allows to define and generalize deterministic results. Finally, we open the possibility to use machine learning with a parametric estimation method, as well as the possibility to define a new type of real-time scheduling yet to be built.

  Deadline of τ 1 is missed.

Figure 1 . 1 :

 11 Figure 1.1: Example of a scheduling algorithm decision on a single processor. The up-arrow represents the activation of a task, the down-arrow a deadline. The black circle means that the task has finished its execution. The gray-squared areas indicates that a task awaits for processing resources

Figure 1 . 3 :

 13 Figure 1.2: Global scheduling policy

  Figure 1.4: Restricted scheduling policy

( i )

 i Approximation: chapters 2, 3 and 4, a. in chapter 2, the mathematical model used to describe real-time systems is introduced, b. in chapter 3, the necessary conditions for the statistical analysis are built, c. in chapter 4, real-time systems are described with queueing theory results, (ii) Estimation: chapter 5, the statistical analysis itself: a parametric estimation adapted for response times, (iii) Optimization: chapters 6 and 7, a. in chapter 6, an online deadline miss probability-driven processor allocation, b. in chapter 7, future potential work for more optimization.

  9 gives us N ptq t Ñ tÑ8 λ and as N ptq Ñ tÑ8 8 the law of large numbers (Lemma 2.5) gives us 1 N ptq

Figure 2 . 3 :

 23 Figure 2.3: Example of a schedule with the discarding policy and without. The downarrow represents the deadline of a task. The black circle means that the task has finished its execution. The gray-squared areas indicates that a task awaits for processing resources

  ì pκq λ j c max j be the local maximum utilization of level i of κ and vmax i pκq " 1 spκq 2 ÿ τ j PΓ ì pκq λ j pc max j ´cmin j q 2

2 Figure 2 . 4 :

 224 Figure 2.4: Two tasks with implicit deadline using the RM policy

  analysis background . . . . . . . . . . . . . . 56 3.1.1 Brownian motions . . . . . . . . . . . . . . . . . . . . . 56 3.1.2 Backlog process . . . . . . . . . . . . . . . . . . . . . . . 58 3.2 Memoryless backlog . . . . . . . . . . . . . . . . . . . . . 59 3.2.1 The Loynes theorem . . . . . . . . . . . . . . . . . . . . 63 3.2.2 The heavy-traffic theorem . . . . . . . . . . . . . . . . . 65 3.3 Periodic backlog . . . . . . . . . . . . . . . . . . . . . . . 71 3.4 Schedulability test . . . . . . . . . . . . . . . . . . . . . . 75 3.5 Potential extensions . . . . . . . . . . . . . . . . . . . . . 77 3.5.1 Extension to EDF and FIFO . . . . . . . . . . . . . . . 77 3.5.2 Extension to general stationary inter-arrival times . . . 77

  Lemma 3.1 (Re-scaling property of Brownian motions). Let B be a standard Brownian motion. For any a ą 0, a ´1{2 Bpatq pdq " Bptq. This is an important property that we use in the next section when introducing the heavy-traffic theorem. Definition 3.2 (Brownian motion). A Brownian motion of drift u and deviation v ą 0 is a process W such that there exists a standard Brownian motion B such that W ptq ´W p0q " ut `vBptq (3.1)

Figure 3 . 1 :

 31 Figure 3.1: Level 3 demand of 1 000 instances of the Diaz and Kim (DK) model, the heavy-traffic demand process and the classical deterministic worst-case analysis (WCET) considering only the maximal execution time for each task, for ū " 0.838 and ūmax " 1.208 and hyper-period T , for Γ defined in Table3.1

  tÑ8 β k ptq and we denote π k pxq " P `β k ď x the distribution function of the steady-state backlog of level k.

  Figure 3.3b illustrates this upper-bound becoming exact in Figure 3.3c and Figure 3.3d.

  Consider the same hypotheses as Theorem 3.5 and let ūk ă 1. The heavy-traffic backlog process β p8q k " lim nÑ8 β pnq k is a reflected Brownian motion of drift ūk ´1 and deviation vk , and β p8q k ptq " Wk ptq ´t `sup

Figure 3 . 3 :

 33 Figure 3.3: Steady-state backlog simulations with different mean utilizations in the Diaz and Kim model. In black the histogram of simulations of βpnq{ ? n for n " 10000, in red the probability function of β.

  idle time . . . . . . . . . . . . . . . . . . . . . . . 84 4.1.2 Heavy-traffic time demand analysis . . . . . . . . . . . . 85 4.1.3 Conditioning response times . . . . . . . . . . . . . . . . 87 4.1.4 Worst-case response time . . . . . . . . . . . . . . . . . 90 4.1.5 Steady-state response time . . . . . . . . . . . . . .

Figure 4 . 1 :

 41 Figure 4.1: Trajectories of W p8q and average of the first idle time for ū " 0.838 and x " 4.85.

  Definition 4.1 (Heavy-traffic response time). Let R pnq k,l be the first idle time after the arrival of the l-th job of the task τ k in the sequence of M {G{1 queues defined in Eq. (3.8), i.e., R pnq k,l " inftt ą 0 : β pnq pA k,l `tq " 0u

Figure 4 . 2 :

 42 Figure 4.2: Representation of the response time R 2,1 as an idle time when O 2 " 0, C 2,1 " y and β 1 p0q " x, in Example 2.1

Figure

  The distribution function of R k is H max k (resp. Hk ).Proof. We can see that by construction Eq. (4.13) and Eq. (4.6) come from conditional probabilities. The representation in Proposition 4.1 indicates that the distribution of response times is conditioned by the values of the backlog and the execution time.

  Figure 3.2b and Figure 3.3b. The level 4 mean utilization is close to 1, hence Figure 3.2c and Figure 3.3c illustrate the behavior of backlogs when the utilization approaches its phase transition. The level 5 mean utilization is greater than 1, which illustrates the explosion (infinite response times) of the system, see Figure 3.2d and Figure 3.3d.

  Histogram of the generated response times of τ 3 in Table3.1, as defined in Section 4.2. Response time distribution functions of τ 3 in Table3.1.

Figure 4 . 3 :

 43 Figure 4.3: Simulations of a 10 000 instances for the SimSo simulations, steady and transient, EVT estimation of the WCRT of the SimSo simulations and simulations of heavy-traffic WCRT (H max

Figure 4 . 4 :

 44 Figure 4.4: First maximum ε-idle time for ε " 10 ´6, for ū " 0.838.

Figure 5 . 1 :

 51 Figure 5.1: Computation time of the EM algorithm with the knowledge of ūi and vi (fixed gamma) and without (non-fixed gamma)

Figure 5 . 4 :

 54 Figure 5.4: Execution time probability functions f i , i " 0, . . . , 29, used in SimSo, see Section 5.2.1. Integer-valued, their support all start at 1, the maximum is reached by Task 10 at 35.

Figure 5 . 5 :

 55 Figure 5.5: Execution time empirical probability functions of the 9 studied tasks of the drone autopilot PX4-RT

Figure 5 . 6 :Table 5 . 2 :Figure 5 . 7 :

 565257 Figure 5.6: Response times empirical distributions of the PX4-RT autopilot and QQplots with the χ 2 1 quantiles from Eq. (5.21) for each component (c.f.,the different colors) of the estimated mixtures

Figure 5 . 8 :

 58 Figure5.8: DMP for 12 randomly generated task sets. The estimation is always below the Hoeffding DMP, and the differences between the minimum and maximum DMP of the inverse Gaussian estimation are small. In solid line the average value, and the colored area represents the values between the 25%-percentile and the 75%-percentile.

(

  resp. deviation) of the tasks in Γ ì pκq. Let u max i

Figure 6 . 1 :

 61 Figure 6.1: Illustration of the non-sustainability of a static-priority scheduling algorithm using the Best-Fit bin-packing algorithm, a set of tasks Γ " tτ 1 , τ 2 , τ 3 u such that C 1 " 1, D 1 " 3; C 2 " 3, T 2 " 5, D 2 " 5; C 3 " 7, T 3 " 20, D 3 " 8, and an identical multiprocessor Π " tκ 1 , κ 2 u (one in grey, one in black).

2 .

 2 The performance of DMP-RAA with Hoeffding DMP is shown in Figure6.3, and a comparison in the periodic and stationary case is shown in Figure6.5. The task set is such that ūmax n ă ř κPΠ spκq and max κPΠ max τ i PΓ u max i spκq ă 1. First, we compare the full DMP and the DMP using Heoffding DMP. Then we compare the stationary and the periodic cases, i.e., considering only t min i as inter-arrival times, with DMP-First-Fit (q RAA paq " 1). Then we compare DMP-RAA with RAA for the Best-Fit and Worst-Fit algorithms. Finally we compare DMP-Best-Fit with some state-of-the-art global scheduling algorithms.

Figure 6 . 3 :

 63 Figure 6.3: Comparison of 100 instances of DMP-First-Fit (yellow) and DMP-First-Fit with Hoeffding DMP (blue).The first row represents the number of deadline misses, the second row the number of preemptions. Each column represents a processor and the last column the accumulation of all processors. In solid line the average value and the colored area represent the values between the 25%-percentile and the 75%-percentile.

Figure 6 . 4 :Figure 6 . 5 :

 6465 Figure 6.4: Comparison of RM-DMP-First-Fit on a stationary task set and its periodic equivalent. The first row represents deadline misses, the second row preemptions. Each column represents a processor. The dotted line represents deadline misses when the maximal local utilization exceeds 1. In solid line the average value and the colored area represent the values between the 25%-percentile and the 75%-percentile.

Figure

  Figure 6.7:

Figure

  Figure 6.8:

  Let µ be a probability function and the shrink operator µ Ñ µ defined by µ `pxq " µpxq1 xą0 `1x"0

Proposition 7. 1 (

 1 Local backlog). Let t ą 0 and consider a processor κ at the instant t ą 0. Let k P t1, . . . , nu and let w i pκq be the workload already executed on the active job of the task τ i P Γ k pκq on the processor κ. The current -i.e., at the instant t ą 0 -local backlog of level k in the processor κ is¨Bmax k pκq ´ÿ τ i PΓ k pκq spκqw i pκq '`( 7.4)with distribution function ˆµk pκq ˚δ´ř τ i PΓ k pκq spκqw i pκq ˙`.

  .1 . . . . . . . . . . . . . . . . . . . . . . . .

3.2 The backlog process of systems with different mean utilization, initialized with W p0q " ř τ i PΓ C i . . . . . . . . . . . . . . . . . . . . 3.3 Steady-state backlog simulations with different mean utilizations in the Diaz and Kim model . . . . . . . . . . . . . . . . . . . . . . . . a deterministic manner, such that statistical methods provide a suitable estimation of time behaviors of the studied system.

work Figure 1.6: Manuscript structure and reading dependencies

  Identification of Execution Modes using Cluster Analysis.Kevin Zagalo,

		1.6. Software
	Chapter 2: Model
	Chapter 3: Fluid
	model
	Chapter 4: Response
	time approximation
	Chapter 6: Optimization of multiprocessor scheduling	Chapter 5: Response time estimation
	Inference of
	scheduling knowledge
	Chapter 7: Future
	Liliana Cucu-Grosjean and Avner Bar-Hen, ETFA 2020, [Zagalo et al., 2020],
	(ii) Response Time Stochastic Analysis for Stable Fixed-Priority Real-Time Sys-
	tems. Kevin Zagalo, Yasmina Abdeddaïm, Avner Bar-Hen and Liliana
	Cucu-Grosjean, IEEE Transactions on Computers, Special issue on Real-
	time Systems, 2023, [Zagalo et al., 2022a],
	(iii) Response Time Parametric Estimation of Real-Time Systems. Kevin Zagalo,
	Olena Verbytska and Avner-Bar-Hen, Arxiv Preprint, 2022, [Zagalo et al.,
	2022b],

  ). Let X and Y be two timing variables. We say that X and Y are identically distributed if and only if @B P B X Y B Y ,

	and equivalently, @x P R `,
		F X pxq " F Y pxq
	and we write X	pdq " Y or equivalently X " dF Y . Particularly X " dF X .
	Definition 2.6 (Conditional probability). Let X and Y be two timing variables.
	The conditional timing variable X given Y " y is written X|Y " y and is such that
		ż
		P X pAq "	PpX P A|Y " yqdF Y pyq
	for all x ą 0.
	Definition 2.7 (Convolutions). Let X and Y be independent timing variables and
			P X pBq " P Y pBq

Z " X `Y . Then the distribution function of Z is the convolution F Z " F X ˚FY defined by

Definition 2.8 (Uniform distribution). The uniform distribution function on the

	bution is characterized by the distribution function Φ defined by
	Φpxq "	1 ? 2π	ż x ´8 exp `´y 2 {2 ˘dy, x P R	(2.4)
	Definition 2.11 (Gaussian distribution). The Gaussian distribution of mean m P R
	and variance v 2 ą 0 is characterized by the distribution function Φ m,v 2 pxq " Φp x´m v q.
	Definition 2.12 (Inverse Gaussian distribution). Let µ ą 0 and λ ą 0. The inverse
	Gaussian distribution of mean µ and shape λ has a probability function ψ defined by
		ψ pt; µ, λq "	c	λ 2πt 3 exp	2µ 2 t ˆ´λpt ´µq 2	˙(2.5)
	for t ą 0. Its mean is µ and variance µ 3 {λ. Its cumulative distribution function is
	given by
	Ψpt; µ, λq " Φ	˜cλ t ˆt µ	´1˙¸`e xp	ˆ2λ µ	˙Φ ˜´c	λ t ˆt µ	`1˙w
	interval r0, ts is defined by
		Gpxq "	minpx, tq t	, x ě 0
	Definition 2.9 (Exponential distribution). The exponential distribution of mean
	1{λ is characterized by the distribution function
		Gpxq " 1 ´e´λx , x ě 0
	Definition 2.10 (Standard Gaussian distribution). The standard Gaussian distri-

  compute the exceedence function of the response time R k,l

	Definition 2.21. Γ is said feasible if and only if there exists at least one scheduling
	policy such that the WCRT R max i

H k,l ptq " P pR k,l ą tq

(2.20)

Computing this exceedence functions requires to know the distribution of all the variables that it involves. For this matter, we build a pessimistic approximation of the response time of the task τ i denoted R max i in Chapter 3 with a fluid model.

With H i,j we can tell if the job τ i,j is schedulable or not. Although, computing all the H i,j , j P N is difficult. In order to be safe, i.e., make a pessimist analysis, we define the WCRT as a bound R max i such that for all j P N, R i,j ď st R max i , i.e., sup jPN H i,j ptq ď P pR max i ą tq

Without further information we cannot say if such bound exists and is finite.

However, if we can compute the distribution of the WCRT R max i , we then have a bound of deadline miss probabilities.

Table 3 . 1 :

 31 Task set used in the simulations of the experimental results of Section 4.4 In the end of this chapter, we focus on idle times, the times where the backlog is 0, and it is important to remark that any

	τ k λ ´1 k	rc min k , c max k	s	dF k	ūk	ūmax k
	τ 1	4	p1, 2q		p0.5, 0.5q	0.375 0.5
	τ 2	6	p1, 2q		p0.5, 0.5q	0.625 0.833
	τ 3	8	p1, 2, 3q		p0.5, 0.3, 0.2q	0.838 1.208
	τ 4 10	p1, 2, 3q		p0.6, 0.2, 0.2q	0.998 1.508
	τ 5 12	p1, 2, 3, 4q p0.5, 0.3, 0.1, 0.1q 1.148 1.841
	two arrival times of jobs of level k.

scheduling policy considering priority levels instead of specific tasks will provide the same idle times. The reason of this is that what is important at the end is the amount of workload demanded to the system and the amount of time that passes between job arrivals. In other words, for a sorted queue, i.e., by priority level, we can use FIFO results on priority level backlog in the next section. See Figure

2

.1.

  Taking nt instead of t gives us the result. Finally, we conclude with (2.12) that gives us n ´1W i pntq " t W i pntq

	(a) ū " 0.625, ūmax " 0.833	(b) ū " 0.838, ūmax " 1.208
	Figure 3.2: The backlog process of systems with different mean utilization, initialized
	with W p0q "	ř	τ i PΓ C i
	that lim tÑ8	W i ptq´u i t ? t	" Φ 0,v 2 i . nt	Ñ nÑ8 ut. Combine those two
	to get
				W i p8q	ptq	´W p8q i	p0q
	The demand processes W 1 , . . . , W p8q p8q n	are independent, thus we get that	W p8q k	"

ξ Wi ptq s Ñ tÑ8 e ξ 2 {2 , where we recognize the Laplace transform of a Gaussian variable N p0, 1q. Which means (c) ū " 0.998, ūmax " 1.508 (d) ū " 1.018, ūmax " 1.608 pdq " u i t `vi Bptq where B is a standard Brownian motion.

  xq λ k e ´λk t dt " lim pxq " 1 ´ż ψ k pt, xq e ´λk t dt where we recognize the Laplace transform of I k pxq, i.e.,

			ż
	Lpsq " Erexp p´sI k pxqqs "	ψ k pt, xq e ´st dt
	we conclude by developing this Laplace transform of an inverse Gaussian distribution
	of mean ξ " x 1´ū k and shape δ " x 2 v2 k
	Lpsq " exp	« ´δ ξ	˜c1 `2s	ξ 2 δ	´1¸ff

tÑ8 Ψ k´1 pt, xqp1 ´e´λ k t q´Ψ k p0, xqp1 ´e´λ k ˆ0q `ż ψ k pt, xq p1 ´e´λ k t qdt because d dt Ψ k pt, xq " ´ψk pt, xq. Finally since ş ψ k pt, xq dt " 1 because ψ k p¨, xq is a probability function for all x ą 0, we get p k

  Let τ k P Γ, ūk ă 1, Hk be the exceedence function of the steadystate response time of τ k , and let η k be as defined in Proposition 3.3 and Ψ k as

	As in Section 4.1.4, we get the distribution function of steady-state response
	times.
	Proposition 4.6. defined in (4.3). Then for all t ą 0,
		ż 8 0 Ψ pk " 1 ´ˆ1 Hk ptq " η k `?1 `2λ k γ k 2v k	´1	˙´1	(4.17)
	Proof. It is a direct consequence of Proposition 4.6 and
	pk " Erp k p βk qs
	" 1	´E " exp ˆ´β k	? 1 `2λ k γ k γ k p1 ´ū k q ´1	˙ȷ	(with (4.10))
	βk being an exponential variable of parameter η k , we conclude by identifying the
	Laplace transform of a exponential variable,
						Consider the
	steady-state response time
	Rk " inf	!	t ą 0 : βk `W k ptq " t ) p8q	(4.16)

k pt, xqe ´ηk x dx Proof. We know from Proposition 3.3 that the steady-state level pk ´1q backlog distribution is π k´1 . We know from Proposition 4.1 that the stead-state response time Rk is the first idle time with an initial demand of βk . Finally by definition of conditional probabilities we have Hk ptq " ş Ψ k pt, zq dπ k pzq, and dπ k pzq " η k e ´ηk z dz. Corollary 4.2. Let τ k P Γ, γ k " ´v k 1´ū k ¯2 and suppose ūk ă 1. The steady-state DMP of τ k is Lpsq " Erexp `´s βk ˘s " ˆ1 `s η k

Table 5 . 1 :

 51 Parameters of the task set used for the simulations in Section 5.2.1.

	0 1 2 3 4 5 6 7 8 9	15.481 5.556 5.708 3.38 5.198 4.057 4.998 3.786 2.167 7.453	17.1957 5.6996 5.9963 3.323 5.5314 4.0299 5.1184 3.9005 1.8259 8.3373	100 114 119 121 132 133 136 144 145 146	100 114 119 121 132 133 136 144 145 146	0.1548 0.2035 0.2515 0.2794 0.3188 0.3493 0.3861 0.4124 0.4273 0.4784	0.28 0.3589 0.443 0.4926 0.5683 0.6285 0.702 0.7506 0.7713 0.874	10 11 12 13 14 15 16 17 18 19	16.812 1.833 2.167 2.7 5.448 8.46 2.167 4.665 2.4 5.604	19.1248 1.5271 1.8259 2.4495 5.4483 9.2277 1.8259 4.7411 2.2361 5.7741	159 165 165 165 166 173 181 182 183 191	159 165 165 165 166 173 181 182 183 191	0.5841 0.5952 0.6083 0.6247 0.6575 0.7064 0.7184 0.744 0.7571 0.7865	1.0879 1.1061 1.1242 1.1485 1.2027 1.301 1.3175 1.3615 1.3834 1.4357	20 21 22 23 24 25 26 27 28	2.333 3.334 5.927 4.535 4.225 6.246 4.779 2.167 1.834	1.9147 3.0555 6.0701 4.4073 4.1931 6.758 4.8654 1.8259 1.4149
	Task τ i	Mean m i (ms)	Std s i (ms)	Periods t i (ms)	Deadlines d i (ms)	Mean utilization ūi	Maximum utilization u max i	Task τ i	Mean m i (ms)	Std s i (ms)	Periods t i (ms)	Deadlines d i (ms)	Mean utilization ūi	i Maximum utilization u max	Task τ i	Mean m i (ms)	Std s i (ms)	Periods t i (ms)

Table 6 . 1 :

 61 Maximum utilization bounds for migration strategies of the multiprocessor Rate-Monotonic with reasonable bin-packing

	full migrations restricted migrations	no migrations
	identical
	processors

  thus the simultaneous activation of all tasks of lower priority than τ i on κ. We call this scenario the local critical instant of level i of κ. B i pκq is the sum 1 of the worst-case blocking time of the tasks of higher or equal priority than τ i on the processor κ, i.e., the remaining workload to process by the processor κ before letting

	B max i	pκq "	ÿ	C j	(6.11)
			τ j PΓ ì pκq

To address this problem, we think locally, i.e., by processor, and use the information on the local utilization of each processor. Proposition 6.1 (Local critical instant). Let κ P Π and τ i P Γ ǹ pκq. If ūi pκq ă 1, the worst-case blocking time of level i in κ is any job of τ i`1 , τ i`2 , . . . execute. Proof. We suppose τ i P Γ ǹ pκq, i.e., τ i is active on κ, and ūi pκq ă 1 and let 1 With ř xPH x " 0.

  Ψpx, t; ūi´1 pκq, vi´1 pκqq and Ψ is as defined in Eq. (4.3). We suppose the processor κ is fixed, and let a " pτ i , κq. With the approximation of response times proposed in Chapter 4, we get the DMP conditionally to a backlog of level i fixed to a value x:

	ij
	p κ i pt, xqdG k ptqdµpxq	(6.14)
	where p κ i pt, xq " Proof. p κ i pT, xq " P ˆinf tPr0,T s	W κ i´1 ptq ´spκqt ą	´x˙( 6.15)

a Lemma 6.1. The DMP induced by the allocation a " pτ i , κq, where the backlog distribution of level i in κ is µ is p i pa, µq "

  Scheme of the RM-DMP-RAA algorithmwhere δ x is the Dirac measure on x, i.e.,

		RM-DMP-RAA
		Task subset	Local scheduler RM	Processor 1
		Task subset	Local scheduler RM	Processor 2 Processor 2
	Jobs	DMP-RAA
		Task subset	Local scheduler RM	Processor m
		Figure 6.2: δ x pAq "	$ ' & 1 if x P A	(6.18)
			' % 0 otherwise

(ii) if τ k P Γ í pκq, the probability that backlog of level k goes from b to b 1 by taking the action a is

  Algorithm 5 DMP-RAA when the task τ i is activated c Ð 0 for κ P A i do a Ð pτ i , κq if c ă r i pµ i pκq, aq `ci`1 pg a pµpκqqq ´log `qRAA paq ˘then c Ð r i pµ i pκq, aq `ci`1 pg a pµpκqqq

	a ˚Ð a
	if c " 0 then
	return H	Ź Discard τ i
	else
	return a 6.3

  We use the same proof as in Proposition 3.5 with W κ i as a Brownian motion of drift ūi pκq and deviation vi pκq, hence for t P p0, t min Thus, we can use the stateless immediate reward of the allocation a " pτ i , κq rpaq " ´log p H i pκq ´log q RAA paq " t min RAA paq for the allocation a " pτ i , κq, and the cost of a on higher priority tasks would be

	p H i pκq " exp ˆ´t min i be the Hoeffding DMP of τ i on κ, where vmax p1 ´ū i pκqq 2 vmax i pκq i pκq " ř τ j PΓ ì pκq pc max ˙(6.20) j ´cmin j q 2 {t min j is the local maximum deviation of τ i in κ. If t min i ą 1 1´ū i pκq ř q, we obtain that ūi pκqt `ÿ τ j PΓ ì pκq ErC j s spκq ą Er W κ i ptqs for all t ą 0. Thus, t ą 1 1´ū i pκq ř τ j PΓ ì pκq ErC j s spκq implies that t ą Er W κ i ptqs. Finally we get the same inequality with ūi pκq and vmax i pκq. For a more detailed proof one may see the proof of Proposition 3.5. Algorithm 6 DMP-RAA with Hoeffding DMP when the task τ i is activated c Ð 0 for κ P Π do if κ P A H i then if c ă t min i p1´ū i pκqq 2 vmax k pκq`v max i {spκq 2 ´log q RAA paq a Ð pτ i , κq if c " 0 then return H Ź Discard τ i else return a τ i ÿ τ k PΓ í pκq p1 ´ū k pκq ´λi ErC i s{spκqq 2 t min k v max k pκq `vmax

Proposition 6.3 (Local Hoeffding DMP). Let κ P Π, τ i P Π and a " pτ i , κq. We suppose ūi pκq ă 1, and let j PΓ ì pκq ErC j s{spκq, then

p i pa, µ i pκqq ď p H i pκq Proof. i pκq `řτ k PΓ í pκq t min k p1´ū k pκq´λ i ErC i s{spκqq 2 vmax k pκq`v max i {spκq 2 ´log q RAA paq then c Ð t min i p1´ū i pκqq 2 vmax i pκq `řτ k PΓ í pκq t min k p1´ū k pκq´λ i ErC i s{spκqq 2 vmax i p1 ´ū i pκqq 2 vmax i pκq ´log q i {spκq 2

  ErC j s spκq and all tasks τ k P Γ í pκq satisfy

								min i	ą
	1 1´ū i pκq	ř	τ j PΓ ì pκq
			t min k	ą	1 1 ´ū k pκq ´λi ErC i s{spκq	spκq ¨ErC i s	`ÿ τ j PΓ k pκq	spκq ErC j s	'
	Hence we redefine the set of possible actions for the Hoeffding DMP
		#
	A H i "	κ P A i : t min i	ą	1 1 ´ū i pκq	ÿ τ j PΓ ì pκq	ErC j s spκq	,
			@τ k P Γ í pκq, t min k	ą	1 1 ´ū k pκq ´λi ErC i s{spκq	spκq ¨ErC i s	`ÿ τ j PΓ k pκq	spκq ErC j s	'+
								(6.21)

in order to keep it reasonable. Any new DMP approximation used with DMP-RAA

Table 6 . 2 :

 62 Parameters of the task set used in the simulation of Section 6.4

	ūi u max i ūmax i	0.309 0.394 0.394	0.536 0.312 0.706	0.623 0.165 0.872	0.71 0.15 1.022	0.793 0.119 1.141
	i s	0.168	0.283	0.071	0.042	0.046
	u dG i {dt λ	p0.5, 0.5q 0.309	p0.5, 0.5q 0.227	p0.5, 0.5q 0.087	p0.5, 0.5q 0.087	p0.5, 0.5q 0.083
	i tt min , . . . , t max i	p132, 142q	p144, 154q	p121, 131q	p40, 50q	p109, 119q
	f i	p0.8, 0.2q	p0.75, 0.25q	p0.9, 0.1q	p0.7, 0.3q	p0.7, 0.3q
	u
	i tc min , . . . , c max i	p40, 52q	p30, 45q	p10, 20q	p3, 6q	p8, 13q
	i	1	2	3	4	5
	τ	τ	τ	τ	τ	τ

i ErC i s λ i ErC 2

Table 6 .3:

 6 Processor parameters used in Section 6.4

https://docs.scipy.org/doc/scipy/reference/generated/scipy.stats.gereme.html

) and steady-state response-time ( H3 ) when ū " 0.838

https://github.com/kevinzagalo/simso/blob/main/generator/task_generator.py

Acknowledgements

I am deeply grateful to my supervisors, Liliana Cucu-Grosjean and Avner Bar-Hen, for their guidance and support throughout my research journey. Their expertise, patience, and encouragement have been crucial in shaping this thesis. I am grateful to the reviewers of this thesis, Ye-Qiong Song and Anne Bouillard, for their valuable feedback and constructive comments, which have greatly improved the quality and clarity of this work.

ing model. Let Tk " lcm `λ´1 1 , . . . , λ ´1 k ˘be the hyper-period of level k of Γ. Let

be the demand of level k released during the l-th hyperperiod, i.e., the interval rpl ´1q Tk , l Tk s. Then if ūk ă 1 ´k 2 Tk the steady-state backlog βk exists, is finite and is equal to

where x `" maxp0, xq, c.f., [Baccelli and Brémaud, 2013, Property 2.2.1] and Theorem 3.3. In addition, there is an infinite number of idle times, c.f., [Baccelli and Brémaud, 2013, Property 2.2.5].

Proof. First of all, the Example 3.1.3 [START_REF] Baccelli | Elements of queueing theory: Palm Martingale calculus and stochastic recurrences[END_REF] shows that a stationary point process with priority class jobs is still associated to a point process of intensity ūk . Next, we observe that for periodic systems, the workload released in the intervals rpl ´1q Tk , l Tk s, l P N are i.i.d.. Indeed,

Then, in order to use Theorem 3.3 "at hyperperiod level" with the W k,l as execution times and Tk as inter-arrival times, we need to check ErW k,1 s ă Tk . We

Data

In this section we use the inverse Gaussian method on real data. We use a real case of 9 programs of an autopilot of a drone, PX4-RT [START_REF] Khazen | Work in progress: Kdbench -towards open source benchmarks for measurement-based multicore WCET estimators[END_REF], Ntaryamira, 2021], a modified version of PX4 [START_REF] Meier | Px4: A node-based multithreaded open source robotics framework for deeply embedded platforms[END_REF] with a real-time behavior, and a clock measuring preempting the operating system itself. PX4-RT is run on an ARM Cortex M4 CPU clocked at 180 MHz with 256 KB of RAM using a simulated environment from Gazebo [START_REF] Koenig | Design and use paradigms for gazebo, an open-source multi-robot simulator[END_REF]. PX4-RT allows to measure execution times (Figure 5.5 and Table 5.2) and response times during the flight of a drone. It runs on top of NuttX, a Unix-like operating system. It provides an infrastructure for internal communications between all programs and off-board applications. Each task is a NuttX task launched at the beginning of the PX4

program. The tasks read data from sensors (snsr), estimate positions and attitudes using a Kalman filter (ekf2), control the position (pctl) and the attitude (actl) of the drone, the flight manager (fmgr), the hover thrust estimator (hte), handle the navigation (navr), command the state of the drone (cmdr), and the rate controller (rctl), which is the inner-most loop to control the body rates. These tasks are in continuous interference with the operating system NuttX. Because the operating system has the highest priority, the nine tasks studied are constantly preempted by NuttX. Unfortunately, it is difficult to have information about the interfering operating system programs. Unlike the simulation in Section 5.2.1, PX4-RT runs concurrently with other tasks which do not have timing requirements, making it a complex system with many unknown variables. We test in this section whether and when the proposed parametric estimation is suitable for such complex system.

In this case, the distribution functions of execution times cannot be provided.

Therefore, we use the empirical distributions shown in Figure 5.5. Thus, the mean utilization ûi is computed with the empirical means of execution times, and the maximal utilization ûmax i with the empirical maximum of execution times, see 123

In this chapter we propose an application of the stochastic analyses proposed in the previous chapters to build a new class of allocation algorithms that use DMPdriven bin-packing that we define in Section 6.1. Let pΩ, P, Γ, Π, tθ t u t q be a stationary multiprocessor real-time system following a

We define DMP-driven bin-packing algorithms, which are allocation algorithms allowing to extend single processor scheduling policies to a restricted migration algorithm for multiprocessor systems that are DMP-aware. We restrict DMPdriven algorithms to the RM policy in this study. The bin-packing problem is NP-hard. For this reason, we build in this chapter an online processor allocation based on forward induction and use the results of previous chapters ensuring this allocation maintains the system stable.

The considered scheduling policy is work-conserving, i.e., does not idle when there is workload to be executed, and preemptive, i.e., a job may be preempted before the end of its complete execution, and its execution can be resumed with no cost.

The problem of the restricted scheduling on a multiprocessor system consists in two decisions: the dynamic allocation of processors and the static-priority assignment of tasks.

(i) Allocation: jobs are allocated to processors online; i.e., immediately upon arrival, a job is assigned to a processor based on its expected DMP. The allocation decision is a global load-balancing optimization problem in which jobs are distributed among multiple identical processors by minimizing their DMP. Tasks migrations are allowed, i.e., all jobs of a same task do not need to be executed on the same processor. However, we require in this study that a job that is allocated to one and only processor, and must finish its execution on the same processor. This is called restricted migration, see Figure 1.4. The restricted migration strategy provides a good compromise between the full migration and the partitioning strategies [START_REF] Carpenter | A categorization of real-time multiprocessor scheduling problems and algorithms[END_REF].

(ii) Priority assignment: the priority assignment is local and consists of solving a Γ ì pκq " tτ i 1 , . . . , τ ip u. Since the processor κ is fixed we can use the single processor reasoning introduced in Chapter 4. Thus the critical instant of level i is when all tasks activated on κ are released at the same time. Then the worst-case blocking time is

c.f., Proposition 4.4. Thus the simultaneous activation of all tasks active on κ of lower priority than τ i . For a speed greater than 1, it is sufficient to divide every execution time by the speed of the processor. Thus we have the result.

Remark. We cannot conclude as we did in Chapter 4 that the WCRT comes from this critical instant. However, we use the local critical instant to bound the demand at each allocation time.

Let µpκq " pµ 1 pκq, . . . , µ n pκqq be the vector of backlog distributions on a processor κ at a given time. In order to use forward induction, we exhibit an iterative behavior of the transitions of µpκq over time. Furthermore, backlogs cannot be measured in real-time, as execution times jobs are unknown until they finish. t ą 0. Instead of looking at the exact values of the backlogs, we look at how the distribution of B i pκq goes over time. Hence, the states considered for our decision are the distributions M " tµpκ j q : @i " 1, . . . , n, ūi pκ j q ă 1, j " 1, . . . , mu

In order to take online decisions, all possible worst-case blocking time distributions must be computed offline, before the run time scheduling. However, there is no need to do it for each processor.

Algorithm 4 Offline computation of the worst-case blocking time distributions

This offline computation is exponential in complexity. Saving those distributions,

RM-DMP-First-Fit on periodic vs. stationary task sets

We see in Figure 6.4 a comparison of RM-DMP-First-Fit, where q RF F paq " 1 with the Hoeffding DMP between the stationary and periodic inter-arrival times with the same inter-arrival rates. We see that its performance are quite equivalent.

This justifies that inter-arrival times act on the response times distributions only through its rate, e.g., Eq. (4.7).

DMP-RAA vs RAA

We test DMP-RAA against RAA on the two bin-packing algorithms Reasonable Best-Fit (RBF), where q RBF ppτ i , κqq " 1 ´umax