Leonie Ahrendts
email: ahrendts@ida.ing.tu-bs.de

Sophie Quinton
email: sophie.quinton@inria.fr

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

Finite Ready eues As a Mean for Overload Reduction in Weakly-Hard Real-Time Systems

Keywords: Computer systems organization → Embedded and cyberphysical systems, Real-time systems, Real-Time Systems, Weakly-Hard Real-Time Guarantees, Limited Queue Capacity

Finite ready queues, implemented by bu ers, are a system reality in embedded real-time computing systems and networks. The dimensioning of queues is subject to constraints in industrial practice, and often the queue capacity is su cient for typical system behavior but is not su cient in peak overload conditions. This may lead to over ow and consequently to the discarding of jobs. In this paper, we explore whether nite queue capacity can also be used as a mean of design in order to reduce workload peaks and thus shorten a transient overload phase. We present an analysis method which is to the best of our knowledge the rst one able to give (a) worst-case response times guarantees as well as (b) weakly-hard guarantees for tasks which are executed on a computing system with nite queues. Experimental results show that nite queue capacity may only a have weak overload limiting e ect. This unexpected outcome can be explained by the system behavior in the worst-case corner cases. The analysis shows nevertheless that a trade-o between weakly-hard guarantees and queue sizes is possible.

INTRODUCTION

Real-time computing systems are said to be overloaded if not all tasks can be completed within their deadlines. Overload is often due to an unusually high number of additional sporadic jobs which appear as a reaction to a scarce environmental condition. Interestingly, it has been observed that many embedded applications, previously classi ed as having hard real-time requirements, actually tolerate occasional deadline misses. For instance, the performance of an imaging application is still acceptable if once in a while a frame is lost or repeated [START_REF] Bernat | Weakly Hard Real-Time Systems[END_REF]. Likewise the quality of a control application is still satisfactory if once in a while a sensor data sample is lost and the control algorithm is performed on an old sensor data sample [START_REF] Frehse | Formal Analysis of Timing E ects on Closed-loop Properties of Control Software[END_REF]. Results from control engineering [START_REF] Blind | Towards Networked Control Systems with guaranteed stability: Using weakly hard real-time constraints to model the loss process[END_REF] could even show Lyapunov stability of the feedback control of an unstable plant that runs in open loop from time to time due to failures. The modern concept of weakly-hard real-time (WHRT) computing systems [START_REF] Bernat | Weakly Hard Real-Time Systems[END_REF] takes this reality into account. The timing guarantees for a WHRT computing system are formulated for every task in the task set in the following manner: A task is guaranteed not to miss more than m deadlines in any sequence of k consecutive executions even in the worst case. Note that this precise statement of the worst-case distribution pattern of deadline misses distinguishes weakly-hard from soft real-time computing systems.

The objective of our work is to explore the timing impact of nite queues. Our hypothesis is that nite queues can serve as a mean to e ectively limit overload peaks. According to our model, if a ready queue of a task is full, any new incoming job is rejected while accepted jobs are always run to completion. The disburdening of the system by rejecting jobs in overload conditions leads to an improved schedulability of accepted jobs. Ideally, the rejection mechanism frees the system from jobs, which would otherwise anyhow miss their deadline due to long waiting times in the queue. If nite queue capacity succeeds in the e cient limitation of overload peaks, then the number of jobs which become schedulable under reduced service demand is larger than the number of rejected jobs. Consequently, WHRT guarantees can be improved, and that at signi cantly smaller queue sizes than required for over ow-free behavior.

Beyond this very desirable property, the virtue of such a workload limiting mechanism would be that it can be realized at a minor implementation impact: Discarding of workload is implicitly realized by queue over ow, no monitoring or task abortion is required. The original scheduling algorithm can still be employed, and nite queues are already system reality: In a context where processing resources are micro-controllers or similar, nite ready queues restrict the number of jobs that can be activated at a time. For instance the size of a ready queue may be speci ed by the real-time operating system (RTOS) standard, as in the case of the automotive OSEK RTOS standard which allows for a task of the basic performance class only one activated job at a time. In a network context, nite queues result from limited storage capacity for packets in switches.

The analysis method presented in this paper is to the best of our knowledge the rst one which is able to give (a) worst-case response times guarantees as well as (b) WHRT guarantee for each task which is executed on a computing system with nite queues. By WHRT guarantee for a task, we understand in this work an upper bound m on the number of generalized deadline misses in any consecutive sequence of k executions of this task. We de ne a generalized deadline miss as either a computational result produced by a task after its given deadline, or a missing computational result which should be produced by the task but is not due to the rejection of a job. Note here the di erence to current research, where only conventional deadline misses have been quanti ed by WHRT guarantees due to the assumption of in nite queues.

Our approach is based on typical worst-case analysis (TWCA) [START_REF] Xu | Improved Deadline Miss Models for Real-Time Systems Using Typical Worst-Case Analysis[END_REF], a veri cation method for WHRT systems with a single processing resource and static priority scheduling. TWCA can principally be included in a compositional performance analysis framework to cover multi-resource processing platforms. TWCA assumes that in a typical workload scenario, where all tasks are activated according to their typical activation pattern (e.g. periodic pattern), no deadline misses occur. Only in the rare non-typical workload scenarios, where a subset of tasks has additional overload (e.g. sporadic) activations, are some deadlines missed and TWCA provides WHRT guarantees. In case of nite queues, previous approaches to compute the required TWCA input parameters are not su cient. In particular, we show in this paper how to derive the accepted workload over time by using techniques from operations research.

At this point we would like to provide an outlook on the experimental results. Surprisingly, the obtained worst-case response times and WHRT guarantees did not systematically pro t from nite queue sizes. As will be explained in detail in the evaluation section, this is primarily caused by the characteristics of the worstcase system behavior under which the upper timing bounds are derived. The experiments give a novel insight into system behavior under nite queues, and show that -if not a systematic improvement of worst-case WHRT guarantees -nevertheless a trade-o between obtainable WHRT guarantees and queue sizes is possible.

In the following, we rst give an overview of related work followed by a detailed description of the system model. Then we successively determine the required TWCA input variables starting with workload arrival curves and then moving to busy period computations including the derivation of worst-case response times. Subsequently we apply TWCA and evaluate the behavior of systems with nite queue capacity in overload conditions.

RELATED WORK

