Trace d'exécution

La trace d'exécution est un graphe orienté dans lequel pour chaque tâche $T_{i}$, chacune des $n_{i}$ opérations est un sommet. Dans ce graphe figurent trois types d'arcs :

1. Contraintes de séquentialité
   
   Une tâche $T_{i}$ ne peut exécuter $o_{i}^{p}$ ($p\not=1$) que si $o_{i}^{p-1}$ a déjà été exécutée. On notera $\mathcal{E}_{1}$ l'ensemble des arcs qui, pour tout $i$ et pour tout $p\not=1$, relie $o_{i}^{p-1}$ à $o_{i}^{p}$. On remarquera au passage qu'une variation de la taille des buffers n'influe en rien sur le contenu de $\mathcal{E}_{1}$.
   
2. Contraintes de buffer vide
   
   Lorsqu'une opération de lecture $o_{i}^{p}$ est demandée par $T_{i}$ sur un buffer $b$, elle ne pourra s'effectuer que si $b$ n'est pas vide. Par conséquent, la $p$-ème opération de lecture effectuée par une tâche $T_{j}$ sur le buffer $b = (T_{i}, T_{j})$ ne pourra être effectuée que si la $p$-ème opération d'écriture de $T_{i}$ a déjà été effectuée. Nous noterons $\mathcal{E}_{2}$ l'ensemble des arcs qui pour tout buffer $b = (T_{i}, T_{j})$, et pour tout $p$, relie la $p$-ème opération d'écriture sur $b$ effectuée par $T_{i}$ à la $p$-ème opération de lecture sur $b$ effectuée par $T_{j}$. Remarquons ici aussi que toute variation des dimensions des buffers laisse l'ensemble $\mathcal{E}_{2}$ inchangé.
   
3. Contraintes de buffer plein
   
   Lorsqu'une opération d'écriture $o_{i}^{p}$ est demandée sur un buffer $b$, elle ne pourra s'effectuer que si $b$ n'est pas plein. Il faut donc attendre qu'une opération de lecture libère un emplacement dans $b$. Plus formellement, pour qu'une tâche $T_{i}$ puisse effectuer sa $p$-ème opération d'écriture sur le buffer $b = (T_{i}, T_{j})$, il faudra avant que $T_{j}$ ait effectué sa $(p-\Delta(b)$)-ème opération de lecture sur $b$. Nous noterons $\mathcal{E}_{3}$ l'ensemble de ces arcs. Remarquons que cette fois-ci, le contenu de $\mathcal{E}_{3}$ dépend directement des dimensions $\Delta(b) (b \in \mathcal{B})$ des buffers.

Nous obtenons un graphe $\mathcal{G=(V, E)}$ où

$$\left\lbrace\begin{array}{l} \mathcal{V = O} \\ \mathcal{E... ... \cup \mathcal{E}_{2} \cup \mathcal{E}_{3} \end{array}\right.$$

Par exemple, voici une instance du problème :

$\left\lbrace\begin{array}{l} \mathcal{T} = \lbrace T_{1}, T_{2} \rbrace \\ ... ...2}^{4}) = b_{2}, b(o_{2}^{5}) = b_{2}, b(o_{2}^{6}) = b_{3}) \end{array}\right.$

Figure 1.4: Contraintes de séquentialité

La trace $\mathcal{G = (V}, \mathcal{E}_1)$ lui correspondant est décrite figure 1.4. A coté de chaque sommet/opération $o_{i}^{p}$ est indiqué le buffer $b(o_{i}^{p})$ sur lequel elle s'exécute. Les arcs sont les contraintes de séquentialité des opérations c'est-à-dire sur l'ordre dans lequel ces dernières doivent s'effectuer. Il suffit donc d'exécuter les opérations $o_{i}^{p}$ de chaque tâche dans l'ordre induit par $p$ pour respecter ces contraintes.

Figure 1.5: Contraintes de buffers vides

La trace $\mathcal{G = (V}, \mathcal{E}_1 \cup \mathcal{E}_2)$ lui correspondant est décrite figure 1.5. On remarque dans la façon dont sont tracés les arcs qu'à chaque opération de lecture peut être associée une opération d'écriture. Considérons par exemple l'opération $o_{1}^{2}$. Comme $b(o_{1}^{2})=b_{3}$, alors cette opération s'exécute sur un buffer appartenant à $\mathcal{B}_{21}$, du fait qu'elle est exécutée par $T_{1}$, nous avons affaire à une opération de lecture. Or la lecture d'une donnée dans un buffer ne peut se faire que si cette donnée a été préalablement écrite dans ce même buffer. Comme $o_{1}^{2}$ est la première opération de lecture sur $b_{3}$, il faut que la première opération d'écriture sur $b_{3}$ ait été effectuée par $T_{2}$, donc que $o_{2}^{1}$ ait déjà été exécutée. D'où la contrainte de précédence liant $o_{2}^{1}$ à $o_{1}^{2}$.

Figure 1.6: Rappel du Graphe de Kahn[1]

Figure 1.7: Contraintes de buffers pleins

En posant $\Delta (b_{1})=1$, $\Delta (b_{2})=1$, $\Delta (b_{3})=1$, on obtient la trace $\mathcal{G = (V}, \mathcal{E}_1 \cup \mathcal{E}_2 \cup \mathcal{E}_3)$ lui correspondant figure 1.7. Ici sont mentionnées les contraintes dites de buffers pleins. Cela signifie qu'une opération d'écriture dans un buffer ne pourra être effectuée que si ce buffer n'est pas saturé. Prenons par exemple l'opération $o_{1}^{4}$. Comme $b(o_{1}^{4})=b_{2}$, et que $b_{2} \in \mathcal{B}_{12}$, alors $o_{1}^{4}$ est une opération d'écriture. Comme $\Delta (b_{2})=1$, $b_{3}$ ne peut pas contenir plus d'une donnée à la fois. Par conséquent, $o_{1}^{4}$ ne pourra être effectuée que lorsque la donnée qui a été écrite dans $b_{2}$ par $T_{1}$ lors de l'exécution de $o_{1}^{3}$ aura été lue. Comme $o_{2}^{4}$ est l'opération de lecture qui libérera une place dans $b_{2}$, il faudra que son exécution précède celle de $o_{1}^{4}$. C'est pour cette raison qu'il existe un arc $(o_{2}^{4}, o_{1}^{4})$

Un circuit dans la trace d'exécution (exemple figure 1.8) correspond à un blocage du système. Un des algorithmes mis au point pour résoudre ce problème se base sur la recherche de ces circuits.

Figure 1.8: Circuit à l'origine d'un inter-blocage