# Mitigating Mode-Switch through Run-time Computation of Response Time

ANGELIKI KRITIKAKOU, Univ Rennes, Inria, IRISA, France

STEFANOS SKALISTIS, Collins Aerospace, Ireland

Mixed-critical systems consist of applications with different criticality. In these systems, different confidence levels of Worst-Case Execution Time (WCET) estimations are used. Dual criticality systems use a less pessimistic, but with lower level of assurance, WCET estimation, and a safe, but pessimistic, WCET estimation. Initially, both high and low criticality tasks are executed. When a high criticality task exceeds its less pessimistic WCET, the system switches mode and low criticality tasks are usually dropped, reducing the overall system Quality of Service (QoS). To postpone mode switch, and thus, improve QoS, existing approaches explore the slack, created dynamically, when the actual execution of a task is faster than its WCET. However, existing approaches observe this slack only after the task has finished execution. To enhance dynamic slack exploitation, we propose a fine-grained approach that is able to expose the slack during the progress of a task, and safely uses it to postpone mode switch. The evaluation results show that the proposed approach has lower cost and achieves significant improvements in avoiding mode-switch, compared to existing approaches.

CCS Concepts: • Computer systems organization → Embedded software; Real-time systems.

Additional Key Words and Phrases: Worst-Case Execution Time, Interference-sensitive, Run-time Adaptation, Time-triggered, Response Time Analysis, Multi-cores

## ACM Reference Format:

Angeliki Kritikakou and Stefanos Skalistis. 2023. Mitigating Mode-Switch through Run-time Computation of Response Time. ACM Trans. Des. Autom. Electron. Syst. 37, 4, Article 111 (August 2023), 26 pages. https://doi.org/10.1145/1122445.1122456

## 1 INTRODUCTION

Mixed-critical systems [31] consist of applications with different levels of criticality. The application's criticality level partially depends on the consequences on the system, when the application fails to meet its timing constraints [26]. As a result, applications with different criticality levels have different properties and requirements. A high criticality application requires strict timing guarantees, i.e., ending before its deadline. To ensure timing guarantees, the Worst-Case Execution Time (WCET) of the application has to be considered. Nonetheless, the WCET estimation depends on the application's criticality level [11]; the same code has a higher WCET, if it requires a higher level of assurance, than it would, if it was considered as a non-critical application [11]. When computing WCET estimations, pessimism is introduced due to application and processor complexity. Applications have several execution paths, and thus, the worst-case path is used during WCET computation. Processor components, that take decisions dynamically, have a difficult-to-predict timing behavior, e.g., cache memories and branch predictors. When pessimistic WCET estimations

Authors' addresses: Angeliki Kritikakou, angeliki.kritikakou@irisa.fr, Univ Rennes, Inria, IRISA, Campus Beaulieu, Rennes, France, 35042; Stefanos Skalistis, stefanos.skalistis@collins.com, Collins Aerospace, xxxx, Cork, Ireland, xxxx.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org.

© 2023 Association for Computing Machinery.

1084-4309/2023/8-ART111 $15.00

https://doi.org/10.1145/1122445.1122456
are used, resources are over-allocated to high criticality applications. However, to provide an overall high Quality of Service (QoS), low criticality tasks should be executed as long as possible [11].

To improve the execution of low criticality tasks, while still guaranteeing safe execution of high criticality tasks, different WCET estimations are used for high criticality tasks; a pessimistic, with high assurance, upper bound ($C^H$) and a less pessimistic, with lower assurance, bound ($C^L$). Low criticality tasks are usually bounded by less pessimistic WCET estimations ($C^L$). A dual-criticality system has two executions modes: low criticality mode (LO-mode), executing low and high criticality tasks considering $C^L$, and high criticality mode (HI-mode), executing only high criticality tasks considering $C^H$. The system starts in LO-mode. Following the common approach, called BaseLine (BL), the system checks at a specific time instance, given by the $C^L$, if the task has finished execution. If not, the task is dropped, if it is a low criticality task, or the system switches from LO-mode to HI-mode, if it is a high criticality task. In HI-mode, low criticality tasks are usually dropped, e.g., [3, 5, 10]. Section 2 provides an illustration example of a mixed-criticality system and the BL approach.

However, in BL approach the mode-switch can occur at specific time instances, which are defined upfront before execution and are equal to the $C^L$ of each high criticality task. To improve the execution of low criticality tasks, existing approaches work on two directions: i) explore other strategies, than dropping low criticality tasks in HI-mode, and ii) explore static or dynamic ways to postpone the mode-switch. In this work, we focus on the second category. Note that, the proposed approach can be combined with approaches of the first category. Regarding the second category, existing static approaches determine the largest value, to be added to the $C^L$ of the high criticality tasks, while the system still remains schedulable; then, this value is used to extend the mode-switch further than $C^L$. Such methods are inspired by sensitivity analysis [27] and zero-slack [13, 14]. However, the static approaches are applied before execution, thus exploring only the existing slack due to system under-utilisation. On the contrary, dynamic approaches (DYN) are able to exploit the slack created during execution. When the actual execution time of a task is lower than its $C^L$, slack is created, since the task finished earlier than expected in LO-mode. This slack can be used by the next high criticality tasks and potentially postpone the mode-switch, e.g., through single budget [17], bailout protocol [7] and feedback control mechanisms [23]. However, existing DYN approaches are able to observe and use the dynamic slack, only after a task has terminated. This limitation is highlighted in the illustration example of Section 2.

To address the aforementioned limitation, this work extends the state-of-the-art with a safe and lightweight approach that dynamically computes, not only the slack created due to the early termination of tasks, but also the slack created due to the actual progress of active tasks, during execution, and safely uses it in order to postpone or even avoid mode-switch. Following this approach, there is no need to apply at run-time approaches that have high overhead and are typically applied offline, such as schedulability test or response time analysis, as in [28]. To achieve that, we propose a run-time controller, which is regularly evoked at a set of points inserted to the high criticality job (named instrumentation points) during execution, when the system is in LO-mode. The controller computes the available dynamic slack based on a safe run-time computation of the worst-case response-time bound of the running job. In this way, the actual execution progress of both finished jobs and currently active jobs is exposed at a given point. The controller computes any dynamic slack created between two instrumentation points of the job, based on the difference of the worst-case response-time bound computed at the current and previous points. More precisely, the worst-case response-time bound of a job of a high criticality task at an instrumentation point is computed by taking into account the actual time when the controller is evoked, the remaining worst case delay, that can still occur for this job from point until the job ends, due to preemption by higher priority (low and high criticality) tasks, and the remaining WCET, which corresponds to the
WCET of the code that remains to be executed from the point until the job ends. After the dynamic slack computation, a simple, and safe, condition decides whether a mode-switch can be postponed for later. From our extensive experiments, RRT was able to avoid mode-switch in 50.10% of the experiments, on average. As a result, on average, 60.34% low criticality tasks finished execution.

The paper is organized as follows: Section 2 describes the limitations of the state-of-the-art and the add-on of the proposed approach through and illustration example. Section 3 presents the system model. Section 4 presents the proposed approach and its Response Time Analysis (RTA). Section 5 presents the evaluation results. Section 6 presents the state-of-the-art, whereas Section 7 concludes this study.

## 2 ILLUSTRATION EXAMPLE

We use a simple example based on a dual-criticality mixed-critical system to illustrate the limitations of the state-of-the-art and show how the proposed approach remedies them. Table 1 shows the characteristics of the dual-criticality mixed-critical system, where tasks $τ_0$ and $τ_2$ are high criticality tasks, and tasks $τ_1$ and $τ_3$ are low criticality tasks. LO-mode mode is depicted in Fig. 1a) and HI-mode mode in Fig. 1b.

<table><caption>Table 1. Illustration example (Period: 40 time units).</caption><thead><tr><th>Task</th><th>C<sup>L</sup></th><th>C<sup>H</sup></th><th>Priority</th><th>Arrival</th><th>Criticality</th></tr></thead><tbody><tr><td>τ<sub>0</sub></td><td>10</td><td>20</td><td>3</td><td>0</td><td>HI</td></tr><tr><td>τ<sub>1</sub></td><td>8</td><td>-</td><td>2</td><td>3</td><td>LO</td></tr><tr><td>τ<sub>2</sub></td><td>8</td><td>16</td><td>0</td><td>4</td><td>HI</td></tr><tr><td>τ<sub>3</sub></td><td>4</td><td>-</td><td>1</td><td>12</td><td>LO</td></tr></tbody></table>

<figure><img src="image_1.png" /><figcaption>Fig. 1. Illustration example a) LO-mode and b) HI-mode.</figcaption></figure>

The behavior of the BL approach is illustrated in Fig. 2a, when $τ_2$ exceeds its $C_{τ_2}^L$ at time $t = 12$, and in Fig. 2b, when $τ_0$ exceeds its $C_{τ_0}^L$ at $t = 30$. The DYN limitation is depicted in Fig. 3. During execution, at $t = 3$, let's assume that $τ_0$ has already executed a large part of its code, but, still, the actual execution time is less than its $C_{τ_0}^L$ ($3 < 10$). Therefore, when $τ_0$ is preempted, it has not reached its $C_{τ_0}^L$, in order to decide mode-switch. At $t = 12$, when $τ_2$ reaches its $C_{τ_2}^L$ without terminating, the system has to switch to HI-mode, since no slack is available at that moment. The slack created due to the progress of $τ_0$ can be seen at this moment, since $τ_0$ has not finished execution. Only after task termination ($t = 20$), the slack created by $τ_0$ can be observed and used.

The proposed approach is based on the Run-time worst-case Response Time (RRT). To illustrate the proposed RRT approach, and keep the complexity of the illustration example low, we use a simple instrumentation for the high criticality tasks of Table 1, i.e., insertion of instrumentation points in a uniform way. As schematically depicted in Fig. 4a, we uniformly inserted five instrumentation points to $τ_0$ and four instrumentation points to $τ_2$, and the partial WCET, required to reach from one point the next one, is $C_{ptp}^H = 4$ in HI-mode and $C_{ptp}^L = 2$ in LO-mode. In section 4 we describe how the instrumentation points are placed in high criticality jobs. Let's now assume that i) at
<figure><img src="image_2.png" /></figure>

(a) Mode-switch at $t = 12$, where $\tau_2$ exceeds its $C_{\tau_2}^L$.

(b) Mode-switch at $t = 30$, where $\tau_0$ exceeds its $C_{\tau_0}^L$.

<figure><img src="image_3.png" /><figcaption>Fig. 3. DYN approach. Mode-switch at $t = 12$, $\tau_2$ exceeds its $C_{\tau_2}^L$ and no slack is available.</figcaption></figure>

$t = 3$ (Fig. 4b), due to a faster execution of $\tau_0$, compared to its WCET, the fourth instrumentation point is reached, and ii) the RRT computed in the previous points of $\tau_0$ was equal to the initial response-time bound, computed offline, i.e., $R_{\tau_0}^L = 30$. The controller computes a new value for the RRT in LO-mode ($RR^L$) of $\tau_0$, based on the actual time ($t$) at which the controller is evoked, the remaining worst-case delay ($RD_{hp}^L$) and the remaining WCET ($RC^L$) of $\tau_0$ from the fourth point until the task ends, i.e., $RR_{\tau_0}^L = t + RD_{hp}(\tau_0) + RC_{\tau_0}^L = 3 + (12 + 8) + 2 = 25$. The difference between the RRT of the current and previous points provides the dynamic slack in LO-mode, i.e., $DS^L = 5$. Mode-switch is decided based on whether the computed dynamic slack is higher than or equal to the additional time required to reach the next instrumentation point in the worst-case, denoted as $C_{ptp}$. This worst-case additional time is given when a high criticality task takes WCET in HI-mode, instead of WCET in LO-mode, to reach the next instrumentation point, i.e., $C_{ptp} = C_{ptp}^H - C_{ptp}^L$, e.g., $C_{ptp} = 2$ in the illustration example. At $t = 12$, the third instrumentation point of $\tau_2$ is reached and the RRT, computed at the previous points of $\tau_2$, is equal to the response-time bound computed offline, i.e., $R_{\tau_2}^L = 12$. A new value for the response-time bound in LO-mode of $\tau_2$ is computed, i.e., $RR_{\tau_2}^L = t + RD_{hp}(\tau_2) + RC_{\tau_2}^L = 12 + (0 + 0) + 2 = 14$. Comparing with the previously computed RRT, the slack between the two points is negative, i.e., -2. The overall dynamic slack is updated, $DS^L = 5 + (-2) = 3$. As the overall slack is higher than or equal to $C_{ptp}$, there is no need to perform mode-switch at $t = 12$; there is enough slack to reach the next instrumentation point and take the decision later, even if the task execution takes WCET in HI-mode. Thus, the proposed approach is able to avoid mode-switch, compared to DYN approach.

