Luca Santinelli
email: luca.santinelli@onera.fr

Zhishan Guo
email: zsguo@cs.unc.edu

Laurent George
email: laurent.george@esiee.fr

Fault-Aware Sensitivity Analysis for Probabilistic Real-Time Systems

In probabilistic real-time modeling, diverse task exe cution conditions can be characterized with probabilistic distribu tions, where multiple execution time thresholds are represented, each with an exceeding probability. Comparing to traditional deterministic real-time, probabilistic approaches provide more flexibility in system behavior modeling, which may result in more precise schedulability analysis. With this work, we combine sensitivity analysis and probabilistic models of fault effects on task execution behaviors. The goal is to develop probabilistic schedulability analysis that is applicable to both faulty and non faulty execution conditions. While the probabilities accurately characterize faults and faults effects on worst-case execution times, the probabilistic schedulability analysis both qualifies and quantifies faults impacts on system schedulability.

I. INTRODUCTION

Since last decade, real-time systems are mostly implemented with multi-core and many-core commercial-off-the-shelf ar chitectures. The numerous interferences within such complex systems may end up into large variability of the execution time of tasks. For example, the state of the cache or the availability of a shared resource at runtime could largely change the time a task takes to execute.

The worst-case execution time (WCET) of a task represents an upper bound to the time needed to finish execution. In presence of faults, the execution time increases from the non faulty conditions, due to recovery and restore procedures that tasks subdue to. Then, in order to be an upper-bound, the WCET has to account for any condition, including the highly improbable pathological cases such as faults. This could lead to extremely pessimistic tasks worst-case execution models.

Probabilistic worst case analysis associates to WCETs the probabilities of happening of execution conditions, including those with vanishingly small probabilities. This may lead to important reduction of the computational resource over provisioning.

First papers on probabilistic approaches describe tasks worst case execution times by random variables, either discrete [START_REF] Tia | Probabilistic performance guarantee for real-time tasks with varying computation times[END_REF] or continuous [START_REF] Lehoczky | Real-time queueing theory[END_REF] distributions. Since Edgar and Burns [START_REF] Edgar | Statistical analysis of WCET for scheduling[END_REF], several papers have worked on obtaining safe and reliable probabilistic Worst-Case Execution Time (pWCET) estimates [START_REF] Hansen | Statistical-based wcet estima tion and validation[END_REF], [START_REF] Cucu-Grosjean | Measurement-based probabilistic timing analysis for mUlti-path pro grams[END_REF], [START_REF] Guet | On the reliability of the probabilistic worst-case execution time estimates[END_REF]. Unfortunately, pWCETs have been rarely applied for charac terizing faults and faults impact on task executions.

The probabilistic worst-case abstraction applies into schedu lability analysis with probabilities. Todays probabilistic schedu lability relies on many restrictive assumptions in order to be applied. Examples are the independence constraint which is imposed, [START_REF] Maxim | Response time analysis for fixed priority tasks with multiple probabilistic parameters[END_REF], [START_REF] Kaczynski | Deriving exact stochastic response times of periodic tasks in hybrid priority-driven soft real-time systems[END_REF] or the consideration of only the worst-case interactions between tasks [START_REF] Diaz | Stochastic analysis of periodic real-time systems[END_REF], [START_REF] Santinelli | A probabilistic calculus for proba bilistic real-time systems[END_REF].

Finally, the sensitivity analysis applied to schedulability stud ies how parameters/input uncertainty affects system schedula bility, [11], [START_REF] Bini | Sensitivity analysis for fixed priority real-time systems[END_REF]. In its probabilistic version, the sensitivity anal ysis quantifies the impact of the different possible probabilistic models on system schedulability [START_REF] Santinelli | Probabilities and mixed-criticalities: the probabilistic c-space[END_REF].

Fault management enlaces with both timing and schedulabil ity analysis. For example, in [START_REF] Pathan | Fault-tolerant and real-time scheduling for mixed criticality systems[END_REF] backups are executed for fault tolerance and recovering form task errors caused by hardware or software faults. In [START_REF] Wong | Schedulability analysis for the abort-and restart (ar) model[END_REF] instead, an algorithm to abort a restart a task in case of conflicts in shared resources accesses is proposed. Actual faults models are not included neither in the probabilistic timing analysis nor in the probabilistic schedulability analysis. Contribution: In this work we investigate the impact of faults on the schedulability of real-time systems. We formalize the scheduling problem with probabilistic task models embedding both faulty and non-faulty execution conditions. Furthermore, we make use of newly developed C-Space+ for representing and studying the probabilistic fault models. The pWCETs, obtained in presence and absence of faults, are used together with the sensitivity analysis and C-Space+ for quantifying faults effects on the system schedulability. Organization of the paper: In Section II we outline some backgrounding notions for probabilistic real-time. Section III details task modeling with probabilities and multiple execution scenarios. Section IV is for defining the probabilistic task modeling with faults effects, while Section V describes the C-Space+ and the possible sensitivity analysis on it. Finally, Section VI is for conclusions and future work.

II. BACKGROUND: REAL-TIME WITH PROBABILITIES

A real-time task consists of an infinite sequence of recurring jobs; each job must be executed before a given deadline.

