Synchronisation par mémoire transactionnelle

Pour des ressources plus générales sur la synchronisation, voir Synchronisation.html

Plusieurs y croient, mais ça demeure expérimental sous bien des plateformes. L'idée est de travailler de manière optimiste : les opérations dans une zone transactionnelle ont lieu comme si elles avaient été faites sans que quelque situation de concurrence se soit produite, puis prennent effet si c'est bel et bien le cas (sinon, on recommence).

On comprendra que cette approche peut être dispendieuse s'il faut recommencer plusieurs fois la transaction, surtout si le travail réalisé dans la transaction est important.

La mémoire transactionnelle semble être la seule avenue vraiment envisageable pour synchroniser de manière générale des opérations impliquant plusieurs objets, comme par exemple std::swap() en C++. En effet, examinons une implémentation plausible de std::swap() :

namespace std {
   template <class T>
      void swap(T &a, T &b) {
         auto temp = std::move(a);
         a = std::move(b);
         b = std::move(temp);
      }
}

Cette fonction est essentielle : elle permet d'exprimer de manière idiomatique l'opérateur d'affectation, et intervient dans une multitude d'algorithmes standards, en particulier dans pratiquement tous les algorithmes de tri. Pourtant, en situation de concurrence, cette fonction est brisée : comment garantir l'absence de conditions de course sur a et b à travers l'ensemble des opérations? Utiliser des mutex est hors de question (ne sachant pas dans quel ordre les prendre, ou lesquels sont déjà pris, nous risquerions un interblocage).

Ce que nous voulons en fait est s'assurer que cette séquence s'exécute sans aucune interférence, ou du moins qu'elle soit reprise si une interférence est constatée. En d'autres termes, nous souhaitons que cette opération exprime une transaction, donc une séquence d'opérations qui n'aura d'effets visibles que lorsqu'elle aura été pleinement complétée sans interférences.

Selon la terminologie qui s'annonce pour C++ 20, nous voulons en fait ceci :

namespace std {
   template <class T>
      void swap(T &a, T &b) {
         atomic {
            auto temp = std::move(a);
            a = std::move(b);
            b = std::move(temp);
         }
      }
}

Évidemment, C++ étant ce qu'il est, il importe que l'approche que sous-tendra l'implémentation soit telle que l'ajout du bloc atomic, qui transforme cette séquence en transaction, soit essentiellement à coût nul si aucune interférence ne survient.

Mémoire transactionnelle avec C++

Pour un survol de ce qu'est la mémoire transactionnelle avec C++, de même que des problèmes qu'elle résout, permettez-moi de reformuler un extrait d'un blogue de Michael Wong lui-même (voir https://www.ibm.com/developerworks/community/blogs/5894415f-be62-4bc0-81c5-3956e82276f3/entry/The_view_from_the_May_2015_C_Standard_meeting?lang=en pour le texte original, qui couvre aussi plusieurs autres sujets, et voir http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/n4514.pdf pour la spécification technique).

Nouveaux mots clés

Avec l'avènement de la mémoire transactionnelle en C++, quelques nouveaux mots clés s'ajoutent au langage.

Mot clé Rôle 
atomic_noexcept

Annonce un bloc de transaction et définit la sémantique de sa complétion

 
atomic_commit

Annonce un bloc de transaction et définit la sémantique de sa complétion

 
atomic_cancel

Annonce un bloc de transaction et définit la sémantique de sa complétion

 
synchronized

Annonce un bloc de transaction

 
transaction_safe

Explicite le comportement d'une fonction/ d'une méthode ou d'un pointeur de fonction/ de méthode

 
transaction_safe_dynamic

Explicite le comportement d'une méthode virtuelle

 
[[transaction_unsafe]]

Annotation destinée à guider la génération de code de manière optionnelle. Donne au compilateur un indice quand aux optimisations possibles. Le compilateur peut en tenir compte ou non, à sa convenance, ce qui explique qu'il s'agisse d'une annotation

 
[[optimized_for_synchronized]]

Annotation destinée à guider la génération de code de manière optionnelle. Indique le souhait une version spéculative pour les blocs synchronized pour le cas « typique » où aucune fonction considérée unsafe ne serait appelée

Les mots transaction_safe et transaction_safe_dynamic doivent être des mots clés à part entière car ils impactent la sémantique du code tel que généré. Ils sont placés à la suite de la parenthèse fermante donnant la liste des paramètres, p. ex. :

int f() transaction_safe;

Blocs transactionnels

