# WIP : Feasibility analysis of real-time periodic multi-phase tasks on unrelated multiprocessor platforms

Thomas Gaspard, Antoine Bertout, Joël Goossens, Emmanuel Grolleau,
Pascal Richard

► To cite this version:

Thomas Gaspard, Antoine Bertout, Joël Goossens, Emmanuel Grolleau, Pascal Richard. WIP : Feasibility analysis of real-time periodic multi-phase tasks on unrelated multiprocessor platforms. OPERA, Dec 2023, Taipei, Taiwan. hal-04297879

HAL Id: hal-04297879

https://hal.science/hal-04297879v1

Submitted on 21 Nov 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# WIP : Feasibility analysis of real-time periodic multi-phase tasks on unrelated multiprocessor platforms

Thomas Gaspard*, Antoine Bertout†, Joël Goossens‡, Emmanuel Grolleau* and Pascal Richard†

*LIAS, ISAE-ENSMA, Université de Poitiers, Chasseneuil-Futuroscope, France, firstname.lastname@ensma.fr

†LIAS, Université de Poitiers, ISAE-ENSMA, Poitiers, France, firstname.lastname@univ-poitiers.fr

‡ Université libre de Bruxelles, Brussels, Belgium, firstname.lastname@ulb.be

***Abstract***—Modern processing architectures, such as System-on-Chip (SoC) feature heterogeneous processors categorized as unrelated platforms in the real-time scheduling theory. Real-time tasks can be decomposed into subtasks called phases, each with a different execution rate depending on the processing unit it is assigned to.

This preliminary work studies the feasibility of scheduling periodic real-time tasks with multiple phases on unrelated platforms. Initially, we apply an existing optimal analysis technique based on linear programming, designed for mono-phase tasks. This approach proves to be non-optimal in this context. Thus, we introduce a more fine-grained formulation and let formal and experimental validation for future work.

## I. INTRODUCTION

Heterogeneous processors have gained widespread use in mainstream computing platforms, particularly in System-on-Chip (SoC) designs found in personal mobile devices. These processors exhibit diverse architectures and incorporate specialized computing units such as GPU (Graphics Processing Unit), DSP (Digital signal processors), NPU (Neural Processing Unit), and others. As a result, applications can be decomposed into subtasks and executed on processors specifically suited to their characteristics, thereby optimizing performance. In certain scenarios, subtasks may be compiled for different architectures and executed conditionally based on the system context.

Emerging platforms, such as the Mediatek Helio X20® or ARM big.LITTLE®-equipped boards, consist of heterogeneous CPUs that share the same Instruction Set Architecture (ISA) and feature full cache coherence. In this configuration, task migration or preemption becomes even more feasible. These platforms typically comprise a cluster of fast but energy-consuming (big) cores and a cluster of slower but more energy-efficient (LITTLE) cores. The performance of such systems naturally relies on the hardware implementation of identical instructions.

In the realm of real-time literature, heterogeneous platforms are classified as unrelated, where tasks can be executed at different speeds or rates across different processors. In this paper, we adopt the multi-phase model to represent applications, whereby each subtask is executed within its dedicated phase. Consequently, each phase of the same task can be executed on different processors (migrations are allowed) and

at a different speed. We focus on the feasibility problem of optimally scheduling a set of multi-phase periodic real-time tasks on unrelated platforms. We first show that employing the seminal techniques for period (mono-phase) tasks is not optimal and propose a novel approach.

It has been shown that constructing a feasible schedule from a workload assignment can be done in polynomial time [1][2][3]. In this paper, we will not address the construction of the schedule itself, but rather, we will focus on the processing of the optimal workload assignment of multi-phase periodic tasks upon unrelated platforms.

The structure of this work-in-progress paper is as follows. In Section II we present the multi-phase periodic task model and define the unrelated platforms. Section III is dedicated to the state of the art, where we review the works on unrelated platforms and the similar model of tasks. In Section IV, we apply a well-known result to our model and highlight its sub-optimality in this context. Section V introduces a less constrained technique, and Section VI is dedicated to future works and conclusion.

## II. MODEL OF COMPUTATION AND ASSUMPTIONS

a) *Unrelated multiprocessors:* The hardware is modelled as a set of *m* unrelated processors $\Pi \doteq \{\pi_1, \dots, \pi_m\}$ (the symbol $\doteq$ means *is equal by definition to*). Each task $\tau_i$ is also characterised by its processor *affinities*, i.e., with the execution rates $r_i^j$ for the task $\tau_i$ upon processor $\pi_j$. When a job executes for a duration of $t$ at a rate $r$, the job progresses by $t \cdot r$.

