Data race con std :: unordered_map, nonostante gli inserimenti di blocco con mutex

Question

Ho un programma C++ 11 che esegue alcuni calcoli e utilizza uno std::unordered_map per memorizzare nella cache i risultati di tali calcoli. Il programma utilizza più thread e utilizza uno spazio condiviso unordered_map per archiviare e condividere i risultati dei calcoli.

In base alla mia lettura dei unordered_map e container STL specifiche, così come unordered_map thread safety, sembra che un unordered_map, condiviso da più thread, in grado di gestire una scrittura thread alla volta, ma molti lettori alla volta.

Pertanto, sto utilizzando un std::mutex per avvolgere le mie chiamate insert() sulla mappa, in modo che al massimo venga inserito solo un thread alla volta.

Tuttavia, le mie chiamate find() non hanno un mutex come, dalla mia lettura, sembra che molti thread dovrebbero essere in grado di leggere contemporaneamente. Tuttavia, di tanto in tanto ricevo dati sulle gare (come rilevato da TSAN), manifestandosi in un SEGV. La corsa dei dati indica chiaramente le chiamate insert() e find() che ho menzionato sopra.

Quando avvolgo le chiamate find() in un mutex, il problema scompare. Tuttavia, non desidero serializzare le letture simultanee, poiché sto cercando di rendere questo programma il più veloce possibile. (FYI: Sto utilizzando gcc 5.4.)

Perché sta succedendo? La mia comprensione delle garanzie di concorrenza di std::unordered_map non è corretta?

Answer 1

Hai ancora bisogno di un mutex per i tuoi lettori di tenere fuori gli scrittori, ma è necessario uno condiviso uno. C++14 ha un std::shared_timed_mutex che è possibile utilizzare con le serrature di ambito std::unique_lock e std::shared_lock come questo:

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

Ci sono diversi problemi con questo approccio.

primo, std::unordered_map ha due sovraccarichi di find - uno che è const e uno che non lo è.
Avrei il coraggio di dire che non credo che quella versione non-const di find muta la mappa, ma ancora per il compilatore che richiama il metodo non const da un thread multiplo è una corsa di dati e alcuni compilatori effettivamente usano un comportamento indefinito per cattive ottimizzazioni.
quindi, per prima cosa, è necessario assicurarsi che quando più thread invocano std::unordered_map::find lo facciano con la versione const. ciò può essere ottenuto facendo riferimento alla mappa con un riferimento const e quindi invocando find da lì.

in secondo luogo, si perde la parte che molti thread possono invocare const sulla mappa, ma altri thread non possono richiamare il metodo non const sull'oggetto! Posso sicuramente immaginare molti thread chiamare lo find e alcuni chiamare lo insert allo stesso tempo, causando una corsa di dati. immagina che, ad esempio, insert renda il buffer interno della mappa riallocato mentre un altro thread lo itera per trovare la coppia desiderata.

una soluzione è quella di utilizzare C++ 14 shared_mutex che ha una modalità di blocco esclusivo/condiviso. quando chiama il thread find, blocca il blocco in modalità condivisa, quando un thread chiama insert lo blocca sul blocco esclusivo.

se il compilatore non supporta shared_mutex, è possibile utilizzare gli oggetti di sincronizzazione specifici della piattaforma, come pthread_rwlock_t su Linux e su Windows SRWLock.

un'altra possibilità è usare l'hashmap lock-free, come quella fornita dalla libreria di thread-building block di Intel, o concurrent_map su runtime di concorrenza MSVC. l'implementazione stessa utilizza algoritmi lock-free che assicurano che l'accesso sia sempre thread-safe e veloce allo stesso tempo.