# Schedulability Analysis in Fixed-Priority Real-Time Multicore Systems with Contention
## 4 Interference-Aware Schedulability Analysis for Fixed Priorities
### Interference-Aware Schedulability Analysis for Deadline Monotonic Scheduling
#### 4.2.1 Previous Definitions  
Below, let us derive an upper bound of the response time of all activations of all tasks allocated to a multicore system with contention. For the subsequent analysis, we need some definitions. Definition 1: Let \(\overrightarrow{v_{j\to i}}\) be the activation pattern from a broadcasting task \(\tau_{j}\) to a receiving task \(\tau_{i}\)[9]. We require this information, represented as an array, to compute the interference that a broadcasting task \(\tau_{j}\) can induce on a receiving task \(\tau_{i}\). This array denotes the number of activations of \(\tau_{j}\) that occur within an activation of \(\tau_{i}\). Array \(\overrightarrow{v_{j\to i}}\) is calculated as a relation of periods between broadcasting and receiving tasks. This expression is valid for implicit deadline task sets. However, if this array is used to calculate the interference between tasks when \(D_{i}\leq T_{i}\), the interference obtained is highly overestimated. The reason is that there are activations of a task that fall within an activation of another that do not provoke interference because the deadline is not taken into account. Then, let us propose an improved definition of the activation pattern for constrained deadlines, noted as \(\overrightarrow{v_{j\to i}^{\ast}}\). Definition 2: Let \(\overrightarrow{v_{j\to i}^{\ast}}\) be the improved activation pattern from a broadcasting task \(\tau_{j}\) to a receiving task \(\tau_{j}\). Figure 2: WCRT of tasks in multicore systems with contention. This definition is similar to the one presented in [9] but considers the deadlines to count the maximum number of overlaps among activations. In this sense, if the broadcasting task is released when the deadline of the receiving task has expired and has not yet been released again (and vice versa), this overlap is not counted. Note that if \(\tau_{i}\) is not a receiving task, \(\overrightarrow{v_{j\to i}^{*}}[a]=0\quad\forall\tau_{j}\in\tau,\forall a\ \in N_{i}\). We use an example to show the differences of both parameters. Let us consider a system with two tasks, \(\tau^{\prime}=[\tau^{\prime}_{0},\tau^{\prime}_{1}]\), with \(\tau^{\prime}_{0}=(1,2,3,1)\) and \(\tau^{\prime}_{1}=(1,6,7,1)\), allocated to a dual-core platform. \(\tau^{\prime}_{0}\) is allocated to core \(M^{\prime}_{0}\), and \(\tau^{\prime}_{1}\), to \(M^{\prime}_{1}\) (Table 2). For simplicity, computation times are not shown. As seen in Figure 3a, \(\overrightarrow{v_{1\to 0}^{*}}=[1,1,2,1,2,1,1]\) from [9]. Equivalently, \(\overrightarrow{v_{0\to 1^{\prime}}}=[3,3,3]\). However, from Figure 3b, \(\overrightarrow{v_{1\to 0}^{*}}=[1,1,1,1,1,1]\) and \(\overrightarrow{v_{0\to 1^{\prime}}^{*}}=[2,3,2]\). Then, \(\overrightarrow{v_{0\to 1^{\prime}}}[2]=2\) and \(\overrightarrow{v_{0\to 1^{\prime}}^{*}}[2]=1\). This difference is due to the fact that first activation of \(\tau^{\prime}_{1}\) does not overlap with the third activation of \(\tau^{\prime}_{0}\) (considering deadlines), as \(D_{1}\) just expires when \(\tau^{\prime}_{0}\) is released. However, as \(\overrightarrow{v_{1^{\prime}\to 0^{\prime}}}\) does not consider deadlines but periods, this overlap is counted. The next theorem proves that \(\overrightarrow{v_{j\to i}^{*}}\) can be used to calculate an upper bound of interference. Theorem 3.1: _The maximum number of activations of broadcasting task \(\tau_{j}\) that fall within the \(a^{th}\) activation of \(\tau_{i}\) and may provoke interference is_  
\[\overrightarrow{v_{j\to i}^{*}}[a]=K+\sum_{t=\overline{t}_{j}+1}^{a \overline{t}_{j}+D)-1}g(t) \tag{4}\]_where_  
\[K= \begin{cases}1&\text{If }aT_{i}\in[nT_{j},nT_{j}+D_{j})\ \forall n\in N_{j}\\ 0&\text{Elsewhere}\end{cases}  \tag{5}\]  
_and_  
\[g(t)= \begin{cases}1&\text{If }t-T_{j}\left|\frac{t}{T_{j}}\right|=0\\ 0&\text{Elsewhere}\end{cases}  \tag{6}\]  
Proof. : Let us suppose that any \(a^{th}\) activation of \(\tau_{i}\) does not fall in the interval defined as \([nT_{j},nT_{j}+D_{j})\). Then, \(nT_{j}+D_{j}\leq a^{\prime}T_{i}<nT_{j}\).