b) *Periodic task:* The application is modelled as a set of *n* periodic *implicit-deadline* tasks $\Gamma \doteq \{\tau_i \mid i = 1, \dots, n\}$. Each task $\tau_i$ is characterised by two parameters $(C_i, T_i)$ where $C_i$ is the *worst-case execution time* on a *fictional processor*, and $T_i$ is the *release period*. Each task releases a *job* every period $T_i$. The first job is released at $t=0$ (i.e., we consider synchronous tasks), the $k^{th}$ at $t = k \times T_i$ and has to complete by $(k+1) \times T_i$ (tasks are said to have implicit deadlines). The utilisation of a task $\tau_i$ is $u_i \doteq \frac{C_i}{T_i}$.

c) *Phases and processor rates:* Each task is composed of *sequence of $\rho_i$ phases*: $(\tau_{i,0}, \dots, \tau_{i,\rho_i-1})$, and computation requirement $c_i^j$ for $j \in [0, \rho_i - 1]$, such as $\sum_{j=0}^{\rho_i-1} c_i^j = C_i$. The novelty of this model is to define processor rates at *phase* level. For each phase $\tau_{i,j}$, and for each processor
<figure><img src="image_2.png" /><figcaption>Fig. 1. A task with three phases visualised as an oriented graph</figcaption></figure>

<figure><img src="image_3.png" /><figcaption>Fig. 2. A task with two phases visualised as an oriented graph where the jobs are separated</figcaption></figure>

<table><caption>TABLE I
A MULTI-PHASE PERIODIC TASK SET</caption><thead><tr><th>τ<sub>i</sub></th><th>T<sub>i</sub></th><th>ρ<sub>i</sub></th><th>κ<sub>i</sub></th></tr></thead><tbody><tr><td>τ<sub>1</sub></td><td>15</td><td>3</td><td>5</td></tr><tr><td>τ<sub>2</sub></td><td>3</td><td>1</td><td>3</td></tr><tr><td>τ<sub>3</sub></td><td>2</td><td>2</td><td>1</td></tr></tbody></table>

$\pi_k$, $r_{i,j}^k$ denotes the execution rate of $\tau_{i,j}$ upon processor $\pi_k$. To ease the presentation of the problem, we consider that the WCET is uniformly distributed among the phases ($\forall \tau_i \in \Gamma, \forall j \in [0, \rho_i - 1], c_i^j \doteq \frac{C_i}{\rho_i}$). However, as shown in Section IV, introducing a WCET per phase in the equations to reflect real-world applications is straightforward.

d) Phases activation: More formally, the sequence of phases is defined as follows. Without loss of generality, we can assume that $\kappa_i \doteq \frac{T_i}{\rho_i}$ is an integer. $\kappa_i$ is the relative deadline of each phase of task $\tau_i$. The parameter $\kappa_i$ also determines the release dates of the phases. Relatively to the job release time, the phase $\tau_{i,j}$ is defined to be released at time $j \cdot \kappa_i$ and must be completed by time $(j+1) \cdot \kappa_i$. Consequently, for each task there is at most one active (released but not completed) phase.

A task can be visualised as an oriented graph. In Figure 1 is shown such a graph with a task $\tau_i$ made of three phases.

In the following, we will use the notation $\tau_{i,j}^k$ for the $j^{th}$ phase of the $k^{th}$ job of the task $\tau_i$. Such an example is given in Figure 2.

e) Timeline: At the system level, the sequence of phases forms a periodic pattern that we refer to as a timeline. Such a timeline is periodic, of period $H \doteq \text{lcm}\{T_i | i \in [1, n]\}$. An example of task set is given in Table I, and the corresponding timeline is drawn in Fig. 3. We emphasize that this visual representation differs from a schedule as no assumptions are made here regarding the order in which phases of different tasks will be executed and on which processors they will be executed.

f) Chunk: In this paper, a chunk will correspond to the 'granularity' of schedule, i.e., within a chunk, there will be no releases of phases. By definition the (largest) size of the chunk is $\kappa_{min} \doteq \text{gcd}\{\kappa_i | i \in [1, n]\}$.

