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

HAL
open science

# Hierarchical Multicore-Scheduling for Virtualization of Dependent Real-Time Systems

Jan Jatzkowski, Marcio Kreutz, Achim Rettberg

► To cite this version:

Jan Jatzkowski, Marcio Kreutz, Achim Rettberg. Hierarchical Multicore-Scheduling for Virtualization of Dependent Real-Time Systems. 5th International Embedded Systems Symposium (IESS), Nov 2015, Foz do Iguaçu, Brazil. pp.103-115, 10.1007/978-3-319-90023-0_9. hal-01854163

HAL Id: hal-01854163

https://inria.hal.science/hal-01854163

Submitted on 6 Aug 2018

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_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Hierarchical Multicore-Scheduling for
Virtualization of Dependent Real-Time Systems

Jan Jatzkowski¹, Marcio Kreutz², and Achim Rettberg³

¹ C-LAB, University of Paderborn, 33102 Paderborn, Germany,
[jan.jatzkowski@c-lab.de](mailto:jan.jatzkowski@c-lab.de)

² UFRN - Department of Informatics and Applied Mathematics, Natal, Brazil
[kreutz@dimap.ufrn.br](mailto:kreutz@dimap.ufrn.br)

³ Carl von Ossietzky University Oldenburg, 26129 Oldenburg, Germany,
[achim.rettberg@iess.org](mailto:achim.rettberg@iess.org)

**Abstract.** Hypervisor-based virtualization is a promising technology to concurrently run various embedded real-time applications on a single multicore hardware. It provides spatial as well as temporal separation of different applications allocated to one hardware platform. In this paper, we propose a concept for hierarchical scheduling of dependent real-time software on multicore systems using hypervisor-based virualization. For this purpose, we decompose offline schedules of singlecore systems based on their release times, deadlines, and precedence constraints. Resulting schedule fragments are allocated to time partitions such that task deadlines as well as precedence constraints are met while local scheduling order of tasks is preserved. This concept, e.g., enables consolidation of various dependent singlecore applications on a multicore platform using full virtualization. Finally, we demonstrate functionality of our concept by an automotive use case from literature.

**Keywords:** Embedded Systems, Dependent Real-time Systems, Real-time Virtualization, Multicore Scheduling, Hierarchical Scheduling

## 1 Introduction

Nowadays, there is a raising interest in multicore technology for embedded real-time systems. Using multicore hardware promises not only more computational power but also reduced system size, weight, and power consumptions. However, many embedded applications require sequential interaction between different components. Increasing system performance is not reached by parallelization of dedicated software but rather by running various applications on one multicore platform concurrently [12]. Virtualization provides means to separate various applications. Multicore architectures and virtualization are therefore known as symbiotic technologies [9].

### 1.1 Hypervisor-based Virtualization

In this paper we focus on type-1 hypervisor-based virtualization, i.e. an additional software layer – the hypervisor – is placed between hardware and oper-
ating system (OS) respectively application software. As type-1 hypervisor run
bare-metal, they must provide, e.g., device drivers either by their own (mono-
lithic) or by means of some special guest system (console-guest). Hypervisor
provide virtual machines (VM) that represent duplicates of the real hardware.
These VMs allow to run various systems spatial and temporal separated on a
single hardware platform. Literature distinguishes full and para-virtualization
[9]. While guest systems running at full virtualization are not aware of the hy-
pervisor, para-virtualized systems are adapted to run in VMs. Consequently,
para-virtualization allows information exchange between guest system and hy-
pervisor, but full virtualization does not.

1.2 Problem Statement

Temporal isolation is an important property of hypervisor-based virtualization for embedded real-time systems. Current real-time hypervisor ensure temporal isolation of various VMs by some cyclic scheduling on hypervisor-level (cf. Sect. 2.2). These approaches provide each VM a guaranteed share of processing time during a predefined period, but dependencies between VMs remain an open issue.

Dependencies between tasks hosted by the same VM must be solved by its
local scheduler. But dependencies between VMs must be solved by hypervisor
scheduler. Using para-virtualization, local schedulers could notify the hypervisor
when tasks are finished. This may enable solutions based on servers to schedule
VMs with precedence constraints. In contrast, full virtualization implies that
local and hypervisor scheduler cannot actively exchange information. Hence, a-
priori knowledge of local schedules and VM-dependencies are required to get an
appropriate global scheduling.

1.3 Contribution

In this paper, we focus on hierarchical real-time scheduling of dependent VMs to
enable full virtualization of singlecore systems deployed to multicore hardware.
Here, dependencies are given by precedence constraints. The challenge is to share
execution time of *p* > 1 cores to *m* > *p* VMs such that deadlines as well as prece-
dence constraints are met. Each VM encapsulates a periodic real-time system
driven by its separate local singlecore schedule. Time sharing shall be realized by
a fixed cyclic scheduling that guarantees holding task deadlines and precedence
constraints. We consider task sets with acyclic dependencies, because cyclic task
dependencies imply non-deterministic behavior. Nevertheless, resulting VM de-
pendency graph may contain cycles. To meet deadlines as well as precedence
constraints of the overall system, hypervisor scheduler has to preempt execution
of VMs. For this purpose, first we decompose local schedules and then allocate
time partitions of various length to those parts of VM schedules. The result of
our approach is an offline multicore schedule for VMs that provides not only
sufficient execution time for each VM but also considers precedence constraints.
# 2 Related Work

