Ébauche d'un type atomic « maison »

Le standard C++ 11 offre un template std::atomic<T> pour les types en fonction desquels un tel comportement est possible (les primitifs d'une taille inférieure ou égale à celle d'un mot mémoire, incluant les pointeurs). Je vous en prie, utilisez-le! Ce qui suit n'est qu'une illustration sans prétention, et peut au mieux servir de dépannage si votre compilateur n'est pas suffisamment à jour.

Allons-y d'office : bien qu'il soit alléchant de tenter d'exprimer sous forme de bibliothèque un type atomique sous une forme telle que celle proposée à droite, un tel type exige, pour être complet, une forme de support du compilateur (surtout pour ce qui est de la gestion des réordonnancements en mémoire), ou un fort couplage avec les services de la plateforme sous-jacente (introduction de barrières ou de clôtures avant et après, par exemple).

On peut toutefois y aller d'une ébauche simpliste pour un pointeur et pour un entier, à titre illustratif.

atomic<int> i = 0;
++i; // incrémentation atomique

La version réduite proposée à droite est spécifique aux plateformes Microsoft Windows. Elle entrepose une valeur de type T dans un long, et remplace l'incrémentation et la décrémentation en format préfixe (donc ++i plutôt que i++) par des invocations à InterlockedIncrement() et à InterlockedDecrement() de la plateforme pour réaliser ces opérations de manière atomique. L'opération exchange(), très importante (voir plus bas), est implémentée à partir d'un appel à InterlockedCompareExchange().

Plusieurs améliorations devraient être apportées à cette implémentation. Par exemple :

on devrait valider que sizeof(T) soit inférieur ou égal à la taille d'un mot mémoire (et on devrait s'assurer que le type de la représentation sous-jacente soit, lui, de la taille d'un mot mémoire);
il serait probablement sage de définir le cas général de manière incomplète (template<class> class atomic;), puis de spécialiser ce type pour les cas couverts seulement. Une alternative serait de définir le template atomic<T> de manière générale mais de tirer les opérations à appliquer à la représentation sous-jacente d'une gamme de traits. Dans un cas comme dans l'autre, ceci pourrait contraindre les cas d'utilisation en fonction des types T utilisés (par exemple, est-il raisonnable d'exposer l'opérateur ++ si T est bool?);
plusieurs opérations pourraient être ajoutées à l'interface publique de la classe;
il pourrait être sage de faire en sorte que la représentation sous-jacente soit volatile, pour contraindre les opportunités de réordonnancement; etc.

Les contraintes détaillées sur le modèle d'exécution de C++ 11 sont décrites dans la version presque complète du standard, que vous trouverez par ici.

#ifndef ATOMIC_H
#define ATOMIC_H
#include <windows.h> // piarkkkk
template <class T>
   class atomic
   {
      long val_;
   public:
      operator T() const
      {
         return *reinterpret_cast<T*>(val_);
      }
      atomic(T val = {})
         : val_{*reinterpret_cast<long *>(&val)}
      {
      }
      atomic &operator++()
      {
         InterlockedIncrement(&val);
         return *this;
      }
      atomic &operator--()
      {
         InterlockedDecrement(&val);
         return *this;
      }
      bool exchange(T val)
      {
         return InterlockedCompareExchange(&val_, static_cast<long>(val), val_) == static_cast<long>(val);
      }
   };

La spécialisation pour les pointeurs est nécessaire du fait que Microsoft Windows offre une version spécialisée pour appliquer Compare and Swap aux pointeurs, à travers la fonction InterlockedExchangePointer(). Ceci permet d'utiliser des représentations différentes pour les adresses et pour les données.

Notez que dans bien des cas, les opérations atomiques d'un système d'exploitation doivent être appliquées sur des données alignées sur un mot mémoire ou sur une Cache Line. Lorsqu'une entité a été allouée dynamiquement (à travers l'opérateur new), elle respecte normalement de facto cette contrainte; dans le cas contraire, il est parfois nécessaire de travailler un peu plus fort. L'opérateur alignas() de C++ 11 simplifie cette tâche.

