Wie effizient ist das Sperren eines entsperrten Mutex? Was kostet ein Mutex?

In einer einfachen Sprache (C, C ++ oder was auch immer): Ich habe die Wahl zwischen einer Reihe von Mutexen (wie das, was mir pthread gibt oder was die native Systembibliothek bietet) oder einer einzelnen für ein Objekt.

Wie effizient ist es, einen Mutex zu sperren? Dh wie viele Assembler-Anweisungen gibt es wahrscheinlich und wie viel Zeit brauchen sie (für den Fall, dass der Mutex entsperrt ist)?

Was kostet ein Mutex? Ist es ein Problem, wirklich viele Mutexe zu haben? Oder kann ich einfach so viele Mutex-Variablen in meinen Code werfen, wie ich intVariablen habe, und das spielt keine Rolle?

(Ich bin mir nicht sicher, wie viele Unterschiede zwischen verschiedenen Hardwarekomponenten bestehen. Wenn ja, würde ich auch gerne davon erfahren. Aber meistens interessiere ich mich für gemeinsame Hardware.)

Der Punkt ist, dass ich durch die Verwendung vieler Mutex, die jeweils nur einen Teil des Objekts anstelle eines einzelnen Mutex für das gesamte Objekt abdecken, viele Blöcke sichern könnte. Und ich frage mich, wie weit ich damit gehen soll. Dh sollte ich versuchen, einen möglichen Block wirklich so weit wie möglich zu sichern, egal wie viel komplizierter und wie viel mehr Mutexe dies bedeutet?

Der WebKits-Blogbeitrag (2016) über das Sperren ist sehr eng mit dieser Frage verbunden und erklärt die Unterschiede zwischen einem Spinlock, einem adaptiven Schloss, einem Futex usw.

Ich habe die Wahl zwischen einer Reihe von Mutexen oder einer einzigen für ein Objekt.

Wenn Sie viele Threads haben und der Zugriff auf das Objekt häufig erfolgt, erhöhen mehrere Sperren die Parallelität. Auf Kosten der Wartbarkeit bedeutet mehr Sperren mehr Debuggen der Sperren.

Wie effizient ist es, einen Mutex zu sperren? Dh wie viel Assembler-Anweisungen gibt es wahrscheinlich und wie viel Zeit brauchen sie (für den Fall, dass der Mutex entsperrt ist)?

Die genauen Assembler-Anweisungen sind der geringste Overhead eines Mutex - die Speicher- / Cache-Kohärenzgarantien sind der Haupt-Overhead. Und seltener wird ein bestimmtes Schloss genommen - besser.

Mutex besteht aus zwei Hauptteilen (zu stark vereinfacht): (1) ein Flag, das angibt, ob der Mutex gesperrt ist oder nicht, und (2) Warteschlange.

Das Ändern des Flags ist nur ein paar Anweisungen und wird normalerweise ohne Systemaufruf durchgeführt. Wenn der Mutex gesperrt ist, fügt syscall den aufrufenden Thread in die Warteschlange ein und startet das Warten. Das Entsperren, wenn die Warteschlange leer ist, ist billig, benötigt aber ansonsten einen Systemaufruf, um einen der Wartevorgänge zu aktivieren. (Auf einigen Systemen werden billige / schnelle Systemaufrufe verwendet, um die Mutexe zu implementieren. Sie werden nur im Streitfall zu langsamen (normalen) Systemaufrufen.)

Das Sperren von freigeschaltetem Mutex ist wirklich billig. Das Freischalten von Mutex ohne Konflikte ist ebenfalls billig.

Was kostet ein Mutex? Ist es ein Problem, wirklich viele Mutexe zu haben? Oder kann ich einfach so viele Mutex-Variablen in meinen Code werfen, wie ich int-Variablen habe, und das spielt keine Rolle?

Sie können beliebig viele Mutex-Variablen in Ihren Code einfügen. Sie sind nur durch die Menge an Speicher begrenzt, die Ihre Anwendung zuweisen kann.

