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

149

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.

Albert
la source
Cela va être spécifique à la mise en œuvre et à l'architecture. Certains mutex ne coûteront presque rien s'il existe un support matériel natif, d'autres coûteront cher. Il est impossible de répondre sans plus d'informations.
Gian le
2
@Gian: Eh bien, bien sûr, j'implique cette sous-question dans ma question. J'aimerais connaître le matériel courant mais aussi les exceptions notables s'il y en a.
Albert le
Je ne vois vraiment cette implication nulle part. Vous posez des questions sur les "instructions de l'assembleur" - la réponse pourrait aller de 1 instruction à dix mille instructions selon l'architecture dont vous parlez.
Gian le
15
@Gian: Alors donnez exactement cette réponse. Veuillez dire ce que c'est réellement sur x86 et amd64, veuillez donner un exemple pour une architecture où il s'agit d'une instruction et en donner une avec 10k. N'est-il pas clair que je veux savoir cela d'après ma question?
Albert

Réponses:

120

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.

Dummy00001
la source
Merci, cela répond principalement à ma question. Je ne savais pas que le noyau (par exemple le noyau Linux) gère les mutex et que vous les contrôlez via des appels système. Mais comme Linux lui-même gère la planification et les changements de contexte, cela a du sens. Mais maintenant, j'ai une imagination approximative sur ce que le verrouillage / déverrouillage mutex fera en interne.
Albert
2
@Albert: Oh. J'ai oublié les commutateurs de contexte ... Les commutateurs de contexte pèsent trop sur les performances. Si l'acquisition de verrouillage échoue et que le thread doit attendre, c'est trop la moitié du changement de contexte. CS lui-même est rapide, mais comme le processeur peut être utilisé par un autre processus, les caches seraient remplis de données étrangères. Une fois que le thread a finalement acquis le verrou, il est probable que le processeur doive recharger à peu près tout à partir de la RAM.
Dummy00001
@ Dummy00001 Le passage à un autre processus signifie que vous devez modifier les mappages de mémoire de la CPU. Ce n'est pas si bon marché.
curiousguy
27

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:

entrez la description de l'image ici

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).

Carlo Wood
la source
10

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é.

Valdo
la source
7
Les sections critiques de Windows sont beaucoup plus proches des mutex. Ils ont une sémantique mutex régulière, mais ils sont locaux au processus. La dernière partie les rend beaucoup plus rapides, car ils peuvent être entièrement gérés dans votre processus (et donc le code en mode utilisateur).
MSalters le
2
Le nombre serait plus utile si la quantité de cycles CPU des opérations courantes (par exemple arithmétique / if-else / cache-miss / indirection) est également fournie à des fins de comparaison. ... Ce serait même génial s'il y avait une référence du nombre. Sur Internet, il est très difficile de trouver de telles informations.
javaLover
Les opérations @javaLover ne s'exécutent pas sur des cycles; ils fonctionnent sur des unités arithmétiques pendant un certain nombre de cycles. C'est très différent. Le coût d'une instruction any dans le temps n'est pas une quantité définie, seulement le coût d'utilisation des ressources. Ces ressources sont partagées. L'impact des instructions de mémoire dépend beaucoup de la mise en cache, etc.
curiousguy
@curiousguy D'accord. Je n'étais pas clair. Je voudrais une réponse telle que la std::mutexdurée d'utilisation moyenne (en seconde) 10 fois plus que int++. Cependant, je sais qu'il est difficile de répondre car cela dépend énormément de beaucoup de choses.
javaLover
6

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 :-)

paxdiablo
la source
1
Oui, mais quelle efficacité? S'agit-il d'une seule instruction machine? Ou environ 10? Ou environ 100? 1000? Plus? Tout cela reste efficace, mais peut faire la différence dans des situations extrêmes.
Albert le
1
Eh bien, cela dépend entièrement de la mise en œuvre. Vous pouvez désactiver les interruptions, tester / définir un entier et réactiver les interruptions dans une boucle dans environ six instructions machine. Le test et le paramétrage peuvent être effectués en autant que possible puisque les processeurs ont tendance à fournir cela comme une seule instruction.
paxdiablo
Un test-and-set verrouillé par bus est une instruction unique (assez longue) sur x86. Le reste de la machinerie pour l'utiliser est assez rapide («le test a-t-il réussi?» Est une question que les processeurs sont bons pour faire vite) mais c'est la longueur de l'instruction verrouillée sur le bus qui compte vraiment car c'est la partie qui bloque les choses. Les solutions avec interruptions sont beaucoup plus lentes, car leur manipulation est généralement limitée au noyau du système d'exploitation pour arrêter les attaques DoS triviales.
Donal Fellows
BTW, n'utilisez pas drop / reacquire comme un moyen d'avoir un thread céder aux autres; c'est une stratégie qui aspire à un système multicœur. (C'est l'une des rares choses que CPython se trompe.)
Donal Fellows
@Donal: Qu'entendez-vous par abandonner / réacquérir? Cela semble important; pouvez-vous me donner plus d'informations à ce sujet?
Albert
5

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.

Grant Petty
la source