Ici encore, plusieurs services pourraient être ajoutés (opérateur * pour le déréférencement, version const de l'opérateur ->, opérateurs de comparaison, etc.).

template <class T>
   class atomic<T*>
   {
      T* p_;
   public:
      operator T*() const
         { return p_; }
      atomic(T* p = {})
         : p_{p}
      {
      }
      atomic &operator++()
      {
         InterlockedIncrement(&p);
         return *this;
      }
      atomic &operator--()
      {
         InterlockedDecrement(&p);
         return *this;
      }
      T *operator->()
         { return p_; }
      bool exchange(T* p)
      {
         return InterlockedExchangePointer(p_, p) == p_;
      }
   };
#endif

L'instruction Compare and Swap

Pour en savoir plus sur le texte séminal de cette approche, un texte de 1991 par Maurice Herlihy, voir http://www.cs.brown.edu/~mph/Herlihy91/p124-herlihy.pdf.

L'instruction Compare and Swap (ou CAS) est l'une des opérations minimales possibles pour permettre l'implémentation d'atomicité à bas niveau, de manière à ce que cette implémentation puisse être prise en charge par le matériel et fonctionner même sur des ordinateurs munis de plusieurs processeurs ou de plusieurs coeurs.

À titre illustratif, si nous pouvions exprimer cette opération en langage C (et nous ne le pouvons pas, puisqu'il est nécessaire que l'opération soit atomique au sens du matériel), alors son implémentation sur des int ressemblerait à ceci (à droite).

Ainsi, dans les termes exprimés par notre exemple, l'opération CAS vise à inscrire la valeur nouveau dans *dest. Au préalable, l'appelant suppose que *dest contient le même contenu que vieux. Ce que CAS fait, concrètement, est de permettre au code client de vérifier s'il y a eu interférence par un tiers pendant que la tentative de modification au contenu de *dest a eu lieu.

int cas(int *dest, int vieux, int nouveau)
{
   int copie = *dest;
   if (copie == vieux)
      *dest = nouveau;
   return copie;
}

En effet :

au tout début, une copie de *dest est faite. Cette copie est la valeur qui sera retournée par la fonction;
seulement si copie a la même valeur que vieux, donc seulement si aucune interférence ne s'est produite entre le moment où le code client a constaté la valeur de vieux dans *dest et le moment où copie et vieux sont comparés, la valeur de nouveau sera déposée dans *dest;
si la partie composée du test et de l'affectation est faite de manière atomique, alors le test est valide et l'affectation n'est faite que si aucune entitê n'a interféré sur *dest;
puisque le code client connaît vieux (par définition, l'ayant lui-même suppléé à la fonction cas()) et connaîtra la valeur de copie suite à l'appel, il saura que personne n'a interféré avec sa propre vision de *dest si cas() retourne la valeur de vieux.

Un exemple d'utilisation de cas() (qui, je le rappelle, illustre CAS mais n'est pas correct au sens strict, puisque CAS exige un support du substrat matériel) pour incrémenter une variable a de 1 serait celui proposé à droite.

Tel qu'indiqué plus haut, cet exemple saisit l'ancienne valeur de a au sens du code client (une copie, placée dans temp_a), détermine la valeur souhaitée (variable a_souhaite), puis invoque cas() pour tenter d'affecter à a la valeur souhaitée (a_souhaite). Ceci est refait tant que la valeur retournée signale qu'il y a eu interférence par un tiers (tant que temp_a n'est pas retourné).

int a = 3;
int temp_a = a;
int a_souhaite = temp_a + 1;
while (cas(&a, temp_a, a_souhaite) != temp_a)
   ; // un tiers a interféré; on recommence...
// ... ici, l'incrémentation a eu lieu sans intérference

Le risque ABA

Les opérations atomiques basées sur CAS sont assujeties au risque ABA, une condition signalant le basculement de l'état d'une variable d'un état A vers un état B puis vers un état A à nouveau, de manière telle que le code client ne puisse s'apercevoir qu'il vient de rencontrer un faux positif.

Le Wiki sur le sujet (http://en.wikipedia.org/wiki/ABA_problem) raconte :

« In multithreaded computing, the ABA problem occurs during synchronization, when a location is read twice, has the same value for both reads, and "value is the same" is used to indicate "nothing has changed". However, another thread can execute between the two reads and change the value, do other work, then change the value back, thus fooling the first thread in to thinking "nothing has changed" even though the second thread did work that violates that assumption »

Ce risque peut se produire en particulier avec des pointeurs détruits puis réalloués au même endroit, dans du code comparant des adresses. Soyez alertes...