Zusammenfassung. User-Space-Sperren (und insbesondere die Mutexe) sind billig und unterliegen keiner Systembeschränkung. Aber zu viele von ihnen bedeuten Albtraum zum Debuggen. Einfache Tabelle:

1. Weniger Sperren bedeuten mehr Konflikte (langsame Systemaufrufe, CPU-Verzögerungen) und weniger Parallelität
2. Weniger Sperren bedeuten weniger Probleme beim Debuggen von Multithreading-Problemen.
3. Mehr Sperren bedeuten weniger Streitigkeiten und höhere Parallelität
4. Mehr Sperren bedeuten mehr Chancen, auf nicht debugierbare Deadlocks zu stoßen.

Es sollte ein ausgeglichenes Verriegelungsschema für die Anwendung gefunden und beibehalten werden, das im Allgemeinen die Nr. 2 und die Nr. 3 ausbalanciert.

(*) Das Problem mit weniger häufig gesperrten Mutexen besteht darin, dass zu viel Sperren in Ihrer Anwendung dazu führt, dass ein Großteil des Datenverkehrs zwischen CPU und Kern den Mutex-Speicher aus dem Datencache anderer CPUs löscht, um dies zu gewährleisten Cache-Kohärenz. Die Cache-Leeren sind wie leichte Interrupts und werden von CPUs transparent gehandhabt - sie führen jedoch sogenannte Stalls ein (Suche nach "Stall").

Und die Stände führen dazu, dass der Sperrcode langsam ausgeführt wird, oft ohne erkennbaren Hinweis darauf, warum die Anwendung langsam ist. (Einige Arch liefern die Inter-CPU / Core-Verkehrsstatistiken, andere nicht.)

Um das Problem zu vermeiden, greifen die Leute im Allgemeinen auf eine große Anzahl von Sperren zurück, um die Wahrscheinlichkeit von Sperrenkonflikten zu verringern und den Stall zu vermeiden. Dies ist der Grund, warum die billige Sperrung des Benutzerraums existiert, die nicht den Systembeschränkungen unterliegt.

Ich wollte dasselbe wissen, also habe ich es gemessen. Auf meiner Box (AMD FX (tm) -8150 Acht-Kern-Prozessor bei 3,612361 GHz) benötigt das Sperren und Entsperren eines entsperrten Mutex, der sich in einer eigenen Cache-Zeile befindet und bereits zwischengespeichert ist, 47 Takte (13 ns).

Aufgrund der Synchronisation zwischen zwei Kernen (ich habe CPU # 0 und # 1 verwendet) konnte ich ein Sperren / Entsperren-Paar nur einmal alle 102 ns auf zwei Threads aufrufen, also einmal alle 51 ns, woraus man schließen kann, dass es ungefähr 38 dauert ns, um wiederherzustellen, nachdem ein Thread entsperrt wurde, bevor der nächste Thread ihn wieder sperren kann.

Das Programm, mit dem ich dies untersucht habe, finden Sie hier: https://github.com/CarloWood/ai-statefultask-testsuite/blob/b69b112e2e91d35b56a39f41809d3e3de2f9e4b8/src/mutex_test.cxx

Beachten Sie, dass es einige fest codierte Werte für meine Box gibt (xrange-, yrange- und rdtsc-Overhead), sodass Sie wahrscheinlich damit experimentieren müssen, bevor es für Sie funktioniert.

Der Graph, den es in diesem Zustand erzeugt, ist:

Dies zeigt das Ergebnis von Benchmark-Läufen mit dem folgenden Code:

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;
}

Die beiden rdtsc-Aufrufe messen die Anzahl der Uhren, die zum Sperren und Entsperren von Mutex erforderlich sind (mit einem Overhead von 39 Uhren für die rdtsc-Aufrufe auf meiner Box). Der dritte Asm ist eine Verzögerungsschleife. Die Größe der Verzögerungsschleife ist für Thread 1 um 1 Anzahl kleiner als für Thread 0, sodass Thread 1 etwas schneller ist.

