Pourquoi le code mutant une variable partagée entre les threads ne souffre-t-il apparemment pas d'une condition de concurrence?

107

J'utilise Cygwin GCC et j'exécute ce code:

#include <iostream>
#include <thread>
#include <vector>
using namespace std;

unsigned u = 0;

void foo()
{
    u++;
}

int main()
{
    vector<thread> threads;
    for(int i = 0; i < 1000; i++) {
        threads.push_back (thread (foo));
    }
    for (auto& t : threads) t.join();

    cout << u << endl;
    return 0;
}

Compilé avec la ligne: g++ -Wall -fexceptions -g -std=c++14 -c main.cpp -o main.o.

Il imprime 1000, ce qui est correct. Cependant, je m'attendais à un nombre inférieur en raison de l'écrasement des threads sur une valeur précédemment incrémentée. Pourquoi ce code ne souffre-t-il pas d'un accès mutuel?

Ma machine de test a 4 cœurs, et je n'ai mis aucune restriction sur le programme que je connais.

Le problème persiste lors du remplacement du contenu du partagé foopar quelque chose de plus complexe, par exemple

if (u % 3 == 0) {
    u += 4;
} else {
    u -= 1;
}
mafu
la source
66
Les processeurs Intel ont une logique interne étonnante de "descente" pour préserver la compatibilité avec les tout premiers processeurs x86 utilisés dans les systèmes SMP (comme les machines doubles Pentium Pro). Beaucoup de conditions d'échec qui nous sont enseignées sont possibles presque jamais sur les machines x86. Disons qu'un noyau va écrire uen mémoire. Le CPU fera en fait des choses étonnantes comme remarquer que la ligne de mémoire pour un'est pas dans le cache du CPU et il redémarrera l'opération d'incrémentation. C'est pourquoi passer de x86 à d'autres architectures peut être une expérience révélatrice!
David Schwartz
1
Peut-être encore trop vite. Vous devez ajouter du code pour vous assurer que le thread cède avant de faire quoi que ce soit pour vous assurer que les autres threads sont lancés avant la fin.
Rob K
1
Comme cela a été noté ailleurs, le code du thread est si court qu'il peut bien être exécuté avant que le thread suivant ne soit mis en file d'attente. Que diriez-vous de 10 threads qui placent u ++ dans une boucle de 100 points. Et un court délai avant le début de la boucle (ou un drapeau global "go" pour les démarrer tous en même temps)
RufusVS
5
En fait, générer le programme à plusieurs reprises dans une boucle montre finalement qu'il se brise: quelque chose comme while true; do res=$(./a.out); if [[ $res != 1000 ]]; then echo $res; break; fi; done;imprime 999 ou 998 sur mon système.
Daniel Kamil Kozar

Réponses:

266

foo()est si court que chaque thread se termine probablement avant même que le suivant ne soit généré. Si vous ajoutez un sommeil pendant un temps aléatoire foo()avant le u++, vous pouvez commencer à voir ce que vous attendez.

