## 5 Heuristic Scheduling Algorithm
### Algorithm 2: Assignment  
This section details Algorithm 2, the objective of which is to identify a subset of callbacks that could be regrouped with one executor while satisfying real-time requirements.  
**Theorem 1**.: _Suppose a set \(\Delta\) of callbacks and an executor \(e_{j}\). There is a subset \(\Pi_{j}\subseteq\Delta\) that can be assigned to the same executor \(e_{j}\) if and only if each element \(\tau_{i}\) of \(\Pi_{j}\) is schedulable when assigned a lower priority and other elements\(\Delta\) -\(\tau_{i}\) are assigned higher priorities._  
Proof.: The proof can be obtained by contradiction. Let us suppose two callbacks \(\tau_{1}\) and \(\tau_{2}\) with \(d_{1}\) and \(d_{2}\) as deadlines, respectively. Suppose that the set of callbacks \(\{\tau_{1}\), \(\tau_{2}\}\) is feasible with the lowest priority. Two distinct cases may appear: (1) \(\tau_{1}\) has a higher priority than \(\tau_{2}\), or (2) \(\tau_{2}\) has a higher priority than \(\tau_{1}\). The response times of \(\tau_{1}\) and \(\tau_{2}\) when assigned the lowest priority are identical for the two cases. This means that \(\tau_{1}\) and \(\tau_{2}\) must always complete the execution before the shortest deadline. Therefore, the set of callbacks \(\tau_{1}\), \(\tau_{2}\)) can be assigned to an executor with a deadline D =min\(\{d_{1},d_{2}\}\). Consequently, if a set of callbacks is feasible when all callbacks are assigned the lowest priority, then this set can be assigned to only one executor. On the other hand, if \(\{\tau_{1}\), \(\tau_{2}\}\) is not schedulable with the lowest priority, there is no priority assignment that allows scheduling callbacks. Therefore, if a set of callbacks can be assigned to one executor, each callback is feasible when assigned to the lowest priority.  
As stated in the above theorem, the subset \(\Pi_{j}\) can be obtained if each callback of \(\Delta\) satisfies the following equation:  
\[R_{i}=c_{i}+\sum_{k\in\Delta-\{\tau_{i}\}}\left[\frac{R_{i}}{p_{k}}\right]c_{ k}\leq d_{i} \tag{9}\]  
\(R_{i}\) is the worst-case response time of callback \(\tau_{i}\) when assigned the lowest priority and all callbacks are released at the same time (critical instant). \(p_{k}\) and \(c_{k}\) are, respectively, the period and the worst-case execution time for the \(k^{th}\) callback. This results in the longest response time to callback [21]. As all callbacks have the same wcrt when assigned to the lowest priority, \(R_{i}\) can be simplified as:  
\[\forall\tau_{i}\in\Delta:R=\sum_{k=1}^{|\Delta|}\left[\frac{R}{p_{k}}\right]e_ {k}\leq d_{i} \tag{10}\]  
and \(R\) can be solved by the following recurrence relation:  
\[R_{t+1}=\sum_{k=1}^{|\Delta|}\left[\frac{R_{t}}{p_{k}}\right]c_{k} \tag{11}\]  
where \(R_{0}=\sum_{k=1-\mid\Delta\mid}c_{k}\). Equation (11) surely converges if the processor utilization factor does not exceed 100%. The schedulability condition is given by the following condition:  
\[R_{t+1}>\max_{k=1}^{|\Delta|}\{d_{k}\} \tag{12}\]  
where \(d_{k}\) is the deadline for the \(k^{th}\) callback.  
The Algorithm 2 finds, from a set \(\Delta\), a subset of callbacks \(\Pi\) that can be assigned to the same executor with a time complexity of \(\mathcal{O}((\max(p_{i})/\min(p_{i}))n)\).  
```
Input:\(\Delta=\{\tau_{1},\tau_{2},\ldots,\tau_{n}\}\) Output:\(\Pi\)
1\(\Pi=\emptyset\) ; //
2\(R=\sum_{i=1}^{|\Delta|}c_{i}\) ; //
3\(D_{max}=\max_{i=1}^{|\Delta|}\{d_{i}\}\) ; //
4 cont = True ; //
5 whilecontdo
6\(R_{t}=\sum_{i=1}^{|\Delta|}\left\lceil\frac{R}{p_{i}}\right\rceil c_{i}\) ; //
7 if\(R==R_{t}\)then
8 cont = False
9
10 end if
11 if\(R_{t}>D_{max}\)then
12 return\(\emptyset\) ; // \(\Delta\) is not schedulable
13 end if
14\(R=R_{t}\) ;
15
16 end if
17 for\(i=1\) to \(|\Delta|\)do
18 if\((R\leq d_{i})\)then
19\(\Pi=\Pi\cup\{\tau_{i}\}\);
20
21 end if
22
23 end for
```  
**Algorithm 2**Mapping feasibility test