# 3 SYSTEM MODEL

## 3.1 System model

We consider a uni-processor system with a set of tasks $\mathcal{T}$ to be executed preemptively. A dual-criticality system is assumed, where each task has a level of criticality equal to either high ($H$) or low ($L$), with $H > L$. We use the basic mixed-criticality model, where the system has two modes of execution: i) LO-mode, where both high criticality tasks and low criticality tasks are executed on the processor, and ii) HI-mode, where only the high criticality tasks are executed on the processor. When a job of a low criticality task exceeds its WCET, the job is dropped, whereas when a high criticality job exceeds its WCET, a mode-switch occurs. The proposed approach has as goal to postpone or avoid mode-switch, even if a high criticality task exceeds its WCET, as long as it does
<figure><img src="image_4.png" /><figcaption>Fig. 4. RRT approach. a) Instrumentation of high criticality tasks and $C_{ptp}$ in LO-mode and in HI-mode, and b) No mode-switch, $\tau_2$ exceeds its $C_{\tau_2}^L$ at $t = 12$, but enough slack exist due to $\tau_0$ progress.</figcaption></figure>

<table><caption>Table 2. Summary of main notation</caption><thead><tr><th colspan="2">System model</th></tr></thead><tbody><tr><td>T, τ</td><td>Task τ belonging to task-set T</td></tr><tr><td>CL<sub>τ</sub></td><td>Criticality level CL of task τ, CL ∈ {H, L}</td></tr><tr><td>r<sub>τ</sub>, D<sub>τ</sub></td><td>Arrival time and deadline of task τ</td></tr><tr><td>C<sub>τ</sub><sup>CL</sup></td><td>WCET C<sub>τ</sub><sup>CL</sup> of task τ at criticality level CL</td></tr><tr><td>P</td><td>Common period P</td></tr></tbody><thead><tr><th colspan="2">Remaining WCET</th></tr></thead><tbody><tr><td>S</td><td>Set of functions S = {F<sub>0</sub>, F<sub>1</sub>, ..., F<sub>l</sub>}, with F<sub>0</sub> being the main function</td></tr><tr><td>G</td><td>The ECFG G = (V, E) of a function F</td></tr><tr><td>V</td><td>The set of nodes V = N ∪ C ∪ F ∪ {IN} ∪ {OUT} of an ECFG G</td></tr><tr><td>E</td><td>The sets of edges E ⊆ V × V of ECFG G</td></tr><tr><td>N ∈ N</td><td>Block of one or more binary instructions</td></tr><tr><td>C ∈ C</td><td>Block of binary instructions of a condition statement</td></tr><tr><td>F<sub>i</sub> ∈ F</td><td>Binary instructions of the function caller of a function F<sub>i</sub></td></tr><tr><td>IN, OUT</td><td>The input/output node of ECFG G</td></tr><tr><td>p<sub>τ</sub></td><td>A point of task τ</td></tr><tr><td>level[p<sub>τ</sub>], head[p<sub>τ</sub>]</td><td>The depth of point p<sub>τ</sub> and its ancestor point head[p<sub>τ</sub>]</td></tr><tr><td>C<sub>τ</sub>[p'<sub>τ</sub>-p<sub>τ</sub>]</td><td>Partial WCET from point p'<sub>τ</sub> to p<sub>τ</sub> of task τ</td></tr><tr><td>STI<sub>τ</sub></td><td>Structure & Timing Information (level, head & partial WCET of τ points)</td></tr><tr><td>RC<sub>τ</sub></td><td>Remaining WCET of task τ</td></tr></tbody><thead><tr><th colspan="2">Remaining Response Time</th></tr></thead><tbody><tr><td>C<sub>ptp</sub></td><td>Overhead to reach next point, with WCET in HI-mode, instead of LO-mode</td></tr><tr><td>PD<sub>hp(τ)</sub><sup>L</sup></td><td>Preemption delay of τ in LO-mode, due to higher priority tasks</td></tr><tr><td>RD<sub>hp(τ)</sub><sup>L</sup></td><td>Remaining preemption delay of τ in LO-mode, due to higher priority tasks</td></tr><tr><td>RR<sub>τ</sub><sup>L</sup></td><td>LO-mode remaining response time of τ in LO-mode</td></tr><tr><td>DS<sup>L</sup></td><td>Dynamic slack</td></tr><tr><td>Δ<sub>p+1</sub><sup>P</sup>x</td><td>Difference of x at point p and at point p + 1</td></tr></tbody></table>

not exceed its response time. We define the response time of a task $\tau_i$ per criticality-level, $R_{\tau_i}^{CL}$, and the response time when a mode-switch occurs, $R_{\tau_i}^*$, Each task, $\tau_i \in T$, is characterized by its arrival
time $r_{\tau_i}$, deadline $D_{\tau_i}$, criticality level $CL_{\tau_i}$ and the WCET $C_{\tau_i}^{CL}$ for each criticality level, i.e., $C_{\tau_i}^H$ and $C_{\tau_i}^L$. $C_{\tau_i}^{CL}$ is assumed to be monotonically non-decreasing, with increasing criticality level $CL$ [4]. Tasks are periodically executed with a common period $P$, i.e., at the $k$-th period a task releases a job at time $k \ast P + r_{\tau_i}$. Jobs can be either dependent or independent. We focus on constrained deadlines, i.e., $D_{\tau_i} \le P$. The task-set $\mathcal{T}$ is considered to be executed preemptively with a scheduling policy $S$ following a Fixed Priority (FP) scheme using a unique priority assignment algorithm (e.g. Audsley's Algorithm [2]). Notice that, a low criticality task could have higher priority than a high criticality task. Our task model depicts asynchronous mono-periodic task-sets. Multi-periodic task-sets could be unrolled to the hyper-period of the system, i.e., the least common multiple of the task periods, and the approach applied inside the hyper-period. Note that, in such a case, the unrolled jobs are executed once in the hyper-period and thus, they do not require additional memory to store information, as they can reuse the memory space of the previous job. Between hyper-periods, the dynamic slack is set to zero. More efficient ways to deal with multi-periodic task sets are future work. A summary of the main notation is presented in Table 2.

# 4 PROPOSED APPROACH

Our goal is to postpone, or even avoid, mode-switch, even if a high criticality job exceeds its WCET. To achieve that, the proposed approach regularly computes in a fine-grained and safe way the dynamic slack in LO-mode and uses it to safely postpone mode-switch. It takes into account not only the actual progress of the running high criticality job (that invoked the controller), but also the actual execution progress of the remaining active, but preempted, jobs and the actual execution time of already finished jobs. Fig. 5 overviews the proposed approach. Section 4.1 describes the design-time analysis, Section 4.2 presents the run-time control and Section 4.3 presents the approach safety. Table 3 summarises the acronyms.

<figure><img src="image_5.png" /><figcaption>Fig. 5. Overview of the proposed approach.</figcaption></figure>

## 4.1 Design-time system analysis

Design-time analysis performs the task instrumentation and extracts the information required for the run-time computation of the dynamic slack. We use the approach of [20] as a starting block, and leverage it in order to be applicable for the system under study. Note that, the approach of [20] is designed for only a single task with a unique WCET estimation running on one processor
<table><caption>Table 3. Summary of acronyms</caption><tr><td>QoS</td><td>Quality of Service</td><td>WCET</td><td>Worst-Case Execution Time</td></tr><tr><td>BL</td><td>BaseLine</td><td>RWCET</td><td>Remaining Worst-Case Execution Time</td></tr><tr><td>DYN</td><td>DYNamic</td><td>RRT</td><td>Run-time worst-case Response Time</td></tr><tr><td>LO-mode</td><td>LOw criticality mode</td><td>HI-mode</td><td>HIgh criticality mode</td></tr><tr><td>RTA</td><td>Response Time Analysis</td><td>FP</td><td>Fixed Priority</td></tr><tr><td>WCD</td><td>Worst-Case Delay</td><td>RWCD</td><td>Remaining Worst-Case Delay</td></tr><tr><td>CL</td><td>Criticality Level</td><td>STI</td><td>Structure and Timing Information</td></tr><tr><td>CFG</td><td>Control Flow Graph</td><td>ECFG</td><td>Extended Control Flow Graph</td></tr></table>

without preemption. As a result, it cannot be applied in systems where multiple periodic tasks with different criticalities are preemptively executed on the same processor. Our approach addresses this limitation by computing at run-time the worst-case response-time bound. To achieve this, not only information regarding the RWCET per high criticality task in LO-mode is needed, but also information regarding the overall system execution, i.e., the Worst-Case Delay (WCD) in LO-mode per high criticality task, due to the preemption from higher priority (low and high criticality) tasks in any period.

**High criticality task:** A high criticality task is described by a set of Control Flow Graph (CFGs), constructed by the assembly code. Each CFG corresponds to a function *F* of the high criticality task. Therefore, the high criticality task $\tau_i$ is a set of functions $S = \{F_0, F_1, ..., F_l\}$, with $F_0$ the main function.

**Definition 1.** The CFG of a function *F* is a directed graph *G* = (*V*, *E*), consisting of:

* A finite set of nodes *V* composed of 5 disjoint sub-sets $V = N \cup C \cup F \cup \{IN\} \cup \{OUT\}$:

i) $N \in N$ represents a block of one or more binary instructions,

ii) $C \in C$ represents the block of binary instructions of a condition statement,

iii) $F \in F$ represents the binary instructions of the function caller of a function *F* and links the node of the current function with the CFG of the function *F*,

iv) *IN* is the input node,

v) *OUT* is the output node,

* a finite set of edges $E \subseteq V \times V$ representing the control flow between nodes.

Therefore, a CFG can include the following components: i) a single node *N*, ii) an if-then-else component, i.e., the concatenation of a *C* conditional node with two mutually executed paths that have the same end node, iii) a loop component, i.e., the concatenation of a loop condition *C* with two mutually executed paths, one with the exit path and one with the loop repetition, and iv) a function call node *F*. F Fig. 6 illustrates how to obtain CFG through an example. L.1 to L.9 (Fig. 6c) handle the stack and initialise the local variables and correspond to $B_1$, which is a component of type *N*, (Fig. 6b), L.10 to L.14 describe the exit condition of the loop and correspond to $B_2$ (which is a component of type *C*), L.15 to L.26 describe the loop kernel and the increase of *i* and correspond to $B_3$ (component of type *N*), and L.27 to L.32 manage the stack and performs the return from the function call correspond to $B_4$ (component of type *N*). A special point *start* exists before task execution, which denotes the function call to the main function.

Instrumentation points $p_{\tau_i}$ are inserted in the high criticality task $\tau_i$, in order to evoke the controller that will compute the remaining WCET at run-time. Instrumentation points can be inserted before the execution of the first binary instruction of each node of CFG. Representing instrumentation points by a lower-case symbol, five disjoint sub-sets of instrumentation points
```c
344 1 int main(void) {
345 2   int i;
346 3   int A[10];
347 4   for (i=0; i<10; i++) {
348 5   A[i]=i;
349 6   }
350 7   return 0;
351 8   }
```

<figure><img src="image_6.png" /><figcaption>(b) Basic blocks</figcaption></figure>