The handling of overload conditions in real-time systems has been a research topic since the 1990s. Both scheduling algorithms and scheduling analysis have focused on this. Baruah et al. [START_REF] Baruah | On the competitiveness of on-line real-time task scheduling[END_REF] and Buttazzo et al. [START_REF] Buttazzo | Value vs. deadline scheduling in overload conditions[END_REF] introduced value-based performance metrics for evaluating the behavior of scheduling algorithms in overload conditions. Their system model assumes that each job contributes at its completion a "value" to the system. Late completion generally reduces signi cantly the value of a job. The objective of value-based scheduling is to maximize the cumulative value contributed by n jobs. Value constraints assure that it is prohibitively expensive to complete hard real-time jobs after their deadline. Thus, hard realtime jobs are typically scheduled at the expense of rm and soft real-time tasks using appropriate priority assignments as well as on-line or o -line acceptance schemes [START_REF] Buttazzo | Value vs. deadline scheduling in overload conditions[END_REF][START_REF] Giorgio | Adding robustness in dynamic preemptive scheduling[END_REF][START_REF] Koren | Skip-over: Algorithms and complexity for overloaded systems that allow skips[END_REF]. A related line of research (e.g. [START_REF] Umamaheswari | Tardiness bounds under global EDF scheduling on a multiprocessor[END_REF]) derives bounds on the tardiness of tasks, where tardiness is de ned as the di erence between completion time and deadline of a task. In the context of soft real-time tasks bounded tardiness is acceptable as long as in the long term each task may utilize the processor as speci ed.

Based on network calculus, a few works analyze systems with losses. The computed guarantees are upper bounds on the packet loss rates in the presence of tra c clippers, which are tra c shapers with zero bu ering capacity [START_REF] Cruz | An analysis of tra c clipping[END_REF]. The authors of [START_REF] Chang | A time varying ltering theory for constrained tra c regulation and dynamic service guarantees[END_REF] derive an optimal tra c regulator with constraints on maximum tolerable delay and maximum bu er size, which generates output tra c conforming to a subadditive tra c envelope and minimizes the number of discarded packets.

The concept of WHRT systems [START_REF] Bernat | Weakly Hard Real-Time Systems[END_REF] allows to apply a di erent scheduling approach in overload conditions. WHRT jobs tolerate by de nition a bounded number of deadline misses, where the tolerance is speci ed by (m, k )-constraints. Consequently scheduling algorithms have been proposed which attempt to guarantee or guarantee by design (m, k )-constraints of weakly-hard tasks and apply best e ort for soft real-time tasks e.g. [11] [3]. TWCA [START_REF] Xu | Improved Deadline Miss Models for Real-Time Systems Using Typical Worst-Case Analysis[END_REF] veri es (m, k )-constraints for static priority scheduling on single processing resources.

In this paper, we concentrate on the analysis of WHRT systems using a xed priority scheduling with the special property of nite queues. The timing analysis for such a setting is more complex than in previous works because [START_REF] Baruah | On the competitiveness of on-line real-time task scheduling[END_REF] the (m, k )-guarantees are not inherent in the design of the scheduling algorithm and (2) the limited queue capacity represents a nonlinearity in system behavior which has not been treated so far. However, the system model is realistic and results are relevant for the behavior of industrial real-time systems in overload conditions. We compute both maximum response times and frequency of deadline misses for each task in the system.

SYSTEM MODEL

A system consists of one processing resource which schedules a task set T according to the static priority preemptive (SPP) policy. The task set T = τ j |1 ≤ j ≤ N consists of N independent tasks. Each task τ j is characterized by its static priority π j , its minimum and maximum workload-based arrival curve α -,∞ i (∆t ), α +,∞ i (∆t ) cf. Sec. 3.1, the lower and upper bound of its execution time C - j , C + j , and its relative deadline d i . The priority π j of each task τ j ∈ T corresponds to its index j and is therefore unique. Smaller priority indices mean higher priority. The task set T i = τ j |1 ≤ j ≤ i includes the i tasks with the i highest priorities in the task set T . The system is said to have nite queue capacity if for every task τ j ∈ T the maximum accepted amount of pending workload is limited to b j = s j • C + j due to the nite number of slots s j in the queue. The system is said to have in nite queue capacity if for every task τ j ∈ T the accepted amount of pending workload is not limited. The workload of the qth job τ i (q) is said to be accepted by the system if a free queue slot is available. Otherwise, the job τ j (q) is discarded and the workload of τ j (q) is said to have been rejected by the system.

Workload-based arrival curves

We use workload-based arrival curves to describe the workload imposed by a task on the system. In contrast to previous work, our de nition of the workload-based arrival curves takes the queue capacity of the system for pending workload into account and only considers accepted workload as incurred workload.

De nition 3.1. The workload-based arrival curve α i [s, t ) of a task τ i with s ≤ t and s, t ∈ R describes the accepted workload of τ i between s and t taking into account the queue capacity of the system and is bounded by

