Tom Fleming

Alan Burns
email: alan.burns@york.ac.uk

Utilising Asymmetric Parallelism in Multi-Core MCS Implemented via Cyclic Executives

Near future real-time systems are faced with the inevitability of multi-core architectures. Theoretically, multi-core architectures bring an increase in platform resources and speed, however, this comes at the cost of the predictability fundamental to real-time systems. With the increase in platform speed and resources comes the added pressure to incorporate more and more functionality into a common hardware platform. In this work we consider a Mixed Criticality (MC) approach applicable to all future, but particularly near future systems, which must support sequential high criticality code alongside less critical (perhaps parallelised) applications. We propose a simple design objective to reduce the number of cores high criticality work executes on, with the aim to increase the predictability of these applications by requiring verification over a fewer number of cores. We investigate how an increase in predictability might provide a reduction in Worst Case Execution Time and use Integer Linear Programming (ILP) to reduce the number of cores utilised by high criticality tasks as far as possible.

I. INTRODUCTION

It is becoming more and more evident that future and near future real-time systems will be required to execute on powerful multi-core hardware platforms. This requirement is born initially of necessity, as single-core architectures are being abandoned for multi-core, however, many are seeing the opportunity to utilise these powerful platforms to combine previously federated functionality. By integrating functionality onto the same hardware platform, inevitably, the situation arises where applications of differing levels of criticality must execute alongside each other. This poses the challenge of providing the suitable level of separation to the higher criticality work, such that it may be guaranteed that no lower criticality work may effect its execution. Providing such mechanisms is fundamental for the certification and validation of Mixed Criticality systems.

Complicating the matter further is the simple usage of multi-core platforms themselves. Typical real-time applications of a high level of criticality are, and have been for a long time, residents of the single-core/processor domain. The introduction of multiple cores brings problems such as interference between tasks, controlling memory access and inter-core communications to name a few. In addition to these issues, when considering a mixed criticality system, one must also ensure the sufficient isolation of criticality levels, such that non of the above factors may have impact from a lower to a higher criticality level. For example, a lower criticality application may not cause contention on the shared bus and adversely effect the execution of a higher criticality task such that its execution cannot be guaranteed within safe bounds. However, multi-core platforms promise improvement over previous single-core architectures. In addition to increased processing capacity, they offer improved power usage and thermal output due to lower individual clock speeds. Finally, they provide a platform amenable to parallelised applications which may benefit lower criticality work, particularly that involved in tasks such as run-time simulation and image processing.

With all these advantages and drawbacks in mind, we propose a design optimisation to, in some way, ease the transition from single-core to multi-core architectures. Our work is based on the well known Cyclic Executive paradigm [START_REF] Baker | The cyclic executive model and ada[END_REF] where a barrier protocol [START_REF] Giannopoulou | Scheduling of mixed-criticality applications on resourcesharing multicore systems[END_REF] is used to strictly separate the execution of differing levels of criticality. We utilise this separate notion of criticality level execution to pursue the goal of reducing the number of cores the highest criticality (HI) work may execute on. The aim being that with a reduction in the number of cores, simpler verification with fewer overheads will be available. We illustrate this optimisation and its impact with an example and provide experimental work investigating the reduction in the number of cores for high criticality work using synthetic task sets. This work aims to present the reasoning and advantages of reducing the number of cores for higher criticality level execution.

The remainder of this paper is structured as follows: Section II described the system model and reviews prior work on ILP, Section III presents and discusses the notion of limiting the number of cores for HI criticality execution, Section IV provides some insight via an example, Section V provides an evaluation and Section VI poses some concluding remarks.

II. THE SYSTEM MODEL

Throughout this work, we make reference to features of general systems and our mixed criticality cyclic executive model. This section will define and clarify the notation used.

While this work is applicable to mixed criticality applications with greater than two levels of criticality, we restrain ourselves to just two. We make use of the Mixed Criticality model proposed by Vestal [START_REF] Vestal | Preemptive scheduling of multi-criticality systems with varying degrees of execution time assurance[END_REF] with a minor alteration. In the standard model a task has a WCET value assigned for its own criticality level and all those below, we simply consider each task to only ever have two WCET values, one at its own criticality level and one at the lowest criticality level in the system. In general, we define a standard mixed criticality (dual criticality) task set as τ i = {C i (LO), C i (HI), T i , D i , L i }, where C i (LO) is the Worst Case Execution Time (WCET) of a task in the LO criticality mode, C i (HI) is the WCET of a task in the HI criticality mode, T i is the period, D i is the deadline and L i is the criticality level.

When discussing the Mixed Criticality Cyclic Executive we define T M as the major cycle length. This major cycle is comprised of a number of minor cycles T F . The minor cycles execute in order during each major cycle while the major cycle repeats cyclically upon completion of the previous cycle. Figure 1 shows an example set-up of 4 minor cycles within a major cycle.

T M T F T F T F T F
Fig. 1. The Cyclic Executive Structure.

In addition to the somewhat standard CE practice described above, we utilise a barrier mechanism [START_REF] Giannopoulou | Scheduling of mixed-criticality applications on resourcesharing multicore systems[END_REF] to account for mixed criticality workloads. The barrier completely separates the execution of criticality levels across all cores during a given minor cycle. Thus at runtime: HI criticality work is executed first (up to their C(LO) values), once all HI work has completed on all CPU cores the barrier is triggered, this releases LO criticality work for execution. A criticality change occurs when all HI work, executing to their C(LO) predictions, has not completed by the predicted LO invocation of the barrier. In this situation, HI criticality work may execute up until its C(HI). Be this as it may, in reality, the barrier protocol occurs when HI work has completed, regardless of whether it is before or after a criticality change. It provides a level of dynamic behaviour such that we do not discuss the dropping of low criticality tasks, but due to the statically ordered nature of the cyclic executive, in the worst case, they would simply not execute. Finally, if a criticality change does occur, the criticality level of the system may be reduced at the start of the next major cycle.

Integer Linear Programming is used in this work to solve our allocation problem. We will briefly review the construction of a standard ILP model as presented in [START_REF] Fleming | Investigating mixed criticality cyclic executive schedule generation[END_REF], extensions to allow for task splitting are presented in [START_REF] Fleming | Improving the schedulability of mixed criticality cyclic executives via limited task splitting[END_REF] but are omitted from this work. We will describe how the model is constructed based on the .lp (intended to be more user readable) format provided by the Gurobi [START_REF]Gurobi Optimization[END_REF] LP solver 1 .