```c
1 | main:
2 |     addi   sp, sp, -64
3 |     sw     ra, 60(sp)
4 |     sw     s0, 56(sp)
5 |     addi   s0, sp, 64
6 |     li      a0, 0
7 |     sw     a0, -12(s0)
8 |     sw     a0, -16(s0)
9 |     j       .LBB0_1
10 .LBB0_1:
11 | lw      a1, -16(s0)
12 | li      a0, 9
13 | blt     a0, a1, .LBB0_4
14 |     j     .LBB0_2
15 .LBB0_2:
16 | lw      a0, -16(s0)
17 | slli    a2, a0, 2
18 | addi    a1, s0, -56
19 | add     a1, a1, a2
20 | sw      a0, 0(a1)
21 |     j     .LBB0_3
22 .LBB0_3:
23 | lw      a0, -16(s0)
24 | addi    a0, a0, 1
25 | sw      a0, -16(s0)
26 |     j     .LBB0_1
27 .LBB0_4:
28 | li      a0, 0
29 | lw      ra, 60(sp)
30 | lw      s0, 56(sp)
31 | addi    sp, sp, 64
32 | ret
```

<caption>(c) Assembly code (RISC-V).</caption>

Fig. 6. Example: CFG is obtained from complied C code.

can exist, based on the node type: `{n}`, `{c}`, `{fi}`, `in`, `out`. Note that, the point *start* refers to the point before execution, i.e., point *in* of function $F_0$. Such instrumentation points can be implemented in several ways depending on which level of abstraction the high criticality task code is given and whether we can modify the hardware of the processor. When the source code is available, a function call can be inserted in the source code to call the controller code. When only the assembly code is available, we can modify the assembly code in order to add the call to the controller. When the binary code is available, we can obtain the assembly code from the binary code, for instance using a disassembler. If the hardware is modifiable, a hardware block can be inserted to monitor the program counter and execute the controller.

After the insertion of the instrumentation points, we use an ECFG parser in order to extract information regarding the ECFG structure that will allow us to distinguish different visits of the same instrumentation point during execution (e.g., in loops, function calls).

**Definition 2.** The structure information of a point $p_{\tau_i}$ is:

* The nested level of $p_{\tau_i}$, level[$p_{\tau_i}$], which is:

i) set to 0, if $p_{\tau_i}$ is the start point,

ii) set to 1, if $p_{\tau_i}$ is a sequential point between the IN and OUT of an ECFG,

iii) increased by 1, for each loop where $p_{\tau_i}$ resides in.

* The ancestor point of $p_{\tau_i}$, head[$p_{\tau_i}$], that indicates the point where a loop entry or a function call occurred. The head[$p_{\tau_i}$] of a point $p_{\tau_i}$ is:

i) the start point, if $p_{\tau_i}$ is a point with level 1 in the main function $F_0$,
ii) the function caller, if $p_{\tau_i}$ is a point with level 1 in the called function,

iii) the condition of the loop, if $p_{\tau_i}$ is inside a loop.

• The function call behavior, type[$p_{\tau_i}$], which is:

i) F_ENTRY, if $p_{\tau_i}$ is a function entry (function caller),

ii) F_EXIT, if $p_{\tau_i}$ is a function exit, i.e. the node where a function returns to,

iii) F_ENEX, if $p_{\tau_i}$ is both a function entry and a function exit, i.e. the point $p_{\tau_i}$ where the function returns is also a function caller,

iv) -, if $p_{\tau_i}$ is not related to function calls.

Let's illustrate the structure information with the example of Fig. 6b. With $b_1$, $b_2$, $b_3$ and $b_4$ being the points inserted in the beginning of each CFG block, we obtain: level[$b_1$]=1, level[$b_2$]=1, level[$b_4$]=1 and level[$b_3$]=2, head[$b_1$]=start, head[$b_2$]=start, head[$b_4$]=start, and head[$b_3$]=b_2, type[$b_1$]=-, type[$b_2$]=-, type[$b_4$]=-, and type[$b_3$]=--.

Last, we extract the timing information by extending the approach of [20] to be applied per criticality level.

**Definition 3.** Let $x_{\tau_i}$ and $p_{\tau_i}$ be two instrumentation points; the partial WCET between these points in a given criticality level CL is $C_{\tau_i}^{CL}[x_{\tau_i}, p_{\tau_i}] = C_{\tau_i}^{CL}[x_{\tau_i}] - C_{\tau_i}^{CL}[p_{\tau_i}]$, where $C_{\tau_i}^{CL}[x_{\tau_i}]$ denotes the WCET from point $x_{\tau_i}$ until the end of code execution and $C_{\tau_i}^{CL}[p_{\tau_i}]$ denotes the WCET from point $p_{\tau_i}$ until the end of execution.

Two types of partial WCET are computed: (1) For all points, we compute $C_{\tau_i}^{CL}[\text{head}[p_{\tau_i}] - p_{\tau_i}]$, and (2) For points placed in the entry of a loop, we compute the $C_{\tau_i}^{CL}$ between any two consecutive loop iterations ($j-1$ and $j$), i.e., $C_{\tau_i}^{CL}[p_{\tau_i}^{j-1} - p_{\tau_i}^j]$. If multiple paths exist between these points (e.g., branches of if-then-else components, function calls from different entry points), the minimum difference is maintained. Note that, the minimum value is required in order to be safe, since this value will be subtracted from the overall WCET, during RWCET computation at run-time [20].

The timing information extracted for Fig. 6 is: $C_{\tau_i}^{L}[\text{start}-b_1]$ and $C_{\tau_i}^{H}[\text{start}-b_1]$, $C_{\tau_i}^{L}[\text{start}-b_2]$ and $C_{\tau_i}^{H}[\text{start}-b_2]$, $C_{\tau_i}^{L}[\text{start}-b_4]$ and $C_{\tau_i}^{H}[\text{start}-b_4]$, $C_{\tau_i}^{L}[b_2-b_3]$ and $C_{\tau_i}^{H}[b_2-b_3]$, $C_{\tau_i}^{L}[b_2^{j-1}-b_2^j]$ with $j=0 \dots 9$ and $C_{\tau_i}^{H}[b_2^{j-1}-b_2^j]$ with $j=0 \dots 9$.

The above partial WCETs are computed in LO-mode and in HI-mode. Note that, the partial WCETs for LO-mode will be used by the run-time controller for RWCET computation in LO-mode. The partial WCETs for HI-mode are used only at design-time to compute the additional time required to reach the next instrumentation point, in the worst-case, denoted as point-to-point overhead $C_{ptp}$, used to safely decide mode-switch. The worst-case is when the high criticality job takes $C_{\tau_i}^{HI}[x_{\tau_i}, p_{\tau_i}]$, instead of $C_{\tau_i}^{LO}[x_{\tau_i}, p_{\tau_i}]$, to reach point $p_{\tau_i}$ from point $x_{\tau_i}$. It is computed as $C_{ptp}=\max(C_{ptp,F}, C_{ptp,B})$, where $C_{ptp,F}=\max(C_{\tau_i}^{H}[\text{head}[p_{\tau_i}] - p_{\tau_i}]) - C_{\tau_i}^{L}[\text{head}[p_{\tau_i}, p_{\tau_i}])$, $\forall i$ and $p_{\tau_i}$, and $C_{ptp,B}=\max(C_{\tau_i}^{H}[p_{\tau_i}^{j-1}, p_{\tau_i}^j] - C_{\tau_i}^{L}[p_{\tau_i}^{j-1}, p_{\tau_i}^j])$, $\forall i, p_{\tau_i} \in \mathcal{C}$, and $j$. The maximum difference provides the worst-case overhead among points.

**System Analysis:** Initially, we verify whether the task-set $\mathcal{T}$ is schedulable in LO-mode, HI-mode, and mode-switch. The task-set $\mathcal{T}$ at each mode is considered schedulable if the worst-case response-time bound $R_{\tau_i}$ of each task $\tau_i$ is not greater than its corresponding deadline $d_{\tau_i}$, for all periods. The worst-case response-time $R_{\tau_i}^{CL}$ of a task $\tau_i$, at each criticality level CL, is the greatest response-time of its jobs, where response-time of a job is the time interval from the job release to the job completion. To acquire the worst-case response-time of all tasks, the corresponding RTA for the selected scheduling policy is applied, as required by our system model. The worst-case delay of a high criticality task in LO-mode, denoted as $D_{hp}(\tau_i)$, due to the execution of higher priority tasks,
considering all periods, is given by $D_{hp(\tau_i)}^L = R_{\tau_i}^L - C_{\tau_i}^L$. The $D_{hp(\tau_i)}^L$ and $C_{\tau_i}^L$ are used to initialise the run-time controller variables at the beginning of each time period $T_{\tau_i}$.

<table><caption>**Algorithm 1:** Run-time control mechanism.</caption><tr><td>1</td><td>Function RTcontrol_start(C<sub>τi</sub><sup>L</sup>, D<sub>hp(τi)</sub><sup>L</sup>, k<sub>τi</sub>, T<sub>τi</sub>)</td><td></td></tr><tr><td>2</td><td>if (LO-mode is active) then</td><td>/* in low mode */</td></tr><tr><td>3</td><td>RC<sub>τi</sub><sup>L</sup> = C<sub>τi</sub><sup>L</sup>;</td><td></td></tr><tr><td>4</td><td>RD<sub>hp(τi)</sub><sup>L</sup> = D<sub>hp(τi)</sub><sup>L</sup>;</td><td></td></tr><tr><td>5</td><td>RR<sub>τi</sub><sup>L</sup> = k<sub>τi</sub> * T<sub>τi</sub> + D<sub>hp(τi)</sub><sup>L</sup> + C<sub>τi</sub><sup>L</sup>;</td><td></td></tr><tr><td>6</td><td>Function RTcontrol_exec(p<sub>τi</sub>, STI<sub>τi</sub>, RR<sub>τi</sub><sup>L</sup>, RD<sub>hp(τi)</sub><sup>L</sup>, RC<sub>τi</sub><sup>L</sup>)</td><td></td></tr><tr><td>7</td><td>if (LO-mode is active) then</td><td>/* in low mode */</td></tr><tr><td>8</td><td>t = get_current_time();</td><td></td></tr><tr><td>9</td><td>RC<sub>τi</sub><sup>L</sup> = Compute_RWCET(p<sub>τi</sub>, STI<sub>τi</sub>);</td><td></td></tr><tr><td>10</td><td>RR<sub>τi</sub><sup>L</sup> = t + RD<sub>hp(τi)</sub><sup>L</sup> + RC<sub>τi</sub><sup>L</sup>;</td><td></td></tr><tr><td>11</td><td>DS<sup>L</sup> = DS<sup>L</sup> + (RR<sub>τi</sub><sup>L</sup> - RR<sub>τi</sub><sup>L</sup>);</td><td></td></tr><tr><td>12</td><td>progress<sub>τi</sub> = get_total_execution(τi) + (t-get_latest_start_time(τi));</td><td></td></tr><tr><td>13</td><td>if (progress<sub>τi</sub> >= C<sub>τi</sub><sup>L</sup>) then</td><td></td></tr><tr><td>14</td><td>if (DS<sup>L</sup> &lt; C<sub>ptp</sub>) then</td><td></td></tr><tr><td>15</td><td>signal(HI-mode);</td><td></td></tr><tr><td>16</td><td>Function RTcontrol_end(C<sub>τi</sub><sup>L</sup>, lphc(τi))</td><td></td></tr><tr><td>17</td><td>if (LO-mode is active) then</td><td>/* in low mode */</td></tr><tr><td>18</td><td>for τj ∈ lphc(τi) do</td><td></td></tr><tr><td>19</td><td>RD<sub>τj</sub><sup>L</sup> = RD<sub>τj</sub><sup>L</sup> - C<sub>τi</sub><sup>L</sup>;</td><td></td></tr></table>

## 4.2 Run-time control for dynamic slack computation