α - i (∆t ) ≤ α i [s, t ) ≤ α + i (
A - i (∆t ) ≤ A i [s, t ) ≤ A + i (∆t ).
In the following, whenever the queue capacity is assumed to be in nite, we add the superscript ∞ to the corresponding (cumulative) workload-based arrival curves.

It is important to realize that for the case of nite queue capacity, the variables α i [s, t ) and A i [s, t ) = i j=1 α i [s, t ) as well as their lower and upper bounds are not known. There is some computational e ort required to derive them from the information provided by the system model cf. Section 4. This is a contrast to α ∞ i (∆t ) and

A ∞ i (∆t ) = i j=1 α ∞ i (∆t )
, which are usually either given or can be easily derived.

Service curve, remaining service, and processed, pending workload

While in the previous subsection the incurred workload of tasks has been described, this subsection introduces concepts which characterize the processing behavior of the system.

De nition 3.3. The service curve β[s, t ) := ts, or equivalently β (∆t ) := ∆t, indicates the available processing time in any time interval ∆t of length ts with s ≤ t and s, t ∈ R.

De nition 3.4. The remaining service for task τ i , denoted as γ i [s, t ), is the amount of time in [s, t ) with s ≤ t and s, t ∈ R during which the processor is not used by higher priority tasks such that its service can be assigned to task τ i . De nition 3.5. The processed workload of task τ i , denoted as proc i [s, t ), corresponds to the amount of time that task τ i occupies the processor in the time interval [s, t ) with s ≤ t and s, t ∈ R.

De nition 3.6. The pending workload of task τ i denoted as pend i (t ) is the amount of accepted workload that has been requested to be processed by a task τ i but has not yet been processed at instant t taking into account the queue capacity of the system. The de nition of the processed [pending] workload of a task τ i can be adapted to a set of tasks T i analogous to Def. 3.2. The cumulative processed [pending] workload of the task set

T i is then denoted as Proc i [s, t ) [Pend i (t )] .
Again we add the superscript ∞ for variables corresponding to the in nite queue capacity assumption. Lower, resp. upper, bounds are additionally indexed with the superscript -, resp. +.

COMPUTATION OF WORKLOAD BOUNDS UNDER FINITE QUEUES 4.1 Motivational Example

In the well-known case of in nite ready queues, when workload is always accepted, the maximum cumulative workload-based arrival curve A ∞,+ i (∆t ) is computed by the superposition of the maximum

workload-based arrival curves α ∞,+ j (∆t ) of each task τ j in the task set T i A ∞,+ i (∆t ) = i j=1 α ∞,+ j (∆t ). (1)
In the case of nite ready queues, the accepted workload of each task τ j ∈ T i depends not only on the processing request of task τ j itself but also on the demand of tasks with higher priority. All three factors determine the queue lling of the queue of task τ j . Therefore A + i (∆t ) cannot be computed by simple superposition of independent α +,∞ j (∆t ) as in the case of in nite queue capacity. Let us illustrate this important property with an example.

Example 4.1. We assume an SPP-scheduled resource. The task set T = {τ 1 , τ 2 , τ 3 , τ 4 } is schedulable if no sporadic overload activations are present. The queues are so dimensioned that if no overload is present, all task instances will be accepted.

priorities π 1 = 1, π 2 = 2, π 3 = 3, π 4 = 4 periods T 1 = T 2 = 4, T 3 = 8, T 4 = 16 deadlines d 1 = 4, d 2 = 8, d 3 = 8, d 4 = 16 WCETs C + 1 = 1.5, C + 2 = 1, C + 3 = 2, C + 4 = 0.5 queues b 1 = 2C + 1 , b 2 = C + 2 , b 3 = C + 3 , b 4 = C + 4
Figure 1a illustrates the classical worst case with in nite ready queues. The overload is represented by one additional sporadic overload activation of task τ 1 (marked in red). The resource demand of each task τ j behaves according to α ∞,+ j (∆t ) = C + j • ∆t /T j . As a consequence of overload, task instance τ 3 (1) misses its deadline. Figure 1b shows the same system behavior in the case of nite ready queues. Contrary to the previous situation, only a part of the resource demand is accepted w.r.t. some tasks. Task instance τ 3 (2) is rejected because the queue is still blocked by τ 3 (1). In Figure 1c, the situation is slightly di erent. The di erence to the scenario in Figure 1b is that task instance τ 2 (2) only demands half of its WCET. Consequently task τ 3 becomes schedulable. Figure 1d compares the cumulative accepted workload of the task set T over the time interval [0, 16). As can be seen, at a given point in time either scenario 2 or scenario 3 or both scenarios produce the larger cumulative accepted workload demand A 4 [0, t ). For the time interval [0, 8), scenario 2 produces the absolute worst case since

A 4 [0, t ) = A ∞,+
4 (∆t ). Figure 1c shows that the workload curves of the two scenarios overtake each other and that at di erent points in time a di erent scenario represents the worst case w.r.t. the cumulative workload-based arrival curves.

The above example illustrates the fact that it is in general not possible to derive, for a given task set, a single scenario which produces the maximum cumulative load-based arrival curve A i (∆t ) for all ∆t such that we could de ne A + i (∆t ) = A i (∆t ). We must therefore nd an envelope over all possible cumulative workloadbased arrival curves so that A + i (∆t ) is an upper bound. Of course, A +,∞ i (∆t ) is a possible solution yet it is not tight and we want to improve over it.

Computing A + i (∆t ) for a given interval

In this section we present an inductive calculation rule to bound from above the cumulative workload-based arrival curve A i [s, t ) for an arbitrary time interval [s, t ) of length ∆t = t -s where A i-1 [s, t ) is assumed to be known. First remember that by de nition

A i [s, t ) = A i-1 [s, t ) + α i [s, t ). ( 2
)
The so far unknown accepted resource demand α i [s, t ) can be derived as follows. The balance equation

pend i (t ) = pend i (s) + α i [s, t ) -proc i [s, t ). ( 3
)
expresses that the workload of task τ i that is pending at t is the sum of the workload pending at s and the workload incoming during the time interval [s, t ) minus the workload processed within [s, t ). Eq. 3 can now be used to expand the calculation rule given in Eq. 2.

A i [s, t ) = A i-1 [s, t ) + proc i [s, t ) + pend i (t ) -pend i (s) (4) P 1.
Our objective is to maximize

A i-1 [s, t ) + proc i [s, t ) + pend i (t ) -pend i (s)
(5) The maximal value of A i [s, t ) thus obtained can then be used to de ne A + i (∆t ) where ∆t = ts, i.e. the maximum accepted cumulative workload demand in any time interval of length ∆t. The constraints de ned in Eq. 6, 7, 8, 10, and 14 restrict the solution.

In the following, we detail the above mentioned constraints.

C1 Incoming workload. The cumulative workload-based arrival curve

A i-1 [s, t ) in [s, t ) is bounded by A - i-1 (t -s) ≤ A i-1 [s, t ) ≤ A + i-1 (t -s). (6)
Also, we know that

α i [s, t ) ≤ α ∞,+ i (t -s), which corresponds after expansion of α i [s, t ) to proc i [s, t ) + pend i (t ) -pend i (s) ≤ α ∞,+ i (t -s). ( 7
)
Note that with the given constraints on incoming workload only, Problem 1 could be solved yet this would result in the trivial solu-

tion A i-1 [s, t ) = A + i-1 (t -s).
C2 Pending workload. The pending workload is for any instant restricted by the nite queue capacity of task τ i . For the starting value pend i (s), we have

0 ≤ pend i (s) ≤ b i . (8)
For every subsequent instant s < t * ≤ t, the pending workload pend i (t * ) follows directly from the initial queue lling pend i (s) and the de ned system behavior. Suppose that at t * -ϵ an amount si of the queue slots s i is occupied, and immediately afterwards at t * a number n of task instances τ (q 1 ), τ (q 2 ), . . . , τ (q n ) with execution demand C i (q) are activated. The system will admit as many of the n ordered task instances as free queue space is available

pend i (t * ) =          pend i (t * -ϵ ) if n = 0 ∨ si = s i pend i (t * -ϵ ) + q 1 +M -1 q=q 1 C i (q) else. (9)
where M = max {m | m ≤ n ∧ m ≤ s isi }, i.e. the largest number of task instances that t into the queue.

Note that the constraint for pending workload in Eq. 9 is nonlinear and has to be veri ed for every t * with s < t * ≤ t. Therefore, we relax the constraint in Eq. 9 into

0 ≤ pend i (t ) ≤ b i . ( 10
)
such that with Eq. 8 and 10 the limited queue size is enforced at the beginning and end of the time interval [s, t ). Applying the the queue constraint only twice instead at each activation of task τ i can only reduce the amount of rejected workload. Furthermore, a continuous kind of workload clipping is modeled which ignores the slot organization of the queue. Continuous workload clipping always rejects less or equal workload than the discarding of discrete task instances because also "parts" of task instances can be accepted. Thus the constraint relaxation delivers a safe upper bound on the accepted workload.

C3 Processed workload. The processed workload proc i [s, t ) depends on the remaining service γ i [s, t ) and the processing request of task τ i , where the latter is given by the pending workload pend i (s) at s and the incoming accepted processing request

α i [s, t ) ≤ α ∞ i .
It is the minimum of the remaining service and the accepted processing request since not more than the remaining service but also not more than the accepted workload request can be processed in [s, t ). In order to simplify the constraint, we bound the processed workload proc i [s, t ) from above by the remaining service γ i [s, t ):

proc i [s, t ) = min γ i [s, t ), pend i (s) + α i [s, t ) ≤ γ i [s, t ). ( 11
)
The remaining service γ i [s, t ) has been derived [START_REF] Wandeler | Modular performance analysis and interface-based design for embedded real-time systems[END_REF] as

γ i [s, t ) = sup s ≤t * ≤t {0, β[s, t * ) -A i-1 [s, t * ) -Pend i-1 (s)} (12)
where A i-1 [s, t * ) + Pend i-1 (s) is the accepted workload of higher priority tasks. We bound the remaining service from above by

γ i [s, t ) ≤ γ + i [s, t ) = sup s ≤t * ≤t {0, β[s, t * ) -A i-1 [s, t * )}. (13)
for simpli cation. Thus, a simpli ed constraint which upper-bounds the processed workload proc

i [s, t ) is 0 ≤ proc i [s, t ) ≤ γ + i [s, t ). ( 14
) P 2. Problem 1
does not yet correspond to a standard ILPproblem due to the involved constraint for processed workload in Eq. 14. The upper bound of proc i [s, t ) depends on the curve A i-1 and not only the value A i-1 [s, t ). We strive in the following to transform Eq. 14 into an ILP constraint, so that the optimization problem with the objective function given in Eq. 4 is then constrained by (Eq. 6, 7, 8, 14, 10 ) and (Eq. 30, 31, 32, 33, 34, 35, 36).

The constraint in Eq. 14 which we repeat here

0 ≤ proc i [s, t ) ≤ γ + i [s, t ) = sup s ≤t * ≤t {0, β[s, t * ) -A i-1 [s, t * )} (15)
prevents the optimization from being treated as a linear problem. The reason is that γ + i [s, t ) is a nonlinear function and this in the curve A i-1 (not in the optimization variable A i-1 [s, t )!). In order to simplify the constraint [START_REF] John P Lehoczky | Fixed priority scheduling of periodic task sets with arbitrary deadlines[END_REF], it is our intention to

(Step 1): bound γ + i [s, t ) by a function Γ i in the variable A i-1 [s, t ) -not the curve A i-1 -such that γ + i [s, t ) ≤ Γ i (A i-1 [s, t )). (16)
(

Step 2): over-approximate the nonlinear decreasing function Γ i (A i [s, t )) by a step function. The step function can be encoded by the weighted sum of 0-1-integer variables. This transforms the optimization problem in a linear integer programming (ILP) problem which can be handled by standard methods. (Step 1) To provide a solution for (Step 1), we need to nd the cumulative workload curve Ãi-1 which maximizes the supremum expression in Eq. 15 and goes through the given value

A i-1 [s, t ). The function Γ i (A i-1 [s, t ))
, indicating an upper bound of the remaining service, is therefore

Γ i (A i-1 [s, t )) = sup s ≤t * ≤t {0, β[s, t * ) -Ãi-1 [s, t * )} (17)
where the argument

A i-1 [s, t ) of Γ i refers to the constraint Ãi-1 [s, t ) = A i-1 [s, t ).
In Lemma 4.2, we rst present a de nition of Ãi-1 and show that this curve has some required properties. In the subsequent Theorem 4.3, we show that Ãi-1 actually maximizes the supremum expression in Eq. 15 for a given value

A i-1 [s, t ). L 4.2. The cumulative load-based arrival function Ãi-1 [s, t * ) in variable t * with 0 ≤ s ≤ t * ≤ t is de ned as Ãi-1 [s, t * ) = (18)
     0 for s ≤ t * ≤ s + (t -s) -t min A i-1 [s, t ) -A + i-1 (t -t * ) for s + (t -s) -t min ≤ t * ≤ t
where

A i-1 [s, t ) = const . (19) A - i-1 (t -s) ≤ A i-1 [s, t ) ≤ A + i-1 (t -s) (20)
t min = min σ | A + i-1 (σ ) = A i-1 [s, t ) . (21)
We want to show that Ãi-1 [s, t * ) is bounded by

0 ≤ Ãi-1 [s, t * ) ≤ A + i-1 (t * -s), (22)
and ful lls the constraint

Ãi-1 [s, t ) = A i-1 [s, t ). (23)
P . We rst verify the lower and upper bound given in Eq. 22. For the interval s ≤ t * ≤ s + (ts) -t min , Eq. 22 is satis ed because Ãi-1 [s, t * ) = 0 . For the interval s + (ts) -t min ≤ t * ≤ t, the upper bound is guaranteed since

A i-1 [s, t ) -A + i-1 (t -t * ) ≤ A + i-1 (t -s) -A + i-1 (t - t * ) ≤ A + i-1 (t * -s).
The lower bound is also guaranteed since

A i-1 [s, t ) -A + i-1 (t -t * ) ≥ A i-1 [s, t ) -A + i-1 (t min ) = 0.
That the constraint 23 is met by the function Ãi-1 can be shown by substituting t * by t in Eq. 18 and considering the fact that A + i-1 (0) := 0.

0 ≤ Ȃi-1 [s, t * ) ≤ A + i-1 (t * -s) (24) Ȃi-1 [s, t * ) = A i-1 [s, t ) (25)
with

A - i-1 (t -s) ≤ A i-1 [s, t ) ≤ A + i-1 (t -s) AND maximizes the expression sup s ≤t * ≤t {0, β[s, t * ) -Ȃi-1 [s, t * )}. (26)
P . The function Ãi-1 ful lls the given constraints (24, 25), this has been shown in Lemma 4.2. The function Ãi-1 also maximizes the supremum expression sup s ≤t * ≤t {0, β[s, t * ) -A i-1 [s, t * )}, if there is no other left-continuous step function Ȃi-1 ful lling the constraints (24, 25) which is at any instant s ≤ t * ≤ t smaller than Ãi-1 . In the interval s ≤ t * ≤ s + (ts) -t min , we have by de nition Ãi-1 [s, t * ) = 0 so that Ãi-1 ≤ Ȃi-1 is true. The time interval t min = min σ |A + i-1 (σ ) = x is the shortest time interval required for any curve Ȃi-1 to grow up to the value x. This means that any curve Ȃi-1 ful lling (24, 25) has to be non-zero starting at the latest from s + (ts) -t min .

In the time interval s + (ts) -t min ≤ t * ≤ t, the de nition of Ãi-1 [s, t * ) ensures that load is introduced as late possible. This due to the fact that A + i-1 (∆t ) is by de nition a subadditive load function. By horizontally and vertically mirroring A + i-1 (∆t ) for 0 ≤ ∆t ≤ t min , a load curve with the steepest possible increase in growth rate over time is created in this interval cf. Figure 2. This mirrored function de nes the value domain in the interval s

+ (t -s) -t min ≤ t * ≤ t of Ãi-1 , since Ãi-1 [s, t * ) = x -A + i-1 (t -t * ) for s + (t -s) -t min ≤ t * ≤ t.
This means no other curve Ȃi-1 can increase later than Ãi-1 , which proves that ∀t * : Ãi-1 [s, t * ) ≤ Ȃi-1 [s, t * ).

(Step 2)

The upper bound of the remaining service Γ i (A i-1 [s, t )) is a nonlinear but monotonically decreasing function. To be able to formulate the optimization problem as an integer linear programming (ILP) problem, Γ i (A i-1 [s, t )) is approximated from above by a step function with M steps as shown in Figure 3. Let A (m) i-1 with 1 ≤ m ≤ M + 1 de ne a uniformly discretized set of possible values

for A i-1 [s, t ) A (m) i-1 = A - i-1 (t -s) + m -1 M • A + i-1 (t -s) -A - i-1 (t -s) . (27) If A (m) i-1 < A i-1 [s, t ) ≤ A (m+1) i-1 then the step size is Γ i (A (m) i-1
). This approximation can be formalized by the following constraints

ξ m • A i-1 [s, t ) -A (m) i-1 • ξ m ≥ 0 (28) -ξ m • A i-1 [s, t ) + A (m+1) i-1 • ξ m ≥ 0 (29) M m=1 ξ m = 1 (30) γ + i [s, t ) ≤ M m=1 ξ m Γ i (A (m) i-1 ). (31)
where (28, 29) determine the interval in which A i-1 [s, t ) falls. Eq. (30) marks this interval by setting the corresponding 0-1-integer variable to 1, and Eq. 31 selects the step size. In Eqs. (28, 29) the product of the continuous variable A i-1 [s, t ) and the integer variable ξ m appears. For linearization, the product can be replaced by an auxiliary continuous variable Ξ m so that

Ξ m -A (m) i-1 • ξ m ≥ 0 (32) -Ξ m + A (m+1) i-1 • ξ m ≥ 0 (33)
if the following additional constraints are introduced [START_REF] Williams | Model building in mathematical programming[END_REF] Ξ

m -A (m+1) i-1 • ξ m ≤ 0 (34) -A i-1 [s, t ) + Ξ m ≤ 0 (35) A i-1 [s, t ) -Ξ m + A (m+1) i-1 • ξ m ≤ M ν =1 A (ν +1) i-1 • ξ ν . (36)
We have thus found that the complete optimization problem can be described by the objective function given in Eq. 4, and the constraints (Eq. 6, 7, 8, 14, 10 ) as well as (Eq. 30, 31, 32, 33, 34, 35, 36).

Computing A + i (∆t ) Over a Sequence of Intervals

In order to construct the curve A + i (∆t ) over time, the computation of the optimization problem has to be performed repeatedly for the time intervals ∆t ν which are integer multiples of the discretization time step ∆τ ν ∈ N :

∆t ν = ν • ∆τ . ( 37
)
The time step is preferably chosen according to the system tick or, respectively, the smallest time constant of the system. If A + i (∆t ν ) is computed iteratively over increasing time intervals, then we know that workload which has de nitely been rejected in a previous time interval cannot reappear in a subsequent time interval:

A + i (∆t ν ) ≤ A +,∞ i (∆t ν ) -R(∆t ν -1 ) (38)
where R(∆t ν -1 ) is the amount of workload which is de nitely rejected in the time interval ∆t ν -1

R(∆t ν -1 ) = max ν A +,∞ i (∆t ν -1 ) -A + i (∆t ν -1 ) . ( 39
)
The constraint in Eq. 38 couples the individual optimization problems for each time interval ∆t ν .

Reduction of Computational Complexity.

The maximum time interval ∆t ν that needs to be computed corresponds to the largest representative time window needed for response time computation. According to [START_REF] John P Lehoczky | Fixed priority scheduling of periodic task sets with arbitrary deadlines[END_REF], this is the largest level-i busy window BW i of the investigated task set.

De nition 4.4.

A level-i busy window BW i , resp. BW ∞ i , is the maximal time interval during which the processing resource is busy with tasks having an equal or higher priority than task τ i in the presence of nite, resp. in nite, queue capacity.

The maximum level-i busy window is known to correspond the earliest intersection between the maximum cumulative load-based arrival curve and the service curve because this is the rst time when the accepted workload and the available service equal each other and the resource becomes idle again. This principle can be expressed by the following xed-point equation

A + i (BW i ) = β (BW i ) resp. ( 40
) A ∞,+ i (BW ∞ i ) = β (BW ∞ i ). ( 41
)
If we assume that a reasonable time step is in the order of ∆τ = 10 µs and the largest level-i busy window BW i is in the order of 1 . . . 1000 ms, then 100 . . . 100 000 small ILP problems have to be solved. This is prohibitively costly. A powerful mean to reduce the number of ILP problems to be solved, is a heuristic which indicates if workload rejection is unlikely. We assume for the computation of A + i (∆t ν ) that the queue capacity is su cient if the maximum utilization U i incurred by T i in the considered time interval, i.e.,

U i (∆t ν ) = A +,∞ i (∆t ν )/∆t ν is below a certain utilization threshold U i,t h . The utilization threshold is heuristically set to U i,th = 1.2. This means if A + i (∆t ν -1
) is known and U i (∆t ν ) < U i,t h , then we immediately write

A + i (∆t ν ) = A + i-1 (∆t ν ) + (α +,∞ i (∆t ν ) -α +,∞ i (∆t ν -1 )). ( 42
)
We also assume if no new event occurs in the current time interval ∆t ν compared to the previous one ∆t ν -1 , no further workload rejection occurs. The heuristic delivers always a safe upper bound for A + i (∆t ν ) because the amount of accepted workload can only be overestimated by assuming su cient queue capacity. In our experiments, we had to solve approximately 15-150 optimization problems per system, depending on the workload, with a run time of several seconds.

WORST-CASE RESPONSE TIME ANALYSIS

The worst-case response time W CRT ∞ i for task τ i in case of in nite queue capacity can be precisely computed since a single worst-case scenario, captured in BW ∞ i , is known in detail. The derivation of W CRT ∞ , i.e. the worst case response time of a task τ i under the SPP scheduling policy and in the presence of su cient queue capacity, is based on [START_REF] Tindell | An extendible approach for analyzing xed priority hard real-time tasks[END_REF]. Due to the fact that there is not a single worst-case scenario for all times w.r.t. to the response time in case of nite ready queues and queue over ow as described in Example 4.1, it is not possible to determine the W CRT i of a task τ i on the basis of a concrete busy window as in the case of in nite ready queues. The only available information on the "worst-case" busy window, which has been constructed from the overestimated A + i , is its maximum length BW i see 41. Therefore, we bound W CRT i as speci ed in Theorem 5.1. T 5.1.

W CRT i = min{BW i , W CRT ∞ i , b i + A + i-1 (W CRT i )} (43)
P . No worst-case response time W CRT i can be larger than the longest busy window BW i since by de nition a busy window BW i starts with an activation of task τ i only closes if no pending workload of task τ i is left. Therefore BW i is a safe upper bound for W CRT i .

Alternatively, the worst-case response time of a task τ i can be computed if the following is known: (1) the maximum execution demand C + i of a task instance τ i (q), and ( 2) the maximum interference that task instance τ i (q) sees until its termination. The interference is caused by the execution of tasks with higher priority but also by task instances of task τ i which haven been activated before τ i (q) and are not processed yet. The maximum pending workload of task τ i is the queue size b i , while the maximum higher priority interference is A + i-1 (W CRT i ). Therefore, a safe upper bound on the W CRT i in case of nite queue capacity is

W CRT i = b i + A + i-1 (W CRT i ).
Note that this is an over-estimation because it is assumed that a full queue coincides with the maximum higher priority interference. Finally it is known that the worst-case response time W CRT ∞ i will always be equal or larger than W CRT i because the latter is derived without any discarding of pending workload. Since it is not known for a given data set which bound approach delivers the tightest result, the in mum of all three safe upper bounds is introduced.

TYPICAL WORST-CASE ANALYSIS

TWCA as de ned in [START_REF] Xu | Improved Deadline Miss Models for Real-Time Systems Using Typical Worst-Case Analysis[END_REF] derives formal weakly-hard guarantees for every task τ i in an SP(N)P-scheduled task set assuring that no more than m deadlines in any sequence of k consecutive executions of a task τ i are missed. In this section, we extend the veri cation capability of TWCA to weakly-hard guarantees of generalized deadline misses considering systems with limited queue capacity.

TWCA assumes that the system under analysis has a typical conguration which is schedulable. Deadline misses are only caused when additionally so called overload activations occur. For instance, a given system may be schedulable if all tasks are activated periodically but additional sporadic activations may induce overload. The method states that there is a maximal but limited time window ∆T j→i k during which overload activations of a task τ j can have an impact on k consecutive instances of task τ i where with j ≤ i. This time window is composed in case of an SPP-scheduled system according to the following equation

∆T j→i =      BW i + δ + i (k ) i = j BW i + δ + i (k ) + W CRT i i j. (44)
The term δ + i (k ) describes the longest possible time window in which exactly k activations of task τ i can be observed. The term BW i is the longest interval before δ + i (k ) during which overload can impact the rst instance of task τ i in the k sequence. The term W CRT i is the longest time interval after δ + i (k ) during which overload can impact the last instance of task τ i in the k sequence due to preemption.

With the maximum overload activation event arrival curve η j o er (∆t ) of task τ j , the maximum number of overload activations in the interval ∆T ). Each overload activation can at most cause N i deadline misses of task τ i . So an upper bound for the maximum number of deadline misses in any sequence of k consecutive executions of a task τ i (also called deadline miss model DMM) is 1