Fundamental to our ILP models is the representation of possible task locations as binary variables, these are defined in the following format:

1 For a more detailed overview see [START_REF] Fleming | Investigating mixed criticality cyclic executive schedule generation[END_REF]

& [3] • T [taskN umber] [core][minorCycle]
For a dual criticality system the model is structured in the following way: -Maximise/Minimise: The first section contains the objective function, in the case of our standard ILP model this is left blank as we only seek to establish feasibility.

-Constraints: Arguably the largest and most significant section, the constraints in our ILP models are split broadly in two.

• Group One: The first group ensures that tasks are allocated correctly based on their periods. In a system with four minor cycles per major cycle, a task, τ i , where T i = T F , would require the following constraints:

T i 11 + T i 21 = 1 T i 12 + T i 22 = 1 T i 13 + T i 23 = 1 T i 14 + T i 24 = 1
However, if T i = T M the constraint would be:

T i 11 + T i 21 + T i 12 + T i 22 + T i 13 + T i 23 + T i 14 + T i 24 = 1
• Group Two: The constraints in group two seek to ensure that any allocation is also schedulable. The WCETs are used in conjunction with the location variables to check feasibility. If a task is allocated to a location, the variable will be set to 1 and thus the relevant WCET is included. In a dual criticality system, this is achieved in three stages: Stage One: Ensure the schedulability of the HI criticality tasks using their C(HI) values. For HI criticality tasks τ i and τ l :

C i (HI) × T i 11 + C l (HI) × T l 11 ≤ T F C i (HI) × T i 21 + C l (HI) × T l 21 ≤ T F
Stage Two: Ensure the schedulability of the HI tasks executing to their C(LO) estimates. In addition, an X variable in included to represent the spare capacity available for LO criticality tasks to execute. The same X variable is used across all cores during any given minor cycle, providing a means of modelling the barrier protocol. For the same HI criticality tasks τ i and τ l :

C i (LO) × T i 11 + C l (LO) × T l 11 + X 1 ≤ T F C i (LO) × T i 21 + C l (LO) × T l 21 + X 1 ≤ T F
Stage Three: Ensure the scheduability of the LO criticality tasks. This must ensure that their C(LO) values fit within the relevant X variable for each minor cycle. Given two LO criticality tasks τ z and τ x :

C z (LO) × T z 11 + C x (LO) × T x 11 -X 1 ≤ 0 C z (LO) × T z 21 + C x (LO) × T x 21 -X 1 ≤ 0
-Bounds: This section simply states the upper and lower bounds placed on our variables. As all but the X variables are integers, only they are bounded to be 0 ≤ X ≤ T F .

-Variable Types: Finally, the last section is where variable types are declared, all but the X variables are declared as binaries.

III. REDUCING THE NUMBER OF CORES USED IN HI CRITICALITY EXECUTION

The general scheduling of real-time task sets on multi-core platforms is a challenging topic. Many COTS (Consumer Off The Shelf) hardware platforms contain ambiguous and often poorly document features which do not facilitate real-time software. Often these hardware platforms are designed with the average case in mind, rather than the worst case. Knowledge of execution and performance is fundamental to real-time system design, as without verification and certification, such software is not fit for purpose. An important part of this problem, is that verification becomes more difficult as the number of cores in use is increased. Often this leads to an increased level of pessimism in WCET predictions as increasingly large margins are added for safety, due to the unpredictable nature of the platform.

When Mixed Criticality is added to the issue, a balance is required between pessimism for safety, but effective use of the, new, larger, multi-core platform. While higher criticality work seeks to maintain the same guarantees of timeliness as it did in the single-core era, new lower criticality applications are able to make use of the multi-core architecture. Coupled with these conflicting requirements is the necessity to support legacy code, designed for single-core sequential execution. The development of software is expensive, companies often utilise legacy and even commercial code to fulfil the needs of the system. As such platforms treat these applications in a black box fashion, in this situation re-design for a more parallel architecture isn't possible.

In order to, at least partially, deal with this issue we propose a simple design goal. Given a multi-core computing platform, the number of cores that any higher criticality work is executing upon should be reduced to the minimum possible. We consider this goal in relation to our Mixed Criticality Cyclic Executive model where work of differing criticality levels is temporally separated, thus removing the chance for lower criticality levels to interfere in some way with the execution of higher levels. We envisage a scenario where HI criticality work executes first, on a very small number of cores (perhaps only one or two), the remaining LO criticality work is then allowed to execute using the complete system resources (4,8,16 cores). Such a situation allows both the safety critical sequential (legacy) HI criticality code to execute alongside LO criticality, perhaps highly parallelised code designed for new multi-core platforms.

In short, the advantages of such an approach are twofold. Firstly, with a reduction in the number of cores used for HI criticality work, we increase the predictability in its execution. The increase is due to, in essence, reducing the number of factors that must be considered during analysis, and thus increasing the ease in which the performance of a system may be understood. Secondly, as a result of the first point, we are able to provide a reduction in the WCET estimates for HI criticality tasks. The WCETs may be reduced as a direct result of the increase in predictability.

While it is difficult to reason about exactly how much more difficult analysis becomes as additional cores are included at the HI criticality level, we may make an assumption in order to illustrate how reducing the number of cores used by the HI criticality work is beneficial to the system as a whole. To this end, one might assume that, perhaps optimistically, for every core which does not execute any HI criticality tasks, all HI criticality tasks have their WCETs reduced by 10%. This serves the purpose of simulating the increase in predictability and accuracy of the analysis and therefore the reduction in pessimism required for verifiably safe WCETs.

To satisfy the requirements described above our model must implement two key features.

1) We must provide an optimisation to reduce the number of cores HI criticality work is executing on as far as possible. 2) We model the improved analysability of a task by reducing its WCET by 10% for each core not executing HI criticality work. To achieve these goals we first define a variable for each core in the system to represent whether HI criticality work is allocated. The variable P z , where z is the core, is a binary variable which is set equal to 1 if no HI criticality work is allocated and 0 if HI criticality work is allocated. As such our optimisation goal is simply to maximise P, and thus reduce the number of cores HI criticality work is executing on as much as possible.

To model the 10% reduction in WCET for each core unused by HI criticality work we must modify the binary variables used to represent HI criticality tasks. These variables become Integers, for example 0 ≤ T i 11 ≤ 10, they must be less than or equal to 10 and greater than or equal to 0. Setting a variable to 0 still indicates that the task is not scheduled in that location, however a positive value now indicates that a task is allocated to that location. A value of 10 indicates that all cores in the system are used to execute HI criticality work, whereas a value of 9 indicates one core does not execute any HI criticality tasks.

