Introduction aux plates-formes SMP pour Android

Les versions de la plate-forme Android 3.0 et versions ultérieures sont optimisées pour prendre en charge les architectures multiprocesseurs. Ce document présente des problèmes qui peuvent survenir lors de l'écriture de code multithread pour les systèmes multiprocesseurs symétriques en C, C++ et le langage de programmation Java (appelés ci-après simplement "Java" par souci de concision). Il s'agit d'une introduction aux développeurs d'applications Android, et non d'une discussion complète sur le sujet.

Introduction

SMP est l'acronyme de "Symmetric Multi-Processor". Il décrit une conception dans laquelle deux ou plusieurs cœurs de processeur identiques partagent l'accès à la mémoire principale. Jusqu'à il y a quelques années, tous les appareils Android étaient opérationnels (Uni-Processor).

La plupart, voire la totalité, des appareils Android avaient toujours plusieurs processeurs, mais auparavant, un seul d'entre eux était utilisé pour exécuter des applications, tandis que d'autres géraient plusieurs éléments matériels de l'appareil (par exemple, la radio). Les processeurs peuvent avoir des architectures différentes, et les programmes exécutés sur ceux-ci ne pouvaient pas utiliser la mémoire principale pour communiquer entre eux.

La plupart des appareils Android vendus aujourd'hui sont construits autour de conceptions de SMP, ce qui complique un peu plus les choses pour les développeurs de logiciels. Les conditions de concurrence dans un programme multithread peuvent ne pas causer de problèmes visibles sur un monoprocesseur, mais elles peuvent échouer régulièrement lorsque deux ou plusieurs threads s'exécutent simultanément sur des cœurs différents. De plus, le code peut être plus ou moins sujet aux défaillances lorsqu'il est exécuté sur différentes architectures de processeur, ou même sur différentes implémentations de la même architecture. Le code qui a été minutieusement testé sur x86 peut présenter des dysfonctionnements sur ARM. Le code peut commencer à échouer lorsqu'il est recompilé avec un compilateur plus récent.

Le reste de ce document vous expliquera pourquoi et ce que vous devez faire pour vous assurer que votre code se comporte correctement.

Modèles de cohérence de la mémoire: pourquoi les plates-formes de réseaux sociaux sont un peu différentes

Il s'agit d'un aperçu rapide et brillant d'un sujet complexe. Certains aspects seront incomplets, mais aucun d'entre eux ne devrait être trompeur ou faux. Comme vous le verrez dans la section suivante, ces détails ne sont généralement pas importants.

Consultez la section Complément d'informations à la fin du document pour découvrir des traitements plus approfondis du sujet.

Les modèles de cohérence de la mémoire, ou simplement "modèles de mémoire", décrivent les garanties offertes par le langage de programmation ou l'architecture matérielle concernant l'accès à la mémoire. Par exemple, si vous écrivez une valeur pour l'adresse A, puis une valeur pour l'adresse B, le modèle peut garantir que chaque cœur de processeur verra ces écritures se produire dans cet ordre.

Le modèle auquel la plupart des programmeurs sont habitués est la cohérence séquentielle, décrite comme (Adve & Gharachorloo):

• Toutes les opérations de mémoire semblent s'exécuter une par une
• Toutes les opérations d'un même thread semblent s'exécuter dans l'ordre décrit par le programme de ce processeur.

Supposons que nous disposons temporairement d'un compilateur ou d'un interpréteur très simple qui ne présente aucune surprise: il traduit les attributions dans le code source pour charger et stocker les instructions exactement dans l'ordre correspondant, à raison d'une instruction par accès. Pour des raisons de simplicité, nous partirons également du principe que chaque thread s'exécute sur son propre processeur.

Si vous examinez un peu de code et constatez qu'il effectue des lectures et des écritures à partir de la mémoire, sur une architecture de processeur cohérente de manière séquentielle, vous savez que le code effectue ces opérations de lecture et d'écriture dans l'ordre attendu. Il est possible que le processeur réorganise les instructions et retarde les lectures et les écritures, mais il n'y a aucun moyen pour que le code exécuté sur l'appareil indique que le processeur effectue autre chose que l'exécution d'instructions de manière simple. (Nous allons ignorer les E/S du pilote de périphérique mappés en mémoire.)

Pour illustrer ces points, il est utile d'utiliser de petits extraits de code, couramment appelés tests de litmus.

Voici un exemple simple dans lequel le code s'exécute sur deux threads:

Thread 1	Thread 2
A = 3 B = 5	reg0 = B reg1 = A

Dans cet exemple et dans tous les suivants, les emplacements de mémoire sont représentés par des lettres majuscules (A, B, C), et les registres de processeur commencent par "reg". La mémoire est initialement égale à zéro. Les instructions sont exécutées de haut en bas. Ici, le thread 1 stocke la valeur 3 à l'emplacement A, puis la valeur 5 à l'emplacement B. Le thread 2 charge la valeur de l'emplacement B dans reg0, puis charge la valeur de l'emplacement A dans reg1. (Notez que nous écrivons dans un ordre et lisons dans un autre.)

Les threads 1 et 2 sont supposés s'exécuter sur des cœurs de processeur différents. Vous devez toujours faire cette hypothèse lorsque vous pensez à du code multithread.

La cohérence séquentielle garantit qu'une fois l'exécution des deux threads terminée, les registres sont dans l'un des états suivants:

Registres	États
reg0=5, reg1=3	possible (thread 1 exécuté en premier)
reg0=0, reg1=0	possible (thread 2 exécuté en premier)
reg0=0, reg1=3	possible (exécution simultanée)
reg0=5, reg1=0	jamais

Pour arriver à une situation où nous voyons B=5 avant de voir le magasin vers A, les lectures ou les écritures doivent se produire dans le désordre. Cela n'est pas possible sur une machine à cohérence séquentielle.

Les processeurs mono, y compris x86 et ARM, sont normalement cohérents de manière séquentielle. Les threads semblent s'exécuter de manière entrelacée, lorsque le noyau de l'OS passe de l'un à l'autre. La plupart des systèmes SMP, y compris x86 et ARM, ne sont pas cohérents de manière séquentielle. Par exemple, il est courant que le matériel mette en mémoire tampon les magasins lorsqu'ils sont acheminés vers la mémoire, de sorte qu'ils n'atteignent pas immédiatement la mémoire et ne deviennent pas visibles par les autres cœurs.

Les détails varient considérablement. Par exemple, bien qu'il ne soit pas cohérent sur le plan séquentielle, x86 garantit toujours que reg0 = 5 et reg1 = 0 reste impossible. Les magasins sont mis en mémoire tampon, mais leur ordre est conservé. En revanche, ARM ne le fait pas. L'ordre des magasins mis en mémoire tampon n'est pas conservé, et les magasins peuvent ne pas atteindre tous les autres cœurs en même temps. Ces différences sont importantes pour les programmeurs. Toutefois, comme nous le verrons ci-dessous, les programmeurs C, C++ ou Java peuvent et doivent programmer de manière à masquer ces différences architecturales.

Jusqu'à présent, nous avons supposé irréaliste que seul le matériel réorganise les instructions. En réalité, le compilateur réorganise également les instructions pour améliorer les performances. Dans notre exemple, le compilateur peut décider qu'un code ultérieur dans Thread 2 a besoin de la valeur de reg1 avant reg0, et charge donc reg1 en premier. Il se peut également qu'un code précédent ait déjà chargé A et que le compilateur puisse décider de réutiliser cette valeur au lieu de charger à nouveau A. Dans les deux cas, les chargements dans reg0 et reg1 peuvent être réorganisés.

La réorganisation des accès à différents emplacements de mémoire, dans le matériel ou dans le compilateur, est autorisée, car cela n'affecte pas l'exécution d'un seul thread et peut améliorer considérablement les performances. Comme nous le verrons, avec un peu de précaution, nous pouvons également l'empêcher d'affecter les résultats des programmes multithread.