dmm i (k ) = N i • i j=1 η j o er (∆T j→i k ). (45)
For the case of nite queue capacity, this basic TWCA principle remains valid if (1) the input parameters are re-computed under this new restriction as done above, and (2) the schedulability condition is adapted to the detection of generalized deadline misses as following. In the case of nite queue capacity and generalized deadline misses, a task τ i is schedulable if neither a deadline miss or a queue over ow is possible. As (3)rd requirement, we ask for a queue dimensioning that is su cient if a task τ i behaves according to its timing restriction. I.e. if the worst-case response time of τ i is smaller than the required deadline, no queue over ow should take place.

The nite queue capacity impacts the DMM dmm i (k ) compared to the case of in nite queues as follows: For the impact interval of an overload activation, we have

∆T j→i k ≤ ∆T j→i,∞ k since BW i ≤ BW ∞ i and W CRT i ≤ W CRT ∞ i .
The e ect decreases with increasing k. With regard to N i and N ∞ i , there is no generally true order relation.

N ∞

i corresponds to the number of jobs of task τ i which miss their deadlines in the longest level-i busy window [START_REF] Xu | Improved Deadline Miss Models for Real-Time Systems Using Typical Worst-Case Analysis[END_REF]. For nite queue capacity, we have indeed BW i ≤ BW ∞ i but a safe bound on N i equals the number of all jobs of task τ i in BW i . Consider e.g. task τ 3 Fig. 1b, where one overload activation causes 2 of 2 jobs in the level-3 busy window to experience a generalized deadline miss (a conventional deadline miss and a queue over ow). However, in the worst case with in nite queues depicted in Fig. 1a only 1 deadline is missed in BW ∞ i . The reason is that a queue over ow may reject a job, even if it would theoretically meet its deadline if accepted. In conclusion, whether or not