We will divide the timeline into chunks of duration $\kappa_{min}$. We will thus characterise a chunk by the set of phases that must be scheduled within. We label the different chunks as follows: $t_0, t_1, t_2, \dots$. Hence, $t_a$ represents the time interval $[a \cdot \kappa_{min}, (a+1) \cdot \kappa_{min})$.

g) Preemptions and migrations: We assume that preemptions and migrations have zero cost. There is no restriction on the migration at the job or phase level, including inside a chunk.

As a timeline is periodic, it is sufficient to build a workload assignment on $[0, H)$ for the chunks $t_0, t_1, \dots, t_{\frac{H}{\kappa_{min}}} - 1$.

Our workload assignment problem will be formulated as a linear program with $x_{i,j}^a$ as variables. $x_{i,j}^a$ is the workload of the phase of task $\tau_i$ on $\pi_j$ during the chunk $t_a$, see details in sections IV and V.

### III. STATE OF THE ART

In this section, we provide a brief review of the state of the art on unrelated platforms and present related models that are formally and/or semantically different from our multi-phase model.

#### A. Optimal scheduling algorithms on unrelated Platforms

Optimal real-time scheduling algorithms for unrelated platforms all follow the same two-step methods. In the first step, the workload of tasks on processors is computed, either by solving a linear programming problem (LP) [1], [3] or by using an ad hoc algorithm [4]. In the second step, the (pattern) schedule is constructed offline [5], typically through bipartite matching, Birkhoff-Von Neumann decomposition [1], or by using an ad hoc algorithm [4], on a one-time unit and then rolled out into a concrete schedule within intervals delimited by successive absolute deadlines (deadline partitioning). The seminal work by Baruah [2] introduced this approach. For two-types multi-core unrelated processors (clusters), the work of Chwa et al. [4] propose tailored algorithms for the two-step. Bertout et al. [5] addressed the problem of n-types clustered platforms with the objective of reducing inter and intra-cluster migrations.

#### B. Related Model

a) Multi-Phase Multi-Thread (MPMT) [6]: The multi-phase model adopted in this work corresponds to the single-threaded version of the MPMT model. In the MPMT a task (referred to as a process in [6]) is divided in consecutive phases. Each phase consists of multiple threads, and each thread requires a dedicated processor for execution. Notice that the authors consider the preemptive scheduling of periodic MPMT tasks on identical multiprocessor platforms. Therefore, their results do not directly apply to the unrelated platform model considered in our research.

b) Multi-frame [7] (MF) task model: The multi-frame approach characterises a sporadic task with an implicit deadline and a cyclic pattern of executions, expressed by a vector of WCET. More precisely, each task job is executed with the WCET at the vector index corresponding to the job index modulo the vector size. Our multi-phase model is formally equivalent to the multi-frame model applied to periodic tasks,
<figure><img src="image_4.png" /><figcaption>Fig. 3. Timeline of the task set given in Table I</figcaption></figure>