As a scheduled task has a value from 1 to 10, when including the task in the WCET constraints we multiply the variable by the WCET / 10. As such if all cores are used for HI criticality tasks, and the variable is equal to 10, then 10 × W CET /10 will include the full WCET with no reduction. However if one core is unused by HI criticality work, the variable will equal 9, thus 9 × W CET /10 models a 10% reduction in WCET as a result. The WCET constraint for T i 11 was:

C i (HI) × T i 11 It now becomes: C i (HI) 10 × T i 11
An additional constraint ensures that for each core unused by HI criticality tasks, the location variable is reduced by 1.

Consider the HI criticality task τ i and two processor variables

P 1 & P 2 . T i 11 + T i 21 + P 1 + P 2 = 10
The task is scheduled in one of the two variables (T i 11&T i 21). As the constraint must equal 10, the variable will be reduced, from 10, by the number of processors with no HI criticality execution. Thus if P 1 = 1 (no HI criticality execution on core 1) and P 2 = 0 (HI criticality execution is present on core 2) then the variable containing the task location must equal 9. As such, 90% of the task is included in the WCET constraints, modelling a 10% reduction.

The optimisation is driven by a set of constraints which only allow P z to be set to 1 if no HI criticality work is allocated to that core. An example of this is shown for core 1.

T i 11 + T i 12 + T i 13 + T i 14+
T l 11 + T l 12 + T l 13 + T l 14 + 80 × P 1 ≤ 80 ...

Here the HI criticality variables which represent possible locations for tasks τ i & τ l as summed with 80 × P z . If any location contains a HI criticality task, P z may not be set equal to 1, thus indicating that HI criticality work is present on that core. The value 80, used to both multiply P z and constrain the inequality is calculated by multiplying the number of location variables in the constraint ×10. Thus ensuring that even if tasks are located in every variable, the constraint is still satisfied, but P z may only equal 1 if no HI criticality work is allocated on that core.

We will briefly go over the changes to each section of the constraints.

-Periodicity Constraints

The changes to these constraints are perhaps the most significant in structure. As the original variables were binaries, adjusting the constraints for our integer location variables required a re-work. We make use of a familiar trick, where a task + a binary variable ×10 is constraint to be less than or equal to 10. We introduce a number of B variables to facilitate this. Given two task locations:

T i 11 T i 21
We define two constraints:

T i 11 + 10 × B 1 ≤ 10 T i 21 + 10 × B 2 ≤ 10
We require this task to be scheduled in one of the two variables, thus we constrain the B variables:

B 1 + B 2 = 1
The sum of the B variables is required to equal 1, thus one task variable must contain no execution to allow for the B variable to equal 1. The actual value the task variable takes is controlled in a later constraint, but if it is allocated to that location the variable will be greater than or equal to 1. The complete set of constraints for a task where T i = T F as as follows:

T i 11 + 10 × B 1 ≤ 10 T i 21 + 10 × B 2 ≤ 10 T i 12 + 10 × B 3 ≤ 10 T i 22 + 10 × B 4 ≤ 10 T i 13 + 10 × B 5 ≤ 10 T i 23 + 10 × B 6 ≤ 10 T i 14 + 10 × B 7 ≤ 10 T i 24 + 10 × B 8 ≤ 10 B 1 + B 2 = 1 B 3 + B 4 = 1 B 5 + B 6 = 1 B 7 + B 8 = 1 -WCET Constraints
The constraints which use the WCET values of each task to ensure scheduability must simply be altered to include the WCET / 10 for each HI criticality task. This is required for both stage one (HI WCET):

C i (HI) 10 × T i 11 + C l (HI) 10 × T l 11 ≤ T F C i (HI) 10 × T i 21 + C l (HI) 10 × T l 21 ≤ T F
And for stage two (LO WCETs of HI criticality tasks):

C i (LO) 10 × T i 11 + C l (LO) 10 × T l 11 + X 1 ≤ T F C i (LO) 10 × T i 21 + C l (LO) 10 × T l 21 + X 1 ≤ T F

-Additional constraints

Additional constraints are added firstly to ensure the P z variables correctly represent which cores are executing HI criticality tasks. The complete set of constraints are shown for τ i and τ l on two cores:

T i 11 + T i 12 + T i 13 + T i 14+
T l 11 + T l 12 + T l 13 + T l 14 + 80 × P 1 ≤ 80

T i 21 + T i 22 + T i 23 + T i 24+ T l 21 + T l 22 + T l 23 + T l 24 + 80 × P 2 ≤ 80
Finally constraints are included to reduce the value in the location variable for each core HI criticality work is not allocated to. These constraints are show for τ i where T i = T M :

T i 11 + T i 21 + T i 12 + T i 22+ T i 13 + T i 23 + T i 14 + T i 24 + P 1 + P 2 = 10
And where T i = T F : T i 11 + T i 21 + P 1 + P 2 = 10 T i 12 + T i 22 + P 1 + P 2 = 10 T i 13 + T i 23 + P 1 + P 2 = 10 T i 14 + T i 24 + P 1 + P 2 = 10 Finally it should be noted that, while these constraints and variables have changed for HI criticality tasks, the variables and constraints of LO criticality tasks have not changed. LO criticality tasks still make use of binary variables to indicate their location.

IV. EXAMPLE

In this section we will describe the process in more detail using our Mixed Criticality Cyclic Executive model. We will make use of an example set of tasks, and illustrate through example schedules how the design optimisation might work. The ILP model from [START_REF] Fleming | Investigating mixed criticality cyclic executive schedule generation[END_REF] will be used as a base to allow for the optimisation.

The task set shown in Table I will be used as our example. This task set contains 10 tasks, 5 of HI criticality and 5 of LO. Initially, we seek any acceptable schedule of the task set on a 3 core platform with 4 minor cycles. Each minor cycle has a length of 25 (T F = 25) and the major cycle has a length of 100 (T M = 100). An ILP model is produced to solve this problem and ascertain the initial feasible solution. The resulting non-optimised schedule is shown in Figure 2.

With the dashed vertical line within each minor cycle representing the last possible time at which the barrier switches from the HI to LO work without triggering a criticality change, it is clear that the HI criticality work is spread across all cores during each minor cycle. In addition, it is also apparent that there is a significant amount of free capacity in LO mode (to the right of the barrier). By optimising the schedule the aim would be to use this spare capacity to reduce the number of cores HI criticality work is scheduled upon.