During execution, the scheduler selects the job with the highest priority to be executed, until a higher priority job arrives. At an instrumentation point of the current active job, when the system is in LO-mode, the controller is executed, with the highest priority. Algorithm 1 depicts the run-time controller that implements our approach. It has three functionalities: i) at the beginning of the job execution, it performs initialization of a set of variables, ii) during job execution, it updates the slack based on its actual progress and verifies whether execution in LO-mode is still safe, otherwise it informs the scheduler for the mode-switch, and iii) when the job ends, the job contribution to the overall delay of lower priority jobs is removed.

**Beginning of period (L. 1-5):** As soon as the job is released at the beginning of a new period $k_{\tau_i}$, the remaining WCET in LO-mode is initialized with the overall WCET in LO-mode, i.e., $RC_{\tau_i}^L = C_{\tau_i}^L$. The remaining worst-case delay in LO-mode is initialized with the value computed offline, $RD_{hp(\tau_i)}^L = D_{hp(\tau_i)}^L$. Then, the worst-case response-time bound for period $k$ is computed as $RR_{\tau_i}^L = k_{\tau_i} * T_{\tau_i} + D_{hp(\tau_i)}^L + C_{\tau_i}^L$.

**During execution (L. 6-15):** The approach computes the new remaining WCET of the job of task $\tau_i$ in LO-mode at the current point, $RC_{\tau_i}^L'$. This corresponds to the WCET in LO-mode only of the code that remains to be executed, from point $p_{\tau_i}$ until the end of the job. For the computation of $RC_{\tau_i}^L'$ of
the running high criticality job, the proposed approach applies the approach of [20], leveraged for LO-mode. Algorithm 2 summarises the computation of $RC_{\tau_i}^L'$ at a point $p_{\tau_i}$. The algorithm takes as input the instrumentation point $p_{\tau_i}$ along with its Structure and Timing Information ($STI_{\tau_i}$), which includes the *type*, *level*, *head* and partial WCETs of the point, pre-computed during the design-time analysis of the high criticality task. To be able to compute the *RC*, without unrolling the code of the high criticality task, the computation is performed per level, with the help of the array $RL_{\tau_i}$. A local level $ll_{\tau_i}$ is used to depict the current nested level of point $p_{\tau_i}$, taking into account function calls and loops. The local level is computed by adding the $offset_{\tau_i}$ and the *level* of the point $p_{\tau_i}$ (L. 5). Note that, the *level*[$p_{\tau_i}$] depicts the level of nested loops inside the ECFG of a function, by definition. The $offset_{\tau_i}$ provides the level that must be added, because of any occurred function call. Therefore, when a function entry point is observed (C5 is true, L. 14), i.e., a function call occurs, we increase the offset with the level of the entry point (L. 15). When an exit point is observed (C1 is true, L. 2), i.e., a function returns, we decrease the offset by the level of the entry point (L. 3). Then, the observation level $o\_level_{\tau_i}$ is used to decide if we are traversing ECFG in a forward (C2 or C4 is true) or backward direction (C3 is true). When the ECFG is traversed in a forward direction, the remaining WCET in local level $ll_{\tau_i}$, $RL_{\tau_i}$ [$ll_{\tau_i}$], is computed by subtracting the partial WCET of the point $p_{\tau_i}$ from the remaining WCET computed on the previous local level (L. 7 and L. 11). By definition, the point in the previous local level is the head point of $p_{\tau_i}$. When the ECFG is traversed backward, we are in a loop. Thus, we have reached the point that corresponds the condition statement of the loop and we subtract the partial WCET computed between any two iterations, $j-1$ and $j$ (L. 9). In this way, the remaining WCET of the head point at local level $ll_{\tau_i}-1$ is updated accordingly, before entering the loop, where points have a local level equal to $ll_{\tau_i}$. Note that, before execution, the initialisation is as follows: $RL_{\tau_i}$ [0] = $C_{\tau_i}$ (the overall WCET of $\tau_i$), the remaining elements of the array $RL_{\tau_i}$ to zero, $offset_{\tau_i} = 0$, $o\_level_{\tau_i} = 0$, and $last\_point_{\tau_i}$ [0] = start.

Let's illustrate how the RWCET is computed for the example of Figure 6. At the first invocation of the controller at point c, $ll_{\tau_i} = 1$. Since $o\_level_{\tau_i} = 0$, the graph is traversed in forward direction and the RWCET is given by $RL_{\tau_i}$ [1] = $RL_{\tau_i}$ [0] - $C_{\tau_i}$ [start-c]. The rest of the variables are updated, i.e., $last\_point_{\tau_i}$ [1] = c and $o\_level_{\tau_i} = 1$. For the first invocation at point $n_2$, $ll_{\tau_i} = 2$. The graph is still traversed in forward direction and the RWCET is given by $RL_{\tau_i}$ [2] = $RL_{\tau_i}$ [1] - $C_{\tau_i}$ [c-n2], $last\_point_{\tau_i}$ [2] = $n_2$ and $o\_level_{\tau_i} = 2$. When c is invoked in the second iteration, $ll_{\tau_i} = 1$. Since $o\_level_{\tau_i} < ll_{\tau_i}$ and the last point in this level was c, the graph is now traversed in backward direction. The RWCET is updated by $RL_{\tau_i}$ [1] = $RL_{\tau_i}$ [1] - $C_{\tau_i}$ [c^{j-1}-c^j], $last\_point_{\tau_i}$ [1] = c and $o\_level_{\tau_i} = 1$. With this update, the RWCET will be correctly computed for the points inside the loop. The RWCET in the other points is computed in a similar way.

Then, the approach monitors the current time $t$ using low level functions of the platform that allow us to read the processor clock. The new value of the worst-case response-time bound of job $\tau_i$ at point $p_{\tau_i}$ ($RR_{\tau_i}^L$), is computed at run-time by adding to the current time $t$, the updated remaining WCET of task $\tau_i$ in LO-mode ($RC_{\tau_i}^L'$) and the remaining delay for task $\tau_i$ due to higher priority (both low and high criticality) tasks in LO-mode. The difference between the updated value, $RR_{\tau_i}^L'$, and the previously computed value, $RR_{\tau_i}^L$, provides in a safe way any new slack (positive or negative) created due to the progress made between two instrumentation points of the job. The overall slack $DS^L$ is updated accordingly. The actual progress of the job is computed based on the total execution up this point, using information provided by the scheduler. More precisely, the *get_total_execution*($\tau_i$) denotes the sum of all previous execution fragments, where $\tau_i$ was preempted, and *get_latest_start_time*($\tau_i$) is the time instance that the current fragment of $\tau_i$ started execution. Note that, this value is used only to check whether the $C_{\tau_i}^L$ has been reached, and thus, to enable the safe condition that checks for mode-switch. The safety condition verifies
<table><caption>**Algorithm 2:** Run-time computation of remaining $RC_{\tau_i}$ at point $p_{\tau_i}$.</caption><thead><tr><th></th><th></th><th></th></tr></thead><tbody><tr><td>1</td><td>Function Compute_RWCET(p<sub>τi</sub>, STI<sub>τi</sub>)</td><td></td></tr><tr><td>2</td><td>if (type[p<sub>τi</sub>] == F_EXIT || F_ENEX) then</td><td>/* C1 */</td></tr><tr><td>3</td><td>offset<sub>τi</sub> = offset<sub>τi</sub> - level[p<sub>τi</sub>];</td><td></td></tr><tr><td>4</td><td>o_level<sub>τi</sub> = o_level<sub>τi</sub> - 1;</td><td></td></tr><tr><td>5</td><td>ll<sub>τi</sub> = offset<sub>τi</sub> + level[p<sub>τi</sub>];</td><td></td></tr><tr><td>6</td><td>if (o_level<sub>τi</sub> &lt; ll<sub>τi</sub>) then</td><td>/* C2 */</td></tr><tr><td>7</td><td>RL<sub>τi</sub>[ll<sub>τi</sub>] = RL<sub>τi</sub>[ll<sub>τi</sub>] - C<sub>τi</sub>[head[p<sub>τi</sub>]-p<sub>τi</sub>];</td><td></td></tr><tr><td>8</td><td>else if (last_point<sub>τi</sub>[ll<sub>τi</sub>] == p<sub>τi</sub>) then</td><td>/* C3 */</td></tr><tr><td>9</td><td>RL<sub>τi</sub>[ll<sub>τi</sub>] = RL<sub>τi</sub>[ll<sub>τi</sub> - 1] - C<sub>τi</sub>[p<sub>τi</sub><sup>j-1</sup>, p<sub>τi</sub><sup>j</sup>];</td><td></td></tr><tr><td>10</td><td>else</td><td>/* C4 */</td></tr><tr><td>11</td><td>RL<sub>τi</sub>[ll<sub>τi</sub>] = RL<sub>τi</sub>[ll<sub>τi</sub>] - C<sub>τi</sub>[head[p<sub>τi</sub>]-p<sub>τi</sub>];</td><td></td></tr><tr><td>12</td><td>last_point<sub>τi</sub>[ll<sub>τi</sub>] = p<sub>τi</sub>;</td><td></td></tr><tr><td>13</td><td>o_level<sub>τi</sub> = ll<sub>τi</sub>;</td><td></td></tr><tr><td>14</td><td>if (type[p<sub>τi</sub>] == F_ENTRY || F_ENEX) then</td><td>/* C5 */</td></tr><tr><td>15</td><td>offset<sub>τi</sub> = offset<sub>τi</sub> + level[p<sub>τi</sub>]</td><td></td></tr><tr><td>16</td><td>return RL<sub>τi</sub>[ll<sub>τi</sub>];</td><td></td></tr></tbody></table>

if it is still safe to continue execution in LO-mode, i.e., whether enough slack exists to reach the next instrumentation point in the worst-case. Otherwise, we switch to HI-mode by suspending low criticality tasks.

**End of execution (L. 16-19):** When a task $\tau_i$ finishes, it informs the lower priority, high criticality, tasks $lphc(\tau_i)$, that have been preempted from the task $\tau_i$. This is achieved by updating their worst-case delay, through subtraction of the overall WCET of $\tau_i$ in LO-mode, i.e., $C_{\tau_i}^L$.

Due to the instrumentation points inserted to the high criticality task $\tau_i$, a controller is invoked during execution and re-computes in a safe way the remaining WCET (RWCET), $RC_{\tau_i}$ at each point $p_{\tau_i}$, based on the task progress. $RC_{\tau_i}$ is the $C_{\tau_i}$ of the rest of the code that remains to be executed from point $p_{\tau_i}$ until the high criticality task $\tau_i$ ends.

## 4.3 Safety

In this section, we prove that the proposed run-time approach is safe, i.e., tasks respect their deadlines and system execution is correct. We will follow a two-step approach to prove the safety of the proposed method, as the former will allow us to build up the safety proof of the latter. At step one, we consider the extreme case where each instruction of a high criticality task is also an instrumentation point, and thus, any preemption has to occur at an instrumentation point. Considering the maximum number of points is, of course, a mathematical artifact that would enable us to prove that the approach is safe in all cases and is not envisioned for application in real-life. At step two, having proven that the proposed method is safe for the extreme case, we will prove that by removing an instrumentation point, it only impacts the slack that is exposed between two consecutive points. This means that by removing points, less slack is computed, while the proposed approach remains safe for an arbitrary number of points.

To ease notation, for a given a point $p_{\tau_i}$, we will refer to the previous visited point as $p_{\tau_i} - 1$ and to the next point as $p_{\tau_i} + 1$, even if they are the same instrumentation point, e.g. in a loop. This suffices, since the sequence of visited points, during execution, constitutes a linear execution
path, as if all loops were unrolled and all function calls were in-lined [19]. We will also refer to any execution between two points of a job as a segment.

### 4.3.1 Step 1: Each instruction corresponds to an instrumentation point.

**Lemma 1.** For any job of a high-criticality task $\tau_o$ that is executed non-preemptively in LO-mode, if the previous jobs (of the same or other tasks) executed with precisely their worst-case behavior in LO-mode, then the proposed run-time control correctly signals a mode switch, when an overrun occurs, and $\tau_o$ always respects its deadline.

**PROOF.** According to L. 13-14 (Alg. 1), a mode switch will occur during the execution of job j of task $\tau_o$, iff the progress of $\tau_o$ is greater or equal to its $C_{\tau_o}^L$ ($progress_{\tau_o} \ge C_{\tau_o}^L$) and the slack $DS^L$ is less than the point-to-point overhead $C_{\rho p t}$. Assuming that the overrun occurs at some point $p_{\tau_o}^o$ of the unique points $P_{\tau_o}$ of task $\tau_o$; at that point, the progress would be, based on L. 12, equal to the actual execution of all previously executed segments due to preemption (first term) plus the execution time, since the job was last scheduled (second term). Since the job overruns at point $p_{\tau_o}^o$, its actual execution time is greater than $C_{\tau_o}^L$, thus the condition $progress_{\tau_o} \ge C_{\tau_o}^L$ holds. Given two consecutive points p, p + 1 the computed dynamic slack is (L. 10-11):

$$DS^{L'} = DS^L + (RR_{\tau_o}^L - RR_{\tau_o}^{L'}) \Rightarrow \qquad (1)$$

