La condition de course
Ce que ce chapitre apporte
- Décomposer une ligne comme stock = stock - 1 en ses trois instructions réelles.
- Provoquer une perte de mise à jour à volonté, et la reproduire par un entrelacement donné.
- Nommer la section critique, l'atomicité, l'entrelacement et la condition de course.
- Dénombrer les entrelacements d'un cas simple et lire la distribution des résultats obtenus.
- Expliquer pourquoi un défaut présent dans dix-huit cas sur vingt traverse les tests sans se montrer.
Le magasin de pièces détachées d'un atelier tient un stock de dix roulements. Deux postes en retirent un au même instant, chacun par son propre fil d'exécution. Le stock devrait tomber à huit. Il tombera à neuf, et le logiciel n'aura commis aucune faute visible : la ligne fautive est juste, le calcul est juste, et le résultat est faux. Ce chapitre fait provoquer ce défaut au clic, autant de fois que voulu, puis compte tous les ordres d'exécution possibles. La réponse du dénombrement est l'inverse de ce que tout le monde suppose.
Deux retraits au même instant
Le logiciel du magasin tient le stock dans une variable, et un retrait s'écrit d'une ligne.
Rien à redire. Un seul fil, un seul retrait, neuf roulements. Le programme est ensuite déployé sur un serveur qui sert deux postes de l'atelier, chacun dans son fil, et le stock affiché se met à dériver. Une pièce par-ci, deux par-là, jamais reproductible, jamais au même endroit. Les inventaires du vendredi ne tombent plus juste.
La cause tient entièrement dans une affirmation que personne ne pense à mettre en doute : que stock = stock - 1 soit une opération.
Une ligne, trois instructions
Le processeur ne sait pas retrancher un d'une case mémoire d'un seul geste. Il procède en trois temps : il copie la valeur de la mémoire dans un registre, il effectue le calcul dans ce registre, il recopie le registre en mémoire.
Ces trois lignes font exactement ce que faisait la ligne unique. La différence n'est pas dans le résultat, elle est dans le nombre d'endroits où l'ordonnanceur peut interrompre le fil : deux endroits au lieu de zéro apparents.
Une opération est atomique quand aucun autre fil ne peut s'intercaler pendant son déroulement : elle a lieu entièrement, ou pas du tout. stock = stock - 1 n'est pas atomique, quoi qu'en dise son écriture d'une ligne. Elle se décompose en une lecture, un calcul et une écriture, et un autre fil peut prendre le processeur entre deux d'entre elles.
La figure ci-dessous écrit les trois temps, pour les deux postes. Première consigne : la plus sage.
fil A
registre vide- lire stock
- ajouter -1
- écrire stock
fil B
registre vide- lire stock
- ajouter -1
- écrire stock
Avancer un fil, puis l'autre, dans l'ordre voulu. Un fil peut aussi être avancé plusieurs fois de suite : c'est ce que fait l'ordonnanceur quand il ne l'interrompt pas.
Huit. Le poste A lit dix, calcule neuf, écrit neuf ; le poste B lit neuf, calcule huit, écrit huit. Chaque poste a vu le travail de l'autre, parce que l'un a entièrement fini avant que l'autre ne commence. C'est le cas que tout le monde a en tête, et c'est un cas particulier.
Le défi
La figure qui suit est la précédente, à l'identique. Le programme n'a pas bougé d'une instruction. Seule la consigne change, et c'est tout le sujet de ce chapitre.
fil A
registre vide- lire stock
- ajouter -1
- écrire stock
fil B
registre vide- lire stock
- ajouter -1
- écrire stock
Avancer un fil, puis l'autre, dans l'ordre voulu. Un fil peut aussi être avancé plusieurs fois de suite : c'est ce que fait l'ordonnanceur quand il ne l'interrompt pas.
L'ordre qui réussit à coup sûr est l'alternance stricte : A, B, A, B, A, B. Le voici pas à pas, avec les deux registres et la mémoire.
| Étape | Fil | Instruction | Registre de A | Registre de B | stock |
|---|---|---|---|---|---|
| 1 | A | lire stock | 10 | vide | 10 |
| 2 | B | lire stock | 10 | 10 | 10 |
| 3 | A | ajouter -1 | 9 | 10 | 10 |
| 4 | B | ajouter -1 | 9 | 9 | 10 |
| 5 | A | écrire stock | 9 | 9 | 9 |
| 6 | B | écrire stock | 9 | 9 | 9 |
Tout est correct, ligne par ligne. Le poste A a lu dix, retranché un, écrit neuf : il n'a pas tort. Le poste B a lu dix, retranché un, écrit neuf : il n'a pas tort non plus. Seulement B a lu avant que A n'ait écrit, donc il a travaillé sur une valeur qui n'était déjà plus la bonne, et son écriture a recouvert celle de A sans la voir.
Une condition de course est une situation où le résultat d'un programme dépend de l'ordre dans lequel plusieurs fils accèdent à une donnée commune. Une perte de mise à jour en est la forme la plus fréquente : deux fils lisent la même valeur, la modifient chacun de son côté, et la seconde écriture efface la première. La section critique est la portion de code qui va de la première lecture d'une donnée commune à la dernière écriture de cette donnée : ici, les trois instructions du retrait.
« Le retrait est instantané, les deux postes ne peuvent pas tomber exactement au même moment. » Ils n'ont pas besoin de tomber au même moment. Il suffit que l'ordonnanceur interrompe le poste A entre sa lecture et son écriture, soit une fenêtre de quelques dizaines de nanosecondes, et que le poste B y passe. Sur un serveur qui traite des milliers de requêtes, cette fenêtre est franchie plusieurs fois par jour.
Est-ce un coup de chance ?
C'est la question que le lecteur se pose après avoir provoqué le défaut, et elle est légitime : il a fallu cliquer dans un ordre choisi exprès. Le bouton de dénombrement y répond, et sa réponse est l'inverse de ce que l'intuition annonce.
Sur les vingt entrelacements possibles de deux retraits non protégés, deux seulement donnent le bon stock. Les deux qui réussissent sont les deux ordres entièrement séquentiels : les trois instructions de A puis les trois de B, ou l'inverse. Dix-huit entrelacements sur vingt perdent une mise à jour et laissent le stock à neuf.
Le défaut n'est donc pas un cas limite. C'est le cas général, et le fonctionnement correct est l'exception.
Il faut alors expliquer une contradiction, et c'est le passage le plus important du module. Si dix-huit ordres sur vingt sont mauvais, pourquoi le magasin fonctionne-t-il correctement des mois durant avant que quiconque remarque une dérive ? Pourquoi les tests passent-ils ?
Parce que l'ordonnanceur ne tire pas les entrelacements au hasard. Il n'y a aucune équiprobabilité dans un système réel. Un fil qui obtient le processeur le garde pendant toute sa tranche de temps, quelques millisecondes, et trois instructions élémentaires se déroulent en quelques nanosecondes. Le fil a donc largement le temps de terminer ses trois instructions avant d'être interrompu, et l'ordonnanceur produit presque toujours l'un des deux ordres séquentiels. Les dix-huit autres restent possibles, mais ils demandent que l'interruption tombe précisément dans la fenêtre minuscule qui sépare la lecture de l'écriture.
Trois conséquences en découlent, et elles décrivent la vie réelle de ce défaut.
La première : la rareté ne vient pas du programme, elle vient de l'ordonnanceur. Rien dans le code n'a été rendu plus sûr. Un seul choix extérieur, invisible et non garanti, fait la différence entre un magasin juste et un magasin faux.
La deuxième : les tests ne peuvent pas trouver ce défaut. Une suite de tests exécute le retrait quelques milliers de fois sur une machine tranquille, où chaque fil finit sa tranche de temps sans concurrent. Elle tire donc presque exclusivement dans les deux bons entrelacements, et elle conclut que le code est correct. Elle n'a rien prouvé du tout : elle a seulement constaté que l'ordonnanceur était de bonne humeur.
La troisième : le défaut éclate le jour où la machine est chargée. Plus il y a de fils prêts à s'exécuter, plus les interruptions sont fréquentes, et plus les entrelacements dangereux sortent souvent. Le passage sur un serveur à plusieurs cœurs aggrave encore les choses, puisque deux fils y avancent réellement en même temps. Un défaut de concurrence se manifeste donc précisément au pire moment : en production, sous charge, un jour de forte activité, et jamais pendant la mise au point.
Un test qui passe ne dit rien sur une condition de course. La seule démonstration recevable est le raisonnement sur les entrelacements : chercher si un ordre fait échouer le programme, sans se demander s'il est probable.
La section critique, et ce qu'elle contient
Toutes les instructions d'un fil ne sont pas dangereuses. La figure ci-dessous entoure le retrait de deux messages qui ne touchent à aucune donnée commune.
fil A
registre vide- afficher « poste A : demande d'une pièce »
- lire stock
- ajouter -1
- écrire stock
- afficher « poste A : pièce remise »
fil B
registre vide- afficher « poste B : demande d'une pièce »
- lire stock
- ajouter -1
- écrire stock
- afficher « poste B : pièce remise »
Avancer un fil, puis l'autre, dans l'ordre voulu. Un fil peut aussi être avancé plusieurs fois de suite : c'est ce que fait l'ordonnanceur quand il ne l'interrompt pas.
Les messages peuvent s'entrelacer dans tous les sens sans dommage. Ce qui est fragile tient dans les trois instructions du milieu, et uniquement là.
Le dénombrement donne ici deux cent cinquante-deux entrelacements, dont cinquante-deux corrects, soit un sur cinq environ, contre un sur dix pour la figure sans messages. Cette amélioration apparente est un piège à comprendre : le code n'est pas devenu plus sûr, les instructions inoffensives ne font que diluer la proportion. Dans un programme réel, où le retrait est noyé dans des milliers d'instructions anodines, cette proportion devient excellente, et le défaut reste entier.
Délimiter la section critique de la première lecture à la dernière écriture, et non autour de la seule ligne qui modifie la variable. Un programme qui lit le stock, affiche une confirmation à l'opérateur, puis écrit le stock décrémenté, a une section critique qui englobe l'affichage : la fenêtre dangereuse est alors longue de plusieurs millisecondes au lieu de quelques nanosecondes.
Ce n'est pas l'ordre, c'est le dernier qui écrit
Quand les deux retraits portent sur des quantités différentes, la distribution des résultats devient plus parlante.
fil A
registre vide- lire stock
- ajouter -3
- écrire stock
fil B
registre vide- lire stock
- ajouter -5
- écrire stock
Avancer un fil, puis l'autre, dans l'ordre voulu. Un fil peut aussi être avancé plusieurs fois de suite : c'est ce que fait l'ordonnanceur quand il ne l'interrompt pas.
Trois valeurs sortent de cette figure. Trente-deux est la bonne, et elle apparaît dans deux entrelacements sur vingt, les deux ordres séquentiels. Trente-sept apparaît neuf fois : le poste B a été écrasé, seul le retrait de trois subsiste. Trente-cinq apparaît neuf fois aussi : c'est le poste A qui a été écrasé.
La règle se lit directement : dès que les deux postes ont lu avant que l'un ait écrit, le dernier qui écrit impose son résultat et efface l'autre. Aucune information n'est mélangée, aucune valeur intermédiaire absurde n'apparaît. Un retrait est simplement perdu, entier, sans trace.
C'est ce qui rend le défaut si difficile à repérer après coup dans les données : le stock ne contient pas une valeur impossible qu'un contrôle rejetterait. Il contient une valeur parfaitement plausible, celle qu'on aurait eue avec un retrait de moins.
Un troisième poste, et la proportion s'effondre
L'atelier ouvre un troisième poste de retrait. Le programme n'a pas changé.
fil A
registre vide- lire stock
- ajouter -1
- écrire stock
fil B
registre vide- lire stock
- ajouter -1
- écrire stock
fil C
registre vide- lire stock
- ajouter -1
- écrire stock
Avancer un fil, puis l'autre, dans l'ordre voulu. Un fil peut aussi être avancé plusieurs fois de suite : c'est ce que fait l'ordonnanceur quand il ne l'interrompt pas.
Mille six cent quatre-vingts entrelacements. Le stock correct, sept, n'apparaît que dans six d'entre eux : les six façons d'exécuter les trois postes entièrement l'un après l'autre. Deux cent soixante-dix ordres donnent huit, un retrait perdu, et mille quatre cent quatre donnent neuf, deux retraits perdus sur trois.
De dix pour cent à moins d'un demi pour cent. Ajouter un poste de retrait à un magasin qui fonctionnait divise par vingt-huit la proportion d'ordres d'exécution corrects, sans qu'aucune ligne de code ait été touchée. C'est la raison pour laquelle un programme concurrent qui a tenu des années se met à échouer le jour où la charge augmente.
Le contre-exemple : deux variables, aucune course
Il serait faux de conclure que toute exécution concurrente est menacée. La figure ci-dessous mène les mêmes trois instructions dans chaque fil, sur deux variables distinctes.
fil A
registre vide- lire stock
- ajouter -1
- écrire stock
fil B
registre vide- lire retraits
- ajouter +1
- écrire retraits
Avancer un fil, puis l'autre, dans l'ordre voulu. Un fil peut aussi être avancé plusieurs fois de suite : c'est ce que fait l'ordonnanceur quand il ne l'interrompt pas.
Vingt entrelacements, un seul résultat. La condition de course ne vient pas du fait que des fils avancent ensemble, ni du fait qu'ils écrivent : elle vient du fait que plusieurs fils atteignent la même donnée et qu'au moins un l'écrit. Deux fils qui lisent une même variable sans jamais l'écrire ne courent aucun risque non plus.
Ce critère est celui du relevé établi au chapitre précédent, et il se vérifie sur le texte du programme, sans rien exécuter.
Exercices type
Un compteur de production est incrémenté par deux postes d'assemblage. Le compte final est-il exposé au même défaut que le stock, alors qu'il augmente au lieu de diminuer ?
fil poste_1
registre vide- lire pieces_montees
- ajouter +1
- écrire pieces_montees
fil poste_2
registre vide- lire pieces_montees
- ajouter +1
- écrire pieces_montees
Avancer un fil, puis l'autre, dans l'ordre voulu. Un fil peut aussi être avancé plusieurs fois de suite : c'est ce que fait l'ordonnanceur quand il ne l'interrompt pas.
Oui, exactement le même, et la distribution est identique : deux entrelacements sur vingt donnent le compte correct de deux, dix-huit donnent un. Le sens de la variation n'a aucune importance, puisque la décomposition en lire, calculer, écrire est la même.
Le défaut est même plus pernicieux à l'usage. Un stock qui dérive vers le haut finit par se voir à l'inventaire, quand la quantité annoncée dépasse ce que les rayonnages contiennent. Un compteur de production qui dérive vers le bas produit un chiffre simplement plus petit que la réalité, que personne ne peut recouper sans un second comptage indépendant. Le défaut s'installe dans les indicateurs de performance sans jamais déclencher d'alerte.
Un créneau de banc d'essai est libre, et deux ateliers le réservent au même instant. Le compteur de créneaux disponibles vaut 1. Que peut-il se passer, et quelle est la conséquence concrète ?
fil atelier_A
registre vide- lire creneaux
- ajouter -1
- écrire creneaux
fil atelier_B
registre vide- lire creneaux
- ajouter -1
- écrire creneaux
Avancer un fil, puis l'autre, dans l'ordre voulu. Un fil peut aussi être avancé plusieurs fois de suite : c'est ce que fait l'ordonnanceur quand il ne l'interrompt pas.
Dans dix-huit entrelacements sur vingt, le compteur finit à zéro : les deux ateliers ont lu un créneau libre, ont tous les deux conclu qu'ils l'obtenaient, et ont écrit zéro l'un après l'autre. Le compteur est cohérent en apparence, et deux équipes se présentent le même jour au même banc d'essai.
Dans les deux entrelacements séquentiels, le compteur descend à moins un. Ce cas est le moins grave des deux, parce qu'une valeur négative est absurde et qu'un contrôle la rejettera. La situation vraiment dangereuse est celle qui laisse une valeur plausible.
La différence avec le stock de roulements mérite d'être notée. Sur un stock, le défaut fausse un chiffre. Sur une réservation, il fausse une décision : les deux ateliers ont pris leur décision sur une lecture périmée, et aucun contrôle en aval ne peut la rattraper, puisque le compteur final ne porte aucune trace de la double réservation.
Un développeur propose de corriger le magasin ainsi : relire le stock juste après l'avoir écrit, et recommencer le retrait si la valeur relue ne correspond pas à celle qui vient d'être écrite. Cette correction tient-elle ?
Elle ne tient pas, et l'exercice consiste à dire pourquoi sans se contenter d'une intuition.
Le fil A écrit neuf, puis relit. S'il relit immédiatement, il trouve neuf et conclut que tout va bien, alors même que le fil B a déjà lu dix et s'apprête à écrire neuf à son tour. La relecture se fait dans la même fenêtre de vulnérabilité que le reste, et elle ne fait que l'allonger : la section critique va maintenant de la lecture initiale à la relecture, ce qui donne à l'ordonnanceur davantage d'occasions d'intercaler l'autre fil.
Le raisonnement général est celui qu'il faut retenir. Aucune suite d'instructions ordinaires ne peut se protéger elle-même, parce que chaque instruction ajoutée est un point d'interruption de plus. Vérifier, comparer, relire, recommencer : chacune de ces opérations est elle-même faite de lectures et d'écritures non atomiques, et le défaut se déplace au lieu de disparaître.
Ce qu'il faut est d'une autre nature : un mécanisme qui empêche un second fil d'entrer dans la section critique tant qu'un premier y est, et que le processeur garantit atomique. C'est exactement l'objet du chapitre suivant.
Vérification
1.En combien d'instructions élémentaires stock = stock - 1 se décompose-t-il ?
2.Deux postes retirent une pièce d'un stock de 10 sans protection. Sur les 20 entrelacements possibles, combien donnent le bon stock de 8 ?
3.Pourquoi une condition de course est-elle rare en production alors que 18 entrelacements sur 20 sont mauvais ?
4.Une suite de tests exécute dix mille retraits concurrents sans jamais échouer. Que peut-on en conclure ?
5.Qu'est-ce que la section critique d'un retrait de stock ?
6.Deux postes retirent 3 et 5 pièces d'un stock de 40, et un entrelacement dangereux se produit. Que vaut le stock final ?
7.Un troisième poste de retrait est ajouté. Que devient la proportion d'entrelacements corrects ?
8.Quelle condition exacte expose une donnée à une condition de course ?
La méthode
- Relever chaque donnée atteinte par plus d'un fil, et marquer celles qu'au moins un fil écrit : ce sont les seules à traiter.
- Réécrire en trois temps chaque ligne qui modifie l'une de ces données, sous la forme lire, calculer, écrire, pour faire apparaître les points d'interruption.
- Délimiter la section critique, de la première lecture à la dernière écriture, et vérifier qu'aucune instruction inutile n'a été enfermée dedans.
- Jouer l'entrelacement le plus défavorable : intercaler l'autre fil juste après la lecture, avant l'écriture, et calculer le résultat obtenu.
- Dénombrer plutôt que d'essayer, en comptant la proportion d'ordres corrects, et ne jamais conclure d'un essai ni d'un test qui passe.
- Consigner chaque section critique repérée, en attendant de la protéger : tant qu'elle ne l'est pas, le programme est faux même s'il donne le bon résultat.
Synthèse
- Une affectation comme
stock = stock - 1n'est pas atomique : elle se décompose en lire, calculer, écrire, et un autre fil peut s'intercaler entre ces trois temps. - Une condition de course est une situation où le résultat dépend de l'ordre d'accès de plusieurs fils à une donnée commune ; la perte de mise à jour en est la forme la plus courante.
- La section critique va de la première lecture d'une donnée commune à sa dernière écriture, et toute instruction enfermée dedans allonge la fenêtre dangereuse.
- Sur deux retraits non protégés, deux entrelacements sur vingt donnent le bon résultat : le fonctionnement correct est l'exception, pas la règle.
- La rareté du défaut en production vient de l'ordonnanceur, qui laisse en général un fil terminer ses trois instructions, et non d'une quelconque sûreté du code : le défaut éclate sous charge, et les tests ne le trouvent pas.
- Une donnée n'est exposée que si plusieurs fils l'atteignent et qu'au moins un l'écrit : deux lectures concurrentes, ou deux variables distinctes, ne courent aucun risque.
Aucune suite d'instructions ordinaires ne peut se protéger elle-même, puisque chaque instruction ajoutée offre un point d'interruption de plus. Ce qu'il faut est d'une autre nature : un mécanisme, garanti atomique par le système, qui empêche un second fil d'entrer dans la section critique tant qu'un premier s'y trouve. C'est l'objet du chapitre suivant.