:: Enseignements :: Master :: M1 :: 2021-2022 :: Java Avancé ::

TP noté de concurrence 2021

Le but de ce TP noté est de vérifier que vous maîtrisez les mécanismes de base de protection de code exécuté de manière concurrente.

Vos sources Java produites pendant l'examen devront être placées sous le répertoire EXAM de votre compte ($HOME) (qui est vide dans l'environnement de TP noté). Sinon, elles ne seront pas récupérées.

Tout document papier est proscrit.
Vous pouvez consulter la javadoc à travers Eclipse (onglet Javadoc), sinon la doc est là: http://igm.univ-mlv.fr/~juge/javadoc-17/api/index.html.
Les seuls documents électroniques autorisés sont les supports de cours à l'url http://igm.univ-mlv.fr/~forax/ens/java-avance/cours/pdf/.

Vous avez le droit de lire le sujet jusqu'au bout, cela vous donnera une bonne idée de là où on veut aller !

Exercice 1 - HalfSyncCounter

Un HalfSyncCounter est un compteur thread-safe qui possède deux champs counter et syncCounter, tous deux de type entier, ainsi que deux méthodes

increment qui incrémente counter ou, si ce n'est pas possible, incrémente syncCounter. Cette méthode ne renvoie rien.
result qui met à jour counter avec la somme de counter et syncCounter. Elle remet également syncCounter à zéro et renvoie la valeur de counter mise à jour.

L'algorithme exact de la méthode increment() est le suivant : dans un premier temps, on essaye de calculer la prochaine valeur de counter (l'ancienne valeur + 1) et de mettre à jour la nouvelle valeur avec un compareAndSet. Si ça échoue, parce qu'une autre thread a mis à jour counter entre temps, alors le code utilise une solution de repli qui consiste à incrémenter syncCounter qui est protégé par un verrou, ce qui est plus lent mais dont le succès est garanti.
Cela veut donc dire que deux compteurs sont incrémentés, counter et syncCounter en cas de contention. Donc result doit réunir les valeurs des deux compteurs. L'algorithme est le suivant : si syncCounter est égal à zéro, alors la valeur de counter est renvoyée, sinon, la valeur de counter est mise à jour inconditionnellement en lui ajoutant la valeur de syncCounter avec un compareAndSet. Cette somme est renvoyée et syncCounter est remis à zéro.

Le squelette de la classe HalfSyncCounter est le suivant:

  public class HalfSyncCounter {
    private int counter;
    private int syncCounter;

    public void increment() {
      counter++;
      // or syncCounter++; if it fails
    }

    public int result() {
      System.out.println("syncCounter = " + syncCounter);
      if (syncCounter == 0) {
        return counter;
      }
      counter += syncCounter;
      syncCounter = 0;
      return counter;
    }

    public static void main(String[] args) throws InterruptedException {
      var counter = new HalfSyncCounter();
      var thread = new Thread(() -> {
        for(var i = 0; i < 100_000; i++) {
          counter.increment();
        }
      });
      thread.start();
      for(var i = 0; i < 100_000; i++) {
        counter.increment();
      }
      thread.join();
      System.out.println(counter.result());
      System.out.println(counter.result());
    }
  }

Un affichage possible est

syncCounter = 21158
200000
syncCounter = 0
200000

Implanter la classe HalfSyncCounter pour quelle soit thread-safe, en utilisant un AtomicInteger du package java.util.concurrent.atomic pour faire les opérations compareAndSet.
Attention, la synchronisation autour de l'accès à syncCounter doit être faite correctement.
On souhaite maintenant utiliser la classe VarHandle du package java.lang.invoke pour implanter les opérations compareAndSet.
Créer une classe VarHandleHalfSyncCounter, elle aussi thread-safe, qui implante la classe HalfSyncCounter en utilisant des VarHandle.
On peut remarquer que la méthode result peut être écrite en utilisant un add atomique au lieu d'utiliser un compareAndSet. Dans la classe VarHandleHalfSyncCounter, commenter l'ancienne version de result et écrire une nouvelle implantation sans compareAndSet.

Exercice 2 - Lottery

On souhaite simuler un mécanisme de loterie. À la construction, on indique le nombre de threads participantes (party) et le constructeur mélange au hasard des tickets dont un seul est gagnant (Tiket.WINNER). Puis chaque thread appelle la méthode bet(). Cette méthode renvoie le ticket de chaque thread par ordre d'appel (la thread qui fait le premier appel à bet reçoit le premier ticket, la seconde le second ticket, etc). Tant que le ticket gagnant n'est pas trouvé, les threads ayant parié sont mises en attente. Dès que le ticket est trouvé, toutes les threads en attente sont réveillées. Les futures threads qui appellent bet ne sont pas mise en attente.
On propose le code suivant :

import java.util.concurrent.ThreadLocalRandom;

public class Lottery {
  public enum Ticket { WINNER, LOSER }

  // TODO ajouter ou modifier les champs comme vous voulez
  private int party;
  private int winner;

  public Lottery(int party) {
    if (party < 2) {
      throw new IllegalArgumentException();
    }
    this.party = party;
    this.winner = ThreadLocalRandom.current().nextInt(party);
  }

  public Ticket bet()
    // TODO
    return null;
  }

  public static void main(String[] args) {
      var threadCount = 5;
      var lottery = new Lottery(threadCount);
      // TODO
  }
}

Écrire un main de test qui lance threadCount threads qui, chacune, exécute le code suivant
```
     System.out.println(lottery.bet() + " " + id);
    
```
sachant que id correspond à une variable contenant un numéro de 0 à threadCount - 1.
De plus, chaque thread doit avoir comme nom "thread " + id pour aider au debugging.
Note : on ne cherche pas à attendre que les threads aient fini !
Écrire la méthode bet() qui renvoie le Ticket correspondant à la thread. La première thread qui l'appelle reçoit le premier ticket, etc... Cette méthode bloque les threads jusqu'à ce que le ticket gagnant soit trouvé.
Pour aider au debugging, on vous demande d'ajouter dans votre code les morceaux de code suivants
- ```
       System.out.println("réveil " + Thread.currentThread());
      
```
  au moment où l'on réveille les threads en attente et
- ```
       System.out.println("en attente " + Thread.currentThread());
      
```
  avant qu'une thread s'endorme.
Voici un exemple de trace d'exécution
```
     en attente Thread[thread 0,5,main]
     en attente Thread[thread 1,5,main]
     réveil Thread[thread 3,5,main]
     LOSER 1
     LOSER 2
     LOSER 4
     WINNER 3
     LOSER 0
    
```
Pour que la classe Lottery soit thread-safe, on vous demande de faire une implantation à base de ReentrantLock (toute autre implantation sera considérée comme hors sujet).
Que se passe-t-il si on a plus de threads qui appellent bet que le nombre pris à la construction ? Quelle devrait être la bonne façon de gérer ce cas ? Si ce n'est pas déjà fait, modifier votre code en conséquence.