Exercice 1

Question 1

Non, cette implémentation n’est pas linéarisable. L’opération add() n’est pas atomique.
Si plusieurs threads appellent add() simultanément, il peut y avoir des interférences entre
les lectures et les écritures de la variable c, ce qui peut entraîner des résultats incorrects.
Par exemple, deux threads pourraient lire la même valeur de c, l’incrémenter, et retourner la même
valeur, ce qui viole la linéarisabilité.

Question 2

Oui, cette implémentation est linéarisable. Chaque appel à add() parcourt le tableau t jusqu’à
trouver un objet TS dont la méthode ts() retourne 1. Comme chaque TS ne peut retourner 1 qu’une
seule fois, chaque appel à add() retourne un index unique, garantissant ainsi la linéarisabilité.

Question 3

Objet TS

1

TS ne peut être utilisé que pour résoudre le consensus pour un seul thread, car une fois que ts()
a retourné 1, il ne peut plus être utilisé pour décider entre plusieurs threads.

Objet Compteur

Infini

Chaque thread peut obtenir une valeur unique en appelant add().

Exercice 2

Deux threads se mettent d’accord sur une valeur en utilisant les opérations push et pop.
Cependant, avec plus de deux threads, il est impossible de garantir que tous les threads pourront
se mettre d’accord sur une seule valeur, car les opérations sur la pile peuvent être interrompues
par d’autres threads.

Exercice 3

Question 1

L’utilisation de “C&S” est nécessaire pour garantir l’atomicité des opérations sur la pile,
en vérifiant si la valeur actuelle de top correspond à celle qu’on a lue au de départ avant de
réaliser toute modification, assurant ainsi la cohérence des données en concurrence.

Question 2

Les point de linéarisation seront placés au moment où la dernière lecture de la variable top a été effectué.

Question 3

Non, l’implémentation proposée n’est pas wait-free. Elle utilise une boucle while (true) pour retenter
les opérations CAS en cas d’échec, ce qui signifie qu’un thread pourrait être bloqué indéfiniment si
d’autres threads modifient constamment Top. Pour être wait-free, chaque thread devrait être garanti
de terminer son opération en un nombre fini de pas, indépendamment des autres threads.