In a periodic task system, a task Ti is described with the tuple (Oi, Ti, Di, Ci), where Oi is the offset or starting time that specifies the time instant at which the first job of Ti is released; Ti is the period representing the temporal separation between two successive jobs; Di is the deadline which defines the time interval in which task execution has to terminate; and Ci is the worst-case execution time defining the processing requirements for each job. The scheduling policy decides the task execution ordering, possibly with preemption or migration, while schedulability analysis guarantees the respect of the timing constraints.

Due to interferences from the system elements and the environment, tasks can exhibit multiple durations at runtime. It is then reasonable to describe task execution time as random

1 processes I .
The probabilistic worst-case execution time Ci of a task Ti generalizes the deterministic WCET. It is defined as the worst case distribution that upper-bounds any possible execution time the task can exhibit. In its abstract interpretation, Ci would includes multiple values, each with the probability of being the worst -case execution time of the task2 • Assuming the pWCETs as discrete distributions, the proba bility distribution function (pdf) representation of Ci is: [START_REF] Tia | Probabilistic performance guarantee for real-time tasks with varying computation times[END_REF] with pdfc,(Gi,r) = P(Ci = Gi,r), L;�l pdfc, (Gi,r) = 1 , and ki is the number of elements composing the p WCET distribution. P( Ci :s: Gi) = 1, and for all k 1 :s: k :s: ki' Ci,x: :s: Gi. a) WCET Thresholds: From Ci it is possible to define WCET thresholds (Gi,j, Pi,j) such that the value Gi,j is as sociated to the probability Pi,) of being the WCET for Ti.

Pi,j d:;j icdfci (Gi,j) quantifies the confidence on Gi,j of being the task worst-case execution time; 1 -Pi,j is the probability of respecting Gi,j and Pi,j is the probability of passing it. WCET thresholds are derived from pWCET estimates and are complementary representations to the worst-case. They are single value WCET with associated a probability.

With finite support pWCETs, it exist a WCET threshold G; such that cdfc, (Gn = 1. G; would be the deterministic WCET estimation upper-bounding any WCET threshold.

Recent works have investigated how to derive continuous pWCETs estimates from execution time measurements in different system conditions, [START_REF] Cucu-Grosjean | Measurement-based probabilistic timing analysis for mUlti-path pro grams[END_REF]. Discrete and finite support pWCETs can always be derived as approximations, at relatively low probabilities, of such continuous pWCET estimates [START_REF] Guo | Edf schedulability analysis on mixed-criticality systems with permitted failure probability[END_REF].

b) Worst-Case Independence: Assuming Ci to be the probabilistic worst-case distribution of Ti, it means that in Ci there have already been included all the possible inter ferences and their effects [START_REF] Cucu-Grosjean | Independence -a misunderstood property of and for (probabilistic) real-time systems[END_REF]. This is from the definition of statistical independences, cdfci , C ; = cdfci . cdfc;, which creates independence between tasks. By assuming the pWCET Ci, tasks become independent at the cost of having embedded dependence effects; thus more pessimistic worst-case models.

In this work we consider a set on n periodic probabilistic tasks r = {Tl, ... ,Tn } , with Ti = (Oi,Ti, Di,Ci). The hyperperiod H is the last common multiple of all the peri ods, H = lcm(Tl, ... , Tn). r is scheduled according to the preemptive Earliest Deadline First (EDF) paradigm, [START_REF] Baruah | Algorithms and complexity concerning the preemptive scheduling of periodic, real-time tasks on one processor[END_REF].

III. PROBABILISTIC WORST-CASE EXECUTION TIME

MODELING A Measurement Based Probabilistic Timing Analysis (MBPTA) approach applies the Extreme Value Theory (EVT) I A random process is a sequence of random variables describing a process whose outcomes do not follow a detemlinistic pattern, but follow probability distributions.

2 Calligraphic letters are used to represent distributions while non calligraphic letters are for scalars. for computing pWCET estimates out of measured execution times, [START_REF] Guet | On the reliability of the probabilistic worst-case execution time estimates[END_REF]. Figure 1 describes the general idea of MBPTA: i) measurements of task execution times are taken from a system configuration and specific execution conditions; ii) the trace of measurements is transformed into pWCET estimates with the extreme value theory (red line distribution). The EVT guarantees that if certain hypotheses are verified, from the actual measured execution behavior it is possible to infer rare events, where the worst-case execution time should lie. The EVT produces a continuous distribution which is a safe estimation of the worst-case behavior of the task: the pWCET estimate Ci. By safe estimation we mean a pWCET which is larger than or equal to any possible task execution time.

In the rest of the paper we apply both Ci and Gi, the WCET threshold (Gi, lO-9), for modeling task behaviors and formalizing the sensitivity analysis. We consider Ci and Gi from different task execution conditions. A trace of measurements accounts for some of the interfering conditions and the inputs which happens at runtime. The resulting pWCET estimate Ci embeds those system conditions and others which have not been measured. Therefore, the EVT is able to infer some of the unknown from the known measurements.

A. Worst-Case Guarantees

The pWCET from the MBPTA could be considered the worst case for only the execution conditions measured -pWCET relative to the conditions measured. But what if the execution scenario/inputs heavily changes e.g., operational mode change, different environment conditions or faults appears, and they have not been included into the measurements? In that case, the EVT would not be able to correctly estimate absolute rare events anymore.

