Bref – conditions de course (Race Conditions)

Une condition de course est une situation dans un programme dont l'occurrence dépend de circonstances en lien avec le rythme d'exécution des différents threads qui le composent, et qui peuvent rendre le programme imprévisible ou même le plonger dans un vilain comportement indéfini.

Le Wiki sur le sujet des conditions de course décrit celles-ci sur la base de l'électronique, domaine dont les praticiens ont en général plus d'expérience que les informaticiens dace à de telles situations :

« A race condition or race hazard is a flaw in an electronic system or process whereby the output or result of the process is unexpectedly and critically dependent on the sequence or timing of other events »

Il est possible de définir des modèle mémoire qui préviendraient, à la compilation ou à l'exécution, les conditions de course. Bien qu'un tel comportement apparaisse souhaitable, et bien que certains langages (p. ex. : Java) suivent cette voie, il s'agit d'un choix prohibitif en pratique pour tout ce qui touche aux performances à l'exécution des programmes, et qui brime fortement la capacité des compilateurs d'optimiser le code généré.

Un exemple très simple de condition de course, emprunté à une présentation de Rainer Grimm en 2014 (http://meetingcpp.com/index.php/tv14/items/8.html), est présenté à droite.

En effet, si le thread représenté par th continue de s'exécuter suite à la fin de main(), une course s'installe entre l'utilisation de std::cout qu'on y fait et le destructeur de std::cout, qui est une variable globale. Une tel programme nous mène tout droit dans le très vilain Undefined Behavior.

 
#include <thread>
#include <iostream>
int main() {
   using namespace std;
   thread th { [] { cout << this_thread::get_id(); }
   th.detach();
   // faudrait plutôt faire th.join()!
}

Data Races

Les conditions de course sont souvent très vilaines; elles compliquent notre capacité de raisonner sur un programme à partir de son code source. Parmi les diverses conditions de course possibles, certaines sont plus vilaines que d'autres. Techniquement, C++ 11 définit qu'une Data Race mène à du Undefined Behavior, et les Data Races ne sont qu'un type de condition de course parmi plusieurs.

Une Data Race survient quand (a) une donnée partagée (b) est accédée par au moins deux threads (c) dont au moins un en écriture (d) et ce, sans synchronisation.

Une solide explication de ce type de condition de course peut être lue sur http://corensic.wordpress.com/2011/06/07/benign-data-races-considered-harmful/ (par Bartosz Milewski), qui met de l'avant qu'un programme est normalement considéré comme étant constitué d'exécution séquentiellement cohérentes (Sequentially Consistent), et qu'une condition de course, même bénigne, est toute situation pouvant survenir dans un programme qui permettrait de briser cette cohérence.

Ce texte met aussi en valeur l'importance d'avoir une à la fois un modèle mémoire formel et une définition claire des concepts de simultanéité et de synchronisation pour en arriver à définir le concept de condition de course. Un commentaire en début de parcours fait référence aux importants travaux de Leslie Lamport (ceci et ceci) qui fait la démonstration que, dans un système réparti, la « simultanéité » obéit à la loi de la relativité, pas à la physique plus simple de Galilée. Ceci l'amène à présenter le concept de condition de course comme un conflit d'accès en mémoire sans outil de synchronisation.

Cohérence séquentielle

Une manière de prévenir certaines conditions de course est d'utiliser des opérations atomiques pour certaines données partagées, en particulier celles accédées en écriture par au moins un thread. Les atomiques sont le seuil de synchronisation minimal permettant d'atteindre une propriété-clé : SC-DRF (Sequentially Consistent, Data-Race-Free; séquentiellement cohérent et sans conditions de course); évidemment, avec des outils plus lourds (mutex ou autres), SC-DRF peut aussi être atteint.

Dans un programme qui n'est pas SC, il est possible qu'un thread ait constaté les événements et dans l'ordre, alors qu'un autre thread aura quant à lui constaté les événements et dans l'ordre. Ceci brise en grande partie notre capacité de comprendre nos propres programmes!

Notez que même dans un programme SC, le parallélisme peut mener à des exécutions indéterministes. Par exemple, les opérations sur des nombres à virgule flottante ne sont pas commutatives, dû à leur imprécision fondamentale, donc deux exécutions distinctes sur les mêmes données mais traitant les données dans un ordre différent peuvent mener à des résultats distincts.

Un programme SC-DRF est, essentiellement, un programme parallèle mais sur le code source duquel il est possible de raisonner : le résultat de son exécution peut être inféré à partir du code source, et tous les threads du processus constatent a posteriori que les opérations d'écriture sur des états partagés se sont faites dans un ordre cohérent

TOCTTOU

Un TOCTTOU, pour Time of check to time of use, constitue une condition de course survenant quand un programme pose un geste sur la base d'un constat qui peut ne plus s'avérer au moment où le geste est posé.

Par exemple, ci-dessous, un TOCTTOU survient si un autre thread accède en écriture la variable à laquelle réfère denom concurremment avec la fonction division_entiere(). En effet, si cette variable prend la valeur zéro entre le test (le if) et le calcul (num / denom), alors la division aura été faite sur la base de la présomption selon laquelle denom != 0, ce qui s'avérait au moment du test (Time of Check) mais ne s'avère plus au point d'utilisation (Time of Use).

class division_par_zero {};
int division_entiere(int num, int &denom) {
   if (denom == 0)
      throw division_par_zero{};
   return num / denom; // Oups!
}

Deux solutions simples à de tels problèmes sont :

En pratique, un TOCTTOU est une Data Race. Un programme C++ contenant une telle condition a un comportement indéfini, chose vilaine s'il en est une.

Interblocage

Outre les conditions de course, il existe aussi deux périls face auxquels il vaut mieux être vigilant(e)s : les interblocages de type Deadlock et ceux de type Livelock. En effet, on veut que nos algorithmes parallèles demeurent actifs (Liveness) : qu'ils progressent vers la résolution de leur tâche. Les interblocages sont des obstacles au respect de cette condition.

DeadlockLivelock

Un Deadlock se produit quand au moins deux unités d'exécution s'empêchent mutuellement de progresser dans leur exécution, chacune possédant une ressource dont une autre a besoin mais ne pouvant la céder parce qu'elle est bloquée en attente de la ressource entre les mains de l'autre

Un Livelock se produit quand au moins deux unités d'exécution s'empêchent mutuellement de progresser dans leur exécution, chacune possédant une ressource dont une autre a besoin. Dans un Livelock, plutôt que de bloquer en attente d'une ressource manquante, un thread relâchera les ressources qu'il possède et essaiera à nouveau.

Le Livelock est en quelque sorte plus pervers que le Deadlock, car le programme semble demeurer actif... 

#include <thread>
#include <mutex>
using namespace std;
int main() {
   mutex m0, m1;
   thread th0 {
      [&] {
         lock_guard<mutex> lg0 { m0 };
         lock_guard<mutex> lg1 { m1 };
         cout << "Ouf (th0)!" << endl;
      }
   };
   thread th1 {
      [&] {
         lock_guard<mutex> lg1 { m1 };
         lock_guard<mutex> lg0 { m0 };
         cout << "Ouf (th1)!" << endl;
      }
   };
   th1.join();
   th0.join();
}
 
#include <thread>
#include <mutex>
using namespace std;
int main() {
   mutex m0, m1;
   thread th0 {
      [&]{
         for (bool fait = false; !fait;)
            if (m0.try_lock()) {
               if (m1.try_lock()) {
                  cout << "Ouf (th0)!" << endl;
                  m1.unlock();
                  fait = true;
               }
               m0.unlock();
            }
      }
   };
   thread th1 {
      [&]() {
         for (bool fait = false; !fait;)
            if (m1.try_lock()) {
               if (m0.try_lock()) {
                  cout << "Ouf (th1)!" << endl;
                  m0.unlock();
                  fait = true;
               }
               m1.unlock();
            }
      }
   };
   th1.join();
   th0.join();
}

Dans l'exemple ci-dessus, si th0 obtient m0 et m1 avant que th1 ne tente d'obtenir m1, ou encore si th1 obtient m1 puis m0 avant que th0 ne tente d'obtenir m0, alors le programme se complétera sans heurts et affichera les deux messages dans un ordre ou l.'autre.

Si toutefois chacun des deux threads obtient l'un des mutex, alors les deux bloqueront ensuite sur l'obtention du second, et le programme cessera de progresser. Il sera, effectivement, paralysé.

À la manière de l'exemple de Deadlock à gauche, les threads th0 et th1 sont susceptibles de se bloquer mutuellement ici, mais en reculant et en réessayant sans arrêt, il est possible que le blocage se perpétue sur une durée arbitrairement longue, tout en consommant du temps de processeur totalement inutile.

Il existe plusieurs techniques pour éviter les interblocages, la plus simple (quand elle est applicable, ce qui n'est pas toujours le cas) étant de s'assurer que les ressources soient toujours prises dans un ordre prédéterminé. La mémoire transactionnelle peut aussi aider à éviter ces situations., Enfin, vous pouvez, à cet effet, vous inspirer de de l'algorithme du banquier de Dijkstra.

Inversion de priorités

Problème typique des systèmes ordonnancés de manière inéquitable sur la base de priorités, comme c'est le cas des systèmes en temps réel (STR), l'inversion de priorités (Priority Inversion) survient lorsqu'une unité d'exécution de faible priorité possède une ressource dont une unité d'exécution de plus haute priorité a besoin. Lorsque l'ordonnanceur est inéquitable et donne systématiquement la main à la tâche la plus prioritaire du lot, la tâche la moins prioritaire ne parvient pas à s'exécuter et à libérer la ressource, bloquant ainsi effectivement la progression de la tâche la plus prioritaire et donnant naissance à un interblocage très vilain.

Il existe deux grandes familles de solution au problème d'inversion de priorités :

Héritage de priorités

L'une des approches possibles repose sur les épaules (métaphoriques) du système d'exploitation, qui détectera l'interblocage et accordera temporairement au processus de faible priorité, bloquant celui de haute priorité, la priorité du processus ainsi bloqué.

En faisant hériter au processus de faible priorité celle du processus de haute priorité, cela donne au processus « temporairement important » l'opportunité de s'exécuter. Par la suite, sa ressource étant libérée, le processus « temporairement important » reprend sa priorité initiale, plus faible, et la situation « revient à la normale ».

Cela semble simple, mais l'implémenter est une chose complexe :

Protocole de plafonnage de priorités

Les protocoles de plafonnage de priorités viennent en deux variantes. Dans les deux cas, le « plafond » de la ressource est la priorité du plus important demandeur potentiel :

En pratique :

Herb Sutter a écrit quelques GOTW (Guru of the Week) en 2014 sur le sujet des conditions de course et de la synchronisation. Voir :

Lectures complémentaires

Quelques textes d'autres individus :

Les Data Races :

Les bitfields :

Les TOCTTOU :

Je vous invite à examiner la délicate question de la chronologie des événements dans un système réparti, de l'article Time, Clocks, and the Ordering of Events in a Distributed System par Leslie Lamport en 1978 (ma petite présentation ne rend pas justice à ce texte, qui est très important)

Les interblocages :

L'inversion de priorités :

Valid XHTML 1.0 Transitional

CSS Valide !