In this paper, we address hierarchical scheduling of periodic tasks with precedence constraints on a multicore platform. We therefore divide related work into approaches related to multicore scheduling and hierarchical scheduling.

## 2.1 Multicore Scheduling

Multicore scheduling approaches are classified as partitioned or global [1]. Davis and Burns [5] state that i) most published research addresses independent tasks and ii) main advantage of partitioned multicore scheduling is reuse of results from singlecore scheduling theory after allocation of tasks to cores has been achieved. Considering periodic task sets with precedence constraints, partitioned scheduling allows to apply, e.g., adapted Earliest Deadline First (EDF*) presented by Chetto et al. [2] or Deadline Monotonic (DM) based scheduling proposed by Forget et al. [6]. Both approaches adapt deadlines to solve dependencies between tasks allocated to a singlecore and thus enable deadline-based scheduling as for independent task sets. But dependencies between tasks allocated to different cores are not considered. For global multicore scheduling, e.g., some scheduling policies from singlecore scheduling were adapted. For independent tasks, global EDF schedules *p* tasks with earliest absolute deadline at each time, where *p* is number of cores. Lee [11] extended global EDF to Earliest Deadline Zero Laxity (EDZL) that was proven to dominate global EDF [1]. Cho et al. [3] presented Largest Local Remaining Execution time First (LLREF). It is an optimal offline real-time scheduling approach for independent periodic tasks with implicit deadlines (*d* = *T*) and it performs non-work-conserving scheduling, i.e. cores can be idle even in case of ready tasks. Rönngren and Shirazi [15] proposed static scheduling of periodic tasks with precedence constraints for multiprocessor systems connected by a time division multiple access (TDMA) bus network. They adapt task deadlines – similar to [2], [6] – and apply a heuristic that schedules tasks w.r.t. earliest starting time, laxity, etc. In contrast to these approaches, our work aims at global offline scheduling that does not adapt local schedules, i.e. task parameters as well as local execution order keep untouched.

## 2.2 Hierarchical Scheduling

Most approaches for hierarchical scheduling at virtualization focus on independent sub-systems, while our work allows dependencies between those systems. In [7], Grösbrink and Almeida present hierarchical scheduling for hypervisor-based real-time virtualization of mixed-criticality systems. They address independent periodic VMs and apply partitioned hierarchical scheduling, i.e. VMs are allocated as periodic servers to cores and each core schedules its servers according to Rate Monotonic (RM). Masmano et al. [13] present the monolithic hypervisor XtratuM that provides para-virtualization. It schedules VMs – called partitions – globally by a static cyclic schedule and locally by a preemptive fixed priority-based policy [4]. Xi et al. [16] present the console-guest hypervisor RT-Xen. It
enables scheduling VMs as periodic or deferrable servers by EDF or DM priority schemes. Masrur et al. [14] proposed the priority-based scheduling plus simple EDF (PSEDF) to apply XEN hypervisor for mixed-criticality systems in automotive domain. But in contrast to our work, none of these approaches allows precedence constraints between VMs.

## 3 System Model

This paper focuses on hierarchical scheduling of periodic dependent real-time systems on a multicore platform. Usually, periodic embedded real-time systems get input from some sensors and compute output to control some acutators. But resources are limited to get input respectively set output via direct I/O access or network interfaces. To take this into account, we consider a periodic task model that allows asynchronous release of tasks:

$$ \Gamma = \{ \tau_i = (C_i, T_i, D_i, O_i) \mid 1 \le i \le n \}. \qquad (1) $$

Each task $\tau_i \in \Gamma$ is characterized by its worst case execution time (WCET) $C_i$, period $T_i$, constrained deadline $D_i \le T_i$, and offset $O_i$. By means of constrained deadlines and offsets, we are able to cover systems where the multicore platform is connected to a time-triggered network. We denote $j^{th}$ instance of task $\tau_i$ by $\tau_{ij}$ and its absolute deadline by $d_{ij}$. Task dependencies are given by precedence constraints $\tau_i \prec \tau_j$ meaning that $\tau_i$ must finish before $\tau_j$ can start execution. This corresponds to implicit communication between tasks, i.e. tasks require input just when they start and provide output when finished. To keep software behavior deterministic, we assume acyclic task graphs. Consequently, task dependencies can be described by directed acyclic graphs (DAG). We define the set of source respectively sink nodes as

$$ source = \{ \tau_i \in \Gamma \mid \exists \tau_j \in \Gamma : \tau_j \prec \tau_i \}, \qquad (2) $$

$$ sink = \{ \tau_i \in \Gamma \mid \exists \tau_j \in \Gamma : \tau_i \prec \tau_j \}. \qquad (3) $$

While tasks $\tau_i \in source$ make progress as soon as they are scheduled, tasks with predecessors ($\tau \in \Gamma \setminus source$) can only progress when required input has been delivered. Using hypervisor-based virtualization, task set $\Gamma$ is mapped to a set of virtual machines (VM)

$$ \mathcal{Y} = \{ v_k = (\gamma_k, \sigma_k) \mid 1 \le j \le m \} \qquad (4) $$

where VM $v_k$ is given by a task set $\gamma_k \subset \Gamma$ and a scheduling $\sigma_k$. In general, $\sigma_k$ can be an online or offline scheduling. In this paper, however, we assume offline singlecore scheduler running within VMs, i.e. $\sigma_k$ represents a fix order how tasks $\tau_i \in \gamma_k$ are scheduled. We denote worst case start time of task instance $\tau_{ij}$ scheduled by $\sigma_k$ with $\sigma_k^s(\tau_{ij})$ and its worst case finishing time with $\sigma_k^f(\tau_{ij})$.