Étant donné que les compilateurs peuvent également réorganiser les accès à la mémoire, ce problème n'est en fait pas nouveau pour les plates-formes SMP. Même sur un monoprocesseur, un compilateur peut réorganiser les chargements vers reg0 et reg1 dans notre exemple, et le thread 1 pourrait être programmé entre les instructions réorganisées. Mais si notre compilateur ne réorganise pas les données, il est possible que nous n'observions jamais ce problème. Sur la plupart des plates-formes SMP ARM, même sans réorganisation du compilateur, cette réorganisation se produira probablement après un très grand nombre d'exécutions réussies. À moins que vous ne programmiez en langage assembleur, les plates-formes SMP augmentent généralement la probabilité de rencontrer des problèmes depuis le début.

Programmation sans racismes de données

Heureusement, il existe généralement un moyen simple d'éviter de penser à ces détails. Si vous suivez des règles simples, vous pouvez généralement oublier toutes les sections précédentes, à l'exception de la partie "cohérence séquentielle". Malheureusement, les autres complications peuvent s'afficher si vous enfreignez accidentellement ces règles.

Les langages de programmation modernes encouragent ce que l'on appelle un style de programmation "sans origine ethnique". Tant que vous vous engagez à ne pas introduire de "courses de données" et à éviter quelques constructions indiquant le contraire au compilateur, le compilateur et le matériel promettent de fournir des résultats cohérents de manière séquentielle. Cela ne signifie pas qu'ils évitent la réorganisation de l'accès à la mémoire. Cela signifie que si vous suivez les règles, vous ne pourrez pas savoir si les accès à la mémoire sont en cours de réorganisation. Cela revient à vous dire que la saucisse est un plat délicieux et appétissant, tant que vous promettez de ne pas visiter la fabrique de saucisses. Ce sont les courses de données qui révèlent la mauvaise vérité concernant la réorganisation de la mémoire.

Qu'est-ce qu'une "course aux données" ?

Une course de données se produit lorsqu'au moins deux threads accèdent simultanément aux mêmes données ordinaires et qu'au moins l'un d'eux les modifie. Par "données ordinaires", nous entendons tout élément qui n'est pas spécifiquement un objet de synchronisation destiné à la communication de threads. Les mutex, les variables de condition, les volatiles Java ou les objets atomiques C++ ne sont pas des données ordinaires, et leurs accès sont autorisés à entrer en concurrence. En fait, ils sont utilisés pour éviter les courses de données sur d'autres objets.

Pour déterminer si deux threads accèdent simultanément au même emplacement de mémoire, nous pouvons ignorer la discussion sur la réorganisation de la mémoire ci-dessus et supposer une cohérence séquentielle. Le programme suivant n'a pas de concurrence de données si A et B sont des variables booléennes ordinaires dont la valeur initiale est "false" :

Thread 1	Thread 2
if (A) B = true	if (B) A = true

Comme les opérations ne sont pas réorganisées, les deux conditions seront évaluées sur "false" et aucune variable n'est jamais mise à jour. Il ne peut donc pas y avoir de concurrence des données. Il n'est pas nécessaire de réfléchir à ce qui pourrait se produire si la charge de A et le stockage vers B dans le thread 1 étaient réorganisés d'une manière ou d'une autre. Le compilateur n'est pas autorisé à réorganiser Thread 1 en le réécrivant sous la forme "B = true; if (!A) B = false". Cela équivaudrait à faire de la saucisse en ville en plein jour.

Les courses de données sont officiellement définies sur des types intégrés de base tels que des entiers, des références ou des pointeurs. L'attribution à un int tout en le lisant simultanément dans un autre thread constitue clairement une course de données. Toutefois, la bibliothèque standard C++ et les bibliothèques Java Collections sont écrites pour vous permettre de réfléchir aux courses de données au niveau de la bibliothèque. Elles promettent de ne pas introduire de concurrences de données à moins qu'il n'y ait des accès simultanés au même conteneur, et au moins l'un de ceux-ci le met à jour. Mettre à jour un set<T> dans un thread tout en le lisant simultanément dans un autre permet à la bibliothèque d'introduire une course de données et peut donc être considérée de manière informelle comme une "course de données au niveau de la bibliothèque". À l'inverse, la mise à jour d'une set<T> dans un thread, tout en lisant une autre dans un autre, n'entraîne pas de course de données, car la bibliothèque promet de ne pas introduire de concurrence (de bas niveau) pour les données dans ce cas.

Normalement, les accès simultanés à différents champs d'une structure de données ne peuvent pas introduire une concurrence entre les données. Cependant, il existe une exception importante à cette règle: les séquences contiguës de champs de bits en C ou C++ sont traitées comme un seul "emplacement de mémoire". L'accès à n'importe quel champ de bits d'une telle séquence est considéré comme un accès à tous les champs afin de déterminer l'existence d'une course de données. Cela reflète l'incapacité du matériel commun à mettre à jour des bits individuels sans lire et réécrire les bits adjacents. Les programmeurs Java n'ont pas les mêmes préoccupations.

Éviter les courses de données

Les langages de programmation modernes fournissent un certain nombre de mécanismes de synchronisation pour éviter les conflits de données. Les outils les plus élémentaires sont les suivants:

Verrous ou mutex

Les blocs mutex (C++11 std::mutex, ou pthread_mutex_t) ou synchronized en Java permettent de s'assurer qu'une certaine section de code ne s'exécute pas simultanément avec d'autres sections de code accédant aux mêmes données. Ces installations et d'autres installations similaires sont généralement appelées "serrures". L'acquisition systématique d'un verrou spécifique avant d'accéder à une structure de données partagée et sa libération par la suite permettent d'éviter les courses de données lors de l'accès à la structure de données. Il garantit également que les mises à jour et les accès sont atomiques, c'est-à-dire qu'aucune autre mise à jour de la structure de données ne peut s'exécuter au milieu. C'est de loin l'outil le plus courant pour éviter les concurrences de données. L'utilisation de blocs synchronized Java ou de C++ lock_guard ou unique_lock garantit que les verrous sont correctement libérés en cas d'exception.

Variables volatiles/atomiques

Java fournit des champs volatile qui acceptent l'accès simultané sans introduire de concurrences de données. Depuis 2011, C et C++ sont compatibles avec les variables atomic et les champs ayant une sémantique similaire. Elles sont généralement plus difficiles à utiliser que les verrous, car ils garantissent uniquement que les accès individuels à une seule variable sont atomiques. (En C++, cela s'étend généralement aux opérations de lecture-modification-écriture simples, telles que les incréments. Java nécessite des appels de méthode spéciaux pour cela.) Contrairement aux verrous, les variables volatile ou atomic ne peuvent pas être utilisées directement pour empêcher d'autres threads d'interférer avec des séquences de code plus longues.

Il est important de noter que volatile a des significations très différentes en C++ et en Java. En C++, volatile n'empêche pas les courses de données, bien que le code plus ancien l'utilise souvent comme solution de contournement pour l'absence d'objets atomic. Ce n'est plus recommandé. En C++, utilisez atomic<T> pour les variables auxquelles plusieurs threads peuvent accéder simultanément. C++ volatile est destiné aux registres d'appareil et autres.

Les variables atomic C/C++ ou les variables Java volatile peuvent être utilisées pour éviter les courses de données sur d'autres variables. Si flag est déclaré comme étant de type atomic<bool>, atomic_bool(C/C++) ou volatile boolean (Java) et qu'il a initialement la valeur "false", l'extrait suivant est sans origine ethnique:

Thread 1	Thread 2
A = ...   flag = true	while (!flag) {} ... = A

Étant donné que le thread 2 attend que flag soit défini, l'accès à A dans le thread 2 doit avoir lieu après l'attribution à A dans le thread 1, et non simultanément. Il n'y a donc pas de concurrence des données sur A. La course sur flag ne compte pas comme une course de données, car les accès volatiles/atomiques ne sont pas des "accès ordinaires à la mémoire".

L'implémentation est nécessaire pour empêcher ou masquer suffisamment la réorganisation de la mémoire pour que le code se comporte comme prévu. Cela rend généralement les accès à la mémoire volatile/atomique beaucoup plus chers que les accès ordinaires.

Bien que l'exemple précédent ne fasse pas l'objet d'une course de données, les verrouillages avec Object.wait() en Java ou les variables de condition en C/C++ offrent généralement une meilleure solution qui n'implique pas d'attendre dans une boucle tout en déchargeant la batterie.