$$\Delta_p^{p+1} DS^L = \Delta_{p+1}^p t + \Delta_{p+1}^p RD_{hp}(\tau_o) + \Delta_{p+1}^p RC_{\tau_o}^L \qquad (2)$$

where $\Delta_{p+1}^p x$ is difference operator between the value of the associated variable x at point p and its value at point p + 1, e.g. $\Delta_{p+1}^p t = t_p - t_{p+1} = -\Delta_{p+1}^{p+1} t$. Applying Equation 2 for all pairs of consecutive points up to $p_{\tau_o}^o$ we establish the total slack as:

$$\sum_{p \in P_{\tau_o}} p_{\tau_o}^p \Delta_p^{p+1} DS^L = \sum_{p \in P_{\tau_o}} p_{\tau_o}^p \left( \Delta_{p+1}^p t + \Delta_{p+1}^p RD_{hp}(\tau_o) + \Delta_{p+1}^p RC_{\tau_o}^L \right) \Rightarrow \qquad (3)$$

$$DS_{p_{\tau_o}^o}^L = DS_{p_{\tau_o}^o}^L + \sum_{p \in P_{\tau_o}} p_{\tau_o}^p \Delta_{p+1}^p t + \sum_{p \in P_{\tau_o}} p_{\tau_o}^p \Delta_{p+1}^p RD_{hp}(\tau_o) + \sum_{p \in P_{\tau_o}} p_{\tau_o}^p \Delta_{p+1}^p RC_{\tau_o}^L \qquad (4)$$

where $DS_{p_{\tau_o}^o}^L$ is the available slack at the first point $p_{\tau_o}^o$ of the running task. Since all previous tasks executed with precisely their worst-case behavior in LO-mode, $DS_{p_{\tau_o}^o}^L$ is equal to zero. In addition, since the task is executed non-preemptively (assumption of this Lemma), the second sum, containing the remaining preemptions, equals zero. The first sum is equal to the progress of task $\tau_o$. Note that, the value is negative, since in $\Delta_{p+1}^p t$, later time instances (with larger values) are subtracted from earlier time instances (with smaller values). The last sum equals to the partial WCET of task $\tau_o$ from the first point up to $p_{\tau_o}^o$, since $C_{\tau_o}^L = \sum_{p \in P_{\tau_o}} p_{\tau_o}^p \Delta_{p+1}^p RC_{\tau_o}^L + \sum_{p \in P_{\tau_o}} p_{\tau_o}^p \Delta_{p+1}^p RC_{\tau_o}^L$. Thus, the last sum is clearly less than $C_{\tau_o}^L$ (assuming that the computation of remaining WCET (L. 9) is safe, which was proven in [19]). We therefore establish:

$$DS_{p_{\tau_o}^o}^L = -progress_{\tau_o} + \left( C_{\tau_o}^L - \sum_{p \in P_{\tau_o}} p_{\tau_o}^p \left( \Delta_{p+1}^p RC_{\tau_o}^L \right) \right) \qquad (5)$$
Since task $\tau_o$ has overrun, i.e. $\text{progress}_{\tau_o} \ge C_{\tau_o}^L$ it follows that:

$$DS_{p_{\tau_o}^o}^L \le -C_{\tau_o}^L + C_{\tau_o}^L - \sum_{p \in P_{\tau_o}}^{p \ge p_{\tau_o}^o} \left( \Delta_{p+1}^p RC_{\tau_o}^L \right) \Rightarrow DS_{p_{\tau_o}^o}^L \le 0 \quad (6)$$

which satisfies the condition $DS^L < C_{ptp}$ and, therefore, concludes the proof. □

**Corollary 1.** Given two consecutive points $p, p+1$ of any job of task $\tau_i$, that are executed non-preemptively, the approach will correctly signal an overrun if it occurs at point $p+1$.

Having this fundamental guarantee, i.e., for two consecutive points, executed non-preemptively, the run-time control is safe, allows us to focus on what happens when preemptions and underruns/overruns occur, collectively. As in this extreme case we assumed the maximum number of instrumentation points, some of these points will coincide with the preemption points. Thus, two consecutive instrumentation points of the same task are always executed non-preemptively or a pre-emption occurred at the former point. In the following lemmas we prove each separate case with respect to the amount of slack available and whether a mode-switch has already occurred. All lemmas assume that a schedulable task-set $\mathcal{T}$ is given and that $p_{\tau_o}^o$ is the first point where some job of a high-criticality task overruns, with the response-time bound of that point $p_{\tau_o}^o \in P_{\tau_o}$ is $R_{p_{\tau_o}^o}^{CL}$ in CL-mode, with $CL \in \{H, L\}$ and the actual time at that point is $t_{p_{\tau_o}^o}$.

**Lemma 2.** For any job of a high-criticality task $\tau_u$ that is executed non-preemptively in LO-mode and underruns by $U$, the computed slack is never greater than the underrun.

**PROOF.** Since the task $\tau_u$ is executed non-preemptively it suffices that the difference between the slack at the beginning of execution, i.e. $DS_{p_{\tau_u}^s}^L$, and at the end of execution, i.e. $DS_{p_{\tau_u}^e}^L$, is not greater than the underrun $U$, where $p_{\tau_u}^s, p_{\tau_u}^e$, are the instrumentation points at the beginning and end of the task, respectively. Applying Equation 4 for the end of execution we acquire:

$$DS_{p_{\tau_u}^e}^L = DS_{p_{\tau_u}^e}^L + \sum_{p \in P_{\tau_u}}^{p < p_{\tau_u}^e} \Delta_{p+1}^p t + \sum_{p \in P_{\tau_u}}^{p < p_{\tau_u}^e} \Delta_{p+1}^p RD_{hp}(\tau_u) + \sum_{p \in P_{\tau_u}}^{p < p_{\tau_u}^e} \Delta_{p+1}^p RC_{\tau_o}^L \quad (7)$$

The first sum is equal to the progress of task $\tau_u$, which is equal to its WCET $C_{\tau_u}^L$ minus the amount of underrun $U$. Note that, the value is negative, since in $\Delta_{p+1}^p t$, later time instances (with larger values) are subtracted from earlier time instances (with smaller values). In addition, since the task is executed non-preemptively (assumption of this Lemma), the second sum, containing the remaining preemptions, equals zero. The last sum equals to the partial WCET of task $\tau_u$ from the first point $p_{\tau_u}^s$ up to $p_{\tau_u}^e$, i.e. its WCET $C_{\tau_u}^L$. Therefore, we establish:

$$DS_{p_{\tau_u}^e}^L - DS_{p_{\tau_u}^s}^L = -(C_{\tau_u}^L - U) + (0) + (C_{\tau_u}^L) \Rightarrow DS_{p_{\tau_u}^e}^L - DS_{p_{\tau_u}^s}^L = U \quad (8)$$

Thus, the computed slack is no greater than the amount of underrun $U$, which concludes this proof. □

**Lemma 3.** Given the first point $p_{\tau_o}^o$, where some job of a high-criticality task overruns and there is not enough slack to reach the next point, a mode-switch will occur and the next point $p_{\tau_o}^o + 1$ will respect its response-time bound in mode HI-mode, i.e. $t_{p_{\tau_o}^o+1} \le R_{p_{\tau_o}^o+1,\tau_o}^H$, when the mode-switch is being controlled by the proposed approach.

**PROOF.** Since we assume the maximum number of points, the segment of the current job of task $\tau_o$ from $p_{\tau_o}^o - 1$ to $p_{\tau_o}^o$, is executed non-preemptively; if a preemption existed, it would be either at
$p_{\tau_o}^o - 1$ or $p_{\tau_o}^o$. Thus, according to Corollary 1, if there is not enough slack, the overrun would be correctly detected at point $p_{\tau_o}^o$ and since there is not enough slack a mode-switch will occur.

During the mode-switch, by definition of RTAs for mixed-critical systems, all points $p$ that have a larger response-time bound at mode switch, i.e., $R_p^* \ge R_{p_{\tau_o}}^*$, will respect their response-time bound $t_p \le R_p^*$, and thus, high-criticality tasks will meet their deadlines. Similarly, when the system has fully transitioned to HI-mode, high-criticality tasks will meet their deadlines, since the task-set has been deemed schedulable. □

Having established that the approach behaves correctly, when there is not enough slack, and high-criticality tasks meet their deadlines, we now establish correctness in case there is enough slack, i.e. $DS_{p_{\tau_o}}^L \ge C_{ptp}$. An amount of slack existing at an overrunning point $p_{\tau_o}^o$ can only be due two orthogonal reasons. The first reason is that the slack existed at the start of execution of the current job of $\tau_o$ which is addressed by Lemma 4. The other reason is due to some jobs of other tasks $\tau_u$, that preempted the current job of $\tau_o$, have completed their execution and underrun in LO-mode, prior to $t_{p_{\tau_o}^o}$, which is addressed by Lemma 5. Note that, since $p_{\tau_o}^o$ is the first point to overrun, its actual execution (progress at $\tau_o$) is no less than its WCET in LO-mode, $C_{\tau_o}^L$. Thus, any slack at point $p_{\tau_o}^o$ cannot occur because of any underrun of the current job of $\tau_o$ at some previous points.

**Lemma 4.** Given the first point $p_{\tau_o}^o$, where some job of a high-criticality task overruns and there is enough slack to reach the next point, i.e. $DS_{p_{\tau_o}}^L \ge C_{ptp}$, and that slack existed at the start of execution of the current job of $\tau_o$ (denoted as point $p_{\tau_o}^s$), then no mode-switch will occur and all tasks will meet their deadlines if they do not overrun, when the mode-switch is being controlled by the proposed approach.

*PROOF.* Since all subsequent tasks are assumed not to overrun, it suffices to show that the computed slack at $p_{\tau_o}^o$ is not greater than the underrun of previous jobs (of the same or different tasks) at that point. This is sufficient as from the response time perspective, the overrun execution is equivalent to some other execution, where the underrun jobs of tasks $\tau_u$ executed for (at most) their WCET in LO-mode, and thus, the overrun job of task $\tau_o$ executes for less than its $C_{\tau_o}^L$ at the point of overrun $p_{\tau_o}^o$. The fact that the computed slack at $p_{\tau_o}^o$ is not greater than the underrun of previous jobs is nevertheless given by Lemma 2. □

**Lemma 5.** Given the first point $p_{\tau_o}^o$, where some job of a high-criticality task overruns and there is enough slack to reach the next point, i.e. $DS_{p_{\tau_o}}^L \ge C_{ptp}$, and that slack was created by underrunning jobs that preempted $\tau_o$, then no mode-switch will occur and all tasks will meet their deadlines if they do not overrun, when the mode-switch is being controlled by the proposed approach.

