Examen de Collection Concurrente 2026 - Session 2

À lire absolument

Exercice 1 - FixedList est-elle thread-safe ?

import java.lang.invoke.MethodHandles;
import java.lang.invoke.VarHandle;
import java.util.Objects;

public final class ThreadSafeFixedList<E> {
  private static final VarHandle VH_SIZE, VH_ELEMENTS;
  static {
    var lookup = MethodHandles.lookup();
    VH_SIZE = ... /* TODO */
    VH_ELEMENTS = MethodHandles.arrayElementVarHandle(Object[].class)
        .withInvokeExactBehavior();
  }

  private static final IllegalStateException FULL = new IllegalStateException("list is full");

  private /*keyword*/ E[] elements;
  private volatile int size;

  public ThreadSafeFixedList(int capacity) {
    if (capacity < 0) {
      throw new IllegalArgumentException("capacity < 0");
    }
    @SuppressWarnings("unchecked")
    var elements = (E[]) new Object[capacity];
    this.elements = elements;
    super();
  }

  public int size() {
    return this.size;  // volatile read
  }

  public void add(E element) {
    Objects.requireNonNull(element);
    var index = (int) VH_SIZE.getAndAdd(this, 1);  // volatile read/write
    var elements = this.elements;  // plain read
    if (index >= elements.length) {
      throw FULL;
    }
    VH_ELEMENTS.setVolatile(elements, index, element);  // volatile elements[index] = element;
  }

  @SuppressWarnings("unchecked")
  public E get(int index) {
    var size = this.size;  // volatile read
    var elements = this.elements;      // plain read
    if (size > elements.length) {
      throw new IllegalStateException("??");
    }
    Objects.checkIndex(index, size);
    E element;
    while((element = (E) VH_ELEMENTS.getVolatile(elements, index)) == null) {  // volatile read
      Thread.onSpinWait();
    }
    return element;
  }
}
            

1. Au niveau de la déclaration du champ elements, quel doit être le mot-clé (à la place de /*keyword*/) ?
   Justifier ! (en écrivant un commentaire dans le code)


2. À quoi sert l'appel à .withInvokeExactBehavior() pour initialiser le champ VH_ELEMENTS ?
   Écrire un commentaire au niveau de l'initialisation de VH_ELEMENTS pour expliquer.


3. Il manque le code pour initialiser VH_SIZE (le TODO), pouvez-vous l'écrire ?


4. Expliquer ce que fait la ligne var index = (int) VH_SIZE.getAndAdd(this, 1); (en commentaire au dessus de la ligne).


5. Dans quel cas, la méthode get(int index) peut lever l'IllegalStateException avec le message "??" ?
   Écrivez un commentaire au-dessus de l'instruction throw pour expliquer.


6. La classe ThreadSafeFixedList est-elle thread-safe ? Si oui ou non, expliquer pourquoi.


7. On change le code de get(int index) pour

     public E get(int index) {
       var size = this.size;  // volatile read
       var elements = this.elements;    // plain read
       if (size > elements.length) {
         throw new IllegalStateException("??");
       }
       Objects.checkIndex(index, size);
       var element = elements[index];   // plain read
       if (element != null) {
         return element;
       }
       while((element = (E) VH_ELEMENTS.getVolatile(elements, index)) == null) {  // volatile read
         Thread.onSpinWait();
       }
       return element;
     }
               

   Avec ce nouveau code, la classe ThreadSafeFixedList est-elle thread-safe ? Si oui ou non, expliquer pourquoi.

Exercice 2 - VectorizedIntView

public final class VectorizedIntView {
  private int[] elements;

  public VectorizedIntView(int... elements) {
    this.elements = elements;
  }

  public int size() {
    return elements.length;
  }

  public int get(int index) {
    Objects.checkIndex(index, size);
    return elements[index];
  }

  public boolean contains(int value) {
    throw new UnsupportedOperationException("TODO");
  }

  public int indexOf(int value) {
    throw new UnsupportedOperationException("TODO");
  }

  public record MinMax(int min, int max) {}

  public MinMax minMax(int fromIndex, int toIndex) {
    throw new UnsupportedOperationException("TODO");
  }

  public MinMax parallelMinMax() {
    throw new UnsupportedOperationException("TODO");
  }
}
            

var array = new int[] {3, 1, 4, 1, 5, 9, 2, 6};
var view = new VectorizedIntView(array);
IO.println(view.contains(9));             // true
IO.println(view.indexOf(5));              // 4
IO.println(view.minMax(0, view.size()));  // MinMax[min=1, max=9]
IO.println(view.parallelMinMax());        // MinMax[min=1, max=9]
            

1. Écrire la méthode contains en utilisant les opérations vectorisées, avec une post-loop pour traiter les éléments restants.
   Vérifier que les tests unitaires marqués "Q1" passent.


2. Écrire la méthode indexOf, toujours vectorisée avec une post-loop.
   Note : après avoir trouvé un bit à vrai dans le masque, il faut retrouver la position exacte du bit/lane où l'égalité est vraie dans le vecteur.
   Vérifier que les tests unitaires marqués "Q2" passent.


3. Écrire la méthode minMax(fromIndex, toIndex) qui calcule le minimum et le maximum en un seul passage vectorisé sur l'intervalle [fromIndex, toIndex).
   Dans le cas où il n'y a pas d'élément dans l'intervalle, une exception doit être levée.
   Vérifier que les tests unitaires marqués "Q3" passent.
   Note: si vous n'y arrivez pas, faite juste une version non-vectorizé et passez à la question suivante.


4. Écrire la méthode parallelMinMax qui calcule le minimum et le maximum sur toute la vue en utilisant fork/join, en réutilisant la méthode minMax écrite précédemment (pour les intervalles de moins de 1024 éléments), et en combinant deux résultats partiels en prenant le minimum des minimums et le maximum des maximums.
   Dans le cas où il n'y a pas d'élément, une exception doit être levée.
   Vérifier que les tests unitaires marqués "Q4" passent.