Data Race mit std :: unordered_map, trotz Sperren Einfügungen mit Mutex

Question

Ich habe ein C++ 11 Programm, das einige Berechnungen durchführt und eine std::unordered_map verwendet, um Ergebnisse dieser Berechnungen zwischenzuspeichern. Das Programm verwendet mehrere Threads und verwendet eine gemeinsame unordered_map, um die Ergebnisse der Berechnungen zu speichern und zu teilen.

Basierend auf meiner Lektüre von unordered_map und STL-Container-Spezifikationen sowie unordered_map thread safety, so scheint es, dass ein unordered_map, von mehreren Threads gemeinsam genutzt, kann zu einem Zeitpunkt einen Thread Schreiben handhaben, aber viele Leser auf einmal.

Daher verwende ich eine std::mutex um meine insert() Aufrufe auf die Karte zu wickeln, so dass höchstens nur ein Thread auf einmal eingefügt wird.

Allerdings haben meine find() Anrufe keinen Mutex als, aus meiner Lesung scheint es, dass viele Threads in der Lage sein sollten, auf einmal zu lesen. Allerdings bekomme ich gelegentlich Datenrennen (wie von TSAN entdeckt), die sich in einem SEGV manifestieren. Das Datenrennen weist eindeutig auf die oben erwähnten Aufrufe insert() und find() hin.

Wenn ich die find() Anrufe in einen Mutex wickeln, verschwindet das Problem. Allerdings möchte ich die gleichzeitige Lesevorgänge nicht serialisieren, da ich versuche, dieses Programm so schnell wie möglich zu machen. (FYI: Ich laufe mit gcc 5.4.)

Warum passiert das? Ist mein Verständnis der Nebenbürgschaften von std::unordered_map falsch?

Answer 1

Sie benötigen immer noch eine mutex für Ihre Leser, um die Brenner zu halten, aber Sie benötigen eine shared eins. C++14 hat ein std::shared_timed_mutex, die Sie zusammen mit scoped Schlösser std::unique_lock und std::shared_lock wie diese verwenden:

using mutex_type = std::shared_timed_mutex; 
using read_only_lock = std::shared_lock<mutex_type>; 
using updatable_lock = std::unique_lock<mutex_type>; 

mutex_type mtx; 
std::unordered_map<int, std::string> m; 

// code to update map 
{ 
    updatable_lock lock(mtx); 

    m[1] = "one"; 
} 

// code to read from map 
{ 
    read_only_lock lock(mtx); 

    std::cout << m[1] << '\n'; 
} 

Answer 2

Es gibt mehrere Probleme mit diesem Ansatz.

erste, std::unordered_map hat zwei Überladungen von find - eine, die const ist, und eine, die nicht ist.
Ich würde es wagen zu sagen, dass ich nicht glaube, dass diese nicht-const Version von find die Karte mutieren wird, aber immer noch für den Compiler non-const-Methode von einem mehrere Threads ist ein Datenrennen und einige Compiler verwenden tatsächlich undefiniert Verhalten für böse Optimierungen.
so erste Sache - Sie müssen sicherstellen, dass, wenn mehrere Threads aufrufen std::unordered_map::find sie tun es mit der const-Version. Dies kann erreicht werden, indem man die Karte mit einer const-Referenz referenziert und dann von dort aus find aufruft.

Zweitens, Sie vermissen den Teil, den viele Thread Const auf Ihrer Karte finden können, aber andere Threads können keine non const Methode auf dem Objekt aufrufen! Ich kann mir definitiv vorstellen, dass viele Threads find aufrufen und einige gleichzeitig insert aufrufen, was zu einem Datenrennen führt. Stellen Sie sich vor, dass beispielsweise insert den internen Puffer der Map neu zuordnen lässt, während ein anderer Thread ihn iteriert, um das gewünschte Paar zu finden.

eine Lösung für die Verwendung von C++ 14 shared_mutex, die einen exklusiven/gemeinsamen Sperrmodus hat. Beim Thread-Aufruf find sperrt es die Sperre für den freigegebenen Modus, wenn ein Thread insert aufruft und ihn für die exklusive Sperre sperrt.

Wenn Ihr Compiler shared_mutex nicht unterstützt, können Sie plattformspezifische Synchronisationsobjekte wie pthread_rwlock_t unter Linux und SRWLock unter Windows verwenden.

Eine andere Möglichkeit ist Lock-Free hashmap, wie die von der Intel gewinde Bausteine-Bibliothek zur Verfügung gestellt zu verwenden, oder concurrent_map auf MSVC concurrency Laufzeit. Die Implementierung selbst verwendet Lock-Free-Algorithmen, die sicherstellen, dass der Zugriff immer Thread-sicher und schnell zugleich ist.