*PROOF.* Since all subsequent tasks are assumed not to overrun, it suffices to show that the computed slack at $p_{\tau_o}^o$ is not greater than the underrun at that point. This is sufficient as from the response time perspective, the overrun execution is equivalent to some other execution, where the underrun jobs of tasks $\tau_u$ executed for (at most) their WCET in LO-mode, and thus, the overrun job of task $\tau_o$ executes for less than its $C_{\tau_o}^L$ at the point of overrun $p_{\tau_o}^o$. Following Equation 4, considering preemptions, the sum $\sum_{p \in P_{\tau_o}} \Delta p^{p<p_{\tau_o}^o} t$ contains both the progress of the job of task $\tau_o$ and the actual progress of the job of tasks $\tau_u$ that preempted $\tau_o$. Since the job of task $\tau_o$ overrun at point $p_{\tau_o}^o$, its progress is equal to its WCET in LO-mode, i.e. $C_{\tau_o}^L$. Let $hpjf(\tau_o)$, be the set of jobs that preempted
the job of $\tau_o$ and finished, i.e., $hpjf(\tau_o) \subseteq hp(\tau_o)$. We establish:

$$ \sum_{p \in P_{\tau_o}}^{p < p_{\tau_o}^o} \Delta_{p+1}^p t = - \sum_{p \in P_{\tau_o}}^{p < p_{\tau_o}^o} \Delta_p^{p+1} t = - \left( C_{\tau_o}^L + \sum_{j_{\tau_u} \in hpjf(\tau_o)} \sum_{p \in P_{\tau_u}} \Delta_{p+1}^p t \right) = \quad (9) $$

$$ = -C_{\tau_o}^L - \left( \left( \sum_{j_{\tau_u} \in hpjf(\tau_o)} C_{\tau_u}^L \right) - U_p \right) = -C_{\tau_o}^L - \left( \sum_{j_{\tau_u} \in hpjf(\tau_o)} C_{\tau_u}^L \right) + U_p \quad (10) $$

where $U_p \ge 0$ is the total amount of underrun, if any, of the jobs that preempted the current job of $\tau_o$. Thus, the computed slack is established as (Equation 4):

$$ DS_{p_{\tau_o}^o}^L = DS_{p_{\tau_o}^s}^L - C_{\tau_o}^L - \left( \sum_{j_{\tau_u} \in hpjf(\tau_o)} C_{\tau_u}^L \right) + U_p + \sum_{p \in P_{\tau_o}}^{p < p_{\tau_o}^o} \Delta_{p+1}^p RD_{hp(\tau_o)}^L + \left( C_{\tau_o}^L - \sum_{p \in P_{\tau_o}}^{p \ge p_{\tau_o}^o} \Delta_{p+1}^p RC_{\tau_o}^L \right) \Rightarrow \quad (11) $$

$$ DS_{p_{\tau_o}^o}^L = U_p + DS_{p_{\tau_o}^s}^L + \left( - \sum_{j_{\tau_u} \in hpjf(\tau_o)} C_{\tau_u}^L + \sum_{p \in P_{\tau_o}}^{p < p_{\tau_o}^o} \Delta_{p+1}^p RD_{hp(\tau_o)}^L \right) - \sum_{p \in P_{\tau_o}}^{p \ge p_{\tau_o}^o} \Delta_{p+1}^p RC_{\tau_o}^L \quad (12) $$

According to Algorithm 1 (L. 16-19) when a job finishes execution, it subtracts its WCET from the remaining delay of its lower priority, high criticality tasks that it has preempted. Thus, the jobs $j_{\tau_u} \in hpjf(\tau_o)$ that preempted the current job of $\tau_o$, have subtracted their WCET from $RD_{hp(\tau_o)}$, hence the terms in parenthesis cancel each other. The last sum of Equation 12 is greater than zero, since it is the partial WCET of $\tau_o$ from the start point up to point $p_{\tau_o}^o$. Thus, the slack $DS_{p_{\tau_o}^o}^L$ at point $p_{\tau_o}^o$ is no greater than any underrun that was created during execution of $\tau_o$ plus the slack $DS_{p_{\tau_o}^s}^L$ that $\tau_o$ started with. Therefore, we have shown that the execution is equivalent, from a response time perspective, to an execution where the underrun jobs executed for at most their WCET in LO-mode and the overrun job of task $\tau_o$ executed for less than its $C_{\tau_o}^L$ at the point of overrun, thus proving that the next point $p_{\tau_o}^o + 1$ will respect its response-time bound. □

**Theorem 6 (Time safety).** Given a schedulable task-set $\mathcal{T}$ where the mode switch is being controlled by the proposed approach, the tasks always respect their deadlines.

**PROOF.** In Lemma 4 and Lemma 5 it was proven that the execution to the first point of overrun is safe, i.e. either a mode switch will occur or there is enough slack to proceed to the next point. In addition, the execution in case of enough slack is equivalent, in terms of time, to an execution where the under-running task(s) executed for at most their WCET in LO-mode and the overrunning task $\tau_o$ executed for less than its $C_{\tau_o}^L$ at the point of overrun. As a result, that point can be considered as not having an overrun and some other future point will be the first to overrun. By iterative application of those Lemmata, until a mode switch occurs or the end of execution, to all points, we conclude our proof. □

**4.3.2 Step 2: Impact of removing instrumentation points.** Following, we prove that removing points preserves safety of the proposed approach and it only impacts the exposed slack.

**Theorem 7.** Any task $\tau_i$ will meet its deadline, if some instrumentation points are removed.
PROOF. Applying Equation 2 to three consecutive points $p-1, p, p+1$ of a high-criticality task, we establish:

$$ \Delta_{p-1}^{p} DS^{L} = \Delta_{p}^{p-1} t + \Delta_{p}^{p-1} RD_{hp}(\tau_{i}) + \Delta_{p}^{p-1} RC_{\tau_{i}}^{L} \quad (13) $$

$$ \Delta_{p}^{p+1} DS^{L} = \Delta_{p+1}^{p} t + \Delta_{p+1}^{p} RD_{hp}(\tau_{i}) + \Delta_{p+1}^{p} RC_{\tau_{i}}^{L} \quad (14) $$

By adding the equations together, the computed slack, if point $p$ did not exist, is:

$$ \Delta_{p-1}^{p+1} DS^{L} = \Delta_{p+1}^{p-1} t + \Delta_{p+1}^{p-1} RD_{hp}(\tau_{i}) + \Delta_{p+1}^{p-1} RC_{\tau_{i}}^{L} \quad (15) $$

This effectively states that the slack computation remains the same, when a point is removed, and becomes visible only at the next point. Since the control algorithm decides if there is enough slack to reach the next point (L. 14) based on the point-to-point WCET overhead $C_{ptp}$, Lemma 1 and Theorem 6 still applies, hence the response-time bound cannot increase. Thus, by iteratively removing points, we prove that any assignment of instrumentation points is safe. □

# 5 EXPERIMENTAL EVALUATION

To evaluate the proposed approach (RRT), we compare the run-time control overhead and the performance, with respect to the mode-switch decisions and the execution of the low criticality tasks, with the: i) BaseLine (BL) approach, which switches mode when a high criticality job exceeds its $C^L$, such as [3, 5, 10], and ii) Dynamic (DYN) approach, which observes the dynamic slack, but only after a job finishes, such as [7, 17, 23].

## 5.1 Run-time control overhead

For the timing overhead, we implemented the controllers of RRT, DYN and BL approaches on the TMS320C6678 chip (TMS) of Texas Instrument [29] (Table 4). The overhead in cycles, depicted in Table 5, is obtained by applying a measurement-based approach. The measurements have been obtained using the processor's local timer during the controller execution and we have followed the approach of multiple executions, where each controller is executed 50 times and we maintain the largest observed value.

<table><caption>Table 4. TMS platform (8 DSP cores).</caption><thead><tr><td>Instr./cycle</td><td>Freq.</td><td>Instr. L1</td><td>Data L1</td><td>L2</td><td>L3</td><td>DDR3</td></tr></thead><tbody><tr><td>8</td><td>1 GHz</td><td>32 KB</td><td>32 KB</td><td>512 KB</td><td>4 MB</td><td>512 MB</td></tr></tbody></table>

To obtain the overall overhead, we compute how many times the actions of each mechanism will be performed, which depends on the task set and the actual execution.

* For the BL approach, a timer must be set, before the task starts execution, in order to trigger an interrupt when $C^L$ has been reached, and check for mode-switch [18]. The timer is set in the beginning of a job execution (895 cycles) and there is a single time moment when the BL controller will be executed (192 cycles), i.e., when the timer is triggered. In this overhead, we need to add the cost due to potential preemptions. Each time the job is preempted, its timer has to be paused, as a new timer will be set with the WCET in low mode of the higher priority job that will be now executed. When the execution returns to the preempted job, the timer needs to be resumed with the WCET in low mode (895 cycles) of the preempted job. Thus, the overhead of the BL mechanism per job is given by $O_{BL} = (895 + 192) + 895 * \#preemptions = 1,087 + 895 * \#preemptions$. The minimum overhead is given when the job is not preempted. For the maximum overhead, the worst-case is when a high-criticality job, that has the lower priority, is preempted sequentially
(i.e., no nested preemption takes place). In the worst-case, the number of preemption is equal to the number of jobs, that have a higher priority. Figure 7a depicts the cost of BL mechanism based on the number of preemptions.

* For the DYN approach, on top of the overhead due to preemptions (similar to BL), the controller may be evoked many times in order to check for the mode-switch. The number of possible evocations depends on how many of the higher priority tasks, that have preempted the task, have created slack, and whether the slack has been used to extend the WCET in low mode, each time. When a higher priority task finishes execution, it updates the dynamic slack (45 cycles). When the timer is triggered, the DYN controller is executed (252 cycles). If slack exists, it is used to extend the WCET in low mode (895 cycles to re-set the timer). The overhead of the DYN mechanism per task is given by $O_{DYN} = (895 + 252) + (895 + 45) * \#preemptions + (252 + 895) * \#extensions = 1, 147+940 * \#preemptions + 1, 147 * \#extensions$. Similar to BL, the minimum overhead is when the task is not preempted. For the maximum overhead, the worst-case is when all tasks with higher priorities, thus they preempted the task, created slack, and when between two preemptions, the task has reached the mode-switch point and extended the WCET in low, but not enough so as the task can finish execution. Figure 7a gives the DYN cost as box plot, considering the minimum and the maximum possible extensions for each number of preemptions.

* On the contrary, the proposed approach does not require the use of such a timer, that requires to be paused and resume during job preemptions, inserting high overhead. The RRT overhead depends on how many times the controller is evoked and it is exactly bounded by the number of instrumentation points. When the job finishes execution, the preemption delay of the high criticality low priority jobs (lphc), that has preempted, is updated. The RRT overhead is given by $O_{RRT} = 42 + 274 * \#points + 28 * \#lphc$. The maximum cost is given when all the points evoke the controller, i.e., no mode-switch took place, and only one low criticality task exist in the task set, and thus, the high priority high criticality task will have to update, at the end of execution, all the low priority high criticality tasks. Figure 7b depicts in box plots (considering 1 up to 31 low priority high criticality tasks that need to be updated) for 10 up to 100 instrumentation points.