Quand la réorganisation de la mémoire devient visible

La programmation sans origine ethnique nous évite normalement d'avoir à gérer explicitement les problèmes de réorganisation des accès à la mémoire. Toutefois, dans plusieurs cas, la réorganisation devient visible :

1. Si votre programme présente un bug entraînant une course involontaire de données, les transformations du compilateur et du matériel peuvent devenir visibles, et le comportement de votre programme peut être surprenant. Par exemple, si nous avons oublié de déclarer la valeur volatile de flag dans l'exemple précédent, le thread 2 peut voir une A non initialisée. Ou bien le compilateur peut décider que l'indicateur ne peut pas être modifié pendant la boucle du thread 2 et transformer le programme en

   Thread 1	Thread 2
   A = ...   flag = true	reg0 = flag; while (!reg0) {} ... = = A

   Lors du débogage, il est possible que la boucle se poursuive indéfiniment même si flag est vrai.
2. C++ fournit des installations permettant d'assouplir explicitement la cohérence séquentielle, même en l'absence de races. Les opérations atomiques peuvent prendre des arguments memory_order_... explicites. De même, le package java.util.concurrent.atomic fournit un ensemble plus restreint d'installations similaires, notamment lazySet(). Les programmeurs Java utilisent parfois des courses de données intentionnelles pour obtenir un effet similaire. Tous ces éléments améliorent les performances, et cela engendre un coût élevé en termes de complexité de la programmation. Nous n'en parlerons que brièvement ci-dessous.
3. Certains codes C et C++ sont écrits dans un style plus ancien, qui n'est pas entièrement conforme aux normes de langage actuelles, dans lequel les variables volatile sont utilisées à la place de atomic, et l'ordre de la mémoire est explicitement interdit en insérant ce que l'on appelle des barrières ou des barrières. Cela nécessite un raisonnement explicite concernant la réorganisation des accès et la compréhension des modèles de mémoire matérielle. Un style de codage le long de ces lignes est toujours utilisé dans le noyau Linux. Il ne doit pas être utilisé dans les nouvelles applications Android. Nous n'en parlerons pas plus en détail ici.

S'entraîner

Le débogage des problèmes de cohérence de la mémoire peut s'avérer très difficile. Si un verrou manquant, atomic ou volatile entraîne la lecture de données obsolètes par du code, vous ne pourrez peut-être pas en comprendre la raison en examinant les vidages de mémoire avec un débogueur. Au moment où vous pouvez émettre une requête de débogage, il est possible que les cœurs de processeur aient tous observé l'ensemble des accès. Le contenu de la mémoire et des registres de processeur apparaît alors dans un état "impossible".

Ce qu'il ne faut pas faire en C

Voici quelques exemples de code incorrect, ainsi que des moyens simples de les corriger. Avant cela, nous devons discuter de l'utilisation d'une fonctionnalité de langage de base.

C/C++ et "volatile"

Les déclarations volatile C et C++ constituent un outil très spécial. Ils empêchent le compilateur de réorganiser ou de supprimer les accès volatils. Cela peut être utile pour le code qui accède aux registres de périphériques matériels, pour la mémoire mappée à plusieurs emplacements ou en lien avec setjmp. Toutefois, contrairement au volatile Java, le volatile C et C++ n'est pas conçu pour la communication de threads.

En C et C++, les accès aux données volatile peuvent être réorganisés avec l'accès aux données non volatiles, et il n'y a aucune garantie d'atomicité. Ainsi, volatile ne peut pas être utilisé pour partager des données entre des threads en code portable, même sur un monoprocesseur. Cvolatile n'empêche généralement pas la réorganisation des accès par le matériel. Il est donc encore moins utile dans les environnements SMP multithread. C'est la raison pour laquelle C11 et C++11 acceptent les objets atomic. Vous devriez les utiliser à la place.

Un grand nombre d'anciens codes C et C++ abusent toujours de volatile pour la communication de threads. Cela fonctionne souvent correctement pour les données qui rentrent dans un registre de machine, à condition qu'elles soient utilisées avec des barrières explicites ou dans les cas où l'ordre de la mémoire n'est pas important. Mais cela n'est pas garanti pour fonctionner correctement avec les futurs compilateurs.

Exemples

Dans la plupart des cas, il est préférable d'utiliser un verrou (comme un pthread_mutex_t ou un std::mutex C++11) plutôt qu'une opération atomique, mais nous utiliserons cette dernière pour illustrer leur utilisation dans une situation pratique.

MyThing* gGlobalThing = NULL;  // Wrong!  See below.
void initGlobalThing()    // runs in Thread 1
{
    MyStruct* thing = malloc(sizeof(*thing));
    memset(thing, 0, sizeof(*thing));
    thing->x = 5;
    thing->y = 10;
    /* initialization complete, publish */
    gGlobalThing = thing;
}
void useGlobalThing()    // runs in Thread 2
{
    if (gGlobalThing != NULL) {
        int i = gGlobalThing->x;    // could be 5, 0, or uninitialized data
        ...
    }
}

L'idée ici est d'allouer une structure, d'initialiser ses champs, puis de la "publier" à la fin en la stockant dans une variable globale. À ce stade, n'importe quel autre thread peut le voir, mais ce n'est pas un problème puisqu'il est entièrement initialisé.

Le problème est que le magasin vers gGlobalThing peut être observé avant l'initialisation des champs, généralement parce que le compilateur ou le processeur a réorganisé les magasins vers gGlobalThing et thing->x. Un autre thread qui lisait à partir de thing->x pourrait voir 5, 0 ou même des données non initialisées.

Le problème principal ici est une course aux données sur gGlobalThing. Si le thread 1 appelle initGlobalThing() alors que le thread 2 appelle useGlobalThing(), gGlobalThing peut être lu pendant l'écriture.

Pour résoudre ce problème, déclarez gGlobalThing comme atomique. En C++11:

atomic<MyThing*> gGlobalThing(NULL);

Cela garantit que les écritures seront visibles pour les autres threads dans le bon ordre. Il garantit également d'éviter d'autres modes de défaillance autorisés par ailleurs, mais qui ne se produiront probablement pas sur du matériel Android réel. Par exemple, cela garantit que nous ne pouvons pas voir un pointeur gGlobalThing qui n'a été que partiellement écrit.

Ce qu'il ne faut pas faire en Java

Nous n'avons pas abordé certaines fonctionnalités pertinentes du langage Java. Nous allons donc commencer par les examiner rapidement.

Techniquement, Java n'a pas besoin de code pour éliminer les origines ethniques de données. De plus, il existe une petite quantité de code Java soigneusement rédigé qui fonctionne correctement en présence de courses de données. Cependant, l'écriture d'un tel code est extrêmement complexe, et nous n'en parlerons que brièvement ci-dessous. Pour ne rien arranger, les experts qui ont spécifié la signification de ce code ne pensent plus que la spécification est correcte. (La spécification est acceptable pour le code sans race de données.)

Pour l'instant, nous allons adhérer au modèle sans origine ethnique de données, pour lequel Java fournit essentiellement les mêmes garanties que C et C++. Là encore, le langage fournit des primitives qui assouplissent explicitement la cohérence séquentielle, en particulier les appels lazySet() et weakCompareAndSet() dans java.util.concurrent.atomic. Comme pour C et C++, nous allons les ignorer pour le moment.

Mots clés "synchronisés" et "volatiles" de Java

Le mot clé "synchronized" fournit le mécanisme de verrouillage intégré du langage Java. Chaque objet est associé à un "contrôle" qui peut être utilisé pour fournir un accès mutuellement exclusif. Si deux threads tentent de se "synchroniser" sur le même objet, l'un d'eux attend que l'autre se termine.

Comme indiqué ci-dessus, le volatile T de Java est l'analogique du atomic<T> de C++11. Les accès simultanés aux champs volatile sont autorisés et n'entraînent pas de concurrences de données. À l'exception de lazySet() et al. et des courses de données, la tâche de la VM Java est de s'assurer que le résultat s'affiche toujours de manière séquentielle.

