“doc” (Col. : Science Sup 17x24) — 2007/7/19 — 18:18 — page 187 — #197
i
i
i
i
i
i
i
i
4.1 Le modèle concurrent dataflow
187
s : :=
skip
Instruction vide
| |s 1 s 2
Séquence d’instructions
| local x in s end
Création de variable
| |x 1 =x 2
Lien variable-variable
| |x=v
Création de valeur
| if x then s 1 else s 2 end Instruction conditionnelle
| case x of pattern
Correspondance de formes
then s 1 else s 2 end
| {x y 1 · · · ·y n }
Application de procédure
| thread s end
Création de fil
Tableau 4.1 Le langage noyau concurrent dataflow.
L’entrelacement
Réfléchissons un instant pour comprendre exactement ce que veut dire « en même
temps ». Il y a deux façons de voir ce qui se passe ; le point de vue langage et le point
de vue implémentation :
– Le point de vue langage est la sémantique du langage telle qu’elle est vue par le
programmeur. De ce point de vue, l’hypothèse la plus simple est de laisser les fils
faire une exécution entrelacée ; il y a une séquence globale de pas d’exécution
et les fils s’exécutent à tour de rôle : chaque fil attend son tour pour exécuter
quelques pas et passe ensuite le contrôle au suivant. Les pas d’exécution ne se
chevauchent pas ; nous pouvons dire que chaque pas d’exécution est atomique.
Le raisonnement sur les programmes est donc simplifié.
– Le point de vue implémentation est l’implémentation des fils sur une machine
réelle. Si le système est implémenté sur un seul processeur, l’implémentation fera
de l’entrelacement aussi. Mais le système pourrait être implémenté sur plusieurs
processeurs, ce qui permettrait à des fils de faire des pas simultanément. Le
parallélisme ainsi obtenu peut améliorer la performance.
Nous utilisons la sémantique d’entrelacement partout. On peut démontrer qu’avec
toute exécution parallèle, il existe au moins un entrelacement qui est équivalent pour
l’observation. Si nous observons la mémoire pendant l’exécution, nous pourrons
toujours trouver une exécution entrelacée qui donne la même évolution de la mémoire.
L’ordre causal
La différence entre les exécutions séquentielle et concurrente peut être comprise en
termes d’un ordre défini entre les états d’exécution d’un programme :
© 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
187
s : :=
skip
Instruction vide
| |s 1 s 2
Séquence d’instructions
| local x in s end
Création de variable
| |x 1 =x 2
Lien variable-variable
| |x=v
Création de valeur
| if x then s 1 else s 2 end Instruction conditionnelle
| case x of pattern
Correspondance de formes
then s 1 else s 2 end
| {x y 1 · · · ·y n }
Application de procédure
| thread s end
Création de fil
Tableau 4.1 Le langage noyau concurrent dataflow.
L’entrelacement
Réfléchissons un instant pour comprendre exactement ce que veut dire « en même
temps ». Il y a deux façons de voir ce qui se passe ; le point de vue langage et le point
de vue implémentation :
– Le point de vue langage est la sémantique du langage telle qu’elle est vue par le
programmeur. De ce point de vue, l’hypothèse la plus simple est de laisser les fils
faire une exécution entrelacée ; il y a une séquence globale de pas d’exécution
et les fils s’exécutent à tour de rôle : chaque fil attend son tour pour exécuter
quelques pas et passe ensuite le contrôle au suivant. Les pas d’exécution ne se
chevauchent pas ; nous pouvons dire que chaque pas d’exécution est atomique.
Le raisonnement sur les programmes est donc simplifié.
– Le point de vue implémentation est l’implémentation des fils sur une machine
réelle. Si le système est implémenté sur un seul processeur, l’implémentation fera
de l’entrelacement aussi. Mais le système pourrait être implémenté sur plusieurs
processeurs, ce qui permettrait à des fils de faire des pas simultanément. Le
parallélisme ainsi obtenu peut améliorer la performance.
Nous utilisons la sémantique d’entrelacement partout. On peut démontrer qu’avec
toute exécution parallèle, il existe au moins un entrelacement qui est équivalent pour
l’observation. Si nous observons la mémoire pendant l’exécution, nous pourrons
toujours trouver une exécution entrelacée qui donne la même évolution de la mémoire.
L’ordre causal
La différence entre les exécutions séquentielle et concurrente peut être comprise en
termes d’un ordre défini entre les états d’exécution d’un programme :
© Dunod – La photocopie non autorisée est un délit