“doc” (Col. : Science Sup 17x24) — 2007/7/19 — 18:18 — page 191 — #201
i
i
i
i
i
i
i
i
4.1 Le modèle concurrent dataflow
191
La mémoire initiale est vide (aucune variable, s = f) et l’état d’exécution
initial a une pile sémantique qui contient une instruction sémantique (s, f).
La seule différence avec le chapitre 2 est que la pile sémantique est dans un
multi-ensemble.
– À chaque pas, une pile sémantique exécutable ST est sélectionnée de MST, ce
qui laisse MST
. Nous pouvons dire MST = {ST } } MST
. (L’opérateur
désigne l’union de multi-ensembles.) Un pas d’exécution est fait dans ST selon
la sémantique du chapitre 2, ce qui donne
(ST, s) → (ST
, s
)
Le pas d’exécution pour le calcul complet est alors
({ST} } MST
, s) → ({ST
} } MST
, s
)
La sémantique est entrelacée parce qu’il y a une séquence globale de pas d’exécution. Chaque fil attend son tour pour avancer.
– Le choix de la pile ST à sélectionner est fait par l’ordonnanceur selon un ensemble
de règles précises qui s’appelle l’algorithme d’ordonnancement. Cet algorithme s’assure que les propriétés désirées, comme l’équité, sont satisfaites pour
tout calcul. Un ordonnanceur pratique doit prendre en compte bien plus que
l’équité. La section 4.2.4 rentre dans les détails de ces propriétés pour l’ordonnanceur de Mozart.
– S’il n’y a aucune pile sémantique exécutable dans MST, alors le calcul ne peut
pas continuer :
• Si toutes les ST dans MST sont terminées, nous dirons que le calcul est terminé.
• S’il existe au moins une ST suspendue dans MST qui ne peut pas être récupérée
(voir plus loin), alors nous dirons que le calcul est suspendu.
L’instruction thread
La sémantique de l’instruction thread est définie en termes de modifications du
multi-ensemble MST. Une instruction thread ne bloque jamais. Si la ST sélectionnée a la forme [(thread s end, E)] + ST
, le nouveau multi-ensemble sera
{[(s, E)]} } {ST
} } MST
. En d’autres termes, nous ajouterons une nouvelle pile
sémantique [(s, E)] qui correspond au nouveau fil. La figure 4.4 en donne une illustration. Nous résumons cette opération dans le pas d’exécution suivant :
({[(thread s end, E)] + ST
} } MST
, s) → ({[(s, E)]} } {ST
} } MST
, s)
© Dunod – La photocopie non autorisée est un délit
i
i
i
i
i
i
i
i
4.1 Le modèle concurrent dataflow
191
La mémoire initiale est vide (aucune variable, s = f) et l’état d’exécution
initial a une pile sémantique qui contient une instruction sémantique (s, f).
La seule différence avec le chapitre 2 est que la pile sémantique est dans un
multi-ensemble.
– À chaque pas, une pile sémantique exécutable ST est sélectionnée de MST, ce
qui laisse MST
. Nous pouvons dire MST = {ST } } MST
. (L’opérateur
désigne l’union de multi-ensembles.) Un pas d’exécution est fait dans ST selon
la sémantique du chapitre 2, ce qui donne
(ST, s) → (ST
, s
)
Le pas d’exécution pour le calcul complet est alors
({ST} } MST
, s) → ({ST
} } MST
, s
)
La sémantique est entrelacée parce qu’il y a une séquence globale de pas d’exécution. Chaque fil attend son tour pour avancer.
– Le choix de la pile ST à sélectionner est fait par l’ordonnanceur selon un ensemble
de règles précises qui s’appelle l’algorithme d’ordonnancement. Cet algorithme s’assure que les propriétés désirées, comme l’équité, sont satisfaites pour
tout calcul. Un ordonnanceur pratique doit prendre en compte bien plus que
l’équité. La section 4.2.4 rentre dans les détails de ces propriétés pour l’ordonnanceur de Mozart.
– S’il n’y a aucune pile sémantique exécutable dans MST, alors le calcul ne peut
pas continuer :
• Si toutes les ST dans MST sont terminées, nous dirons que le calcul est terminé.
• S’il existe au moins une ST suspendue dans MST qui ne peut pas être récupérée
(voir plus loin), alors nous dirons que le calcul est suspendu.
L’instruction thread
La sémantique de l’instruction thread est définie en termes de modifications du
multi-ensemble MST. Une instruction thread ne bloque jamais. Si la ST sélectionnée a la forme [(thread s end, E)] + ST
, le nouveau multi-ensemble sera
{[(s, E)]} } {ST
} } MST
. En d’autres termes, nous ajouterons une nouvelle pile
sémantique [(s, E)] qui correspond au nouveau fil. La figure 4.4 en donne une illustration. Nous résumons cette opération dans le pas d’exécution suivant :
({[(thread s end, E)] + ST
} } MST
, s) → ({[(s, E)]} } {ST
} } MST
, s)
© Dunod – La photocopie non autorisée est un délit