as the execution of *l* jobs of an MF task with a strict period of *T*/*l* (with *l* frames) is equivalent to the execution of one job of a multi-phase task with a period of *T* and *l* phases. However, they are semantically different in the sense that we consider a single job as a task execution with different “parts”, with different processor rates (and computing requirements). For instance, one can imagine that the compiler decomposes the binary into different phases with different rates for CPUs, FPGAs, GPUs, etc. Nonetheless, to the best of our knowledge, there is no existing work on the execution of MF tasks on unrelated platforms.

c) *Graph-based models:* Similarly to an MF task, a multi-phase task can be represented using a directed graph [8] representation, where each phase is represented as a vertex and the edges symbolize the sequential execution between phases. Phases may be considered as multiple mono-phase tasks with equal periods linked by simple precedence constraints. Nevertheless, our model is more restrictive because a phase can not start as soon as the previous phase completes its execution but only at its set release time. Graph-based models also possess the expressiveness to represent conditional executions and parallel execution models of fork-join type. The constraint of executing each phase within its time window can be viewed as a horizontal and sequential version of the Gang model [9], but we do not consider parallelism in this work.

d) *Asynchronous task model:* Precedence constraints can be encoded by modifying offsets and deadlines [10] to analyze tasks as independent. As we set phase release times inside a task, our model could be viewed a special case of the periodic mono-phase model with asynchronous releases and implicit deadlines by transforming each phase into a task with an offset equal to the relative deadline of the previous phase. However, explicitly considering the offsets would not simplify the problem resolution.

e) *PREM and phased execution:* the PRedictable Execution Model (PREM) [11], [12] divides the execution of the runnables (executable entities) into three distinct and consecutive phases to avoid memory contention in a time-triggered system. Each task starts by executing a memory phase in which all the data and instructions needed by the task are read from main memory and stored in local private memory (e.g., cache or scratchpad). The subsequent computation phase can then perform the actual computation of the task using data and instructions that are readily available in the private memory, without any need to access the interconnect or shared main memory. Lastly, a last memory phase is performed at the end of each task to write back the updated data into the main memory. The phased execution of tasks is typically used in

conjunction with a scheduling algorithm that exploits the fact that access to the shared main memory and bus are only going to occur during the memory phases of the tasks. Therefore, the scheduler can avoid contention in the main memory by not overlapping memory phases in different cores (i.e., such parallelism is forbidden). The memory phases (read & write) are assumed to be non-preemptive, while the execution phases can be preemptive. Our model is different in that the read and write phases are non-preemptive. Additionally, it is not equivalent to consider memories as specific types of processors. Lastly, we do not aim to avoid parallelism between phases of different tasks (memory phases in the PREM model). On the contrary, it is encouraged to achieve optimal scheduling.

f) *Distributed models:* Sun and Liu [13] present a model in which tasks are decomposed into subtasks, similar to the way we decompose ours into phases. However, our approach differs in that the subtasks can only be executed on a single processor, whereas we consider that the phases can run on several and could migrate between them.

## IV. CHUNK BY CHUNK APPROACH

In the following, without loss of generality, we will assume that $\kappa_{min} = 1$ (by dividing, for all tasks, $T_i$ by $\kappa_{min}$ and multiplying all the rates by the same factor, we actually solve an equivalent problem where $\kappa_{min} = 1$).

Baruah [2] proposes an exact feasibility test for the scheduling of mono-phase tasks on unrelated multiprocessors. The feasibility problem is equivalent to solve a Linear Program (LP). A solution to the LP exists iff a feasible schedule exists. A first approach could be to apply the Baruah's method chunk by chunk. That is, considering *H* independent problems by evenly distributing the workload of each phase within each chunk. More formally, by solving independently the LP 1 for each $t \in [0, H - 1]$.

### LP 1.

$$ \sum_{j=1}^{m} x_{i,j}^{t} \times r_{i,j}^{\lambda_i(t)} = \frac{C_i}{\kappa_i \times \rho_i} \quad \forall i \in [1, n] \quad (1) $$

$$ \sum_{j=1}^{m} x_{i,j}^{t} \leq 1 \quad \forall i \in [1, n] \quad (2) $$

$$ \sum_{i=1}^{n} x_{i,j}^{t} \leq 1 \quad \forall j \in [1, m] \quad (3) $$

where $\lambda_i(t) \doteq \lfloor \frac{t \bmod T_i}{\kappa_i} \rfloor$ is the index of the current phase of task $\tau_i$ at time $t$, and $x_{i,j}^t \ge 0 \forall i \in [1, n], \forall j \in [1, m]$ is the fraction of the chunk $t$ assigned to $\tau_i$ on $\pi_j$. Equation (1)
ensures that the phases will meet their deadlines; while equations (2)–(3) ensure no intra-phase parallelism nor overloaded processor, respectively. As explained in Section II, the WCET of each task is here shared uniformly among the phases, but the LP can be readily extended by modifying $\frac{C_i}{\rho_i}$ to $c_i^{\lambda_i(t)}$ in (1). Notice that the same remark applies for LP 2 later in Section V.

Such a solution forces some kind of fairness: each phase progresses by the same amount during each chunk. This solution is not optimal as, sometimes, a phase's execution should be delayed to ensure schedulability of other phases. For instance, let's take a look at the task set given in Table II. $\tau_1$ is divided into two phases. The timeline of this task set is drawn in Fig. 4. The LP problem to solve for the first chunk is given by (4).

<table><caption>TABLE II</caption><thead><tr><th></th><th>τ<sub>1</sub></th><th>τ<sub>2</sub></th><th>τ<sub>3</sub></th></tr></thead><tbody><tr><th></th><th>ρ<sub>0</sub></th><th>ρ<sub>1</sub></th><th>ρ<sub>0</sub></th><th>ρ<sub>0</sub></th></tr><tr><th>T</th><td>2</td><td>2</td><td>2</td><td>2</td></tr><tr><th>C</th><td>2</td><td>1</td><td>1</td><td>1</td></tr><tr><th>π<sub>1</sub></th><td>1</td><td>0</td><td>1</td><td>1</td></tr><tr><th>π<sub>2</sub></th><td>0</td><td>1</td><td>0</td><td>0</td></tr></tbody></table>

AN EXAMPLE TASK SET NOT FEASIBLE WITH A CHUNK BY CHUNK APPROACH

<figure><img src="image_5.png" /><figcaption>Fig. 4. Timeline of the task set given in Table II</figcaption></figure>

$$ \left\{ \begin{array}{l} x_{1,1}^0 = 1 \\ x_{2,1}^0 = \frac{1}{2} \\ x_{3,1}^0 = \frac{1}{2} \\ x_{1,1}^0 + x_{1,2}^0 \le 1 \\ x_{2,1}^0 + x_{2,2}^0 \le 1 \\ x_{3,1}^0 + x_{3,2}^0 \le 1 \\ x_{1,1}^0 + x_{2,1}^0 + x_{3,1}^0 \le 1 \\ x_{2,2}^0 + x_{2,2}^0 + x_{3,2}^0 \le 1 \end{array} \right. \quad (4) $$

This LP has no solution: $x_{1,1}^0 + x_{2,1}^0 + x_{3,1}^0 = 2 > 1$. However, the task set is trivially feasible: $\tau_{1,0}$ can be executed on $\pi_1$ during the whole first chunk, and $\tau_{1,1}$ on $\pi_2$ for the second chunk, while $\tau_2$ and $\tau_3$ share the second chunk on $\pi_1$ during the second chunk to meet their deadlines.

In the following section, we will present a less constrained approach for the workload assignment of multi-phase task sets which does not fail on such examples.

## V. TOWARDS AN OPTIMAL MULTI-PHASE TECHNIQUE

A second approach is to consider the problem globally, relaxing the fairness constraint of the first approach. The

constraint now applies to the boundaries of each phase (of each job within the hyperperiod). Indeed, each phase must be fully executed at these instants. More formally, $\forall \tau_i \in \Gamma, \forall \rho \in [0, \rho_i]$, $\forall \alpha \in [0, \frac{H}{T_i} - 1]$:

$$ \alpha T_i + (\rho+1)\kappa_i - 1 \left( \sum_{j=1}^{m} x_{i,j}^t \times r_{i,j}^{\rho} \right) = \frac{C_i}{\rho_i} \quad (5) $$

This finer grained approach to the multi-phase problem is introduced in the LP 2.

## LP 2.

$$ \left\{ \begin{array}{l} \displaystyle \sum_{t=\alpha T_i + \rho \kappa_i}^{\alpha T_i + (\rho+1)\kappa_i - 1} \left( \sum_{j=1}^{m} x_{i,j}^t \times r_{i,j}^{\rho} \right) = \frac{C_i}{\rho_i} \\ \\ \displaystyle \sum_{j=1}^{m} x_{i,j}^t \le 1 \\ \\ \displaystyle \sum_{i=1}^{n} x_{i,j}^t \le 1 \end{array} \right. \quad \left\{ \begin{array}{l} \forall i \in [1, n] \\ \\ \forall \alpha \in [0, \frac{H}{T_i} - 1] \\ \\ \forall \rho \in [0, \rho_i - 1] \\ \\ \forall i \in [1, n] \\ \\ \forall t \in [0, H - 1] \\ \\ \forall j \in [1, m] \\ \\ \forall t \in [0, H - 1] \end{array} \right. $$

with $x_{i,j}^t \ge 0 \forall i \in [1, n], \forall j \in [1, m], \forall t \in [0, H - 1]$.

**Proposition 1.** LP 2, has a solution if and only if $\Gamma$ is feasible.

The proof is left for future work.

## VI. FUTURE WORKS AND CONCLUSION

### Formal guarantees

We still need to demonstrate that LP 2 produces an optimal solution, so that we can verify the feasibility of the multi-phase problem in an unrelated multiprocessor platform. It is quite clear that both approaches can be exponential, but this also needs to be demonstrated formally. The first approach is local and consists in replicating the solution of several LPs over the entire hyperperiod. The second approach is global and aims at computing the solution of one LP over the entire hyperperiod. It is also important to carefully quantify the number of variables and constraints generated as a function of the input size of the problem (distribution of the periods, number of tasks, number of phases per task, distribution of the WCET among phases, number of processors, etc.). We also plan to effectively release the constraint on the uniform distribution of periods and WCETs among phases.

### Experiments

We intend to generate synthetic systems to compare both approaches in practice, for example on the success ratio metric, assuming that LP 2 is optimal. However, this requires to generate tasks and rates with variability whose total load can be controlled, which is not trivial, especially with a rate per phase. We do not rule out the use of linear programming to generate feasible sets. Next, it will be necessary to evaluate the runtime of the two approaches, in order to verify not only their practicality, but also whether under certain conditions there is
any point in favouring the sub-optimal solution if the optimal
solution is not practicable.

Conclusion

In this work-in-progress, we have presented the problem of scheduling multi-phase periodic tasks in an unrelated multiprocessor platforms. A first approach using a state-of-the-art technique for mono-phase task proved to be sub-optimal. We are currently working on the assessment of the second approach optimality. Next, we will evaluate the runtime of the two approaches, in particular to verify under certain conditions (e.g. with non-harmonic periods) if it is reasonable to favour the sub-optimal solution if the optimal one is not practicable.

ACKNOWLEDGEMENTS

The authors would like to express their gratitude to Quentin Bontemps for the valuable ideas and insightful discussions pertaining to this work.

REFERENCES

[1] E. L. Lawler and J. Labetoulle, "On Preemptive Scheduling of Unrelated Parallel Processors by Linear Programming," en, *Journal of the ACM*, vol. 25, no. 4, pp. 612-619, Oct. 1978.

[2] S. Baruah, “Feasibility Analysis of Preemptive Real-Time Systems upon Heterogeneous Multiprocessor Platforms,” en, in *25th IEEE International Real-Time Systems Symposium*, Lisbon, Portugal: IEEE, 2004, pp. 37–46, ISBN: 978-0-7695-2247-0. DOI: 10.1109/REAL.2004.20. [Online]. Available: http://ieeexplore.ieee.org/document/1381293/.

[3] A. Bertout, J. Goossens, E. Grolleau, and X. Poczekajlo, “Workload assignment for global real-time scheduling on unrelated multicore platforms,” en, in *Proceedings of the 28th International Conference on Real-Time Networks and Systems*, Paris France: ACM, Jun. 2020, pp. 139–148.

[4] H. S. Chwa, J. Seo, J. Lee, and I. Shin, "Optimal real-time scheduling on two-type heterogeneous multicore platforms," in *Real-Time Systems Symposium*, IEEE, 2015, pp. 119–129.

[5] A. Bertout, J. Goossens, E. Grolleau, and X. Poczekajlo, “Template schedule construction for global real-time scheduling on unrelated multiprocessor platforms,” en, in *2020 Design, Automation & Test in Europe Conference & Exhibition (DATE)*, Grenoble, France: IEEE, Mar. 2020, pp. 216–221.

[6] P. Courbin, I. Lupu, and J. Goossens, "Scheduling of hard real-time multi-phase multi-thread (MPMT) periodic tasks," *Real-time systems*, vol. 49, pp. 239–266, 2013.

[7] A. K. Mok and D. Chen, "A Multiframe Model for Real-Time Tasks," en, *IEEE Transactions on Software Engineering*, vol. 23, no. 10, 1997.

[8] M. Stigge, P. Ekberg, N. Guan, and W. Yi, "The digraph real-time task model," in *2011 17th IEEE real-time and embedded technology and applications symposium*, IEEE, 2011, pp. 71–80.

[9] J. Goossens and P. Richard, "Optimal Scheduling of Periodic Gang Tasks," *Leibniz transactions on embedded systems*, vol. 3, no. 1, pp. 04–1, 2016.

[10] T. Bouchentouf, "Dynamic scheduling of real-time tasks under precedence constraints," *Real-Time Systems*, vol. 2, no. 3, pp. 181–194, 1990.

[11] R. Pellizzoni, E. Betti, S. Bak, et al., "A predictable execution model for cots-based embedded systems," in *2011 17th IEEE Real-Time and Embedded Technology and Applications Symposium*, IEEE, 2011, pp. 269–279.

[12] A. Alhammad and R. Pellizzoni, "Schedulability analysis of global memory-predictable scheduling," in *Proceedings of the 14th International Conference on Embedded Software*, 2014, pp. 1–10.

[13] J. Sun and J. Liu, "Synchronization protocols in distributed real-time systems," in *Proceedings of 16th International Conference on Distributed Computing Systems*, IEEE Comput. Soc. Press. DOI: 10.1109/icdc s.1996.507899. [Online]. Available: https://doi.org/10.1109%2Ficdcs.1996.507899.