:: Enseignements :: ESIPE :: E4INFO :: 2015-2016 :: Java Réseau I - Concurrence et E/S ::

TP noté de Concurrence

Le but de ce TP noté est d'écrire quelques classes permettant de vérifier que vous maitrisez 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.

Vos TPs sont à rendre sur elearning.

Tout document papier est proscrit. Vous pouvez consulter la javadoc à travers 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/.

Même si les deux exercices ont le même but, calculer des sommes d'entiers en utilisant plusieurs threads, les techniques sont différentes ce qui fait que les exercices sont complètement indépendants et peuvent être traités dans n'importe quel ordre.

Exercice 1 - Decomposition binaire

Le but de cet exercice est de calculer la somme des éléments d'un tableau d'entiers assez grand en utilisant un algorithme de décomposition binaire.
L'idée est de couper (virtuellement, on changera juste les index) un tableau en deux, puis de demander le calcul de la somme des entiers de chaque partie en faisant un appel récursif, la somme des entiers du tableau étant égale à l'addition de la somme des entiers des deux parties de tableau.
Pour éviter de couper si la partie de tableau dont on doit faire la somme est trop petite, on introduit un paramètre cutoff. Si la taille de la partie du tableau est supérieure à cutoff, on décompose la partie de tableau en 2, et si la taille de la partie du tableau est inférieure à cutoff, la somme est calculée en itérant sur le tableau.
Programmé en Java sans thread, cela donne le code suivant:

  public static int sum(int[] array, int start, int end, int cutoff) {
    if (end - start > cutoff) {
      int middle = (start + end) / 2;
      int sum1 = sum(array, start, middle, cutoff);
      int sum2 = sum(array, middle, end, cutoff);
      return sum1 + sum2;
    }
    System.out.println("sum " + start + " " + end);
    return Arrays.stream(array, start, end).sum();
  }

que l'on peut tester avec le main suivant

  public static void main(String[] args) {
    int[] array = new Random(0).ints(10_000, 0, 1_000).toArray();
    System.out.println(sum(array, 0, array.length, 1_000));
  }

Le but de cet exercice est de faire le calcul de chaque partie (lorsque la taille est supérieure à cutoff) en parallèle en créant une thread pour calculer la seconde partie de tableau.
Bien sûr, le calcul de la première partie de tableau comme le calcul de la seconde partie de tableau peuvent eux même créer des threads.

Ecrire une méthode sum2 thread-safe qui implante la décomposition multi-threadée telle que décrite ci-dessus.
Attention à ce que les calculs intermédiaires aient bien été finis avant de faire l'addition des sommes des deux parties.
Pour transférer le résultat d'un calcul d'une thread à l'autre, vous pourrez avoir besoin d'une structure comme Result
```
      static class Result {
        int sum;
      }
      
```
La méthode précédente n'est pas très efficace car elle crée trop de threads. Pour remédier au problème, ajouter un paramètre maxThread (que l'on fixera à 8 dans le main) qui correspond au nombre maximal de threads qui doivent être utilisés. Si il n'y a plus de thread disponible, le calcul se fera sans faire de décomposition même si le nombre d'éléments du tableau est supérieur à cutoff.
Ecrire une méthode sum3 threadsafe qui implante ces changements.

Exercice 2 - Decomposition Linéaire

Le but de cet exercice est de calculer la somme des entiers d'un tableau en utilisant une décomposition linéaire.
La décomposition linéaire consiste à découper (virtuellement, on changera juste les index) un tableau en parties de même longueur (appelée ici cutoff) puis de faire la somme de chaque partie et enfin la somme des sommes de chaque partie.
Le code ci-dessous implante l'algorithme sans thread:

  static class Interval {
    final int start;
    final int end;
    int sum;
    
    public Interval(int start, int end) {
      this.start = start;
      this.end = end;
    }
  }
  
  public static int sum(int[] array, int cutoff) {
    // split in several parts of length equals to cutoff
    ArrayList<Interval> results = new ArrayList<>();
    for(int i = 0; i < array.length; i+= cutoff) {
      Interval interval = new Interval(i, Math.min(i + cutoff, array.length));
      results.add(interval);
    }
    
    // compute the sum of each interval
    for(Interval interval: results) {
      System.out.println("sum " + interval.start + " " + interval.end);
      int sum = Arrays.stream(array, interval.start, interval.end).sum();
      interval.sum = sum;
    }
    
    // compute the sum of the partial sums
    int sum = 0;
    for(Interval interval: results) {
      sum += interval.sum;
    }
    return sum;
  }

Notez que le code est pas très 'Objet' mais c'est pas un tp noté de POO...

Le but de cet exercice est de produire une version multi-threadée de la méthode sum.
Dans un premier temps, la méthode va créer maxThread threads qui vont se mettre en attente sur une queue qui va contenir les intervalles dont on cherche la somme.
Chaque thread, va essayer d'extraire un intervalle de la queue, puis calculer la somme des entiers pour cet intervalle et enfin renseigner le champ sum de la classe Interval. Si aucun n'intervalle n'est disponible dans la queue, la thread va se mettre en attente jusqu'à ce qu'un intervalle soit créé.
Au niveau de la thread main, celle-ci va créer les intervalles, les ajouter dans la queue, puis se mettre en attente des différentes sommes partielles dans le but de calculer la somme totale.

Ecrire une méthode sum4 threadsafe qui prend en paramètre un tableau, la valeur cutoff et un nombre de threads maxThread et renvoie la somme des entiers du tableau en utilisant l'algorithme décrit ci-dessus.
Lorsque l'on execute la méthode sum4 dans le main, la machine virtuelle ne s'arrête plus car les threads créées ne sont pas détruites. Utiliser le mécanisme d'interruption pour arrêter toutes les threads créées à la fin de la méthode sum4.