<table><caption>Table 5. Overhead of run-time control (cycles).</caption><thead><tr><th colspan="3">Start</th><th colspan="2">Execution</th><th colspan="2">End</th></tr><tr><th>App.</th><th>Action</th><th>Cyc.</th><th>Action</th><th>Cyc.</th><th>Action</th><th>Cyc.</th></tr></thead><tbody><tr><td rowspan="3">BL</td><td rowspan="3">Set timer</td><td rowspan="3">895</td><td>Interrupt</td><td>162</td><td rowspan="3">N/A</td><td rowspan="3">-</td></tr><tr><td>Decide mode-switch</td><td>30</td></tr><tr><td>Total</td><td>192</td></tr><tr><td rowspan="4">DYN</td><td rowspan="4">Set timer</td><td rowspan="4">895</td><td>Interrupt</td><td>162</td><td rowspan="4">Update DS<sup>L</sup></td><td rowspan="4">48</td></tr><tr><td>Use DS<sup>L</sup> to extend C<sub>τ<sub>i</sub></sub><sup>L</sup></td><td>90</td></tr><tr><td>Re-set timer</td><td>895</td></tr><tr><td>Total</td><td>1147</td></tr><tr><td rowspan="5">RRT</td><td rowspan="5">Initialize</td><td rowspan="5">42</td><td>RC<sub>τ<sub>i</sub></sub><sup>L</sup> and progress<sub>τ<sub>i</sub></sub></td><td>152</td><td rowspan="5">Update RD<sub>τ<sub>j</sub></sub></td><td rowspan="5">28 per τ<sub>j</sub></td></tr><tr><td>Monitor t</td><td>32</td></tr><tr><td>RR<sub>τ<sub>i</sub></sub><sup>L</sup> and DS<sup>L</sup></td><td>45</td></tr><tr><td>Decide mode-switch</td><td>45</td></tr><tr><td>Total</td><td>274</td></tr></tbody></table>
<figure><img src="image_7.png" /><figcaption>Fig. 7. Overhead comparison</figcaption></figure>

## 5.2 Performance evaluation

For the performance evaluation, we developed a simulation framework where we can tune different parameters of the task set in order to perform extensive evaluation experiments. We compare the decisions taken by RRT and DYN with the BL decisions, by computing how many times RRT and DYN decided to i) Not Switch (NS), same as BL, ii) Switch at the Same (SS) job as BL did, iii) Switch at another job, executed Later (SL) compared to BL, and iv) Switch Avoided (SA), compared to BL. Furthermore, we compare the percentage of the low criticality jobs (among all experiments) that i) did not start execution, and ii) finished.

**Benchmark characterisation:** To obtain realistic values for the simulation set-up in order to perform the above comparison, e.g., regarding the $C^L$, $C^H$, number of instrumentation points, partial WCETs, and actual execution time of jobs, we execute benchmarks with different characteristics on the TMS under different platform configurations. We used the Discrete Cosine Transformation (DCT), Mergesort (MERGE), and Fast Fourier Transformation (FFT) from StreamIT benchmarks [30], as they are typical kernels for real-time systems, exhibiting different characteristics in terms of memory accesses and execution paths. The source code of each benchmark has been modified in order to implement the instrumentation points, following the approach presented in Section 4.1, and executed on the TMS platform. The instrumentation points have been inserted uniformly in the benchmark codes. The number of instrumentation points per benchmark has been selected in order to have the total controller cost around 1% of the benchmark's WCET, in the worst-case, based on controller overhead measured on the TMS platform (Table 5). The measurements have been obtained using the processor's local timer during the benchmark execution.

Our first set of experiments obtains estimations of the $C^L$ and the partial WCETs between instrumentation points. To achieve that, the sources that variate the execution time have to be eliminated [15], by disabling data-caches, removing interferences (i.e., disabling all but one processor) and providing, as much as possible, values as input data that potentially enforce the worst-case path. We have followed the approach of multiple executions, where each benchmark has been executed 50 times, for each different input. We observed a deviation of ~ 1% between measurements among the executions of one input. We maintain the largest observed value among all inputs as the $C^L$ value. The $C^H$ is obtained by applying a common practise of inserting a margin of 30%.

Our second set of experiments characterizes the behavior of the actual execution time of the benchmarks under different software and hardware scenarios, and compute the observed timing variability. We studied two parameters that typically affect the execution time, i.e., the different
execution paths due to the inputs and the benchmark and the use of caches of the hardware platform. We tune each parameter independently in order to characterize its impact to the execution time. Table 6 shows the observed variability, computed by comparing the execution time of the best observed value and the worst observed value (which is given by $C^L$ in Table 6). On the one hand, we observe that the impact of caches in execution time is similar for all benchmarks, with 71.14% on average. On the other hand, we observe that the impact of different execution paths is benchmark depended; it is higher for applications with several execution paths, e.g., DCT, and, smaller for single-path applications, e.g., FFT. The obtained values depicted in Table 6 will be used to drive the simulation set-up with realistic values.

<table><caption>Table 6. Benchmark characterisation</caption><thead><tr><th colspan="3">Instr. points (Number)</th><th colspan="3">WCET (cycles)</th><th colspan="3">Cache variability</th></tr><tr><th>DCT</th><th>MERGE</th><th>FFT</th><th>DCT</th><th>MERGE</th><th>FFT</th><th>Path</th><th>DCT</th><th>MERGE</th><th>FFT</th></tr></thead><tbody><tr><td rowspan="2">25</td><td rowspan="2">17</td><td rowspan="2">10</td><td>C<sup>L</sup></td><td>981,120</td><td>669,026</td><td>275,891</td><td>Best-Path</td><td>73.83%</td><td>69.03%</td><td>69.40%</td></tr><tr><td>C<sup>H</sup></td><td>1,177,344</td><td>802,832</td><td>331,070</td><td>Worst-Path</td><td>76.57%</td><td>68.60%</td><td>69.38%</td></tr></tbody><thead><tr><th colspan="4">Path variability</th></tr><tr><th>Caches</th><th>DCT</th><th>MERGE</th><th>FFT</th></tr></thead><tbody><tr><td>Disabled</td><td>46.65%</td><td>12.84%</td><td>0.15%</td></tr><tr><td>Enabled</td><td>40.51%</td><td>14.69%</td><td>0.46%</td></tr></tbody></table>

**Experimental set-up:** The experimental simulation framework consists of i) a task-set generator, ii) an offline analysis, iii) an online scheduler, and iv) an online controller. The task-set generator constructs schedulable task-sets with realistic parameters based on the benchmark characterization, i.e., $C^L$, $C^H$, number of instrumentation points, and partial WCETs. The instrumentation points are generated in a uniform way, following the instrumentation of the benchmark codes. The offline analysis provides the worst-case delay in LO-mode, due to higher priority tasks. The online scheduler dynamically selects the ready task with the highest priority to be executed, taking into account the mode of execution. The online controller implements each approach to be evaluated. If the online controller decides mode-switch, it informs the online scheduler to drop low criticality tasks.

We perform experiments by generating task-set sizes from 2 tasks up to 40 tasks, consisting of an equal number of high and low criticality tasks. For each task set size, we perform a number of experiments. At each experiment, the task-set generator creates a different task-set using the measured information provided in Table 6. For each task, it selects the $C^L$ randomly in the range [275,891-981,120], the number of points randomly in the range [10,25], the period computed considering a system utilisation $U = 70\%$, with $U = \sum_{\tau_i \in T} \frac{C^L}{P_{\tau_i}}$, and a unique task priority given by Rate Monotonic, where the shorter the task period, the higher the job priority [2]. The timing overhead of the controller is included in the $C^L$. Note that, each task invokes a number of jobs. Among all experiments, the minimum, average and maximum number of simulated jobs is 22, 835, and 1,787.

For each experiment, the actual execution time of low criticality tasks is equal to their $C^L$. The actual execution time of high criticality tasks is tuned based on the benchmark characterisation. Two configurations are evaluated:

* Cache-related configuration, based on the trend of the observed timing variability regarding caches, i.e., similar variability for all benchmarks. Thus, the actual execution time of high criticality tasks is tuned in a similar way. Per task-set size, we perform 10 experiments. At each experiment,
the actual execution time among two points is varied almost exhaustively, from $C^L - 40\% \times C^L$ up to $C^L + 30\% \times C^L$, with a step of 5%, based on the observed variability.

* Path-related configuration, based on the trend of the observed timing variability regarding execution paths, i.e., the variability due to execution paths is benchmark-dependent. Thus, the actual execution time of each high criticality tasks is tuned independently. Per task-set size, we performed 1,000 experiments. At each experiment, the actual execution time among two points is randomly given in the range [$C^L - 50\% \times C^L, C^L + 50\% \times C^L$], based on the observed variability.

**Cache-related configuration:** Fig. 8 shows the mode-switch decisions and the number of non-started and finished low criticality tasks. We observe that the proposed approach (Fig. 8a) is able to avoid the mode-switch (SA) in a significant number of experiments, outperforming the DYN approach (Fig. 8b). When the actual execution time of all tasks is lower than the $C^L$ (avg. in 17.1% of the experiments), RRT and DYN have the same behavior with BL, since mode-switch does not occur. For the majority of the experiments, DYN, most of the time decides to switch mode at the same time as BL approach, i.e., on average, 78.46% of the experiments. On the contrary, RRT behaves as BL for only 17.78% of the experiments. Compared to BL, RRT is able to avoid mode-switch in 64.13% of the experiments. DYN avoids mode-switch for only 3.46% of the experiments. Hence, RRT managed to increase the mode-switch avoidance by a factor of ×18.54, compared to DYN. In the rest of the experiments, the approaches perform mode-switch later than BL; 1.99% for RRT and 0.98% for DYN. Regarding the execution of low criticality task, DYN behaves quite similarly to BL. DYN manages to start execution 2.67% more low criticality tasks, compared to the number of low criticality tasks that started execution with BL. Moreover, with DYN manages to finish, on average, 20.9% of the total number of low criticality jobs, compared to 17.5% for the BL. This provides a gain of a factor of ×1.19 more low criticality jobs that managed to finish their execution, compared to the number of low criticality jobs that finished in BL. On the contrary, due to the fine-grained slack exploitation, RRT provides significant improvements, as 82.60% of the total low criticality jobs managed to finish execution. This provides a gain factor of ×4.72, compared to the number of low criticality tasks that finished execution with BL.

**Path-related configuration:** As shows Fig. 9, on average, RRT switches as BL in 50.42% of the experiments, while DYN in 63.26%. For the remaining experiments, RRT avoids mode-switch (SA) in 36.07% of the experiments (Fig. 9a), while DYN in 11.03% (Fig. 9b). As a result, RRT increases mode-switch avoidance by ×3.27. Furthermore, we observe that DYN decides to switch mode later than BL in 25.7% of the experiments, while RRT in 13.5%. This difference comes from the fact in 12.20% of these experiments RRT totally avoided mode-switch, whereas DYN performed mode-switch, but later that BL. We also explore the impact of these decisions in the execution of the low criticality tasks. On average, for DYN, 13.50% low criticality jobs finished their execution, which is 12.28% more jobs than BL. However, RRT managed to finish 38.09% low criticality jobs, corresponding to 36.82% more jobs than BL.

# 6 RELATED WORK

We briefly describe the representative mixed-criticality approaches, relevant to our work, which are summarised in Table 7. A detailed survey is available in [12].

The majority of existing works use static decisions regarding when the mode switch occurs, typically given by the value of the low criticality WCET of high criticality tasks. Upon mode switch, low-criticality jobs are dropped, e.g., in time-triggered scheduling [10], EDF with Virtual Deadlines scheduling [3] and priority based on Adaptive Mixed Criticality [5] on uniprocessors, global [21] and partitioned [6] Earliest Deadline First (EDF)-based scheduling and global fixed-priority scheduling [25] on multiprocessors. However, as the mode switch decision is defined
<figure><img src="image_8.png" /><figcaption>Fig. 8. Cache-related configuration.</figcaption></figure>
<figure><img src="image_9.png" /><figcaption>Fig. 9. Path-related configuration.</figcaption></figure>
<table><caption>Table 7. Comparison with representative State-of-the-Art</caption><thead><tr><th rowspan="2">Ref.</th><th colspan="4">When to switch</th><th colspan="4">In HI-mode</th></tr><tr><th>Low crit. WCET</th><th>Static Slack</th><th>Dynamic Slack</th><th>Dynamic Delay</th><th>Drop low</th><th>Reduce priority</th><th>Timing budget</th><th>Extend Periods</th></tr></thead><tbody><tr><td>[3, 5, 10]<br>[6, 21, 25]</td><td>√</td><td></td><td></td><td></td><td>√</td><td></td><td></td><td></td></tr><tr><td>[1, 16, 22]<br>[13, 14, 27]</td><td>√</td><td></td><td></td><td></td><td>√</td><td></td><td></td><td></td></tr><tr><td>[17, 24]</td><td></td><td>√</td><td>√</td><td></td><td>√</td><td></td><td></td><td></td></tr><tr><td>[7]</td><td></td><td>√</td><td>√</td><td></td><td>√</td><td></td><td></td><td></td></tr><tr><td>[23]</td><td></td><td>√</td><td>√</td><td></td><td></td><td></td><td>√</td><td></td></tr><tr><td>[28]</td><td></td><td></td><td></td><td>√</td><td>√</td><td></td><td></td><td></td></tr><tr><td>[9]</td><td>√</td><td></td><td>√</td><td></td><td></td><td>√</td><td>√</td><td>√</td></tr><tr><td>Proposed</td><td></td><td></td><td>√</td><td></td><td>√</td><td></td><td></td><td></td></tr></tbody></table>

