:: Enseignements :: Master :: M1 :: 2018-2019 :: Java Avancé ::

TP noté de Concurrence

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

Vos sources Java produites pendant le TP devront être placées sous le répertoire EXAM de votre compte ($HOME) (qui est vierge 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 dans Eclipse (onglet Javadoc) ou en lançant la commande jdoc dans un shell. Les seuls documents électroniques autorisés sont les supports de cours à l'url http://igm.univ-mlv.fr/~forax/ens/java-avance/cours/pdf/.

La javadoc est accessible en local : /usr/local/apps/java9/docs/api/index.html.

Exercice 1 - Maximums

La classe MaxCollector permet de garder en mémoire les 10 plus grandes valeurs parmi celles qui lui sont proposées. La classe utilise en interne une PriorityQueue qui permet d'insérer et de retirer des valeurs de façon ordonnée. Par contre, l'itérateur sur une PriorityQueue ne parcourt pas les valeurs de façon ordonnée, c'est pour cela que la méthode winners trie les valeurs avant de les renvoyer.

Le code de la classe MaxCollector est le suivant:

public class MaxCollector {
  private final PriorityQueue<Integer> maxes = new PriorityQueue<>();
  
  public void proposeValue(int value) {
    maxes.offer(value);
    if (maxes.size() > 10) {
      maxes.poll();
    }
  }
  
  public List<Integer> winners() {
    var list = new ArrayList<>(maxes);
    list.sort(null);
    return list;
  }
}

Rendre la classe MaxCollector thread-safe en utilisant le mot clé synchronized.
On peut remarquer que l'opération de tri List.sort peut être faite indépendamment par chaque thread. Avez vous pris cela en compte lorsque vous avez rendu la classe MaxCollector thread-safe? Sinon, modifier votre code en conséquence.
Ajouter un main qui crée 4 threads qui appellent chacune la méthode proposeValue 10 000 fois, sur un même objet de la classe MaxCollector, avec des valeurs pseudo-aléatoires comprises entre 0 (inclus) et 1 000 000 (exclu). Faire afficher la liste des 10 gagnants quand tout le monde a fini.
Pour que les résultats soient reproductibles d'une exécution à l'autre, on vous demande d'utiliser un objet de la classe java.util.Random par thread, initialisé avec le numéro de la thread (de 0 à 3 donc). Pour obtenir les valeurs pseudo-aléatoires, vous utiliserez la méthode Random.ints() à 3 arguments (ou, si vous avez du mal avec les Stream, la méthode Random.nextInt à 1 argument).
Écrire une classe MaxCollector2 qui fait exactement la même chose que la classe MaxCollector, mais qui utilise les verrous ré-entrants fournis par l'API Java, pour garantir que la classe est thread-safe.

Exercice 2 - Un peu plus équitable

En se basant sur le code de la classe MaxCollector2 créée précédemment, on souhaite créer une nouvelle classe FairerMaxCollector qui utilise un algorithme un peu différent.
On souhaite désormais qu'une thread qui a fait un appel à proposeValue soit bloquée si elle fait un autre appel à proposeValue sans qu'une autre thread ait fait un appel à proposeValue entre-temps.
Bien sûr, lorsqu'il ne reste qu'une seule thread, celle-ci peut faire des appels à proposeValue successivement.

Pour savoir s'il ne reste qu'une seule thread, on ajoute, dans la classe, un constructeur qui prend en paramètre le nombre de threads initiales et on ajoute une méthode end sans paramètre qui doit être appelée une fois qu'une thread a transmis toutes ses valeurs.

On ne garantit pas le bon fonctionnement des méthodes de la classes si elles sont mal utilisées (par exemple, si moins de threads que prévu proposent des valeurs ou si une thread utilise plusieurs fois la méthode end).

Écrire la classe FairerMaxCollector et penser à modifier le main (en appelant la méthode end) pour pouvoir tester le nouvel algorithme.
Note: Il n'y a pas qu'une seule façon d'écrire un code correct pour la la classe FairerMaxCollector. Si vous avez besoin d'une section critique dans le constructeur (ça dépend de comment vous écrivez le code), ne l'oubliez pas !!
Note 2: Faites attention à gérer correctement les éventuelles exceptions !
On remarque que si on utilise le mot clé volatile judicieusement, on peut améliorer le code de la méthode end pour qu'il soit un peu plus efficace. Modifier le code en conséquence.
Note: Si vous aviez besoin d'une section critique dans le constructeur, ça peut permettre de la retirer. Dans ce cas, modifier également le code en conséquence.