Zain A H Hammadeh
email: hammadeh@ida.ing.tu-bs.de

Sophie Quinton
email: sophie.quinton@inria.fr

Marco Panunzio
email: marco.panunzio@thalesaleniaspace.com

Rafik Henia
email: rafik.henia@thalesgroup.com

Laurent Rioux
email: laurent.rioux@thalesgroup.com

Rolf Ernst
email: ernst@ida.ing.tu-bs.de

© Zain

A H Hammadeh

Budgeting Under-Specified Tasks for Weakly-Hard Real-Time Systems *

Keywords: 1998 ACM Subject Classification B.8.2 Performance Analysis and Design Aids real-time, weakly-hard, slack analysis, execution budget, fixed priority Digital Object Identifier 10.4230/LIPIcs.ECRTS.2017.17

In this paper, we present an extension of slack analysis for budgeting in the design of weaklyhard real-time systems. During design, it often happens that some parts of a task set are fully specified while other parameters, e.g. regarding recovery or monitoring tasks, will be available only much later. In such cases, slack analysis can help anticipate how these missing parameters can influence the behavior of the whole system so that a resource budget can be allocated to them. It is, however, sufficient in many application contexts to budget these tasks in order to preserve weakly-hard rather than hard guarantees. We thus present an extension of slack analysis for deriving task budgets for systems with hard and weakly-hard requirements. This work is motivated by and validated on a realistic case study inspired by industrial practice.

Introduction

In the design of real-time systems, it is not uncommon for some parts of a task set to be fully specified while other parameters, e.g. regarding recovery or monitoring tasks, will be available only much later. In such cases, slack analysis can help anticipate how these missing parameters can influence the behavior of the whole system so that a resource budget can be allocated to them. It is, however, sufficient in many application contexts to budget these tasks so as to preserve weakly-hard rather than hard guarantees. Such guarantees allow for a bounded number of consecutive deadline misses ("at most m out of k deadlines may be missed"). We thus present an extension of slack analysis for budgeting under-specified tasks for systems with hard and weakly-hard requirements.

The four main contributions of this paper are: an extension of slack analysis [START_REF] Lehoczky | An optimal algorithm for scheduling soft-aperiodic tasks in fixed-priority preemptive systems[END_REF] to compute the maximum slack which guarantees that no more than m deadline misses out of k consecutive executions can happen; an execution time budget for under-specified tasks based on the multiframe task model [START_REF] Mok | A multiframe model for real-time tasks[END_REF] where we consider that each under-specified task has two execution times: a long one and short one; a methodology that explains why and how this method should be used safely in the design of systems that have hard and weakly-hard requirements; a case study dealing with satellite on-board software which shows the practical usefulness of weakly-hard constraints and how to guarantee them.

This paper is organized as follows. Section 2 introduces the application context of this paper, that is a satellite on-board software system. Section 3 then explains the timing verification problem that we are facing and why the proposed analysis is the appropriate solution to address it. Section 4 provides the preliminaries on response-time analysis which are needed to introduce our work. These preliminaries include principles of standard worstcase response-time analysis, typical worst-case analysis and slack analysis. Section 5 shows how to budget the under-specified tasks to satisfy hard real-time constraints. Our major contribution is in Section 6 where we present an extension of slack analysis and our general approach for budgeting based on the multiframe task model. We summarize the methodology that we propose in Section 7, present our experimental results in Section 8 and discuss related work in Section 9. Section 10 concludes.

Motivational Example

In this section we introduce the case study which motivates the work presented in this paper.

State of the practice for the timing analysis of satellite software

A satellite is made of two major parts: the platform and the payload. The payload realizes the main satellite mission, and comprises scientific instruments, telescopes or telecommunication antennas, according to the mission of the satellite. The payload is typically characterized by high computation requirements but in the general case its software is considered at best firm or soft real-time.

The platform is the service module that governs the satellite and ensures the execution of the mission. The platform on-board software (OBSW) implements all major functions of the satellite: e.g., the Attitude and Orbit Control System (AOCS), the Thermal Control System (TCS), mode management, Data Handling System (DHS).

A subset of those OBSW functions are characterized by hard real-time requirements. For example, sending thruster commands at the wrong moment during an attitude modification or an orbital maneuver (e.g., the main orbit insertion of a deep-space orbiter) may lead to mission failure.

In contrast, some tasks executing some less critical functions, may occasionally miss deadlines without dreadful consequences on the mission, and at most some performance degradation. One example is the AOCS functions itself, where sensor acquisition and processing are somehow robust to occasional deadline misses because of the intrinsic robustness of the implemented control laws.

The OBSW is however traditionally designed, analyzed and implemented with techniques typical of safety-critical, hard real-time systems. This implies that all tasks defined for the OBSW are considered as hard real-time and treated as such in the schedulability analysis used to confirm the system feasibility. The analysis is performed using representative worst-case operational scenarios. The reason for this choice is twofold: 1. It is much easier to prove to clients that the system is schedulable and fulfills the mission goals by treating all tasks as hard real-time, with a design process and analysis equations consolidated along several years, and without admitting exceptions on the treatment of task deadlines.

2.

The OBSW development team does not know completely the possible consequences of deadline misses from the point of view of performance degradation or function losses, as such knowledge requires deep analysis at system / avionics level. It is therefore not obvious to understand if deadline misses are admissible in the overall mission context.

System model and use case

Current satellite OBSW is typically executed on a single-core processor, and using a Fixed-Priority Preemptive scheduling policy (FPP).

Table 1 shows a representative task set and the real-time attributes of each task. The attributes are representative of a high-load scenario for the OBSW in a mission operational mode. Each task τ i in the system is characterized by its: priority index π i ; for simplicity of notation, we assume that tasks are given in order of their static priority, i.e., τ j has higher priority than τ i for every j < i; type of task release pattern: periodic (P), possibly with static offset, software sporadic (S), hardware sporadic (HWS), i.e., triggered by an interrupt, background task; worst-case execution time C i ; this value is not based on static analysis but rather on the observed execution times; period or interarrival time T i ; offset ϕ i if applicable; relative deadline D i -all deadlines are constrained; maximum blocking time b i ; execution in mutual exclusion is enforced with semaphores or protected objects (monitors) for which the maximum blocking can be bounded.

Note that some tasks specified as sporadic have in fact a pseudo-periodic behavior. Table 1 includes two different kinds of tasks: (i) nominal tasks: tasks that are active and executed in the represented operational scenario; (ii) recovery tasks: tasks that are involved in asynchronous fault handling or recovery activities and are triggered only on given fault / error occurrences. They are marked as gray in the table. Among the nominal tasks, some have real-time constraints that we will consider as hard real-time; others can be considered as weakly-hard real-time, as they can withstand occasional deadline misses without significant system-level consequences.

Problem Statement

The specification of recovery tasks typically occurs in the latest development phases, and therefore their characteristics are not known until late in the development cycle. The execution of such recovery tasks may however perturb the execution of nominal tasks, leading to deadline misses which would potentially induce a degradation of the system performance. Configuring the timing attributes of the recovery tasks represents a challenging timing issue for the real-time architect. It is important to guarantee that the reconfiguration and recovery tasks can accomplish their functions, which are related to the safety of the spacecraft. At the same time, it is necessary to preserve a sound timing behavior for the nominal tasks.

Moreover, the timing behavior of the recovery tasks must be established and assessed as early as possible in the development, as in later phases the development of the rest of the software system approaches completion, with little freedom for significant modifications.

The reader should note that the problem statement regards finding a convenient method for assigning attributes and guarantees to such tasks, rather than establishing a complete fault tolerance strategy [START_REF] Rubel | Fault tolerant approaches for distributed real-time and embedded systems[END_REF] [START_REF] Maode | A fault-tolerant strategy for real-time task scheduling on multiprocessor system[END_REF] for the on-board software and the satellite. The latter requires a much more global reasoning at system level and it is not in the scope of this paper. Those tasks would be just some among several mechanisms (hardware and software) that are devoted to the implementation of such global fault tolerance strategy for a given satellite, and the method we seek would simply concur to their definition in a convenient manner.

To solve this problem, there is a need for a timing verification method fulfilling two conditions:

(i) applicability at early design stages;

(ii) a guarantee on the provided upper bounds for the tasks' response times. Worst-case response time analysis seems well adapted to solve the timing challenge mentioned above, since its applicability already starts with the early conceptual design phases and it provides formal proofs based on a mathematical model of the system timing behavior. These proofs allow calculating safe lower and upper bounds on the response times, thus guaranteeing corner-case coverage.

Classic worst-case response-time analysis would however not be able to take into account the weakly-hard nature of some tasks, and would just check that deadlines of those tasks are met in the worst case. This would lead to an under-estimation of the timing budget available for the recovery tasks (and therefore to ensure the safety functions), which could be delicate, especially in case of a system with a high CPU load.

A method that takes into account the weakly-hard nature of some tasks and can provide to the real-time architect means to perform tradeoffs on the budget to be assigned to the recovery tasks would be considered attractive in this context.

Let us now formulate our problem. We consider a single processing resource which schedules a task set T = {τ 1 , τ 2 , . . . , τ n } according to a Fixed Priority Preemptive (FPP) policy. Each task τ i ∈ T is modeled by its worst-case execution time C i worst-case activation pattern η + i (see below) priority π i constrained deadline D i

The tasks described in the motivating example of Section 2 are either periodic or sporadic. We will in this paper use the more general model of arrival curves to describe activation patterns, such that we can model sporadic tasks (in particular the recovery tasks that we want to budget) less conservatively than using a model based on the minimum interarrival time. We do not however handle offsets and conservatively assume that all periodic tasks can be activated at the same time. We leave to future the formal proof that offset analysis is compatible, as we conjecture, with the analysis presented in this paper. In contrast, blocking times are not mentioned in the rest of the paper for readability but they can easily be included in the analysis (and they are accounted for in the experiments).

