Quelle est l'efficacité du verrouillage 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 avoir un tas de mutex (comme ce que pthread me donne ou tout ce que la bibliothèque système native fournit) ou un seul pour un objet.

Quelle est l'efficacité de verrouiller un mutex? C'est-à-dire combien d'instructions d'assembleur 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 vraiment beaucoup de mutex? Ou puis-je simplement ajouter autant de variables mutex dans mon code que de intvariables et cela n'a pas vraiment d'importance?

(Je ne suis pas sûr des différences entre les différents matériels. S'il y en a, j'aimerais aussi en savoir plus à leur sujet. Mais surtout, je m'intéresse au matériel commun.)

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

Le billet de blog WebKits (2016) sur le verrouillage est très lié à cette question et explique les différences entre un verrou tournant, un verrou adaptatif, un futex, etc.

J'ai le choix entre avoir un tas de mutex ou un seul pour un objet.

Si vous avez de nombreux threads et que l'accès à l'objet se produit souvent, plusieurs verrous augmenteraient le parallélisme. Au détriment de la maintenabilité, car plus de verrouillage signifie plus de débogage du verrouillage.

Quelle est l'efficacité de verrouiller un mutex? C'est-à-dire combien d'instructions d'assembleur sont-elles probables et combien de temps prennent-elles (dans le cas où le mutex est déverrouillé)?

Les instructions d'assembleur précises sont la moindre surcharge d' un mutex - la cohérence mémoire / cache garanties de sont la principale surcharge. Et moins souvent, un verrou particulier est pris - mieux.

Le mutex est composé de deux parties principales (simplifiant à l'extrême): (1) un indicateur indiquant si le mutex est verrouillé ou non et (2) la file d'attente.

Le changement du drapeau est juste quelques instructions et normalement effectué sans appel système. Si le mutex est verrouillé, syscall ajoutera le thread appelant dans la file d'attente et démarrera l'attente. Le déverrouillage, si la file d'attente est vide, est bon marché mais nécessite sinon un appel système pour réveiller l'un des processus en attente. (Sur certains systèmes, des appels système bon marché / rapides sont utilisés pour implémenter les mutex, ils deviennent des appels système lents (normaux) uniquement en cas de conflit.)

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

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

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

Résumé. Les verrous d'espace utilisateur (et les mutex en particulier) sont bon marché et ne sont soumis à aucune limite système. Mais trop d'entre eux sont un cauchemar pour le débogage. Tableau simple:

1. Moins de verrous signifie plus de conflits (appels système lents, décrochages du processeur) et un parallélisme moindre
2. Moins de verrous signifie moins de problèmes de débogage des problèmes de multi-threading.
3. Plus de verrous signifie moins de conflits et un parallélisme plus élevé
4. Plus de verrous signifie plus de chances de se heurter à des blocages indéfendables.

Un schéma de verrouillage équilibré pour l'application doit être trouvé et maintenu, é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 avez trop de verrouillage dans votre application, une grande partie du trafic inter-CPU / cœur vide la mémoire du mutex du cache de données d'autres CPU pour garantir le cohérence du cache. Les vidages de cache sont comme des interruptions légères et sont gérés par les processeurs de manière transparente - mais ils introduisent ce que l'on appelle des stalls (recherchez "stall").

Et les blocages sont ce qui fait que le code de verrouillage s'exécute lentement, souvent sans aucune indication apparente pour laquelle l'application est lente. (Certains archets fournissent les statistiques de trafic inter-CPU / cœur, d'autres non.)

Pour éviter le problème, les gens ont généralement recours à un grand nombre de serrures pour diminuer la probabilité de conflits de serrures et pour éviter le décrochage. C'est la raison pour laquelle le verrouillage de l'espace utilisateur bon marché, non soumis aux limites du système, existe.

Je voulais savoir la même chose, alors je l'ai mesurée. Sur ma boîte (processeur AMD FX (tm) -8150 à huit cœurs à 3,612361 GHz), verrouiller et déverrouiller un mutex déverrouillé qui se trouve dans sa propre ligne de cache et est déjà mis en cache, prend 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 de verrouillage / déverrouillage qu'une fois toutes les 102 ns sur deux threads, donc une fois toutes les 51 ns, à partir de laquelle on peut conclure qu'il en faut environ 38 ns pour récupérer après qu'un thread ait fait un déverrouillage avant que le thread suivant puisse le verrouiller à nouveau.

Le programme que j'ai utilisé pour enquêter sur cela 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 en dur spécifiques à ma boîte (xrange, yrange et rdtsc overhead), vous devez donc probablement l'expérimenter avant que cela fonctionne pour vous.

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

Cela montre le résultat des exécutions de référence 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 qu'il faut pour verrouiller et déverrouiller le «mutex» (avec une surcharge de 39 horloges pour les appels rdtsc sur ma box). Le troisième asm est une boucle de retard. La taille de la boucle de délai est inférieure de 1 point pour le thread 1 à celle du thread 0, donc le thread 1 est légèrement plus rapide.

La fonction ci-dessus est appelée dans une boucle étroite de taille 100 000. Malgré cela, la fonction est légèrement plus rapide pour le thread 1, les deux boucles se synchronisent à cause de l'appel au mutex. Ceci est visible sur le graphique du fait que le nombre d'horloges mesurées pour la paire verrouillage / déverrouillage est légèrement plus grand pour le fil 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 retard loop_count de 150, puis en suivant les points en bas, vers la gauche, le loop_count est réduit d'un à chaque mesure. Lorsqu'elle devient 77, la fonction est appelée toutes les 102 ns dans les deux threads. Si par la suite loop_count est encore plus réduit, 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 verrouillage / déverrouillage. De plus, la durée moyenne de l'appel de fonction augmente à cause de cela; donc les points de l'intrigue montent maintenant et à nouveau 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 l'OP est que l'ajout de plus de mutex est préférable tant que cela entraîne moins de conflits.

Essayez de verrouiller les mutex aussi courts que possible. La seule raison de les mettre -dire- 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 multiplié par 50 ns) ou lorsque 13 ns fois la taille de la boucle est supérieure au délai que vous obtenez par contention.

EDIT: J'ai maintenant beaucoup plus de connaissances sur le sujet et je commence à douter de la conclusion que j'ai présentée ici. Tout d'abord, les CPU 0 et 1 s'avèrent être hyper-threadées; même si AMD prétend avoir 8 vrais cœurs, il y a certainement quelque chose de très louche car les délais entre deux autres cœurs sont beaucoup plus importants (c'est-à-dire que 0 et 1 forment une paire, tout comme 2 et 3, 4 et 5, et 6 et 7 ). Deuxièmement, le std :: mutex est implémenté de telle sorte qu'il se verrouille un peu avant de faire des appels système lorsqu'il ne parvient pas à obtenir immédiatement le verrou sur un mutex (ce qui sera sans aucun doute extrêmement lent). Donc, ce que j'ai mesuré ici est la situation la plus idéale absolue et dans la pratique, le verrouillage et le déverrouillage peuvent prendre beaucoup plus de temps par verrouillage / déverrouillage.

En bout de ligne, un mutex est implémenté avec atomics. Pour synchroniser les atomiques entre les cœurs, un bus interne doit être verrouillé, ce qui gèle la ligne de cache correspondante pendant plusieurs centaines de cycles d'horloge. Dans le cas où 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 (les appels système sont de l'ordre de 10 mircosecondes). Normalement, ce n'est pas vraiment un problème car ce thread doit de toute façon dormir - mais cela pourrait être un problème avec une forte contention où un thread ne peut pas obtenir le verrou pendant le temps qu'il tourne normalement et l'appel système aussi, 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 garde le verrou pendant environ 1 microseconde, alors ils pourraient être considérablement ralentis par le fait qu'ils sont constamment endormis et réveillés à nouveau. De plus, une fois qu'un thread est en veille et qu'un autre thread doit le réveiller, ce thread doit faire un appel système et est retardé d'environ 10 microsecondes; ce délai se produit donc lors du déverrouillage d'un mutex lorsqu'un autre thread attend ce mutex dans le noyau (après que la rotation ait pris trop de temps).

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

Au minimum, c'est le 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" est un objet noyau (ie - objet géré par le système d'exploitation) et exécuté en mode utilisateur - chaque opération sur celui-ci conduit à une transaction en mode noyau, ce qui est très lourd.

Par exemple sur le processeur Intel Core Duo, Windows XP. Fonctionnement verrouillé: prend environ 40 cycles CPU. Appel en mode noyau (c.-à-d. Appel système) - environ 2000 cycles CPU.

Si tel est le cas, vous pouvez envisager d'utiliser des sections critiques. C'est un hybride d'un mutex de noyau et d'un accès mémoire verrouillé.

Le coût varie en fonction de l'implémentation, mais vous devez garder à l'esprit deux choses:

• le coût sera très probablement minime car c'est à la fois une opération assez primitive et elle sera optimisée autant que possible en raison de son modèle d'utilisation ( beaucoup utilisé ).
• peu importe son coût, car vous devez l'utiliser si vous voulez un fonctionnement multi-thread sécurisé. Si vous en avez besoin, vous en avez besoin.

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

Dans ces deux cas, les instructions sont relativement efficaces.

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

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

Je suis complètement nouveau dans les pthreads et les mutex, mais je peux confirmer par l'expérimentation que le coût du verrouillage / déverrouillage d'un mutex est presque nul en l'absence de conflit, mais en cas de conflit, le coût du blocage est extrêmement élevé. J'ai exécuté un code simple avec un pool de threads dans lequel la tâche consistait simplement à calculer une somme dans une variable globale protégée par un verrou mutex:

y = exp(-j*0.0001);
pthread_mutex_lock(&lock);
x += y ;
pthread_mutex_unlock(&lock);

Avec un thread, le programme totalise 10 000 000 valeurs pratiquement instantanément (moins d'une seconde); avec deux threads (sur un MacBook à 4 cœurs), le même programme prend 39 secondes.