# DAG Hierarchical Schedulability Analysis for Avionics Hypervisor in Multicore Processors
## 4 Schedulability Analysis
### Scheduling
#### 4.1.1 Concurrent Parent and Child Model  
The CPCM includes two key parts. (i) The CP is divided into a set of consecutive sub-paths based on the potential delay that can happen (in Figure 3a). (ii) With every sub-path, CPCM distinguishes NC-joints, which can run in parallel with the sub-path and prolong the start of the next sub-path on the basis of priority constraints (in Figure 3b,c). Figure 3: The CPCM of a DAG. (**a**) the CP is divided into a set of consecutive sub-paths based on the potential delay it can incur. (**b**) execute in parallel with the sub-path. (**c**) delay the start of the next sub-path, based on precedence constraints. The intuition of the CPCM is: when the critical path is executing, it utilizes just one core so that the non-critical ones can execute in parallel on the remaining \((m-1)\) cores. The time allowed for executing non-critical joints in parallel is termed as the capacity, which is the length of the critical path. Note that non-critical joints that utilize this capacity to execute cannot cause any delay to the critical path. The sub-paths in the critical path are termed capacity parents \(\Phi^{*}\) and all non-critical joints are capacity children \(\Phi\). For each parent \(\phi_{i}^{*}\in\Phi^{*}\), it has a set of children \(H(\phi_{i}^{*})\) that can execute using \(\phi_{i}^{*}\)'s capacity as well as delay the next parent \(\phi_{i+1}^{*}\) in the critical path. Algorithm 1 shows the process for constructing the CPCM. Starting from the scratch in \(\delta^{*}\), capacity parents are formed by analyzing joint dependency between the CP and NC-joints. A parent \(\phi_{i}^{*}\), its joints should run consecutively without prolong from NC-joints according to dependency. Every joint in \(\phi_{i}^{*}\), other than the scratch, only owns a predecessor which is the previous joint in \(\phi_{i}^{*}\). Three capacity parents are identified in Figure 3b. ```
Input:\(G=(V,E)\)\(\delta^{*}\) Output:\(\Phi^{*},H(\phi_{i}^{*}),G(\phi_{i}^{*}),\forall\phi_{i}^{*}\in\Phi^{*}\) Specifications:\(\delta^{*},V^{-}=V/\delta^{*}\) if\(\Phi^{*}=\varnothing\) /* distinguishing capacity parents */ for every \(v_{j}\in\delta^{*}\) \(\phi_{i}^{*}=\left\{v_{j}\right\}\);\(\delta^{*}=\delta^{*}/v_{j}\) whilepredecessor\((v_{j+1})=\left\{v_{j}\right\}\)do \(\phi_{i}^{*}=\phi_{i}^{*}\cup\left\{v_{j+1}\right\}\);\(\delta^{*}=\delta/v_{j}\) end \(\Phi^{*}=\Phi^{*}\cup\phi_{i}^{*}\) end /* distinguishing capacity children */ for every \(\phi_{i}^{*}\in\Phi^{*}\) \(H(\phi_{i}^{*})=\mathit{ancestors}(\phi_{i+1}^{*})\cap V^{-}\) \(G(\phi_{i}^{*})=\cup_{v_{j}\in H(\phi_{i}^{*})}\{C(v_{j})\cap V^{-}\}\) \(V^{-}=V^{-}/H(\phi_{i}^{*})\) end return\(\Phi^{*},H(\phi_{i}^{*}),G(\phi_{i}^{*}),\forall\phi_{i}^{*}\in\Phi^{*}\)
```  
**Algorithm 1**Concurrent Parent and Child Model algorithm \(\mathit{CPCM}(G,\delta^{*})\)  
Every \(\phi_{i}^{*}\in\Phi^{*}\), its children \(H(\phi_{i}^{*})\) are determined to the joints that can run synchronously to \(\phi_{i}^{*}\), and prolong the start of \(\phi_{i+1}^{*}\). Joints in \(H(\phi_{i}^{*})\) that finish after \(\phi_{i}^{*}\) will prolong the start of \(\phi_{i+1}^{*}\). Joints in \(H(\phi_{1}^{*})\) can prolong \(\phi_{2}^{*}\) if they are finished later than \(\phi_{1}^{*}\) in Figure 3b. The CPCM shows details of the possible latency attributed to NC-joints on the CP. In addition, a child \(v_{j}\in H(\phi_{i}^{*})\) can start before, synchronized with, or after the start of \(\phi_{i}^{*}\). With the latter two, they will just use the capacity of \(\phi_{i}^{*}\). Children of earlier releases can run at the same time as some previous parents, thus interfering with their children and causing indirect delays to parents. With a parent \(\phi_{i}^{*}\), \(G(\phi_{i}^{*})\) is the joints that fall within the child groups of later parents, but which can run with \(\phi_{i}^{*}\) in parallel. Joints in \(G(\phi_{1}^{*})\), \(G(\phi_{2}^{*})\) fall within \(H(\phi_{1}^{*})\), \(H(\phi_{2}^{*})\) in Figure 3c.