E C R T S 2 0 1 7 17:6

Budgeting Under-Specified Tasks for Weakly-Hard Real-Time Systems Definition 1. Arrival curves are functions η + i , η - i : N → N to model the possible activations of a task τ i such that for any time window ∆, η + i (∆) defines the maximum number of activations of τ i that might occur within ∆, and , and η - i the minimum (in this paper we only use η + i ). The pseudo-inverse of arrival curves, namely δ - i , δ + i : N → N, such that δ - i (k) (respectively δ + i (k)) defines the minimum (respectively maximum) time that might pass between the first and the last activation in any sequence of k consecutive activations of τ i .

In this context, the fact that deadlines are constrained translates into D i ≤ δ - i (2). Our task set T is partitioned into nominal tasks, which are fully specified, and recovery tasks, for which only priorities and deadlines are known, such that we call these under-specified tasks. We denote by N the set of nominal tasks and R the set of under-specified tasks. Under-specified tasks are considered to be sporadic. Weakly-hard constraints are assumed to be given for nominal tasks.

Our problem is to provide a set of constraints on the execution times and the activation patterns of the tasks in R that is sufficient (and ideally necessary too) to guarantee (m, k)schedulability of all tasks in N , where a task is said to be (m, k)-schedulable if it cannot miss more than m deadlines out of a sequence of k consecutive executions.

Preliminaries on Response-Time Analysis

In this section we recall some state-of-the-art definitions and results on response-time analysis which we will use in the rest of the paper, based on the notations introduced at the end of our problem statement. We specifically present results related to worst-case response-time analysis, Typical Worst-Case Analysis (TWCA) and slack analysis. Note that we suppose throughout this paper a representation of time based on natural numbers. This is reasonable since we consider single processor systems, which operate according to a unique, discrete clock.

Worst-case response-time analysis

A standard approach to establish schedulability of a system is to compute the worst-case response time of each task based on the concept of busy window. In this section we present results for the case where deadlines are arbitrary as we will need these later.

Definition 2. A level-i busy window (originally called busy period in [START_REF] Lehoczky | Fixed priority scheduling of periodic task sets with arbitrary deadlines[END_REF]) is a maximal time interval during which the resource still has activations of tasks of equal or higher priority than τ i pending.

The longest such window, called worst-case level-i busy window and denoted BW i , is built by assuming the occurrence of a so-called critical instant, where τ i and higher-priority tasks are all activated at the same time, inducing maximum interference with τ i . It is also assumed that all tasks are activated as early as possible after the critical instant, and that they always use their maximum execution time. The maximum level-i busy window stops at the first instant when no activation of τ i or any higher priority task remains incomplete. It has been proven that the worst-case response time of task τ i can be found in the longest level-i busy window. Definition 3. For a task τ i and q ≥ 1, the multiple event busy time, denoted B i (q), represents the maximum time it may take to process q activations of τ i within a level-i busy window starting with the first of these q activations.

B i (q) = min{∆T ≥ 0 | ∆T = q × C i + τj ∈hp(i) η + j (∆T ) × C j } (1)
where hp(i) denotes the set of tasks with higher priority than τ i (we assume that all tasks have distinct priorities).

The maximum number K i of activations of τ i in a level-i busy window is then

K i = min{q ≥ 1 | B i (q) < δ - i (q + 1)}
K i is the smallest number such that the resource would be able to start processing the (K i + 1)-th activation before this activation can occur according to δ i , which implies an idle time. The worst-case level-i busy window can then be determined as

BW i = B i (K i ).
The response time of every activation of τ i is bounded by

RT i (q) = B i (q) -δ - i (q) .
The response time of τ i is bounded by Theorem 4.

WCRT i = max 1≤q≤Ki {RT i (q)} . ( 2
)
We refer the reader to [START_REF] Tindell | An extendible approach for analyzing fixed priority hard real-time tasks[END_REF] for detailed explanations about the FPP response-time analysis.

Typical Worst-Case Analysis

Typical Worst-Case Analysis (TWCA) as presented e.g. in [START_REF] Quinton | Formal analysis of sporadic overload in real-time systems[END_REF] [23] aims at providing weaklyhard guarantees for real-time systems, where a weakly-hard guarantee states that in no more than m out of k consecutive executions of a task, a deadline is missed. TWCA relies on the assumption that deadline misses in a system are due to transient overload resulting e.g. from sporadic activations.

We present here a specific application scenario of TWCA where activations of some specific tasks are considered as overload while activations of all other tasks are classified as typical.

We say that the system is in the typical case in a time interval in which there are no past or currently pending/executing overload activations which could impact the behavior of the system. We require the system to be schedulable in the typical case. The alternative case is called the worst case scenario where some overload activations may incur transient overload and therefore deadline misses.

The objective of TWCA is to compute a deadline miss model (DMM) for each task.

Definition 5.

A deadline miss model (DMM) for task τ i is a function dmm i : N → N, with the property that out of any sequence of k consecutive activations (called k-sequence) of τ i , at most dmm i (k) might miss their deadline D i .

In the basic TWCA as introduced in [START_REF] Quinton | Formal analysis of sporadic overload in real-time systems[END_REF], dmm i (k) is computed in four steps: 1. Computation of N i , the number of deadline misses that occur in the longest level-i busy window BW i . Note that one overload activation of any task cannot result in more than N i deadline misses of τ i as it can only impact activations of τ i which are in the same level-i busy window.

E C R T S 2 0 1 7 17:8

Budgeting Under-Specified Tasks for Weakly-Hard Real-Time Systems

τ 3 case 1 τ 2 τ 1 X X X Ω 3 4 = 2 case 2 Ω 2 4 = 2 Ω 1 4 = 3 X

X busy windows

Figure 1 Packing overload activations into busy windows of task τ4 (X = deadline miss).

2.

Computation of ∆T i k , the longest time window during which an overload activation (of any task) can impact the response time of activations in the k-sequence. Activations in different busy windows cannot influence each other's response time. As a result, only activations of an overload task occurring at most BW i time before the first activation of τ i in the k-sequence and before the last activation finishes can have an impact. This time interval is thus bounded by:

∆T i k = BW i + δ + i (k) + WCRT i .

3.

Computation of Ω i , the maximum number of higher-priority overload activations that may occur within a window of size ∆T i k :

Ω i = τj ∈hp(i)∩O η + j (∆T i k )
where O denotes the set of overload tasks.

We can then safely define dmm

i (k) = min{k, Ω i × N i }.
The improved TWCA of [START_REF] Xu | Improved deadline miss models for real-time systems using typical worst-case analysis[END_REF] uses an additional concept called combinations to improve the accuracy of DMMs. Definition 6. A combination is a subset of the overload tasks, the idea being that one overload activation alone is usually not sufficient to cause a deadline miss as most tasks have some slack. Here we distinguish the overload due to different overload tasks:

∀τ j ∈ O ∩ hp(i), Ω j i = η + j (∆T i k ) .
A bound on the maximum number of deadlines that τ i may miss in a k-sequence is then obtained by packing overload activations into level-i busy windows.

Example 7. As an example see Figure 1 where we consider a system with 4 tasks: τ 1 , τ 2 , τ 3 are overload tasks while τ 4 is a typical task. To bound the maximum number of deadlines that τ 4 may miss within a given time interval, we pack respectively Ω 1 i , Ω 2 i and Ω 3 i activations into the busy windows of τ 4 . Figure 1 shows two possibilities of packing where in case 1 the number of deadline misses is 3 while in case 2 τ 4 may miss only 2 deadlines. Notice that not all combinations may lead to deadline misses. Theorem 8. The following function is a DMM. where U is the set of unschedulable combinations, i.e. combinations c which may lead to a deadline miss if all tasks in c are activated in the same level-i busy window. Note that in this approach it is assumed that all unschedulable may result in N i deadline misses.

dmm i (k) = min{k, N i × max{ c∈U x c | ∀τ j , {c∈U |τj ∈c} x c ≤ Ω j i }} Priority τ 1 τ 2 τ 3
[23] additionally provides an efficient criterion to determine whether a combination is schedulable as well as an efficient ILP solution to compute the above DMM.

Slack analysis

Finally, we now recall some results related to slack analysis [START_REF] Davis | Scheduling slack time in fixed priority pre-emptive systems[END_REF], [START_REF] Lehoczky | An optimal algorithm for scheduling soft-aperiodic tasks in fixed-priority preemptive systems[END_REF], [START_REF] Ramos-Thuel | On-line scheduling of hard deadline aperiodic tasks in fixed-priority systems[END_REF], [START_REF] Tia | Algorithms and optimality of scheduling soft aperiodic requests in fixed-priority preemptive systems[END_REF]. Definition 9. The slack S 0 i of task τ i is the maximum amount of processing time which may be stolen from any job of τ i without causing its deadline to be missed.

The slack of a task τ i can be computed by noticing that any level-i idle time between the completion of a job of τ i and its deadline can be used for computation of that job without causing it to miss its deadline.

Definition 10. By level-i idle time we refer to any maximal time interval between two level-i busy windows. Theorem 11. For FPP scheduling, the slack of τ i is equal to the sum of all level-i idle times between the critical instant and D i in the worst-case busy window. This is illustrated in Figure 2.

Budgeting with Hard Real-Time Constraints

In this section, we first focus on the problem of providing a set of constraints on the load incurred by the tasks in R (i.e. recovery tasks, a.k.a. under-specified tasks) that is sufficient to guarantee schedulability of all tasks in the nominal mode, before we move to discuss weakly-hard schedulability.

Let us first focus on a task τ i in the nominal mode. Denote R i the set of under-specified tasks with a priority higher than τ i . We can directly reuse the concept of slack to budget the under-specified tasks.

