A hybrid performance analysis technique for distributed real-time embedded systems

It remains a challenging problem to tightly estimate the worst-case response time of an application in a distributed embedded system, especially when there are dependencies between tasks. Recently, a holistic worst-case response time analysis approach called scheduling time bound analysis has been proposed to find a tight upper bound of the worst-case response times of applications specified by a set of task graphs. Since it assumes that the starting offsets of applications are known and fixed, it fails to make a tight estimation despite increased computation time when the starting offsets are dynamic. To overcome this problem, we propose a novel conservative performance analysis, called hybrid performance analysis, combining the response time analysis technique and the scheduling time bound analysis technique to compute a tighter bound faster. The proposed scheme is proven to be conservative formally. Through extensive experiments with real-life benchmarks and synthetic examples, the superior performance of our proposed approach compared with previous methods is confirmed.

This research was supported by the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIP) (No. NRF-2016R1A2B3012662) and Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education (No. 2017R1A2B4009903).

Authors and Affiliations

1. Department of Computer Science and Engineering, Seoul National University, Seoul, Republic of Korea

   Junchul Choi & Soonhoi Ha

2. Department of Information Systems, Hanyang University, Seoul, Republic of Korea

   Hyunok Oh

Corresponding author

Correspondence to Soonhoi Ha.

Appendix

In this section, we prove lemmas and theorems presented in Sects. 5, 6, and 7. As listed in Table 3, \(r(\tau _{t})\), \(s(\tau _{t})\), and \(f(\tau _{t})\) denote the actual release time, start time, and finish time of task \(\tau _{t}\), respectively.

1.1 A.1 Proof of Theorem 1

In this section we prove that the schedule time bounds computed in the proposed technique are all conservative. We make several definitions and lemmas in this section.

Definition A.1

In our task graph model, the release time of a task is the maximum finish time of its immediate predecessors, which is summarized as

where \(r(\mathcal {G}_{\tau _{t}})\) denotes the release time of the task graph and \({ pred}(\tau _{t})\) is the immediate predecessor set of task \(\tau _{t}\).

Lemma A.1

\({RB}_{t}^{l}\) and \({RB}_{t}^{u}\) are conservative, or \({RB}_{t}^{l} \le r(\tau _{t}) \le {RB}_{t}^{u}\).

Proof

If \(\tau _{t}\) is a source task, \({RB}_{t}^{l}=0\le r(\tau _{t})\le J_{\mathcal {G}_{\tau _{t}}}={RB}_{t}^{u}\) since \(0 \le r(\mathcal {G}_{\tau _{t}}) \le J_{\mathcal {G}_{\tau _{t}}}\).

For a non-source task \(\tau _{t}\), assume that it holds for all predecessor tasks of \(\tau _{t}\). Since \( {RB}_{t}^{l} = \max _{\tau _{p}\in {{ pred}(\tau _{t})}}{{FB}_{p}^{l}} \le \max _{\tau _{p}\in {{ pred}(\tau _{t})}}{f(\tau _{p})} = r(\tau _{t}) \le \max _{\tau _{p}\in {{ pred}(\tau _{t})}}{{FB}_{p}^{u}} = {RB}_{t}^{u}\), \({RB}_{t}^{l} \le r(\tau _{t}) \le {RB}_{t}^{u}\).

By induction, Lemma A.1 holds. \(\square \)

Definition A.2

The start time is formally defined as

where \({\varGamma _{\tau _{t}}}=\{\tau _{s}| \tau _{s} \in \mathcal {G}_{\tau _{t}}, {M}_{s}={M}_{t},{PR}_{s}>{PR}_{t},r(\tau _{t})<f(\tau _{s}),s(\tau _{s}) \le s(\tau _{t})\}\) for the preemptive scheduling policy, and \({\varGamma _{\tau _{t}}}=\{\tau _{s}|\tau _{s} \in \mathcal {G}_{\tau _{t}}, {M}_{s}={M}_{t},({PR}_{s}>{PR}_{t},r(\tau _{t})<f(\tau _{s}), s(\tau _{s})\le s(\tau _{t}))\text { or }({PR}_{s}<{PR}_{t}, s(\tau _{s})<r(\tau _{t})<f(\tau _{s}))\}\) for the non-preemptive scheduling policy.

Lemma A.2

\({SB}_{t}^{l}\) is conservative, or \({SB}_{t}^{l} \le s(\tau _{t})\).

Proof

Since \({RB}_{t}^{l} \le r(\tau _{t})\), we need to prove \(\max _{\tau _{s}\in \mathcal {A}_{\tau _{t}}}{{FB}_{s}^{l}} \le s(\tau _{t})\).

Proof will be completed by showing that \(\max \limits _{\tau _{s}\in \mathcal {A}_{\tau _{t}}- {\varGamma _{\tau _{t}}}}{f(\tau _{s})} \le r(\tau _{t})\) since

We define \(\mathcal {A}_{\tau _{t}}^\mathcal {P}=\{\tau _{s}|\tau _{s} \in \mathcal {G}_{\tau _{t}},{M}_{s}={M}_{t},{PR}_{s}>{PR}_{t}, {RB}_{t}^{l}<{FB}_{s}^{l},{SB}_{s}^{u}\le {SB}_{t}^{l}\}\) and \(\mathcal {A}_{\tau _{t}}^\mathcal {N}=\{\tau _{s}| \tau _{s}\in \mathcal {G}_{\tau _{t}},{M}_{s}={M}_{t}, {PR}_{s}<{PR}_{t},{SB}_{s}^{u}<{RB}_{t}^{l}<{FB}_{s}^{l}\}\). Then \(\mathcal {A}_{\tau _{t}} = \mathcal {A}_{\tau _{t}}^\mathcal {P}\) for preemptive scheduling policy and \(\mathcal {A}_{\tau _{t}} = \mathcal {A}_{\tau _{t}}^\mathcal {P} \cup \mathcal {A}_{\tau _{t}}^\mathcal {N}\) for non-preemptive scheduling policy. Similarly, We define \(\varGamma _{\tau _{t}}^\mathcal {P}=\{\tau _{s}| \tau _{s} \in \mathcal {G}_{\tau _{t}}, {M}_{s}={M}_{t},{PR}_{s}>{PR}_{t},r(\tau _{t})<f(\tau _{s}),s(\tau _{s}) \le s(\tau _{t})\}\) and \(\varGamma _{\tau _{t}}^\mathcal {N}=\{\tau _{s}| \tau _{s} \in \mathcal {G}_{\tau _{t}}, {M}_{s}={M}_{t},{PR}_{s}<{PR}_{t},s(\tau _{s})<r(\tau _{t})<f(\tau _{s})\}\).