En particulier, si le thread 1 écrit dans un champ volatile, et que le thread 2 lit ensuite dans ce même champ et voit la valeur nouvellement écrite, le thread 2 aura également la garantie de voir toutes les écritures effectuées précédemment par le thread 1. En termes d'effet sur la mémoire, l'écriture sur une valeur volatile est semblable à une version de contrôle, et la lecture à partir d'une source volatile est semblable à une acquisition de moniteur.

Il existe une différence notable par rapport à la méthode atomic de C++ : si nous écrivons volatile int x; en Java, x++ est identique à x = x + 1. Il effectue une charge atomique, incrémente le résultat, puis effectue un magasin atomique. Contrairement à C++, l'incrément dans son ensemble n'est pas atomique. Les opérations d'incrément atomique sont à la place fournies par java.util.concurrent.atomic.

Exemples

Voici une implémentation simple et incorrecte d'un compteur monotone: (Théorie et pratique de Java: gérer les fluctuations).

class Counter {
    private int mValue;
    public int get() {
        return mValue;
    }
    public void incr() {
        mValue++;
    }
}

Supposons que get() et incr() soient appelés à partir de plusieurs threads et que nous voulons nous assurer que chaque thread voit le nombre actuel lorsque get() est appelé. Le problème le plus flagrant est que mValue++ correspond en réalité à trois opérations:

1. reg = mValue
2. reg = reg + 1
3. mValue = reg

Si deux threads s'exécutent simultanément dans incr(), l'une des mises à jour peut être perdue. Pour rendre l'incrément atomique, nous devons déclarer incr() "synchronisé".

Cependant, elle ne fonctionne pas, en particulier sur les plates-formes SMP. Il existe toujours une concurrence des données, dans la mesure où get() peut accéder à mValue en même temps que incr(). Sous les règles Java, l'appel get() peut sembler être réorganisé par rapport à un autre code. Par exemple, si nous lisons deux compteurs à la suite, les résultats peuvent sembler incohérents, car les appels get() que nous avons réorganisés, par le matériel ou le compilateur. Nous pouvons corriger le problème en déclarant get() pour être synchronisé. Avec cette modification, le code est évidemment correct.

Malheureusement, nous avons introduit la possibilité de conflits de verrouillage, qui pourraient entraver les performances. Au lieu de déclarer get() comme synchronisé, nous pourrions déclarer mValue avec "volatile". (Remarque : incr() doit toujours utiliser synchronize, car mValue++ n'est sinon pas une opération atomique unique.) Cela évite également toutes les courses de données et préserve la cohérence séquentielle. incr() sera un peu plus lent, car il entraîne à la fois une surcharge de surveillance des entrées/sorties et la surcharge associée à un magasin volatile. Toutefois, get() sera plus rapide. Par conséquent, même en l'absence de conflit, c'est une victoire si les lectures dépassent considérablement le nombre d'écritures. (Consultez également AtomicInteger pour savoir comment supprimer complètement le bloc synchronisé.)

Voici un autre exemple, semblable aux exemples C précédents:

class MyGoodies {
    public int x, y;
}
class MyClass {
    static MyGoodies sGoodies;
    void initGoodies() {    // runs in thread 1
        MyGoodies goods = new MyGoodies();
        goods.x = 5;
        goods.y = 10;
        sGoodies = goods;
    }
    void useGoodies() {    // runs in thread 2
        if (sGoodies != null) {
            int i = sGoodies.x;    // could be 5 or 0
            ....
        }
    }
}

Cela présente le même problème que le code C, à savoir qu'il existe une concurrence de données sur sGoodies. Ainsi, l'attribution sGoodies = goods peut être observée avant l'initialisation des champs dans goods. Si vous déclarez sGoodies avec le mot clé volatile, la cohérence séquentielle est restaurée, et tout fonctionnera comme prévu.

Notez que seule la référence sGoodies elle-même est volatile. Les accès aux champs qu'il contient ne le sont pas. Une fois que sGoodies est défini sur volatile et que l'ordre de la mémoire est correctement préservé, les champs ne sont plus accessibles simultanément. L'instruction z = sGoodies.x effectue une charge volatile de MyClass.sGoodies suivie d'une charge non volatile de sGoodies.x. Si vous créez une référence locale MyGoodies localGoods = sGoodies, une z = localGoods.x ultérieure n'effectuera aucune charge volatile.

Un idiome plus courant en programmation Java est le tristement célèbre "verrouillage en double contrôlé" :

class MyClass {
    private Helper helper = null;
    public Helper getHelper() {
        if (helper == null) {
            synchronized (this) {
                if (helper == null) {
                    helper = new Helper();
                }
            }
        }
        return helper;
    }
}

L'idée est que nous voulons qu'une seule instance d'un objet Helper soit associée à une instance de MyClass. Nous ne devons le créer qu'une seule fois. Nous le créons et le renvoyons donc via une fonction getHelper() dédiée. Pour éviter une concurrence dans laquelle deux threads créent l'instance, nous devons synchroniser la création de l'objet. Toutefois, nous ne voulons pas payer les frais généraux liés au bloc "synchronisé" à chaque appel. Nous n'effectuons donc cette partie que si la valeur helper est actuellement nulle.

Il y a une course de données sur le champ helper. Il peut être défini simultanément avec le helper == null dans un autre thread.

Pour voir comment cela peut échouer, considérez que le même code a été légèrement réécrit, comme s'il était compilé dans un langage de type C (j'ai ajouté quelques champs d'entiers pour représenter l'activité du constructeur Helper’s):

if (helper == null) {
    synchronized() {
        if (helper == null) {
            newHelper = malloc(sizeof(Helper));
            newHelper->x = 5;
            newHelper->y = 10;
            helper = newHelper;
        }
    }
    return helper;
}

Rien n'empêche le matériel ou le compilateur de réorganiser le magasin vers helper avec ceux des champs x/y. Un autre thread peut trouver helper non nul, mais ses champs ne sont pas encore définis et prêts à être utilisés. Pour en savoir plus sur les différents modes de défaillance et en savoir plus, consultez le lien "Double Checked Locking is Broken" dans l'annexe concernant la déclaration, ou l'article 71 ("Utilisez l'initialisation différée de manière réfléchie") dans l'ouvrage Effective Java, 2nd Edition de Josh Bloch.

Vous disposez de deux options pour corriger ces erreurs :

1. Faites la chose la plus simple et supprimez la vérification externe. Cela garantit que nous n'examinons jamais la valeur de helper en dehors d'un bloc synchronisé.
2. Déclarez helper comme volatil. Avec cette petite modification, le code de l'exemple J-3 fonctionnera correctement sur Java 1.5 et versions ultérieures. (Vous pouvez prendre une minute pour vous convaincre.)

Voici une autre illustration du comportement de volatile:

class MyClass {
    int data1, data2;
    volatile int vol1, vol2;
    void setValues() {    // runs in Thread 1
        data1 = 1;
        vol1 = 2;
        data2 = 3;
    }
    void useValues() {    // runs in Thread 2
        if (vol1 == 2) {
            int l1 = data1;    // okay
            int l2 = data2;    // wrong
        }
    }
}

En regardant useValues(), si le thread 2 n'a pas encore observé la mise à jour vers vol1, il ne peut pas savoir si data1 ou data2 a encore été défini. Lorsqu'il voit la mise à jour de vol1, il sait que data1 peut être accessible et lu correctement sans introduire de course de données. Toutefois, il ne peut faire aucune hypothèse concernant data2, car ce magasin a été exécuté après le store volatile.

Notez que volatile ne peut pas être utilisé pour empêcher la réorganisation d'autres accès à la mémoire qui se font concurrence. Il n'est pas garanti de générer une instruction de cloisonnement de la mémoire de la machine. Il peut être utilisé pour éviter les courses de données en n'exécutant du code que lorsqu'un autre thread a rempli une certaine condition.

Que faire ?

