Qu'est-ce que le CAS (Compare-And-Swap) ?

Le Compare-And-Swap (CAS) est une instruction atomique, essentielle pour la programmation concurrente non bloquante. Il s'agit d'une opération primitive fournie par le matériel, garantissant que la vérification et la mise à jour d'une valeur se produisent comme une seule action indivisible. Le mécanisme CAS opère avec trois composants principaux :

• V (Valeur en Mémoire) : L'emplacement mémoire de la variable cible.
• A (Ancienne Valeur Attendue) : La valeur que l'on s'attend à trouver actuellement à l'emplacement V.
• B (Nouvelle Valeur) : La valeur à écrire à l'emplacement V si la condition est remplie.

En pratique, l'opération CAS vérifie si la valeur actuelle à l'adresse mémoire V est égale à l'ancienne valeur attendue A. Si c'est le cas, elle met à jour atomiquement V avec la nouvelle valeur B. Si les valeurs ne correspondent pas (c'est-à-dire que la valeur en mémoire a été modifiée par un autre thread entre-temps), l'opération échoue et aucune modification n'est effectuée.

Démonstration du CAS avec un Exemple Java

Pour illustrer la nécessité et l'efficacité du CAS, considérons un scénario simple d'incrémentation de compteurs par plusieurs threads en parallèle. Nous allons utiliser un compteur statique standard (non thread-safe) et un AtomicInteger (thread-safe grâce au CAS).

import java.util.concurrent.CountDownLatch;
import java.util.concurrent.atomic.AtomicInteger;

public class DemonstrationCAS {
    public static int compteurSimple = 0; // Compteur non atomique
    private final static int NB_THREADS_MAX = 10;
    private final static int ITERATIONS_PAR_THREAD = 1000;
    public static AtomicInteger compteurAtomique = new AtomicInteger(0); // Compteur atomique

    public static void main(String[] args) throws InterruptedException {
        // CountDownLatch permet à un ou plusieurs threads d'attendre que d'autres threads aient terminé
        CountDownLatch demarreur = new CountDownLatch(NB_THREADS_MAX);

        // Tâche d'incrémentation exécutée par chaque thread
        Runnable tacheIncrementation = () -> {
            for (int i = 0; i < ITERATIONS_PAR_THREAD; i++) {
                compteurSimple++; // Incrémentation non atomique, sujette aux problèmes de concurrence
                compteurAtomique.getAndIncrement(); // Incrémentation atomique utilisant CAS
            }
            demarreur.countDown(); // Informe que ce thread a terminé sa tâche
        };

        // Lancement de plusieurs threads
        for (int i = 0; i < NB_THREADS_MAX; i++) {
            new Thread(tacheIncrementation).start();
        }

        demarreur.await(); // Le thread principal attend que tous les autres threads soient terminés

        System.out.println("Résultat attendu : " + ITERATIONS_PAR_THREAD * NB_THREADS_MAX);
        System.out.println("Compteur simple (non-thread-safe) : " + compteurSimple);
        System.out.println("Compteur AtomicInteger (thread-safe) : " + compteurAtomique.get());
    }
}

L'exécution de ce programme produira un résultat similaire à celui-ci :

Résultat attendu : 10000
Compteur simple (non-thread-safe) : 9993
Compteur AtomicInteger (thread-safe) : 10000

Nous observons que le compteurSimple, incrémenté avec l'opérateur ++, donne un résultat incorrect et variable à chaque exécution. C'est parce que l'opération compteurSimple++ n'est pas atomique ; elle se décompose en plusieurs instructions (lecture, incrémentation, écriture) qui peuvent être interrompues par d'autres threads. En revanche, le compteurAtomique, utilisant AtomicInteger.getAndIncrement(), renvoie toujours la valeur correcte, illustrant l'efficacité du CAS pour garantir l'atomicité des opérations.

Classes Atomiques en Java (Package java.util.concurrent.atomic)

Le package java.util.concurrent.atomic (JUC) de Java fournit un ensemble de classes qui exploitent le mécanisme CAS pour offrir des opérations atomiques sur diverses structures de données. Ces classes sont fondamentales pour la construction d'applications concurrentes robustes sans avoir recours à des verrous explicites comme synchronized.

Les classes atomiques de JUC peuvent être regroupées en quatre catégories principales :

1. Classes Atomiques de Base

   Ces classes permettent des mises à jour atomiqeus de variables de types primitifs.

   • AtomicInteger : Pour les entiers (int).
   • AtomicLong : Pour les entiers longs (long).
   • AtomicBoolean : Pour les booléens (boolean).

2. Classes Atomiques pour Tableaux

   Ces classes offrent des opérations atomiques sur des éléments spécifiques au sein de tableaux.

   • AtomicIntegerArray : Tableau d'entiers atomiques.
   • AtomicLongArray : Tableau d'entiers longs atomiques.
   • AtomicReferenceArray : Tableau de références d'objets atomiques.

3. Types de Références Atomiques

   Ces classes étendent le concept de CAS pour gérer des références d'objets, parfois avec des informations supplémentaires pour résoudre des problèmes spécifiques.

   • AtomicReference : Référence d'objet atomique.
   • AtomicMarkableReference : Référence d'objet atomique avec un marqueur booléen (pour signaler qu'une valeur a été modifiée).
   • AtomicStampedReference : Référence d'objet atomique avec un "timestamp" ou numéro de version (pour résoudre le problème ABA).

   AtomicStampedReference est particulièrement utile pour mitiger le problème ABA en introduisant une notion de version.