Figure 3 shows the results of such an optimisation. This solution restricts HI criticality work to cores 2 and 3 while after the barrier protocol, LO tasks are able to utilise all cores, particularly during minor cycles 2 and 4 where the additional core is required to schedule τ 9 . Thus our optimisation was able to reduce the number of cores used by HI criticality work from 3 to 2.

V. EVALUATION

This evaluation aims to provide a broad picture as to the performance of our scheme using ILP. The setup for the evaluation is as follows:

• Each task set contained 20 tasks.

• The target platform has 4 cores.

• Task utilisation were generated using UUniFast [START_REF] Bini | Measuring the performance of schedulability tests[END_REF] providing an unbiased distribution of utilisation values. • Task periods were randomly selected from 25, 50 and 100 (as T F = 25 & T M = 100). • Deadlines were set equal to periods. D i = T i .

• The execution time of a task must account for criticality, as such: C i (L i ) = U i /T i • For all but the execution time of the task at its own criticality level, execution times were determined by 4 are a standard plot of schedulability (eg. Number or % of scheduleable task sets) as the utilisation of the generated task sets is increased. The x axis continues to 400% utilisation as the system contains 4 cores. This plot illustrates that the ability to reduce the pessimism in the WCET predictions does provide a small improvement to schedulability. Fig. 3. An allocation, optimised to minimise the number of cores for HI criticality tasks.

C i (L v ) = C i (L i ) *

VI. CONCLUSION

In conclusion, in this work we have put forward the notion of reducing the number of cores work at the HI criticality level execute upon. We reason about the desire to support the conflicting requirements of sequential (legacy) and parallised code, and argue that by reducing the number of cores, the level of pessimism and difficulty in analysing HI criticality tasks can be reduced. We propose a model which provides a 10% reduction in HI criticality task's WCET for each core not used by HI criticality tasks. This was illustrated through the use of an example set of tasks, showing how in our cyclic executive system an allocation may be optimised to this end. Finally, we used experimental data to illustrate how reducing the WCET, in line with a reduced number of cores used for HI criticality execution, provides an increase in overall schedulability.

Fig. 4 .

 4 Fig. 4. A standard schedulability plot illustrating the difference between the optimised and non-optimised ILP models..

Figure 5

 5 Figure 5 illustrates the average number of cores used by HI criticality work (Y axis) as the utilisation is increased. The results show that the non-optimised ILP implementation very quickly uses all 4 cores to schedule its HI criticality work, whereas the optimised ILP model increases more gradually as the utilisation of the task sets is increased.

Fig. 5 .

 5 Fig. 5. A plot showing the average number of cores used by HI criticality tasks at each given utilisation.

  CF CF is the criticality factor, a random variable between X and Y.• Criticality levels within each task set were evenly distributed. • A reduction in WCET of 10% per core HI criticality work does not execute on is included to simulate a decrease in pessimism when fewer cores are used. The results shown in Figure

  Fig.2. A standard (non-optimised) schedule of the task set in TableI.

	NO OPT			S max (1)		S max (2)			S max (3)					S max (4)
	Core 1	t 3	t 4		t 8	t 1	t 3	t 7	t 10		t 2	t 6	t 8	t 9	t 2	t 3	t 6	t 7
	Core 2	t 2	t 5		t 7	t 2		t 6	t 9		t 1	t 7			t 8
		t 1			t 6			t 8			t 3				t 1	t 4
			T F
	OPT		S max (1)				S max (2)				S max (3)			S max (4)
	Core 1								t 9								t 9
	Core 2	t 1	t 2	t 6	t 7	t 1	t 2	t 3	t 6	t 8	t 2	t 3	t 6	t 8	t 1	t 3	t 7	t 10
		t 3	t 4	t 8			t 5		t 7		t 1	t 4	t 7		t 2		t 6	t 8
			T F

ACKNOWLEDGEMENTS

The authors acknowledges the support and funding provided for this work by BAE Systems, and the ESPRC (UK) via MCC & MCCps grants.


Stefan Draskovic

Pengcheng Huang

Lothar Thiele

On the Safety of Mixed-Criticality Scheduling

A common assumption for scheduling mixedcriticality systems is the degradation of less critical tasks when the system is in the emergency mode; which is entered when critical tasks overrun their expected WCET. In the meanwhile, common safety standards enforce strict safety requirements on all criticality levels. However, the impact of degrading less critical tasks on the overall system safety is not well understood. By introducing probabilistic distributions of task execution times, we show in this paper a first analysis of safety of mixed-criticality systems. Inspired by standards, we provide the probability-offailure-per-hour (PFH) of a system when no overrun is detected. We also introduce and analyze the expected mode switching time, which describes how often emergency mode is entered. Our results reveal a fundamental trade-off between these two values. Finally, we discuss other possible safety measures that form a complete overview of a system's safety.

I. INTRODUCTION

Today, mixed-criticality is becoming a significant trend for many major industries including automotive and avionics [START_REF] Burns | Mixed criticality systems-a review[END_REF], where applications of different safety criticality levels are consolidated into a common computing platform to reduce cost, weight, and energy [START_REF] Trujillo | European project cluster on mixed-criticality systems[END_REF]. In the meanwhile, the design process of mixed-criticality systems is often regulated by industrial safety standards (see e.g. DO-178C [START_REF]Rtca/do-178c, software considerations in airborne systems and equipment certification[END_REF] and ISO 26262 [START_REF]ISO 26262, Road Vehicles -Functional Safety[END_REF]), with the ultimate goal to meet different safety requirements on all criticality levels. To achieve this, a common safety measure, probability-of-failure-per-hour (PFH), is often suggested. For certification, it is required by the safety standards that different PFHs must be met on different criticality levels. In addition, criticality segregation is often suggested in safety standards as "best practice" towards ensuring system safety.

