## 3 FENP_MC: Fixed Execution Non-Preemptive Mixed Criticality
### Feasibility Analysis  
#### 3.3.1 Theoretical Aspects  
Next, we present an exact feasibility test for perfectly periodical execution in a non-preemptive context. We call this type of execution Fixed Execution Non-Preemptive (FENP). The test is analogous with that provided in [24].  
\begin{table}
\begin{tabular}{c c c c c c} \hline \hline
**Task** & \(T_{i}\) & \(D_{i}\) & \(L_{i}\) & \(C_{i,L_{Lo}}\) & \(C_{i,L_{Hi}}\) \\ \hline \(M_{1}\) & 8 & 8 & Lo & 2 & - \\ \(M_{2}\) & 12 & 12 & Hi & 2 & 6 \\ \(M_{3}\) & 16 & 16 & Lo & 2 & - \\ \(M_{4}\) & 24 & 24 & Hi & 1 & 5 \\ \hline \hline \end{tabular}
\end{table}
Table 2: Four-task set example.  
Figure 3: Example of a criticality mode switch.  
Let \(M=\{M_{1},\ M_{2},\ \ldots,\ M_{n}\}\) be a set of \(n\) independent MC fixed execution tasks (MC-FModXs), sorted in nondecreasing order of their periods. The MC tasks are characterized by the same parameters as those in Equation (2); thus,  
\[M_{k}\equiv\Big{\{}T_{k},D_{k},L_{k_{\prime}}\big{\{}C_{k,L_{\prime}}\big{|}j \in 1,\ldots,l\big{\}},\big{\{}S_{k,L_{\prime}}\big{|}\ j\in 1,\ldots,l\big{\}}\Big{\}},\ \text{ where for any task }i, \tag{5}\]  
\(T_{i}\leq T_{k}\) for \(i<k\).  
**Definition 2**.: _The task set \(M\) is FENP schedulable in a mixed criticality system if, and only if, the task set \(M\) is FENP schedulable for each criticality level \(L_{j}\), where \(j\in 1,\ldots,l\)._  
**Definition 3**.: _The task set \(M\) is FENP schedulable in a mixed criticality system for criticality level \(L_{j}\) if all the tasks in the set \(M\) with criticality equal to or higher than \(L_{j}\) are FENP schedulable using the next feasibility test. Only the parameters for level \(L_{j}\) (\(C_{k,L_{j}}\) and \(S_{k,L_{j}}\)) are considered in this case._  
The feasibility tests are based on an execution mapping function, which is defined next.  
**Definition 4**.: _A fixed-execution mapping of task \(M_{k}\) over the period of task \(M_{i}\) is a function of the form:_  
\[\begin{array}{c}\Delta_{M_{i}/M_{k}}:\{0,\ 1,\ldots,\ T_{i}-1\}\to\{0,\ 1\}\\ \Delta_{M_{i}/M_{k}}(\tau)=\overset{\overbrace{\cup}\limits_{x=0}^{\tau}\cdot T _{k}-1}{\cup\limits_{x=0}^{\tau}}M_{k}(\tau+x\cdot T_{i})\end{array} \tag{6}\]  
_where \(\tau\) represents a discrete time function with values between 0 and \(T_{i}\), \(\text{GCD}(T_{i},T_{k})\) computes the greatest common divisor of the periods of tasks \(M_{i}\) and \(M_{k}\), and \(M_{k}(\tau+x\cdot T_{i})\) represents the execution function of \(M_{k}\):_  
\[M_{k}:N\to\{0,1\},\ M_{k}(\tau)=\ \sigma\ (t\ mod\ T_{k}-S_{k})-\ \sigma\ (t\ mod\ T_{k}-S_{k}-C_{k}) \tag{7}\]  
_where mod is the modulo operator and \(\sigma\) is the unity step function:_  
\[Z\to\{0,1\},\ \sigma=\left\{\begin{array}{c}1,x\geq 0,\\ 0,x<0.\end{array}\right. \tag{8}\]  
For a certain criticality level \(L_{j}\), Equation (7) becomes  
\[M_{k}:N\to\{0,1\},\ M_{k}(\tau)=\ \sigma\ \Big{(}t\ mod\ T_{k}-S_{k,L_{j}} \Big{)}-\ \sigma\ \Big{(}t\ mod\ T_{k}-S_{k,L_{j}}-C_{k,L_{j}}\Big{)}. \tag{9}\]  
Feasibility test: For a given criticality level \(L_{j}\), a subset \(M_{L_{j}}\) of tasks with criticality level \(L_{k}\geq L_{j}\) are schedulable if, and only if,  
\[\begin{array}{c}\forall M_{k}\in M_{L_{j}},M_{k}\equiv\Big{\{}T_{k},D_{k},L_ {k},C_{k,L_{j}},S_{k,L_{j}}\Big{\}},\\ \exists t_{q}\in\Big{\{}0,\ 1,\ldots,\ T_{k}-C_{k,L_{j}}\Big{\}}\ \text{so that}\ \cup_{\tau=t_{0}}^{t_{q}+C_{k,L_{j}}-1}\cup_{i=1}^{k-1}\Delta_{M_{k}/M_{i}( \tau)}=0\end{array} \tag{10}\]  
where \(t_{q}\) is a discrete time instant between 0 and the latest possible start time of task \(M_{k}\) and \(\Delta_{M_{i}/M_{k}(\tau)}\) is defined by Equation (6).