4. Classes Atomiques de Mise à Jour de Champs

   Ces classes permettent d'effectuer des opérations atomiques sur des champs (attributs) spécifiques d'objets. Elles sont basées sur la réflexion et nécessitent que les champs soient volatile et non static.

   • AtomicIntegerFieldUpdater : Mises à jour atomiques pour les champs de type int.
   • AtomicLongFieldUpdater : Mises à jour atomiques pour les champs de type long.
   • AtomicReferenceFieldUpdater : Mises à jour atomiques pour les champs de type référence.

Exploration de la Classe AtomicInteger

AtomicInteger est l'une des classes atomiques les plus courantes. Elle fournit des méthodes pour effectuer des opérations atomiques sur une valeur entière.

Méthodes Courantes de AtomicInteger

Exemple d'Utilisation de AtomicInteger

import java.util.concurrent.atomic.AtomicInteger;

public class OperationsAtomicInteger {
    private static void afficherEvolution(String operation, int ancienneVal, int nouvelleVal) {
        System.out.println(operation + " - Ancienne valeur: " + ancienneVal + ", Nouvelle valeur: " + nouvelleVal);
    }

    public static void main(String[] args) {
        AtomicInteger compteurUnique = new AtomicInteger(5); // Initialisation à 5

        int valeurPrecedente = compteurUnique.getAndSet(10);
        afficherEvolution("getAndSet(10)", valeurPrecedente, compteurUnique.get());

        valeurPrecedente = compteurUnique.getAndIncrement();
        afficherEvolution("getAndIncrement()", valeurPrecedente, compteurUnique.get());

        valeurPrecedente = compteurUnique.getAndAdd(7);
        afficherEvolution("getAndAdd(7)", valeurPrecedente, compteurUnique.get());

        boolean reussie = compteurUnique.compareAndSet(18, 25);
        System.out.println("compareAndSet(18, 25) - Succès: " + reussie + ", Valeur finale: " + compteurUnique.get());

        reussie = compteurUnique.compareAndSet(100, 30); // Échec, car la valeur actuelle n'est pas 100
        System.out.println("compareAndSet(100, 30) - Succès: " + reussie + ", Valeur finale: " + compteurUnique.get());
    }
}

Résultat de l'exemple :

getAndSet(10) - Ancienne valeur: 5, Nouvelle valeur: 10
getAndIncrement() - Ancienne valeur: 10, Nouvelle valeur: 11
getAndAdd(7) - Ancienne valeur: 11, Nouvelle valeur: 18
compareAndSet(18, 25) - Succès: true, Valeur finale: 25
compareAndSet(100, 30) - Succès: false, Valeur finale: 25

Analyse du Code Source de AtomicInteger

Les opérations atomiques de AtomicInteger reposent sur une classe interne très puissante et "dangereuse" de la JVM : sun.misc.Unsafe. Voici un aperçu simplifié de son fonctionnement :

public class AtomicInteger extends Number implements java.io.Serializable {
    // Une instance de la classe Unsafe, permettant des opérations de bas niveau
    private static final sun.misc.Unsafe instanceUnsafe = sun.misc.Unsafe.getUnsafe();
    // L'offset mémoire du champ 'valeur' à l'intérieur d'un objet AtomicInteger
    private static final long decalageValeur;

    static {
        try {
            // Récupération de l'offset du champ 'valeur'
            decalageValeur = instanceUnsafe.objectFieldOffset(
                    AtomicInteger.class.getDeclaredField("valeur"));
        } catch (Exception ex) {
            throw new Error(ex);
        }
    }
    
    // Le champ qui contient la valeur réelle, marqué volatile pour garantir la visibilité
    private volatile int valeur; 

    // Constructeur et autres méthodes omises pour la clarté

    // Définit atomiquement la valeur donnée et retourne l'ancienne valeur.
    public final int getAndSet(int nouvelleValeur) {
        return instanceUnsafe.getAndSetInt(this, decalageValeur, nouvelleValeur);
    }

    // Incrémente atomiquement la valeur actuelle de 1 et retourne l'ancienne valeur.
    public final int getAndIncrement() {
        return instanceUnsafe.getAndAddInt(this, decalageValeur, 1);
    }

    // Décrémente atomiquement la valeur actuelle de 1 et retourne l'ancienne valeur.
    public final int getAndDecrement() {
        return instanceUnsafe.getAndAddInt(this, decalageValeur, -1);
    }

    // Ajoute atomiquement la valeur donnée à la valeur actuelle et retourne l'ancienne valeur.
    public final int getAndAdd(int delta) {
        return instanceUnsafe.getAndAddInt(this, decalageValeur, delta);
    }

