Mit vielen Mutex Schlösser

Question

Ich habe eine große Baumstruktur auf der mehrere Threads gleichzeitig arbeiten. Idealerweise hätte ich gerne eine individuelle Mutex-Sperre für jede Zelle.

Ich sah die Definition von pthread_mutex_t in bits/pthreadtypes.h und es ist ziemlich kurz, so dass die Speichernutzung kein Problem in meinem Fall sein sollte.

Gibt es jedoch eine Leistungseinbuße bei der Verwendung von vielen (sagen wir ein paar tausend) verschiedenen pthread_mutex_t s für nur 8 Threads?

Answer 1

Wenn Sie sehr häufig sperren und entsperren, kann es zu einer Strafe kommen, da das Abrufen und Freigeben von Sperren einige Zeit in Anspruch nimmt und bei Sperren viel Zeit in Anspruch nehmen kann.

Wenn viele Schlösser in einer Struktur wie diese verwendet, werden Sie sehr spezifisch sein, was eigentlich jedes Schloss verriegelt, und stellen Sie sicher, dass Sie von AB-BA Deadlocks vorsichtig sind. Wenn Sie beispielsweise die Struktur des Baums während einer Sperroperation ändern, müssen Sie alle Knoten, die geändert werden sollen, in einer konsistenten Reihenfolge sperren und sicherstellen, dass Threads, die an Nachkommen arbeiten, nicht verwechselt werden.

Wenn Sie sehr viele Sperren haben, die sich über den gesamten Arbeitsspeicher verteilen, können Caching-Probleme je nach Architektur zu Leistungsproblemen führen, da Sperrvorgänge zumindest einen Teil des Caches ungültig machen.

Ihre beste Wette ist wahrscheinlich eine einfache Verriegelungsstruktur zu implementieren, dann ist es das Profil, dann verfeinern sie die Leistung zu verbessern, falls erforderlich. Ich bin mir nicht sicher, was Sie mit dem Baum machen, aber ein guter Anfang ist vielleicht eine einzige Leser-Schreiber-Sperre für den ganzen Baum, wenn Sie erwarten, dass Sie viel mehr lesen, als Sie aktualisieren.

"Wir sollten kleine Wirkungsgrade vergessen, sagen etwa 97% der Zeit: vorzeitige Optimierung ist die Wurzel allen Übels." - Donald Knuth

Answer 2

Ihre Sperr-/Zugriffsmuster müssen angegeben werden, um dies richtig zu bewerten. Wenn jeder Thread nur eine oder mehrere Sperren gleichzeitig hält und die Wahrscheinlichkeit, dass zwei oder mehr Threads die gleiche Sperre zur gleichen Zeit wünschen, ist niedrig (entweder ein Zufallszugriffsmuster oder 8 Läufer an verschiedenen Positionen auf einer kreisförmigen Spur mit ungefähr der gleichen Geschwindigkeit oder anderen komplizierteren Dingen laufen), dann werden Sie meistens den schlimmsten Fall vermeiden, wo ein Thread schlafen muss, um eine Sperre zu erhalten (oder in einigen Fällen das Betriebssystem involviert zu entscheiden, wer gewinnt), weil Sie es haben wenige Fäden und so viele Schlösser.

Wenn jeder Thread zu jeder Zeit wollen vielleicht Hunderte oder Tausende von Sperren dann werden die Dinge beginnen sich zu ändern.

Ich werde Deadlock-Vermeidung nicht berühren, weil ich nichts über den Container weiß, den Sie verwenden, aber Sie müssen sich der Notwendigkeit bewusst sein, sie zu vermeiden.