“doc” (Col. : Science Sup 17x24) — 2007/7/19 — 18:18 — page 212 — #222
i
i
i
i
i
i
i
i
212
4
• La programmation concurrente dataflow
– Le préprocesseur transforme les programmes à état en programmes déclaratifs
avec un état enfilé, qui sont inefficaces à cause de tous les arguments supplémentaires.
Il faut donc faire très attention à bien séparer les différents niveaux d’abstraction.
4.4.2 Le non-déterminisme
Le modèle déclaratif concurrent apparaît assez puissant pour faire des programmes
concurrents. Par exemple, nous pouvons facilement construire un simulateur pour les
circuits digitaux (voir [97]). Mais malgré cette puissance apparente, le modèle a une
limitation qui le handicape fortement pour beaucoup d’applications concurrentes : il
se comporte toujours de façon déterministe. Si un programme a un non-déterminisme
observable, il ne sera pas déclaratif. Cette limitation est apparentée à la modularité : pour des composants qui sont vraiment indépendants, chacun se comporte de
façon non-déterministe par rapport à l’autre. Pour montrer que ce n’est pas purement
une limitation théorique, nous donnons deux exemples réalistes : une application
client-serveur et une application d’affichage vidéo.
La limitation peut être enlevée par l’ajout d’une opération non-déterministe au
modèle. Le modèle étendu n’est plus déclaratif. Il y a beaucoup d’opérations nondéterministes que l’on pourrait ajouter. Voici un résumé des possibilités les plus
courantes :
– Une première solution est d’ajouter une opération d’attente non-déterministe,
comme la fonction {WaitTwo X Y} qui attend jusqu’à ce que X ou Y soit
déterminée, et qui pourra renvoyer 1 si X est déterminée et 2 si Y est déterminée.
Si les deux sont déterminées, la fonction renverra une des deux valeurs. Sa
définition est donnée dans le fichier de suppléments sur le site Web du livre.
WaitTwo est pertinente pour l’application client/serveur.
– Une deuxième solution est d’ajouter la fonction booléenne {IsDet X}, qui
teste si une variable dataflow X est déterminée ou pas et renvoie tout de suite
true ou false sans attendre. Avec cette opération on peut utiliser les variables
dataflow comme une forme faible d’état. IsDet est pertinente pour l’application
d’affichage vidéo.
– Une troisième solution est d’ajouter l’état explicite au modèle, par exemple des
cellules (variables affectables) ou des ports (canaux de communication).
Quelles sont les relations entre les trois solutions ? WaitTwo peut être programmée
dans le modèle déclaratif concurrent avec l’état explicite. L’état explicite peut être
programmé avec IsDet mais sans garder la complexité temporelle. Il semble donc
que le modèle le plus expressif a besoin uniquement d’état explicite et IsDet.
i
i
i
i
i
i
i
i
212
4
• La programmation concurrente dataflow
– Le préprocesseur transforme les programmes à état en programmes déclaratifs
avec un état enfilé, qui sont inefficaces à cause de tous les arguments supplémentaires.
Il faut donc faire très attention à bien séparer les différents niveaux d’abstraction.
4.4.2 Le non-déterminisme
Le modèle déclaratif concurrent apparaît assez puissant pour faire des programmes
concurrents. Par exemple, nous pouvons facilement construire un simulateur pour les
circuits digitaux (voir [97]). Mais malgré cette puissance apparente, le modèle a une
limitation qui le handicape fortement pour beaucoup d’applications concurrentes : il
se comporte toujours de façon déterministe. Si un programme a un non-déterminisme
observable, il ne sera pas déclaratif. Cette limitation est apparentée à la modularité : pour des composants qui sont vraiment indépendants, chacun se comporte de
façon non-déterministe par rapport à l’autre. Pour montrer que ce n’est pas purement
une limitation théorique, nous donnons deux exemples réalistes : une application
client-serveur et une application d’affichage vidéo.
La limitation peut être enlevée par l’ajout d’une opération non-déterministe au
modèle. Le modèle étendu n’est plus déclaratif. Il y a beaucoup d’opérations nondéterministes que l’on pourrait ajouter. Voici un résumé des possibilités les plus
courantes :
– Une première solution est d’ajouter une opération d’attente non-déterministe,
comme la fonction {WaitTwo X Y} qui attend jusqu’à ce que X ou Y soit
déterminée, et qui pourra renvoyer 1 si X est déterminée et 2 si Y est déterminée.
Si les deux sont déterminées, la fonction renverra une des deux valeurs. Sa
définition est donnée dans le fichier de suppléments sur le site Web du livre.
WaitTwo est pertinente pour l’application client/serveur.
– Une deuxième solution est d’ajouter la fonction booléenne {IsDet X}, qui
teste si une variable dataflow X est déterminée ou pas et renvoie tout de suite
true ou false sans attendre. Avec cette opération on peut utiliser les variables
dataflow comme une forme faible d’état. IsDet est pertinente pour l’application
d’affichage vidéo.
– Une troisième solution est d’ajouter l’état explicite au modèle, par exemple des
cellules (variables affectables) ou des ports (canaux de communication).
Quelles sont les relations entre les trois solutions ? WaitTwo peut être programmée
dans le modèle déclaratif concurrent avec l’état explicite. L’état explicite peut être
programmé avec IsDet mais sans garder la complexité temporelle. Il semble donc
que le modèle le plus expressif a besoin uniquement d’état explicite et IsDet.