dmm i (k ) ≤ dmm ∞ i (k ) depends essentially on BW i /BW ∞ i .
1 A more re ned TWCA approach has been proposed by [START_REF] Xu | Improved Deadline Miss Models for Real-Time Systems Using Typical Worst-Case Analysis[END_REF] for in nite queue capacity. The concept cannot be immediately applied to nite queue capacity. We therefore use the basic approach for nite queues, and [START_REF] Xu | Improved Deadline Miss Models for Real-Time Systems Using Typical Worst-Case Analysis[END_REF] for in nite queues in our experiments.

EVALUATION

The performed experiments serve to test whether transient overload peaks can be reduced by nite queues due to the e ect of over ow. If so, the maximum busy windows and the worst-case response times will be shortened and the weakly-hard guarantees will be improved under nite queues compared to the case of in nite queues.

Experimental Setup

We have tested our overload analysis on embedded software systems which have characteristics as described in "Real World Automotive Benchmarks For Free" [START_REF] Kramer | Real world automotive benchmarks for free[END_REF]. The benchmark is suitable for our purpose since it de nes the timing properties of an automotive engine control application, which is typically marked by both a high static utilization and transient workload peaks caused by interrupts. Such industrial systems can often not be proven to have hard real-time properties in the worst case, but often WHRT properties are su cient due to functional robustness [START_REF] Tobuschat | System-level timing feasibility test for cyber-physical automotive systems[END_REF]. The benchmark addresses both single core and multicore architectures, and we selected the single core variant according to our system model. Basically, the single core variant can neglect communication overhead and scales workload.

