Exercice 1

Question 1

Non, car le synchronized dans echange met un verrou sur les threads déclaré, mais pas entre les threads.

Question 2

Supprimer les synchronized ne change rien.

Exercice 2

Question 1

Non, parce que c’est le calcul de max qui compte, l’écriture du max + écriture n’est pas atomique.

Question 2

Dans ce cas-là, l’ordre est assuré, car le thread j ne commence qu’après l’écriture du max du thread i.

Question 3

On reset le label à zéro quand on libère le verrou.

On perd l’équité (et l’exclusion mutuelle), parce que des threads peuvent avoir des valeurs des autres labels des threads différents de la réalité.

Question 4

ReentrantLock : Si on possède le verrou et qu’on rappelle le lock, on ne bloque pas.

• On met un if dans la fonction lock
• Il faut aussi rajouter une variable locale au thread qui s’incrémente en fonction du nombre de lock acquis
• On met un if aussi dans la fonction unlock

La variable ajoutée est protégée, car interne au thread, pas partagé. Donc pas besoin de lock.

Exercice 3

Question 1

Non.

Question 2

Oui, puisqu’il y a une implémentation atomique.

Question 3

Oui parce que l’update et le scan sont atomiques ensemble. La collecte est donc incluse dans le scan (mais des updates peuvent avoir lieu ailleurs et qui ne sont pas dans le collect).

Pas parce que c’est une implémentation atomique

Question 4

Ça reste atomique, mais pas wait-free, car un scan peut ne jamais se terminer. Il faut s’assurer que chaque valeur est différente.

Exercice 4

Question 1

Correction : Quel est le numéro de consensus de Inc ?

C’est un consensus à deux.

Inc Partagée

Thread i:
R[i] = ma_prop
if (Inc() == 0) then decide(R[i])
                else decide(R[i - 1])

On peut utiliser l’exemple du Test and Set pour montrer que l’on ne peut pas faire de consensus à 3.

L’idée, c’est que le premier, il sait qu’il est premier, le deuxième, il sait qu’il n’est pas premier, et le troisième, il ne sait pas, alors ça se limite à deux.

Question 2

Non, on ne peut pas.

Question 3

A priori non, car le résultat d’universalité à deux nous dit qu’on doit se limiter à deux threads.
Par contre, dans le cas de Inc c’est possible via du Test And Set à n.

Question 4

\dots

Exercice 5

Question 1

Non on peux pas avoir de blocage car on déplace toujours l’ancien verrou.

Question 2

Le point de linéarisation, c’est quand on trouve l’endroit où on doit faire (ou pas) des choses : l’élément qu’on rajoute avec le return false et pred.next = node ; avec contains c’est la comparaison à l’intérieur du if ; et pour le retrait, c’est le return false et pred.next = curr.next.

Question 3

Il nous faut un verrou pour éviter de regarder un élément qui est en train de se faire supprimer et nous éviter de quitter la liste.

Question 4

Déjà, un verrou, ce n’est pas vraiment wait-free, mais on suppose qu’il l’est, aussi qu’il est équitable.

Si le verrou est équitable, alors oui, il est wait-free.
Sinon alors, on va possiblement attendre tout le temps le verrou, mais vu que c’est non-bloquant, il y aura toujours un thread qui va progresser.