Exercice 1

a

Si update et scan sont atomiques alors chaque thread i met à jour son propre index avec update(i). Lorsqu’il effectue scan(), il retrouve bien i à l’index i. Alors oui, on a toujours scan[i]=i

b

Vrai, Un thread j peut observer i uniquement si i a déjà exécuté update(i). Sinon, la valeur reste -1 (valeur initiale).

c

Faux, contre-exemple:
Si scan(j) lit i, cela signifie que i a écrit sa valeur avant que j effectue scan(). Mais rien ne garantit que j ait écrit avant que i fasse son propre scan().

d

Même raisonnement que (c). i peut voir j si l’ordre des mises à jour et des scans le permet.

e

Vrai, Au moins un des threads doit avoir exécuté update(), donc soit j voit i, soit i voit j.

f

Si un scan a plus d’entrées non -1 que l’autre, alors il inclut toutes les valeurs du second.

Exercice 2

a

Non, car les ordres d’exécution des threads ne sont pas contrôlés.
Les opérations ne sont pas synchronisées, donc l’affichage dépend du moment où scan() est appelé.

b

Non, l’implémentation actuelle n’est pas atomique, car scan() ne capture pas un état instantané.
Contre-exemple :

  1. Thread i exécute scan(), lit les premières valeurs.
  2. Pendant ce temps, d’autres threads update(), modifiant les valeurs.
  3. scan() continue la lecture avec les nouvelles valeurs. Résultat : scan() capture un état incohérent.

c

Non, car un thread peut être bloqué par l’ordonnancement.
Il peut se retrouver en attente indéfinie d’accéder à la mémoire partagée.

2.a

L’utilisation de AtomicStampedReference garantit que chaque mise à jour (update) est atomique parce que :

  1. L’estampille (stamp) empêche les lectures incohérentes : Un scan() ne validera sa lecture que si deux lectures consécutives sont identiques.

  2. L’opération set() de AtomicStampedReference est atomique : Elle assure que la mise à jour de value et de stamp est réalisée comme une seule opération indivisible.

  3. Si un scan() détecte un changement dans l’un des indices entre deux lectures successives, il recommence. Cela garantit qu’il capture un état cohérent du tableau.

Conclusion : L’implémentation avec AtomicStampedReference est atomique, car elle assure qu’un scan() capture un état valide du tableau.

Si on remplace AtomicStampedReference par Stamped, Non, l’implémentation ne serait plus atomique !
Pourquoi?

  1. Stamped n’a pas d’opérations atomiques intégrées : il faut une synchronisation explicite, sinon un thread pourrait voir des mises à jour partielles.

  2. Il y aurait des conditions de concurrence : un scan() pourrait lire une référence qui a été mise à jour sans voir la mise à jour correspondante de stamp.

Exercice 3

1

Oui, l’algorithme utilise des AtomicStampedReference et effectue des lectures répétées jusqu’à obtenir un état stable (on ne boucle pas indéfinément)

Contre-exemple :
Si un update() a lieu entre les deux collect(), on peut capturer un état mixte où certains threads voient la nouvelle valeur et d’autres non.

2

Même raisonnement que la question 1
Ce n’est toujours pas atomique.

3

Combien fait-on au plus de collect pour un scan ?
Au plus 3 collect() suffisent :

Premier collect() : Lecture initiale.
Deuxième collect() : Vérification si c’est identique.
Troisième collect() : Recherche de la troisième valeur différente si nécessaire.

Le scan et update terminent-ils toujours ?
Oui, ils terminent toujours :

Scan : Il ne boucle jamais indéfiniment car au plus 3 collect sont nécessaires.
Update : Constamment possible, car AtomicStampedReference garantit que les mises à jour sont terminales.

L’implémentation est-elle atomique ?
Non, ce n’est pas totalement atomique

Pendant les collect(), des updates peuvent modifier certaines valeurs, rendant le snapshot incohérent.
Contre-exemple :
Un thread fait collect() et lit [A, B, C].
Durant ce temps, un update() modifie B → B’.
collect() suivant lit [A, B’, C].
collect() encore après voit [A, B’, C’] → Il croit que c’est un snapshot cohérent, alors que des valeurs ont changé pendant la lecture.