Gibt es Probleme mit einer großen Anzahl von kritischen Abschnitten?

Question

Ich habe eine große Anzahl von Strukturen, etwa diese:

typedef struct
{
    int a;
    int b;
    int c;
    etc...
}
data_type;

data_type data[100000];

Ich habe eine Reihe von separaten Threads, von denen jeder Änderungen an Elementen innerhalb von data[] vornehmen möchte. Ich muss sicherstellen, dass nicht zwei Threads gleichzeitig versuchen, auf dasselbe Datenelement zuzugreifen. Um genau zu sein: ein Thread, der data[475].a = 3; und ein anderer Thread, der data[475].b = 7; zur gleichen Zeit ausführt, ist nicht erlaubt, aber ein Thread, der data[475].a = 3; ausführt, während ein anderer Thread data[476].a = 7; ausführt, ist erlaubt. Das Programm ist sehr Geschwindigkeit kritisch. Mein Plan ist es, für jedes Datenelement einen separaten kritischen Abschnitt zu erstellen, etwa so:

typedef struct
{
    CRITICAL_SECTION critsec;
    int a;
    int b;
    int c;
    etc...
}
data_type;

Auf eine Art und Weise ich denke, es sollte alles funktionieren und ich sollte keine wirklichen Fragen haben, aber nicht mit viel Erfahrung in Multithread-Programmierung habe ich nur ein wenig unruhig über so viele kritische Abschnitte fühlen. Ich frage mich, ob die schiere Anzahl von ihnen eine Art von Ineffizienz verursachen könnte. Ich frage mich auch, ob vielleicht eine andere Multithreading-Technik schneller sein könnte? Sollte ich mich einfach entspannen und mit Plan A weitermachen?

Answer 1

Bei so vielen Objekten sind die meisten kritischen Abschnitte freigeschaltet, und es gibt fast keine Konflikte mehr. Wie Sie bereits wissen (anderer Kommentar), benötigen kritische Abschnitte keinen Kernel-Mode-Übergang, wenn sie nicht in Besitz sind. Das macht kritische Abschnitte für diese Situation effizient.

Die einzige andere Überlegung wäre, ob Sie die kritischen Abschnitte innerhalb Ihrer Objekte oder in einem anderen Array haben wollen. Die Lokalität der Referenz ist ein guter Grund, die kritischen Abschnitte innerhalb des Objekts unterzubringen. Wenn Sie den kritischen Abschnitt eingegeben haben, befindet sich eine ganze Cache-Zeile (z. B. 16 oder 32 Byte) im Speicher. Mit ein wenig Auffüllen können Sie sicherstellen, dass jedes Objekt auf einer Cache-Zeile beginnt. Dadurch befindet sich das Objekt (teilweise) im Cache, sobald sein kritischer Abschnitt erreicht ist.

Answer 2

Ihr Plan ist einen Versuch wert, aber ich denke, Sie werden feststellen, dass Windows unglücklich darüber ist, so viele Critical Sections zu erstellen. Jeder CS enthält ein oder mehrere Kernel-Handles und Sie verbrauchen wertvollen Kernel-Speicherplatz. Ich denke, je nach Ihrer Windows-Version wird Ihnen der Handle-Speicher ausgehen und InitializeCriticalSection() oder eine andere Funktion wird fehlschlagen.

Was Sie tun könnten, ist ein Pool von CSs für die Verwendung zur Verfügung haben, und speichern Sie einen Zeiger auf die "in Gebrauch" CS innerhalb Ihrer Struktur. Aber dann wird es ziemlich schnell kompliziert und Sie müssen Atomic-Operationen verwenden, um den CS-Zeiger zu setzen/zu löschen (auf atomar den Array-Eintrag als 'in Gebrauch' kennzeichnen). Möglicherweise müssen auch einige Verweise gezählt werden, usw...

Es wird kompliziert.

Versuchen Sie es also zuerst auf Ihre Art und Weise, und sehen Sie, was passiert. Wir hatten einmal eine ähnliche Situation und mussten uns für einen Pool entscheiden, aber vielleicht haben sich die Dinge seither geändert.

Answer 3

Je nach den Typen der Datenelemente in Ihrer data_type-Struktur (und auch je nach den Operationen, die Sie mit diesen Elementen durchführen möchten) können Sie möglicherweise auf die Verwendung eines separaten Synchronisationsobjekts verzichten und stattdessen die Interlocked-Funktionen verwenden.

In Ihrem Beispielcode sind alle Datenelemente Ganzzahlen, und alle Operationen sind Zuweisungen (und vermutlich Lesevorgänge), so dass Sie InterlockedExchange() verwenden könnten, um die Werte atomar zu setzen und InterlockedCompareExchange(), um die Werte atomar zu lesen.

Wenn Sie nicht-ganzzahlige Datentypen verwenden, komplexere Operationen durchführen oder den atomaren Zugriff auf mehr als eine Operation gleichzeitig koordinieren müssen (z. B. data[1].a lesen und dann data[1].b schreiben), müssen Sie ein Synchronisationsobjekt wie CRITICAL_SECTION verwenden.

Wenn Sie ein Synchronisationsobjekt verwenden müssen, empfehle ich Ihnen, Ihren Datensatz in Teilmengen aufzuteilen und ein einziges Synchronisationsobjekt pro Teilmenge zu verwenden. Sie könnten zum Beispiel ein CRITICAL_SECTION für jede Spanne von 1000 Elementen im Datenfeld verwenden.

Answer 4

Sie könnten auch MUTEX in Betracht ziehen. Dies ist eine gute Methode. Jeder Client könnte die Ressource selbst mit Mutex (gegenseitiger Ausschluss) reservieren.

Dies ist häufiger der Fall, einige Bibliotheken unterstützen dies auch mit Threads. Lesen Sie über boost::thread und es ist Mutexe

Mit Ihrem Ansatz:

data_type data[100000];

Ich hätte Angst vor einem Stapelüberlauf, es sei denn, Sie allozieren es auf dem Heap.

EDITAR:

Boost::MUTEX verwendet win32 Critical Sections

Answer 5

Wie andere darauf hingewiesen haben, ja gibt es ein Problem, und es heißt zu feinkörnig Sperren.. es ist Ressourcen verschwenderisch und obwohl die Chancen gering sind, werden Sie beginnen, eine Menge von Backing-Primitive und Daten zu erstellen, wenn die Dinge eine gelegentliche, nennen Sie es länger als üblich oder was auch immer, Konflikt. Außerdem werden Ressourcen verschwendet, da es sich nicht wirklich um eine triviale Datenstruktur handelt, wie zum Beispiel bei VM-Impls.

Wenn ich mich richtig erinnere, haben Sie ab diesem Zeitpunkt unter Win32 eine höhere Wahrscheinlichkeit einer SEH-Ausnahme oder einfach eine höhere Speichernutzung. Partitionierung und Pooling sie ist wahrscheinlich der Weg zu gehen, aber es ist eine komplexere Implementierung. Paritioning auf etwas anderes (re:action) und erwarten einige kurzlebige Streitigkeiten ist eine weitere Möglichkeit, damit umzugehen.

In jedem Fall ist es ein Problem der Ressourcenverwaltung mit dem, was Sie jetzt haben.