Volatile, Opérations atomiques et CompareAndSet

Exercice 1 - A vos chronometres

public class Bogus {
  private boolean stop;

  public void runCounter() {
    var localCounter = 0;
    for(;;) {
      if (stop) {
        break;
      }
      localCounter++;
    }
    System.out.println(localCounter);
  }

  public void stop() {
    stop = true;
  }

  public static void main(String[] args) throws InterruptedException {
    var bogus = new Bogus();
    var thread = new Thread(bogus::runCounter);
    thread.start();
    Thread.sleep(100);
    bogus.stop();
    thread.join();
  }
}  

1. Sans exécuter le code, que fait ce programme ?
2. Vérifier, en exécutant le programme (plusieurs fois), si vous avez vu juste.
3. Comment doit-on corriger le problème ?
   Modifier la classe Bogus en conséquence.
4. On cherche maintenant à accélérer le code de Bogus en utilisant le mot clé volatile au lieu des blocs synchronized.
   Créer une classe BogusVolatile qui n'utilise pas de bloc synchronized.
   Comment appelle-t-on les implantations qui n'ont ni bloc synchronized, ni lock ?

Exercice 2 - Compteur

   public class Counter {
     private int counter;
     
     public int nextInt() {
       return counter++;
     }
   }
  

1. Expliquer pourquoi le code ci-dessus n'est pas thread-safe ?
   Écrire un main démontrant le problème.
2. Que se passe-t-il si on déclare le champ counter volatile ?
3. A quoi correspond la valeur de retrour de la méthode compareAndSet de la classe AtomicInteger ?
   Utiliser la méthode compareAndSet pour créer une implantation thread-safe de la classe Counter.
4. A quoi sert la méthode getAndIncrement de la classe AtomicInteger ?
   Créer une nouvelle classe Counter2, marchant comme Counter, utilisant la méthode getAndIncrement pour obtenir une implantation thread-safe.
5. Que veut dire le terme lock-free pour un algorithme ?
   Les implantations Counter et Counter2 sont-elles lock-free ?

Exercice 3 - Liste chainée lock-free

    public class Linked<E> {
      private record Link<E>(E value, Link<E> next) {
        private Link {
          Objects.requireNonNull(value);
        }
      }

      private Link<E> head;

      /**
       * Adds a non-null value at the start of the list
       */
      public void addFirst(E value) {
        Objects.requireNonNull(value);
        head = new Link<>(value, head);
      }

      /**
       * Applies the consumer to the elements of the list in order
       */
      public void forEach(Consumer<? super E> consumer) {
        Objects.requireNonNull(consumer);
        for (var current = head; current != null; current = current.next) {
          consumer.accept(current.value);
        }
      }

      public static void main(String[] args) {
        var list = new Linked<String>();
        list.addFirst("foo");
        list.addFirst("bar");
        list.addFirst("baz");
        list.forEach(System.out::println);
      }
    }
  

1. Expliquer pourquoi le code ci-dessus n'est pas thread-safe ?
   Écrire un main démontrant le problème.
2. Modifier votre implantation pour rendre la classe Linked thread-safe (et lock-free) utilisant la classe AtomicReference et sa méthode compareAndSet.
3. Expliquer pourquoi utiliser la classe AtomicReference n'est pas super efficace ?
4. On souhaite ajouter la méthode pollFirst qui enlève le premier élément ou renvoie null s'il n'y a pas de premier élément.
   Voici le code non-thread safe de pollFirst :

          /**
           * Removes the first value of the list, otherwise, returns null.
           */
          public E pollFirst() {
            if (head == null) {
              return null;
            }
            var value = head.value;
            head = head.next;
            return value;
          }
        

   Écrire une version lock-free de pollFirst.
5. Créer une classe Linked2 thread-safe (et lock-free) utilisant la classe VarHandle au lieu de la classe AtomicReference.
   Rappel: les types paramétrés sont érasés à l'exécution !
6. A quoi sert la méthode withInvokeExactBehavior() ?
   Comment doit-on l'utiliser dans Linked2 ?
   Faites les changements qui s'imposent.