While traditional industrial practice favors static temporal and spatial isolation for mixed-criticality systems [START_REF]Rtca/do-178c, software considerations in airborne systems and equipment certification[END_REF], [START_REF]ISO 26262, Road Vehicles -Functional Safety[END_REF], [START_REF] Tȃmas ¸-Selicean | Design optimization of mixed-criticality real-time embedded systems[END_REF], a significant recent trend is to enforce dynamic and asymmetric isolation among different criticality levels [START_REF] Giannopoulou | Scheduling of mixed-criticality applications on resource-sharing multicore systems[END_REF], [START_REF] Burns | Mixed criticality systems-a review[END_REF]. This means having several possible modes of operation for the system, among which one is chosen based on decisions made at runtime. The system starts in normal mode, and stays in it as long as there are no execution time overruns. In this mode, all tasks are guaranteed to meet their real-time requirements. If any task overruns its expected WCET, then the system switches to an emergency mode, where less critical tasks are given degraded service in order to free system resources for critical tasks. There can be several emergency modes, depending on which criticality levels are degraded. In the general case, there are as many modes of operation as criticality levels. A plethora of scheduling policies have been proposed based on this model [START_REF] Burns | Mixed criticality systems-a review[END_REF] for both single-core and multi-cores -fixed-priority scheduling [START_REF] Baruah | Response-time analysis for mixed criticality systems[END_REF], [START_REF] Vestal | Preemptive scheduling of multi-criticality systems with varying degrees of execution time assurance[END_REF], earliest deadline first scheduling [START_REF] Baruah | Mixed-criticality scheduling of sporadic task systems[END_REF], [START_REF] Park | Dynamic scheduling algorithm and its schedulability analysis for certifiable dual-criticality systems[END_REF], [START_REF] Ekberg | Bounding and shaping the demand of mixedcriticality sporadic tasks[END_REF], [START_REF] Huang | Service adaptions for mixed-criticality systems[END_REF] and time-triggered scheduling [START_REF] Baruah | Certification-cognizant time-triggered scheduling of mixed-criticality systems[END_REF], [START_REF] Giannopoulou | Scheduling of mixed-criticality applications on resource-sharing multicore systems[END_REF], [START_REF] Huang | An isolation scheduling model for multicores[END_REF]. Furthermore, the scheduling techniques are extended to consider fault-tolerance [START_REF] Saraswat | Task migration for faulttolerance in mixed-criticality embedded systems[END_REF], [START_REF] Islam | Dependability driven integration of mixed criticality sw components[END_REF], [START_REF] Pathan | Fault-tolerant and real-time scheduling for mixedcriticality systems[END_REF], [START_REF] Kang | Reliability-aware mapping optimization of multi-core systems with mixed-criticality[END_REF], energy-conservation [START_REF] Legout | Mixed-criticality multiprocessor real-time systems: Energy consumption vs deadline misses[END_REF], [START_REF] Wognsen | Battery-aware scheduling of mixed criticality systems[END_REF], resource interference [START_REF] Giannopoulou | Mixed-criticality scheduling on cluster-based manycores with shared communication and storage resources[END_REF], [START_REF] Yun | Memory access control in multiprocessor for real-time systems with mixed criticality[END_REF], etc.

We observe that safety quantification of mixed-criticality scheduling techniques remains largely unexplored in the stateof-the-art [START_REF] Burns | Mixed criticality systems-a review[END_REF], despite its importance from the certification's point of view. On the one hand, system resource efficiencies can be improved by enforcing asymmetric isolation among different criticality levels [START_REF] Burns | Mixed criticality systems-a review[END_REF], since resources can be "shifted" to more critical tasks when they execute in emergency mode. On the other hand, degrading less critical tasks (dropping them in the extreme case [START_REF] Baruah | Mixed-criticality scheduling of sporadic task systems[END_REF], [START_REF] Park | Dynamic scheduling algorithm and its schedulability analysis for certifiable dual-criticality systems[END_REF], [START_REF] Ekberg | Bounding and shaping the demand of mixedcriticality sporadic tasks[END_REF], [START_REF] Baruah | Certification-cognizant time-triggered scheduling of mixed-criticality systems[END_REF], [START_REF] Giannopoulou | Scheduling of mixed-criticality applications on resource-sharing multicore systems[END_REF], [START_REF] Huang | An isolation scheduling model for multicores[END_REF]) would naturally affect the safety of those tasks; this dependency needs to be understood and bounded in order to meet safety (PFH) requirements on all criticality levels, as required by existing safety standards [START_REF]Rtca/do-178c, software considerations in airborne systems and equipment certification[END_REF], [START_REF]ISO 26262, Road Vehicles -Functional Safety[END_REF]. Existing work either focus on deadline missing probabilities of individual tasks [START_REF] Masrur | A probabilistic scheduling framework for mixed-criticality systems[END_REF], [START_REF] Santinelli | Probabilities and mixed-criticalities: the probabilistic c-space[END_REF] or implicitly address system safety [START_REF] Guo | Edf schedulability analysis on mixed-criticality systems with permitted failure probability[END_REF].

In light of this, we strive in this paper to answer the following question: How safe is each criticality level for a mixed-criticality system?

A. Contribution and Organization

As a step to answer the above question, we assume fixed-priority scheduling and dynamic mode-switched dualcriticality systems. Our contributions are as follows.

• A new probabilistic mixed-criticality system model is introduced in Section II. It features a normal and an emergency mode of operation, and the system choses one based on run-time events. • For this model, we propose several safety metrics. These are the mode independent PFH (in Section II), the PFH inside normal and inside emergency mode (see Section III), and the expected mode switch time (Section IV). • An analysis that produces the PFH in normal mode is given in Section III. It is based on the steady state analysis, presented in [START_REF] Díaz | Stochastic analysis of periodic real-time systems[END_REF]. A way to safely use this analysis for our problem is proven, and it is extended to produce the PFH in normal mode. • The expected mode switch time is calculated in Section IV. It is derived from execution time thresholds of higher criticality tasks. A fundamental trade-off, between normal mode safety and expected mode switch time, is presented and discussed in Section V.

• Experimental results in Section VI illustrate the PFH in normal mode and the expected mode switch time, with the trade-off between these two clearly visible.

II. SYSTEM MODEL

We consider a mixed-criticality system with two criticality levels, scheduled using fixed-priority on a preemptive unicore. The criticality levels are denoted HI (high criticality) and LO (low criticality). The PFHs of criticality levels (PFH HI and PFH LO ) are drawn from the five criticality levels in DO-178C [START_REF]Rtca/do-178c, software considerations in airborne systems and equipment certification[END_REF]. The values 10 -7 and 10 -5 can be used as an example.

We assume a periodic task set τ , and each instance of a task is called a job. Task τ i is characterized by its criticality χ i ∈ {HI, LO}, period T i , initial arrival phase φ i , worst-case execution time (WCET) C i , and deadline D i . We define the hyper-period (HP) as the least common multiple of all task periods.