Lemma 12. Let S 0 i be the slack of τ i in the system made of only nominal tasks (i.e. excluding under-specified tasks). If τr∈Ri C r ≤ S 0 i and δ - r (2) > D i then τ i is schedulable.

E C R T S 2 0 1 7

17:10

Budgeting Under-Specified Tasks for Weakly-Hard Real-Time Systems

Proof. This follows directly from the definition of slack. Note that we need to ensure that at most one activation of any under-specified task will interfere with a given job of τ i for the result to hold.

We can generalize the above result by splitting the load allocated to an under-specified task among several of its jobs.

Lemma 13. Let BW 0

i be the longest level-i busy window obtained by analyzing the nominal task set with an additional load of size S 0 i . That is:

BW 0 i = min{∆T ≥ 0 | ∆T = C i + S 0 i + τj ∈ N ∩ hp(i) η + j (∆T ) × C j } . If τr∈Ri η + r (BW 0 i ) × C r ≤ S 0 i then τ i is schedulable.
Proof. Again, this follows directly from the definition of slack. In this case the slack used by an under-specified task τ r is shared among several of its jobs.

We can now state our general result on how to budget under-specified tasks to guarantee hard real-time schedulability of all nominal tasks.

Theorem 14. If for all τ

i ∈ N τr∈Ri η + r (BW 0 i ) × C r ≤ S 0 i (3)
then the system is schedulable.

Proof. The above equation and Lemma 13 guarantee together than all nominal tasks remain schedulable in presence of under-specified tasks satisfying the given constraints.

If this budget is acceptable then there is no need to consider budgeting for the weakly-hard case. The rest of this paper is dedicated to proposing solutions if a larger budget is needed for execution times of the under-specified tasks.

Budgeting with Weakly-Hard Real-Time Constraints

Our problem is now to provide a set of constraints on the load incurred by the tasks in R that is sufficient to guarantee weakly-hard schedulability of all tasks in the nominal mode rather than (hard) schedulability. Again, we first focus on a task τ i in the nominal mode, this time supposing that it has an (m, k) weakly-hard requirement, i.e. τ i may miss no more than m out of k deadlines. Denote R i the set of under-specified tasks with a priority higher than τ i .

As recalled in Section 4.2, the standard way to establish (m, k)-schedulability using Typical Worst-Case Analysis [START_REF] Xu | Improved deadline miss models for real-time systems using typical worst-case analysis[END_REF] is to consider a sequence of k consecutive activations of τ i and to prove that no more than m activations in this sequence may miss their deadline. In our case the activations of under-specified tasks can be considered as overload since they are not taken into account by the initial worst-case analysis. We can therefore adapt TWCA to our context. We reuse in particular the following notations.

N i , the number of deadline misses that occur in the longest level-i busy window BW i of the system with nominal and under-specified tasks.

∆T i k , the longest time window during which an activation of an under-specified task can impact the response time of activations in the k-sequence.

∆T i k = BW i + δ + i (k) + WCRT i .
Ω r i , the maximum number of activations of higher-priority under-specified task τ r that may occur within a window of size ∆T i k :

Ω r i = η + r (∆T i k )
and Ω i the sum over all higher-priority under-specified tasks:

Ω i = τr∈Ri Ω r i .
Notice here that budgeting according to constraints on N i and ∆T k i is not easy as these parameters themselves depend on the parameters of the under-specified tasks. In the next section we first focus on how to relate the load budget of recovery tasks and N i , i.e. the maximum number of deadline misses in a single busy window.

Extending the concept of slack to weakly-hard systems

Let us start with a few lemmas.

Lemma 15. There can be more than one activation of a given task τ i in one level-i busy window only if that task misses its deadline in that busy window. Formally:

K i ≥ 2 only if WCRT i > D i . Proof. By definition of K i , B i (K i ) ≤ δ - i (K i + 1
) and for any q < K i , B i (q) > δ - i (q + 1). For q = 1 : B i (1) > δ - i (2). We work with constrained deadlines so D i ≤ δ - i (2) so B i (1) > D i . As B i (1) = RT i (1) and therefore WCRT i ≥ B i (1) we can conclude that WCRT i > D i . This lemma is easily generalized to consecutive deadlines misses: ∀q < K i , RT i (q) > D i . This result is useful for us as it directly relates the number of deadline misses in a busy window with the length of that busy window. In particular, we obtain that

N i = K i -1 if B i (K i ) ≤ δ - i (K i ) + D i .
Let us now go one step further and extend the slack analysis of Section 4 to systems in which a bounded number of deadline misses are allowed. Definition 16. For µ ∈ N, the µ-slack of a task τ i , denoted S µ i , is the maximum amount of processing time which may be stolen from τ i in a level-i busy window without causing more than µ deadlines of τ i to be missed in a row.

The µ-slack of a task τ i can be computed in a way similar to the usual slack but focusing on the (µ + 1)-th deadline instead of the first deadline.

Theorem 17. For FPP scheduling, the µ-slack of τ i is equal to the sum of all level-i idle times between the critical instant and δ - i (µ + 1) + D i in the worst-case busy window.

Proof. The above condition guarantees that the (µ + 1)-th deadline is met.

Let us now introduce a definition which will be useful to bound BW i and WCRT i .

E C R T S 2 0 1 7 17:12

Budgeting Under-Specified Tasks for Weakly-Hard Real-Time Systems Definition 18. Let BW µ i be the longest level-i busy window obtained by analyzing the nominal task set with an additional load of size S µ i . We know that such a busy window contains exactly µ + 1 activations of τ i so:

BW µ i = min{∆T ≥ 0 | ∆T = (µ + 1) × C i + S µ i + τj ∈ N ∩ hp(i) η + j (∆T ) × C j } .
Since τ i may not miss more than m deadlines in a row, we can conclude that BW i ≤ BW m i . Similarly WCRT i is bounded by the response times of τ i observed in BW m i . We thus know how to define ∆T k i . Let us now state the condition which guarantees that τ i may not miss more than m deadlines in a row, and thus

N i = m. Lemma 19. If τr∈Ri η + r (BW m i ) × C r ≤ S m i then τ i cannot miss more than m deadlines in a row.
Proof. This is a direct consequence of the definition of m-slack.

At this point, it may seem that the intuitive, if pessimistic, way to budget the underspecified tasks is to require that τr∈Ri η + r (∆T k i ) × C r ≤ S m i . This, however, is not a sufficient condition for (m, k)-schedulability. The reason is that the same load incurred by under-specified tasks may result in more deadline misses if they happen in different busy windows. This is the meaning of the following lemma.

Lemma 20.

∀µ ∈ N

+ : S µ i ≥ (µ + 1) × S 0 i .
Proof. Consider a sequence of µ + 1 consecutive activations of τ i . Remember that S 0 i is the sum of all level-i idle times between the critical instant and D i in the worst-case busy window. Because deadlines are constrained, this is smaller than or equal to the sum of all level-i idle times between the critical instant and δ - i (2) in the worst-case busy window. Allowing only S 0 i slack for each activation in the sequence furthermore assumes that the critical instant may repeat for each activation, which is pessimistic compared to the way S µ i is computed. As a result, S µ i provides more slack than (µ + 1) × S 0 i .

The consequence of this is that a safe bound on the budget for the under-specified tasks must be based for now on S 0 i .

Lemma 21. Let

Λ i = (m + 1) × S 0 i . If τr∈Ri η + r (∆T k i ) × C r ≤ Λ i then τ i is (m, k)-schedulable.
Proof. We have to prove that a load of Λ i within ∆T k i causes no more than m consecutive deadline misses if it occurs in one level-i busy window of τ i , and no more than m nonconsecutive deadline misses if it distributes over several busy windows.

The first condition is directly satisfied by Lemmas 19 and 20. Suppose now that Λ i is distributed over n level-i busy windows with l b denoting the load in each busy window:

η + r (∆T k i ) × C r ≤ (m + 1) × S 0 i ( 4
)
then the system satisfies its hard and weakly-hard requirements.

Proof. This results is a direct consequence of Lemma 21.

This result is obviously quite pessimistic. It is clear at this point that obtaining better bounds requires us to use a more fine-grained model of how load distributes over busy windows. We investigate this possibility in the next section.

Budgeting for multiframe tasks

In the following, we focus on a specific application scenario and assume that each underspecified task performs two activities:

A frequent monitoring activity with a relatively short execution time aiming at analyzing deviations from safe state in the system and perform some rapid recovery or triggering higher-level recovery, characterized by a short minimum distance between two consecutive occurrences.

A less frequent failure recovery activity (e.g., an avionics reconfiguration procedure) which requires a longer execution time and characterized by a longer minimum time distance between two consecutive executions.

Based on the behavior described above, the execution time model of any under-specified task τ r can be characterized by (C l r , C s r , x) where: C s r is the short execution time corresponding to the recovery activity of the task; C l r is the long execution time corresponding to the error handling activity of the task; x is the number of short execution times between two long execution times.

Based on this new model we again address the problem of providing a set of constraints on the execution times and activation patterns of the tasks in R that is sufficient to guarantee weakly-hard schedulability of all tasks τ in the nominal mode.

Let us first focus on a task τ i in the nominal mode with an (m, k) weakly-hard requirement, i.e. τ i may miss no more than m out of k deadlines. Denote R i the set of under-specified tasks with a priority higher than τ i , Ω r i = η + r (∆T k i ) for all τ r ∈ R i and Ω i = r∈Ri Ω r i . Let us first by formulating a hypothesis which is consistent with the application scenario mentioned at the beginning of this section. We use the notation c c r to refer to the execution time of τ r in combination c. Note that we exclude here the possibility for several activations of the same under-specified task to be in the same level-i busy window. That is, we suppose that ∀τ r ∈ R i :

δ - r (2) > BW m i .
Definition 24. Let µ(c) denote the maximum number of deadlines misses which may be caused by a combination c. Formally we have:

