“doc” (Col. : Science Sup 17x24) — 2007/7/19 — 18:18 — page 20 — #30
i
i
i
i
i
i
i
i
20
1
• Introduction aux concepts de programmation
quoi la nouvelle classe est différente. Par exemple, supposons que nous ayons une
classe compteur avec une seule méthode, Bump. Nous pouvons définir une nouvelle
classe qui prend la première classe et ajoute une deuxième méthode Read. On dit
que la nouvelle classe hérite de l’ancienne. L’héritage est un concept puissant pour la
structuration des programmes. Le chapitre 6 étudie la programmation orientée objet et
montre comment programmer avec l’héritage.
1.14 LE NON-DÉTERMINISME ET LE TEMPS
Nous avons vu comment ajouter la concurrence et l’état explicite à un programme, mais
de façon séparée. Que se passe-t-il quand un programme utilise les deux ensemble ?
Nous constatons que les utiliser ensemble est difficile, car le même programme peut
donner des résultats différents d’une exécution à une autre puisque l’ordre dans lequel
les fils utilisent l’état peut changer d’une exécution à une autre. Cette variabilité
s’appelle le non-déterminisme. Le non-déterminisme existe car nous ne connaissons
pas le temps exact de l’exécution de chaque opération. Si nous pouvions connaître
ce temps, il n’y aurait pas de non-déterminisme. Mais nous ne pouvons le connaître,
simplement parce que les fils sont indépendants. Chaque fil ne peut donc pas connaître
quelles sont les instructions exécutées par les autres fils à un moment donné.
Le non-déterminisme en soi n’est pas un problème ; nous l’avons déjà avec la
concurrence. Les difficultés apparaîtront seulement si le non-déterminisme devient
visible dans le programme, c’est-à-dire s’il devient observable. Un non-déterminisme
observable est parfois appelé une course (« race condition »). En voici un exemple
simple :
declare
C={NewCell 0}
thread C:=1 end
thread C:=2 end
Quel est le contenu de C après l’exécution de ce programme ? La figure 1.4 montre
deux exécutions possibles de ce programme. Selon l’exécution qui est faite, le contenu
final de la cellule peut être 1 ou 2. Le problème est que nous ne pouvons pas prévoir
ce qui arrivera. C’est un exemple de non-déterminisme observable. Le comportement
peut devenir encore plus compliqué. Par exemple, utilisons une cellule pour stocker
un compteur qui peut être incrémenté par plusieurs fils :
declare
C={NewCell 0}
thread I in I=@C C:=I+1 end
thread J in J=@C C:=J+1 end
Quel est le contenu de C après l’exécution de ce programme ? Il semble que chaque
fil ajoute 1 au contenu, ce qui fait 2 à la fin. Mais il y a une surprise : le contenu final
i
i
i
i
i
i
i
i
20
1
• Introduction aux concepts de programmation
quoi la nouvelle classe est différente. Par exemple, supposons que nous ayons une
classe compteur avec une seule méthode, Bump. Nous pouvons définir une nouvelle
classe qui prend la première classe et ajoute une deuxième méthode Read. On dit
que la nouvelle classe hérite de l’ancienne. L’héritage est un concept puissant pour la
structuration des programmes. Le chapitre 6 étudie la programmation orientée objet et
montre comment programmer avec l’héritage.
1.14 LE NON-DÉTERMINISME ET LE TEMPS
Nous avons vu comment ajouter la concurrence et l’état explicite à un programme, mais
de façon séparée. Que se passe-t-il quand un programme utilise les deux ensemble ?
Nous constatons que les utiliser ensemble est difficile, car le même programme peut
donner des résultats différents d’une exécution à une autre puisque l’ordre dans lequel
les fils utilisent l’état peut changer d’une exécution à une autre. Cette variabilité
s’appelle le non-déterminisme. Le non-déterminisme existe car nous ne connaissons
pas le temps exact de l’exécution de chaque opération. Si nous pouvions connaître
ce temps, il n’y aurait pas de non-déterminisme. Mais nous ne pouvons le connaître,
simplement parce que les fils sont indépendants. Chaque fil ne peut donc pas connaître
quelles sont les instructions exécutées par les autres fils à un moment donné.
Le non-déterminisme en soi n’est pas un problème ; nous l’avons déjà avec la
concurrence. Les difficultés apparaîtront seulement si le non-déterminisme devient
visible dans le programme, c’est-à-dire s’il devient observable. Un non-déterminisme
observable est parfois appelé une course (« race condition »). En voici un exemple
simple :
declare
C={NewCell 0}
thread C:=1 end
thread C:=2 end
Quel est le contenu de C après l’exécution de ce programme ? La figure 1.4 montre
deux exécutions possibles de ce programme. Selon l’exécution qui est faite, le contenu
final de la cellule peut être 1 ou 2. Le problème est que nous ne pouvons pas prévoir
ce qui arrivera. C’est un exemple de non-déterminisme observable. Le comportement
peut devenir encore plus compliqué. Par exemple, utilisons une cellule pour stocker
un compteur qui peut être incrémenté par plusieurs fils :
declare
C={NewCell 0}
thread I in I=@C C:=I+1 end
thread J in J=@C C:=J+1 end
Quel est le contenu de C après l’exécution de ce programme ? Il semble que chaque
fil ajoute 1 au contenu, ce qui fait 2 à la fin. Mais il y a une surprise : le contenu final