## 5 Heuristic Scheduling Algorithm
### Algorithm 3: Executor Creation  
This section presents the algorithm \(CreateExecutor\), whose objective is to select a subset of callbacks to be assigned to one executor and to determine its scheduling parameters.  
The Algorithm 3 takes as input a set of callbacks \(\Pi\) and then determines as output a subset \(\Lambda\) to be assigned to an executor e. The algorithm also defines the sequence order of callbacks within the executor and computes its timing parameters: vector of execution times \(E\), period \(T\), and deadline \(D\).  
We say that there is a set of callbacks \(\Lambda\subseteq\Pi\) that can be assigned to the same executor if and only if:  
**Condition 1:**: \(\forall i\in\Lambda:T=GCD_{i=1}^{|\Lambda|}p_{i}>1\)
**Condition 2:**: \(\overline{E}=\sum_{s=0}^{N-1}C_{s}\leq T_{j}\)
**Condition 3:**: \(R\leq\min_{i=1}^{|\Lambda_{j}|}d_{i}\)  
Condition 3 is ensured by the feasibility test, which guarantees that R is less than or equal to the shortest callback deadline. Moreover, the executor deadline may be longer than its period, and consequently, buffering instances may occur for the execution of an executor. The number of buffered instances of an executor \(e_{j}\) is bounded by \(\left\lceil R_{\tau_{j}}/T_{j}\right\rceil\). The first condition prevents the maximum buffering of an executor instance by creating subsets of callback periods.  
To implement this, the bucket select algorithm (BSA) is used to divide \(n\) callbacks into several buckets \(\{L_{i}\}\) using the divisibility test by prime numbers. The bucket select Algorithm 4 described in the following and illustrated by an example in Figure 5 selects one bucket from n callbacks with a time complexity of \(\mathcal{O}(kn)\).  
Let [K] be a list of first prime numbers. For each prime number \(x_{i}\) (\(i=1\) to \(k\)), the algorithm regroups in a list \(L_{i}\) (\(i=1\) to \(k\)) the callbacks whose periods can be divided by \(x_{i}\). Therefore, each bucket \(L_{i}\) contains a subset of callback periods characterized by two timing parameters: \(T[i]\), which corresponds to the GCD of the callback periods of the bucket \(L_{i}\), and \(P[i]\), which is the minimum prime number, where \(T[i]\) is divisible by it. Finally, the algorithm returns the bucket \(L_{b}\) with \(x_{i}=P[i]\) and the highest period value \(T[i]\), denoted by \(T_{b}\).  
Figure 5: Example of the bucket select algorithm (BSA).  
```
Input:\(\Pi=\{\tau_{1},\tau_{2},\ldots,\tau_{n}\}\), \(K=\{x_{1},x_{2},\ldots,x_{k}\}\) Output:\(L_{b}\), \(T_{b}\) /* Creating k empty list \(\{L\}\) and two list of k sise [T] and [P] */ for\(i=1\) to kdo
1\(L_{i}=\emptyset;T[i]=0;P[i]=0;\)
2 end for /* Creating buckets \(L_{1},L_{2},\ldots,L_{k}\) */ for\(i=1\) to ndo
3 for\(j=1\) to kdo
4 if\(mod(p_{i},x_{j})=0\)then
5\(L_{j}=L_{j}\cup\tau_{i}\) ; /* */
6 end if
7
8 end for /* Computing [T] and [P] */ for\(i=1\) to kdo
9\(T[i]=GCD(L_{i})\) ; // for\(j=1\) to kdo
10 if\(mod(T[i],x_{j})=0\)then
11\(P[i]=x_{j}\) ; // This is the first prime number, where \(T_{i}\) is divisible by it
12 break
13 end if
14
15 end for /* Determining \(L_{b}\) and \(T_{b}\) */
16 for\(j=1\) to kdo
17 if\(x_{j}=P[j]\) and \(T[j]>T_{b}\)then
18\(T_{b}=T[j]\) ; //
19\(L_{b}=L_{j}\) ; // Select the bucket that has the greatest period value
20 end if
21
22 end for
```  
**Algorithm 4**Bucket select algorithm  
To avoid overloading the executor, a sequencing of callbacks within the executor is necessary. For that, we adapt the lowest peak (LP) method developed in [35]. The algorithm chooses the callback offset through a larger frame window \(T_{w}\), which is equal to the LCM of the callback periods. The maximum execution time \(\overline{E_{j}}=max_{s=0}^{T_{w}/T_{j}}C_{s}\) must be less than or equal to the executor period \(T_{j}\).  
The Algorithm 3 creates an executor e from n callbacks with a time complexity of \(\mathcal{O}((k+N)n+n)\), where N is the frame number (\(N=T_{w}/T\)) and k is the number of prime numbers.