Examen de concurrence (Session de Juillet)

On souhaite écrire une classe implantant les opérations put et take des buffers bloquants utilisés entre un producteur et un consommateur. On utilise la classe ArrayDeque pour stocker les éléments en interne.
De plus, on souhaite ajouter une troisième opération slurpAll qui prend en paramètre une collection et retire du buffer tous ses élements pour les copier dans la collection prise en paramètre, en une seule opération atomique.

On souhaite écrire un algorithme récursif assez simple de trie d'un tableau d'entiers en parallèle.
Avant de décrire comment l'algorithme marche avec des threads, commençont par expliquer comment il marche sans thread. L'idée est de diviser le tableau d'entier en deux parties égales (ou presque) si le tableau à une taille supérieur à 8 et pour les tableaux de taille 8 ou moins d'appeler le trie classique de Java, à savoir la méthode java.util.Arrays.sort.
Lors de la remonter de l'algorithme récursif, les deux parties de tableau sont triés, on peut alors appliquer l'algorithme de merge ci-dessous, qui va prendre les éléments du tableau trié array1 entre start1 et start2 et les éléments du tableau trié array2 entre start2 et end et recopier les élements dans le tableau dst (qui doit être différent de array1 et de array2 entre les positions start et end.

  static void merge(int[] dst, int[] array1, int start1,
                               int[] array2, int start2, int end) {
    int i = start1;
    int i1 = start1;
    int i2 = start2;
    int e1 = array1[i1++];
    int e2 = array2[i2++];
    for(;;) {
      if (e1 <= e2) {
        dst[i++] = e1;
        if (i1 == start2) {
          dst[i++] = e2;
          while(i2 < end) {
            dst[i++] = array2[i2++];
          }
          return;
        }
        e1 = array1[i1++];
      } else {
        dst[i++] = e2;
        if (i2 == end) {
          dst[i++] = e1;
          while(i1 < start2) {
            dst[i++] = array1[i1++];
          }
          return;
        }
        e2 = array2[i2++];
      }
    }
  }
    

Par exemple avec le tableau à 20 éléments

      [12, 8, 0, 11, 9, 2, 6, 17, 3, 7, 10, 1, 15, 5, 19, 18, 16, 4, 13, 14]
    

Le tableau sera séparé en deux parties

      [12, 8, 0, 11, 9, 2, 6, 17, 3, 7]   et   [10, 1, 15, 5, 19, 18, 16, 4, 13, 14]
    

puis en

      [12, 8, 0, 11, 9] et [2, 6, 17, 3, 7]    [10, 1, 15, 5, 19] et [18, 16, 4, 13, 14]
    

comme les tableaux sont plus petit que 8, ils vont être triés

      [0, 8, 9, 11, 12]    [2, 3, 6, 7, 17]    [1, 5, 10, 15, 19]    [4, 13, 14, 16, 18]
    

puis les deux tableaux de gauche vont être mergés ainsi que les deux tableaux de droite

      [0, 2, 3, 6, 7, 8, 9, 11, 12, 17]        [1, 4, 5, 10, 13, 14, 15, 16, 18, 19]
    

les deux tableaux restant vont alors eux aussi être mergé pour obtenir

      [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
    

Maintenant en ajoutant les threads, lors de l'appel à la méthode parallelSort, en plus du tableau d'entiers, l'utilisateur va passer un second paramètre indiquant sur combien de threads le calcul doit se faire, ce nombre doit toujours être une puissance de 2.
Par exemple si l'utilisateur passe 4, on aura la décomposition suivante (avec t1 pour thread1, t2 pour thread2 etc.)

      t1 [12, 8, 0, 11, 9, 2, 6, 17, 3, 7, 10, 1, 15, 5, 19, 18, 16, 4, 13, 14]
      
      t1 [12, 8, 0, 11, 9, 2, 6, 17, 3, 7]           t2 [10, 1, 15, 5, 19, 18, 16, 4, 13, 14]
   
      t1 [12, 8, 0, 11, 9]   t3 [2, 6, 17, 3, 7]     t2 [10, 1, 15, 5, 19]   t4 [18, 16, 4, 13, 14]
   
      t1 [0, 8, 9, 11, 12]   t3 [2, 3, 6, 7, 17]     t2 [1, 5, 10, 15, 19]   t4 [4, 13, 14, 16, 18]
    
      t1 [0, 2, 3, 6, 7, 8, 9, 11, 12, 17]           t2 [1, 4, 5, 10, 13, 14, 15, 16, 18, 19]
    
      t1 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
    

Comme les calculs sont effectués par des threads différentes, à vous de faire attention à ce que les choses se fasse dans l'ordre.
Note: pour la fonction de merge on a besoin d'un tableau supplémentaire, mais ce tableau peut servir à plusieurs merge.

Pour vous aider à débugger, la fonction ci-dessous affiche le contenu d'un tableau entre start et end.

  private static void dump(String name, int[] array, int start, int end) {
    StringBuilder builder = new StringBuilder().append(name).append(' ');
    builder.append('[').append(array[start]);
    for(int i = start + 1; i < end; i++) {
      builder.append(", ").append(array[i]);
    }
    System.out.println(builder.append(']').toString());
  }