TP noté de concurrence

Exercice 1 - Shop

import java.util.Set;

public class Shop<E> {
  ...

  // constructeur

  public static <T> Shop<T> launch(Set<T> items) {
    // TODO
  }

  public boolean restock(E item, int count) {
    // TODO
    return true;
  }

  public boolean isInStock(E item) {
    // TODO
    return true;
  }

  public int buy(E item) {
    // TODO
    return 0;
  }

  public static void main(String[] args) throws InterruptedException {
    String[] fruits = { "Apricot", "Cherry", "Raspberry", "Strawberry",
              "Rhubard", "Quince", "Apple", "Blackberry" };
    var shop = Shop.launch(Set.of(fruits));

    // TODO
  }
}
   

1. Compléter le code de la méthode main pour créer une Thread par fruit de la liste fruits. Chacune de ces thread propose toutes les secondes entre 1 et 4 (aléatoirement) exemplaires de ce fruit à la vente. Créer également 5 threads qui achètent en boucle (et sans temps d'attente) des fruits de la liste au hasard. Faire en sorte que les thread affichent leur nom et ce qu'elles font au fur et à mesure.
   Voici un exemple d'affichage threads (pour l'instant, restock, isInStock et buy se contentent de renvoyer true ou 0):

   ----> Thread-3 restocks 1 Strawberry
   ----> Thread-4 restocks 2 Rhubard
   Thread-11 buys one Rhubard
   Thread-11 buys one Rhubard
   ----> Thread-0 restocks 3 Apricot
   ----> Thread-5 restocks 3 Quince
   ----> Thread-1 restocks 4 Cherry
   ----> Thread-7 restocks 4 Blackberry
   Thread-12 buys one Blackberry
   Thread-12 buys one Blackberry
   ----> Thread-2 restocks 4 Raspberry
   ----> Thread-6 restocks 4 Apple
   Thread-9 buys one Blackberry
   Thread-8 buys one Blackberry
   Thread-9 buys one Cherry
   Thread-9 buys one Quince
   Thread-9 buys one Quince
   ...
       



2. Écrire le code de la classe Shop et ses méthodes restock, isInStock et buy afin d'avoir le comportement suivant :
   • Si l'item demandé ne fait pas partie des items vendus ou n'est pas en stock, la méthode isInStock renvoie false. Sinon, elle renvoie true.
   • Si l'item proposé ou demandé ne fait pas partie des items vendus, les méthodes restock ou buy lèvent une exception.
   • Si l'item demandé n'est pas en stock, la méthode buy attend qu'il y en ait de nouveau avant de diminuer le stock de 1 et de renvoyer la quantité restante en stock de cet item.
   • Si l'item demandé est déjà en stock, la méthode restock attend qu'il n'y en ait plus avant de remettre la quantité proposée en stock et de renvoyer true.
   • La classe Shop doit être thread-safe.
   L'implantation doit utiliser des blocs synchronized. Dans le main faire également afficher la quantité restant en stock quand un fruit vient d'être acheté (voir exemple à la fin de l'exercice).


3. Copier-coller la classe Shop dans une classe ShopRL et modifier l'implantation pour qu'elle ait exactement le même comportement mais en utilisant les verrous ré-entrants du package java.util.concurrent.locks.


4. Copier-coller la classe Shop dans une classe nommée ShopWithOutOfStock et modifier l'implantation des méthodes restock et buy afin d'avoir le comportement suivant :
   • Si une thread est interrompue alors qu'elle attend de pouvoir proposer des items dans restock, la méthode renvoie false immédiatement et cet item devient définitivement épuisé (il ne sera plus jamais possible d'en acheter dans cette Shop).
   • Si l'item proposé est définitivement épuisé, la méthode restock lève une exception.
   • Si on essaie d'acheter un item définitivement épuisé avec buy, la méthode lève une NoSuchElementException.
   • Si l'item demandé ne fait pas partie des items vendus, n'est pas en stock ou est définitivement épuisé, la méthode isInStock renvoie false. Sinon, elle renvoie true.
   • La classe ShopWithOutOfStock doit rester thread-safe.
   Remarque : une façon simple d'indiquer qu'un item est définitivement épuisé est de lui associer une quantité négative.