Given a scenario j among the set of possible system execu tion scenarios3 J, the worst-case profile for j is C! and it comes from the measurements taken under condition j. The way for guaranteeing safe pWCET estimates Ci for J is to account for all the scenarios within J.

c) Worst-Case Profiling: The worst-case estimate Ci could be defined as an envelope among the possible probabilistic profiles: Ci d;j maXjE J {C{}. With the l-CDFs it is:

(2) d) Worst-Case Sets: Alternative to Equation (2), it is the solution where the scenarios are kept separated. All of them are needed but they are not merged in a single model. It is:

-de! ( 1 2 I J I ) Ci = C i, Ci ,•••, C i (3)
the set of pWCET estimates, and

-d ef ( 1 2

IJI)

C i = Ci , Ci , ... , Ci the set of WCET thresholds such that (Cf, 10-9) 'Vj E J.

(4)

The worst-case sets representation i.e. Equation (3) and Equation ( 4) is what we apply in this work. Figure 2 gives an example of worst-case representations for a task multi scenario. In particular there are illustrated two scenarios with the histogram, the pdf and the icdf representations of the measurements.

IV. FAULTS EFFECTS ON TASK EXECUTION TIME

Real-time systems are prone to faults, either transient or permanent faults, which could affect task executions [START_REF] Slijepcevic | Dtm: Degraded test mode for fault-aware probabilistic timing analysis[END_REF]. For example, a cache fault could end up in a temporal or permanent impossibility of using a cache block [START_REF] Chen | Static probabilistic timing analysis in presence of faults[END_REF]; this increases the task execution time due to the larger latencies for retrieving the information in memory.

The abort and restart model [START_REF] Wong | Schedulability analysis for the abort-and restart (ar) model[END_REF] can be used to model the occurrence of a fault i.e. to restart the faulty task, thus increasing its WCET. There exist other fault models with different impacts on the task execution time. In this work we could exploit them all by investigating the resulting task execution times.

It would be possible to measure execution times under faulty conditions i.e. fault scenario. The fault scenario assumes that the fault happens at each task instance. The measurements would account for the penalties on the task execution time due to faults, such as the delay due to the restoring of the system status and the re-execution of the task. Traces of measurements under fault would have execution times, each impacted by the constant presence of faults. Crult would be the pWCET for that scenario.

Instead, by considering non-faulty conditions i.e. fault never happening -no-fault scenario, it is possible to have the pWCET Intuitively, the fault scenario is the worst-case scenario (among the two considered) since the penalties/largest exe cution times are measured from it. Thus crult could be a more pessimistic safe pWCET for both no-fault and fault. Nonetheless, it would happen that small execution times values in the no-fault scenario have larger probabilities than the fault scenario. In order to have a complete task execution time model, both no-fault and fault scenarios have to be collected.

C n o-f au lt

In this paper we consider faults and faults impact abstractly modeled through traces of execution times. This allows us to develop a modeling and analysis framework general enough to approach any possible fault. The examples presented are abstract case studies that we apply to validate the framework.

Example 1. We consider a task with two execution conditions i. e. two scenarios happening: no-faults and fault. In case of no-faults the task executes in its normal way, no faults happening. The execution time variability is given by functional and systemic effects from the normal task behavior. no-faults is the baseline for the other cases. In case of fault the task executes always under the most critical fault condition.

The impacts of the 2 scenarios on the task execution times are represented in both Figure 2 and Figure 3( a). The execution times dif f er according to the conditions experienced, and the dif f erences quantifies the fault effects. Figure 3( b) depicts the pWCET resulting from the measured execution time. The 2 pWCETs reflect the faults impact on the task worst-case behavior.

In this example we assume that the measurements of execu tion times follow a Gaussian distribution in both scenarios. In particular, with the mean JL = 15 and the standard deviation a = 2 for the no-fault, and with JL = 70 and a = 2 for the fault scenario. The fault scenario is more than doubling the no-faults condition. This could happen due to fault models where the task is asked to re-execute, or a recovery procedure is called for restoring the task normal behavior. In this example the faults affects task executions on average with an increase of 4.6 times. This is an abstract example where we chose to emphasize fault effects, even though in real cases faults could have a smaller impact on the average task execution.

The dif f erent distributions are illustrated in Figure 2

A. Task Modeling with Faults

Having different execution scenarios directly affects the safety of pWCET estimations, intended as the capability of upper-bounding the assumed scenarios. Supposing to have the set of possible scenarios J = {nofault, fault}, by considering only the no-fault scenario it is not safe enough for characterizing the task worst-case behavior among J. The resulting pWCET estimation C; o-f aul t cannot be assumed as safe worst-case estimation for the task because the fault effects are not included. The fault scenario, by embedding the faults effects in the measurements (fault penalties that increases the execution times) is an upper-bound to non-faulty conditions also. Hence, the pWCET C! aul t could be considered a safe estimation of the worst-case task behavior resulting from the worst-case execution conditions within J.