En C/C++, préférez les classes de synchronisation C++11, telles que std::mutex. Si ce n'est pas le cas, utilisez les opérations pthread correspondantes. Celles-ci incluent des barrières de mémoire appropriées, ce qui permet d'assurer un comportement approprié (cohérent dans l'ordre séquentiel, sauf indication contraire) et un comportement efficace sur toutes les versions de la plate-forme Android. Assurez-vous de les utiliser correctement. Par exemple, n'oubliez pas que les temps d'attente de la variable de condition peuvent renvoyer par erreur sans être signalés et doivent donc apparaître dans une boucle.

Il est préférable d'éviter d'utiliser directement des fonctions atomiques, sauf si la structure de données que vous mettez en œuvre est extrêmement simple, comme un compteur. Le verrouillage et le déverrouillage d'un mutex pthread nécessitent une seule opération atomique, et coûtent souvent moins d'un défaut de cache (miss) en l'absence de conflit. Vous n'allez donc pas faire beaucoup d'économies en remplaçant les appels mutex par des opérations atomiques. Les conceptions sans verrou pour les structures de données complexes nécessitent beaucoup plus de soin pour garantir que les opérations de niveau supérieur sur la structure de données semblent atomiques (dans leur ensemble, et pas seulement leurs parties explicitement atomiques).

Si vous utilisez des opérations atomiques, assouplir l'ordre avec memory_order... ou lazySet() peut offrir des avantages en termes de performances, mais nécessite une compréhension plus approfondie que ce que nous avons transmis jusqu'à présent. Une grande partie du code existant qui les utilise contient des bugs après coup. Évitez-les si possible. Si vos cas d'utilisation ne correspondent pas exactement à l'un des cas décrits dans la section suivante, assurez-vous d'être un expert ou d'en avoir consulté un.

Évitez d'utiliser volatile pour la communication de threads en C/C++.

En Java, il est souvent préférable de résoudre les problèmes de simultanéité en utilisant une classe utilitaire appropriée du package java.util.concurrent. Le code est bien écrit et bien testé sur SMP.

La solution la plus sûre consiste sans doute à rendre vos objets immuables. Les objets de classes telles que "String" et "Integer" de Java contiennent des données qui ne peuvent plus être modifiées une fois qu'un objet est créé, ce qui évite tout risque de concurrence des données sur ces objets. Le livre Effective Java, 2nd Ed. contient des instructions spécifiques dans "Item 15: Reduce Mutability" (Élément 15 : Réduire la mutabilité). Notez en particulier l'importance de déclarer les champs Java "final" (Bloch).

Même si un objet est immuable, n'oubliez pas que sa communication avec un autre thread sans synchronisation constitue une course de données. Cela peut parfois être acceptable en Java (voir ci-dessous), mais nécessite une attention toute particulière et est susceptible de fausser le code. Si les performances ne sont pas critiques, ajoutez une déclaration volatile. En C++, la communication d'un pointeur ou d'une référence à un objet immuable sans synchronisation appropriée, comme dans toute course de données, est un bug. Dans ce cas, il est raisonnablement susceptible de provoquer des plantages intermittents, car, par exemple, le thread de réception peut voir un pointeur de table de méthode non initialisé en raison de la réorganisation du magasin.

Si ni une classe de bibliothèque existante, ni une classe immuable ne convient, l'instruction Java synchronized ou les lock_guard / unique_lock C++ doivent être utilisés pour protéger les accès à tout champ accessible par plusieurs threads. Si les mutex ne fonctionnent pas dans votre situation, vous devez déclarer les champs partagés volatile ou atomic, mais vous devez veiller à bien comprendre les interactions entre les threads. Ces déclarations ne vous épargneront pas les erreurs de programmation simultanées courantes, mais elles vous aideront à éviter les mystérieux échecs liés à l'optimisation des compilateurs et aux erreurs de SMP.

Vous devez éviter de "publier" une référence à un objet, c'est-à-dire de la mettre à la disposition d'autres threads, dans son constructeur. C'est moins important en C++ ou si vous vous en tenez à nos conseils de type "pas de concurrence des données" en Java. Toutefois, c'est toujours un bon conseil et cela devient essentiel si votre code Java est exécuté dans d'autres contextes où le modèle de sécurité Java est important. Un code non approuvé peut introduire une course de données en accédant à cette référence d'objet "fuite". Il est également essentiel si vous choisissez d'ignorer nos avertissements et d'utiliser certaines des techniques présentées dans la section suivante. Pour en savoir plus, consultez la section Techniques de construction sécurisées en Java.

En savoir plus sur les commandes de mémoire faible

C++11 et les versions ultérieures fournissent des mécanismes explicites permettant d'assouplir les garanties de cohérence séquentielle pour les programmes sans origines ethniques de données. Les arguments explicites memory_order_relaxed, memory_order_acquire (chargements uniquement) et memory_order_release(magasins uniquement) pour les opérations atomiques fournissent chacun des garanties strictement plus faibles que les arguments par défaut, généralement implicites, memory_order_seq_cst. memory_order_acq_rel fournit des garanties memory_order_acquire et memory_order_release pour les opérations atomiques de lecture-modification d'écriture. memory_order_consume n'est pas encore suffisamment bien spécifié ni implémenté pour être utile, et doit être ignoré pour le moment.

Les méthodes lazySet dans Java.util.concurrent.atomic sont semblables aux magasins memory_order_release C++. Les variables ordinaires de Java sont parfois utilisées pour remplacer les accès memory_order_relaxed, bien qu'elles soient en réalité encore plus faibles. Contrairement à C++, il n'existe pas de véritable mécanisme pour les accès non ordonnés aux variables déclarées comme volatile.

En règle générale, évitez-les, sauf s'il existe des raisons urgentes de les utiliser. Sur les architectures de machine faiblement ordonnées comme ARM, leur utilisation permet généralement d'économiser quelques dizaines de cycles machine pour chaque opération atomique. Sur x86, l'amélioration des performances est limitée aux magasins et sera probablement moins visible. Même si cela peut paraître paradoxal, l'avantage peut diminuer avec un plus grand nombre de cœurs, à mesure que le système de mémoire devient un facteur limitant.

La sémantique complète des composants atomiques faiblement ordonnés est compliquée. En général, elles nécessitent une compréhension précise des règles de langage, ce que nous n'allons pas aborder ici. Par exemple :

• Le compilateur ou le matériel peuvent déplacer les accès memory_order_relaxed vers (mais pas hors) une section critique limitée par une acquisition et une libération de verrous. Cela signifie que deux magasins memory_order_relaxed peuvent devenir visibles dans le désordre, même s'ils sont séparés par une section critique.
• Une variable Java ordinaire, lorsqu'elle est utilisée de manière abusive en tant que compteur partagé, peut apparaître dans un autre thread et nécessiter une diminution, même si elle n'est incrémentée que d'un seul autre thread. Mais ce n'est pas le cas pour memory_order_relaxed atomique en C++.

À titre d'avertissement, nous donnons ici un petit nombre d'idiomes qui semblent couvrir de nombreux cas d'utilisation des expressions atomiques peu ordonnées. Nombre d'entre eux ne s'appliquent qu'au langage C++.

Accès hors course

Il est assez courant qu'une variable soit atomique, car elle est parfois lue simultanément avec une écriture, mais tous les accès ne présentent pas ce problème. Par exemple, une variable peut avoir besoin d'être atomique, car elle est lue en dehors d'une section critique, mais toutes les mises à jour sont protégées par un verrou. Dans ce cas, une lecture qui se trouve être protégée par le même verrou ne peut pas entrer en concurrence, car il ne peut pas y avoir d'écritures simultanées. Dans ce cas, l'accès hors concurrence (chargement dans ce cas) peut être annoté avec memory_order_relaxed sans modifier l'exactitude du code C++. L'implémentation du verrouillage applique déjà l'ordre de la mémoire requis en ce qui concerne l'accès par d'autres threads, et memory_order_relaxed spécifie qu'aucune contrainte d'ordre supplémentaire ne doit être appliquée pour l'accès atomique.

Il n'existe pas d'équivalent dans Java.

Le résultat n'est pas pris en compte pour l'exactitude

Lorsque nous n'utilisons une charge de course que pour générer un indice, il est généralement également acceptable de ne pas appliquer d'ordre de mémoire pour la charge. Si cette valeur n'est pas fiable, nous ne pouvons pas non plus utiliser le résultat de manière fiable pour déduire des informations sur d'autres variables. Ce n'est donc pas grave si l'ordre de la mémoire n'est pas garanti et que la charge est fournie avec un argument memory_order_relaxed.

Une exemple courante est l'utilisation de C++ compare_exchange pour remplacer de manière atomique x par f(x). Le chargement initial de x pour calculer f(x) n'a pas besoin d'être fiable. En cas d'erreur, compare_exchange échouera et nous ferons une nouvelle tentative. Il est acceptable que le chargement initial de x utilise un argument memory_order_relaxed. Seul l'ordre de la mémoire pour la compare_exchange réelle est important.

Données non lues, mais modifiées de manière atomique

Il arrive parfois que les données soient modifiées en parallèle par plusieurs threads, mais ne soient pas examinées tant que le calcul parallèle n'est pas terminé. Un bon exemple est un compteur qui est incrémenté de manière atomique (par exemple, en utilisant fetch_add() en C++ ou atomic_fetch_add_explicit() en C) par plusieurs threads en parallèle, mais le résultat de ces appels est toujours ignoré. La valeur obtenue n'est lue qu'à la fin, une fois toutes les mises à jour terminées.

Dans ce cas, il n'y a aucun moyen de savoir si les accès à ces données ont été réorganisés. Par conséquent, le code C++ peut utiliser un argument memory_order_relaxed.

Les compteurs d'événements simples en sont un exemple courant. Comme il est très courant, il convient de faire quelques observations à ce sujet:

• L'utilisation de memory_order_relaxed améliore les performances, mais ne résout pas nécessairement le problème de performances le plus important: chaque mise à jour nécessite un accès exclusif à la ligne de cache contenant le compteur. Cela entraîne un défaut de cache chaque fois qu'un nouveau thread accède au compteur. Si les mises à jour sont fréquentes et alternent entre les threads, il est beaucoup plus rapide d'éviter de mettre à jour le compteur partagé à chaque fois, par exemple en utilisant des compteurs locaux de threads et en les additionnant à la fin.
• Cette technique peut être combinée avec la section précédente: il est possible de lire simultanément des valeurs approximatives et non fiables lors de leur mise à jour, toutes les opérations utilisant memory_order_relaxed. Mais il est important de traiter les valeurs résultantes comme étant complètement peu fiables. Ce n'est pas parce que le décompte semble avoir été incrémenté une fois qu'il n'est pas possible de compter sur un autre thread pour avoir atteint le point où l'incrément a été effectué. L'incrément peut avoir été réorganisé à la place avec un code précédent. (Comme pour le cas similaire mentionné précédemment, C++ garantit qu'un deuxième chargement d'un tel compteur ne renverra pas une valeur inférieure à un chargement précédent dans le même thread. À moins, bien sûr, que le compteur n'a pas dépassé.)
• Il est courant de trouver du code qui tente de calculer des valeurs de compteur approximatives en effectuant des lectures et des écritures atomiques (ou non) individuelles, mais en ne rendant pas l'incrément dans son ensemble. L'argument habituel est que cette valeur est "suffisamment proche" pour les compteurs de performances ou autres. Ce n'est généralement pas le cas. Lorsque les mises à jour sont suffisamment fréquentes (un cas qui vous tient probablement à cœur), une grande partie des décomptes est généralement perdue. Sur un appareil à quatre cœurs, plus de la moitié des comptes peuvent être perdus. (Exercice simple: créez un scénario à deux threads dans lequel le compteur est mis à jour un million de fois, mais la valeur finale du compteur est un.)

