# DAG Hierarchical Schedulability Analysis for Avionics Hypervisor in Multicore Processors
## 4 Schedulability Analysis
### Analysis of Response Time
#### 4.2.1 The (\(\alpha\), \(\beta\))-pair Analysis Formulation  
In CPCM, the CP of the DAG task is converted to a series of uninterrupted parents \(\Phi^{*}\). A parent \(\phi^{*}_{i}\in\Phi^{*}\) can start, only if the previous parent \(\phi^{*}_{i-1}\) and its children \(H(\phi^{*}_{i-1})\) have finished the run (in Figure 3b). In any case, \(H(\phi^{*}_{i-1})\) can lead to a latency from \(G(\phi^{*}_{i-1})\) (early-released children that can run concurrently with \(H(\phi^{*}_{i-1})\)), which in turn, delays the start of \(\phi^{*}_{i-1}\) (in Figure 3c). Based on Definitions 1 and 2, the parallel workload \(\alpha_{i}\) of \(\phi^{*}_{i}\) finishes no later than \(h(\phi^{*}_{i})\) on \(m-1\) processors. After \(\phi^{*}_{i}\) completes, the interfering workload then executes on whole processors, in which the latest-finished joint in \(H(\phi^{*}_{i})\) gives the earliest starting time to the next parent (if exist). Therefore, bounding this delay requires:  
1. Bounds of parallel workload (\(\alpha_{i}\));
2. Bounds of the longest run sequence in \(H(\phi^{*}_{i})\) that runs later than \(h(\phi^{*}_{i})\), expressed as \(\beta_{i}\).  
With a random execution order, the WC completion time of \(\beta_{i}\) imposed an effective upper bound for the WC completion of workload in \(H(\phi^{*}_{i})\) that runs later than \(h(\phi^{*}_{i})\). With \(\alpha_{i}\) and \(\beta_{i}\) expressed, Theorem 2 offers the bounds on the latency \(\phi^{*}_{i}\) due to the child joints in \(H(\phi^{*}_{i-1})\).  
**Theorem 3**.: _Two uninterrupted offers \(\phi_{i}^{*}\), \(\phi_{i-1}^{*}\), the children joints in \(H(\phi_{i-1}^{*})\), can prolong \(\phi_{i}^{*}\) no more than \(\lceil\left(C_{i}-\alpha_{i}-L_{i}-\beta_{i}\right)/m+\beta_{i}\rceil\)._  
Proof.: By Definition 2, the interfering workload in \(H(\delta_{i}^{*})\cup G(\delta_{i}^{*})\) that can (directly or transitively) delay \(\delta_{i}^{*}\) is at most \(C_{i}-L_{i}-\alpha_{i}\). Given the longest execution sequence in \(H(\delta_{i}^{*})\) in the interfering workload (i.e., \(\beta_{i}\)), the worst-case finish time of \(H(\delta_{i}^{*})\) (and also \(\beta_{i}\)) is bounded as \(\lceil\left(C_{i}-\alpha_{i}-L_{i}-\beta_{i}\right)/m+\beta_{i}\rceil\), for a system with \(m\) cores. Note, as \(\beta_{i}\) is accounted for explicitly, it is removed from the interfering workload to avoid repetition.  
On the basis of Theorem 3, the RTA of DAG task can be expressed by Formula (2). As \(C_{i}-L_{i}-\alpha_{i}\) starts strictly after \(h(\phi_{i}^{*})\), the completion time of both \(\phi_{i}^{*}\) and \(H(\phi_{i}^{*})\) is bounded by the length of \(\phi_{i}^{*}\) and the WCET of \(\beta_{i}\). In short, \(\phi_{i+1}^{*}\) can only start after the finish of \(\phi_{i}^{*}\) and whole joints in \(H(\phi_{i}^{*})\). Therefore, the final response time of DAG is limited by the sum of the CTs of every parent and its children.  
\[R=\sum\
olimits_{\phi_{i}^{*}\in\Phi^{*}}\{\lceil\left(C_{i}-\alpha_{i}-L_{i}- \beta_{i}\right)/m\rceil+\beta_{i}+L_{i}\} \tag{2}\]  
Compared with traditional analysis, it can promote the WC response time approximation by tightening the interference on the CP, and the correctness is not damaged. Namely, analysis is not always carried out beyond the traditional limits. Hence, \(\min\{L+\lceil\left(C-L\right)/m\rceil,R\}\) is the final analytical boundary.