S µ(c)-1 i < τr∈Ri c c r ≤ S µ(c) i with the convention that S -1 i = 0. If µ(c) = 0 then c is called schedulable, otherwise it is said to be unschedulable.
Of course µ(c) depends on the values chosen for the various execution times C l r and C s r for τ r ∈ R i . Our strategy for budgeting the under-specified tasks is to first assign values on µ(c) for all combinations and then in a second step to assign execution time budgets. Hypothesis 2. We suppose that a combination containing only short execution times of under-specified tasks cannot be unschedulable. That is, τr∈Ri C s r ≤ S 0 i .

Again this hypothesis seems realistic given the application context. Based on the notion of combination we can define gangs which correspond to distributions of the Ω i instances within ∆T k i . More specifically, a gang is a packing of activations of the under-specified tasks into the level-i busy windows of ∆T k i .

Definition 25. A gang G is a set of combinations which contain at least one long execution time and such that for all

τ r ∈ R i #{c ∈ G | c c r > 0} ≤ Ω r i #{c ∈ G | c c r = C l r } = 1
Notice that we ignore combinations which do not contain any long execution time as they cannot lead to deadline misses. Note also that each combination appears at most once in a gang (since there can be only one long execution time of each task within ∆T k i ). We use G i to denote all possible gangs with respect to τ i .

Lemma 26. If ∀G ∈ G i : c∈G µ(c) ≤ m then τ i is (m, k)-schedulable.
Proof. The above condition guarantees that no matter how activations of under-specified tasks align, they can never result in more than m deadline misses. This lemma trivially extends to upper bounds on the µ(c) as we formulate now.

Lemma 27. For all c, let µ c be an upper bound on µ(c). If ∀G ∈ G

i : c∈G µ c ≤ m then τ i is (m, k)-schedulable.
Now, one thing which does not appear in the above lemma is that the µ(c) are not independent from each other. Definition 28. There exists a partial order ≤ on combinations such that c1 ≤ c2 if and only if the execution times in c1 are all smaller than their counterpart in c2 , i.e.,

∀τ r ∈ R i : c c1 r c c2 r . Lemma 29. If c1 ≤ c2 then µ(c 1 ) ≤ µ(c 2 ).
Proof. This directly follows from the fact that c1 ≤ c2 implies that the load incurred within one level-i busy window by the under-specified tasks in c1 is smaller than that in c2 .

Theorem 30. Suppose that you have assigned the µ c such that ∀G ∈ G i : c∈G µ c ≤ m. Then any assignment of the c c r such that for all combination c, r∈Ri c c r ≤ S µc i guarantees the (m, k)-schedulability of τ i .

Proof. This follows directly from Lemma 27 and the definition of µ c-slack.

Note that there always exists such an assignment. Now that we have presented our solution for budgeting under-specified tasks based on the multiframe execution time model, let us show how it proceeds on an illustrative example.

Example 31. Consider as an example a system with only one task τ 3 in the nominal mode and two under-specified tasks τ 1 and τ 2 , as illustrated in Figure 3. Task τ 3 has a (2, 10) weakly-hard requirement. τ 1 and τ 2 have priorities higher than the priority of τ 3 , and no more than 2 instances within ∆T k i . Figure 3 shows gang

G = {c 1 , c4 , c7 } where c1 = (C l 1 ), c4 = (C s 1 , C l 2 ) and c7 = (C s 2 )
-to improve readability we omit 0s in the representation of combinations. There are five combinations containing at least one long execution time:

c1 = (C l 1 ), c2 = (C l 2 ), c3 = (C l 1 , C s 2 ), c4 = (C s 1 , C l 2 ), c5 = (C l 1 , C l 2 ) .
There are three more combinations containing at least one short execution time:

c6 = (C s 1 ), c7 = (C s 1 ), c8 = (C s 1 , C s 2 ) .
Let us now focus on gangs. Remember that gangs consist of combinations containing at least one long execution time and that two combinations with the long same execution time cannot be in the same gang. We only list here maximal gangs.

G 1 = {c 1 , c2 }, G 2 = {c 1 , c4 }, G 3 = {c 2 , c3 }, G 4 = {c 3 , c4 }, G 5 = {c 5 } .
E C R T S 2 0 1 7

17:16

Budgeting Under-Specified Tasks for Weakly-Hard Real-Time Systems

This yields the following constraints, the first five of which are directly derived from the gangs while the remaining four constraints are obtained by comparing combinations.

1. µ c1 + µ c2 ≤ 2 2. µ c1 + µ c4 ≤ 2 3. µ c2 + µ c3 ≤ 2 4. µ c3 + µ c4 ≤ 2 5. µ c5 ≤ 2 6. µ c1 ≤ µ c3 7. µ c3 ≤ µ c5 8. µ c2 ≤ µ c4 9. µ c4 ≤ µ c5
One solution to this set of constraints is e.g.

µ c1 = 1, µ c2 = 1, µ c3 = 1, µ c4 = 1, µ c5 = 2.
Assuming we have chosen the above assignment for the µ c we now the define the constraints to be satisfied by the execution times of tasks, one per combination and then one for the short execution times.

1. C l 1 ≤ S 1 i 2. C l 2 ≤ S 1 i 3. C l 1 + C s 2 ≤ S 1 i 4. C s 1 + C l 2 ≤ S 1 i 5. C l 1 + C l 2 ≤ S 2 i 6. C s 1 + C s 2 ≤ S 0 i
Any solution to this set of constraints guarantees (m, k)-schedulability of τ i .

Methodology and Discussion

Let us now summarize the methodology that we propose to provide the architect with simple answers helping him/her dimension the tasks that are still under-specified in the system. 1. We first compute an execution time budget for the under-specified tasks which guarantees hard real-time constraints (zero deadline misses). If this execution time budget is acceptable for the architect then we do not need to go further. 2. If, however there is a need for larger execution times for the under-specified tasks, we then compute a second execution time budget which guarantees weakly-hard constraints.

Taking into account weakly-hard constraints we can allow more load within shorter time windows but over longer time windows the load available for under-specified tasks is still limited.

3.

If the activation patterns of the under-specified tasks are known and a multiframe execution time model is meaningful we can propose more relaxed bounds on execution times budgets.

Experimental Results

Let us now provide some experimental results we have obtained using the cplex constraint solver on budgeting under-specified tasks. We first address the motivational example of Section 2 and then present experiments made on synthetic test cases.

The OBSW case study

The case study presented in Section 2 is a system made of a single resource and a task set shown in Table 1 where 27 tasks are in the nominal mode and there are 3 recovery and reconfiguration tasks τ 10 , τ 11 , τ 21 which are under-specified. As discussed before in Section 2, all on-board software is currently typically analyzed with hard real-time techniques; and yet by experience, the overall system is still quite robust to For the sake of the case study we propose some weakly-hard constraints for tasks that are purposely quite aggressive: the reader could notice that in some cases a tolerance of 1 deadline every 2 seconds is admitted for some tasks. This would permit to ascertain the robustness (at least from the point of view of real-time constraints) of such representative task set even in case of severe degradation (which would require high sporadic load for the recovery activities).

The worst-case response time analysis of the nominal mode shows that the system is schedulable. Our goal is to synthesize a load budget for the under-specified tasks τ 10 , τ 11 , τ 21 which guarantees that all weakly-hard real-time constraints described in Table 2 are satisfied. We show first the constraints on the execution times and activation models of the tasks in R which guarantee absence of any deadline miss before providing the same result when a few deadline misses are tolerated.

Note that tasks {τ 1 , . . . , τ 9 } have higher priority than the recovery and reconfiguration tasks so their timing properties do not depend on the budget of tasks in R. They will therefore be excluded from our study. We denote by T the remaining tasks with lower priority, that is: T = T \ {τ 1 , . . . , τ 9 }.

Budgeting with hard real-time constraints

If we want to guarantee that the system is schedulable then the budget to be shared between the under-specified tasks is S 0 i = 48.01ms. If this budget is not sufficient for the architect we can propose a budget with weakly-hard real-time guarantees.

Budgeting with weakly-hard real-time constraints

If the architect can accept to work with weakly-hard rather than hard guarantees then the available budget for the recovery tasks is (m + 1) × S 0 i = 96.02 ms. This budget is twice as much as the budget for the hard real-time case. We can obtain even better bounds by using a more fine-grained model of how load distributes over busy windows.

Budgeting for multiframe tasks

Let us assume that for all τ i ∈ N there are at most This means in particular that the budget that is available for the under-specified tasks within ∆T k i is at least 108.015 ms. Note that there are many other possible assignments for the µ values which lead to different execution times.

Synthetic examples

In this section, we present a set of synthetic test cases to test more extensively our approach on a variety of systems. In this experiment we study the impact of different characteristics such as utilization, (m, k) constraints, system size, etc.

For that purpose we generated 1000 task sets randomly depending on UUniFast [START_REF] Emberson | Techniques for the synthesis of multiprocessor tasksets[END_REF]. We define a set of tasks T with a priority, a worst-case execution time, a period, a deadline, and an (m, k) real-time constraint. The standard approach is to first define the system utilization and then assign a share of it to each task [START_REF] Emberson | Techniques for the synthesis of multiprocessor tasksets[END_REF]. We picked up a utilization among {0.4, 0.5, 0.6, 0.7, 0.8}, then the number of tasks are chosen to be ∈ [START_REF] Bernat | Weakly hard real-time systems[END_REF][START_REF] Tia | Algorithms and optimality of scheduling soft aperiodic requests in fixed-priority preemptive systems[END_REF] and periods are harmonic. The worst-case execution time is then computed C i = U i * T i . Deadlines = {0.6, 0.8, 1} * T i as our approach supports only constrained and implicit deadlines. We generate a random (m, k) for each task in the system such that:

k ∈ [2, 100], m ∈ [1, k -1].
The number of under-specified tasks is limited to r = 3 and the maximum number of instances of each under-specified task is generated randomly to be in [1, r 2 ].

Results

Figure 4 shows in the form of a histogram how much we gain in terms of load budget for the under-specified tasks by using a multiframe task model with weakly-hard constraints instead of using a single worst-case execution time with hard real-time constraints. Note that the results in the former case are obviously at least as good as those for the latter case. Figure 4 shows for example that for 198 task sets the load budget in the multiframe case (load M F ) is between 5 and 10 times larger than the load budget in the hard case (load H ), that is:

5 < load M F load H ≤ 10
.

The load we gain, however, is related to the number of under-specified tasks. Figure 5 shows that the larger the number of under-specified tasks the less load we gain, that is due to sharing the available slack among more under-specified tasks which makes the long execution C l shorter.

The results shows that there is no impact of the utilization on the load we gain. Number of periodic tasks causes no degradation on the load we gain by using multiframe task model. Note that we have repeated our experiment 10 times and observed similar results.

Related Work

The work presented in this paper most closely relates to sensitivity analysis, slack analysis, multiframe task systems and weakly-hard real-time systems. Note that determination of bounds on unspecified system parameters is the scope of Parametric Model Checking [6] [9]. Even if such approaches are known to have difficulty scaling up to even simple settings, it would be interesting to see if these approaches could apply to our problem. This work focuses on budgeting under-specified tasks for weakly-hard real-time systems. Although the under-specified tasks in our case study (OBSW) are recovery tasks, schedulability analysis of fault-tolerant real-time systems [START_REF] Burns | Feasibility analysis of fault-tolerant real-time task sets[END_REF] [START_REF] Lima | Scheduling fixed-priority hard real-time tasks in the presence of faults[END_REF] is not in the scope of this paper.

Sensitivity analysis is used to provide guarantees on the schedulability of a system in case of uncertainty on the system parameters. In [START_REF] Bini | Sensitivity analysis for fixed-priority real-time systems[END_REF] Bini et al. introduced an analytical sensitivity analysis for FPP scheduled periodic task sets with constrained deadlines (i.e. D ≤ T ). Work by [START_REF] Wandeler | Real-time interfaces for interface-based design of real-time systems with fixed priority scheduling[END_REF] and [START_REF] Neukirchner | Sensitivity analysis for arbitrary activation patterns in real-time systems[END_REF] propose solutions for sensitivity analysis of systems with activation patterns specified with arrival curves.

In contrast to all these papers, our work proposes for the first time a solution for the sensitivity analysis of weakly-hard real-time systems: We constrain the admissible load that under-specified tasks in the system can use without violating weakly-hard real-time constraints in FPP scheduled task sets with arbitrary activation patterns and constrained deadlines.

E C R T S 2 0 1 7 17:20

Budgeting Under-Specified Tasks for Weakly-Hard Real-Time Systems Slack stealing is a scheduling algorithm proposed by [START_REF] Lehoczky | An optimal algorithm for scheduling soft-aperiodic tasks in fixed-priority preemptive systems[END_REF] to schedule aperiodic tasks by stealing all the processing time it can from the periodic tasks without causing their deadlines to be missed. Similar algorithms based on slack stealing have been proposed by other authors [START_REF] Davis | Scheduling slack time in fixed priority pre-emptive systems[END_REF] [18] [START_REF] Tia | Algorithms and optimality of scheduling soft aperiodic requests in fixed-priority preemptive systems[END_REF]. These algorithms do not take into account any weakly hard guarantees and they, therefore, bound the maximum slack in a window of size D i . In our approach, however, we consider (m, k) weakly-hard requirements and we thus bound the maximum slack in a window of size δ - i (m + 1) + D i . Multiframe task model was invented originally in [START_REF] Mok | A multiframe model for real-time tasks[END_REF] to provide a less pessimistic schedulability test than [START_REF] Liu | Scheduling algorithms for multiprogramming in a hardreal-time environment[END_REF] for hard real-time systems. This model assigns to each periodic task N execution times (C 0 , C 1 , . . . , C N ), the execution time alternates between them where the execution time of the i-th instance of the task is C ((i-1)modN ) where i ≥ 1. In this paper we use a specific case of the multiframe task model for sporadic tasks which assigns two execution times: long C l and short C s where within a time window ∆ one instance of the task uses the long execution time while the rest use the short execution times. We propose our multiframe task model in a context of budgeting under-specified recovery tasks (sporadic) to provide the recovery tasks with more load for weakly-hard real-time systems.

Weakly-hard systems [START_REF] Bernat | Weakly hard real-time systems[END_REF] is a concept which guarantees that out of k consecutive executions of a task, not more than m deadline misses may occur. The approach of [START_REF] Quinton | Formal analysis of sporadic overload in real-time systems[END_REF] and the related articles provide analyses to verify such constraints. In this paper we reuse the concepts developed in these papers to better budget under-specified tasks.

Conclusion

In this paper, we have shown how to budget under-specified tasks in the early design of weakly-hard real-time systems by providing sufficient conditions which guarantee (m, k) schedulability. This is particularly useful in industrial practice because it often happens during design that some parts of a task set are fully specified while other parameters, e.g. regarding recovery or monitoring tasks, do not become available before much later. Existing budgeting techniques, which are restricted to hard real-time constraints, can help anticipating how these missing parameters influence the behavior of the whole system, but they are likely to yield execution time budgets that are too tight to be useful. We have shown that using weakly-hard rather than hard guarantees, whenever possible, results in much more applicable execution time budgets. Our results are thus of real practical value for the design of systems such as the on-board software system discussed in the paper. Note that in this paper we have not at all addressed the issue of the complexity of the analysis. The reason for that is that this does not appear to be a limiting factor for industrial applicability at this point. It would however be interesting to better understand how far the approach presented in this paper can scale and how much we can improve its efficiency.

Finally, we need to acknowledge the need for complementary work related to weakly-hard real-time systems as mentioned in Section 2, in particular in relation with the impact of deadline misses on system functions. Recent work [START_REF] Frehse | Formal analysis of timing effects on closed-loop properties of control software[END_REF][START_REF] Blind | Towards networked control systems with guaranteed stability: Using weakly hard real-time constraints to model the loss process[END_REF] in this direction indicate that this question is indeed considered as relevant in the research community as well as in the industry.

Figure 2

 2 Figure 2Worst-case busy window analysis. The slack S 0 4 of τi is shown.

Theorem 22 .

 22 n b=1 l b = Λ i . For each l b let µ b denote the maximum number of (consecutive) deadline misses that may be caused by l b (µ b ≥ 0). We have to prove that n b=1 µ b ≤ m. By definition we know that l b > S µ b -1 i for all l b so from Lemma 20 we can derive that l b > µ b × S 0 i . If we now sum this over all l b we get b = Λ i = (m + 1) × S 0 i we can conclude that m + 1 > n b=1 µ b , which is what we had to prove. If for all τ i ∈ N with an (m, k) schedulability constraint

  τr∈Ri

Hypothesis 1 .

 1 For each task τ r ∈ R i , we allow only one instance out of Ω r i to have a long execution time C l r . The other Ω r i -1 activations of τ r within ∆T k i will be bounded by the short execution time bound C s r . Tasks for Weakly-Hard Real-Time SystemsIn a way that is similar to the state of the art in TWCA as explained in Section 4.2 we now introduce the concept of combinations.Definition 23. A level-i combination is a tuple c = (c 1 , c 2 , . . . , c |Ri| ) such that each task τ r ∈ R i corresponds to one c r in the tuple and c r = 0 or c r = C s r or c r = C l r .

Figure 3 A

 3 Figure 3 A gang of τ1 and τ2 within ∆T k i where τ3 has a real time constraints (2,10).

≤ 1 ≤ 2 ≤ 3 ≤ 4 ≤ 5 ≤Figure 4

 123454 Figure 4The relation between loadMF and loadH .

Figure 5

 5 Figure 5The relation between the gain of load and r.

Table 1

 1 A task set representative of on-board software. π, C, T , ϕ, D and b denote respectively: priority, worst-case execution time, period/minimum distance, offset, deadline, blocking time. The time unit is ms.

	Name π Type	C	T	ϕ	D	b
	τ 1	1	HWS	0.56 15.625		15.625 0.1
	τ 2	2	P	0.76 15.625		15.625 0.1
	τ 3	3	P	15	125		31.25	0.1
	τ 4	4	P	25.03	125	78.125 46.875 0.1
	τ 5	5	P	7.5	62.5		62.5	0.1
	τ 6	6	P	6.15	125		125	0.1
	τ 7	7	P	1.2	125	93.750	125	0.1
	τ 8	8	P	0.9	1000	500	500	0.1
	τ 9	9	P	1.95	250		250	0.1
	τ 10	10	S		10000		125	0.1
	τ 11	11	S				125	0.1
	τ 12	12	P	1.2	125		125	0.1
	τ 13	13	P	5.15	250	46.875 203.125 0.1
	τ 14	14	P	1.2	1000		500	0.1
	τ 15	15	P	22.5	500		500	0.1
	τ 16	16	P	3.5	250		250	0.1
	τ 17	17	P	27	500		500	0.1
	τ 18	18 HWS	1.5	1000		1000	0.1
	τ 19	19	P	16	1000		1000	0.1
	τ 20	20	P	19.1	1000		1000	0.1
	τ 21	21	S				1000	0.1
	τ 22	22	P	88.8	2000		2000	0.1
	τ 23	23	P	2	32000		32000	0.1
	τ 24	24	P	1	32000		32000	0.1
	τ 25	25	P	1	1000		1000	0.1
	τ 26	26	S	20	1000		1000	0.1
	τ 27	27	S	40	2000		2000	0.1
	τ 28	28	S	1.5	2000		2000	0.1
	τ 29	29	S	1.5	2000		2000	0
	τ 30	30	P	0.2	32000		32000	0