The hypervisor scheduler is a fix cyclic schedule, i.e. VMs are scheduled by means of time partitions to keep temporal isolation. Each time partition
represents a time interval $I_h = [a_h, a_h + l_h]$ defined by its start time $a_h$ and length (duration) $l_h$. A VM $v_k$ mapped to a time partition $I_h$ will be scheduled at time $a_h$ for $l_h$ time units. During this time, VM $v_k$ can progress according to its schedule $\sigma_k$. The hypervisor schedule finally provides for each core a set of time partitions where each partition $I_h$ is associated to a dedicated VM $v_k$. We note this association by $I_h^{v_k}$.

# 4 Hierarchical Scheduling with Precedence Constraints

Hierarchical scheduling comprises scheduling of schedules and thus introduces different levels of scheduling. We consider hierarchical scheduling for hypervisor-based virtualization that implies two levels: Global scheduling of VMs by hypervisor and local scheduling of tasks within each VM. We restrict local schedulers to offline singlecore schedules, i.e. execution order of tasks is fix within each VM. This restriction simplifies handling a-priori knowledge of local schedules that we require to cover full virtualization.

The main idea of our approach is to combine knowledge of local schedulers’ task execution order with a-priori knowledge of tasks’ WCETs and dependencies to compute worst case time partitions (WCTP) for VMs. That is, we calculate worst case VM execution time required to guarantee that a dedicated task $\tau$ has finished (cf. Sect. 4.2). In Section 4.3, we schedule these time partitions, which represent activation slots of the corresponding VMs, on a multicore system. In case of success, assigning execution time to VMs according to the resulting schedule ensures that task dependencies as well as tasks’ deadlines are met.

## 4.1 Necessary Condition for Schedulability

To our best knowledge, literature provides no schedulability test that is necessary as well as sufficient for periodic tasks with precedence constraints on multicore systems. For multicore scheduling, there are also no approaches known that convert precedence constraints to real-time constraints – as proposed by Chetto et al. [2] for singlecore scheduling. This makes transferring results of multicore scheduling theory from independent to dependent task sets challenging. However, some results from multicore scheduling theory of independent tasks can be transferred to task sets with precedence constraints at least as necessary conditions. For instance, a trivial fact from scheduling theory is that a task set $\Gamma$ with computation demand higher than computation supply provided by some hardware with $p$ cores is not schedulable. Consequently, for multicore hardware with $p$ identical cores, utilization of feasible task set $\Gamma$ cannot be higher than available number of cores, i.e.

$$ \sum_{i=1}^{n} \frac{C_i}{T_i} \le p \qquad (5) $$

Although Eq. 5 is just a necessary condition, it allows to exclude at least some non-feasible task sets.
## 4.2 Decomposition of Local Schedules

Here, we consider local schedules that result from offline singlecore scheduling. Precedence constraints of tasks which are mapped to the same VM are solved by the corresponding local scheduler:

$$ \forall \tau_i, \tau_j \in v_k : \tau_i < \tau_j \implies \sigma_k^f(\tau_{il}) \le \sigma_k^s(\tau_{jl}) \quad \forall l \in \mathbb{N} \quad (6) $$

Hence, two challenges remain to be solved by hypervisor during VM scheduling: it has to schedule VMs such that (i) deadlines of tasks running within VMs are met and (ii) dependencies between tasks hosted by different VMs are taken into account. For this purpose, we decompose local schedules of VMs based on

1. deadlines of tasks that are sink nodes of dependency graphs ($\tau \in sink$)

2. release times of tasks that are source nodes of dependency graphs ($\tau \in source$)

3. dependencies between tasks that are hosted by different VMs

A first step towards enabling hypervisor to keep deadlines of tasks is done by splitting local schedules at worst case finishing time of sink nodes $\tau \in sink$. This eases handling of different periods within task set $\Gamma$. Since execution order of tasks is static within a local schedule $\sigma$, fulfilling an absolute deadline $d$ requires to run each local schedule until all task instances with absolute deadline $d$ are finished. Therefore, we split local schedule $\sigma$ at worst case finishing time of a sink node that is scheduled by $\sigma$ last amongst all other sink nodes of equal absolute deadline:

$$ \max \{\sigma^f(\tau_{ij}) | \tau_i \in sink, d_{ij}\} \quad j \in \mathbb{N} \quad (7) $$

Note, that each resulting fragment of a local schedule is associated with the earliest absolute deadline $d$ of all its tasks.

Hypervisor must also consider release time of task instances because VMs with offline schedules cannot progress as long as the currently scheduled task is not ready. To avoid that hypervisor schedules VMs that cannot progress because of unreleased tasks, we apply another decomposition step onto local schedules based on release times. We split local schedule $\sigma$ at the beginning of a source node that is scheduled first amongst all other source nodes of equal release time by $\sigma$:

$$ \min \{\sigma^s(\tau_{ij}) | \tau_i \in source, r_{ij}\} \quad j \in \mathbb{N} \quad (8) $$