Die obige Funktion wird in einer engen Schleife der Größe 100.000 aufgerufen. Obwohl die Funktion für Thread 1 etwas schneller ist, werden beide Schleifen aufgrund des Aufrufs des Mutex synchronisiert. Dies ist in der Grafik aus der Tatsache ersichtlich, dass die Anzahl der für das Verriegelungs- / Entriegelungspaar gemessenen Takte für Thread 1 etwas größer ist, um die kürzere Verzögerung in der Schleife darunter zu berücksichtigen.

In der obigen Grafik ist der untere rechte Punkt eine Messung mit einer Verzögerung von loop_count von 150. Wenn Sie dann den Punkten unten nach links folgen, wird der loop_count bei jeder Messung um eins reduziert. Wenn es 77 wird, wird die Funktion in beiden Threads alle 102 ns aufgerufen. Wenn anschließend loop_count noch weiter reduziert wird, ist es nicht mehr möglich, die Threads zu synchronisieren, und der Mutex wird die meiste Zeit tatsächlich gesperrt, was zu einer erhöhten Anzahl von Uhren führt, die zum Sperren / Entsperren erforderlich sind. Dadurch erhöht sich auch die durchschnittliche Zeit des Funktionsaufrufs; Die Handlungspunkte gehen nun wieder nach rechts.

Daraus können wir schließen, dass das Sperren und Entsperren eines Mutex alle 50 ns auf meiner Box kein Problem darstellt.

Alles in allem ist meine Schlussfolgerung, dass die Antwort auf die Frage von OP lautet, dass das Hinzufügen von mehr Mutexen besser ist, solange dies zu weniger Konflikten führt.

Versuchen Sie, Mutexe so kurz wie möglich zu halten. Der einzige Grund, sie außerhalb einer Schleife zu platzieren, wäre, wenn diese Schleife alle 100 ns schneller als einmal wiederholt wird (oder besser gesagt, die Anzahl der Threads, die diese Schleife gleichzeitig ausführen möchten, mal 50 ns) oder wenn 13 ns mal Die Schleifengröße ist mehr Verzögerung als die Verzögerung, die Sie durch Konkurrenz erhalten.

EDIT: Ich habe jetzt viel mehr über das Thema erfahren und beginne an der Schlussfolgerung zu zweifeln, die ich hier vorgestellt habe. Zunächst stellen sich heraus, dass CPU 0 und 1 Hyper-Threaded sind. Obwohl AMD behauptet, 8 echte Kerne zu haben, gibt es sicherlich etwas sehr faul, da die Verzögerungen zwischen zwei anderen Kernen viel größer sind (dh 0 und 1 bilden ein Paar, ebenso wie 2 und 3, 4 und 5 und 6 und 7 ). Zweitens ist der std :: mutex so implementiert, dass er Sperren ein wenig dreht, bevor er tatsächlich Systemaufrufe ausführt, wenn er die Sperre für einen Mutex nicht sofort erhält (was zweifellos extrem langsam sein wird). Was ich hier gemessen habe, ist die absolut idealste Situation. In der Praxis kann das Sperren und Entsperren pro Sperre / Entsperrung drastisch länger dauern.

Unterm Strich wird ein Mutex mit Atomics implementiert. Um Atomics zwischen Kernen zu synchronisieren, muss ein interner Bus gesperrt werden, der die entsprechende Cache-Zeile für mehrere hundert Taktzyklen einfriert. Für den Fall, dass keine Sperre erhalten werden kann, muss ein Systemaufruf ausgeführt werden, um den Thread in den Ruhezustand zu versetzen. das ist offensichtlich extrem langsam (Systemaufrufe liegen in der Größenordnung von 10 Mircosekunden). Normalerweise ist das kein wirkliches Problem, da dieser Thread sowieso schlafen muss - aber es könnte ein Problem mit hohen Konflikten sein, bei dem ein Thread die Sperre für die Zeit, in der er sich normalerweise dreht, nicht erhalten kann, und der Systemaufruf auch, aber CAN Nehmen Sie kurz darauf das Schloss. Wenn beispielsweise mehrere Threads einen Mutex in einer engen Schleife sperren und entsperren und jeder die Sperre etwa 1 Mikrosekunde lang beibehält, dann könnten sie enorm verlangsamt werden, weil sie ständig eingeschläfert und wieder aufgewacht werden. Sobald ein Thread in den Ruhezustand versetzt wurde und ein anderer Thread ihn aufwecken muss, muss dieser Thread einen Systemaufruf ausführen und ist um ~ 10 Mikrosekunden verzögert. Diese Verzögerung tritt also beim Entsperren eines Mutex auf, wenn ein anderer Thread im Kernel auf diesen Mutex wartet (nachdem das Drehen zu lange gedauert hat).