The engine control application conforms to the AUTOSAR standard, and is structured into 10 periodically activated tasks with periods ranging from 1ms to 1000ms and implicit deadlines. Each task is a container for a set of runnable entities, i.e. a set of software functions which are executed in a row at each task activation. We scaled the total number of runnables R in the system from [1000, 1500] to [250,375] due to the use of a single core platform, and each task contains the de ned share of the total number of runnables. WCETs of runnables, which are then accumulated to the task WCET, are determined according to the rules de ned in the benchmark. Note that variability in the generated systems results from the total number of runnables and the runnable WCETs, the latter being extracted from a Weibull distribution. Tasks are scheduled according to the SPP scheduling algorithm, and priorities are assigned proportionally to the activation rate. Each task is of the basic conformance class such that it can only be preempted by tasks of higher priority, several concurrent activations of a task are not allowed. This means that each task has a ready queue with one slot. Task properties are summarized in Table 1.

The benchmark also speci es a high interrupt workload at top priorities, however, details on interrupt characteristics are scarce. It is known that interrupts sporadically activate some runnables, and that the overall interrupt-related utilization may reach up to 30%. Arbitrary event arrival curves are proposed to model the arrival pattern of activation events, yet none are indicated. We chose to add 8 interrupts service routines (ISRs), each consisting of two runnables with a runnable WCET of 10us. The ISRs have a sporadically bursty event arrival pattern [START_REF] Richter | Compositional Scheduling Analysis Using Standard Event Models: The SymTA-S Approach[END_REF], which is de ned by a set of 3 parameters. The outer period T out describes the minimum distance between any two bursts of interrupt events. A single burst contains at most b events, and the inner period T in describes the minimum distance between any two burst events. Those 8 ISRs are schedulable. The transient overload in the system is caused by an additional ISR with high worst-case workload containing 10 runnables. The parameters of the overload ISR, namely (1) the runnable WCET and (2) the characteristics of the sporadically bursty event arrival pattern, are added as controlled impact factors in the experiments.