Une transaction est délimitée par un bloc (une portée). Les blocs transactionnels peuvent être des blocs synchronized ou des blocs atomiques, qu'il s'agisse de blocs atomic_noexcept, atomic_commit ou atomic_cancel.

Une Data Race s'exécutant dans un bloc synchronized ou dans un bloc atomique n'est pas en situation de condition de course avec une condition de course dans un autre bloc synchronized ou atomique; elle peut toutefois se trouve en condition de course avec des opérations exécutées hors de blocs synchronized ou atomiques. Sans surprises, un programme contenant une Data Race tombe dans le domaine du comportement indéfini, ici comme ailleurs.

Bloc synchronized

La caractéristique d'un bloc synchronized est que, dans un programme, tous les blocs synchronized se comportent « comme si » ils étaient protégés d'un même mutex récursif global. Il n'est pas possible d'en arriver à un interblocage dans un programme où les blocs synchronized sont les seuls mécanismes de synchronisation utilisés.

Évidemment, on parle bien d'un « comme si », d'un comportement manifeste au sens de la synchronisation; en pratique, il est peu probable qu'une implémentation offre un mécanisme aussi inefficace. Cependant, en fonction du matériel et du système d'exploitation, les stratégies pour implémenter un bloc synchronized varieront beaucoup : verouillage spéculatif, détection de conflits et autres techniques d'analyse statique de code sont possibles ici, et certaines architectures matérielles offrent un support direct à la mémoire transactionnelle. Ceci explique que le standard de C++ laisse les détails de l'implémentation de ces blocs aux gens qui implémentent les divers compilateurs.

Pour en arriver à un programme efficace, il est préférable de restreindre les blocs synchronized à des zones de taille limitée, et de réduire les risques de conflits entre opérations dans des blocs synchronized distincts. De gros blocs synchronized ou des blocs où les opérations sont sujettes à forte contention mènent à des programmes moins rapides. Enfin, certaines opérations ne peuvent être exécutées de manière spéculative (p. ex. : les entrées / sorties), alors mieux vaut les éviter dans les blocs synchronized.

Le rôle des blocs synchronized est de résoudre quelques-uns des irritants associés à l'utilisation de mutex pour synchroniser de la mémoire. Avec un bloc synchronized, les programmeuses et les programmeurs n'ont pas à associer un verrou avec une zone mémoire, et n'ont pas non plus à se discipliner quant à la gestion des verrous (ordre de saisie, saine libération) pour éviter un interblocage.

Blocs atomiques

Les blocs atomiques sont ceux qu'on nomme blocs transactionnels atomiques, ou tout simplement blocs transactionnels. Ces blocs s'exécutent « comme si » ils s'exécutaient sans interférence externe et sans concurrence avec un autre bloc synchronized, à mois que le bloc atomique ne fasse lui-même partie d'un bloc synchronized bien sûr. De par son caractère transactionnel, un bloc atomique dicte le comportement à adopter lorsqu'une exception est levée dans le bloc mais n'y est pas attrapée.

Certaines opérations sont interdites dans un bloc atomique du fait qu'il serait impossible / ardu / coûteux (selon le cas) de les supporter. On dit de ces opérations qu'elles sont Transaction-Unsafe.

Comme pour les blocs synchronized, les blocs atomiques visent à remplacer des cas de synchronisation par verrous et à réduire les risques d'interblocage. Ici encore, mieux vaut se restreindre à des blocs atomiques de petite taille et englobant des opérations à faible contention pour « maximiser le retour sur l'investissement ».

Si un tel bloc se complète sans laisser sortir d'exception et sans appeler std::abort(), alors ses effets de bord deviennent visibles au reste du programme.

Transaction-Safety

Certaines opérations sont Transaction-Unsafe et ne peuvent être exécutées dans un bloc atomique ou dans le code de fonctions appelées, directement ou non, d'un tel bloc. Le mot clé transaction_safe a été ajouté au langage pour faciliter l'analyse statique de cette propriété des fonctions d'un programme.

Élément intéressant et un peu novateur de C++ avec la mémoire transactionnelle : une fonction est présumée Transaction-Safe si sa définition ne contient pas de code Transaction-Unsafe. Cela s'applique aussi aux fonctions non-virtuelles dont le compilateur ne voit pas la définition (dans un tel cas, la vérification sera faite au moment de l'édition des liens). Le mot clé transaction_safe_dynamic permet à une méthode virtuelle de signaler qu'elle est transaction_safe et constitue un engagement pour ses classes dérivées.