We stress the fact that the worst-case is intended as the worst scenario among the possible known conditions J. The conditions are modeled by measurements which makes the pWCET ony relative to the conditions accounted. Instead, the non considered scenarios j 'I. J, cannot be modeled by any MBPTA approach, thus it is not possible to provide an absolute guarantee on the worst-case. To note that fault is an extreme scenario, since the fault is always active in it e.g., the task is always forced to abort and restart. We make use of it to enforce the task worst-case execution conditions. Nonetheless, both the modeling and the analysis we propose can face any scenario, including more realistic fault models.

• From Crult it would be possible to extract (Ci(HI),1O-9) ; we name Ci(HI) the HI-safe WCET as it results from the safest pWCET model among the possible scenarios, Cr ult == Crr. The difference that exist between fault and no-fault execution conditions results into Crr greater than or equal to C} o . This is due to the larger execution time and eventually larger variability of the execution times in case of faulty conditions. The partial ordering between distributions defined as in [START_REF] Diaz | Stochastic analysis of periodic real-time systems[END_REF]. Also Ci(HI)

The enhanced task model from Equation ( 5) is essentially asserting that depending on the conditions for the timing analysis applied, it is possible to have more or less guarantees on the pWCET and the WCET thresholds estimates. Only by considering all the scenarios it would be possible to have safe worst-case models. Equation ( 5) defines the fault model to tasks. Equation ( 5) reminds of the mixed-criticality task modeling with high and low criticality modes, [START_REF] Guo | Edf schedulability analysis on mixed-criticality systems with permitted failure probability[END_REF]. Indeed it is a very similar notion, although here is more general as it applies to faults modeling, execution scenarios and confidence on the timing analysis tools. It could apply also to the mixed-criticality problem and the possible operational modes the task can have. While the WCET thresholds are taken at probability 10-9, other thresholds at 10-3, 10-5 and 10-6 can be considered for increasing the flexibility and the representative of the prob abilistic task representation. Then, it could exist (C}P, 10-3) , (c}?, 10-5 ), (C}?,1O-6) and (C},?, 10-9 ). Fi�ure 3(a) sho'ws traces of execution time measJrements in case of no fault and fault conditions. Figure 3(b) depicts pWCETs in the two scenarios from the dif f erent measured execution times.

V. THE C-SPACE+

The C-Space+ is the extension of C-Space we develop for pWCETs appliying the new task model of Equation [START_REF] Cucu-Grosjean | Measurement-based probabilistic timing analysis for mUlti-path pro grams[END_REF] for different execution scenarios and different safety levels. We make use of the C-Space+ for formalizing the sensitivity sensitivity and the schedulability analysis with probabilities and safety levels.

A. The C-Space

The C-Space is a space built on tasks WCETs Ci, [11], [START_REF] Bini | Sensitivity analysis for fixed priority real-time systems[END_REF]. Within it, it is possible to represent feasibility regions where each point c = (CI, C 2 , ... ,Cn) inside the region represents a schedulable task set. A point c outside the feasibility region is a task set not schedulable. Each task Ti assumes WCETs from c, Ci E c.

In case of EDF, the feasibility region is derived from the comparison between the demand bound function dbf and the available resource. The task schedulability is assured iff

\It E D, dbf(t):s; t , (6)
with D the set of r deadlines within the hyperperiod H, [START_REF] Baruah | Algorithms and complexity concerning the preemptive scheduling of periodic, real-time tasks on one processor[END_REF].

Task Ti demand bound functions dbfi is such that dbfi(t , ') d ;J l t T�i +1 J XCi, while the demand bound function dbf of the set of tasks is the combination of tasks demand bound functions dbf(t , ') d ;J Li dbfi(t , . ). The WCETs Ci are the variables for building the C-Space. The feasibility region defined according to Equation ( 6) defines bounds on the CiS.

B. C-Space+ Representativeness

The C-Space+ accounts for the fault models with the discrete and finite possible execution conditions per task, Equation (5). C-Space+ is a space built on tasks WCET thresholds of Equation ( 4), where it is possible to represent schedulable task set, safety levels and confidence probabilities. A point c outside the feasibility region is a task set not schedulable.

The task model Ti = ((Ci(LO), Ci(HI)), Ti, Di) results into the set of dbfs:

modeling and the analysis we propose can face any scenario, including more realistic fault models.

• From e { ault it would be possible to extract (Ci (HI) , 1O -9 ) ; we name Ci (HI) the HI-safe WCET as it results from the safest pWCET model among the possible scenarios, eta ult == err. The difference that exist between fault and no-fault execution conditions results into err greater than or equal to efO. This is due to the larger execution time and eventually larger variability of the execution times in case of faulty conditions. The partial ordering between distributions defined as in [START_REF] Diaz | Stochastic analysis of periodic real-time systems[END_REF]. Also Ci (HI) ?: Ci LLO) as they are both taken at p = 10- 9 from respectively e i I and efo. How much they differ depends on the relationship between faults and no faults and the impact that faults have on the task execution time.

Generalizing, there could exist sets of pWCETs (efo, et, ... , erI)