Table 2

 2 Real-time constraints of tasks in T . (m, w) represents the maximum number of allowed deadline misses m every w seconds, (m, k) means that a task may miss at most m deadline out of k consecutive activations.

	task	τ 12	τ 13	τ 14	τ 15	τ 16	τ 17	τ 18	τ 19	τ 20
	(m, w) (1,2)	(1,4) (1,8) (1,4) (1,4)	(1,4)	(1,8)	(1,8) (1,8)
	(m, k) (1,16) (1,16) (1,8) (1,8) (1,16) (1,8)	(1,8)	(1,8) (1,8)
	task	τ 22	τ 23	τ 24	τ 25	τ 26	τ 27	τ 28	τ 29	τ 30
	(m, w) (1,16)	hard	hard (1,8) (1,8) (1,16) (1,16) (1,16) hard
	(m, k)	(1,8)	hard	hard (1,8) (1,8)	(1,8)	(1,8)	(1,8)	hard
	occasional deadline misses, although at the moment there is no necessity to formally evaluate
	such tolerance in the state-of-the-practice process.

1 * This work has been partially funded by the German Research Foundation (DFG) as part of the project "TypicalCPA" under the contract number TWCA ER168/30-1.

Cons

ist en t * Comple te * We ll Docum en


Leonie Ahrendts

Sophie Quinton

Rolf Ernst

Exploiting Execution Dynamics in Timing Analysis Using Job Sequences

Keywords: Embedded and cyber-physical systems, Real-time systems, Weakly hard real-time systems, Automotive systems, Safety, Timing analysis, Constraint specification !

Worst case design as needed for critical systems usually resorts to established methods for worst case response time analysis which rely on the worst case execution time of tasks and the minimum temporal distance between task activations. The result is often very pessimistic when compared to the real worst case load. Many feasible designs are therefore rejected under such analyses. Using worst case models based on job sequences rather than single jobs leads to less pessimistic results and makes worst case design more practical. This paper outlines existing modeling and analysis techniques which are based on job sequences and refers to several examples from automotive design where great benefits were demonstrated.

INTRODUCTION

Deriving tight bounds on the timing behavior of a realtime computing system is known to be a challenging verification problem. Verification itself is difficult, but another major problem is that of identifying a precise yet analyzable system model for which safe (i.e., possibly approximate but always correct) parameter values can be obtained in practice through measurements or formal approaches.

A real-time computing system consists of a set of software tasks which compete for processing and communication resources and are served according to a scheduling algorithm. A task is executed repeatedly and each of its instances is called a job. A task can therefore be seen as an infinite sequence of jobs over time. The creation of a job is triggered by an activation event, and the amount of service requested by a job is called its workload. Jobs may access shared resources such as memory during execution. For performance verification, a task is modeled using bounds on its timing parameters. To derive such bounds, it is common to (1) characterize the best case/worst case parameters that can be observed for a single job of this task, and then (2) attribute these extreme parameters to every job of the considered task. Characteristic parameters of a job include its execution time, access times to shared resources, communication delays, as well as the temporal distance to the activation event of the subsequent job (simply called job distance in the sequel). This procedure leads to a safe but pessimistic timing model of a task. A similar approach is commonly chosen for specifying the constraints imposed on a real-time computing system: The hardest timing constraint that applies to one job of a given • L. Ahrendts and R. Ernst are with the Institute of Computer and Network Engineering, TU Braunschweig, Hans-Sommer-Strasse 66, 38106 Braunschweig, Germany. Email: {ahrendts, ernst}@ida.ing.tu-bs.de • S. Quinton is with Inria Grenoble -Rhône-Alpes, 655 Avenue de l'Europe -Montbonnot, 38334 St Ismier Cedex, France. Email: sophie.quinton@inria.fr task is adopted for all jobs of that task. One such example is a task deadline which must be met for every job.

In this paper, we advocate the use of job sequences to describe the best case/worst case timing parameters and constraints of a task: These should be formulated for sequences of n consecutive jobs (also called n-sequences in the following). By this means, execution dynamics and therefore variability in task behavior can be taken into account. For instance, in an n-sequence of jobs of the same task, the temporal distance between the first and the last activation event is guaranteed to be larger than n times the minimum job distance. Similarly, n consecutive jobs of a task have a maximum cumulative workload that is smaller than n times the worst case execution time. On the constraint side, it may be tolerable for some jobs in a given n-sequence to miss their deadline.

In various works on real-time computing systems, specific problems have been successfully solved by considering sequences of jobs for modeling and/or constraint specification. We believe that a rigorous and consistent use of job sequences for task modeling and constraint specification could represent an important step towards tighter bounds on system timing behavior. In addition, the effort required to model timing parameters and to derive constraints for potentially any n ∈ N can be reduced with appropriate mathematical methods.

In the rest of this paper, we first survey and discuss existing work based on job sequences for either modeling or constraint specification. We then show as an example how Typical Worst-Case Analysis (TWCA) achieves substantial improvements in accuracy by systematically using job sequences for both modeling and constraint specification. We illustrate its practical significance by industrial case studies.

USING JOB SEQUENCES FOR TASK MODELING AND CONSTRAINT SPECIFICATION

In this section, we discuss seminal research contributions which exploit properties of job sequences for modeling or constraint specification of real-time computing systems. Note that, although these powerful abstractions for the description of job sequences exist, they are often not used to their full potential in practice.

Task Modeling Using Timing Parameters Based on Job Sequences

An activation event may be caused by a periodic timer interrupt, or by a measured variable falling below or exceeding a threshold value, an alarm indicating a specific incident like a timer overflow or a fault, etc. Many activation events thus have an aperiodic nature, and their timing depends on the dynamics of the system environment. The execution time of a task, on the other hand, may vary due to several reasons: data-dependent control flow, variable resource usage or access times as in e.g. memory accesses.

Using job sequences for modeling the arrival of activation events and workload can greatly improve the accuracy of the model when the timing of these parameters is subject to high variability. This important observation is at the core of Network Calculus [START_REF] Boudec | Network calculus: a theory of deterministic queuing systems for the internet[END_REF], and has been exploited by a host of work in communication theory. Network Calculus was later adapted and proposed as a method for real-time system design under the name of Real-time Calculus [2] [3]. Both Network Calculus and Real-time Calculus use as fundamental modeling concepts event arrival curves and workload curves, which describe best case/worst case task parameters for job sequences. For instance, the upper event arrival curve α + i (∆t) of a task τ i bounds from above the number of activation events that may occur in any time interval ∆t. The relation to job sequences is even more obvious if one considers the pseudo inverse δ - i (n) of α + i (∆t), which we call the distance function: δ - i (n) returns the minimum temporal distance between the first and the last activation event in any sequence of n consecutive jobs of task τ i . Similarly, the upper workload curve γ + i (n) of a task τ i bounds from above the workload requested by any n consecutive jobs.

Event arrival and workload curves provide an expressive task modeling approach which can yield more accurate analysis results. Figure 1 illustrates the striking difference between event arrival and workload curves obtained based on (1) worst case parameter values for a sequence of jobs and (2) linear extrapolations of worst case parameter values of a single job. We mean by linear extrapolation w.r.t. event arrival that the minimum inter-arrival time of any two jobs is used as period. Linear extrapolation w.r.t. requested workload is the weighting of the worst case execution time with the number of activation events. In contrast, the non-linear, job sequence-based worst case models represent tighter upper bounds α + (∆t) and γ + (n) since they are based on the observation of more than one job. The shaded area between the linear models and the non-linear sequence models in Figure 1 illustrates the gain in accuracy.

Let us now shortly discuss options for deriving in practice such tight and expressive event arrival and workload curves over job sequences. Event arrival curves which are formally derived are tight if the behavior of the event source is either analytically known or enforced. Periodic event arrivals with jitter fall, for instance, in the first category. Shaped events streams fall in the second category. The workload of a job sequence can be formally bounded using e.g. a multiframe task model [START_REF] Wandeler | Quantitative characterization of event streams in analysis of hard real-time applications[END_REF] [4] whenever knowledge about the task structure and functional behavior is available. Besides, it is not a problem if upper event arrival curves or upper workload curves are only known up to a specific n, as the concept of sub-additive extension can be applied [START_REF] Wrege | Video traffic characterization for multimedia networks with a deterministic service[END_REF].

The tightness of formal bounds relies on detailed information on the software and the hardware platform in use. Such information is not always available and then formally derived bounds are pessimistic. When platforms with complex performance-enhancing and power-saving features are used, this pessimism is so large that the practical usability of these formal bounds is disputable. A complementary approach is thus to derive bounds on event arrival and workload by measurements over execution traces. An execution trace of a task is a list of observed activation instants and execution times of an actual job sequence. Although it has the character of experiments and an uncertainty thus formally remains, trace recording is a widely used and accepted technique in industrial practice.

Constraint Specification Based on Job Sequences

The classical timing constraint for real-time systems is the deadline of a task, specifying the maximum allowed response time of any job of this task. Satisfying this constraint guarantees a maximum reaction time which fits the time constants of the system and its environment.

For systems with control or imaging applications, it has been demonstrated that deadline misses can actually be tolerated without any impact on their functional correctness cf. [START_REF] Bernat | Weakly hard real-time systems[END_REF] [7] [START_REF] Blind | Towards networked control systems with guaranteed stability: Using weakly hard real-time constraints to model the loss process[END_REF] as long as the pattern of deadline misses is precisely known. Such robust systems are called weakly-hard real-time systems. A tolerable pattern of deadline misses is usually defined as an (m, k) constraint, where at most m deadline misses in k consecutive task executions are allowed. This implies that for weakly-hard systems a response time constraint is a function of the past system behavior. (m, k) constraints thus capture variability in timing constraints over a sequence of k jobs. Weakly-hard systems are usually verified as if they had hard real-time constraints. Specifying (m, k) constraints for them rather than a single deadline clearly increases their likelihood to be successfully verified. Interestingly, from the guaranteed satisfaction of a given (m, k) constraint one can infer satisfaction of constraints for other values of k [START_REF] Quinton | Generalized weakly-hard constraints[END_REF].