Exemple de pertinence

Michael Wong signale avoir pris les exemples qui suivent de Generic Programming Needs Transactional Memory par Justin Gottschlich et Hans Boehm (TRANSACT 2013)

La programmation générique à l'aide de verrous mène parfois à des situations inextricables d'interblocage... Inextricables en l'absence de mémoire transactionnelle, du moins.

L'exemple suivant présente une telle situation à partir de l'interaction entre trois entités synchronisées à partir de verrous sur une base individuelle :

Dans tous les cas, les inclusions et les using sont présumés faits, pour alléger le propos.

Le concurrent_sack<T> est trivial, au sens mathématique du terme, n'offrant que deux services pour modifier et consulter de manière synchronisée un T.

 
template <class T>
   class concurrent_sack {
      T item;
      mutex m;
   public:
      // ...
      void set(T const &obj) {
         lock_guard<mutex> _{m};
         item = obj;
      }
      T const & get() const {
         lock_guard<mutex> _{m};
         return item;
      }
   };

La classe log permet d'ajouter de manière synchronisée du texte à ce qui s'y est accumulé. Les auteurs de cette classe ont choisi d'exposer des services explicites pour verrouiller et déverrouiller un log dans l'optique, on peut le présumer, de faire des ajouts en bloc.

L'objet ze_log est une instance globale de log, tout simplement.

 
class log {
   recursive_mutex m;
   string l_;
public:
   // ...
   void add(string const &s) {
      lock_guard<recursive_mutex> _{m};
      l_ += s;
   }
   void lock() {
      m.lock();
   }
   void unlock() {
      m.unlock();
   }
} ze_log;

Enfin, un X accepte l'affectation si ses invariants sont respectés (sorte d'encapsulation mal foutue) et écrit un message dans ze_log si l'affectation est refusée. Un X se convertit en std::string par son service to_str().

 
class X {
public:
   // ...
   X& operator=(X const &rhs) {
      if (!check_invariants(rhs))
         ze_log.add("non-respect d'invariant (encapsulation brisee)");
      return *this;
   }
   bool check_invariants(X const& rhs) {
      return /* verification selon le type */;
   }
   string to_str() const {
      return "...";
   }
};

Le problème est qu'avec ces classes, les extraits de programme ci-dessous tombent en Deadlock, et cet interblocage ne peut être résolu en permutant l'ordre de saisie des verrous.

Code global 
concurrent_sack<X> sack;
Thread A Thread B 
// obtenir sack.m
sack.set(X{});
// le problème: veut obtenir ze_log.m (deadlock)
// si dans X::operator=(), X::check_invariants(),
// retourne false
 
// obtenir ze_log.m
lock_guard<log> _{ze_log};
// pour faire ce qui suit, doit obtenir
// sack.m (deadlock!)
ze_log.add(sack.get().to_str());
ze_log.add("...");

En réécrivant une partie de ce programme à l'aide de blocs transactionnels, toutefois, le problème s'évapore. La classe X ne change pas. Pour le reste :

Le concurrent_sack<T> est encore plus simple qu'auparavant, n'ayant plus besoin d'un mutex.

 
template <class T>
   class concurrent_sack    {
      T item;
   public:
      // ...
      void set(T const &obj) {
         atomic_cancel { item = obj; }
      }
      T const & get() const {
         atomic_cancel { return item; }
      }
   };

Il en va de même pour classe log. L'objet ze_log demeure une instance globale de log, tout simplement.

 
class log {
   string l_;
public:
   // ...
   void add(string const &s) {
      atomic_cancel { l_ += s; }
   }
} ze_log;
Code global 
concurrent_sack<X> sack;
Thread A Thread B 
// début d'une transaction sur sack
sack.set(X{});
// si dans X::operator=(), X::check_invariants(),
// retourne false, alors début une transaction
// sur ze_log
 
// début d'une transaction locale
atomic_cancel
{
   // débute une transction sur sack,
   // puis sur ze_log
   ze_log.add(sack.get().to_str());
   ze_log.add("...");
}

L'ordre dans lequel les opérations synchronisées a lieu n'influence pas les risques d'interblocage puisqu'il n'y a pas de verrous nommés à verrouiller. Le recours aux blocs transactionnels apporte une abstraction plus épurée, moins entremêlée avec les détails d'implémentation.

Lectures complémentaires

Quelques liens suivent pour enrichir le propos.

Valid XHTML 1.0 Transitional

CSS Valide !