In a conventional model [START_REF] Burns | Mixed criticality systems-a review[END_REF], [START_REF] Vestal | Preemptive scheduling of multi-criticality systems with varying degrees of execution time assurance[END_REF], tasks in a dual-criticality system can have two levels of WCETs. While in the normal system mode, all tasks are guaranteed to meet their deadlines adhering to their LO level WCETs (C i (LO), ∀τ i ). If any HI criticality task overruns its LO level WCET, then the system switches to emergency mode. In this mode, all HI tasks are guaranteed with a more pessimistic WCETs (C i (HI), ∀τ i ∈ τ HI ). In emergency mode LO criticality tasks are guaranteed with reduced service. As an example, reduced service could imply less in precision. LO criticality tasks are not allowed to overrun C i (LO).

In an attempt to match theoretical insights with applicable safety standards, we now introduce a probabilistic mixedcriticality task model. In this model we augument the WCETs model by making execution times independent random variables C i , ∀τ , whose probability distributions are known. Well established methods like static or measurement based probabilistic timing analysis techniques already exist to derive safe estimations of task execution time distributions, see [START_REF] Orshansky | A general probabilistic framework for worst case timing analysis[END_REF], [START_REF] Cucu-Grosjean | Measurement-based probabilistic timing analysis for multi-path programs[END_REF], [START_REF] Devgan | Block-based static timing analysis with uncertainty[END_REF], [START_REF] Malik | Static timing analysis of embedded software[END_REF]. For computational reasons, we assume a discrete distribution of task execution times.

Similar to the conventional model, we assume a normal and an emergency system mode. The system starts in normal mode and switches to emergency mode when any HI criticality task overruns an execution time threshold θ i . LO criticality tasks are not allowed to exceed their execution thresholds, thus when the threshold is reached they are killed. In emergency mode, more resources are provided to HI tasks, at the expense of LO tasks -LO criticality tasks could be completely dropped [START_REF] Baruah | Mixed-criticality scheduling of sporadic task systems[END_REF], [START_REF] Park | Dynamic scheduling algorithm and its schedulability analysis for certifiable dual-criticality systems[END_REF], [START_REF] Ekberg | Bounding and shaping the demand of mixedcriticality sporadic tasks[END_REF], their service could be degraded with longer activation periods [START_REF] Huang | Service adaptions for mixed-criticality systems[END_REF], [START_REF] Giannopoulou | Scheduling of mixed-criticality applications on resource-sharing multicore systems[END_REF], or they can be served as background tasks by lowering their priorities. We provide general safety analysis techniques considering all of these cases.

Once in emergency mode, the system could either stay in that mode forever, or switch back to normal mode when the system is idle [START_REF] Burns | Mixed criticality systems-a review[END_REF], i.e. when there are no jobs executing or waiting to be executed. We shall assume the later case, the argument being, that degrading a criticality level indefinitely A value used often in this paper is the backlog. A backlog b λ,i is a random variable, describing how much more execution time is needed at time λ to finish old jobs of priority i and higher. Backlogs are important because they determine when an arriving job can start its execution.

A. Notations on Probabilities

It is useful to introduce some notations that will be used, as well as a relation for ordering random variables.

1) Discrete PDFs: We deal with discrete non-negative random variables in this paper, the probability distributions of which are modeled with probability density functions (PDFs). Formally, for a random variable x and its probability density function p x (•), it follows that u p x (u) = 1 as u runs through the set of all possible values of x. Without loss of generality, we assume that the possible values of a random discrete variable x span the entire range of natural numbers, where p x (u) = 0 if x can not take the value u. For notational convenience, we omit the random variable in our notation if it is irrelevant in the context. All probability distributions are density functions unless otherwise stated. Note that we alternate between function representation of a probability density function p(•) and its vector representation

[p(0), p(1), • • • , p(u), • • • ] T whenever it is convenient.
2) Comparison of PDFs: Let us define a relation q p, that is used to compare any two probability distributions p and q. With this relation, we say that p is greater or equal to q, if the sum from any arbitrary value l onward, is greater or equal for p than for q. Mathematically this is noted as in [START_REF] Burns | Mixed criticality systems-a review[END_REF]. Note that probability densities can be incomparable.

∀l : ∞ u=l q(u) ≤ ∞ u=l p(u) ⇔ q p (1)
3) Limiting PDFs: By limiting a probability distribution with a threshold θ, we find a conditional probability distribution, where values above the threshold θ are not allowed. This new probability distribution is calculated as in (2).

p(x|x ≤ θ) = p(x, x ≤ θ) p(x ≤ θ) = p(x) p(x≤θ) x ≤ θ 0 x > θ (2)
We can see that this conditional distribution retains the same shape but is scaled up before the threshold, and is equal to zero afterwards. This operation is illustrated in Figure 1, where p 2 is the limit of p 1 with the threshold θ.

4) Convolution of PDFs: The well known convolution operation [START_REF] Díaz | Stochastic analysis of periodic real-time systems[END_REF] defines the addition of independent random variables. For some discrete probability distributions p and q, it is defined as in [START_REF]Rtca/do-178c, software considerations in airborne systems and equipment certification[END_REF].

(p ⊕ q)(i) = i u=0 p(u) • q(i -u) = i u=0 p(i -u) • q(u) (3)
(i) = m j=0 p(j) i = 0 p(i + m) i > 0 (4)
We now use a minimal example to show the usage of the convolution and shrinking functions in analyzing real-time systems with probabilistic execution times.

Example 1. Let us consider the example shown in Figure 2. Two tasks τ 1 and τ 2 are scheduled via fixed-priority (τ 2 has higher priority), with task parameters also as shown in the figure . Their presented execution times are already limited by thresholds, p τi = p τifull (x|x ≤ θ i ), where p τifull are the execution times with no limiting thresholds. τ 1 starts its execution with no backlog at time 0. At time 4, we get the backlog w 1 = shrink(p τi , 4). Intuitively, we see that this operation shifts the execution time distribution of τ 1 to the left by 4 time units. In addition, τ 2 is arriving at 4 and will preempt the execution of τ 1 . For τ 2 , it can be seen that its deadline miss probability is zero as it will finish before time 8 for both possible execution times. However, to get the failure probability of τ 1 , we need to consider the interference from τ 2 . This can be done by applying the convolution operation at time 4 to get the total backlog at this time: w 2 = w 1 ⊕ p τ2 . From our derivation as shown in Figure 2 (b), τ 2 has a deadline miss probability of 0.03. Likewise, one could extend this analysis to arbitrary tasks under deterministic scheduling policies.

III. PLAIN SAFETY ANALYSIS

