Synchronisation

Il arrive que l'on ait besoin de synchronisation dans un programme multiprogrammé, entre autres pour éviter les très vilaines Data Races qui entraînent le fruit de notre travail dans des situations de comportement indéfini.

La synchronisation est principalement caractéristique de la concurrence car dans le parallélisme, du moins dans sa déclinaison puriste, l'absence d'états mutables partagés permet d'escamoter cette problèmatique.

La synchronisation a un coût, que l'on préfère généralement éviter lorsque cela s'avère possible.

En ce sens, examinez l'image proposée à droite; il s'agit d'une photographie d'une diapositive électronique de Kevlin Henney, prise par Cory House (voir https://twitter.com/housecor/status/864482919099752450 pour l'original).

Portez une attention particulière aux axes :

• L'axe vertical indique lecaractère modifiable ou non d'une donnée
• L'axe horizontal indique le fait que la donnée soit partagée ou non

Cette représentation met de l'avant une réalité de la programmation, en particulier de la programmation concurrente :

• Pas besoin de synchronisation dans le cas d'une donnée à la fois non-partagée et non-modifiable
• Pas besoin de synchronisation dans le cas d'une donnée non-partagée mais modifiable
• Pas besoin de synchronisation dans le cas d'une donnée partagée mais non-modifiable
• La synchronisation devient un besoin ferme dans le cas de données à la fois modifiables et partagées seulement

Conséquemment :

• Ne partagez que ce qu'il est pertinent et nécessaire de partager
• Ne rendez modifiable que ce qu'il est pertinent de permettre à un programme de modifier

Votre programme ne s'en portera que mieux.

Synchronisation avec verrous

La synchronisation avec verrous a été localisée dans un document à part entière : verrous.html

Synchronisation sans verrous

Il est possible, mais très périlleux, d'exprimer des algorithmes et des structures de données synchronisées sans passer par des verrous. On utilise alors typiquement des variables et opérations atomiques.

La synchronisation sans verrous repose fortement sur les variables atomiques et sur Compare-Exchange. Elle peut éviter des interblocages, mais mène typiquement à des programmes plus difficiles à tester, à écrire et à comprendre.

Plusieurs exemples sont proposés dans la section Lectures complémentaires, plus bas.

Considérations clés

Plusieurs envisagent de programmer à l'aide de structures de données sans verrous, et le font typiquement dans une optique de « performance », au sens où ne pas se suspendre sur un verrou peut aider à améliorer la fluidité et la vitesse d'exécution d'un programme. Notez, car c'est important, que « sans verrou » ne signifie pas nécessairement rapide : si plusieurs threads accèdent concurremment et fréquemment à une structure de données sans verrous, causant de la contention, il est possible qu'un programme soit plus lent qu'un équivalent reposant sur des structures de données avec verrous.

La raison pour cet état de fait est qu'un algorithme sans verrous est actif, et boucle typiquement jusqu'à ce que l'opération qu'il tente d'accomplir ait réussi. Que d'autres threads r réalisent des actions susceptibles d'interférer avec lui peut le faire boucler plus longtemps, alors qu'un algorithme avec verrous verrait les threads se suspendre volontairement et réaliser leurs opérations à la queue-leu-leu, évacuant en quelque sorte les considérations résultant de la contention.

Exprimé autrement, sans verrous signifie souvent, mais pas nécessairement, plus rapide que « avec verrous ». Ce qui est presque toujours vrai, en retour, est qu'un algorithme (ou une structure de données) sans verrous est délicat à construire, à valider et à tester.

Prenez la maxime de Donald E. Knuth en considération si vous envisagez vous lancer dans la conception d'algorithmes et de structure de données sans verrous : l'optimisation prématurée est la source de tous les maux. Si vous pensez aller dans cette direction, identifiez d'abord les goulots d'étranglement et les facteurs de ralentissement réel de votre programme. Si vos mesures montrent que le recours à des verrous est la source de vos ennuis, alors seulement lancez-vous dans des stratégies plus délicates.

L'approche RCU

Une approche de synchronisation sans verrous parmi plusieurs, mais avec un rôle particulier dans l'écosystème de C++ est l'approche Read-Copy-Update, ou RCU, qui sert entre autres dans le cas bien connu du noyau de Linux.

L'approche RCU est surtout utilisée pour fins d'accès concurrent à des structures de données chaînées (des listes, par exemples) pour lesquelles la majorité des accès sont en lecutre; pour ce cas d'utilisation bien précis, synchroniser par RCU est souvent presque gratuit.

Pour arriver à cette caractéristique sympathique de coût presque nul, il faut faire en sorte que les threads souhaitant modifier les éléments de la structure de données accédée concurremment ne puissent pas ralentir les threads qui se limitent à y lire des éléments.

Conséquemment, un thread réalisant une écriture par RCU doit en quelque sorte « prendre en charge » les lecteurs qui traversaient cette structure de données à tout moment avant, pendant et après l'écriture. Pour y arriver, les threads modifiant la structure de données doivent tenir à jour de multiples versions de cette structure de données, et doivent attendre que tous les lecteurs susceptibles d'accéder à une version donnée l'aient quitté avant de la libérer.

Les opérations clés de synchronisation par RCU, par exemple pour pointer sur un élément d'une structure ou faire une mise à jour de la structure, passent par des fonctions spécialisées. La beauté est que certaines (pas toutes, évidemment) de ces opérations sont en fait des noop, et servent à titre d'« ingénierie sociale » pour discipliner les gens à agir correctement, ce qui explique le coût faible ou nul de parties de cette approche.

L'exemple qui suit est pris d'une présentation de 2012 par Paul E. McKenney, et montre comment RCU affecte l'écriture du code :

p = malloc(sizeof(*p));
p->a = 1;
p->b = 2;
p->c = 3;
gptr = p;

p = malloc(sizeof(*p));
p->a = 1;
p->b = 2;
p->c = 3;
rcu_assign_pointer(gptr, p);

p = gptr;
foo(p->a, p->b, p->c);

p = rcu_dereference(gptr);
foo(p->a, p->b, p->c);

Les macros utilisées dans cet exemple correspondent essentiellement à ceci (il y a des variantes, et j'ai légèrement adapté l'écriture originale pour C++) :

// rcu_assign_pointer() publie un pointeur
#define rcu_assign_pointer(p, v) \
   ({ \
      smp_wmb(); /* SMP Write Memory Barrier */ \
      (p) = (v); \
   })
// rcu_dereference() permet à un lecteur de s'abonner à un pointeur
#define rcu_dereference(p) \
   ({ \
      decltype(p) _p1 = (*(volatile decltype(p)*)&(p)); \
      smp_read_barrier_depends(); \
      _p1; \
   })

Pour réaliser son travail, RCU repose sur quelques concepts :

• Des sections critiques en lecture, délimitées par rcu_read_lock() et rcu_read_unlock(), et susceptibles de contenir des abonnements (appels à rcu_dereference())
• Des états tranquilles (Quiescent State), pour le code qui n'est pas dans une section critique. Ces états peuvent être prolongés
• Une période de grâce, ou période où tous les threads sont passés par au moins un état tranquille. Cette période se conclut quand tous les lecteurs existant avant le début de la période ont conclu leur lecture, et se complètera dans un temps fini si tous les passages par une section critique sont aussi de durée finie

Sur cette base, RCU (une version académique, pas commerciale!) peut s'exprimer comme suit (le code est de Paul E. McKenney, pas de moi) :

// primitives en lecture
#define rcu_read_lock() // eh oui, rien!
#define rcu_read_unlock() // idem; c'est pour nous discipliner!
#define rcu_dereference(p) \
({ \
   decltype(p) _p1 = (*(volatile decltype(p)*)&(p)); \
   smp_read_barrier_depends(); \
   _p1; \
})
// primitives en écriture
#define rcu_assign_pointer(p, v) \
({ \
   smp_wmb(); \
  (p) = (v); \
})
void synchronize_rcu() { // prenez ceci comme du pseudocode
   int cpu;
   for_each_online_cpu(cpu)
      run_on(cpu);
}

Événements, signaux et variables conditionnelles

Pour qu'un thread se mette en attente de l'occurrence d'un événement, il existe des mécanismes plus fin qu'une répétitive itérant sans arrêt sur une variable (et provoquant de la contention sur celle-ci tout en consommant des ressources sur le processeur).

Ces mécanismes demandent typiquement que le demandeur se suspende volontairement et soit réveillé par un tiers externe lorsque l'événement se sera produit. Avec C++, le mécanisme privilégié en ce sens est la condition_variable, bien que les future<void> soient aussi pertinents dans des cas ciblés.

Loquets (Latches)

La gamme de primitives de synchronisation de C++ s'enrichit en vue de C++ 17 sur la base de la spécification technique sur la concurrence. Parmi les nouvelles primitives proposées, on trouve les loquets (en anglais : Latches).

Un loquet est une clôture à usage unique, pouvant servir de point de rendez-vous pour $n$ threads, la valeur de $n$ étant connue à la construction du loquet. Un loquet représente le concept de « point de rendez-vous », typiquement pour synchroniser le démarrage d'un travail collectif ou l'attente du passage à une autre étape.

Un loquet est incopiable. Il contient un compteur initialisé à la construction, décrémenté à chaque fois qu'un thread s'y suspend, et devient prêt (ready()) lorsque la valeur de ce compteur devient nulle. Les méthodes clés d'un loquet sont :

• count_down_and_wait(), qui est bloquante
• count_down(), qui est atomique et non-bloquante
• is_ready(), qui est atomique et non-bloquante, et
• wait(), qui est bloquante

Avec un loquet, il existe une relation Synchronizes-With entre les wait et les décomptes.

Clôtures (Barriers)

Comme mentionné plus haut, la gamme de primitives de synchronisation de C++ s'enrichit en vue de C++ 17 sur la base de la spécification technique sur la concurrence. Parmi les nouvelles primitives proposées, on trouve les clôtures (en anglais : Barriers).

Une clôture est un peu comme un loquet, mais est aussi réutilisable. Les clôtures proposées pour C++ 17 se déclinent en deux types : les barrier et les flex_barrier. La mécanique générale dans chaque cas est :

• Tous les threads qui se synchronisent sur une même clôture sont suspendus jusqu'à ce que la condition de la clôture soit rencontrée
• À ce moment, se produit ce qu'on appelle la phase de complétion de la clôture
• Suite à la fin de la phase de complétion seulement, tous les threads mis en attente seront libérés

Les services clés offerts aux threads participants à une clôture sont :

• arrive_and_wait(), qui place le thread en attente de la phase de complétion, et
• arrive_and_drop(), note que le thread est arrivé à la barrière mais le retire de la liste des participants. Cette méthode peut provoquer la phase de complétion même si elle retire un thread du lot des participants

Une clôture ne connaît pas ses participants a priori mais en connaît le nombre. Ce nombre est décrémenté lors de l'arrivée des participants au point de rendez-vous.

Pour le type barrier, la phase de complétion est vide.

Pour le type flex_barrier, la phase de complétion peut être prise en charge par une entité appelable de signature ptrdiff_t() qui retournera -1 ou plus. Cette entité appelable sera sollicitée lorsque s'amorcera la phase de complétion; si elle retourne -1, alors le nombre de participants restera le même à la prochaine utilisation de la clôture, mais si elle retourne un entier supérieur ou égale à, alors cette valeur sera le nombre de participants de la prochaine utilisation de la clôture.

Avec une barrier, il est possible de faire travailler $n$ threads en collaboration sur une tâche complexe, une étape à la fois, en synchronisant le passage d'une étape à l'autre. Avec une flex_barrier, le principe est le même mais la valeur de $n$ peut changer d'une étape à l'autre.

Mémoire transactionnelle

La synchronisation avec mémoire transactionnelle a été localisée dans un document à part entière : memoire_transactionnelle.html

Contention

On nomme contention sur un outil de synchronisation ou sur une ressource le fait que plusieurs unités d'exécution y accèdent concurremment. Une forte contention sur un objet survient quand deux threads ou plus y accèdent de manière successive et répétitive. La contention a pour effet type de bloquer la plupart des demandeurs d'accès, et influence les caractéristiques d'exécution d'un processus.

Lectures complémentaires

Quelques liens suivent pour enrichir le propos. J'ai essayé de les grouper par grandes thématiques.

Clôtures

• En 2010, Paul E. McKenney explique aux programmeuses et aux programmeurs la perspective matérielle derrière les clôtures : http://irl.cs.ucla.edu/~yingdi/web/paperreading/whymb.2010.06.07c.pdf
• Texte de Raymond Chen :
  • texte de 2015 où il s'amuse avec des clôtures de synchronisation : https://blogs.msdn.microsoft.com/oldnewthing/20151123-00/?p=92161/
  • en 2016, il explique l'implémentation de ces clôtures : https://blogs.msdn.microsoft.com/oldnewthing/20160729-00/?p=93985
• Les clôtures en C++, expliquées par Rainer Grimm en 2016 :
  •  http://www.modernescpp.com/index.php/fences-as-memory-barriers
  • http://www.modernescpp.com/index.php/acquire-release-fences

Événements, signaux, variables conditionnelles

À propos des variables conditionnelles (CondVars) :

• Implémenter une variable conditionnelle à l'aide d'un sémaphore : http://www.cs.uwaterloo.ca/~brecht/courses/702/Possible-Readings/synchronization/Implementing-condition-variables-birrell-2004.pdf
• Les variables conditionnelles sous Microsoft Windows : http://msdn.microsoft.com/en-us/library/ms682052(VS.85).aspx

Programmation sans verrous

À propos de la programmation synchronisée sans verrous, sujet périlleux s'il en est un :

• Un article portant sur la synchronisation sans attente et sur la définition de bases à partir desquelles il est possible de définir des constructions sans attente à partir d'algorithmes linéaires (sans répétitives) : http://www.cs.brown.edu/~mph/Herlihy91/p124-herlihy.pdf
• Algorithmes de synchronisation sans verrous : http://en.wikipedia.org/wiki/Lock-free_and_wait-free_algorithms
• Synchronisation non-bloquante, utilisée par exemple pour mettre au point des Try-Locks : http://en.wikipedia.org/wiki/Non-blocking_synchronization
• Synchronisation sans verrous pour la XBox, texte de Bruce Dawson en 2008 : http://msdn.microsoft.com/en-us/library/windows/desktop/ee418650%28v=vs.85%29.aspx
• Article en plusieurs morceaux, mais assez détaillé, sur la synchronisation sans verrous (entre autres choses), par Dmitry Vyukov : http://www.1024cores.net/home/lock-free-algorithms
• Introduction aux algorithmes sans verrous, par Samy Bahra en 2012 : http://techblog.appnexus.com/2012/introduction-to-lock-free-algorithms/
• Quelques textes de Raymond Chen :
  • à propos des « performances » des algorithmes de synchronisation sans verrous, texte de 2011 : http://blogs.msdn.com/b/oldnewthing/archive/2011/04/21/10156539.aspx
  • la Cache opportuniste, texte de 2011 : http://blogs.msdn.com/b/oldnewthing/archive/2011/04/14/10153633.aspx
  • le constructeur de singletons : http://blogs.msdn.com/b/oldnewthing/archive/2011/04/06/10150261.aspx
  • fonctions d'initialisation unique : http://blogs.msdn.com/b/oldnewthing/archive/2011/04/08/10151258.aspx
  • quelques suggestions de lecture « légère » sur le sujet, en 2014 : http://blogs.msdn.com/b/oldnewthing/archive/2014/11/27/10576382.aspx
• Quelques textes de Jeff Preshing :
  • texte de 2012 proposant une introduction aux subtilités de la programmation sans verrous. Ce texte inclut une définition opératoire de ce que signifie le terme « sans verrous ». Entre autres, ce texte met de l'avant que l'exécution d'un programme sans verrous ne cessera pas de progresser même si l'un de ses threads s'arrête. Le texte propose aussi un processus de décision mettant de l'avant les risques de cette pratique en fonction des caractéristiques du programme rédigé : http://preshing.com/20120612/an-introduction-to-lock-free-programming/
  • texte de 2013 qui définit une recherche linéaire sans verrous, technique qui peut être acceptable pour un conteneur de petite taille mais dont l'intérêt est principalement d'ordre pédagogique. L'implémentation a entre autres recours à des atomiques relaxées : http://preshing.com/20130529/a-lock-free-linear-search/
• Série d'articles sur la programmation sans verrous : 
  • une introduction au concept de structures de données synchronisées sans verrous, par Max Khiszinsky en 2014 : http://kukuruku.co/hub/cpp/lock-free-data-structures-introduction. Ce texte explique pourquoi l'auteur s'est intéressé à cette question, et pourquoi les structures de données, pas les algorithmes, sont au coeur de ses efforts
  • texte de 2014 par Max Khiszinsky offrant un survol de l'atomicité et des primitives qui l'accompagnent : http://kukuruku.co/hub/cpp/lock-free-data-structures-basics-atomicity-and-atomic-primitives. Cet article discute entre autres du problème ABA et du faux partage
  • texte de 2014 par Max Khiszinsky et portant sur la question des modèles mémoire : http://kukuruku.co/hub/cpp/lock-free-data-structures-memory-model-part-3. Ce texte montre comment construire un Spin-Lock à partir d'opérations atomiques, et décrit la nuance entre Compare-Exchange Weak et Compare-Exchange Strong
  • opérations synchronisées sans verrous pour Microsoft Windows, texte de 2014 : http://kukuruku.co/hub/cpp/lock-free-stack-for-windows
  • gestion de la mémoire avec une structure de données synchronisées sans verrous, par Max Khiszinsky en 2014 : http://kukuruku.co/hub/cpp/lock-free-data-structures-the-inside-memory-management-schemes. Cet article sera probablement caduque avec l'avènement probable de std::atomic<std::shared_ptr<T>> dans C++ 17
• Programmer sans verrous ni collecte d'ordures, texte d'Aaron Turon en 2015 : http://aturon.github.io/blog/2015/08/27/epoch/#looking-ahead
• Texte de 2015 qui relate un bogue dans une pile sans verrous : http://mdf356.blogspot.ca/2015/06/the-difficulty-of-lock-free-programming.html

Approche RCU :

• Ce que c'est : http://www2.rdrop.com/users/paulmck/RCU/RCU.TU-Dresden.2012.05.15a.pdf
• Présentation plus récente de RCU : http://the-paper-trail.org/blog/make-any-algorithm-lock-free-with-this-one-crazy-trick/
• La page officielle de cette approche : http://www.rdrop.com/~paulmck/RCU
• Une bibliothèque pour programmer avec RCU en User-Space, décrite par by Paul E. McKenney, Mathieu Desnoyers et Lai Jiangshan : https://lwn.net/Articles/573424/
• En 2015, Max Khiszinsky explique l'approche RCU : http://kukuruku.co/hub/cpp/lock-free-data-structures-the-inside-rcu
• Quels sont les prérequis pour RCU? Textes de Paul E. McKenney en 2015 :
  • http://lwn.net/Articles/652156/
  • http://lwn.net/Articles/652677/
  • http://lwn.net/Articles/653326/
• D'autres techniques Read-Mostly : http://lwn.net/Articles/667593/
• Variante Read-Log-Update, par Paul E. McKenney en 2015 : http://lwn.net/Articles/667720/
• Traverser une longue liste chaînée par voie de RCU, selon Paul E. McKenney en 2015 : http://paulmck.livejournal.com/40593.html
• Ordonnancement des rappels dans une situation de RCU, texte intéressant de Paul E. McKenney en 2016 : http://paulmck.livejournal.com/43731.html
• Texte de 2016 par Jeff Preshing, à propos des états de tranquilité : http://preshing.com/20160726/using-quiescent-states-to-reclaim-memory/

Structures de donnéess de données sans verrous :

• Une pile synchronisée sans verrous en C++, texte du Code Project par Michael Gazonda en 2014 : http://www.codeproject.com/Articles/801537/A-Fundamental-Lock-Free-Building-Block-The-Lock-Fr
• Une pile synchronisée sans verrous, proposée par Max Khiszinsky en 2015 : http://kukuruku.co/hub/cpp/lock-free-data-structures-the-evolution-of-a-stack
• Une pile synchronisée sans verrous avec C11, proposée par Chris Wellons en 2014 : http://nullprogram.com/blog/2014/09/02/
• Une file synchronisée sans verrous, proposée par Max Khiszinsky en 2015 :
  • http://kukuruku.co/hub/cpp/lock-free-data-structures-yet-another-treatise
  • http://kukuruku.co/hub/cpp/lock-free-data-structures-exploring-queues
• Exemples (corrects et moins corrects) de files synchronisées sans verrous : lock_free_queue.html
• File circulaire sans verrous, article de 2011 du Code Project : http://www.codeproject.com/KB/threads/LockFree.aspx
• Article de 1996 par Maged M. Michael et Michael L. Scott relatant quelques algorithmes de gestion de file sans verrous supportant les accès concurrents (merci à Adam Galarneau pour la suggestion) : http://www.research.ibm.com/people/m/michael/podc-1996.pdf
• Articles d'Andrei Alexandrescu :
  • sur les structures de données synchronisées sans verrous : http://www.ddj.com/cpp/184401865.
  • complément discutant de ce qu'il nomme les Hazard Pointers (format PDF) : http://erdani.org/publications/cuj-2004-12.pdf
• Textes de Herb Sutter, en 2008, qui relatent la difficulté d'écrire du code synchronisé sans verrous qui soit correct :
  • http://www.drdobbs.com/cpp/lock-free-code-a-false-sense-of-security/210600279
  • http://www.drdobbs.com/high-performance-computing/208801974
  • http://www.drdobbs.com/cpp/211601363
  • http://www.drdobbs.com/high-performance-computing/210604448
• Variantes de structures de données sans verrous : le Triple-Buffering. Textes de 2012 :
  • http://remis-thoughts.blogspot.ca/2012/01/triple-buffering-as-concurrency.html
  • http://remis-thoughts.blogspot.ca/2012/01/triple-buffering-as-concurrency_30.html
• Structures de données sans sans verrous, pour la plateforme .NET (car leurs implémentations dépendent des idiomes de cette plateforme, en particulier du soutien d'un moteur de collecte d'ordures) :
  • une pile : http://www.boyet.com/Articles/LockfreeStack.html
  • une file : http://www.boyet.com/Articles/LockfreeQueue.html
• Bibliothèque de structures de données sans verrous en langage C : http://www.liblfds.org/
• Définir une table de hashage sans verrous, par Jeff Preshing en 2013 : http://preshing.com/20130605/the-worlds-simplest-lock-free-hash-table/
• Vol de travail sans verrous, une série de textes par Stefan Reinalter en 2015 :
  • https://blog.molecular-matters.com/2015/08/24/job-system-2-0-lock-free-work-stealing-part-1-basics/
  • https://blog.molecular-matters.com/2015/09/08/job-system-2-0-lock-free-work-stealing-part-2-a-specialized-allocator/
  • https://blog.molecular-matters.com/2015/09/25/job-system-2-0-lock-free-work-stealing-part-3-going-lock-free/
  • https://blog.molecular-matters.com/2015/09/08/job-system-2-0-lock-free-work-stealing-part-2-a-specialized-allocator/

Autres

• Comparatif illustré de verrous, d'acteurs et de mémoire transactionnelle, par Aditya Bhargava en 2013 : http://adit.io/posts/2013-05-15-Locks,-Actors,-And-STM-In-Pictures.html
• Comparatif quantitatif de pratiques de synchronisation, assorti d'un éloge de la « synchronisation par procrastination », texte solide de Paul E. McKenney en 2013 : https://queue.acm.org/detail.cfm?id=2488549
• Un PDF sur la bibliothèque Joins du langage C-Ω, nommé The Joins Concurrency Library : http://research.microsoft.com/~crusso/papers/padl07.pdf
• Un PDF sur les mécènes en Multilisp : http://www.merl.com/reports/docs/TR93-14a.pdf
• Texte de Jeff Preshing en 2012 montrant comment mettre au point une file circulaire de journalisation en mémoire des événements clés d'un programme, pour faciliter le débogage de programmes parallèles et concurrents : http://preshing.com/20120522/lightweight-in-memory-logging/
• Dans le noyau de Linux, il est possible de réaliser un commit d'une seule opération à faible coût dans la mesure où certaines règles sont respectées. Texte de Jonathan Corbet en 2015 : http://lwn.net/Articles/650333/
• Que peut-on dire sur la cohérence des perspectives sur une zone de mémoire partagée? Texte de Raymond Chen en 2015 : https://blogs.msdn.microsoft.com/oldnewthing/20151218-00/?p=92672
• Les clôtures mémoire dans le noyau de Linux, par David Howells, Paul E. McKenney, Will Deacon et Peter Zijlstra : https://www.kernel.org/doc/Documentation/memory-barriers.txt