1. 1.

   Preemptive case

   $$\begin{aligned} \begin{aligned} \mathcal {A}_{\tau _{t}}-{\varGamma _{\tau _{t}}}&= \mathcal {A}_{\tau _{t}}^\mathcal {P} \cap \big (\varGamma _{\tau _{t}}^\mathcal {P}\big )^c \\&=\mathcal {A}_{\tau _{t}}^\mathcal {P} \cap (\{\tau _{s} | \tau _{s}\in \mathcal {G}_{\tau _{t}}, {M}_{s}={M}_{t}, {PR}_{s}>{PR}_{t}\}^c\\&\qquad \qquad \cup \{\tau _{s} | r(\tau _{t})<f(\tau _{s})\}^c \cup \{\tau _{s} | s(\tau _{s})\le s(\tau _{t})\}^c)\\&=\emptyset \cup \big (\mathcal {A}_{\tau _{t}}^\mathcal {P}\cap \{\tau _{s} | r(\tau _{t})\ge f(\tau _{s})\}\big ) \cup \emptyset \\&\subseteq \{\tau _{s}|\tau _{s}\in \mathcal {G}_{\tau _{t}}, {M}_{s}={M}_{t},r(\tau _{t})\ge f(\tau _{s})\} \end{aligned} \end{aligned}$$
