Quelle est l’efficacité du locking d’un mutex déverrouillé? Quel est le coût d’un mutex?

Dans un langage de bas niveau (C, C ++ ou autre): j’ai le choix entre un tas de mutex (comme ce que pthread me donne ou ce que la bibliothèque de système native fournit) ou un seul pour un object.

Est-ce efficace de verrouiller un mutex? C’est-à-dire combien de fois les instructions d’assemblage sont-elles probables et combien de temps prennent-elles (dans le cas où le mutex est déverrouillé)?

Combien coûte un mutex? Est-ce un problème d’avoir beaucoup de mutex? Ou est-ce que je peux simplement lancer autant de variables de mutex dans mon code que de variables int et cela n’a pas vraiment d’importance?

(Je ne suis pas sûr de l’importance des différences entre les différents matériels. Si c’est le cas, je voudrais aussi savoir à leur sujet. Mais surtout, je suis intéressé par le matériel commun.)

Le fait est que, en utilisant de nombreux mutex qui ne couvrent chacun qu’une partie de l’object au lieu d’un seul mutex pour l’object entier, je pourrais protéger de nombreux blocs. Et je me demande jusqu’où je devrais aller à ce sujet. Est-ce que je devrais essayer de sécuriser autant que possible tout blocage possible, peu importe combien cela est compliqué et combien plus de mutex cela signifie?

    J’ai le choix entre un groupe de mutex ou un seul pour un object.

    Si vous avez beaucoup de threads et que l’access à l’object se produit souvent, alors plusieurs lockings augmenteraient le parallélisme. Au désortingment de la maintenabilité, puisque plus de locking signifie plus de débogage du locking.

    Est-ce efficace de verrouiller un mutex? C’est-à-dire combien de fois les instructions d’assemblage sont-elles probables et combien de temps prennent-elles (dans le cas où le mutex est déverrouillé)?

    Les instructions précises de l’assembleur sont les moindres frais d’ un mutex – les garanties de cohérence mémoire / cache sont la principale surcharge. Et moins souvent un verrou particulier est pris – mieux.

    Mutex est composé de deux parties principales (simplification excessive): (1) un indicateur indiquant si le mutex est verrouillé ou non et (2) la queue.

    Le changement du drapeau ne concerne que quelques instructions et se fait normalement sans appel système. Si mutex est verrouillé, syscall va append le thread appelant dans la queue et lancer l’attente. Le délocking, si la queue est vide, est bon marché mais nécessite un appel système pour réveiller l’un des processus en attente. (Sur certains systèmes, des appels système rapides / bon marché sont utilisés pour implémenter les mutex, ils deviennent des appels système lents (normaux) uniquement en cas de conflit.)

    Verrouiller le mutex déverrouillé est vraiment bon marché. Déverrouiller mutex sans contention est également bon marché.

    Combien coûte un mutex? Est-ce un problème d’avoir beaucoup de mutex? Ou est-ce que je peux simplement lancer autant de variables de mutex dans mon code que de variables internes et cela n’a pas vraiment d’importance?

    Vous pouvez lancer autant de variables mutex dans votre code que vous le souhaitez. Vous êtes uniquement limité par la quantité de mémoire que votre application peut allouer.

    Résumé. Les verrous de l’espace utilisateur (et les mutex en particulier) sont peu coûteux et ne sont soumis à aucune limite système. Mais trop d’entre eux épouvent le cauchemar pour le débogage. Tableau simple:

    1. Moins de verrous signifie plus de contentions (appels système lents, blocages de processeurs) et moins de parallélisme
    2. Moins de verrous signifie moins de problèmes de débogage des problèmes multi-threading.
    3. Plus de verrous signifie moins de querelles et un plus grand parallélisme
    4. Plus de verrous signifie plus de chances de se heurter à des blocages impossibles à neutraliser.

    Un système de locking équilibré pour l’application doit être trouvé et maintenu, en équilibrant généralement le n ° 2 et le n ° 3.


    (*) Le problème avec les mutex moins souvent verrouillés est que si vous verrouillez trop votre application, le trafic inter-CPU / core déborde la mémoire mutex du cache de données des autres CPU pour garantir la cohérence du cache. Les vidages de cache sont comme des interruptions légères et gérés de manière transparente par les CPU, mais ils introduisent des “stalls” (recherche de “stall”).

    Et les cales sont ce qui fait que le code de locking fonctionne lentement, souvent sans aucune indication apparente de la lenteur de l’application. (Certains arch fournissent les statistiques de trafic inter-CPU / core, d’autres non.)

    Pour éviter le problème, les gens ont généralement recours à un grand nombre de verrous pour réduire la probabilité de conflits de locking et pour éviter le décrochage. C’est la raison pour laquelle le locking de l’espace utilisateur à bas prix, non soumis aux limites du système, existe.

    Cela dépend de ce que vous appelez réellement “mutex”, du mode OS, etc.

    Au minimum, il s’agit d’un coût d’une opération de mémoire verrouillée. C’est une opération relativement lourde (comparée à d’autres commandes d’assembleur primitives).

    Cependant, cela peut être beaucoup plus élevé. Si ce que vous appelez “mutex” un object du kernel (par exemple, un object géré par le système d’exploitation) et s’exécute en mode utilisateur, chaque opération entraîne une transaction en mode kernel, ce qui est très lourd.

    Par exemple, sur le processeur Intel Core Duo, Windows XP. Opération verrouillée: prend environ 40 cycles de processeur. Appel en mode kernel (appel système) – environ 2000 cycles de processeur.

    Si tel est le cas, vous pouvez envisager d’utiliser des sections critiques. C’est un hybride d’un mutex du kernel et d’un access mémoire verrouillé.

    Je voulais savoir la même chose, alors je l’ai mesuré. Sur ma boîte (processeur AMD FX ™ -8150 Eight-Core à 3.612361 GHz), le locking et le délocking d’un mutex déverrouillé se trouvant dans sa propre ligne de cache et déjà en cache nécessite 47 horloges (13 ns).

    En raison de la synchronisation entre deux cœurs (j’ai utilisé les processeurs n ° 0 et n ° 1), je ne pouvais appeler une paire verrouiller / déverrouiller qu’une fois toutes les 102 ns sur deux threads, donc une fois toutes les 51 ns ns pour récupérer après un délocking d’un thread avant que le prochain thread puisse le verrouiller à nouveau.

    Le programme que j’ai utilisé pour étudier ceci peut être trouvé ici: https://github.com/CarloWood/ai-statefultask-testsuite/blob/b69b112e2e91d35b56a39f41809d3e3de2f9e4b8/src/mutex_test.cxx

    Notez qu’il a quelques valeurs codées spécifiques à ma boîte (xrange, yrange et rdtsc overhead), vous devrez donc probablement les tester avant qu’il ne fonctionne pour vous.

    Le graphique qu’il produit dans cet état est:

    entrer la description de l'image ici

    Cela montre le résultat de l’exécution de tests sur le code suivant:

     uint64_t do_Ndec(int thread, int loop_count) { uint64_t start; uint64_t end; int __d0; asm volatile ("rdtsc\n\tshl $32, %%rdx\n\tor %%rdx, %0" : "=a" (start) : : "%rdx"); mutex.lock(); mutex.unlock(); asm volatile ("rdtsc\n\tshl $32, %%rdx\n\tor %%rdx, %0" : "=a" (end) : : "%rdx"); asm volatile ("\n1:\n\tdecl %%ecx\n\tjnz 1b" : "=c" (__d0) : "c" (loop_count - thread) : "cc"); return end - start; } 

    Les deux appels rdtsc mesurent le nombre d’horloges nécessaires pour verrouiller et déverrouiller `mutex ‘(avec une surcharge de 39 horloges pour les appels rdtsc sur ma boîte). La troisième asm est une boucle de retard. La taille de la boucle de délai est inférieure d’un point pour le thread 1 par rapport au thread 0, donc le thread 1 est légèrement plus rapide.

    La fonction ci-dessus est appelée dans une boucle serrée de taille 100 000. Bien que la fonction soit légèrement plus rapide pour le thread 1, les deux boucles se synchronisent à cause de l’appel au mutex. Ceci est visible dans le graphique du fait que le nombre d’horloges mesurées pour la paire locking / délocking est légèrement plus grand pour le thread 1, pour tenir compte du délai plus court dans la boucle en dessous.

    Dans le graphique ci-dessus, le point en bas à droite est une mesure avec un loop_count de retard de 150, puis en suivant les points en bas, vers la gauche, le nombre de boucles est réduit de un pour chaque mesure. Quand il devient 77, la fonction est appelée toutes les 102 ns dans les deux threads. Si par la suite loop_count est réduit encore plus, il n’est plus possible de synchroniser les threads et le mutex commence à être réellement verrouillé la plupart du temps, ce qui entraîne une augmentation du nombre d’horloges nécessaires pour effectuer le locking / délocking. De même, le temps moyen de l’appel de fonction augmente à cause de cela; de sorte que les points d’insortinggue montent maintenant vers la droite.

    De cela, nous pouvons conclure que verrouiller et déverrouiller un mutex toutes les 50 ns n’est pas un problème sur ma boîte.

    Dans l’ensemble, ma conclusion est que la réponse à la question de OP est que l’ajout de mutex est meilleur tant que cela se traduit par moins de conflits.

    Essayez de verrouiller les mutex aussi courts que possible. La seule raison de les mettre en dehors d’une boucle serait si cette boucle boucle plus vite qu’une fois toutes les 100 ns (ou plutôt le nombre de threads qui veulent exécuter cette boucle en même temps 50 ns) ou quand 13 ns fois la taille de la boucle est plus longue que le délai obtenu par contention.

    EDIT: Je suis devenu beaucoup plus compétent sur le sujet maintenant et commence à douter de la conclusion que j’ai présentée ici. Tout d’abord, les processeurs 0 et 1 s’avèrent être hyper-threadés; même si AMD prétend avoir 8 cœurs réels, il y a certainement quelque chose de très louche car les délais entre deux autres cœurs sont beaucoup plus importants (0 et 1 forment une paire, comme 2 et 3, 4 et 5 et 6 et 7). ). Deuxièmement, le std :: mutex est implémenté de telle manière qu’il tourne un peu avant de passer aux appels système lorsqu’il ne parvient pas à obtenir immédiatement le verrou sur un mutex (ce qui sera sans doute extrêmement lent). Donc, ce que j’ai mesuré ici est la situation la plus idéale et, en pratique, le locking et le délocking peuvent prendre énormément de temps par verrou / délocking.

    En fin de compte, un mutex est implémenté avec l’atome. Pour synchroniser les atomes entre les kernelx, un bus interne doit être verrouillé, ce qui gèle la ligne de cache correspondante pendant plusieurs centaines de cycles d’horloge. Si un verrou ne peut pas être obtenu, un appel système doit être effectué pour mettre le thread en veille; c’est évidemment extrêmement lent. Normalement, ce n’est pas vraiment un problème car ce thread doit dormir de toute façon – mais cela peut être un problème avec un conflit élevé où un thread ne peut pas obtenir le verrou pendant le temps qu’il tourne normalement et l’appel système, mais CAN prenez la serrure peu de temps après. Par exemple, si plusieurs threads verrouillent et déverrouillent un mutex dans une boucle serrée et que chacun conserve le verrou pendant environ 1 microseconde, ils peuvent être considérablement ralentis par le fait qu’ils sont constamment endormis et réveillés à nouveau.

    Le coût variera en fonction de la mise en œuvre, mais vous devez garder à l’esprit deux choses:

    • le coût sera probablement minime car il s’agit d’une opération assez primitive et elle sera optimisée autant que possible en raison de son mode d’utilisation (utilisé souvent).
    • Peu importe le prix, vous devez l’utiliser si vous souhaitez un fonctionnement multithread sécurisé. Si vous en avez besoin, alors vous en avez besoin.

    Sur les systèmes monoprocesseurs, vous pouvez généralement désactiver les interruptions suffisamment longtemps pour modifier de manière atomique les données. Les systèmes multiprocesseurs peuvent utiliser une stratégie de test et de définition .

    Dans les deux cas, les instructions sont relativement efficaces.

    Quant à savoir si vous devez fournir un seul mutex pour une structure de données massive, ou si vous avez plusieurs mutex, un pour chaque section, c’est un exercice d’équilibre.

    En ayant un seul mutex, vous courez un plus grand risque de conflit entre plusieurs threads. Vous pouvez réduire ce risque en ayant un mutex par section, mais vous ne voulez pas vous retrouver dans une situation où un thread doit verrouiller 180 mutex pour faire son travail 🙂