    // La méthode compareAndSet est également implémentée via Unsafe, typiquement via compareAndSwapInt
    // public final boolean compareAndSet(int expect, int update) { ... }
}

Comme on peut le voir, les opérations atomiques comme getAndIncrement() ou getAndSet() délèguent leur travail à des méthodes de l'instance Unsafe. Ces méthodes, en particulier celles commençant par compareAndSwap... (ou leurs variantes comme getAndAdd... qui les utiliesnt en interne), appellent directement des instructions CPU de bas niveau (comme cmpxchg sur les architectures x86) pour assurer l'atomicité.

La Classe sun.misc.Unsafe

La classe sun.misc.Unsafe, comme son nom l'indique, est une API interne de la JVM qui permet des opérations de bas niveau sur la mémoire, similaires à celles disponibles en C/C++. Elle est normalement inaccessible aux développeurs d'applications Java, mais les classes du package java.util.concurrent.atomic l'utilisent intensivement pour leurs implémentations.

Méthodes CAS Fournies par Unsafe

Les méthodes de "comparaison et échange" clés d'Unsafe sont :

public final native boolean compareAndSwapObject(Object o, long offset, Object expected, Object update);
public final native boolean compareAndSwapInt(Object o, long offset, int expected, int update);
public final native boolean compareAndSwapLong(Object o, long offset, long expected, long update);

Ces méthodes natives prennent quatre arguments :

• o : L'objet contenant le champ à modifier.
• offset : Le décalage mémoire du champ à l'intérieur de l'objet o.
• expected : La valeur que le champ est censé contenir actuellement (l'ancienne valeur).
• update : La nouvelle valeur à attribuer au champ.

Elles comparent la valeur à l'emplacement mémoire spécifié (o et offset) avec la expected. Si elles sont identiques, la valeur est mise à jour avec update et la méthode retourne true. Sinon, aucune action n'est effectuée et la méthode retourne false.

Obtention des Décalages de Propriétés avec Unsafe

Unsafe fournit également des méthodes pour déterminer l'emplacement mémoire (décalage) d'un champ donné au sein d'une classe ou d'une instance :

public native long staticFieldOffset(java.lang.reflect.Field field);
public native long objectFieldOffset(java.lang.reflect.Field field);

• staticFieldOffset(Field field) : Récupère le décalage mémoire d'un champ static au sein de sa classe.
• objectFieldOffset(Field field) : Récupère le décalage mémoire d'un champ d'instance (non-static) au sein d'un objet.

Lecture de la Valeur d'un Champ Volatile par Décalage

Pour lire la valeur la plus récente d'un champ volatile à un décalage donné, Unsafe offre des méthodes comme :

public native int getIntVolatile(Object o, long fieldOffset);

• o : L'instance de l'objet qui contient le champ.
• fieldOffset : Le décalage du champ à lire.

Limites du CAS

Bien que le CAS soit un outil puissant pour la concurrence, il n'est pas sans inconvénients :

1. Le Problème ABA

   Le problème ABA survient lorsque la valeur d'une variable passe de A à B, puis de nouveau à A. Une opération CAS pourrait réussir en pensant que la valeur n'a pas changé depuis sa dernière lecture (elle est toujours A), alors qu'elle a en fait subi des modifications intermédiaires. Pour résoudre ce problème, le JDK propose les classes AtomicStampedReference (qui utilise un numéro de version ou "timestamp") et AtomicMarkableReference (qui utilise un simple drapeau booléen).

2. Atomicité Limitée à une Seule Variable

   Par défaut, le CAS ne garantit l'atomicité que pour une seule variable partagée. Si une opération implique plusieurs variables qui doivent être mises à jour atomiquement, un simple CAS sur chaque variable ne suffit pas. Une solution consiste à encapsuler les variables multiples dans un seul objet, puis à utiliser AtomicReference pour effectuer une opération CAS sur cette référence d'objet composite. Par exemple, si vous avez deux entiers i et j, vous pouvez les regrouper dans un objet Pair<Integer, Integer> et ensuite faire un CAS sur une AtomicReference<Pair<Integer, Integer>>.

3. Coût Élevé en Cas de Forte Contention

   En haute concurrence, si de nombreux threads tentent de modifier la même variable simultanément, la plupart des opérations CAS échoueront. Les threads échouant entrent souvent dans une boucle de "spin-waiting" (attente active), où ils réessayent l'opération CAS. Cela peut entraîner une consommation excessive de CPU et une réduction des performances si la contention est trop élevée. Des solutions pour atténuer ce problème incluent :

   • Dispersion des points chauds : Utiliser des classes comme LongAdder (introduite dans Java 8) ou DoubleAdder, qui réduisent la contention en distribuant les mises à jour sur plusieurs variables internes, puis en agrégeant les résultats.
   • Utilisation de files d'attente pour l'écrêtement : Dans certains cas, il est préférable d'ajouter les threads en attente dans une file d'attente et de les réveiller séquentiellement. C'est le principe de base de l'AbstractQueuedSynchronizer (AQS) dans JUC, qui est à la base de nombreux mécanismes de verrouillage et de synchronisation du JDK.