2021  OriginalPaper  Chapter Open Access
4. On the Formalism and Properties of Timing Analyses in RealTime Embedded Systems
Authors: JianJia Chen, WenHung Huang, Georg von der Brüggen, KuanHsun Chen, Niklas Ueter
Publisher: Springer International Publishing
4.1 Introduction
4.2 Formal Analysis Based on Schedule Functions

σ( t) ≠ J _{j} for any t ≤ r _{j} and t > d _{j} and

, where is a binary indicator. If the condition holds, the value is 1; otherwise, the value is 0.

By the definition of the WCET of task τ _{i}, the actual execution time C _{i,j} of job J _{i,j} is no more than C _{i}, i.e., C _{i,j} ≤ C _{i}.

By the definition of the relative deadline of task τ _{i}, we have d _{i,j} = r _{i,j} + D _{i} for any integer j with j ≥ 1.

By the minimum interarrival time constraint, we have r _{i,j} ≥ r _{i,j−1} + T _{i} for any integer j with j ≥ 2.

By periodic releases, we have r _{i,1} = O _{i} and r _{i,j} = r _{i,j−1} + T _{i} for any integer j with j ≥ 2.

σ( t) ≠ J _{i,j} for any t ≤ r _{i,j} and t > d _{i,j},

, and

if σ( t) = J _{i,j}, then \(\sigma (t') \notin \left \{{J_{i,h}  h=1,2,\ldots ,j1}\right \}\), for any t′ > t and j ≥ 2.
4.2.1 Preemptive EDF

The actual execution time C _{i,j} of job J _{i,j} satisfies C _{i,j} ≤ C _{i}.

d _{i,j} = r _{i,j} + D _{i} for any integer j with j ≥ 1.

r _{i,j} ≥ r _{i,j−1} + T _{i} for any integer j with j ≥ 2.
4.2.2 Preemptive FixedPriority Scheduling Algorithms

\(R_k = \Delta _{\min }\) , if \(\Delta _{\min } \leq T_k\) , and

R _{k} > T _{k} , otherwise.

releasing the first jobs of the higherpriority tasks in hp( τ _{k}) together with a job of τ _{k} and

releasing the subsequent jobs of the higherpriority tasks in hp( τ _{k}) as early as possible by respecting their minimum interarrival times.

A critical instant for task τ _{k} is an instant at which a job of task τ _{k} released at this instant has the largest response time.

A critical time zone for task τ _{k} is a time interval starting from a critical instant of τ _{k} to the completion of the job of task τ _{k} released at the critical instant.

A critical instant for task τ _{k} is an instant such that

a job of task τ _{k} released at this instant has the largest response time if it is no more than T _{k} or

the worstcase response time of a job of task τ _{k} released at this instant is more than T _{k}.


A critical time zone for task τ _{k} is a time interval starting from a critical instant of τ _{k} to the completion of the job of task τ _{k} released at the critical instant.

In a critical time zone for task τ _{k}, all the tasks release their first jobs at a critical instant for task τ _{k} and their subsequent jobs as early as possible by respecting their minimum interarrival times.