Dies hängt davon ab, was Sie tatsächlich als "Mutex", Betriebssystemmodus usw. bezeichnen.

bei Mindest ist es eine Kosten für eine verriegelte Speicheroperation. Es ist eine relativ schwere Operation (im Vergleich zu anderen primitiven Assembler-Befehlen).

Das kann jedoch sehr viel höher sein. Wenn das, was Sie "Mutex" nennen, ein Kernel-Objekt (dh ein vom Betriebssystem verwaltetes Objekt) ist und im Benutzermodus ausgeführt wird, führt jede Operation dazu zu einer Kernel-Modus-Transaktion, was sehr ist schwer ist.

Zum Beispiel auf dem Intel Core Duo-Prozessor Windows XP. Verriegelter Betrieb: dauert ca. 40 CPU-Zyklen. Kernel-Modus-Aufruf (dh Systemaufruf) - ca. 2000 CPU-Zyklen.

Wenn dies der Fall ist, können Sie kritische Abschnitte verwenden. Es ist eine Mischung aus Kernel-Mutex und verriegeltem Speicherzugriff.

Die Kosten variieren je nach Implementierung, Sie sollten jedoch zwei Dinge beachten:

• die Kosten wahrscheinlich minimal sein werden , da sie beide sind eine ziemlich primitive Operation , und es wird so viel wie möglich aufgrund seiner Verwendung Muster (a verwendet optimiert wird viel ).
• Es spielt keine Rolle, wie teuer es ist, da Sie es verwenden müssen, wenn Sie einen sicheren Multithread-Betrieb wünschen. Wenn Sie es brauchen, dann brauchen Sie es.

Auf Einzelprozessorsystemen können Sie Interrupts im Allgemeinen nur so lange deaktivieren, bis Daten atomar geändert werden. Multiprozessorsysteme können eine Test-and-Set- Strategie verwenden.

In beiden Fällen sind die Anweisungen relativ effizient.

Es ist ein Balanceakt, ob Sie einen einzelnen Mutex für eine massive Datenstruktur bereitstellen oder viele Mutexe haben sollten, einen für jeden Abschnitt davon.

Wenn Sie einen einzelnen Mutex haben, besteht ein höheres Risiko für Konflikte zwischen mehreren Threads. Sie können dieses Risiko verringern, indem Sie einen Mutex pro Abschnitt haben, aber Sie möchten nicht in eine Situation geraten, in der ein Thread 180 Mutexe sperren muss, um seine Aufgabe zu erfüllen :-)

Ich bin völlig neu in Pthreads und Mutex, aber ich kann durch Experimente bestätigen, dass die Kosten für das Sperren / Entsperren eines Mutex fast null sind, wenn es keine Konflikte gibt, aber wenn es Konflikte gibt, sind die Kosten für das Blockieren extrem hoch. Ich habe einen einfachen Code mit einem Thread-Pool ausgeführt, in dem die Aufgabe nur darin bestand, eine Summe in einer globalen Variablen zu berechnen, die durch eine Mutex-Sperre geschützt ist:

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

Mit einem Thread summiert das Programm praktisch sofort 10.000.000 Werte (weniger als eine Sekunde). Bei zwei Threads (auf einem MacBook mit 4 Kernen) dauert dasselbe Programm 39 Sekunden.