5. Modifier le main de ShopWithOutOfStock afin d'avoir le comportement suivant :
   • La thread main essaie d'interrompre la thread qui propose des cerises (cherry) à la vente au bout de 10 secondes.
   • Quand une thread échoue à proposer des items (restock renvoie false), elle s'arrête en affichant qu'elle ne proposera plus d'items.
   • Si une thread choisit d'acheter un fruit qui est définitivement épuisé, elle s'arrête en affichant qu'elle n’achètera plus d'items.
     Remarque : puisque chaque thread "acheteuse" choisi le fruit à acheter au hasard parmi tous les fruits, elle finira forcément par essayer d'acheter une cerise et finira donc par s'arrêter.
   • Quand plus aucun thread n'achète d'items, on interrompt ceux qui proposent encore des items à la vente afin que le programme se termine.
   Votre affichage final devrait ressembler à ça :

   ----> Thread-0 restocks 4 Apricot
   ----> Thread-1 restocks 4 Cherry
   ----> Thread-3 restocks 1 Strawberry
   Thread-9 buys one Strawberry (0 left)
   ----> Thread-2 restocks 1 Raspberry
   Thread-9 buys one Cherry (3 left)
   ----> Thread-4 restocks 1 Rhubard
   ----> Thread-5 restocks 4 Quince
   Thread-10 buys one Raspberry (0 left)
   Thread-9 buys one Quince (3 left)
   Thread-9 buys one Rhubard (0 left)
   Thread-9 buys one Apricot (2 left)
   Thread-8 buys one Apple (1 left)
   ----> Thread-6 restocks 2 Apple
   Thread-11 buys one Quince (2 left)
   Thread-10 buys one Apricot (3 left)
   Thread-10 buys one Apricot (1 left)
   Thread-10 buys one Apricot (0 left)
   ----> Thread-7 restocks 2 Blackberry
   ----> Thread-0 restocks 1 Apricot
   ----> Thread-3 restocks 2 Strawberry
   ----> Thread-2 restocks 1 Raspberry
   ----> Thread-4 restocks 3 Rhubard
   Thread-12 buys one Raspberry (0 left)
   Thread-11 buys one Strawberry (0 left)
   Thread-10 buys one Strawberry (1 left)
   Thread-8 buys one Rhubard (2 left)
   Thread-8 buys one Rhubard (1 left)
   ----> Thread-3 restocks 4 Strawberry
   Thread-10 buys one Strawberry (3 left)
   Thread-8 buys one Strawberry (2 left)
   Thread-8 buys one Cherry (2 left)
   Thread-8 buys one Quince (1 left)
   Thread-8 buys one Apple (0 left)
   Thread-8 buys one Apricot (0 left)
   Thread-12 buys one Raspberry (0 left)
   Thread-10 buys one Blackberry (1 left)
   ----> Thread-2 restocks 2 Raspberry
   Thread-11 buys one Raspberry (1 left)
   ----> Thread-6 restocks 2 Apple
   Thread-11 buys one Blackberry (0 left)
   Thread-12 buys one Quince (0 left)
   Thread-8 buys one Rhubard (0 left)
   Thread-12 buys one Blackberry (3 left)
   ----> Thread-5 restocks 1 Quince
   ----> Thread-0 restocks 3 Apricot
   Thread-11 buys one Quince (0 left)
   Thread-11 buys one Apricot (2 left)
   ----> Thread-7 restocks 4 Blackberry
   Thread-10 buys one Rhubard (0 left)
   Thread-12 buys one Apple (1 left)
   Thread-12 buys one Apple (0 left)
   Thread-12 buys one Apricot (1 left)
   Thread-12 buys one Blackberry (1 left)
   Thread-12 buys one Apricot (0 left)
   ----> Thread-4 restocks 1 Rhubard
   Thread-8 buys one Strawberry (1 left)
   Thread-8 buys one Blackberry (0 left)
   Thread-10 buys one Blackberry (2 left)
   ----> Thread-6 restocks 4 Apple
   ----> Thread-0 restocks 1 Apricot
   ----> Thread-7 restocks 2 Blackberry
   ----> Thread-4 restocks 1 Rhubard
   ----> Thread-2 restocks 4 Raspberry
   Thread-11 buys one Raspberry (2 left)
   Thread-11 buys one Apple (2 left)
   Thread-11 buys one Raspberry (1 left)
   Thread-10 buys one Raspberry (3 left)
   Thread-10 buys one Rhubard (0 left)
   Thread-10 buys one Apple (1 left)
   Thread-8 buys one Raspberry (0 left)
   ----> Thread-5 restocks 1 Quince
   Thread-12 buys one Apple (3 left)
   Thread-11 buys one Quince (0 left)
   ----> Thread-4 restocks 2 Rhubard
   Thread-10 buys one Rhubard (1 left)
   XXXXXX Thread-1 won't restock Cherry anymore XXXXXX
   ----> Thread-5 restocks 4 Quince
   Thread-10 buys one Quince (3 left)
   ----> Thread-2 restocks 2 Raspberry
   Thread-12 buys one Raspberry (1 left)
   Thread-11 buys one Raspberry (0 left)
   Thread-10 buys one Rhubard (0 left)
   Thread-10 buys one Blackberry (1 left)
   ----> Thread-4 restocks 2 Rhubard
   ----> Thread-2 restocks 4 Raspberry
   Thread-9 buys one Raspberry (2 left)
   Thread-9 buys one Strawberry (0 left)
   Thread-9 buys one Rhubard (1 left)
   * Thread-9 stops buying *
   Thread-8 buys one Raspberry (3 left)
   Thread-8 buys one Rhubard (0 left)
   Thread-8 buys one Raspberry (1 left)
   Thread-8 buys one Apricot (0 left)
   Thread-12 buys one Raspberry (0 left)
   ----> Thread-0 restocks 1 Apricot
   ----> Thread-3 restocks 3 Strawberry
   Thread-8 buys one Apricot (0 left)
   ----> Thread-2 restocks 4 Raspberry
   Thread-8 buys one Raspberry (3 left)
   Thread-8 buys one Quince (2 left)
   Thread-8 buys one Raspberry (2 left)
   ----> Thread-4 restocks 1 Rhubard
   * Thread-8 stops buying *
   Thread-12 buys one Rhubard (0 left)
   Thread-12 buys one Quince (1 left)
   Thread-12 buys one Quince (0 left)
   ----> Thread-5 restocks 4 Quince
   * Thread-12 stops buying *
   ----> Thread-0 restocks 3 Apricot
   ----> Thread-4 restocks 1 Rhubard
   Thread-10 buys one Rhubard (0 left)
   * Thread-10 stops buying *
   ----> Thread-4 restocks 3 Rhubard
   Thread-11 buys one Rhubard (2 left)
   Thread-11 buys one Apricot (2 left)
   Thread-11 buys one Blackberry (0 left)
   ----> Thread-7 restocks 2 Blackberry
   Thread-11 buys one Blackberry (1 left)
   Thread-11 buys one Apple (0 left)
   Thread-11 buys one Strawberry (2 left)
   Thread-11 buys one Rhubard (1 left)
   Thread-11 buys one Raspberry (1 left)
   Thread-11 buys one Rhubard (0 left)
   ----> Thread-6 restocks 3 Apple
   ----> Thread-4 restocks 4 Rhubard
   Thread-11 buys one Rhubard (3 left)
   Thread-11 buys one Strawberry (1 left)
   Thread-11 buys one Rhubard (2 left)
   Thread-11 buys one Quince (3 left)
   Thread-11 buys one Apple (2 left)
   Thread-11 buys one Apple (1 left)
   Thread-11 buys one Raspberry (0 left)
   Thread-11 buys one Blackberry (0 left)
   ----> Thread-2 restocks 3 Raspberry
   ----> Thread-7 restocks 1 Blackberry
   Thread-11 buys one Blackberry (0 left)
   Thread-11 buys one Rhubard (1 left)
   Thread-11 buys one Apricot (1 left)
   Thread-11 buys one Raspberry (2 left)
   Thread-11 buys one Apricot (0 left)
   Thread-11 buys one Strawberry (0 left)
   Thread-11 buys one Raspberry (1 left)
   ----> Thread-3 restocks 1 Strawberry
   ----> Thread-0 restocks 4 Apricot
   Thread-11 buys one Apricot (3 left)
   * Thread-11 stops buying *
   XXXXXX Thread-0 won't restock Apricot anymore XXXXXX
   XXXXXX Thread-4 won't restock Rhubard anymore XXXXXX
   ----> Thread-7 restocks 4 Blackberry
   XXXXXX Thread-5 won't restock Quince anymore XXXXXX
   XXXXXX Thread-7 won't restock Blackberry anymore XXXXXX
   XXXXXX Thread-2 won't restock Raspberry anymore XXXXXX
   XXXXXX Thread-3 won't restock Strawberry anymore XXXXXX
   XXXXXX Thread-6 won't restock Apple anymore XXXXXX
       