Our last decomposition step is based on precedence constraints of tasks hosted by different VMs. As tasks with precedence constraints are just released when all predecessors have finished execution, we split local schedules based on inter-VM dependencies as follows: if a task $\tau$ allocated to VM $v_k$ has predecessors hosted by another VM $v_l$, $l \neq k$, we just split schedule $\sigma_k$ at beginning of $\tau$.

The result of the described decomposition is a totally ordered set $\Phi_k$ of scheduling fragments $\phi_h$ for each VM $v_k$. The order within $\Phi_k$ is such that composing all scheduling fragments $\phi_h \in \Phi_k$ w.r.t. this order results in the original local singlecore schedule $\sigma_k$. Finally, we compute worst case time partitions
(WCTP) based on these scheduling fragments and WCETs. For each local schedule fragment $\phi_h$, we sum up WCET of task instances covered by this fragment and define a time partition $I_h$ of this length. As this time partition is associated with the VM that hosts these task instances, we note:

$$I_h^{v_k} = \sum_{\tau_{ij} \in \phi_h} C_i \quad \forall \phi_h \in \Phi_k. \qquad (9)$$

## 4.3 Multicore Scheduling of Time Partitions

Our approach for hierarchical multicore scheduling is based on time partitions $I_h$ that were introduced in Sect. 3. While length of time partitions is set according to the WCTP resulting from decomposition of local schedules (cf. Eq. 9), starting time $a_h$ of time partitions as well as a core must be determined by hypervisor scheduler. So, the challenge addressed by our multicore scheduling approach is to allocate time partitions $I_h^{v_k}$ to cores $C_j$ and set their starting time $a_h^{v_k}$ such that all precedence constraints are met and tasks finish before their deadlines even in worst case.

We have to make scheduling decisions each time that a scheduling fragment is released or finished. As we decomposed local schedules based on precedence constraints, finishing one scheduling fragment usually implies that one or more other scheduling fragments were released during this execution. Therefore, we also make scheduling decisions when worst case finishing of a task $\tau_i \in \gamma_l$ with successor task $\tau_j$ hosted by another VM is passed. However, we just need to consider worst case finishing of the task $\tau_i \in \gamma_l$ that is scheduled by $v_l$ last amongst all other predecessors of $\tau$. Keeping order of local schedules guarantees that all other predecessors hosted by VM $v_l$ are then finished, too.

As multicore decisions are not only based on deadlines but have to consider dependencies as well, we define two sets of scheduling fragments that are updated at each scheduling decision:

$$\mathcal{R} \subset \bigcup_{k=1}^{m} \Phi_k, \quad \mathcal{N} \subset \bigcup_{k=1}^{m} \Phi_k \qquad (10)$$

$\mathcal{R}$ covers those scheduling fragments $\phi_h^{VM_k}$ that are ready, i.e. predecessors required to execute $\phi_h^{VM_k}$ are finished and $\phi_h^{VM_k}$ is due according to local schedule $\sigma_k$. In fact, $\mathcal{R}$ is similar to a ready queue known from common task scheduling. Analogous, $\mathcal{N}$ covers those scheduling fragments $\phi_h^{VM_k}$ that are next to become ready w.r.t. order of local schedule. Both, $\mathcal{R}$ and $\mathcal{N}$, contain at most one scheduling fragment $\phi_h^{v_k}$ of a VM $v_k$. Scheduling decisions are based on the following rules with decreasing priority:

1. Schedule the fragment $\phi_h \in \mathcal{R}$ with earliest deadline (EDF)

Note: Here, we use deadlines associated to scheduling fragments during first decomposition step (cf. 4.2)

2. Schedule the fragment that has most successor fragments $\phi \in \mathcal{N}$

While first scheduling rule aims at keeping deadlines, second rule addresses dependencies between different VMs.
<figure><img src="image_3.png" /><figcaption>**Fig. 1.** Three application examples from automotive domain [8]: electric power steering (EPS), adaptive cruise control (ACC), and traction control (TC).</figcaption></figure>

## 5 Application Example

We will use an application example to demonstrate how our approach presented in Sect. 4 works. Based on the problem definition given in Sect. 1.2, we apply our approach to a minimal system that consists of $p = 2$ cores and $m = 3$ VMs. The task set $\Gamma$ deployed to VMs is taken from Kandasamy et al. [8]. It covers three applications from automotive domain: Adaptive cruise control (ACC), traction control (TC), and electric power steering (EPS). Figure 1 shows the corresponding direct acyclic task dependency graphs. In Table 1, we provide original task parameters of these applications given in [8]. In addition, we adapted WCETs of tasks by some reduction. This represents a scenario where singlecore applications are consolidated on a multicore hardware with increased computational power related to original singlecore hardware.

