Examen de Collection Concurrente - Avril 2020

Exercice 1 - Fork/Join Summary (9)

import java.util.Arrays;
import java.util.Random;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveTask;

public class SummaryIndex {
  private static class Entry {
    private double average;
    private int cursor;
    private final double[] data;

    private Entry(int dataLength) {
      this.average = Double.NaN;
      double[] data = new double[dataLength];
      Arrays.fill(data, Double.NaN);
      this.data = data;
    }
  }

  private final Entry[] entries;

  public SummaryIndex(int entryLength, int dataLength) {
    var entries = new Entry[entryLength];
    for(var i = 0; i < entries.length; i++) {
      entries[i] = new Entry(dataLength);
    }
    this.entries = entries;
  }

  public void add(int entryIndex, double value) {
    var entry = entries[entryIndex];
    var cursor = entry.cursor;
    entry.data[cursor] = value;
    entry.cursor = (cursor + 1) % entry.data.length;
  }

  public double average(int entryIndex) {  // pas utilisée dans l'exercice
    return entries[entryIndex].average;
  }

  public double sumSummary() {
    var sum = 0.0;
    for(var i = 0; i < entries.length; i++) {
      var entry = entries[i];
      var stats = Arrays.stream(entry.data).filter(v -> !Double.isNaN(v)).summaryStatistics();
      var average = stats.getAverage();;
      entry.average = average;
      if (!Double.isNaN(average)) {
        sum += stats.getSum();
      }
    }
    return sum;
  }

  public static void main(String[] args) {
    var summaryIndex = new SummaryIndex(20_000, 200);

    var random = new Random(0);
    for(var i = 0; i < 10_000_000; i++) {
      summaryIndex.add(i % 20_000, random.nextInt(100));
    }

    System.out.println(summaryIndex.sumSummary());

    //System.out.println(summaryIndex.parallelSumSummary());
  }
}
   

1. Dans un premier temps, écrire une méthode double sequentialSumSummary(int from, int to) permettant de mettre à jour les moyennes des entries entre [from, to[ et de calculer la somme des valeurs.
   Pour tester, vérifier que sequentialSumSummary(0, entryLength) à la même résultat que sumSummary().
2. Ecrire la classe Task qui hérite de la classe RecursiveTask et implante algorithme fork/join.
   L'algorithme est le suivant: si la distance entre from et to est inférieur ou égale à 100, on utilisera la version séquentielle, sinon on coupera (virtuellement) le tableau au millieu entre from et to, on crée deux sous tâche pour chaque partie de tableau et on applique la logique fork/join
3. Enfin ajouter la méthode parallelSumSummary() qui récupère le pool fork/join par défaut puis envoie une tâche demandant le calcul sur toutes les entries.
   Vérifier que les méthodes parallelSumSummary() et sumSummary() renvoie bien le même résultat.
4. En fait, la structure ne vient pas avec une méthode sumSummary mais une méthode averageSummary qui calcule les moyennes de chaque capteur (comme avant) et renvoie la moyenne globale de toutes les valeurs de tous les capteurs (donc pas la somme).
   Voici le code de la méthode averageSummary

     public double averageSummary() {
       var sum = 0.0;
       var count = 0L;
       for(var i = 0; i < entries.length; i++) {
         var entry = entries[i];
         var stats = Arrays.stream(entry.data).filter(v -> !Double.isNaN(v)).summaryStatistics();
         var average = stats.getAverage();
         entry.average = average;
         if (!Double.isNaN(average)) {
           sum += stats.getSum();
           count += stats.getCount();
         }
       }
       return sum / count;
     }
        

   
   En utilisant le même principe écrire la méthode parallelAverageSummary.
   Note: cette question n'a pas beaucoup de points (2), donc ne passer pas une éternité dessus si vous ne voyez pas comment faire !

Exercice 2 - COWList (8)

1. Ecrire une classe COWList générique avec une méthode add qui permet d'ajouter un élement dans la liste et une méthode size (le nombre d'élements dans la liste)
2. Ecrire un main de test qui créé 4 threads ajoutant chacune 2_500 entiers dans une même liste et qui affiche la taille de la liste une fois que toute les threads ont terminé.
   Rappel: il faut faire un join avant d'afficher la taille !
3. Expliquer pourquoi le code que vous avez écrit est pas thread-safe (en commentaire dans le code).
4. Créer une version thread-safe de la classe COWList nommée SynchronizedCOWList qui utilise des blocs synchronized pour rendre le code thread-safe.
   Attention: lorsque vous tester le main de SynchronizedCOWList à bien vérifier que vous créez une SynchronizedCOWList et pas une COWList !
   Attention 2: SynchronizedCOWList doit être thread-safe quelque soit le main que vous pouvez écrire, cela ne doit pas fonctionner juste avec votre main.
5. Créer une nouvelle version de la classe COWList nommée LockFreeCOWList qui utilise l'API des VarHandle pour rendre la classe thread safe.
   Vérifier que votre main fonctionne correctement !

Exercice 3 - Pour les plus balèze: Generateur pseudo-aléatoire lock-free (3)

public class RandomNumberGenerator {
  private long x;
  
  public RandomNumberGenerator(long seed) {
    if (seed == 0) {
      throw new IllegalArgumentException("seed == 0");
    }
    x = seed;
  }
  
  public long next() {  // Marsaglia's XorShift
    x ^= x >>> 12;
    x ^= x << 25;
    x ^= x >>> 27;
    return x * 2685821657736338717L;
  }
  
  public static void main(String[] args) {
    var rng = new RandomNumberGenerator(1);
    for(var i = 0; i < 5_000; i++) {
      System.out.println(rng.next());
    }
  }
}  
   

1. Expliquer comment l'implantation ci-dessus n'est pas thread-safe !
2. Créer une classe LockFreeOneRandomNumberGenerator qui utilise l'API des VarHandles et la méthode compareAndSet pour créer une version thread-safe de l'API.
   Attention à bien modifier le code pour limiter les écritures concurrentes !
   Attention2: Vérifier bien que l'affichage du main de RandomNumberGenerator et LockFreeOneRandomNumberGenerator sont identiques lorsqu'il n'y a qu'une thread !
3. Créer une classe LockFreeTwoRandomNumberGenerator qui utilise la méthode getAndSet au lieu de la méthode compareAndSet de l'API des VarHandles ce qui devrait simplifier votre code.
4. Comparer les implantations de LockFreeOneRandomNumberGenerator et LockFreeTwoRandomNumberGenerator et indiquer selon vous quelle est la meilleure implantation.