statically, while the low criticality tasks are dropped in HI-mode, the system performance is degraded. To increase the execution time of the low criticality tasks, existing works i) explore other strategies, than dropping low criticality tasks, in HI-mode, and ii) explore, statically or dynamically, ways to postpone the mode switch or switch back to LO-mode. In summary, first category approaches i) set the priority of low criticality tasks below the priority of any high criticality task, ii) reduce the execution time requirements of low criticality tasks in high criticality mode, and iii) extend the periods of low criticality tasks [9]. We will focus on the second category, where the proposed approach belongs to.

Static approaches determine the largest value, that could be added to a task's low criticality WCET, postponing the mode switch, such that the whole task set remains schedulable. Methods inspired by sensitivity analysis [8] compute offline the margins that low criticality tasks are allowed to overrun before being suspended, on uniprocessor systems [27]. Other approaches use zero-slack scheduling, where low-critical tasks are allowed to run until the zero-slack of higher-criticality jobs is finished. The zero-slack of a task is offline computed based on the low criticality and high criticality WCET and the interference from higher-priority and higher-criticality tasks [13, 14]. However, as those techniques exploit only static slacks, usually due to the system being under-loaded, they use the run-time information to further postpone the mode switch.

Dynamic approaches mainly exploit the slack, created during execution due to earlier-than-the- WCET execution of the tasks. The most straightforward way to use the dynamic slack is to enable switching back to LO-mode, after the execution of high criticality tasks [1, 16, 22]. The remaining approaches use the dynamic slack to postpone the mode switch. For instance, a single overrun budget is used for high and low criticality tasks for EDF scheduling. It is based on the feasible task-procrastination timelength, updated using the run-time information about the completion times of tasks [17]. In [24], idle slacks are inserted during scheduling for low criticality tasks, and an online approach explores the slack created due to early termination of tasks. Through the bailout protocol [7], high criticality tasks, that overrun their low criticality WCET, ask for funds, putting the system in bailout mode. Tasks, finished early, donate their slack and low criticality task, released in bailout mode, are abandoned, donating their low criticality WCET. When the bailout fund is zero, the system enters recovery mode. The adaptMC [23] exploits this dynamic slack through a control feedback mechanism that run-time updates the task budgets. Our work extends the state-of-the-art by exploring, not only the slack created due to the early termination of tasks, but also the slack
due to the current execution progress of active tasks, by safely computing, during execution, the
response time of the running job.

Few approaches exploit the dynamic slack based on the progress of a task, by computing the i) observed delay [28], and ii) remaining WCET [19, 20]. The first approach inserts a checkpoint to a high criticality task and profiles the average execution time up to that point. The actual time is compared to the profiled value to compute the observed delay. A schedulability analysis is applied, during execution, to check whether the system remains schedulable, in case the low criticality WCET of the task is extended by the observed delay [28]. Our approach is based on safe remaining WCET, instead of average values, without the need of applying a schedulability test or a response time analysis during execution. The second approaches insert several checkpoints in a high criticality task. At each checkpoint, it safely computes the remaining WCET, i.e., the WCET of the code, that remains to be executed, from the observation point until the end. The WCET is used to decide to postpone mode switch, considering interference from low criticality tasks executed in parallel on a multicore [19, 20]. However, this approach considers that each core runs only a single task non-preemptively and high and low criticality tasks are executed in different processors. Our work extends the approach of [19, 20] for multi-periodic high and low criticality tasks executed pre-emptively on the same processor.

7 CONCLUSION

This work proposes a safe and lightweight approach that at run-time exposes the dynamic slack, created as the execution of jobs progresses, and exploits it in order to postpone and avoid mode switch in mixed-criticality systems. The proposed approach operates upon the novel concepts of run-time computation of the worst case response time, removing the requirement for performing a schedulability test or a response time analysis, at run-time. We have shown formally that the proposed approach is safe. From the obtained results, our approach is able, on average, to avoid mode switch in 50.10% of the experiments, which allows to 60.34% low criticality tasks to finish execution.

REFERENCES

[1] James H. Anderson, Sanjoy K. Baruah, and Björn B. Brandenburg. 2009. Multicore Operating-System Support for Mixed Criticality. In *Int'l Workshop on Mixed Criticality Systems (WMC)*.

[2] Neil C Audsley. 1991. *Optimal priority assignment and feasibility of static priority tasks with arbitrary start times*. Citeseer.

[3] Sanjoy Baruah, Vincenzo Bonifaci, Gianlorenzo D'Angelo, Alberto Marchetti-Spaccamela, Suzanne van der Ster, and Leen Stougie. 2011. Mixed-Criticality Scheduling of Sporadic Task Systems. In *European Symposium on Algorithms (ESA)*, Vol. 6942. 555-566.

[4] S.K. Baruah, L. Haohan, and L. Stougie. 2010. Towards the Design of Certifiable Mixed-criticality Systems. In *Real-Time and Embedded Technology and Applications Symposium (RTAS)*. IEEE, USA, 13-22.

[5] S. K. Baruah, A. Burns, and R. I. Davis. 2011. Response-Time Analysis for Mixed Criticality Systems. In *Real-Time Systems Symposium (RTSS)*. 34-43.

[6] Sanjoy K. Baruah, Bipasa Chattopadhyay, Haohan Li, and Insik Shin. 2013. Mixed-criticality scheduling on multiprocessors. *Real-Time Systems* (2013), 1-36.

[7] I. Bate, A. Burns, and R. I. Davis. 2015. A Bailout Protocol for Mixed Criticality Systems. In *Euromicro Conference on Real-Time Systems (ECRTS)*. 259-268.

[8] E. Bini, M. Di Natale, and G. Buttazzo. 2006. Sensitivity analysis for fixed-priority real-time systems. In *Euromicro Conference on Real-Time Systems (ECRTS)*. 10 pp.-22.

[9] Alan Burns and B. Baruah. 2013. Towards A More Practical Model for Mixed Criticality Systems. In *Real-Time Systems Symposium (RTSS)*.

[10] Alan Burns and Sanjoy K. Baruah. 2011. Timing Faults and Mixed Criticality Systems. In *Dependable and Historic Computing (Lecture Notes in Computer Science, Vol. 6875)*, CliffB. Jones and JohnL. Lloyd (Eds.). Springer Berlin Heidelberg, 147-166.
[11] Alan Burns and Robert Davis. 2020. Mixed criticality systems-a review. *Department of Computer Science, University of York, Tech. Rep* (2020).

[12] Alan Burns and Robert I. Davis. 2018. A Survey of Research into Mixed Criticality Systems. *ACM Comput. Surv. (CSUR)* 50, 6 (2018), 82:1–82:37.

[13] D. d. Niz, K. Lakshmanan, and R. Rajkumar. 2009. On the Scheduling of Mixed-Criticality Real-Time Task Sets. In *Real-Time Systems Symposium (RTSS)*. 291–300.

[14] D. de Niz and L. T. X. Phan. 2014. Partitioned scheduling of multi-modal mixed-criticality real-time systems on multiprocessor platforms. In *Real-Time and Embedded Technology and Applications Symposium (RTAS)*. 111–122.

[15] Jean-François Deverge and Isabelle Puaut. 2007. Safe measurement-based WCET estimation. In *Int’l Workshop on Worst-Case Execution Time Analysis (WCET)*, Reinhard Wilhelm (Ed.), Vol. 1.

[16] Tom Fleming and Alan Burns. 2013. Extending Mixed Criticality Scheduling. In *Real-Time Systems Symposium (RTSS)*.

[17] Biao Hu, Kai Huang, Pengcheng Huang, Lothar Thiele, and Alois Knoll. 2016. On-the-fly fast overrun budgeting for mixed-criticality systems. In *Int’l Conf. Embedded Software (EMSOFT)*. 1–10.

[18] Zhe Jiang, Kecheng Yang, Nathan Fisher, N. Audsley, and Zheng Dong. 2020. Pythia-MCS: Enabling Quarter-Clairvoyance in I/O-Driven Mixed-Criticality Systems. In *RTSS*.

[19] Angeliki Kritikakou, Olivier Baldellon, Claire Pagetti, Christine Rochange, and Matthieu Roy. 2014. Run-time Control to Increase Task Parallelism in Mixed-Critical Systems. In *Euromicro Conference on Real-Time Systems (ECRTS)*.

[20] Angeliki Kritikakou, Christine Rochange, Madeleine Faugère, Claire Pagetti, Matthieu Roy, Sylvain Girbal, and Daniel Gracia Pérez. 2014. Distributed Run-time WCET Controller for Concurrent Critical Tasks in Mixed-critical Systems. In *Int’l Conf. Real Time and Networks Systems (RTNS)*. Article 139, 10 pages.

[21] Haohan Li and S. Baruah. 2012. Global Mixed-Criticality Scheduling on Multiprocessors. In *Euromicro Conference on Real-Time Systems (ECRTS)*. 166–175.

[22] Malcolm S. Mollison, Jeremy P. Erickson, James H. Anderson, Sanjoy K. Baruah, and John A. Scoredos. 2010. Mixed-Criticality Real-Time Scheduling for Multicore Systems. In *International Conference on Computer and Information Technology (CIT)*. 1864–1871.

[23] Alessandro Vittorio Papadopoulos, Enrico Bini, Sanjoy Baruah, and Alan Burns. 2018. AdaptMC: A Control-Theoretic Approach for Achieving Resilience in Mixed-Criticality Systems. In *Euromicro Conference on Real-Time Systems (ECRTS)*, Vol. 106. 14:1–14:22.

[24] T. Park and S. Kim. 2011. Dynamic scheduling algorithm and its schedulability analysis for certifiable dual-criticality systems. In *ACM Int’l Conf. Embedded Software (EMSOFT)*. 253–262.

[25] Risat M. Pathan. 2012. Schedulability Analysis of Mixed-Criticality Systems on Multiprocessors. In *Euromicro Conference on Real-Time Systems (ECRTS)*. 309–320.

[26] SAE. 2010. Aerospace Recommended Practices 4754a - Development of Civil Aircraft and Systems. SAE.

[27] F. Santy, L. George, P. Thierry, and J. Goossens. 2012. Relaxing Mixed-Criticality Scheduling Strictness for Task Sets Scheduled with FP. In *Euromicro Conference on Real-Time Systems (ECRTS)*. 155–165.

[28] Soham Sinha and Richard West. 2020. PAStime: Progress-aware Scheduling for Time-critical Computing. In *Euromicro Conference on Real-Time Systems (ECRTS)*.

[29] Texas Instruments. 2013. *TMS320C6678 Multicore Fixed and Floating-Point Digital Signal Processor*. Technical Report SPRS691D. TI.

[30] William Thies et al. 2010. An Empirical Characterization of Stream Programs and Its Implications for Language and Compiler Design. In *PACT*. 12.

[31] S. Vestal. 2007. Preemptive Scheduling of Multi-criticality Systems with Varying Degrees of Execution Time Assurance. In *Real-Time Systems Symposium (RTSS)*. 239–243.