<table><caption>**Table 1.** Task parameters (original WCET $C_i^O$, adapted WCET $C_i$, period $T_i$, and relative deadline $D_i$) of example applications shown in Fig. 1, cf. [8].</caption><thead><tr><th></th><th colspan="9">EPS System</th><th colspan="9">ACC System</th></tr><tr><th>Task τ<sub>i</sub></th><th>τ<sub>1</sub></th><th>τ<sub>2</sub></th><th>τ<sub>3</sub></th><th>τ<sub>4</sub></th><th>τ<sub>5</sub></th><th>τ<sub>6</sub></th><th>τ<sub>7</sub></th><th>τ<sub>8</sub></th><th>τ<sub>9</sub></th><th>τ<sub>10</sub></th><th>τ<sub>11</sub></th><th>τ<sub>12</sub></th><th>τ<sub>13</sub></th><th>τ<sub>14</sub></th></tr></thead><tbody><tr><th>C<sub>i</sub><sup>O</sup></th><td>150</td><td>175</td><td>300</td><td>250</td><td>150</td><td>100</td><td>300</td><td>150</td><td>175</td><td>300</td><td>250</td><td>200</td><td>150</td><td>200</td></tr><tr><th>C<sub>i</sub></th><td>75</td><td>90</td><td>150</td><td>125</td><td>75</td><td>50</td><td>150</td><td>75</td><td>90</td><td>150</td><td>125</td><td>100</td><td>75</td><td>100</td></tr><tr><th>T<sub>i</sub> = D<sub>i</sub></th><td>1500</td><td>1500</td><td>1500</td><td>1500</td><td>1500</td><td>1500</td><td>3000</td><td>3000</td><td>3000</td><td>3000</td><td>3000</td><td>3000</td><td>3000</td><td>3000</td></tr><tr><th></th><th colspan="9">TC System</th><th colspan="9"></th></tr><tr><th>Task τ<sub>i</sub></th><th>τ<sub>15</sub></th><th>τ<sub>16</sub></th><th>τ<sub>17</sub></th><th>τ<sub>18</sub></th><th>τ<sub>19</sub></th><th>τ<sub>20</sub></th><th>τ<sub>21</sub></th><th>τ<sub>22</sub></th><th>τ<sub>23</sub></th><th>τ<sub>24</sub></th><th>τ<sub>25</sub></th><th>τ<sub>26</sub></th><th>τ<sub>27</sub></th><th>τ<sub>28</sub></th></tr><tr><th>C<sub>i</sub><sup>O</sup></th><td>200</td><td>200</td><td>200</td><td>200</td><td>150</td><td>300</td><td>175</td><td>400</td><td>150</td><td>200</td><td>200</td><td>200</td><td>200</td><td>200</td></tr><tr><th>C<sub>i</sub></th><td>100</td><td>100</td><td>100</td><td>100</td><td>75</td><td>150</td><td>90</td><td>200</td><td>75</td><td>100</td><td>100</td><td>100</td><td>100</td><td>100</td></tr><tr><th>T<sub>i</sub> = D<sub>i</sub></th><td>3000</td><td>3000</td><td>3000</td><td>3000</td><td>3000</td><td>3000</td><td>3000</td><td>3000</td><td>3000</td><td>3000</td><td>3000</td><td>3000</td><td>3000</td><td>3000</td></tr></tbody></table>
<figure><img src="image_4.png" /><figcaption>**Fig. 2.** Local schedules resulting from deployment of example applications to three separate singlecore schedules $\sigma_i$, $1 \le i \le 3$.</figcaption></figure>

Task set $\Gamma$ is deployed to VMs according to an approach presented by Klobedanz et al.([10], “Algorithm 1: Initial Mapping”). This deployment originally addresses singlecore ECU-networks and thus fits to the indicated scenario of consolidating singlecore systems on a multicore platform. Figure 2 shows the resulting local offline schedules based on original WCETs. These local schedules define execution order of tasks within VMs.

## 5.1 Decomposition of Local Schedules

Now, we use schedule $\sigma_2$ to demonstrate decomposition of local schedules. VM $v_2$ hosts tasks of two example applications: EPS and TC. Tasks of EPS have deadline $D = 1500$ while deadline of TC-tasks is $D = 3000$. Our first decomposition step – splitting based on deadlines – therefore splits schedule $\sigma_2$ after finishing of $\tau_{6,1}$ and associates first fragment with absolute deadline $d = 1500$ and second fragment with $d = 3000$.

Next decomposition step – splitting based on release times – is driven by second release of EPS system at host time $t = 1500$. According to our description in Sect. 4.2, we split $\sigma_2$ before beginning of $\tau_{2,2}$. Thus, second fragment resulting from first step is splitted again. Note, that both fragments resulting from this step keep associated with absolute deadline $d = 3000$.

Last decomposition step – splitting based on precedence constraints – requires to consider dependencies to other VMs. In particular, we split $\sigma_2$ at the beginning of tasks that require input from other VMs. In case of $\sigma_2$, this results in splits at the beginning of $\tau_{4,1}$, $\tau_{20,1}$, and $\tau_{22,1}$.

Applying these decomposition steps to the other local schedules of our application scenario results in the scheduling fragments depicted in Fig. 3. Rectangles clustering tasks correspond to the results of our decomposition steps: outmost rectangles result from deadline-based decomposition, middle rectangles from splitting based on release times, and innermost rectangles result from splitting based on dependencies.

Next, we compute length of these scheduling fragments using Eq. 9. Due to adaptation of tasks’ WCETs, handling of preemptions – e.g., task $\tau_{14,1}$ in schedule $VM schedule_1$ – is challenging. Here, we just split WCET to execution
<figure><img src="image_5.png" /><figcaption>**Fig. 3.** Scheduling fragments resulting from decomposition of local schedules $\sigma_i$, $1 \le i \le 3$.</figcaption></figure>

