Exercice 1

Premier point

Oui. La linéarisation peut être réalisée en ordonnant les opérations comme suit :

1. enq(x) ok
2. enq(y) ok
3. deq() y
4. deq() x

Second point

Oui, le deq() de p2 aurait pu se terminer avant le enq(y), donc il aurait renvoyer x et non y.

Exercice 2

Question 1

class R {
  S s;

  void ecrire(boolean valeur) {
    s.ecrire(valeur);
  }

  boolean lire() {
    return s.lire();
  }
}

Question 2

Si on efface d’abord l’écriture précédente, il y a un risque que la lecture concurrente retourne
une valeur incorrecte. Par exemple, si on écrit 5 puis 3, et que la lecture se produit entre
l’effacement de 5 et l’écriture de 3, la lecture pourrait retourner une valeur fausse
(par exemple, 0 si aucune autre écriture n’a eu lieu).

Question 3

Si on écrit d’abord la nouvelle valeur puis on efface l’ancienne, cela garantit que la lecture
concurrente retourne toujours une valeur valide (soit la nouvelle valeur, soit l’ancienne).
Cela évite les lectures incorrectes.

Question 4

Il ne faut pas toujours effacer les précédentes écritures, car cela peut entraîner des
lectures incorrectes. Pour réaliser une écriture, il faut d’abord écrire la nouvelle valeur,
puis effacer l’ancienne. Cela garantit que la lecture concurrente retourne toujours une valeur valide.

Exercice 3

class A {
  RM rm;

  void ecrire(int valeur) {
    rm.ecrire(valeur);
  }

  int lire() {
    return rm.lire();
  }
}

Exercice 4

Voir le Main.java et TS2, TS3 et TS4.

Exercice 5

Question 1

Une pile concurrente est une structure de données LIFO

Question 2

Oui, cette implémentation est linéarisable. Les points de linéarisation sont :

• Pour empiler(int j) : Le point de linéarisation est à la fin de l’exécution de la méthode, lorsque sommet est incrémenté et que j est placé dans le tableau.

• Pour depiler() : Le point de linéarisation est à la fin de l’exécution de la méthode, lorsque sommet est décrémenté et que l’élément est retourné.

Question 3

a

Oui, l’implémentation est linéarisable, car il n’y a pas de conflit entre les threads.

b

Non, l’implémentation n’est pas linéarisable, parce qu’il y a un risque de race condition sur sommet.

c

Non, l’implémentation n’est pas linéarisable, parce qu’il y a un risque de race condition sur sommet.

d

Non, l’implémentation n’est pas linéarisable, parce qu’il y a un risque de race condition sur sommet.