Exercice 2 - CounterList

import java.util.Collections;
import java.util.List;
import java.util.Objects;
import java.util.Random;
import java.util.Set;
import java.util.stream.IntStream;

import static java.util.stream.Collectors.toList;

public class CounterList {
  private static final class Entry {
    private final String tag;
    private final Entry next;
    private int counter;

    private Entry(String tag, Entry next) {
      this.tag = tag;
      this.next = next;
    }

    private int increment() {
      return counter++;
    }
  }

  private /*final*/ /*volatile*/ Entry head;

  public CounterList(Set<String> tags) {
    Entry head = null;
    for(var tag: tags) {
      head = new Entry(tag, head);
    }
    this.head = head;
  }

  public int next(String tag) {
    Objects.requireNonNull(tag);
    for(var e = head; e != null; e = e.next) {
      if (tag.equals(e.tag)) {
        return e.increment();
      }
    }
    return -1;
  }

  public static void main(String[] args) throws InterruptedException {
    // création des compteurs "id1", "id2", "id3" et "id4"
    var ids = List.of("id1", "id2", "id3", "id4");
    var counterList = new CounterList(Set.copyOf(ids));
    
    // création et mélange d'une liste contenant chaque nom de compteur un même grand nombre de fois 
    var tags = Collections.nCopies(25_000, ids).stream().flatMap(List::stream).collect(toList());
    Collections.shuffle(tags, new Random(0));
    
    // créer les threads
    var threads = ... // TODO
    
    // démarrer les threads
    // TODO
    
    // attendre que les threads se terminent
    // TODO
    
    // afficher les compteurs
    ids.forEach(id -> System.out.println(counterList.next(id)));
  }
}
   