<table><caption>**Table 2.** Worst case time partition length for local scheduling fragments.</caption><thead><tr><th></th><th>φ<sub>1</sub><sup>v1</sup></th><th>φ<sub>2</sub><sup>v1</sup></th><th>φ<sub>3</sub><sup>v1</sup></th><th>φ<sub>4</sub><sup>v1</sup></th><th>φ<sub>1</sub><sup>v2</sup></th><th>φ<sub>2</sub><sup>v2</sup></th><th>φ<sub>4</sub><sup>v2</sup></th><th>φ<sub>5</sub><sup>v2</sup></th><th>φ<sub>6</sub><sup>v2</sup></th><th>φ<sub>7</sub><sup>v2</sup></th><th>φ<sub>1</sub><sup>v3</sup></th><th>φ<sub>2</sub><sup>v3</sup></th><th>φ<sub>3</sub><sup>v3</sup></th><th>φ<sub>4</sub><sup>v3</sup></th></tr></thead><tbody><tr><th>l<sub>h</sub><sup>vk</sup></th><td>300</td><td>240</td><td>125</td><td>375</td><td>90</td><td>175</td><td>175</td><td>150</td><td>160</td><td>130</td><td>175</td><td>465</td><td>150</td><td>200</td><td>175</td></tr></tbody></table>

parts of $\tau_{14,1}$ in the same proportion as it was in case of original WCET. Results are summarized in Tab. 2.

## 5.2 Multicore Scheduling by Time Partitions

Having local schedules decomposed into fragments, we now can allocate time partitions to dedicated cores of a multicore platform. In this example, we consider $m = 3$ VMs given by example applications introduced in this Section and $p = 2$ cores. Table 3 shows for each point in time – when the hypervisor can make scheduling decisions – why scheduling point occurs, what the current host time of hypervisor system is, which scheduling fragments are within sets $\mathcal{R}$ and $\mathcal{N}$, and which scheduling fragments are scheduled next on cores $C_1$ and $C_2$. For instance, applying rules defined in Sect. 4.3, hypervisor scheduling makes first decision based on deadlines of scheduling fragments. That is, $\varphi_1^{v1}$ and $\varphi_1^{v2}$ get higher priority than $\varphi_1^{v3}$.

Another interesting circumstance for making scheduling decision is at line 7 where “reason for scheduling” is $\varphi_2^{v1}$. This is the first time, $\mathcal{R}$ does not contain scheduling fragments of all VMs because $\varphi_3^{v1} \in \mathcal{N}$ requires input from $\varphi_2^{v3}$ that in worst case has not finished yet. Therefore, $\varphi_3^{v1} \in \mathcal{N}$ is not passed to $\mathcal{R}$ and thus is not considered by hypervisor. Finally, mapping of scheduling fragments to cores is used to define time partitions $I_h$ resulting, e.g., for core $C_1$ in