As a tool for system generation we created pySMFF, which is a self-written version of System Models for Free (SMFF) [START_REF] Neukirchner | SMFF: System Models for Free[END_REF] in Python. The use of Python instead of Java eases scripting and integrates well with our analysis framework in Python. We generated 15 di erent systems according to the benchmark, which vary in the total number of runnables R and the runnable WCETs of the periodic tasks.

Experiments

In the following, we investigate the behavior of the described benchmark system with implicit deadlines for periodic tasks and one ready queue slot.

7.2.1 Rejected Workload. Finite queues are appear as a promising mean to disburden the system in overload conditions, since only a limited number of pending jobs per task is accepted at a time. The amount of rejected workload due to queue over ow is an insightful variable showing to which extent the system is guaranteed to be freed from workload when overload occurs. Therefore, we compute the di erence A ∞,+ i (∆t ) -A + i (∆t ) which indicates the amount of discarded workload in ∆t w.r.t. the task set T i when maximizing the accepted workload A i (∆t ). Maximizing the accepted workload corresponds to the worst case w.r.t. busy window, the response times, and the (m,k)-guarantees. In the considered benchmark system, it is the 1ms-task τ 10 which is most a ected by overload because the period of the task is comparable to the duration of the interrupt burst. Thus it is likely that a second job is activated before the rst job has terminated, and consequently the over ow mechanism becomes active. Figure 4a shows A ∞,+ 10 (∆t ) -A + 10 (∆t ) for ∆t = 10ms. Beyond this time interval, rejection is unlikely because the maximum utilization A ∞,+ 10 (∆t )/∆t approaches the overload-free behavior. We have observed, that tasks τ >10 experience no guaranteed rejection of workload in the worst case. The amount of guaranteed rejected workload A ∞,+ 10 (∆t ) -A + 10 (∆t ) is expected to depend on the parameters characterizing the overload peak, which are therefore varied in the experiments. Intuitively, the higher an overload peak is, the 2 Operating point of angle-sychronous task more workload has to be discarded. Increasing the runnable WCET of the overload ISR actually leads to a monotonic increase of discarded workload, this is illustrated in Fig. 4a. At the same time, we found that the amount of discarded workload is very sensitive to the activation pattern of overload events, cf. T in .

Considering Fig. 4a, the principal observation is, however, that the amount of rejected workload is surprisingly small in the worst case independent of the chosen overload parameters. W hy is that? The worst case w.r.t. busy window, the response times, and the (m,k)-guarantees occurs -as mentioned above -if as much workload as possible is accepted in a given interval of size ∆t. The optimization algorithm therefore selects the solution which rejects as little workload as possible. Often corner cases can be constructed, where queues are nearly full but rejection can just be avoided.

Reconsider the encouraging Scenario 2 illustrated in Fig. 1b, where workload rejection in case of full queues is e ective and signi cantly reduces, e.g., the busy window of task τ 4 compared to the classical worst case with in nite queue capacity in Fig. 1a. However, Scenario 3 in Fig. 1c di ers from the classical worst case in Fig. 1a only in the slightly shortened execution time of the 2nd job of task τ 2 . Rejection of jobs can be completely avoided in Scenario 3 despite the nite queue capacity. Consequently, the workloadbased arrival curves in Fig. 1d of the classical worst case with in nite queues and the Scenario 3 hardly di er. This means that nite queues can lead to signi cant workload rejection in some scheduling scenarios but do not have to in all high-load cases.

