Lock-free : avec des VarHandle

Générateur aléatoire

On reprend l'exercice du TP précédent avec le générateur pseudo-aléatoire RandomNumberGenerator.java, et on souhaite en faire une nouvelle implémentation lock-free.

Un des inconvénients des champs Atomic est qu'ils alourdissent l'allocation nécessaire pour chaque objet. En effet, pour utiliser un long pour chaque objet générateur, il faut allouer un AtomicLong qui permettra lui-même d'accéder de manière atomique à la valeur d'un long, chaque accès nécessitant lui-même une indirection...

Utiliser la classe VarHandle et sa méthode compareAndSet pour obtenir une implantation lock-free du générateur pseudo-aléatoire. 

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) {
    RandomNumberGenerator rng = new RandomNumberGenerator(1);
    for(var i = 0; i < 5_000; i++) {
      System.out.println(rng.next());
    }
  }
}

Liste chaînée

On souhaite écrire une implantation de liste chaînée avec insertion en fin, concurrente et n'utilisant ni section critique, ni verrou. La liste devra posséder deux méthodes addLast(E e) et size() permettant respectivement d'ajouter un élément en fin de liste et d'obtenir la taille de la liste.

Le code de la classe LinkedList.java que nous vous fournissons est une implémentation naïve qui n'est pas thread-safe.

Détail d'implantation : pour éviter de gérer différemment le cas de la liste vide, une liste est créée initialement avec un faux maillon contenant la valeur null.

L'idée de l'algorithme concurrent est la suivante : pour éviter toute synchronisation lors de l'ajout, on récupère le maillon à la fin de la liste, puis on teste en utilisant une opération atomique si le maillon correspond toujours à la fin de la liste ; si oui, on lui assigne le nouveau maillon créé. Sinon (ce n'est déjà plus) le dernier maillon, on récupère de nouveau le maillon à la fin de la liste et on recommence la même opération...

Recopier le code de la classe LinkedList dans une classe LinkedListLockFree qui va implanter une liste thread-safe sans verrou. Dans un premier temps, implanter la méthode addLast. Pour cela vous utiliserez la classe VarHandle.

Comment doit-on modifier le code de la méthode size pour que la méthode soit thread-safe ?

On souhaite améliorer la complexité de la méthode addLast en maintenant, en plus d'une référence sur la tête de la liste (head), une référence sur la fin de la liste (tail). Modifier l'implantation de addLast pour utiliser le champs tail et le mettre à jour.

Ensemble concurrent

On souhaite écrire une implantation d'un ensemble (Set) concurrent et n'utilisant ni section critique, ni verrou. L'ensemble devra posséder deux méthodes add(E e) et size() permettant respectivement d'ajouter un élément à l'ensemble s'il ne le contient pas déjà et d'obtenir la taille de l'ensemble.

Le code de la classe BogusConcurrentSet.java que nous vous fournissons est une implémentation qui n'est pas thread-safe. L'implémentation est une table de hachage telle que les collisions sont gérées dans des tableaux, ce qui nous amène à manipuler un tableau à double entrée.

public class BogusConcurrentSet<E> {
  private final E[][] table;

  @SuppressWarnings("unchecked")
  public BogusConcurrentSet(int capacity) {
    this.table = (E[][]) new Object[capacity][];
    Arrays.setAll(table, i -> (E[]) new Object[0]);
  }

  public void add(E element) {
    Objects.requireNonNull(element);
    var index = element.hashCode() % table.length;
    for(var item: table[index]) {
      if (element.equals(item)) {
        return;
      }
    }
    var newArray = Arrays.copyOf(table[index], table[index].length + 1);
    newArray[newArray.length - 1] = element;
    table[index] = newArray;
  }

  public int size() {
    return Arrays.stream(table).mapToInt(array -> array.length).sum();
  }
}

Identifiez les problèmes de concurrence de la classe BogusConcurrentSet.

Remarque : pour rendre la classe thread-safe sans introduire des verrous ou des sections critiques, il va nous falloir un accès volatile aux cases du tableau table.

Expliquer pourquoi, dans cette implantation d'un ensemble, on n'agrandit pas une case de tableau en doublant sa taille (si vous ne voyez pas, essayer d'écrire le code de la question suivante et revenez à cette question ensuite).

Copiez la classe BogusConcurrentSet dans une classe ConcurrentSet et rendez la classe thread-safe en utilisant un VarHandle.

Copiez la classe BogusConcurrentSet dans une classe AtomicConcurrentSet et rendez la classe thread-safe en utilisant une classe du package java.util.concurrent.atomic.