# DAG Hierarchical Schedulability Analysis for Avionics Hypervisor in Multicore Processors
## 2 Preliminaries
### Task Model  
Any DAG task is \(\tau_{i}=\{D_{i},T_{i},G_{i}\}\), where \(D_{i}\) is the constrained relative deadline, \(T_{i}\) is the minimum inter-arrival time, within \(D_{i}\leq T_{i}\), and \(G_{i}\) is the graph defining a series of activities forming the task. The graph is characterized by \(G_{i}=(V_{i},E_{i})\) where \(V_{i}\) is a series of joints and \(E_{i}\subseteq(V_{i}^{\rightarrow}V_{j})\) is a series of directed edges connecting any two joints. Every joint \(v_{i}\in V_{i}\) is the computation unit that must be executed unceasingly and is defined by WCET (Worst Case Execution Time), namely \(C_{i}\).  
Either \(v_{j}\), \(v_{k}\) form a directional edge, only if \(v_{j}\) has finished and \(v_{k}\) begins to be executed, \(v_{j}\) is a predecessor of \(v_{k}\), and \(v_{k}\) is a successor of \(v_{j}\). Each joint \(v_{j}\) has a \(predecessor(v_{j})\) and a \(successor(v_{j})\), \(predecessor(v_{j})=\{v_{k}\in V\big{|}(v_{j},v_{k})\in E\}\) and \(successor(v_{j})=\{v_{k}\in V\big{|}(v_{j},v_{k})\in E\}\). Joints that are either directly or transitively predecessors and successors of a joint \(v_{j}\) are termed as its ancestors \(ancestors(v_{j})\) and descendants \(descendants(v_{j})\) respectively. The joint \(v_{j}\) with \(predecessor(v_{j})=\varnothing\) or \(successor(v_{j})=\varnothing\) is referred to as the sink \(v_{sink}\) or source \(v_{source}\). In order not to lose generality, suppose DAG has one sink and source joint. Joints that can execute concurrently with \(v_{j}\) are given by \(C(v_{j})=\{v_{k}\big{|}v_{k}\
otin(ancestors(v_{j}))\cup descendants(v_{j})), \forall v_{k}\in V\}\)[13].  
DAG tasks have basic characteristics. Firstly, an arbitrary path \(\delta_{a}=\{v_{s},\cdots,v_{e}\}\) is a joint sequence in \(V\) and follows \((v_{k},v_{k+1})\in E,\forall v_{k}\in\delta_{a}/v_{e}\). The path in \(V\) is defined as \(\Lambda_{V}\). A local path is a sub-path within the task and as such does not feature both the source \(v_{source}\) and the sink \(v_{sink}\), \(length(\delta_{a})=\sum_{\forall v_{k}\in\delta_{a}}C_{k}\) provides the length of \(\delta_{a}\). Secondly, the longest complete path is referred to as the critical path (CP) \(\delta^{*}\), and its length is denoted by \(L\), where \(L=\max\{length(\delta_{a}),\forall\delta_{a}\in\Lambda_{V}\}\). Joints in \(\delta^{*}\) are referred to as the critical joints. Other joints are referred to as NC-joints (NC-joints), denoted as \(V^{\rightarrow}=V/\delta^{*}\). Finally, the workload \(W\) is the sum of a task's WCETs, \(C=\sum_{\forall v_{k}\in V}C_{k}\). The workload of all NC-joints is called the non-critical workload.  
Figure 2a depicts a DAG task with \(V=\{v_{1},v_{2},\cdots,v_{9}\}\). The number in the upper left corner of every joint provides WCET, for example \(C_{6}=4\). For \(v_{6}\) have \(predecessor(v_{6})=\{v_{2},v_{3}\}\), \(ancestors(v_{6})=\{v_{1},v_{2},v_{3}\}\), \(successor(v_{6})=descendants(v_{6})=\{v_{9}\}\) and \(C(v_{j})=\{v_{2},v_{3}\}\). \(L=14\), \(C=30\), \(\delta^{*}=\{v_{1},v_{2},v_{6},v_{9}\}\), \(v_{source}=v_{1},v_{sink}=v_{9}\).