“doc” (Col. : Science Sup 17x24) — 2007/7/19 — 18:18 — page 190 — #200
i
i
i
i
i
i
i
i
190
4
• La programmation concurrente dataflow
Un fil qui n’est pas prêt est dit suspendu. Sa première instruction ne peut pas
continuer parce qu’elle n’a pas toutes les informations dont elle a besoin. Nous disons
que la première instruction est bloquée. Le blocage est un concept important que nous
verrons à d’autres occasions.
Nous disons que le système est équitable s’il ne laisse pas un fil prêt « s’affamer » ;
c’est-à-dire, tous les fils prêts s’exécuteront tôt ou tard. C’est une propriété importante
pour que le comportement du programme soit prévisible et pour simplifier le raisonnement sur les programmes. Elle est apparentée à la modularité : l’équité implique que
l’exécution d’un fil ne dépende pas de celle d’aucun autre fil. Nous supposons que les
fils sont ordonnancés équitablement.
4.1.2 La sémantique des fils
Nous étendons la machine abstraite de la section 2.4 en lui permettant de s’exécuter
avec plusieurs piles sémantiques au lieu d’une seule. Chaque pile sémantique correspond au concept intuitif de « fil ». Toutes les piles sémantiques accèdent à la même
mémoire. Les fils communiquent entre eux par cette mémoire partagée.
Les concepts
Nous gardons les concepts de mémoire à affectation unique s, environnement E,
instruction sémantique (s, E) et pile sémantique ST. Nous étendons les concepts
d’état d’exécution et calcul pour prendre en compte plusieurs piles sémantiques :
– Un état d’exécution est une paire (MST, s) où MST est un multi-ensemble de piles
sémantiques et s est une mémoire à affectation unique. Un multi-ensemble est un
ensemble dans lequel le même élément peut apparaître plusieurs fois. MST doit
être un multi-ensemble parce que nous pouvons avoir deux piles sémantiques
différentes avec les mêmes contenus, par exemple deux fils qui exécutent les
mêmes instructions.
– Un calcul est une séquence d’états d’exécution qui commence avec un état initial :
(MST 0 , s 0 ) → (MST 1 , s 1 ) → (MST 2 , s 2 ) → · · · .
L’exécution d’un programme
Comme avant, un programme est une instruction s. Voici comment l’exécuter :
– L’état d’exécution initial est
({ [
instruction
(s, f) ]
pile
}
multi-ensemble
, f)
i
i
i
i
i
i
i
i
190
4
• La programmation concurrente dataflow
Un fil qui n’est pas prêt est dit suspendu. Sa première instruction ne peut pas
continuer parce qu’elle n’a pas toutes les informations dont elle a besoin. Nous disons
que la première instruction est bloquée. Le blocage est un concept important que nous
verrons à d’autres occasions.
Nous disons que le système est équitable s’il ne laisse pas un fil prêt « s’affamer » ;
c’est-à-dire, tous les fils prêts s’exécuteront tôt ou tard. C’est une propriété importante
pour que le comportement du programme soit prévisible et pour simplifier le raisonnement sur les programmes. Elle est apparentée à la modularité : l’équité implique que
l’exécution d’un fil ne dépende pas de celle d’aucun autre fil. Nous supposons que les
fils sont ordonnancés équitablement.
4.1.2 La sémantique des fils
Nous étendons la machine abstraite de la section 2.4 en lui permettant de s’exécuter
avec plusieurs piles sémantiques au lieu d’une seule. Chaque pile sémantique correspond au concept intuitif de « fil ». Toutes les piles sémantiques accèdent à la même
mémoire. Les fils communiquent entre eux par cette mémoire partagée.
Les concepts
Nous gardons les concepts de mémoire à affectation unique s, environnement E,
instruction sémantique (s, E) et pile sémantique ST. Nous étendons les concepts
d’état d’exécution et calcul pour prendre en compte plusieurs piles sémantiques :
– Un état d’exécution est une paire (MST, s) où MST est un multi-ensemble de piles
sémantiques et s est une mémoire à affectation unique. Un multi-ensemble est un
ensemble dans lequel le même élément peut apparaître plusieurs fois. MST doit
être un multi-ensemble parce que nous pouvons avoir deux piles sémantiques
différentes avec les mêmes contenus, par exemple deux fils qui exécutent les
mêmes instructions.
– Un calcul est une séquence d’états d’exécution qui commence avec un état initial :
(MST 0 , s 0 ) → (MST 1 , s 1 ) → (MST 2 , s 2 ) → · · · .
L’exécution d’un programme
Comme avant, un programme est une instruction s. Voici comment l’exécuter :
– L’état d’exécution initial est
({ [
instruction
(s, f) ]
pile
}
multi-ensemble
, f)