and sets of WCET thresholds (Ci (LO) , Ci (l) , ... , Ci (HI)) for a task. The intermediate safety levels would model execution conditions in between the worst-case and the no-fault case or different faults models/fault impacts. The probabilistic analysis would benefit from such a more fine grained modeling with better schedulability results. In this work we consider only two safety levels, thus Ti = ((ef o,err),Ti ,Di ) with the pWCET, or as Ti = ((Ci (LO) , Ci(HI)), Ti , D i ) if only the WCET thresholds are applied. Ti d ;j ([(efo , erl) , (Ci(LO), Ci (HI)) ], Ti , Di ) [START_REF] Cucu-Grosjean | Measurement-based probabilistic timing analysis for mUlti-path pro grams[END_REF] The enhanced task model from Equation ( 5) is essentially asserting that depending on the conditions for the timing analysis applied, it is possible to have more or less guarantees on the pWCET and the WCET thresholds estimates. Only by considering all the scenarios it would be possible to have safe worst-case models. Equation (5) defines the fault model to tasks.

Equation (5) reminds of the mixed-criticality task modeling with high and low criticality modes, [16]. Indeed it is a very similar notion, although here is more general as it applies to faults modeling, execution scenarios and confidence on the timing analysis tools. It could apply also to the mixed-criticality problem and the possible operational modes the task can have. While the WCET thresholds are taken at probability 10-9 , other thresholds at 10-3 , 10-5 and 10-6 can be considered for increasing the flexibility and the representative of the probabilistic task representation. Then, it could exist (Cf ? , 10 -3 ) , (Cf?,lO-5 ) , (CfP, and (Cf'?, 10-9 ) . F i ũ r e 3(a) sho'ws traces of execution time measJrements in case of nofault and fault conditions. Figure 3(b) depicts pWCETs in the two scenarios from the different measured execution times.

V. THE C-SPACE+

The C-Space+ is the extension of C-Space we develop for pWCETs appliying the new task model of Equation ( 5) for different execution scenarios and different safety levels. We make use of the C-Space+ for formalizing the sensitivity sensitivity and the schedulability analysis with probabilities and safety levels.

A. The C-Space

The C-Space is a space built on tasks WCETs Ci , [11], [START_REF] Bini | Sensitivity analysis for fixed priority real-time systems[END_REF]. Within it, it is possible to represent feasibility regions where each point c = (Cl , C2 , ... , Cn) inside the region represents a schedulable task set. A point c outside the feasibility region is a task set not schedulable. Each task Ti assumes WCETs from c, Ci E C.

In case of EDF, the feasibility region is derived from the comparison between the demand bound function dbf and the available resource. The task schedulability is assured iff Vt E D , dbf(t) ::::: t , [START_REF] Guet | On the reliability of the probabilistic worst-case execution time estimates[END_REF] with D the set of r deadlines within the hyperperiod H, [START_REF] Baruah | Algorithms and complexity concerning the preemptive scheduling of periodic, real-time tasks on one processor[END_REF].

Task Ti demand bound functions dbfi is such that dbfi (t, •) d;j l t-y.?i + lJ XCi, while the demand bound function dbf of the set of tasks is the combination of tasks demand bound functions dbf(t, •) d;j L i dbfi (t, .). The WCETs Ci are the variables for building the C-Space. The feasibility region defined according to Equation (6) defines bounds on the CiS.

B. C-Space+ Representativeness

The C-Space+ accounts for the fault models with the discrete and finite possible execution conditions per task, Equation (5). C-Space+ is a space built on tasks WCET thresholds of Equation ( 4 i =l

We remind that the combinations and dbfs here before are not all the possible combinations. They are a subset where each element dominates other configurations i.e. upper-bounds other configurations.

The different WCET thresholds per task allow enriching the C-Space+ representation with more informations about the safety or not of the points c. Moreover, by considering the probability associated to the CiS, it is possible to add proba bilities to the C-Space+. Indeed, with (Ci , j , Pi , j), the resulting demand bound function dbfi (t , Ci , j) = l tTD; + 1 J X Ci , j has Pi , j associated which is the confidence on the demand bound function upper-bounding task behaviors. With probability Pi , j, 7i demands more computation time than dbfi (t , Ci , j). For a point C, the probability is given by the product of the WCET thresholds composing c due to the pWCET independence. The HI and LO safety levels and the probabilities remain separated. Figure 4 gives an example of the C-Space+ with points c and probabilities represented. The probabilities are the exceeding thresholds associated to the points, equivalently the confidences of not passing the execution times c at runtime.

(CrJ = 20,10-9). In Figure 5(a) all the possible WCET thresholds combinations c from the input pWCETs are plotted. Schedulable c are distinguished from non schedulable ones. Horizontal planes are to distinguish safety levels (HIand LO) and WCET confidences (at 10-9 and 10-5 per safety level). Figure 5(b) shows the feasibility region for the EDF schedulability.

Figure 6 gives a better insight of the C-Space+ with 2D representations. Only the plane (71,7 2 ) is represented at two values of C3, respectively C3 = 15 and C3 = 20. The probabilities describe confidences on the cs: the tasks WCET configuration has that probability of being passed during execution. For example, for c = [START_REF] Bini | Sensitivity analysis for fixed priority real-time systems[END_REF]11,[START_REF] Chen | Static probabilistic timing analysis in presence of faults[END_REF], it is that 71 and 73 have their HI-safe WCET thresholds in particular, 7 1 with the threshold at P = 10-5 and 73 with the threshold at P = 10-9. Instead, 7 2 has its Lo-safe WCET threshold with the threshold at P = 10-9.

The probability associated to c = [START_REF] Bini | Sensitivity analysis for fixed priority real-time systems[END_REF]11,[START_REF] Chen | Static probabilistic timing analysis in presence of faults[END_REF] is P c = 10-5 * 10-9 * 10-9 = 10-2 3, due to the independence between the tasks. Pc is the probability that the application {71 ' 7 2, 73 } passes the WCET threshold configuration c; it is the confidence on c. As a reminder, the probability is strictly associated to the safety level. P = 10-9 for 7 2 is the probability that C 2 (LO ) is passed while remaining in the Lo-safe characterization of the task. Thus Pc = 10-2 3 is the confidence on c = [START_REF] Bini | Sensitivity analysis for fixed priority real-time systems[END_REF]11,[START_REF] Chen | Static probabilistic timing analysis in presence of faults[END_REF] where 71 and 73, although changing WCETs, they remain in their HI-safe characterization and 7 2 remains in its Lo-safe characterization.

C. Sensitivity Analysis for the C-Space+

The sensitivity analysis on top of the C-Space+ takes into account the different and possible WCET thresholds, the HI as well as LO safety levels and the probabilities.

With respect to faults, the sensitivity analysis allows i) quan tifying the effects of faults on the application schedulability and ii) quantifying the maximum confidence it is possible guaranteeing for a specific configurations.

We describe the contributions of the sensitivity analysis via an example. Future work will consider a more detailed with dbfi (t, Ci (HI)) 2: dbfi (t, Ci(LO)). Some tasks combinations accounting for the safety levels are: L dbfi (t, Ci (HI)).

i= l

We remind that the combinations and dbfs here before are not all the possible combinations. They are a subset where each element dominates other configurations i.e. upper-bounds other configurations.

The different WCET thresholds per task allow enriching the C-Space+ representation with more informations about the safety or not of the points C. Moreover, by considering the probability associated to the CiS, it is possible to add probabilities to the C-Space+. Indeed, with (Ci, j , Pi,j )' the resulting demand bound function dbfi(t, C i,j ) = l t--: t ' + 1 J X Ci, j has Pi, j associated which is the confidence on the demand bound function upper-bounding task behaviors. With probability Pi, j , Ti demands more computation time than dbfi (t, Ci,j)' For a point C, the probability is given by the product of the WCET thresholds composing c due to the pWCET independence. The HI and LO safety levels and the probabilities remain separated. Figure 4 gives an example of the C-Space+ with points c and probabilities represented. The probabilities are the exceeding thresholds associated to the points, equivalently the confidences of not passing the execution times c at runtime. The probabilities describe confidences on the cs: the tasks WCET configuration has that probability of being passed during execution. For example, for c = [START_REF] Bini | Sensitivity analysis for fixed priority real-time systems[END_REF]11,[START_REF] Chen | Static probabilistic timing analysis in presence of faults[END_REF], it is that T 1 and T3 have their HI-safe WCET thresholds in particular, T1 with the threshold at P = 10-5 and T3 with the threshold at P = 10-9 . Instead, T2 has its Lo-safe WCET threshold with the threshold at P = 10-9 .

The probability associated to c = (12 , 11 , 20) is Pc = 10 -5 * 10-9 * 10-9 = 10-23 , due to the independence between the tasks. Pc is the probability that the application {T1 , T 2, T3 } passes the WCET threshold configuration c; it is the confidence on C. As a reminder, the probability is strictly associated to the safety level. P = 10-9 for T2 is the probability that C2 (LO) is passed while remaining in the Lo-safe characterization of the task. Thus Pc = 10-23 is the confidence on c = (12 , 11 , 20) where T 1 and T3, although changing WCETs, they remain in their HI-safe characterization and T2 remains in its Lo-safe characte rization.

C. Sensitivity Analysis for the C-Space+

The sensitivity analysis on top of the C-Space+ takes into account the different and possible WCET thresholds, the HI as well as LO safety levels and the probabilities.

With respect to faults, the sensitivity analysis allows i) quantifying the effects of faults on the application schedulability and ii) quantifying the maximum confidence it is possible guaranteeing for a specific configurations.