In this section, we explain how to derive the probability-offailure-per-hour (PFH) of a criticality level χ inside a single mode of operation M, PFH M χ , with the assumption that the initial conditions, as well as the priority assignments and limiting thresholds, are known. It will be shown that this method can be applied to find the PFH when normal mode operation is assumed, noted as PFH N χ . Deriving the PFH directly, as in Example 1, is computationally prohibitive, as there could be millions of jobs inside an hour. An alternative, safe, analysis is presented, which focuses on one hyper-period, and extrapolates the results to find the probability of failure inside an interval of any length. The analysis presented here is built upon the seminal work Stochastic Analysis of Periodic Real-Time Systems [START_REF] Díaz | Stochastic analysis of periodic real-time systems[END_REF]. There, a single-mode system model is assumed. [START_REF] Díaz | Stochastic analysis of periodic real-time systems[END_REF] concludes that task deadline miss probabilities for every job inside a hyper-period converge, to a steady state value, as more hyperperiods are executed. The same is true for backlogs at specific times inside the hyper-period. In this work, we augment Our paper contributes by investigating when it is safe to use the steady state analysis to obtain safe PFH values, as required by safety standards.

Steady state deadline miss probabilities are obtained by first taking the steady state backlog at the beginning of a hyperperiod, and then analyzing the execution of jobs inside the hyper-period when this backlog is present.

An important question is whether the steady state backlog exists in a given system. The existence of such a backlog is shown to relate to the system utilization, i.e. the ratio of time that the system is busy processing jobs. Using results from queuing theory, it has been proven that if the average system utilization is less than one, a steady state exists [START_REF] Díaz | Stochastic analysis of periodic real-time systems[END_REF]. If the average utilization is greater than or equal to one, the steady state backlog is infinitely large, essentially making system safety guarantees impossible. Therefore, we focus on the case when a steady state exists.

However, we cannot use the steady state backlog for obtaining failure rates directly, as it is not known whether the steady state can be safely used to bound task deadline miss probabilities. In fact, deadline miss probabilities depend on the initial backlog, as stated in the following theorem.

Theorem 1. Let {b n } be a sequence of backlogs, where b n is the backlog present at the beginning of hyper-period n. The sequence

{b n } is monotone in the sense that, if b 0 b 1 , then b n+1 b n+2 , ∀n ∈ N 0 , or if b 0 b 1 , then b n+1 b n+2 , ∀n ∈ N 0 .
The proof is omitted here due to lack of space, but can be found in our technical report [START_REF] Draskovic | On the safety of mixed-criticality scheduling[END_REF]. If the initial backlog at the start of operation in this mode is b 0 , and the steady state backlog is π, then we present the following conclusions.

• If b 0 π, then the steady state deadline miss probabilities are the worst possible in the system, and they can be used to obtain safe failure rates. • If b 0 π, then the deadline miss probabilities found in the first hyper-period are the worst in the system, and they can be used to find failure rates.

• If b 0 and π are neither comparable w.r.t.

nor , we need to find a third probability density q, such that b 0 q and π q, and use this as a backlog in order to get safe failure rates. This value can be calculated as

∞ u=l q(u) = max ( ∞ u=l b 0 (u), ∞ u=l π(u)).
Note, a non-zero initial backlog is unusual at the start of a system, but can happen after a mode switch.

A. Failure Rates

As we know which backlog to use at a hyper-period's beginning, we can continue to determine the PFH M χ . This is done firstly by calculating the deadline miss probability of every job of this hyper-period, and then aggregating these values into the probability of failure inside an interval of arbitrary length.

The detailed procedure for obtaining deadline miss probabilities of jobs is presented in [START_REF] Díaz | Stochastic analysis of periodic real-time systems[END_REF]. It is in the same manner as Example 1, where convolutions and shrinking functions are used to determine when individual jobs will finish their execution.

Let us observe a time interval ∆. Regardless of the start time, the worst possible probability of failure inside the interval shall be denoted as PF ∆ . Because only jobs whose deadlines are inside ∆ are of concern, we can link failure rates inside an interval to job deadline miss probabilities (dmp-s):

PF ∆ = max λ     1 - job's deadline in [λ, λ + ∆] (1 -dmp (job))     (5)
Checking every possible interval start λ can be computationally prohibitive. Fortunately, we can reduce the problem by the following lemma. [START_REF] Tȃmas ¸-Selicean | Design optimization of mixed-criticality real-time embedded systems[END_REF]. First, the interval HP always has all jobs from one hyper-period inside it, so the search for maximum from ( 5) is not necessary. Second, the δ interval is limited in length, so the calculating ( 5) is not computationally prohibitive. More details, along with the proof of the lemma, can be obtained in the report [START_REF] Draskovic | On the safety of mixed-criticality scheduling[END_REF].

B. Application to Normal Mode

In normal mode, by definition, tasks will not overrun their execution time thresholds. Thus, we could use the limited execution time distributions of all tasks and directly apply the plain safety analysis technique to get the failure rates on each criticality level, PFH N LO and PFH N HI . However, special attention needs to be paid to LO criticality tasks due to the conventional mixed-criticality model: in normal mode, if a LO criticality task exceeds its execution θ threshold, it will be killed. This also constitutes a failed execution, which was not taken into account in the afore mentioned analysis. The probability of this event happening can be obtained directly from the execution time distribution function of the task, P (C k > θ k ). Therefore, we define that PFH N LO is the probability that either a LO task is killed, or it misses its deadline. Because these two sources of failure are independent, calculating the cumulative probability of failure can be done directly. Nevertheless, for the scope of this paper and for simplicity reasons, when mentioning PFH N LO only missed deadlines shall be implied.

IV. EXPECTED MODE SWITCH TIME

To show how long the system is expected to stay in normal mode, or how often the normal to emergency mode switch occurs, we introduce the expected mode switch time. If the normal mode starts at time zero, and T sw is the time the mode switch happens, then E[T sw ] is the expected mode switch time. The normal mode start can either be the system start or a safe switch from emergency to normal mode.

The probability that a mode switch occurs in an interval [λ, λ + ∆] can be written as

p sw [λ,λ+∆] = 1 - all HI jobs in interval[λ,λ+∆] P (C k ≤ θ k ) (6)
In a practical system, the mode switch is expected to be a rare event, with the time between the start of normal mode and the mode switch several orders of magnitude larger than an hour. Accordingly, as a precondition to the usefulness of this analysis, we expect the hyper-period to be much smaller than the expected time between two mode switches. Because of this, it is reasonable to view one hyper-period as a time unit. If p sw HP is the probability of mode switch in one hyper-period, then the expected mode switch is after 1 /p sw HP hyper-periods. This can be written as in [START_REF] Baruah | Response-time analysis for mixed criticality systems[END_REF].