Communication simple avec les drapeaux

Un magasin memory_order_release (ou une opération de lecture-modification-écriture) garantit que si, par la suite, un chargement memory_order_acquire (ou une opération de lecture/modification-écriture) lit la valeur écrite, il observe également tous les magasins (ordinaires ou atomiques) qui ont précédé le stockage memory_order_release. À l'inverse, les chargements antérieurs à memory_order_release n'observeront aucun magasin ayant suivi le chargement memory_order_acquire. Contrairement à memory_order_relaxed, cela permet d'utiliser de telles opérations atomiques pour communiquer la progression d'un thread à un autre.

Par exemple, nous pouvons réécrire l'exemple de verrouillage coché ci-dessus en C++ en tant que

class MyClass {
  private:
    atomic<Helper*> helper {nullptr};
    mutex mtx;
  public:
    Helper* getHelper() {
      Helper* myHelper = helper.load(memory_order_acquire);
      if (myHelper == nullptr) {
        lock_guard<mutex> lg(mtx);
        myHelper = helper.load(memory_order_relaxed);
        if (myHelper == nullptr) {
          myHelper = new Helper();
          helper.store(myHelper, memory_order_release);
        }
      }
      return myHelper;
    }
};

Le magasin de chargement et de publication d'acquisition garantit que si nous voyons une helper non nulle, ses champs seront également correctement initialisés. Nous avons également intégré l'observation précédente selon laquelle les charges hors course peuvent utiliser memory_order_relaxed.

Un programmeur Java peut imaginer helper en tant que java.util.concurrent.atomic.AtomicReference<Helper> et utiliser lazySet() comme magasin de versions. Les opérations de chargement continueront à utiliser des appels get() de base.

Dans les deux cas, notre ajustement des performances s'est concentré sur le chemin d'initialisation, qui n'est probablement pas critique pour les performances. Un compromis plus lisible pourrait être:

    Helper* getHelper() {
      Helper* myHelper = helper.load(memory_order_acquire);
      if (myHelper != nullptr) {
        return myHelper;
      }
      lock_guard&ltmutex> lg(mtx);
      if (helper == nullptr) {
        helper = new Helper();
      }
      return helper;
    }

Cette méthode permet d'obtenir le même chemin rapide, mais a recours aux opérations par défaut à cohérence séquentielle sur le chemin lent non critique pour les performances.

Même ici, helper.load(memory_order_acquire) est susceptible de générer le même code sur les architectures actuelles compatibles avec Android qu'une référence simple (cohérente de manière séquentielle) à helper. L'optimisation la plus intéressante ici pourrait être l'introduction de myHelper pour éliminer un deuxième chargement, bien qu'un futur compilateur le fasse automatiquement.

L'ordre d'acquisition/de libération n'empêche pas les magasins d'être visiblement retardés et ne garantit pas que les magasins deviennent visibles pour les autres threads dans un ordre cohérent. Par conséquent, il n'est pas compatible avec un modèle de codage délicat, mais assez courant, illustré par l'algorithme d'exclusion mutuelle de Dekker: tous les threads définissent d'abord un indicateur indiquant qu'ils souhaitent effectuer une action. Si un thread t remarque qu'aucun autre thread ne tente d'effectuer une action, il peut continuer en toute sécurité, sachant qu'il n'y aura aucune interférence. Aucun autre thread ne pourra continuer, car l'indicateur de t est toujours défini. Cette opération échoue si l'accès à l'indicateur est effectué via l'ordre d'acquisition/de publication, car cela n'empêche pas de rendre l'indicateur d'un thread visible en retard pour les autres utilisateurs, qui ont effectué une erreur. L'option memory_order_seq_cst par défaut l'empêche.

Champs immuables

Si un champ d'objet est initialisé lors de la première utilisation, puis n'a jamais été modifié, il peut être possible de l'initialiser, puis de le lire à l'aide d'accès peu ordonnés. En C++, il peut être déclaré comme atomic et accessible à l'aide de memory_order_relaxed ou en Java, il peut être déclaré sans volatile et accessible sans mesures spéciales. Pour ce faire, toutes les obligations de conservation suivantes doivent être satisfaites:

• La valeur du champ lui-même doit permettre de déterminer si celui-ci a déjà été initialisé. Pour accéder au champ, la valeur de test et de retour du chemin rapide ne doit lire le champ qu'une seule fois. En Java, cette dernière étape est essentielle. Même si le champ est testé comme étant initialisé, une deuxième charge peut lire la valeur non initialisée précédente. En C++, la règle de "lecture unique" est simplement une bonne pratique.
• L'initialisation et les chargements ultérieurs doivent être atomiques, en ce sens que les mises à jour partielles ne doivent pas être visibles. Pour Java, le champ ne doit pas être long ni double. Pour C++, une attribution atomique est requise. Sa construction sur place ne fonctionnera pas, car la construction d'un atomic n'est pas atomique.
• Les initialisations répétées doivent être sûres, car plusieurs threads peuvent lire la valeur non initialisée simultanément. En C++, cela découle généralement de l'exigence de "triviament copiable" imposée pour tous les types atomiques. Les types avec des pointeurs propriétaires imbriqués nécessiteraient une désallocation dans le constructeur de copie et ne seraient pas compréhensibles. Pour Java, certains types de références sont acceptables:
• Les références Java sont limitées aux types immuables ne contenant que des champs finaux. Le constructeur du type immuable ne doit pas publier de référence à l'objet. Dans ce cas, les règles des champs finaux Java garantissent que si un lecteur voit la référence, il verra également les champs finaux initialisés. C++ n'a pas d'équivalent à ces règles, et les pointeurs vers des objets propriétaires sont inacceptables pour cette raison également (en plus de ne pas respecter les exigences de "partielablement copiable").

Remarques finales

Bien que ce document ne se contente pas de tracer la surface du document, il ne se contente pas d'analyser la surface de l'écran. Il s'agit d'un sujet très vaste et profond. Voici quelques domaines à explorer:

• Les modèles de mémoire Java et C++ réels sont exprimés en termes d'une relation de type se produit avant, qui spécifie le moment où deux actions sont garanties dans un certain ordre. Lorsque nous avons défini une course aux données, nous avons parlé de manière informelle de deux accès à la mémoire qui se produisent "simultanément". Officiellement, cela se définit comme aucun des deux n'arriveant avant l'autre. Il est instructif d'apprendre les définitions réelles de happens-before et synchronizes-with dans le modèle de mémoire Java ou C++. Bien que la notion intuitive de "simultanément" soit généralement suffisante, ces définitions sont instructives, en particulier si vous envisagez d'utiliser des opérations atomiques à faible ordre en C++. (La spécification Java actuelle définit lazySet() de manière très informelle.)
• Découvrez ce que les compilateurs sont et ne sont pas autorisés à faire lors de la réorganisation du code. (La spécification JSR-133 contient d'excellents exemples de transformations juridiques qui entraînent des résultats inattendus.)
• Découvrez comment écrire des classes immuables en Java et C++ (vous allez bien plus loin que "ne rien modifier après la construction").
• Intériorisez les recommandations dans la section "Simultané" de la page Effective Java, 2nd Edition. Par exemple, évitez d'appeler des méthodes destinées à être remplacées dans un bloc synchronisé.
• Consultez les API java.util.concurrent et java.util.concurrent.atomic pour connaître les options disponibles. Envisagez d'utiliser des annotations de simultanéité comme @ThreadSafe et @GuardedBy (de net.jcip.annotations).

La section Complément d'informations de l'annexe contient des liens vers des documents et des sites Web qui permettront de mieux éclairer ces sujets.

Annexe

Implémenter des magasins de synchronisation

(Ce n'est pas quelque chose que la plupart des programmeurs trouveront implémenter, mais cette discussion est instructive.)

Pour les petits types intégrés tels que int et le matériel compatible avec Android, les instructions de chargement et de stockage ordinaires garantissent qu'un magasin sera visible dans son intégralité, voire pas du tout, pour un autre processeur chargeant le même emplacement. Ainsi, certaines notions de base d'"atomicité" sont fournies sans frais.

Comme nous l'avons vu précédemment, cette situation ne suffit pas. Pour garantir une cohérence séquentielle, nous devons également empêcher la réorganisation des opérations et veiller à ce que les opérations de mémoire deviennent visibles pour les autres processus dans un ordre cohérent. Il s'avère que la deuxième est automatique sur le matériel compatible avec Android, à condition que nous fassions des choix judicieux pour appliquer la première. Nous l'ignorons donc en grande partie ici.

L'ordre des opérations de mémoire est préservé en empêchant à la fois la réorganisation par le compilateur et le matériel. Ici, nous nous concentrons sur ce dernier point.

L'ordre de la mémoire sur ARMv7, x86 et MIPS est appliqué avec des instructions de "cloisonnement" qui empêchent à peu près les instructions qui suivent la clôture de devenir visibles avant celles qui la précèdent. (Il s'agit également d'instructions communément appelées "barrières", mais cela risque de prêter à confusion avec les barrières de type pthread_barrier, qui font bien plus que cela.) La signification précise des instructions de clôture est un sujet assez complexe qui doit traiter de la manière dont les garanties fournies par plusieurs types de clôtures interagissent et de la façon dont elles se combinent à d'autres garanties d'ordonnancement généralement fournies par le matériel. Il s’agit d’une vue d’ensemble de haut niveau, nous allons donc omettre ces détails.

Le type de garantie de tri le plus basique est celui fourni par les opérations atomiques C++ memory_order_acquire et memory_order_release: les opérations de mémoire précédant un magasin de versions doivent être visibles après une charge d'acquisition. Sous ARMv7, ce changement est appliqué comme suit:

• Faire précéder les instructions du magasin par des instructions appropriées concernant les clôtures. Cela empêche tous les accès précédents à la mémoire d'être réorganisés avec l'instruction de magasin. Cela empêche également inutilement de réorganiser les articles avec des instructions ultérieures du magasin.
• Suivez l'instruction de chargement avec une instruction de clôture appropriée, ce qui empêche la réorganisation de la charge lors des accès suivants. (Vous pouvez également fournir un ordre inutile avec des chargements au moins antérieurs.)

Ensemble, ils suffisent pour l'ordre d'acquisition/de publication C++. Ils sont nécessaires, mais pas suffisants, pour Java volatile ou C++ à cohérence séquentielle des éléments atomic.

Pour voir de quoi nous avons besoin, examinez le fragment de l'algorithme de Dekker que nous avons brièvement mentionné précédemment. flag1 et flag2 sont des variables C++ atomic ou Java volatile, qui sont toutes deux initialement fausses.

Thread 1	Thread 2
flag1 = true if (flag2 == false)     critical-stuff	flag2 = true if (flag1 == false)     critical-stuff

La cohérence séquentielle implique que l'une des attributions à flagn doit être exécutée en premier et être vue par le test dans l'autre thread. Ainsi, ces threads ne seront jamais exécutés simultanément.

Toutefois, le cloisonnement requis pour l'ordre d'acquisition et de publication n'ajoute des clôtures qu'au début et à la fin de chaque thread, ce qui n'est pas utile ici. Nous devons également nous assurer que si un magasin volatile/atomic est suivi d'un chargement volatile/atomic, les deux ne sont pas réorganisés. Pour y parvenir, vous devez ajouter une clôture non seulement avant un magasin à cohérence séquentielle, mais aussi après. (Ceci est à nouveau beaucoup plus puissant que nécessaire, car cette clôture ordonne généralement tous les accès à la mémoire antérieurs par rapport à tous les accès ultérieurs.)

Nous pourrions plutôt associer la clôture supplémentaire à des chargements cohérentes séquentiellement. La fréquence des magasins étant moins fréquente, la convention que nous avons décrite est plus courante et utilisée sur Android.

Comme nous l'avons vu dans une section précédente, nous devons insérer une barrière de stockage/chargement entre les deux opérations. Le code exécuté dans la VM pour un accès volatile se présente comme suit:

charge instable	magasin instable
reg = A fence for "acquire" (1)	fence for "release" (2) A = reg fence for later atomic load (3)

Les architectures de machines réelles fournissent généralement plusieurs types de clôtures, qui ordonnent différents types d'accès et peuvent avoir des coûts différents. Le choix entre ces deux options est subtil. Il est influencé par la nécessité de s'assurer que les magasins sont rendus visibles par les autres cœurs dans un ordre cohérent, et que l'ordre de la mémoire imposé par la combinaison de plusieurs clôtures est correctement composé. Pour en savoir plus, consultez la page de l'Université de Cambridge sur les mappages collectés d'atomes atomiques avec des processeurs réels.

Sur certaines architectures, en particulier x86, les barrières liées à l'acquisition et à la libération ne sont pas nécessaires, car le matériel applique toujours implicitement un ordre suffisant. Ainsi, sur x86, seule la dernière clôture (3) est réellement générée. De même, sur x86, les opérations atomiques de lecture-modification-écriture incluent implicitement une barrière forte. Ils ne nécessitent donc aucune clôture. Sur ARMv7, toutes les clôtures dont nous avons parlé ci-dessus sont obligatoires.

ARMv8 fournit des instructions LDAR et STLR qui appliquent directement les exigences liées aux chargements et aux magasins Java volatils ou C++ à cohérence séquentielle. Elles permettent d'éviter les contraintes de réorganisation inutiles mentionnées ci-dessus. Le code Android 64 bits sur ARM les utilise. Nous avons choisi de nous concentrer ici sur le placement des clôtures ARMv7, car cela permet de mieux comprendre les exigences réelles.

Complément d'informations

Pages Web et documents plus détaillés. Les articles les plus utiles se trouvent en haut de la liste.

Modèles de cohérence de mémoire partagée: tutoriel

Écrit en 1995 par Adve & Gharachorloo, c'est un bon point de départ pour approfondir les modèles de cohérence de la mémoire.
http://www.hpl.hp.com/techreports/Compaq-DEC/WRL-95-7.pdf

Barrières de mémoire

Beau article résumant les problèmes.
https://fr.wikipedia.org/wiki/Barrière_de_mémoire

Principes de base des threads

Introduction à la programmation multithread en C++ et Java, par Hans Boehm. Discussion sur les courses de données et les méthodes de synchronisation de base.
http://www.hboehm.info/c++mm/threadsintro.html

Simultanéité Java en pratique

Publié en 2006, ce livre couvre un large éventail de sujets avec une grande précision. Fortement recommandé pour toute personne écrivant du code multithread en Java.
http://www.javaconcurrencyinpractice.com

Questions fréquentes sur JSR-133 (modèle de mémoire Java)

Présentation douce du modèle de mémoire Java, avec une explication de la synchronisation, des variables volatiles et de la construction des champs finaux. (Un peu obsolète, en particulier lorsqu'il aborde d'autres langues.)
http://www.cs.umd.edu/~pugh/java/memoryModel/jsr-133-faq.html

Validité des transformations de programme dans le modèle de mémoire Java

Explication plutôt technique des problèmes restants avec le modèle de mémoire Java. Ces problèmes ne s'appliquent pas aux programmes de type "data-race-free".
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.112.1790&rep=rep1&type=pdf

Présentation du package java.util.concurrent

Documentation du package java.util.concurrent. En bas de la page, vous trouverez une section intitulée "Propriétés de cohérence de la mémoire" qui explique les garanties offertes par les différentes classes.
Résumé du package java.util.concurrent

Théorie et pratique de Java: techniques de construction sûres en Java

Cet article examine en détail les risques liés à l'échappement des références lors de la construction d'objets et fournit des instructions pour les constructeurs thread-safe.
http://www.ibm.com/developerworks/java/library/j-jtp0618.html

Théorie et pratique de Java: gérer la volatilité

Cet article décrit ce que vous pouvez et ne pouvez pas accomplir avec des champs volatiles en Java.
http://www.ibm.com/developerworks/java/library/j-jtp06197.html

Déclaration "Le verrouillage avec vérification a été vérifiée"

Explication détaillée par Bill Pugh des différentes manières dont le verrouillage vérifié est interrompu sans volatile ni atomic. Inclut C/C++ et Java.
http://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckedLocking.html

[ARM] Tests et livre de recettes Barrier Litmus

Discussion sur les problèmes liés à ARM SMP, avec de courts extraits de code ARM. Si vous avez trouvé les exemples de cette page trop peu spécifiques ou si vous souhaitez lire la description formelle de l'instruction DMB, lisez ceci. Décrit également les instructions concernant les barrières de mémoire sur le code exécutable (ce qui peut s'avérer utile si vous générez du code à la volée). Notez que cela est antérieur à ARMv8, qui accepte également des instructions de commande de mémoire supplémentaire, et a été déplacé vers un modèle de mémoire quelque peu plus puissant. Pour en savoir plus, consultez le "ARM® Architecture Reference Manual ARMv8, for ARMv8-A architecture profile".
http://infocenter.arm.com/help/topic/com.arm.doc.genc007826/Barrier_Litmus_Tests_and_Cookbook_A08.pdf

Barrières de mémoire du noyau Linux

Documentation sur les barrières de mémoire du noyau Linux. Comprend quelques exemples utiles et de l'art ASCII.
http://www.kernel.org/doc/Documentation/memory-barriers.txt

ISO/IEC JTC1 SC22 WG21 (normes C++) 14882 (langage de programmation C++), section 1.10 et clause 29 ("Bibliothèque d'opérations atomiques")

Brouillon de norme pour les fonctionnalités d'opérations atomiques C++. Cette version est proche de la norme C++14, qui inclut des modifications mineures dans ce domaine par rapport à C++11.
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/n4527.pdf
(introduction: http://www.hplH.hp.com/techreports-5020

)

ISO/IEC JTC1 SC22 WG14 (normes C) 9899 (langage de programmation C), chapitre 7.16 ("Atomics <stdatomic.h>")

Projet de norme sur les caractéristiques d'opération atomique ISO/CEI 9899-201x C. Pour en savoir plus, consultez également les rapports de défaut ultérieurs.
http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1570.pdf

Mappages C/C++11 avec les processeurs (Université de Cambridge)

Collection de traductions d'atomes C++ en plusieurs ensembles d'instructions de processeur courants par Jaroslav Sevcik et Peter Sewell.
http://www.cl.cam.ac.uk/~pes20/cpp/cpp0xmappings.html

Algorithme de Dekker

La première solution correcte connue au problème d'exclusion mutuelle dans la programmation simultanée. L'article de Wikipédia inclut l'algorithme complet, avec une discussion sur la façon dont il doit être mis à jour pour fonctionner avec des compilateurs d'optimisation et du matériel SMP modernes.
https://en.wikipedia.org/wiki/Dekker's_algorithm

Commentaires sur ARM et version alpha, et gestion des dépendances

E-mail envoyé par Catalin Marinas à partir de la liste de diffusion du noyau. Comprend un bon résumé des dépendances d'adresse et de contrôle.
http://linux.derkeiler.com/Mailing-Lists/Kernel/2009-05/msg11811.html

Ce que tout programmeur doit savoir à propos de la mémoire

Article très long et détaillé sur les différents types de mémoire, en particulier les caches de processeur, d'Ulrich Drepper.
http://www.akkadia.org/drepper/cpumemory.pdf

Raisonnement à propos du modèle de mémoire ARM à cohérence faible

Cet article a été rédigé par Chong & Ishtiaq de ARM, Ltd. Il tente de décrire le modèle de mémoire ARM SMP de manière rigoureuse, mais accessible. La définition de l'observabilité utilisée ici provient de cet article. Là encore, cette version est antérieure à ARMv8.
http://portal.acm.org/ft_gateway.cfm?id=1353528&type=pdf&coll=&dl=&CFID=96099715&CFTOKEN=57505711

Livre de recettes JSR-133 pour les compilateurs

Doug Lea a rédigé ce document en complément de la documentation JSR-133 (Java Memory Model). Il contient l'ensemble initial de consignes d'implémentation pour le modèle de mémoire Java utilisé par de nombreux rédacteurs de compilateur. Il est encore largement cité et susceptible de fournir des informations. Malheureusement, les quatre types de clôture présentés ici ne correspondent pas aux architectures compatibles avec Android, et les mappages C++11 ci-dessus constituent désormais une meilleure source de recettes précises, même pour Java.
http://g.oswego.edu/dl/jmm/cookbook.html

x86-TSO: un modèle de programmeur robuste et utilisable pour les multiprocesseurs x86

Description précise du modèle de mémoire x86. Malheureusement, la description précise du modèle de mémoire ARM est beaucoup plus complexe.
http://www.cl.cam.ac.uk/~pes20/weakmemory/cacm.pdf