We generalize now this observation. The solution to the problem of maximizing the accepted workload A + i (∆t ) is to nd a scheduling scenario in ∆t which respects the constraints (i.e. allowed execution times, activation patterns), includes as much workload as possible and avoids queue over ow if possible. The less restrictive the constraints are, the easier it is to nd a scheduling scenarios which just avoid rejection. That is, a large ratio of (a) C + i and C - 7.2.2 Response Times and Deadline Miss Model. The behavior of a system, which is guaranteed to reject some workload while maximizing A i (∆t ), is shown in Table 4b. The table contains queue sizes, BWs, WCRTs and DMMs for all late tasks, and compares those values with the results for an identical system but with suciently sized queues. The busy window BW i is the basic information to compute the maximum response time W CRT i (Eq. 43) and the DMM dmm i (k ) (Eq. 45) for a given k. It could be reduced in all cases, but only for the 10ms task to a signi cant extent. Consequently, we obtain W CRT i ≤ W CRT ∞ i . The 10ms task can even meet its deadline under nite queue capacity due to the guaranteed workload rejection by higher-priority tasks. (Note that there are other analyzed systems, where the 10ms task does not pro t this much from rejection.) Let us now discuss the obtained DMMs for the nite queue capacity which do not all improve. For instance, the 1ms task and the 2ms tasks have even a worse DMM than in the case of in nite queues. This e ect is related to the factor N i in Eq. 45. N i counts the maximum number of both late and discarded jobs in BW i . As mentioned in Section 6, a safe and realistic upper bound on N i corresponds to the number of all jobs of τ i in BW i . q q q q q T_in=200 T_in=250 T_in=300 This can be larger than N ∞ i , which only counts the number of conventional deadline misses BW ∞ i . Therefore DMMs only pro t from nite queues, if BW i is signi cantly smaller than BW ∞ i such that fewer jobs are included in BW i than in BW ∞ i . From a scheduling perspective, this means that the discarding of jobs is compensated by the improved schedulability of other jobs of the same task. In our experiments, BW i is still relatively large compared to BW ∞ i , since little workload is guaranteed to be rejected. In conclusion, WHRT guarantees could not be improved by nite queues except for the 10ms task. Yet it is interesting to see that when increased DMMs are acceptable, the queue size could be divided by 2. This allows a trade-o between available queue sizes, and achieved timing guarantees. Such a trade-o is interesting, if it is important to use standardized queue sizes and/or if memory is expensive e.g. networks-on-chip.

CONCLUSION

In this work, we analyzed the worst-case timing behavior of weaklyhard real-time (WHRT) systems with nite ready queues. The analysis is, to the best of our knowledge, the rst one to provide worstcase response times as well as formal bounds on deadline misses and over ow losses for such systems. In particular, we investigated whether nite queues sizes can limit overload peaks due to the e ect of over ow such that the overall system schedulability is improved. We summarize now the lessons learned. Finite queues can principally limit the amount of accepted workload. However, often corner cases can be constructed where over ow can just be avoided or is small, so that in the worst case the workload-limiting of nite queues is weak. As a consequence, better worst-case timing guarantees than in the in nite queue case are rare as demonstrated by our use case of an engine control system. Still the analysis allows to formally explore the interesting trade-o between weakly-hard guarantees and costly queue sizes. In the future, we aim to identify and evaluate conditions additionally to the limited queue size, which make job dropping also in the worst case e cient for WHRT systems.

  Scenario 1: all task instances are activated simultaneously and demand their WCET; in nite queues Scenario 2: all task instances are activated simultaneously and demand their WCET; nite queues Scenario 3: all task instances are activated simultaneously and demand their WCET except τ 2 (2); nite queues Comparison of the cumulative workload-based arrival curves A 4 (t ) of Sc. 1 (solid black line), Sc. 2 (dashed red line), and Sc. 3 (dotted blue line). The bisector indicates the service curve.

Figure 1 :

 1 Figure 1: Challenges in determining a maximum cumulative arrival curve. A crossed-out activation arrow illustrates the discarding of a task instance, the lightning symbol indicates a deadline miss.

Figure 2 :

 2 Figure 2: Illustration of theorem proof. The blue dashed curve shows A + i-1 (∆t ) for 0 ≤ ∆t ≤ t min in [s + (ts) -t min , t ) and the red curve represents Ãi-1 in [s, t ).

T 4 . 3 .

 43 There is no other cumulative load-based arrival function Ȃi-1 than Ãi-1 as given in Lemma 4.2 which ful lls the constraints

Figure 3 :

 3 Figure 3: Over-approximation of Γ i (A i [s, t )) by a step function

i

  and (b) A ∞,+ i (∆t ) and A ∞,- i (∆t ) as well as (c) large queues favor rejection-free worst case corner cases.

  Discarded workload A ∞, + 10 (∆t ) -A + 10 (∆t ) over varying parameters of the overload ISR.

( b )

 b Results for two generated systems which di er in the queue capacity ( nite vs. in nite). The overload ISR is characterized by r unnW C ET = 30us, b = 5, T in = 250, T out = 500ms.

Figure 4 :

 4 Figure 4: Experimental results

  ) for any s and t such that ts = ∆t.The concept of quantifying the accepted workload of a task τ i can be adapted to a set of tasks T i .De nition 3.2. A cumulative workload-based arrival curveA i [s, t ) models the accepted workload incurred by the task set T i in the time interval [s, t ) with s ≤ t and s, t ∈ R taking into account the queue capacity of the system. The cumulative workload-based arrival curve A i [s, t ) is bounded by

	∆t )
	where α -i (∆t ) and α + i (∆t ) provide a lower and an upper bound on α i [s, t

Table 1 :

 1 Benchmark Data[START_REF] Kramer | Real world automotive benchmarks for free[END_REF] and Added ISRs

	Task	Prio. # Runn. Activation Pattern
	τ 1 -τ 8 : ISR	1 -8	2 b = 5, T in = 20us T out = 25ms
	τ 9 : Overload ISR	9	10 b = 5, T out = 500ms; Note:
			T in , r unnW C ET controlled
	τ 10 : 1 ms task	10	0.03R periodic
	τ 11 : 2 ms task	11	0.02R periodic
	τ 12 : 5 ms task	12	0.02R periodic
	τ 13 : 6.6 ms task 2	13	0.15R periodic
	τ 14 : 10 ms task	14	0.25R periodic
	τ 15 : 20 ms task	15	0.25R periodic
	τ 16 : 50 ms task	16	0.03R periodic
	τ 17 : 100 ms task	17	0.20R periodic
	τ 18 : 200 ms task	18	0.01R periodic
	τ 19 : 1000 ms task	19	0.04R periodic

ACM acknowledges that this contribution was authored or co-authored by an employee, contractor or a liate of a national government. As such, the Government retains a nonexclusive, royalty-free right to publish or reproduce this article, or to allow others to do so, for Government purposes only. RTNS '17, Grenoble, France © 2017 ACM. 978-1-4503-5286-4/17/10. . . $15.00 DOI: 10.1145/3139258.3139259

ACKNOWLEDGMENTS

This work has received funding from the German Research Foundation (DFG) under the contract number TWCA ER168/30-1.