Rob K
la source
51
Cela a en effet changé la sortie de la manière attendue.
mafu
49
Je note que c'est en général une assez bonne stratégie pour présenter des conditions de course. Vous devriez être en mesure d'injecter une pause entre deux opérations; sinon, il y a une condition de course.
Matthieu M.
Nous avons eu ce problème avec C # récemment. Le code n'échouait presque jamais, mais l'ajout récent d'un appel d'API entre les deux a introduit suffisamment de retard pour le faire changer de manière cohérente.
Obsidian Phoenix
@MatthieuM. Microsoft n'a-t-il pas un outil automatisé qui fait exactement cela, comme une méthode à la fois pour détecter les conditions de course et les rendre reproductibles de manière fiable?
Mason Wheeler
1
@MasonWheeler: Je travaille quasiment exclusivement sur Linux, alors ... je sais pas :(
Matthieu M.
59

Il est important de comprendre qu'une condition de concurrence critique ne garantit pas que le code fonctionnera de manière incorrecte, mais simplement qu'il pourrait faire n'importe quoi, car il s'agit d'un comportement non défini. Y compris courir comme prévu.

En particulier sur les machines X86 et AMD64, les conditions de course causent rarement des problèmes dans certains cas, car la plupart des instructions sont atomiques et les garanties de cohérence sont très élevées. Ces garanties sont quelque peu réduites sur les systèmes multiprocesseurs où le préfixe de verrouillage est nécessaire pour que de nombreuses instructions soient atomiques.

Si l'incrémentation de votre machine est une opération atomique, cela fonctionnera probablement correctement même si selon la norme du langage, il s'agit d'un comportement non défini.

Plus précisément, je pense que dans ce cas, le code peut être compilé en une instruction atomique Fetch and Add (ADD ou XADD dans l'assemblage X86) qui est en effet atomique dans les systèmes à processeur unique, mais sur les systèmes multiprocesseurs, cela n'est pas garanti comme atomique et verrouillé serait nécessaire pour le faire. Si vous utilisez un système multiprocesseur, il y aura une fenêtre où les threads pourraient interférer et produire des résultats incorrects.

Plus précisément, j'ai compilé votre code en assemblage en utilisant https://godbolt.org/ et foo()compile en:

foo():
        add     DWORD PTR u[rip], 1
        ret

Cela signifie qu'il exécute uniquement une instruction d'ajout qui pour un seul processeur sera atomique (bien que comme mentionné ci-dessus, ce n'est pas le cas pour un système multiprocesseur).

Vality
la source
41
Il est important de se rappeler que «courir comme prévu» est un résultat permis d'un comportement indéfini.
Mark
3
Comme vous l'avez indiqué, cette instruction n'est pas atomique sur une machine SMP (ce que sont tous les systèmes modernes). Même inc [u]n'est pas atomique. Le LOCKpréfixe est nécessaire pour rendre une instruction vraiment atomique. L'OP a simplement de la chance. Rappelez-vous que même si vous dites au CPU "ajouter 1 au mot à cette adresse", le CPU doit toujours récupérer, incrémenter, stocker cette valeur et un autre CPU peut faire la même chose simultanément, ce qui rend le résultat incorrect.
Jonathon Reinhart
2
J'ai voté à la baisse, mais ensuite j'ai relu votre question et j'ai réalisé que vos déclarations d'atomicité supposaient un seul processeur. Si vous modifiez votre question pour rendre cela plus clair (lorsque vous dites "atomique", soyez clair que ce n'est le cas que sur un seul processeur), alors je pourrai supprimer mon vote négatif.
Jonathon Reinhart
3
Évalué à la baisse, je trouve cette affirmation un peu meh "En particulier sur les machines X86 et AMD64, les conditions de course causent rarement des problèmes dans certains cas car la plupart des instructions sont atomiques et les garanties de cohérence sont très élevées." Le paragraphe devrait commencer à faire l'hypothèse explicite que vous vous concentrez sur un cœur unique. Même ainsi, les architectures multicœurs sont de facto standard de nos jours dans les appareils grand public que je considérerais comme un cas secondaire pour expliquer en dernier lieu, plutôt qu'en premier.
Patrick Trentin
3
Oh, définitivement. x86 a des tonnes de rétrocompatibilité… des trucs pour s'assurer que le code mal écrit fonctionne dans la mesure du possible. C'était vraiment un gros problème lorsque le Pentium Pro a introduit une exécution dans le désordre. Intel voulait s'assurer que la base de code installée fonctionnait sans avoir besoin d'être recompilée spécifiquement pour sa nouvelle puce. x86 a commencé comme un noyau CISC, mais a évolué en interne vers un noyau RISC, bien qu'il se présente et se comporte toujours de plusieurs façons comme CISC du point de vue d'un programmeur. Pour en savoir plus, consultez la réponse de Peter Cordes ici .
Cody Gray
20

Je pense que ce n'est pas tellement le problème si vous vous endormez avant ou après le u++. C'est plutôt que l'opération se u++traduit par du code qui est - comparé à la surcharge des threads générateurs qui appellent foo- très rapidement exécuté de sorte qu'il est peu probable qu'il soit intercepté. Cependant, si vous "prolongez" l'opération u++, la condition de concurrence deviendra beaucoup plus probable:

void foo()
{
    unsigned i = u;
    for (int s=0;s<10000;s++);
    u = i+1;
}

résultat: 694


BTW: j'ai aussi essayé

if (u % 2) {
    u += 2;
} else {
    u -= 1;
}

et cela m'a donné la plupart du temps 1997, mais parfois 1995.

Stéphan Lechner
la source
1
Je m'attendrais à ce que sur n'importe quel compilateur vaguement sain d'esprit, toute la fonction soit optimisée pour la même chose. Je suis surpris que ce ne soit pas le cas. Merci pour le résultat intéressant.
Vality
C'est tout à fait correct. Plusieurs milliers d'instructions doivent être exécutées avant que le thread suivant ne commence à exécuter la petite fonction en question. Lorsque vous rapprochez le temps d'exécution de la fonction de la surcharge de création de thread, vous voyez l'impact de la condition de concurrence critique.
Jonathon Reinhart
@Vality: Je m'attendais également à ce qu'il supprime la fausse boucle for sous l'optimisation O3. Ce n'est pas le cas?
user21820
Comment pourrait-on else u -= 1jamais être exécuté? Même dans un environnement parallèle, la valeur ne devrait jamais ne pas correspondre %2, n'est-ce pas?
mafu
2
à partir de la sortie, il semble être else u -= 1exécuté une fois, la première fois que foo () est appelée, lorsque u == 0. Les 999 fois restantes u sont impaires et u += 2sont exécutées résultant en u = -1 + 999 * 2 = 1997; c'est-à-dire la sortie correcte. Une condition de concurrence entraîne parfois l'écrasement de l'un des + = 2 par un thread parallèle et vous obtenez 1995.
Luc
7

Il souffre d'une condition de race. Mettre usleep(1000);avant u++;dans fooet je vois une sortie différente (<1000) à chaque fois.

juf
la source
6
  1. La réponse probablement pourquoi la condition de la course n'a pas manifesté pour vous, mais il ne exist, est quefoo() est si rapide, par rapport au temps qu'il faut pour démarrer un fil, que chaque fil se termine avant le prochain pouvez même commencer. Mais...

  2. Même avec votre version originale, le résultat varie selon le système: je l'ai essayé à votre guise sur un Macbook (quad-core), et en dix courses, j'ai obtenu 1000 trois fois, 999 six fois et 998 une fois. La course est donc assez rare, mais clairement présente.

  3. Vous avez compilé avec '-g', ce qui permet de faire disparaître les bugs. J'ai recompilé votre code, toujours inchangé mais sans le'-g' , et la course est devenue beaucoup plus prononcée: j'ai obtenu 1000 une fois, 999 trois fois, 998 deux fois, 997 deux fois, 996 une fois et 992 une fois.

  4. Ré. la suggestion d'ajouter un sommeil - cela aide, mais (a) un temps de sommeil fixe laisse les threads toujours biaisés par l'heure de début (sous réserve de la résolution de la minuterie), et (b) un sommeil aléatoire les étale lorsque ce que nous voulons est de rapprochez-les. Au lieu de cela, je les code pour attendre un signal de départ, afin que je puisse les créer tous avant de les laisser travailler. Avec cette version (avec ou sans '-g'), j'obtiens des résultats partout, aussi bas que 974 et pas plus élevés que 998:

    #include <iostream>
    #include <thread>
    #include <vector>
    using namespace std;
    
    unsigned u = 0;
    bool start = false;
    
    void foo()
    {
        while (!start) {
            std::this_thread::yield();
        }
        u++;
    }
    
    int main()
    {
        vector<thread> threads;
        for(int i = 0; i < 1000; i++) {
            threads.push_back (thread (foo));
        }
        start = true;
        for (auto& t : threads) t.join();
    
        cout << u << endl;
        return 0;
    }
dgould
la source
Juste une note. Le -gdrapeau ne "fait en aucun cas disparaître les bogues". L' -gindicateur sur les compilateurs GNU et Clang ajoute simplement des symboles de débogage au binaire compilé. Cela vous permet d'exécuter des outils de diagnostic comme GDB et Memcheck sur vos programmes avec une sortie lisible par l'homme. Par exemple, lorsque Memcheck est exécuté sur un programme avec une fuite de mémoire, il ne vous indiquera pas le numéro de ligne à moins que le programme n'ait été construit en utilisant l' -gindicateur.
MS-DDOS
Certes, les bogues cachés du débogueur sont généralement plus une question d'optimisation du compilateur; J'aurais dû essayer et dire «utiliser -O2 au lieu de -g». Mais cela dit, si vous n'avez jamais eu la joie de chasser un bogue qui ne se manifesterait qu'une fois compilé sans -g , considérez-vous chanceux. Cela peut arriver, avec certains des bogues d'aliasing subtils les plus méchants. Je l' ai vu, mais pas récemment, et je pourrais croire que c'était peut-être une bizarrerie d'un vieux compilateur propriétaire, donc je vais vous croire, provisoirement, à propos des versions modernes de GNU et Clang.
dgould
-gne vous empêche pas d'utiliser les optimisations. par exemple, gcc -O3 -gfait le même asm que gcc -O3, mais avec des métadonnées de débogage. gdb dira cependant "optimisé" si vous essayez d'imprimer certaines variables. -gpourrait peut-être changer les emplacements relatifs de certaines choses en mémoire, si l'un des éléments qu'il ajoute fait partie de la .textsection. Cela prend certainement de la place dans le fichier objet, mais je pense qu'après la liaison, tout se termine à une extrémité du segment de texte (pas de section), ou ne fait pas du tout partie d'un segment. Peut-être pourrait affecter où les choses sont mappées pour les bibliothèques dynamiques.
Peter Cordes