Exercice 1

Question 1

• add(x) : Le point de linéarisation est le moment où le CAS réussit à ajouter le nouveau nœud dans la liste.

• remove(x) : Le point de linéarisation est le moment où le CAS réussit à marquer le nœud comme supprimé.

• contains(x) : Le point de linéarisation est le moment où la recherche trouve le nœud avec la clé correspondante.

Question 2

• add(x) : Cette opération a une propriété de progression lock-free. Si un thread échoue à ajouter un élément, c’est parce qu’un autre thread a réussi à ajouter un élément en même temps.

• remove(x) : Cette opération a également une propriété de progression lock-free. Si un thread échoue à supprimer un élément, c’est parce qu’un autre thread a réussi à supprimer ou à modifier l’élément en même temps.

• contains(x) : Cette opération a une propriété de progression wait-free. Elle ne peut pas être bloquée par d’autres threads et retourne toujours un résultat.