“doc” (Col. : Science Sup 17x24) — 2007/7/19 — 18:18 — page 21 — #31
i
i
i
i
i
i
i
i
1.14 Le non-déterminisme et le temps
21
peut être 1 ! Comment est-ce possible ? Essayez de comprendre pourquoi avant de
continuer.
6
Deuxième exécution:
C={NewCell 0}
C:=2
C:=1
C={NewCell 0}
C:=1
C:=2
temps
le contenu final de C est 1
le contenu final de C est 2
Première exécution:
Figure 1.4 Toutes les exécutions possibles du premier exemple non-déterministe.
L’entrelacement
Le contenu peut être 1 parce que l’exécution des fils est entrelacée. Chaque fil attend
son tour pour s’exécuter un peu. Il faut supposer que tous les entrelacements possibles peuvent arriver. Par exemple, prenez l’exécution montrée dans la figure 1.5. Les
variables I et J sont toutes les deux liées à 0. Ensuite, parce que I+1 et J+1 font tous
les deux 1, la cellule sera affectée à 1 deux fois. Le résultat final est que le contenu de
la cellule est 1.
Cet exemple est simple. Dans les programmes plus compliqués, le nombre d’entrelacements est beaucoup plus grand. Il faut écrire le programme pour qu’il soit
correct pour chaque entrelacement. Ce n’est pas une tâche facile. Dans l’histoire
des ordinateurs, un grand nombre de « bugs » célèbres et dangereux viennent du
fait que les concepteurs n’avaient pas réalisé la vraie difficulté. L’appareil de radiothérapie Therac-25 en est un exemple connu. À cause des erreurs de programmation
concurrente, l’appareil émettait parfois des doses de radiation des milliers de fois plus
grandes que la normale, ce qui provoquait chez le patient une blessure grave ou même
mortelle [60].
Il y a donc une première leçon à retenir pour les programmes qui utilisent l’état
et la concurrence : si possible, ne les utilisez pas ensemble ! Il apparaît que souvent
il n’est pas nécessaire d’utiliser les deux ensemble. Quand un programme a besoin
des deux, il peut presque toujours être conçu pour limiter leur interaction à une toute
petite partie du programme.
6. Pour faciliter votre raisonnement, l’exemple est codé pour rendre les variables intermédiaires visibles.
Nous aurions pu écrire thread C:=@C+1 end, qui a le même comportement mais sans montrer
de variable intermédiaire !
© Dunod – La photocopie non autorisée est un délit
i
i
i
i
i
i
i
i
1.14 Le non-déterminisme et le temps
21
peut être 1 ! Comment est-ce possible ? Essayez de comprendre pourquoi avant de
continuer.
6
Deuxième exécution:
C={NewCell 0}
C:=2
C:=1
C={NewCell 0}
C:=1
C:=2
temps
le contenu final de C est 1
le contenu final de C est 2
Première exécution:
Figure 1.4 Toutes les exécutions possibles du premier exemple non-déterministe.
L’entrelacement
Le contenu peut être 1 parce que l’exécution des fils est entrelacée. Chaque fil attend
son tour pour s’exécuter un peu. Il faut supposer que tous les entrelacements possibles peuvent arriver. Par exemple, prenez l’exécution montrée dans la figure 1.5. Les
variables I et J sont toutes les deux liées à 0. Ensuite, parce que I+1 et J+1 font tous
les deux 1, la cellule sera affectée à 1 deux fois. Le résultat final est que le contenu de
la cellule est 1.
Cet exemple est simple. Dans les programmes plus compliqués, le nombre d’entrelacements est beaucoup plus grand. Il faut écrire le programme pour qu’il soit
correct pour chaque entrelacement. Ce n’est pas une tâche facile. Dans l’histoire
des ordinateurs, un grand nombre de « bugs » célèbres et dangereux viennent du
fait que les concepteurs n’avaient pas réalisé la vraie difficulté. L’appareil de radiothérapie Therac-25 en est un exemple connu. À cause des erreurs de programmation
concurrente, l’appareil émettait parfois des doses de radiation des milliers de fois plus
grandes que la normale, ce qui provoquait chez le patient une blessure grave ou même
mortelle [60].
Il y a donc une première leçon à retenir pour les programmes qui utilisent l’état
et la concurrence : si possible, ne les utilisez pas ensemble ! Il apparaît que souvent
il n’est pas nécessaire d’utiliser les deux ensemble. Quand un programme a besoin
des deux, il peut presque toujours être conçu pour limiter leur interaction à une toute
petite partie du programme.
6. Pour faciliter votre raisonnement, l’exemple est codé pour rendre les variables intermédiaires visibles.
Nous aurions pu écrire thread C:=@C+1 end, qui a le même comportement mais sans montrer
de variable intermédiaire !
© Dunod – La photocopie non autorisée est un délit