We describe the contributions of the sensitivity analysis via an example. Future work will consider a more detailed From Figure 7 and Figure 8(b) we show how the sensitiv ity analysis work in quantifying the costs for a schedulable task set. For example, to pass from the non-schedulability e = [START_REF] Pathan | Fault-tolerant and real-time scheduling for mixed criticality systems[END_REF][START_REF] Wong | Schedulability analysis for the abort-and restart (ar) model[END_REF][START_REF] Chen | Static probabilistic timing analysis in presence of faults[END_REF] to the schedulability, some possibilities are: i) e I = [START_REF] Pathan | Fault-tolerant and real-time scheduling for mixed criticality systems[END_REF][START_REF] Santinelli | A probabilistic calculus for proba bilistic real-time systems[END_REF][START_REF] Wong | Schedulability analysis for the abort-and restart (ar) model[END_REF], meaning that both 72 and 73 cannot be guaranteed at their HI-safety WCET; ii) e II = [START_REF] Kaczynski | Deriving exact stochastic response times of periodic tasks in hybrid priority-driven soft real-time systems[END_REF][START_REF] Wong | Schedulability analysis for the abort-and restart (ar) model[END_REF][START_REF] Chen | Static probabilistic timing analysis in presence of faults[END_REF], meaning that 71 can be only with its Lo-safety WCET at p = 10-5 ; iii) e III = [START_REF] Bini | Sensitivity analysis for fixed priority real-time systems[END_REF][START_REF] Kaczynski | Deriving exact stochastic response times of periodic tasks in hybrid priority-driven soft real-time systems[END_REF][START_REF] Chen | Static probabilistic timing analysis in presence of faults[END_REF], meaning that 71 can be guaranteed up to C1 = 12 HI-safety but at p = 10-5 and 72 can be guaranteed up to C2 = 8 Lo-safety but at p = 10-9 .