2. 2.

   non-preemptive case

   $$\begin{aligned} \mathcal {A}_{\tau _{t}}-{\varGamma _{\tau _{t}}}= & {} \big (\mathcal {A}_{\tau _{t}}^\mathcal {P} \cup \mathcal {A}_{\tau _{t}}^\mathcal {N}\big ) - \big (\varGamma _{\tau _{t}}^\mathcal {P} \cup \varGamma _{\tau _{t}}^\mathcal {N}\big ) = \big (\mathcal {A}_{\tau _{t}}^\mathcal {P}-\varGamma _{\tau _{t}}^\mathcal {P}\big ) \cup \big (\mathcal {A}_{\tau _{t}}^\mathcal {N} - \varGamma _{\tau _{t}}^\mathcal {N}\big )\\= & {} \big (\mathcal {A}_{\tau _{t}}^\mathcal {P} \cap \big (\varGamma _{\tau _{t}}^\mathcal {P}\big )^c\big ) \cup \big (\mathcal {A}_{\tau _{t}}^\mathcal {N} \cap \big (\varGamma _{\tau _{t}}^\mathcal {N}\big )^c\big )\\= & {} \big (\mathcal {A}_{\tau _{t}}^\mathcal {P} \cap \big (\varGamma _{\tau _{t}}^\mathcal {P}\big )^c\big ) \cup \\&\qquad \big (\mathcal {A}_{\tau _{t}}^\mathcal {N} \cap \big (\{\tau _{s}|\tau _{s}\in \mathcal {G}_{\tau _{t}}, {M}_{s}={M}_{t}, {PR}_{s}<{PR}_{t}\}^c\\&\quad \qquad \qquad \cup \{\tau _{s} | s(\tau _{s})<r(\tau _{t})\}^c \cup \{\tau _{s} | r(\tau _{t})<f(\tau _{s})\}^c\big )\\= & {} \big (\mathcal {A}_{\tau _{t}}^\mathcal {P} \cap \big (\varGamma _{\tau _{t}}^\mathcal {P}\big )^c\big ) \cup (\emptyset \cup \emptyset \cup \big (\mathcal {A}_{\tau _{t}}^\mathcal {N}\cap \{\tau _{s} | r(\tau _{t})\ge f(\tau _{s})\}\big )\big )\\\subseteq & {} \{\tau _{s}|\tau _{s}\in \mathcal {G}_{\tau _{t}}, {M}_{s}={M}_{t},r(\tau _{t})\ge f(\tau _{s})\} \end{aligned}$$

From (1) and (2), \(\mathcal {A}_{\tau _{t}}- {\varGamma _{\tau _{t}}} \subseteq \{\tau _{s}|\tau _{s}\in \mathcal {G}_{\tau _{t}},{M}_{s}={M}_{t}, r(\tau _{t})\ge f(\tau _{s})\}\) for both preemptive and non-preemptive cases. Therefore, \( \max _{\tau _{s}\in \mathcal {A}_{\tau _{t}}- {\varGamma _{\tau _{t}}}}{f(\tau _{s})} \le r(\tau _{t})\) \(\square \)

Definition A.3

We define \(LP_t^{intra}=\{\tau _{s} \mid \tau _{s}\in \mathcal {G}_{\tau _{t}}, {M}_{s}={M}_{t}, {PR}_{s}<{PR}_{t}\}\), a set of lower priority tasks that may interfere \(\tau _{t}\), and \(HP_t^{intra}=\{\tau _{s} \mid \tau _{s}\in \mathcal {G}_{\tau _{t}}, {M}_{s}={M}_{t}, {PR}_{s}>{PR}_{t}\}\), a set of higher priority tasks that may preempt \(\tau _{t}\).

Definition A.4

\(P_s[a,b]\) is defined as the execution amount of \(\tau _{s}\) in time window [b, a]. Then following conditions hold:

1. 1.

   \(\sum _{\tau _{s}\in {HP_t^{intra}}}{P_s[a, b]} \le a-b\)

2. 2.

   \(P_s[a,b] = 0\) if \(f(\tau _{s})\le {b}\) or \(s(\tau _{s})\ge {a}\)

3. 3.

   \(P_s[a,b] \le \min ({C}_{s}^{u}, \min (f(\tau _{s}),a) - \max (s(\tau _{s}), b))\)

Lemma A.3

\({SB}_{t}^{u}\) is conservative, or \(s(\tau _{t}) \le {SB}_{t}^{u}\).

Proof

We will consider the interference by lower priority tasks and higher priority tasks separately.

1. 1.

   For the interference by a lower priority task we prove that \(s(\tau _{t})\le {RB}_{t}^{u}+{ Delay}_t^l\). For a preemptive scheduling policy, it is impossible for a lower priority task to interfere \(\tau _{t}\) so that the interference amount is zero. For a non-preemptive scheduling policy, if all predecessors are mapped to the same processor, there is no time interval between the finish time of the latest predecessor task \(\tau _{p}\) and the release time of \(\tau _{t}\). Thus no lower priority task can start after \(\tau _{p}\) finishes and before \(\tau _{t}\) is released and the interference amount is zero. Otherwise, at most one lower priority task \(\tau _{s}\) can delay the execution of \(\tau _{t}\) if \(\tau _{s}\) starts before and finishes after \(\tau _{t}\) is released, or \(s(\tau _{s})< r(\tau _{t}) < f(\tau _{s})\). We compute the actual start time without the preemptions from higher priority tasks as

   $$\begin{aligned} \begin{aligned} s(\tau _{t}) = r(\tau _{t}) + \max _{\tau _{s}\in {LP_t^{intra}}, s(\tau _{s})< r(\tau _{t}) < f(\tau _{s})}{(f(\tau _{s})-r(\tau _{t}))} \end{aligned} \end{aligned}$$

   \(\forall _{\tau _{s}\in {LP_t^{intra}}, s(\tau _{s})< r(\tau _{t}) < f(\tau _{s})}{(f(\tau _{s}) -r(\tau _{t}) \le {C}_{s}^{u})}\) holds since \(f(\tau _{s})-s(\tau _{s}) \le {C}_{s}^{u}\) for task \(\tau _{s}\) under the non-preemptive policy. Then

   $$\begin{aligned} s(\tau _{t})= & {} r(\tau _{t}) + \max _{\tau _{s}\in {LP_t^{intra}}, s(\tau _{s})< r(\tau _{t})< f(\tau _{s})}{\min ({C}_{s}^{u}, f(\tau _{s})-r(\tau _{t}))} \\= & {} r(\tau _{t}) + \max \left( 0,\max _{\tau _{s}\in {LP_t^{intra}}, s(\tau _{s})<r(\tau _{t})}\min ({C}_{s}^{u}, f(\tau _{s})-r(\tau _{t}))\right) \\= & {} \max (r(\tau _{t}) ,\max _{\tau _{s}\in {LP_t^{intra}}, s(\tau _{s})< r(\tau _{t})}{\min (r(\tau _{t})+{C}_{s}^{u}, f(\tau _{s}))}) \\\le & {} \max ({RB}_{t}^{u} ,\max _{\tau _{s}\in {LP_t^{intra}}, s(\tau _{s})< r(\tau _{t})}{\min ({RB}_{t}^{u}+{C}_{s}^{u}, f(\tau _{s}))}) \\= & {} {RB}_{t}^{u} + \max \left( 0,\max _{\tau _{s}\in {LP_t^{intra}}, s(\tau _{s})<r(\tau _{t})}\min ({C}_{s}^{u}, f(\tau _{s})-{RB}_{t}^{u})\right) \\= & {} {RB}_{t}^{u}+ \max _{\tau _{s}\in {LP_t^{intra}}, s(\tau _{s})< r(\tau _{t}), {RB}_{t}^{u}< f(\tau _{s})}{\min ({C}_{s}^{u}, f(\tau _{s})-{RB}_{t}^{u})} \\\le & {} {RB}_{t}^{u} + \max _{\tau _{s}\in {LP_t^{intra}}, s(\tau _{s})< r(\tau _{t}), {RB}_{t}^{u} < {FB}_{s}^{u}}{\min ({C}_{s}^{u},{FB}_{s}^{u}-{RB}_{t}^{u})}\\\le & {} {RB}_{t}^{u} + \max \limits _{\tau _{s}\in \mathcal {B}_{\tau _{t}}}{\min ({C}_{s}^{u}, {FB}_{s}^{u}-{RB}_{t}^{u})} = {RB}_{t}^{u} + { Delay}_t^l \end{aligned}$$

   The last inequality holds since \(\{\tau _{s}| s(\tau _{s})< r(\tau _{t})\} \subseteq \{\tau _{s} | {SB}_{s}^{l} < {RB}_{t}^{u}\}\) and \(\{\tau _{s} \mid \tau _{s}\in {LP_t^{intra}}, s(\tau _{s})< r(\tau _{t}), {RB}_{t}^{u}< {FB}_{s}^{u}\} \subseteq \{\tau _{s}|\tau _{s}\in {LP_t^{intra}},{SB}_{s}^{l}<{RB}_{t}^{u}<{FB}_{s}^{u}\}=\mathcal {B}_{\tau _{t}}\).

2. 2.

   Consider the interference from higher priority tasks. We compute the actual start time without the lower priority blocking as

   $$\begin{aligned} \begin{aligned} s(\tau _{t})&= r(\tau _{t}) + \sum _{\tau _{s}\in {HP_t^{intra}}}{P_s[s(\tau _{t}), r(\tau _{t})]}\\&\le r(\tau _{t}) + \sum _{\tau _{s}\in {HP_t^{intra}}}\{P_s[\max (s(\tau _{t}), {RB}_{t}^{u}),{RB}_{t}^{u}]+P_s[{RB}_{t}^{u},r(\tau _{t})]\} \end{aligned} \end{aligned}$$

   Since \(\sum _{\tau _{s}\in {HP_t^{intra}}}{P_s[{RB}_{t}^{u},r(\tau _{t})]} \le {RB}_{t}^{u} - r(\tau _{t})\) from Definition A.4.1,

   $$\begin{aligned} \begin{aligned} s(\tau _{t})&\le {RB}_{t}^{u}+\sum _{\tau _{s}\in {HP_t^{intra}}}{P_s[\max (s(\tau _{t}), {RB}_{t}^{u}),{RB}_{t}^{u}]} \end{aligned} \end{aligned}$$

   In case \(s(\tau _{t})\le {RB}_{t}^{u}\), \(s(\tau _{t})\le {RB}_{t}^{u}\le {RB}_{t}^{u}+{ Delay}_t^l+{ Delay}_t^h={SB}_{t}^{u}\). So we consider only the case \(s(\tau _{t})>{RB}_{t}^{u}\).

   $$\begin{aligned} \begin{aligned} s(\tau _{t})&\le {RB}_{t}^{u}+\sum _{\tau _{s}\in {HP_t^{intra}}}{P_s[s(\tau _{t}),{RB}_{t}^{u}]}\\ \end{aligned} \end{aligned}$$

   \(P_s[s(\tau _{t}),{RB}_{t}^{u}]\) is not zero when \(s(\tau _{s})<s(\tau _{t}),{RB}_{t}^{u}<f(\tau _{s})\) according to Definition A.4.2.

   $$\begin{aligned} \begin{aligned} s(\tau _{t})&\le {RB}_{t}^{u}+\sum _{\tau _{s}\in {HP_t^{intra}}, s(\tau _{s})<s(\tau _{t}),{RB}_{t}^{u}<f(\tau _{s})}{P_s[s(\tau _{t}), {RB}_{t}^{u}]}\\&\le {RB}_{t}^{u}+\sum _{\tau _{s}\in \mathcal {C}_{\tau _{t}}}{P_s[s(\tau _{t}), {RB}_{t}^{u}]}\\ \end{aligned} \end{aligned}$$

   According to Definition A.4.3,

   $$\begin{aligned} \begin{aligned} s(\tau _{t})&\le {RB}_{t}^{u}+\sum _{\tau _{s}\in \mathcal {C}_{\tau _{t}}}{\min ({C}_{s}^{u}, \min (f(\tau _{s}),s(\tau _{t})) - \max (s(\tau _{s}), {RB}_{t}^{u}))} \\&\le {RB}_{t}^{u}+\sum _{\tau _{s}\in \mathcal {C}_{\tau _{t}}}{\min ({C}_{s}^{u}, f(\tau _{s})-{RB}_{t}^{u})}\\&\le {RB}_{t}^{u}+\sum _{\tau _{s}\in \mathcal {C}_{\tau _{t}}}{\min ({C}_{s}^{u}, {FB}_{s}^{u}-{RB}_{t}^{u})}={RB}_{t}^{u}+{ Delay}_t^h \end{aligned} \end{aligned}$$

Merging two cases 1 and 2, \(s(\tau _{t})\le {RB}_{t}^{u}+{ Delay}_t^l+{ Delay}_t^h={SB}_{t}^{u}\). \(\square \)

Lemma A.4

\({FB}_{t}^{l}\) is conservative, or \({FB}_{t}^{l} \le f(\tau _{t})\).

Proof

Since there is no preemption delay involved under a non-preemptive scheduling policy, we consider the preemptive scheduling policy only.

where the last term accounts for tasks that start to execute during \(\tau _{t}\) is running, and preempt \(\tau _{t}\). Since \(s(\tau _{t}) + \sum _{\tau _{s}\in {HP_t^{intra}}, s(\tau _{t}) \le s(\tau _{s}) \le f(\tau _{t})}{{C}_{s}^{l}} \ge {SB}_{t}^{l} + \sum _{\tau _{s}\in {HP_t^{intra}}, {SB}_{t}^{l} \le s(\tau _{s}) \le f(\tau _{t})}{{C}_{s}^{l}}\),

The last inequality holds since \(\{\tau _{s} \mid \tau _{s}\in {HP_t^{intra}}, {SB}_{t}^{l} \le s(\tau _{s}) \le f(\tau _{t})\} \supseteq \{\tau _{s} \mid \tau _{s}\in {HP_t^{intra}}, {SB}_{t}^{l} \le {SB}_{s}^{l} \le {SB}_{s}^{u} \le {FB}_{t}^{l}\} = \mathcal {D}_{\tau _{t}}\). \(\square \)

Lemma A.5

\({FB}_{t}^{u}\) is conservative, or \(f(\tau _{t}) \le {FB}_{t}^{u}\).

Proof

Since there is no preemption delay involved under a non-preemptive scheduling policy, we consider the preemptive scheduling policy only. The actual finish time is defined as

We consider only the case \(f(\tau _{t}) > {SB}_{t}^{u} \ge {RB}_{t}^{u}\) since if \(f(\tau _{t}) \le {SB}_{t}^{u}\) then \(f(\tau _{t}) \le {SB}_{t}^{u} + {C}_{t}^{u} + { Preempt}_t^W = {FB}_{t}^{u}\). According to Definition A.4.1, \({RB}_{t}^{u} - r(\tau _{t}) \ge \sum _{\tau _{s}\in {HP_t^{intra}}}{P_s[{RB}_{t}^{u},r(\tau _{t})]}\).

Now we prove that \(\sum _{\tau _{s}\in {HP_t^{intra}}, {SB}_{s}^{l}<{SB}_{t}^{u}}{P_s[f(\tau _{t}), {RB}_{t}^{u}]} \le {{ Delay}_t^h}\) and \(\sum _{\tau _{s}\in {HP_t^{intra}}, {SB}_{t}^{u}\le {SB}_{s}^{l}}{P_s[f(\tau _{t}), {RB}_{t}^{u}]} \le {{ Preempt}_t^W}\).

1. 1.

   By Definition A.4.2 and A.4.3,

   $$\begin{aligned}&\sum _{\tau _{s}\in {HP_t^{intra}}, {SB}_{s}^{l}<{SB}_{t}^{u}}{P_s[f(\tau _{t}), {RB}_{t}^{u}]} \\&\quad \le \sum _{\tiny \begin{array}{ll}\tau _{s}\in {HP_t^{intra}}, {SB}_{s}^{l}<{SB}_{t}^{u}, \\ s(\tau _{s})<f(\tau _{t}), {RB}_{t}^{u}<f(\tau _{s}) \end{array}}{\min ({C}_{s}^{u}, \min (f(\tau _{s}),f(\tau _{t}))-\max (s(\tau _{s}), {RB}_{t}^{u}))} \\&\quad \le \sum _{\tau _{s}\in \mathcal {C}_{\tau _{t}}}{\min ({C}_{s}^{u}, {FB}_{s}^{u} - {RB}_{t}^{u})} = { Delay}_t^h \end{aligned}$$
2. 2.

   \(P_s[{SB}_{t}^{u}, {RB}_{t}^{u}] = 0\) if \({SB}_{t}^{u} \le s(\tau _{s})\) by Definition A.4.2.

   $$\begin{aligned}&\sum _{\tau _{s}\in {HP_t^{intra}}, {SB}_{t}^{u}\le {SB}_{s}^{l}}{P_s[f(\tau _{t}), {RB}_{t}^{u}]} \\&\quad = \sum _{\tau _{s}\in {HP_t^{intra}}, {SB}_{t}^{u}\le {SB}_{s}^{l}}\{P_s[f(\tau _{t}), {SB}_{t}^{u}] + P_s[{SB}_{t}^{u}, {RB}_{t}^{u}]\} \\&= \sum _{\tau _{s}\in {HP_t^{intra}}, {SB}_{t}^{u}\le {SB}_{s}^{l}}{P_s[f(\tau _{t}), {SB}_{t}^{u}]} \\ \end{aligned}$$

   By Definition A.4.2 and A.4.3,

   $$\begin{aligned} \begin{aligned}&\le \sum _{\tiny \begin{array}{c}\tau _{s}\in {HP_t^{intra}}, {SB}_{t}^{u}\le {SB}_{s}^{l}, \\ s(\tau _{s})<f(\tau _{t}), {SB}_{t}^{u}<f(\tau _{s}) \end{array}}{\min ({C}_{s}^{u}, \min (f(\tau _{s}),f(\tau _{t}))-\max (s(\tau _{s}), {SB}_{t}^{u}))} \\&\le \sum _{\tau _{s}\in \mathcal {E}_{\tau _{t}}}{{C}_{s}^{u}} = { Preempt}_t^W \end{aligned} \end{aligned}$$

From 1 and 2, \(f(\tau _{t}) \le ({RB}_{t}^{u} + { Delay}_t^h) + {C}_{t}^{u} + { Preempt}_t^W = {FB}_{t}^{u}\). \(\square \)

Now we restate the theorem and prove it.

Theorem

1 The HPA technique guarantees the conservativeness of every schedule time bound when there is no inter-graph interference.

Proof

Theorem 1 is proven by Lemmas A.1, A.2, A.3, A.4, and A.5.

1.2 A.2 Proof of Lemma 1

We restate the lemma and prove it.

Lemma

1 Suppose \(\tau _{s}\) is a task that may block both preempting tasks of other task graphs and the target task \(\tau _{t}\) of the same task graph. Let \(R_t^\alpha \) be the worst-case response time of \(\tau _{t}\) when \(\tau _{s}\) blocks \(\tau _{t}\) by \(\alpha \) amount of time. Then, \(R_t^\alpha < R_t^\beta \) if \(0\le \alpha <\beta \le {C}_{s}^{u}\).

Proof

When \(\tau _{s}\) blocks \(\tau _{t}\) by \(\alpha \) amount of time, the maximum preemption by a preempting task occurs when it is released right after the start time of \(\tau _{s}\), which is equal to \(r(\tau _{t})-{C}_{s}^{u}+\alpha \). Let A be a set of preempting tasks of \(\tau _{t}\). Then the conventional response time analysis tells that \(R_t^\alpha \) and \(R_t^\beta \) become

where \(R_t^\alpha (i)\) and \(R_t^\beta (i)\) are computed iteratively, and initial values \(R_t^\alpha (0)\) and \(R_t^\beta (0)\) are \(\alpha +{C}_{t}^{u}\) and \(\beta +{C}_{t}^{u}\), respectively. The iteration terminates when it converges. For \(i=0\), \(R_t^\beta (0)-R_t^\alpha (0)\) is \(\beta -\alpha \). For \(i=1\), The first terms in \(R_t^\alpha (1)\) and \(R_t^\beta (1)\) are equal since \(R_t^\beta (0)+{C}_{s}^{u}-\beta =R_t^\alpha (0)+\beta -\alpha +{C}_{s}^{u}-\beta =R_t^\alpha (0)+{C}_{s}^{u}-\alpha \). Hence \(R_t^\beta (1)-R_t^\alpha (1)=\beta -\alpha \). For \(i>1\), we can derive \(R_t^\beta (i)-R_t^\alpha (i)=\beta -\alpha \) in the same way of the case \(i=1\), which means that \(R_t^\alpha (i)\) and \(R_t^\beta (i)\) increase by the same amount at each iteration. Hence \(R_t^\beta \) is always larger than \(R_t^\alpha \). \(\square \)

1.3 A.3 Proof of Lemma 2

We restate the lemma and prove it.

Lemma

2 Period shift formulated as Eq. (14) is conservative, which means that \(\sum _{\tau _{i}\in {A}} {\Big \lceil {\frac{{SB}_{t}^{u}-{RB_t^u} + {\Psi _t}+{RB}_{i}^{u} -{RB}_{i}^{l}}{T_{\mathcal {G}_{\tau _{i}}}}}\Big \rceil \cdot {C}_{i}^{u}}\) is the upper bound of the interference from set A to \(\tau _{t}\) during time interval \([{RB}_{t}^{u}, {SB}_{t}^{u}]\)under a non-preemptive scheduling policy, where A be a set of preempting tasks of other task graphs.

Proof

We prove it by contradiction assuming that the release jitter of a preempting task is zero, or \({RB}_{i}^{u}-{RB}_{i}^{l} = 0\). Assume that an earlier appearance of a higher priority task than the time offset \(\varPsi _{t}\) makes the worst interference to the target task.

1. 1.

   All predecessors are on the same PE. Then one of the predecessors, \(\tau _{s}\in {{ pred}[\tau _{t}]}\), is executed right before the release of \(\tau _{t}\). Assume some task \(\tau _{i}\in {A}\) appears earlier than \({RB}_{t}^{u}-\max \limits _{\tau _{p}\in {{ pred}(\tau _{t})}}{{C}_{p}^{u}}\). Then \(\tau _{i}\) will start before \(\tau _{s}\) instead of being blocked by \(\tau _{s}\) since \(\tau _{i}\) has a higher priority than all tasks in \(\mathcal {G}_{\tau _{t}}\). It means that \(\tau _{i}\) should not be counted as a preempting task of \(\tau _{t}\), which is contradictory to the assumption.

2. 2.

   Otherwise. Suppose there exists a worst-case scheduling scenario that a lower priority task \(\tau _{s}\) starts earlier than \({RB}_{t}^{u}-\varPsi _{t}\) and blocks higher priority tasks in A. It means that \(\tau _{s}\) is not considered in \(\varPsi _{t}\) computation (\(\tau _{s}\not \in \mathcal {F}_{\tau _{t}}\)), or larger period shift value should be considered for \(\tau _{s}\in \mathcal {F}_{\tau _{t}}\). If \(\tau _{s}\in \mathcal {G}_{t}\) and \({SB}_{s}^{l}\ge {RB}_{t}^{u}\), it cannot start and block tasks in A before \({RB}_{t}^{u}\), which is contradictory to the assumption. In case \(\tau _{s}\not \in \mathcal {G}_{t}\) or \(\tau _{s}\in \mathcal {G}_{t} \wedge {SB}_{s}^{l}<{RB}_{t}^{u}\), the larger period shift means lower blocking delay since the sum of the blocking delay and the period shift is equal to the execution time of \(\tau _{s}\). By Lemma 1, it decreases the response time, which is contradictory.

From 1 and 2, the conservativeness is proven. \(\square \)

1.4 A.4 Proof of Lemma 3

We restate the lemma and prove it.

Lemma

3 Phases \(\phi _{t,i}^r\), \(\phi _{t,i}^s\), and \(\phi _{t,i}^f\) are conservative.

Proof

We provide the sketch of proof by induction. First, when task \(\tau _{t}\) is a source task, \(\phi _{t,i}^r\) is \(-(\varPsi _{t}+{RB}_{i}^{u}-{RB}_{i}^{l})\) and it is conservative according to Lemma 2. \(\phi _{t,i}^s\) and \(\phi _{t,i}^f\) are computed referring to the next release time of \(\tau _{i}\) from \({SB}_{t}^{u}\) and \({FB}_{t}^{u}\), respectively. Since the worst-case preemption scenario to the preempted task is the periodic invocation of the preempting task after the worst-case request phase, mod \(T_{\mathcal {G}_{\tau _{i}}}\) operations in Eqs. (19) and (22) find the nearest future request time of \(\tau _{i}\) from \({SB}_{t}^{u}\) and \({FB}_{t}^{u}\) once the request phase is decided. It completes the initial step of the induction process.

Second, we prove the conservativeness of \(\phi _{t,i}^r\), \(\phi _{t,i}^s\), and \(\phi _{t,i}^f\) of non-source task \(\tau _{t}\), assuming that for all \(\tau _{p}\in {{ pred}(\tau _{t})}\), \(\phi _{p,i}^f\)s are conservative. If there is any predecessor \(\tau _{p}\) such that \({M}_{t}\not ={M}_{p}\), then \(\phi _{t,i}^r\) is \(-(\varPsi _{t}+{RB}_{i}^{u}-{RB}_{i}^{l})\) and it is conservative. Otherwise, we find the closest release time of \(\tau _{i}\) from the finish phase \(\phi _{p,i}^f\)s of predecessors, by Eq. (16). Hence \(\phi _{t,i}^r\) is conservative since \(\phi _{p,i}^f\)s are all conservative and the minimum value is chosen. The proof for \(\phi _{t,i}^s\), and \(\phi _{t,i}^f\) is similar to the case that task \(\tau _{t}\) is a source task. \(\square \)

1.5 A.5 Proof of Theorem 2

We prove that the optimization technique of duplicate preemption elimination preserves the conservativeness of the HPA technique. It is a rather long proof. We make several definitions, lemmas, and theorems in this section.

Definition A.5

\(pe(\tau _{t})[x,y]\) is defined as the sum of execution time of tasks of which priority is higher than \(\tau _{t}\) from time x to time y. Then \(0 \le pe(\tau _{t})[x,y] \le y-x\) and \(pe(\tau _{t})[x,z] = pe(\tau _{t})[x,y] + pe(\tau _{t})[y,z]\) are hold.

Lemma A.6

If the maximum release time bound of \(\tau _{t}\) is reduced by \(\varDelta \), or \(r(\tau _{t}) \le {RB}_{t}^{u}-\varDelta \), then it always holds that the maximum finish time bound of \(\tau _{t}\) is reduced by \(\varDelta - pe(\tau _{t})[{RB}_{t}^{u}-\varDelta ,{RB}_{t}^{u}]\), or \(f(\tau _{t}) \le {FB}_{t}^{u} - \varDelta + pe(\tau _{t})[{RB}_{t}^{u}-\varDelta ,{RB}_{t}^{u}]\).

Proof

We prove it by contradiction. Suppose that \(f(\tau _{t})\) exists such that \(f(\tau _{t}) > {FB}_{t}^{u} - \varDelta + pe(\tau _{t})[{RB}_{t}^{u}-\varDelta ,{RB}_{t}^{u}]\). It is obvious that \({FB}_{t}^{u} \ge {RB}_{t}^{u} + {C}_{t}^{u} + pe(\tau _{t})[{RB}_{t}^{u},{FB}_{t}^{u}]\) and \(f(\tau _{t}) \le r(\tau _{t}) + {C}_{t}^{u} + pe(\tau _{t})[r(\tau _{t}),f(\tau _{t})]\) since \(pe(\tau _{t})[x,y]\) is the actual preempting time while \({C}_{t}^{u}\) and \({FB}_{t}^{u}\) are defined as upper bounds. From two inequalities for \(f(\tau _{t})\), we have

and

Thus,

Last inequality comes from \(pe(\tau _{t})[{RB}_{t}^{u}-\varDelta ,{FB}_{t}^{u}] \ge pe(\tau _{t})[{RB}_{t}^{u}-\varDelta ,f(\tau _{t})]\). \(pe(\tau _{t})[r(\tau _{t}),{RB}_{t}^{u}-\varDelta ] > {RB}_{t}^{u}-\varDelta - r(\tau _{t})\) is contradiction since \(pe(\tau _{t})[r(\tau _{t}),{RB}_{t}^{u}-\varDelta ] \le {RB}_{t}^{u}-\varDelta - r(\tau _{t})\) according to Definition A.5. Hence \(f(\tau _{t}) \le {FB}_{t}^{u} - \varDelta + pe(\tau _{t})[{RB}_{t}^{u}-\varDelta ,{RB}_{t}^{u}]\). \(\square \)

Lemma A.6 explains how much the maximum finish time can be reduced if the maximum release time decreases. Since the release time depends on the finish times of predecessor tasks, Lemma A.6 presents the effect of the finish time of predecessor tasks onto the finish time of the target task. This lemma will be generalized below in Lemma A.7. Hereafter, \(pe(\tau _{t},\varDelta )\) denotes \(pe(\tau _{t})[{RB}_{t}^{u}-\varDelta ,{RB}_{t}^{u}]\) for brevity.

Now we will examine the effect of the early finish time of an ancestor task to the finish time of the target task. If we apply Lemma A.6 repeatedly, we can compute how much the finish time reduction of an ancestor task affects the finish time of the target task.

Lemma A.7

If   \(\forall _{\tau _{a} \in { pred}(\tau _{t})}{(f(\tau _{a}) \le {FB}_{a}^{u}-\varDelta _{\tau _{a}}+pe(\tau _{a},\varDelta _{\tau _{a}}))}\), then \(f(\tau _{t}) \le {FB}_{t}^{u} - \varDelta _{\tau _{t}} + pe(\tau _{t},\varDelta _{\tau _{t}})\) where

Note that \(\varDelta _{\tau _{m}} = 0\) if there is no predecessor.

Proof

We prove it by induction. First, \(f(\tau _{a}) \le {FB}_{a}^{u}-\varDelta _{\tau _{a}}+pe(\tau _{a},\varDelta _{\tau _{a}})={FB}_{a}^{u}\) holds for every source task \(\tau _{a}\) since \(\varDelta _{\tau _{a}}=0\). Second, for non-source task \(\tau _{m}\),

assuming that \(f(\tau _{i}) \le {FB}_{i}^{u}-\varDelta _{\tau _{i}}+pe(\tau _{i},\varDelta _{\tau _{i}})\) for all predecessor tasks of \(\tau _{m}\) in the induction process. From definition of \(\varDelta _{\tau _{m}}\), we have

Since \({RB}_{m}^{u} = \max _{\tau _{i} \in { pred}(\tau _{m})}{{FB}_{i}^{u}}\), \(r(\tau _{m}) \le \max _{\tau _{i} \in { pred}(\tau _{m})}{({FB}_{i}^{u})} - \varDelta _{\tau _{m}} = {RB}_{m}^{u} - \varDelta _{\tau _{m}}\), which induces \(f(\tau _{m}) \le {FB}_{m}^{u} - \varDelta _{\tau _{m}}+pe(\tau _{m},\varDelta _{\tau _{m}})\) according to Lemma  A.6. \(\square \)

For the brevity of further formulation, we define a new notation for the reduced finish time bound, \(\overleftarrow{FB}_{t}^{u}\), after reducing the finish time of an ancestor task \(\tau _{a}\) by \(\varDelta \) as following:

Definition A.6

The reduced finish time bound \(\overleftarrow{FB}_{t , \varDelta _{\tau _{a}} \leftarrow \varDelta }^{u}\) after reducing the finish time of a task \(\tau _{a}\) by \(\varDelta \) is

where \(\varDelta _{\tau _m} = \max _{\tau _{i} \in { pred}(\tau _{m})}{{FB}_{i}^{u}} - \max _{\tau _{i} \in { pred}(\tau _{m})} {\overleftarrow{FB}_{i,\varDelta _{\tau _a} \leftarrow \varDelta }^{u}}\).

Lemma A.8

After reducing the finish time of a task \(\tau _{a}\) by \(\varDelta \), \(\varDelta _{\tau _{t}} \le \varDelta \) holds for all \(\tau _{t}\in {descendent(\tau _{a})}\).

Proof

We prove it by induction. First, consider a set of descendant tasks \(\{\tau _{t} \mid \tau _{t}\in {descendent(\tau _{a})}, \forall _{\tau _{i}\in {{ pred}(\tau _{t})}}{(\tau _{i}\not \in {descendent(\tau _{a})})}\}\). Then \(\varDelta _{\tau _{t}} = \max _{\tau _{i} \in { pred}(\tau _{t})}{{FB}_{i}^{u}} - \max _{\tau _{i} \in { pred}(\tau _{t})}{\overleftarrow{FB}_{i,\varDelta _{\tau _a} \leftarrow \varDelta }^{u}} \le \varDelta \) since \(\overleftarrow{FB}_{i,\varDelta _{\tau _a} \leftarrow \varDelta }^{u}\) of every predecessor task \(\tau _{i}\) is either \({FB}_{i}^{u}\) or \({FB}_{i}^{u}-\varDelta \).

Second, we prove that \(\varDelta _{\tau _{t}} \le \varDelta \) holds for a set of remaining descendant tasks \(\{\tau _{t} \mid \tau _{t}\in {descendent(\tau _{a})}, \exists _{\tau _{i} \in {{ pred}(\tau _{t})}}{(\tau _{i}\in {descendent(\tau _{a})})}\}\) assuming \(\forall _{\tau _{i}\in {{ pred}(\tau _{t})}, \tau _{i}\in {descendent(\tau _{a})}}{\varDelta _{\tau _{i}} \le \varDelta }\). For a predecessor task \(\tau _{i}\) who is also descendant of \(\tau _{a}\),

since \(\varDelta _{\tau _{i}} \le \varDelta \) and \(pe(\tau _{i},\varDelta _{\tau _{i}}) \ge 0\). Finally, \(\varDelta _{\tau _{t}} = \max _{\tau _{i} \in { pred}(\tau _{t})}{{FB}_{i}^{u}} - \max _{\tau _{i} \in { pred}(\tau _{t})}{\overleftarrow{FB}_{i,\varDelta _{\tau _a} \leftarrow \varDelta }^{u}} \le \varDelta \) since \(\overleftarrow{FB}_{i,\varDelta _{\tau _a} \leftarrow \varDelta }^{u} \ge {FB}_{i}^{u} - \varDelta \) holds for every predecessor task \(\tau _{i}\). \(\square \)

Lemma  A.8 implies that the contribution of the maximum finish time reduction of an ancestor task diminishes as it propagates to the child tasks.

Now we restate the key theorem in the proposed duplicate preemption elimination technique.

Theorem

2 If a common preemptor \(\tau _{p}\) can preempt an ancestor task \(\tau _{a}\) and the target task \(\tau _{t}\), then \(f(\tau _{t})\) is no smaller when it preempts \(\tau _{t}\) rather than \(\tau _{a}\).

Proof

Since \(\tau _{p}\) can preempt \(\tau _{a}\) and \(\tau _{t}\), it preempt \(\tau _{a}\) completely but \(\tau _{t}\) partially in case \({FB}_{p}^{u} - {RB}_{t}^{u} < {C}_{p}^{u}\). Otherwise, it preempt both tasks completely. Let \(\delta \) be the preemption time of \(\tau _{p}\) to \(\tau _{t}\). Then \(\delta \le {C}_{p}^{u}\).

\(\overleftarrow{FB}_{t,\varDelta _{\tau _{t}} \leftarrow \delta }^{u}\) and \(\overleftarrow{FB}_{t,\varDelta _{\tau _{a}} \leftarrow {C}_{p}^{u}}^{u}\) are the reduced finish time bound when \(\tau _{p}\) does not preempt \(\tau _{t}\) but preempts \(\tau _{a}\) and the reduced finish time bound when \(\tau _{p}\) preempts \(\tau _{t}\), respectively. We prove that \(\overleftarrow{FB}_{t,\varDelta _{\tau _{a}} \leftarrow {C}_{p}^{u}}^{u} \ge \overleftarrow{FB}_{t,\varDelta _{\tau _{t}} \leftarrow \delta }^{u} = {FB}_{t}^{u} - \delta \).

1. 1.

   If \(\varDelta _{\tau _{t}} \le {C}_{p}^{u}-\delta \) then the time interval \([{RB}_{t}^{u}-\varDelta _{\tau _{t}}, {RB}_{t}^{u}]\) is always filled with execution of \(\tau _{p}\) or other higher priority tasks since \(\delta \) amount of \(\tau _{p}\) execution appears after \({RB}_{t}^{u}\). It means that \(pe[\tau _{t}, \varDelta _{\tau _{t}}] = \varDelta _{\tau _{t}}\).

   $$\begin{aligned} \overleftarrow{FB}_{t,\varDelta _{\tau _{a}} \leftarrow {C}_{p}^{u}}^{u}={FB}_{t}^{u} - \varDelta _{\tau _{t}} + pe[\tau _{t}, \varDelta _{\tau _{t}}] = {FB}_{t}^{u} \ge {FB}_{t}^{u} - \delta = \overleftarrow{FB}_{t,\varDelta _{\tau _{t}} \leftarrow \delta }^{u} \end{aligned}$$
2. 2.

   If \(\varDelta _{\tau _{t}} > {C}_{p}^{u}-\delta \) then the time interval \([{RB}_{t}^{u}-\varDelta _{\tau _{t}}, {RB}_{t}^{u}]\) consists of at least \({C}_{p}^{u}-\delta \) amount of execution of \(\tau _{p}\) or other higher priority tasks. It means that \(pe[\tau _{t}, \varDelta _{\tau _{t}}] \ge {C}_{p}^{u} - \delta \). Since \(\varDelta _{\tau _{t}} \le {C}_{p}^{u}\) according to Lemma A.8,

   $$\begin{aligned} \begin{aligned} \overleftarrow{FB}_{t,\varDelta _{\tau _{a}} \leftarrow {C}_{p}^{u}}^{u}&= {FB}_{t}^{u} - \varDelta _{\tau _{t}} + pe[\tau _{t}, \varDelta _{\tau _{t}}] \\&\ge {FB}_{t}^{u} - {C}_{p}^{u} + {C}_{p}^{u} - \delta = {FB}_{}^{u} - \delta = \overleftarrow{FB}_{t,\varDelta _{\tau _{t}} \leftarrow \delta }^{u} \end{aligned} \end{aligned}$$

From 1 and 2, it is confirmed that preempting \(\tau _{t}\) provides no smaller maximum finish time of \(\tau _{t}\) than preempting \(\tau _{a}\), or \(\overleftarrow{FB}_{t,\varDelta _{\tau _{a}} \leftarrow {C}_{p}^{u}}^{u} \ge \overleftarrow{FB}_{t,\varDelta _{\tau _{t}} \leftarrow \delta }^{u}\). \(\square \)

1.6 A.6 Proof of Theorem 3

We restate the theorem and prove it.

Theorem

3 The computed worse-case response times are conservative for the arbitrary deadline model.

Proof

We prove it by contradiction. Assume that the estimated worst-case response time is smaller than the exact worst-case response time, which means that there exists a task \(\tau _{t}\) \({FB}_{t}^{u}\) is under-estimated. We prove that both intra-interference and inter-interference to the task instance \(\tau _{t}\) is conservatively computed in the proposed technique for the arbitrary deadline model.

1. 1.

   Suppose that intra-interference is under-estimated. Since we prove that intra-interference is conservative by Theorem 1 under the condition that all interfering task instances are considered, the assumption is only possible when task instances are not sufficiently expanded. It means that there exists an uncreated interfering task instance \(\tau _{s(i)}\) which will increase \({FB}_{t}^{u}\) if it is created and considered during analysis. Let the index of lastly created graph instance be \({ last}\). Since the graph expansion is terminated when all time bounds are converged, the schedule time bounds before and after adding \({ last}\) graph instance are equal. It means that \({FB}_{t({ last}-1)}^{u}+T_{\mathcal {G}_{t}}={FB}_{t({ last})}^{u}\) and \(\tau _{s({ last})}\) could not affect \({FB}_{t({ last}-1)}^{u}\). Then \({FB}_{t({ last}-1)}^{u} \le {SB}_{s({ last})}^{l}\) holds. Since \({ last} < i\) and the analysis is converged, \({SB}_{s({ last})}^{l} + T_{\mathcal {G}_{t}} \le {SB}_{s(i)}^{l}\). On the other hand, the assumption implies that \(\tau _{s(i)}\) can affect \({FB}_{t}^{u}\), or \({SB}_{s(i)}^{l} < {FB}_{t({ last})}^{u}\). In summary, \({FB}_{t({ last}-1)}^{u} + T_{\mathcal {G}_{t}} \le {SB}_{s({ last})}^{l} + T_{\mathcal {G}_{t}} \le {SB}_{s(i)}^{l} < {FB}_{t({ last})}^{u}\). which is contradictory to the fact that \({FB}_{t({ last}-1)}^{u} + T_{\mathcal {G}_{t}}={FB}_{t({ last})}^{u}\).

2. 2.

   Suppose that inter-interference is under-estimated. By Lemma 3, the under-estimation only happens when the period shift is under-estimated. The period shift \(\varPsi _{t}\) may be under-estimated only when at least one candidate task of \(\mathcal {F}_{\tau _{t}}\) is missed due to the lack of graph expansion. Let the index of the last graph instance be \({ last}\) in the initial graph expansion. Then \({ last} = \lceil {\frac{D_{\mathcal {G}_{}}}{T_{\mathcal {G}_{}}}}\rceil + 1\). The last \(\tau _{t}\) instance, \(\tau _{t({ last})}\) can check all task instances released after \({RB}_{t({ last})}^{u}-\lceil {\frac{D_{\mathcal {G}_{}}}{T_{\mathcal {G}_{}}}}\rceil \cdot T_{\mathcal {G}_{}} \le {RB}_{t({ last})}^{u}-D_{\mathcal {G}_{}}\). If there is a missed candidate task, it should be released before \({RB}_{t}^{u}-D_{\mathcal {G}_{}}\) and it can block the task that finishes at \({RB}_{t({ last})}^{u}\). It is impossible since the task cannot violate the deadline. Hence \(\varPsi _{t({ last})}\) is conservative. Since we use the maximum period shift among all \(\varPsi _{t(i)}\)s in the proposed technique and \(\varPsi _{t({ last})}\) is conservatively computed. So, the inter-interference cannot be under-estimated.

From 1 and 2, we prove that the proposed technique for the arbitrary deadline model computes a conservative WCRT. \(\square \)

Reprints and permissions