Discussion

We have seen so far that several standalone approaches exist which exploit execution dynamics in the timing analysis of real-time computing systems: On the one hand, the consideration of job sequences allows refined modeling of event arrival and workload. On the other hand, weakly-hard constraints improve accuracy in constraint specification by introducing requirements over a sequence of jobs, taking into account the inherent robustness of systems towards occasional deadline misses.

Furthermore, the presented concepts -task modeling based on job sequences and weakly-hard constraintsshare the mathematical property that they describe or constrain job sequences in a cumulative manner. Cumulative functions do not preserve knowledge about the individual timing behavior of each job in the considered sequence, but summarize the timing characteristics of the sequence. This approach is mathematically elegant, because it contains all required information for performance verification but condenses at the same time several equivalent worst cases in one description. The introduced event arrival curves and workload curves are cumulative since they describe worst case aspects of task behavior with regard to a time interval ∆t (event arrival curve) or a sequence of n jobs (workload curve). Likewise weakly-hard constraints define a budget of deadline misses for a sequence of n jobs, which generally includes several allowed patterns of jobs with missed deadlines.

In this paper, we argue for systematically applying sequence-based approaches in both modeling and constraining. As will be demonstrated in the following, this is an important step to significantly reduce pessimism of formal timing analysis results and make the verification of highly loaded, industrial real-time computing systems possible.

VERIFYING HIGHLY LOADED SYSTEMS

Highly loaded real-time computing systems, which actually work in industrial practice, are often rejected by formal timing analysis. The discrepancy between measurements and formal analysis can be considerably reduced, if tighter upper bounds on event arrival and workload are applied as described in Section 2.1. This standalone approach is, however, often not sufficient. System feasibility observed in practice suggests that event arrival and workload demand of tasks must be most of the time below the obtained upper bounds. In the transient overload situations, which may happen, there is experimental evidence that many systems tolerate a limited number of deadline misses. The functional robustness towards m deadlines misses in a sequence of k consecutive jobs can even be proven [START_REF] Frehse | Formal analysis of timing effects on closed-loop properties of control software[END_REF] [START_REF] Blind | Towards networked control systems with guaranteed stability: Using weakly hard real-time constraints to model the loss process[END_REF]. It seems therefore reasonable to combine sequence-based modeling with weakly-hard constraints introduced in Section 2.2.

One key issue is how to formally provide (m, k) guarantees, considering schedulable and unschedulable phases of system behavior. The verification method Typical Worst Case Analysis (TWCA) [START_REF] Xu | Improved deadline miss models for real-time systems using typical worst-case analysis[END_REF] proposes a possible solution. First, event arrival curves and workload curves for each task are derived, which are true upper bounds for most of the run time. Such event arrival curves and workload curves are called typical, because they capture the predominant timing behavior of tasks (for example the periodic workload but not the rare sporadic workload). Those typical curves describe a less service-demanding job behavior than the worst case curves: Figure 2a shows a typical event arrival curve α +,typ (∆t) and a worst case event arrival curve α + (∆t) for a given task, where by definition we have α +,typ (∆t) ≤ α + (∆t). In the example, the typical event pattern is periodic, while in the worst case additional sporadic activation events occur. Figure 2b illustrates a typical workload curve γ +,typ (n) and a worst case workload curve γ + (n) for a given task, where again γ +,typ (n) ≤ γ + (n). In a phase of typical system behavior, a certain maximum typical execution time TCET is never exceeded, while execution times larger than TCET may occur in the worst case.

The difference between the worst case curve and the typical curve is monotonically increasing, both for events and workload. In contrast to the approaches presented in the previous section, however, important differences are not only obtained for longer job sequences but also for a single job: On the one hand, the typical event arrival curve does not assume the minimum inter-arrival time even for a single job. On the other hand, the typical workload curve does not attribute the worst case execution time WCET to a single job but the maximum typical execution time TCET . On the basis of typical event arrival curves and workload curves, highly loaded real-time systems can be proven schedulable in phases of typical behavior.

To verify the worst case behavior, TWCA quantifies the maximum distance between the typical and the worst case curves: The additional activation events contained in the worst case event arrival curve but not in the typical event arrival curve can be considered as cause for transient overload in the system. It is actually possible to bound the occurrence of these overload events in ∆t by the event arrival curve α +,over (∆t). Similarly, jobs which exceed the typical execution time are a potential source of overload. The maximum number of jobs which exceed the typical execution time in ∆t can be bounded by an event arrival curve α +,over T CET (∆t). From the comparison of the typical and worst case workload curves follows, moreover, that the amount of additional workload in a sequence of n consecutive jobs cannot be not larger than γ +,over T CET (n). TWCA now derives the maximum number of missed deadlines in a job sequence of given length k as a function of the number of overload events and the amount of additional workload. As we will see in the following section, highly loaded real-time systems with weakly-hard constraints have been successfully verified using the TWCA method.

CASE STUDIES

The significance of TWCA results for industrial practice has been demonstrated by several major use cases.

Automotive Communication Networks

In [START_REF] Quinton | Typical worst case response-time analysis and its use in automotive network design[END_REF], the timing behavior of automotive CAN buses has been investigated. Automotive CAN buses have seen a massive increase in utilization in recent years due to larger message sizes and a rapidly growing number of messages. CAN messages are time-triggered and/or event-triggered. If the minimum inter-arrival time is used for the modeling of event arrival in a system which is dominated by event triggering, the theoretical worst-case utilization of working systems exceeds 100% and may reach 500%. Tight nonlinear event arrival curves allow for a much more accurate performance analysis. Yet such an improved WCRT analysis still discards many systems, which have proven functional in extensive simulation. The reason is that the occasional loss of messages can actually be tolerated, and the modeling of response times constraints in form of (m, k)-guarantees better represents the actual system requirements.

The work presented in [START_REF] Quinton | Typical worst case response-time analysis and its use in automotive network design[END_REF] therefore applies sequence models and subsequently TWCA to the CAN case study. Firstly tight upper event arrival curves are derived based on specified and measured timing of message dispatch. Then sporadic dispatch events are identified which can be interpreted as overload events potentially causing deadline misses during transient workload peaks. Based on TWCA, for each message an (m, k)-guarantee is obtained. In the case study it could be shown that in at most 15 % of 10 000 executions, a CAN message transmission takes longer than in the overload-free case. For many of the 212 messages the percentage is significantly below 15 %. This experimental result was the first to formally show that an increase of the classical CAN bus load is actually tolerable.

Automotive Software: Engine Management

Automotive software applications integrate a large number of inter-dependent functions. The engine management ranks among the most complex software applications and is composed of about 20 container tasks including around 1500 functions which are scheduled by an OSEK-compliant operating system. These container tasks are a source of strong but well understood execution time variations. The average system utilization is usually above 90%, while the worst-case utilization in those systems exceeds easily 100%. Despite this evidence of overload, extensive simulation often suggests functional correctness of the investigated software systems. This discrepancy can be attributed to inaccurate utilization analysis which does not take into account variability of execution times.

The system-level timing feasibility test proposed in [START_REF] Tobuschat | Systemlevel timing feasibility test for cyber-physical automotive systems[END_REF] for an engine control application shows that with a workload curve γ + (n) which describes the execution demand of job sequences, significantly tighter WCRTs can be derived. While with linear workload modeling 5 out of 20 tasks are found to be infeasible in formal performance analysis, workload modeling w.r.t. job sequences improved the accuracy of results such that only 2 out of 20 tasks are bound to complete after their deadline. Since the involved control applications are inherently robust towards occasional deadline misses, (m, k)-guarantees for the 2 unschedulable tasks are derived. TWCA is applied to this problem of computing the (m, k)guarantees in [START_REF] Tobuschat | Systemlevel timing feasibility test for cyber-physical automotive systems[END_REF], yet the overload is not caused by additional sporadic activations in this use case. In contrast, it is caused by execution times of tasks which are occasionally longer than the T CET . In the case study, the 100ms task and the 200ms task could each tolerate 3 deadline misses in 20 consecutive executions, and as few as 1 deadline miss in 20 executions could actually be guaranteed by TWCA.

CONCLUSION

Modern real-time computing systems with performanceenhancing features have high variability in event arrival and workload. At the same time system requirements with regard to job completion are not static but often depend on system history. For instance, there may be a precisely defined budget for deadline misses of jobs.

An approach to deal with these dynamic system characteristics is to model and constrain sequences of jobs rather than focusing on the behavior of a single job in isolation. Event arrival curves, workload curves and weakly-hard constraints are existing abstractions which allow to make worst case statements about sequences of jobs. The systematic and rigorous use of this more detailed modeling and constraint formulation allows designing systems with formal worst case guarantees where established methods for formal performance analysis are not applicable due to their pessimism. Since the approach is compatible to existing engineering methods of measuring and trace recording it provides an opportunity to improve design verification and optimization where current design practice has to live with unsafe simulation and prototyping. This paper has presented as an example the TWCA method which is based on an analysis of the impact of transient overload. The gained accuracy narrows significantly the gap between verification results of formal performance analysis and simulations that are currently used for validation in industrial practice.

Fig. 1 :

 1 Fig. 1: Bounding event arrival and workload.

Fig. 2 :

 2 Fig. 2: Typical and worst case curves for event arrival and workload