From Figure 8

VI. CONCLUSION

The work proposed embeds faults and fault impacts into real time schedulability analysis. First, the probabilistic task model accounts for both faulty conditions and non-faulty execution conditions. Then, the probabilistic task model is applied with the sensitivity analysis for evaluating the task set schedulability. The C-Space+ allows to both qualify and quantify faults impacts on the schedulability through the sensitivity analysis.

Future works will include the development of schedulability strategies for leveraging the probabilistic fault models and the safety levels. Furthermore, the sensitivity analysis developed will be applied to the mixed-critical scheduling problem.

  cdfc, denotes the cumulative distribution function (cdf) rep- resentation of Ci, cdfci(G) = P(Ci :s: G) = L�=lPdfc,(x) with discrete distributions. The inverse cumulative distribution function (icdf) icdfc, (G) outlines the exceedence thresholds. icdfc; (G) = P( Ci � G) is the probabili2j of having execution time larger than G, icdfdG) = 1 -L x=l pdfcJT).

Fig. I .

 I Fig. I. Measurement-based probabilistic timing analysis toolchain. From the measurements the pWCET is inferred with the extreme value theory.

  t at scenarIO. ere, t e executIOn times observed exploit only the task functional behavior. The trace of measurements would have execution times due to the absence of faults. A collection of execution times measurements is a trace of measurements.

Fig. 2 .

 2 Fig. 2. Different execution scenarios in the histogram representation. Empiric distributions from 1000 measurements following Gaussian law.

Figure 2

 2 Figure 2 illustrates the two scenarios; the two traces of execution times are depicted with the histogram, pdf and icdf representations.

F

  C n o-f au lt . POSSl e to extract (Ci(LO), 10-9 ) ; we name Ci(LO) the Lo-safe WCET. as it results from the less safe p WCET model C � o-f aul t == C LO t .

2 :

 2 CikLO) as they are both taken at p = 10-9 from respectively C i I and C} o . How much they differ depends on the relationship between faults and no faults and the impact that faults have on the task execution time. Generalizing, there could exist sets of pWCETs (C}O, Cl, ... , Cr') and sets of WCET thresholds (Ci(LO), Ci(I), ... , Ci(HI)) for a task. The intermediate safety levels would model execution conditions in between the worst-case and the no-fault case or different faults models/fault impacts. The probabilistic analysis would benefit from such a more fine grained modeling with better schedulability results. In this work we consider only two safety levels, thus Ti = ((C} O ,Crl) ,Ti,Di) with the pWCET, or as Ti = ((Ci(LO), Ci(HI)), Ti, Di) if only the WCET thresholds are applied. d ef [ LO HI 1 Ti = ((C i ,C i ),(Ci(LO),Ci(HI)) ,Ti,Di)

Fig. 3 .

 3 Fig. 3. Different execution scenarios with different worst-case estimates.

F

  extract (Ci (LO) , 10-9 ) ; we name Ci (LO) the Lo-safe WCET. as it results from the less safe p WCET model e ~o -fault == e LO , .

Fig. 3 .

 3 Fig. 3. Different execution scenarios with different worst-case est imates.

  ), where it is possible to represent schedulable task set, safety levels and confidence probabilities. A point c outside the feasibility region is a task set not schedulable. The task model Ti = ((Ci (LO) , C i(HI)) , Ti , Di ) results into the set of dbfs: d ef t -Di dbfi (t, Ci (HI)) = l-----y;;-+ 1J x C i (HI) and , d e f t -D dbfi (t, Ci (LO)) = l T + 1J X Ci (LO),

1 L

 1 Different execution time scenarios and the resulting traces of execution times execution time in CPU cycles probability 10-9 pWCET(LO) pWCET(HI) C(LO) C(HI) (b) Different execution time scenarios and the resulting worst-case estimates with dbfi(t , Ci(HI)) � dbfi(t , Ci(LO)). Some tasks combina tions accounting for the safety levels are: (C1(LO ) , C 2 (LO ) , ... , C n (LO )), (C 1 (LO ) , C 2 (LO ) , ... C n (HI)) , As a result, there exist multiple possible demand bound func tions for the set of tasks depending on the WCET thresholds chosen: n ndbfi(t , Ci(LO )) + dbf n (t , C n (HI)) , i =l n L dbfi(t , Ci(HI)).