$$I_1^{v1} = [0, 540[ \qquad (11)$$
<table><caption>**Table 3.** Offline multicore scheduling of time partitions (scheduling fragments).</caption><thead><tr><th>Reason for scheduling</th><th>Host time</th><th>R</th><th>N</th><th>Core C<sub>1</sub></th><th>Core C<sub>2</sub></th></tr></thead><tbody><tr><td></td><td>0</td><td>φ<sup>v1</sup><sub>1</sub>, φ<sup>v2</sup><sub>1</sub>, φ<sup>v3</sup><sub>1</sub></td><td>φ<sup>v1</sup><sub>2</sub>, φ<sup>v2</sup><sub>2</sub>, φ<sup>v3</sup><sub>2</sub></td><td>φ<sup>v1</sup><sub>1</sub></td><td>φ<sup>v2</sup><sub>1</sub></td></tr><tr><td>σ<sup>f</sup><sub>1</sub>(τ<sub>1,1</sub>)</td><td>75</td><td>φ<sup>v1</sup><sub>1</sub>, φ<sup>v2</sup><sub>1</sub>, φ<sup>v3</sup><sub>1</sub></td><td>φ<sup>v1</sup><sub>2</sub>, φ<sup>v2</sup><sub>2</sub>, φ<sup>v3</sup><sub>2</sub></td><td>φ<sup>v1</sup><sub>1</sub></td><td>φ<sup>v2</sup><sub>1</sub></td></tr><tr><td>φ<sup>v2</sup><sub>1</sub></td><td>90</td><td>φ<sup>v1</sup><sub>1</sub>, φ<sup>v2</sup><sub>2</sub>, φ<sup>v3</sup><sub>1</sub></td><td>φ<sup>v1</sup><sub>2</sub>, φ<sup>v2</sup><sub>2</sub>, φ<sup>v3</sup><sub>2</sub></td><td>φ<sup>v1</sup><sub>1</sub></td><td>φ<sup>v2</sup><sub>2</sub></td></tr><tr><td>φ<sup>v2</sup><sub>2</sub></td><td>265</td><td>φ<sup>v1</sup><sub>1</sub>, φ<sup>v2</sup><sub>3</sub>, φ<sup>v3</sup><sub>1</sub></td><td>φ<sup>v1</sup><sub>2</sub>, φ<sup>v2</sup><sub>4</sub>, φ<sup>v3</sup><sub>2</sub></td><td>φ<sup>v1</sup><sub>1</sub></td><td>φ<sup>v3</sup><sub>1</sub></td></tr><tr><td>φ<sup>v1</sup><sub>1</sub></td><td>300</td><td>φ<sup>v1</sup><sub>2</sub>, φ<sup>v2</sup><sub>3</sub>, φ<sup>v3</sup><sub>1</sub></td><td>φ<sup>v1</sup><sub>3</sub>, φ<sup>v2</sup><sub>4</sub>, φ<sup>v3</sup><sub>2</sub></td><td>φ<sup>v1</sup><sub>2</sub></td><td>φ<sup>v3</sup><sub>1</sub></td></tr><tr><td>σ<sup>f</sup><sub>1</sub>(τ<sub>7,1</sub>)</td><td>450</td><td>φ<sup>v1</sup><sub>2</sub>, φ<sup>v2</sup><sub>3</sub>, φ<sup>v3</sup><sub>1</sub></td><td>φ<sup>v1</sup><sub>3</sub>, φ<sup>v2</sup><sub>4</sub>, φ<sup>v3</sup><sub>2</sub></td><td>φ<sup>v1</sup><sub>2</sub></td><td>φ<sup>v3</sup><sub>1</sub></td></tr><tr><td>φ<sup>v1</sup><sub>2</sub></td><td>540</td><td>φ<sup>v2</sup><sub>3</sub>, φ<sup>v3</sup><sub>1</sub></td><td>φ<sup>v1</sup><sub>3</sub>, φ<sup>v2</sup><sub>4</sub>, φ<sup>v3</sup><sub>2</sub></td><td>φ<sup>v2</sup><sub>3</sub></td><td>φ<sup>v3</sup><sub>1</sub></td></tr><tr><td>σ<sup>f</sup><sub>3</sub>(τ<sub>17,1</sub>)</td><td>565</td><td>φ<sup>v2</sup><sub>3</sub>, φ<sup>v3</sup><sub>1</sub></td><td>φ<sup>v1</sup><sub>3</sub>, φ<sup>v2</sup><sub>4</sub>, φ<sup>v3</sup><sub>2</sub></td><td>φ<sup>v2</sup><sub>3</sub></td><td>φ<sup>v3</sup><sub>1</sub></td></tr><tr><td>φ<sup>v2</sup><sub>3</sub></td><td>715</td><td>φ<sup>v2</sup><sub>4</sub>, φ<sup>v3</sup><sub>1</sub></td><td>φ<sup>v1</sup><sub>3</sub>, φ<sup>v2</sup><sub>5</sub>, φ<sup>v3</sup><sub>2</sub></td><td>φ<sup>v2</sup><sub>4</sub></td><td>φ<sup>v3</sup><sub>1</sub></td></tr><tr><td>φ<sup>v3</sup><sub>1</sub></td><td>730</td><td>φ<sup>v2</sup><sub>4</sub>, φ<sup>v3</sup><sub>2</sub></td><td>φ<sup>v1</sup><sub>3</sub>, φ<sup>v2</sup><sub>5</sub>, φ<sup>v3</sup><sub>3</sub></td><td>φ<sup>v2</sup><sub>4</sub></td><td>φ<sup>v3</sup><sub>2</sub></td></tr><tr><td>φ<sup>v2</sup><sub>4</sub></td><td>865</td><td>φ<sup>v2</sup><sub>5</sub>, φ<sup>v3</sup><sub>2</sub></td><td>φ<sup>v1</sup><sub>3</sub>, φ<sup>v3</sup><sub>3</sub></td><td>φ<sup>v2</sup><sub>5</sub></td><td>φ<sup>v3</sup><sub>2</sub></td></tr><tr><td>φ<sup>v3</sup><sub>2</sub></td><td>880</td><td>φ<sup>v1</sup><sub>3</sub>, φ<sup>v2</sup><sub>5</sub>, φ<sup>v3</sup><sub>3</sub></td><td>φ<sup>v3</sup><sub>4</sub></td><td>φ<sup>v2</sup><sub>5</sub></td><td>φ<sup>v3</sup><sub>3</sub></td></tr><tr><td>φ<sup>v2</sup><sub>5</sub></td><td>1025</td><td>φ<sup>v1</sup><sub>3</sub>, φ<sup>v3</sup><sub>3</sub></td><td>φ<sup>v3</sup><sub>4</sub></td><td>φ<sup>v1</sup><sub>3</sub></td><td>φ<sup>v3</sup><sub>3</sub></td></tr><tr><td>φ<sup>v3</sup><sub>3</sub></td><td>1080</td><td>φ<sup>v1</sup><sub>3</sub>, φ<sup>v3</sup><sub>4</sub></td><td></td><td>φ<sup>v1</sup><sub>3</sub></td><td>φ<sup>v3</sup><sub>4</sub></td></tr><tr><td>φ<sup>v1</sup><sub>3</sub></td><td>1150</td><td>φ<sup>v3</sup><sub>4</sub></td><td></td><td></td><td>φ<sup>v3</sup><sub>4</sub></td></tr><tr><td>φ<sup>v3</sup><sub>4</sub></td><td>1255</td><td></td><td></td><td></td><td></td></tr><tr><td>σ<sup>s</sup><sub>1</sub>(τ<sub>1,2</sub>)</td><td>1500</td><td>φ<sup>v1</sup><sub>4</sub>, φ<sup>v2</sup><sub>6</sub></td><td>φ<sup>v2</sup><sub>7</sub></td><td>φ<sup>v1</sup><sub>4</sub></td><td>φ<sup>v2</sup><sub>6</sub></td></tr><tr><td>σ<sup>f</sup><sub>1</sub>(τ<sub>1,2</sub>)</td><td>1575</td><td>φ<sup>v1</sup><sub>4</sub>, φ<sup>v2</sup><sub>6</sub></td><td>φ<sup>v2</sup><sub>7</sub></td><td>φ<sup>v1</sup><sub>4</sub></td><td>φ<sup>v2</sup><sub>6</sub></td></tr><tr><td>φ<sup>v2</sup><sub>6</sub></td><td>1630</td><td>φ<sup>v1</sup><sub>4</sub>, φ<sup>v2</sup><sub>7</sub></td><td></td><td>φ<sup>v1</sup><sub>4</sub></td><td>φ<sup>v2</sup><sub>7</sub></td></tr><tr><td>φ<sup>v2</sup><sub>7</sub></td><td>1805</td><td>φ<sup>v1</sup><sub>4</sub></td><td></td><td>φ<sup>v1</sup><sub>4</sub></td><td></td></tr><tr><td>φ<sup>v1</sup><sub>4</sub></td><td>1875</td><td></td><td></td><td></td><td></td></tr></tbody></table>

# 6 Conclusion

In this paper, we presented an approach for hierarchical scheduling of periodic dependent singelcore real-time systems on a multicore hardware. We introduced a system model that covers tasks with precedence constraints as well as VMs that host subsets of these tasks. To schedule the set of VMs on a multicore hardware with full hypervisor-based virtualization, we first proposed a concept to decompose local singlecore schedules into fragments based on deadlines, release times and inter-VM dependencies. Afterwards, we presented our approach for offline scheduling of these fragments on a multicore platform. Finally, we applied our approach to an automotive use case from literature to demonstrate functionality of the proposed concept. Future work aims at taking overhead induced by virtualization as well as communication costs between VMs into account.

# Acknowledgment

This work was partly funded by German Ministry of Education and Research (BMBF) through project “it’s OWL Intelligente Technische Systeme OstWestfalenLippe” (02PQ1021) and ITEA2 project AMALTHEA4public (01IS14029J).
References

1. Baruah, S., Bertogna, M., Buttazzo, G.: Multiprocessor Scheduling for Real-Time Systems. Springer (2015)

2. Chetto, H., Silly, M., Bouchentouf, T.: Dynamic scheduling of real-time tasks under precedence constraints. Real-Time Systems 2(3), 181–194 (1990)

3. Cho, H., Ravindran, B., Jensen, E.: An optimal real-time scheduling algorithm for multiprocessors. In: 27th IEEE International Real-Time Systems Symposium. pp. 101–110 (2006)

4. Crespo, A., Ripoll, I., Masmano, M.: Partitioned embedded architecture based on hypervisor: The xtratum approach. In: European Dependable Computing Conference (EDCC). pp. 67–72 (2010)

5. Davis, R.I., Burns, A.: A survey of hard real-time scheduling for multiprocessor systems. ACM Comput. Surv. 43(4), 35:1–35:44 (Oct 2011)

6. Forget, J., Boniol, F., Grolleau, E., Lesens, D., Pagetti, C.: Scheduling dependent periodic tasks without synchronization mechanisms. In: 16th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS). pp. 301–310 (2010)

7. Groesbrink, S., Almeida, L.: A criticality-aware mapping of real-time virtual machines to multi-core processors. In: IEEE Emerging Technology and Factory Automation (ETFA). pp. 1–9 (2014)

8. Kandasamy, N., Hayes, J., Murray, B.: Dependable communication synthesis for distributed embedded systems. In: Anderson, S., Felici, M., Littlewood, B. (eds.) Computer Safety, Reliability, and Security, Lecture Notes in Computer Science, vol. 2788, pp. 275–288. Springer Berlin Heidelberg (2003)

9. Kleidermacher, D.: System virtualization in multicore systems. In: Moyer, B. (ed.) Real World Multicore Embedded Systems – A Practical Approach, pp. 227–267. Elsevier (2013)

10. Klobedanz, K., Jatzkowski, J., Rettberg, A., Mueller, W.: Fault-tolerant deployment of real-time software in autosar ecu networks. In: Schirner, G., Götz, M., Rettberg, A., Zanella, M., Rammig, F. (eds.) Embedded Systems: Design, Analysis and Verification, IFIP Advances in Information and Communication Technology, vol. 403, pp. 238–249. Springer Berlin Heidelberg (2013)

11. Lee, S.K.: On-line multiprocessor scheduling algorithms for real-time tasks. In: Proceedings of TENCON '94. IEEE Region 10's Ninth Annual International Conference. Theme: Frontiers of Computer Technology. pp. 607–611 (1994)

12. Main, C.: Virtualization on multicore for industrial real-time operating systems [from mind to market]. Industrial Electronics Magazine, IEEE 4(3), 4–6 (2010)

13. Masmano, M., Ripoll, I., Crespo, A.: Xtratum: A hypervisor for safety critical embedded systems. In: Proceedings of 11th Real-Time Linux Workshop. pp. 263–272 (2009)

14. Masrur, A., Drossler, S., Pfeuffer, T., Chakraborty, S.: Vm-based real-time services for automotive control applications. In: IEEE 16th International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA). pp. 218–223 (2010)

15. Rönngren, S., Shirazi, B.: Static multiprocessor scheduling of periodic real-time tasks with precedence constraints and communication costs. In: Proceedings of 28th Hawaii International Conference on System Sciences. vol. 2, pp. 143–152 (1995)

16. Xi, S., Xu, M., Lu, C., Phan, L., Gill, C., Sokolsky, O., Lee, I.: Real-time multicore virtual machine scheduling in xen. In: International Conference on Embedded Software (EMSOFT). pp. 1–10 (2014)