1. Après avoir copié le code ci-dessus dans un fichier CounterList.java, expliquer en commentaire en dessous du champ head, si on a un problème de publication si
   • head est déclaré comme ci-dessus (donc sans autre mot-clé)
   • head est déclaré final
   • head est déclaré volatile
2. Modifier le main pour créer 4 threads (en fait, autant de threads que d'id dans la liste ids) ayant pour noms id1, id2, etc... et qui exécute chacun le code suivant :

   for (var tag : tags) {
     counterList.next(tag);
   }  
       

   
   Puis ajouter un code qui démarre toutes les threads créés.
   Et enfin ajouter un code qui attend que toutes les threads créés se terminent.
3. Expliquer pourquoi la méthode increment de la classe Entry empêche la classe CounterList d'être thread-safe en donnant un scénario précis démontrant que le code n'est pas thread-safe. Écrire ce scénario en commentaire en dessous de la méthode increment.
4. Après avoir mis le code de increment en commentaire, écrire une version thread-safe en utilisant le mot-clé synchronized.
   Vous pouvez exécuter votre main pour vous rassurer sur le fait que votre code semble être correct.
5. En fait, on peut améliorer l'implantation de la méthode increment en utilisant une implantation lock free à base de VarHandle. Commenter l'ancienne implantation de increment et proposer une nouvelle implantation utilisant un VarHandle.
   Note : si vous n'y arrivez pas, vous pouvez écrire une version à base d'AtomicInteger, moins efficace, mais qui vous évitera de perdre trop de points.
6. On souhaite désormais permettre de créer des compteurs dynamiquement. Pour cela changer le code de la méthode next de la classe CounterList : si il n'existe pas déjà un compteur pour le tag donné en paramètre, au lieu de renvoyer -1, la méthode next crée un nouveau compteur et l'ajoute à la liste.
   Modifier la méthode next, en faisant attention à ce que la classe CounterList reste thread-safe.
   Vous pouvez vérifier que le code que vous proposez à l'air de marcher en modifiant le main pour que l'instance de counterList soit créée à partir d'un ensemble vide. Le comportement (valeurs affichées) devrait être exactement le même qu'avant.

   var counterList = new CounterList(Set.of()));    
       

7. Enfin, il est possible que l'implantation complète de CounterList soit lock free.
   Si vous ne l'avez pas déjà fait, faire les changements pour que ce soit le cas.
   En fait, une implantation complètement lock free est assez dangereuse en termes de performance... expliquer pourquoi en commentaire en bas de la classe.