Leonie

  Ahrendts is a Ph.D. student in the Embedded System Design Automation group of the Institute of Computer and Network Engineering at TU Braunschweig. She received her Master degree in electrical engineering from TU Braunschweig in 2015, and was fellow of the German Academic Scholarship Foundation. Her current research concerns the analysis of real-time systems with an emphasis on weakly-hard realtime systems. Other areas of interest are faulttolerant real-time computing systems and communication networks. Sophie Quinton is a researcher at Inria Grenoble Rh ône-Alpes in France. She received her Ph.D. degree from the University of Grenoble, in 2011. She was a graduate research assistant at the VERIMAG laboratory and a postdoc at the Institute of Computer and Network Engineering at TU Braunschweig. Her research focus is mostly on real-time schedulability analysis and contract-based design and verification of embedded systems. Rolf Ernst is a professor at the Technische Universit ät Braunschweig where he chairs the Institute of Computer and Network Engineering covering embedded systems research from realtime systems theory to challenging automotive and aerospace applications. He has a Ph.D. in EEIT from the University of Erlangen. He is an IEEE Fellow.

ACKNOWLEDGMENTS

This work has received funding from the German Research Foundation (DFG) under the contract number TWCA ER168/30-1. This work has also been partially supported by the LabEx PERSYVAL-Lab (ANR-11-LABX-0025-01).


Rafik Henia
email: rafik.henia@thalesgroup.com

Laurent Rioux
email: laurent.rioux@thalesgroup.com

Nicolas Sordon
email: nicolas.sordon@thalesgroup.com

Zain A H Hammadeh †
email: hammadeh@ida.ing.tu-bs.de

Rolf Ernst
email: ernst@ida.ing.tu-bs.de

Sophie Quintonᵀ
email: sophie.quinton@inria.fr

Bounding Deadline Misses for Weakly-Hard Real-Time Systems Designed in CAPELLA

Keywords: model-based design, model transformation, weakly-hard real-time systems, scheduling analysis

Real-time systems with functional dependencies between tasks often require guarantees on end-to-end delays. For many of these systems, end-to-end deadline misses are accepted if one can limit their frequency. Such systems are called weakly-hard. Recent work has shown that typical worst-case analysis (TWCA) can compute an upper bound on the number of potential deadline misses in a sequence of activations of a task chain. In a joint collaboration between Thales and TU Braunschweig, the use of TWCA to limit the number of deadline misses in an aerial video tracking (AVT) system was evaluated. The AVT casestudy, the complete automated model-based tool chain from the design environment to the timing verification using TWCA, as well as the results of the evaluation will be presented in the demonstration. The tool chain involves four tools: the design modeling tool CAPELLA extended by a performance viewpoint which allows annotating the design model with timing properties needed to perform TWCA, the pivot model TEMPO which handles mismatches between the semantics of the design model and the semantics of the model used in TWCA, the scheduling analysis tool pyCPA that performs TWCA and finally the graphical tool TimingGraphics used to visualize the TWCA results. To show the pertinence of the use of TWCA, we will also compare in the demonstration the obtained results with those obtained using worst-case analysis and simulation.

INTRODUCTION

In real-time systems, it is not uncommon to tolerate deadline misses for task chains, if their number can be bounded. Such systems are called weakly-hard [START_REF] Bernat | Weakly hard real-time systems[END_REF]. Classic worst-case analysis would not be able to take into account the weakly-hard nature of these systems, and would just reveal that some deadlines may not be met in the worst-case. This would lead to an overestimation of the required computing resources to safely run the system, which could be delicate, especially in the case of a system with a high CPU load. It is therefore important to design these systems so as to preserve weaklyhard rather than hard guarantees. TWCA can help providing such guarantees by calculating an upper bound on the number of deadline misses in a sequence of consecutive executions of a task ("at most m out of k deadlines of the task may be missed"). Recently, the TWCA approach was extended to handle end-to-end delays of task chains [START_REF] Hammadeh | Bounding Deadline Misses in Weakly-Hard Real-Time Systems with Task Dependencies[END_REF], thus making its use in industry more attractive. To evaluate the pertinence of using TWCA in industry, Thales and TU Braunschweig set up a toolchain (Figure 1) to compute upper bounds on deadline misses in an AVT system with weakly-hard end-to-end timing constraints. Starting from an initial system model in the modelbased engineering workbench CAPELLA [3], a performance viewpoint was developed to annotate the model with various timing and scheduling properties, such as execution times, periods, priorities, weakly-hard ("m misses out of k deadlines") constraints, etc. Then, a bridge was implemented to transform the annotated design model into a model that is analyzable by the scheduling analysis tool pyCPA [START_REF] Pycpa | Compositional performance analysis in python with pycpa[END_REF]. The transformation is performed via the pivot model TEMPO [START_REF] Henia | Integrating Formal Timing Analysis in the RealTime Software Development Process[END_REF] that ensures compatibility between the semantics of the design model and analysis model by performing model transformations, when needed, according to pre-defined rules. After running the analysis in pyCPA, results are sent back to CAPELLA and graphically displayed, using the tool TimingGraphics [6]. To assess the pertinence of TWCA, we have compared the results with those obtained using a Thales in-house tool for worst-case scheduling analysis and simulation, called TEMPO Verifier. All analyses and simulation are run on the same model.

In the demonstration, we will present the AVT system modeled in CAPELLA (Figure 2). Here, we will focus in particular on the implemented performance viewpoint. Then we will run the TWCA analysis in pyCPA and load the results back into CAPELLA. The whole tool chain is automated and can be run using a push button command in CAPELLA. All generated intermediate models will be presented in the demonstration. We will also compare the results with those obtained using TEMPO Verifier. The individual building blocks of the tool chain as well as the AVT case-study are briefly described in the next sections. The system purpose is to detect and track moving objects, e.g. vehicles on a roadway. AVT systems are mission critical real-time systems since they embed intelligence, surveillance, reconnaissance and tactical applications characterized by hard and weakly hard constraints on timing. For simplicity's sake, the case-study we present at the demonstration is limited to two subsystems of the AVT system running on a single processor according to the static priority scheduling policy: a periodic activated video frame processing application and a sporadic activated tracking and camera control application. CAPELLA is an Open Source solution hosted at polarsys.org. It provides a process and tooling for graphical modeling of systems, hardware or software architectures, in accordance with the principles defined by the model-based engineering method ARCADIA [7]. CAPELLA is mainly used for modeling complex and safety-critical real-time embedded systems in various industries such as aerospace, avionics, transportation and automotive. CAPELLA can be specialized, according to the concept of "Viewpoint", to manage information specific to a particular engineering need, e.g. nonfunctional properties such as timing performance.

IV. PERFORMANCE VIEWPOINT

In order to apply scheduling analysis to any design model, the later must be annotated with information describing the timing characteristics of tasks (e.g. execution times, activation periods, etc.), the behavior of the application (e.g. functional dependencies between tasks, end-to-end deadlines, etc.) and the characteristics of the hardware platform (e.g. CPU speed, scheduling policy, etc.). The UML Profile for MARTE [START_REF]MARTE[END_REF] is a key technology for this purpose. It allows extending design models with concepts modeling real-time behavior, thus making possible the extraction of a scheduling analysis model from a design model. We therefore selected concepts from MARTE to develop the CAPELLA performance viewpoint. In addition to these concepts, the performance viewpoint we developed includes concepts specific to weakly-hard systems and required by the TWCA, in particular the « at most m deadline misses out of k consecutive executions » constraint.

V. PIVOT MODEL TEMPO

Scheduling analysis is very often not directly applicable to conceptual design models due to the semantic mismatch between the latter and the variety of scheduling analysis models known from the classical real time systems research and represented by academic [START_REF] Pycpa | Compositional performance analysis in python with pycpa[END_REF] [9] and commercial tools [10]. For instance, in the common scheduling analysis models, a standard assumption is that a task writes its output data at the end of its execution. This is not always the case in design models, since very often, calls are either synchronous (blocking) or asynchronous (non-blocking). As a consequence, a task may write data into the input of a connected task at any instant during its execution and not necessarily at the end. TEMPO allows adapting design models to the semantics of the chosen scheduling analysis models through a set of transformation rules. Such transformations preserve the timing behavior modeled in the conceptual design. After performing scheduling analysis, the obtained results are, in turn, adapted back to the semantics of the design model.

VI. TYPICAL WORST-CASE ANALYSIS IN PYCPA

TWCA is a technique to compute an upper bound on the number of deadline misses in a sequence of consecutive executions of a task. Recently TWCA was extended at TU Braunschweig to compute an upper bound on the number of deadline misses in any sequence of consecutive executions of a task chain under fixed priority preemptive scheduling in a uniprocessor system [START_REF] Hammadeh | Bounding Deadline Misses in Weakly-Hard Real-Time Systems with Task Dependencies[END_REF]. The extended TWCA is implemented as a plugin for the scheduling analysis tool pyCPA.

VII. TIMINGGRAPHICS

TimingGraphics is a visualization tool allowing the illustration of the temporal behavior of real-time systems through a set of graphs [6]. In the context of this work, Ganttcharts and histograms were used respectively to visualize the worst-case end-to-end delay scenarios of the task chains, as well as illustrate the maximum number of end-to-end deadline misses as a function of the number of consecutive executions.

VIII. DEMONSTRATION

The evaluation of TWCA that we propose and show in this demonstration is the result of a fruitful collaboration between industry and academia, namely Thales and TU Braunschweig. It represents a contribution to the industrial exploitation of model-driven technologies and scheduling analysis in the design of weakly-hard real-time systems. An industrial casestudy is available as hands-on demonstration of the quality of the proposed technical solution.

Figure 1 :

 1 Figure 1: Tool chain to compute an upper bound on deadline misses for weakly-hard systems designed in CAPELLA II. AERIAL VIDEO TRACKING CASE-STUDY

Figure 2 :

 2 Figure 2: Design model (left fig.), performance viewpoint and TWCA result illustration (right fig.) for the aerial video tracking system in CAPELLA III. CAPELLA