# DAG Hierarchical Schedulability Analysis for Avionics Hypervisor in Multicore Processors
## 4 Schedulability Analysis
### Analysis of Response Time
#### 4.2.3 Explicit Execution Order (ESO)  
Tighter boundaries can be achieved by using ESO for NC-joints, because every joint could just be interfered with by concurrent joints with higher priority. Taking the proposed scheduling, a novel analysis method is illustrated, which can sustain CPE and explicit run sequence of NC-joints. With joint priority, the interfering joints of \(v_{j}\) on \(m-1\) processors could be effectively decreased to joints in \(\mathrm{N}(v_{j})\) that have a higher priority than \(p_{j}\), \(m-1\) joints in \(\mathrm{N}(v_{j})\) that have a lower priority and the highest WCET because of the non-preemptive schedule [10]. \(\mathrm{N}^{e}(v_{j})\) are the joints that can interfere with a NC-joint \(v_{j}\) with an explicit order, in Formula (3), in which \(\mathrm{argmax}_{v_{2}}^{m-1}\) returns the first \(m-1\) joints with the highest value of the given metric. For the sake of simplicity, it takes \((m-1)\) low-priority joints as the upper limit. The better ILP-based method can be used to calculate this congestion accurately. In short, if joint-level preemption is allowed, \(\mathrm{N}^{e}(v_{j})\) will further decrease to \(\left\{v_{k}|q_{k}>q_{j},v_{k}\in\mathrm{N}(v_{j})\right\}\). \[\mathrm{N}^{e}(v_{j})=\left\{v_{k}|q_{k}>q_{j},v_{k}\in\mathrm{N}(v_{j})\right\} \cup\underset{v_{k}\in\mathrm{N}(v_{j})}{\mathrm{argmax}}\{\mathrm{C}_{k}|q_{ k}<q_{j},v_{k}\in\mathrm{N}(v_{j})\} \tag{3}\]  
\(h(v_{j}),\forall v_{j}\in V\) could be calculated by Formula (3), \(\mathrm{N}^{e}(v_{j})\) applied to NC-joints running on other \(m-1\) processors. Therefore, \(\alpha_{i}\), \(\beta_{i}\) can be bounded with the updated \(h(\phi_{i}^{*})\), \(h(v_{j}),\forall v_{j}\in H(\phi_{i}^{*})\cup G(\phi_{i}^{*})\). Note that with an explicit schedule, \(\delta_{v_{e}}\) calculated in Formula (3), it is not necessarily the longest path in \(H(\phi_{i}^{*})\) that runs in the interfering workload [11]. On the contrary, \(\delta_{v_{e}}\) offers the path that is always finished last because of the pre-planned joint execution sequence. However, the final limit of the response time is different from the general situation. With joint priority, whole workload in \((\mathrm{C}_{i}-L_{i}-\alpha_{i}-\beta_{i})\) do not have to hinder the execution of \(\delta_{v_{e}}\). \(R^{e}\) is the response time of the DAG task with ESO. It is defined in Formula (4), in which decides the joints that could prolong \(\delta_{v_{e}}\), \(l_{\delta_{v_{e}},j}\) offers the real latency on \(\delta_{v_{e}}\) from joint \(v_{j}\) in the interfering workload. \[R^{e}=\beta_{i}+\sum_{\phi_{i}^{*}\in\Phi^{*}}L_{i}+\left\{ \begin{matrix}0& if\Big{|}\Lambda_{\mathrm{N}^{e}(\delta_{v_{e}})}|<\mathrm{m}\\ \Big{|}\sum_{v_{j}\in\mathrm{N}^{e}(\delta_{v_{e}})}I_{\delta_{v_{e}},j}/m \Big{|}&\text{otherwise}\end{matrix} \right. \tag{4}\]  
The length of \(\phi_{i}^{*}(L_{i})\) and the WC latency on \(\delta_{v_{e}}(I_{\delta_{v_{e}}})\) in the interfering workload, of \(\phi_{i}^{*}\) is the WC completion time and \(H(\phi_{i}^{*})\) is upper bounded by \(\beta_{i}+L_{i}+\left\lceil\sum_{v_{j}\in\mathrm{N}^{e}(\delta_{v_{e}})}I_{ \delta_{v_{e}},j}/m\right\rceil\). If the number of paths in the joints that can cause \(I_{\delta_{v_{e}}}\) is smaller than \(m\), \(\left(|\wedge_{\mathrm{N}^{e}(\delta_{v_{e}})}|<m\right)\), \(\delta_{v_{e}}\) runs directly after \(\phi_{i}^{*}\) and finishes by \(L_{i}+\beta_{i}\). Note that \(I_{\delta_{v_{e}}}=0\), \(\beta_{i}=0\), as whole workload in \(H(\phi_{i}^{*})\) contributes to \(\alpha_{i}\) so that \(\phi_{i+1}^{*}\) can start immediately after \(\phi_{i}^{*}\). These joints can interfere with \(\delta_{v_{e}}\) (namely, \(\mathrm{N}^{e}(\delta_{v_{e}})\)) are bound by Formula (5), in which \(I_{\delta_{v_{e}},j}\) offers the real latency from joint \(v_{j}\) on \(\delta_{v_{e}}\).