E[T sw ] = 1 p sw HP × HP (7)
V. CHOOSING THE THRESHOLDS An important and novel question not dealt within the previous analysis is how to determine the θ i (execution time) thresholds that trigger a mode switch. These are thresholds for HI tasks. Choosing such thresholds is a design space exploration problem, but is not a straightforward task. As we explain, it involves a trade-off between two safety related values.

Let us first investigate the impact of the threshold on the expected mode switch time, E[T sw ]. As [START_REF] Giannopoulou | Scheduling of mixed-criticality applications on resource-sharing multicore systems[END_REF] shows, with increased thresholds, the probability of mode switch per hyperperiod (p sw ) will decrease; consequently, the expected mode switch time (E[T sw ]) will increase, see [START_REF] Baruah | Response-time analysis for mixed criticality systems[END_REF]. In practice, we would like to have the expected switch time to be as long as possible, in order to keep the system "away" from the emergency mode. This implies that thresholds should be large.

However, we need to still consider the impacts of selected thresholds on system safety. We continue to discuss the way the thresholds influence failure rates in normal mode, PFH N χ . Since the execution time of a HI task in normal mode (C N i ) depends on its threshold θ i ≥ C N i , we observe that the average normal mode execution time of a task E[C N i ] decreases with decreasing θ i ; accordingly, we get smaller average job execution times and less average system utilization. This implies a smaller probability that jobs miss their deadlines and fail. In summary, we find that the failure rates on each criticality level in normal mode (PFH N χ ) monotonically increase with increasing task execution time thresholds (θ). Thus, to have the failure rates for both LO and HI tasks as low as possible, we would favor thresholds to be small.

A corner case of this trade-off gives us the comparison between systems with and without modes of operation -the latter option being when HI task's thresholds are their WCETs, in which case the system never enters emergency mode. We can see that a system in normal mode of operation is safer than the same system operating with no modes at all. However, this comes at a cost, which is the introduction of the emergency mode.

VI. SIMULATION RESULTS

To illustrate the afore presented analysis, as well as the impact of execution time thresholds on the system, we present generalized observations with random simulations.

First, we have used Gumbel distributions to model the execution times of tasks, as can be seen in Figure 3. The Gumbel distribution is a standard assumption for task execution time distributions [START_REF] Wartel | Measurementbased probabilistic timing analysis: Lessons from an integrated-modular avionics case study[END_REF]. It is used to model the distribution of maximum values, in this case long but unlikely execution times.

We simulated 54 random systems, each with an average utilization close to 0.8, a hyper-period of 300µs, and up to eight jobs. The threshold varied was always the one of the task with the highest priority; this way the varied threshold effects tasks of all priority levels. This was varied from the respective WCET (right side in Figures 4 and5), to a value 25µs less than that (left side of figures). All other thresholds, both for HI and LO criticality tasks, were 3µs less than their respective WCET. In order to present different values together, we normalized them, so instead of showing absolute values, all values are relative to the case when the threshold of the highest priority task is at its WCET. Figures 4 and5 are box-whisker plots aggregating results from all of the systems. On one hand, we observe in Figure 5 that increasing threshold θ 1 increases the system failure rates in normal mode. On the other hand, Figure 4 shows that a higher threshold delays the expected time the system switches to emergency mode. This is in line with the analysis from Sections IV and V: a fundamental trade-off between normal mode safety and the expected mode switch time does exist.

VII. FUTURE WORK: SAFETY OF EMERGENCY MODE

The plain safety analysis, used to describe normal mode, would be pessimistic to be used for emergency mode. Thus, finding the safety of this mode is left for future work.

The reason is twofold. First, at the start of emergency mode, the backlog is expected to be large. This is because one of the jobs, the one causing the mode switch, is experiencing a high execution time. Backlogs later shall drop as time passes, and due to LO criticality tasks being degraded. However, Theorem 1 implies that this large backlog should be used to get deadline miss probabilities of all the jobs, and this potentially makes the failure rates unjustifiably high.

Second, the emergency mode is conceived by the system model to last as short as the safety requirements allow it, and having degraded service longer than necessary is not acceptable. This is why we can not take for granted that the steady state values will be reached during the operation of this mode.

Generally speaking, an analysis dealing with emergency mode should address the following challenges:

• The time of mode switch is unknown, as well as the job causing it. This causes the initial backlog to be unknown. • The switch back to normal mode has to be understood, including proving when it is statistically safe to switch back. The statistically safe to switch back condition would be met if for example, after the switch the failure rates are in accordance with safety standards. • For jobs in emergency mode, an algorithm to safely obtain deadline misses should be presented. Apart from understanding the emergency mode, addressing these challenges would contribute to provide a holistic, mode independent PFH.

VIII. CONCLUSION

In this paper, we showed that it is possible to analyze the safety of mixed-criticality systems. We introduced a probabilistic model for dual-criticality systems, and defined safety metrics for this model in line with industry standards. These are the holistic or mode-independent PFH, the PFH in a single mode, and the expected mode switch time.

Next, we proved that the values we obtained for PFH in normal mode are safe. Expected mode switch times, from normal to emergency, were also analyzed.

Towards designing a feasible system, we showed that a trade-off has to be taken into account: this exists between the failure rates in normal mode for both HI and LO tasks, and the expected mode switch time. This was confirmed with the simulation results as well.

However, further work towards understanding emergency mode is still needed to form a complete view of the safety of a mixed-criticality system.

2 Fig. 1 :

 21 Fig. 1: p 2 created by limiting p 1 with θ

w 1 =Fig. 2 :

 12 Fig.2: Finding the failure probabilities of jobs in a simple scenario -at time 4, w 1 is the backlog (unfinished workload) from τ 1 while w 2 is the backlog including τ 2

5 )

 5 Shrinking PDFs: Shrinking a probability distribution function p by m is defined as summing up the first m + 1 elements into the first element, and left shifting the remaining distribution by m. (4) is a formal definition of this shrinking shrink(p, m)

Lemma 1 .

 1 Surely n b = ∆ HP -1 whole hyper-periods are present inside an interval ∆, regardless of its start time. If we note the reminder of the interval as δ = ∆-n b •HP, we can calculate the failure rate inside an interval as PF ∆ = n b • PF HP + PF δ . The values PF HP and PF δ can be easily computed based on

Fig. 5 :

 5 Fig. 3: Execution times as Gumbel distributions