Example 3 . 9 )

 39 Given the probabilistic set of tasks (7 1, 7 2, 73) such that: 71 = (( C1 (LO ) = 10, C1 (HI) = 14),40,40), 7 2 = ((C 2 (LO ) = 8 , C 2 (HI) = 15),50,50) and 73 = ((C3(LO ) = 15, C3(HI) = 20),40,40); time is expressed in CPU ticks. To the tasks model of Equation (5) we add two more thresholds per task at probability 10-5. In particular, it is for 71 (C �? = 8 , 10-5), (C �� = 10,10-9), (C rI = 12,10-5) and (C H i = 14 10-9) . fi�r T (C LO = 5 1 0 -5) (C LO = 1(C H i = 11 10-5) and (C HI = 15 10-9) . fior T = 10 10-5) (C LO = 15 10-9) (C H i = 16 10-5)

Fig. 6 .

 6 Fig. 5. C-space+ representations.

c LO c 1 (

 1 C1(LO), C2 (LO) , ... , Cn(LO)) , (C1 (LO), C2 (LO) , ... Cn (HI)), CHI (C1 (HI) , C2 (HI), ... Cn(HI)). As a result, there exist multiple possible demand bound functions for the set of tasks depending on the WCET thresholds chosen: n dbf(t, c LO ) L dbfi (t, Ci (LO)), n -1 dbf(t,c 1 ) L dbfi (t, Ci (LO)) + dbfn(t, Cn(HI)) , i=l n dbf(t, cHi)

Example 3 .

 3 Given the probabilistic set of tasks (T1 ' T 2 , T 3 ) such that: T1 = ((C1 (LO) = 10,C1 (HI) = 14),40,40), T2 = (( C2 (LO) = 8, C2 (HI) = 15),50,50) and T3 = (( C3 (LO) = 15 , C3 (HI) = 20),40,40); time is expressed in CPU ticks. To the tasks model of Equation (5) we add two more thresholds per task at probability 10-5 . In particular, it is for T (C LO = 8 10-5 ) (C LO = 10 10-9 ) (CHI = 12 10-= 14, 10 -9 ); for T2 (c}? = 5, 10-5 ) , ( C } ~ = 8,10-9 ): (cJ1I = 11,10-5 ) and (cJ1J = 15 , 10 -9 ); f r T3 (C LO = 10 10-5 ) (CLO = 15 10--'9) (CHI = 16 10-5 ) = 20 , 10-9 ). In Figure 5( a) all the possible WCET thresholds combinations c from the input pWCETs are plotted. Schedulable c are distinguished from non schedulable ones. Horizontal planes are to distinguish safety levels (HIand LO) and WCET confidences (at 10-9 and 10 -5 per safety level).Figure 5(b) shows the feasibility region for the EDF schedulability. Figure 6 gives a better insight of the C-Space+ with 2D representations. Only the plane (T1' T2) is represented at two values of C3, respectively C3 = 15 and C3 = 20.

  Fig. 5. C-space+ representations.

Fig. 4 .

 4 Fig. 4. Discrete points represented with probabilities associated to each point.

Example 4 .

 4 sched investigation of the sensitivity analysis for the C-Space+. Given the task set of Example 3, Figure5(b) represents the feasibility region. Figure7depicts the C-Space+ with the distinction between HI-safe and Lo-safe WCETs for 73 represented with the two horizontal planes. Figure8provides two 2D planes where both probabilities and safety levels are represented for the couple (71,72) with both Lo-safety and HI safety WCET for 73.We first observe how the non-schedulability relates to HI safety WCETs, especially with C3 = 20. There are couples of non-schedulabilities, one with the Lo-safety 73, C3 = 15, e =[START_REF] Pathan | Fault-tolerant and real-time scheduling for mixed criticality systems[END_REF][START_REF] Wong | Schedulability analysis for the abort-and restart (ar) model[END_REF][START_REF] Wong | Schedulability analysis for the abort-and restart (ar) model[END_REF] and one with the HI-safety 73, C3 = 16 with probability 10-5 , e =[START_REF] Pathan | Fault-tolerant and real-time scheduling for mixed criticality systems[END_REF][START_REF] Wong | Schedulability analysis for the abort-and restart (ar) model[END_REF][START_REF] Guo | Edf schedulability analysis on mixed-criticality systems with permitted failure probability[END_REF].

(a) 20 20 Fig. 8 .

 20208 Fig. 8.2D representations with safety levels H I and LO to distinguish effects on schedulability. Some possible transitions from non-schedulability to schedulability are represented.

2 7.

 2 (b) we can see that, in order to restore task set schedulability and leaving 73 unchanged, either: both 71 and 72 change to the Lo-safety level, or only 71 changes to the Lo-safety level at probability 10-5 , or 72 has to change to the Lo-safety level. Each of the solutions has a dif f erent cost. For example, the first would have mean that for guaranteeing 73 schedulability with faults, both 71 and 72 can be guaranteed only without faults. With the second solution, it would have been possible guarantee 71 without faults and with a confidence ofl0-5 instead of 10-5 . The third solution instead, would have implied that only 72 would have been guaranteed without faults but with a confidence of 10-9 . In terms of confidence of the schedulable points, both the first solution and the third solution have associated a confidence of 10-The second solution instead has a confidence associated of 10-23 .

Fig. 7 .

 7 Fig. 7. C-Space+ with HI and LO safety levels of τ 3 represented. Some possible transitions from non-schedulability to schedulability are represented.

The scenario is an abstract concept which could embed system inputs, system configurations, etc .. Defined a scenario, the measurements under it are the execution times of the effects enclosed by the scenario.