“doc” (Col. : Science Sup 17x24) — 2007/7/19 — 18:18 — page 189 — #199
i
i
i
i
i
i
i
i
4.1 Le modèle concurrent dataflow
189
Ordre causal
2
I
1
I
2
I
1
I
2
I
1
I
2
I
1
I
a
I
a
I
a
I
a
I
b
I
b
I
b
I
b
I
c
I
c
I
c
I
c
I
I
Quelques exécutions possibles
T2
T1
1
I
c
I
I 2
b
I
a
Figure 4.3 La relation entre l’ordre causal et les exécutions entrelacées.
choix s’appelle le non-déterminisme. Le non-déterminisme apparaît naturellement
quand il y a des états concurrents. Par exemple, dans la figure 4.3, après le premier
pas, qui fait toujours I a , il y a le choix entre I 1 ou I b pour le pas suivant.
Dans un modèle déclaratif concurrent, le non-déterminisme n’est pas visible pour le
programmeur.
1 C’est à cause de deux choses. Premièrement, les variables dataflow ne
peuvent être liées qu’à une valeur. Le non-déterminisme influence le moment précis
où chaque lien a lieu ; il n’influence pas le fait qu’il y a un lien. Deuxièmement, toute
opération qui a besoin de la valeur d’une variable n’a d’autre choix que d’attendre
jusqu’à ce que la variable soit liée. Si nous permettons des opérations qui pourraient
choisir d’attendre ou pas, le non-déterminisme deviendra visible.
En conséquence, un modèle déclaratif concurrent garde les bonnes propriétés du
modèle déclaratif. En plus, nous allons voir que le modèle concurrent enlève certaines
limitations du modèle déclaratif, mais pas toutes.
L’ordonnancement
Le choix du fil à exécuter à tout moment est fait par une partie du système qui s’appelle
l’ordonnanceur. À chaque pas d’exécution, l’ordonnanceur choisit un fil parmi tous
ceux qui sont prêts à s’exécuter. Nous disons qu’un fil est prêt, ou exécutable, si sa
première instruction a toutes les informations nécessaires pour exécuter au moins un
pas. Une fois qu’un fil est prêt, il reste prêt indéfiniment. Nous disons que la réduction
des fils est monotone. Un fil prêt peut être exécuté à tout moment.
1. S’il n’y a pas de tentatives de lier la même variable à des valeurs partielles incompatibles. Cela
s’appelle un échec d’unification parce que l’algorithme qui lie les variables s’appelle l’unification. En
général, l’échec d’unification est une conséquence d’une erreur de programmation.
© 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
189
Ordre causal
2
I
1
I
2
I
1
I
2
I
1
I
2
I
1
I
a
I
a
I
a
I
a
I
b
I
b
I
b
I
b
I
c
I
c
I
c
I
c
I
I
Quelques exécutions possibles
T2
T1
1
I
c
I
I 2
b
I
a
Figure 4.3 La relation entre l’ordre causal et les exécutions entrelacées.
choix s’appelle le non-déterminisme. Le non-déterminisme apparaît naturellement
quand il y a des états concurrents. Par exemple, dans la figure 4.3, après le premier
pas, qui fait toujours I a , il y a le choix entre I 1 ou I b pour le pas suivant.
Dans un modèle déclaratif concurrent, le non-déterminisme n’est pas visible pour le
programmeur.
1 C’est à cause de deux choses. Premièrement, les variables dataflow ne
peuvent être liées qu’à une valeur. Le non-déterminisme influence le moment précis
où chaque lien a lieu ; il n’influence pas le fait qu’il y a un lien. Deuxièmement, toute
opération qui a besoin de la valeur d’une variable n’a d’autre choix que d’attendre
jusqu’à ce que la variable soit liée. Si nous permettons des opérations qui pourraient
choisir d’attendre ou pas, le non-déterminisme deviendra visible.
En conséquence, un modèle déclaratif concurrent garde les bonnes propriétés du
modèle déclaratif. En plus, nous allons voir que le modèle concurrent enlève certaines
limitations du modèle déclaratif, mais pas toutes.
L’ordonnancement
Le choix du fil à exécuter à tout moment est fait par une partie du système qui s’appelle
l’ordonnanceur. À chaque pas d’exécution, l’ordonnanceur choisit un fil parmi tous
ceux qui sont prêts à s’exécuter. Nous disons qu’un fil est prêt, ou exécutable, si sa
première instruction a toutes les informations nécessaires pour exécuter au moins un
pas. Une fois qu’un fil est prêt, il reste prêt indéfiniment. Nous disons que la réduction
des fils est monotone. Un fil prêt peut être exécuté à tout moment.
1. S’il n’y a pas de tentatives de lier la même variable à des valeurs partielles incompatibles. Cela
s’appelle un échec d’unification parce que l’algorithme qui lie les variables s’appelle l’unification. En
général, l’échec d’unification est une conséquence d’une erreur de programmation.
© Dunod – La photocopie non autorisée est un délit