Гонка данных с std :: unordered_map, несмотря на блокировку вставки с мьютексом

Question

У меня есть программа C++ 11, которая выполняет некоторые вычисления и использует std::unordered_map для кэширования результатов этих вычислений. Программа использует несколько потоков, и они используют общий unordered_map для хранения и совместного использования результатов вычислений.

Основываясь на моем чтении unordered_map и STL контейнеров спецификации, а также unordered_map thread safety, кажется, что unordered_map, разделяемые несколькими потоками, может обрабатывать одну нить писать в то время, но многие читатели в то время.

Поэтому я использую std::mutex для переноса моих insert() звонков на карту, так что не более одного потока вставляется одновременно.

Однако мои звонки find() не имеют мьютекса, так как из моего чтения кажется, что многие потоки должны быть в состоянии читать сразу. Тем не менее, я иногда получаю данные рас (как было обнаружено TSAN), проявляясь в SEGV. Гонка данных четко указывает на вызовы insert() и find(), о которых я упоминал выше.

Когда я обертываю вызовы find() в мьютексе, проблема исчезает. Тем не менее, я не хочу сериализовать параллельные чтения, поскольку я пытаюсь сделать эту программу как можно быстрее. (FYI: я бегу с использованием gcc 5.4.)

Почему это происходит? Является ли мое понимание гарантий параллельности для std::unordered_map неверным?

Answer 1

Вам по-прежнему нужен mutex для ваших читателей, чтобы оставить авторов, но вам нужен общий номер. C++14 имеет std::shared_timed_mutex, что вы можете использовать вместе с контекстными замками std::unique_lock и std::shared_lock как это:

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

Есть несколько проблем с этим подходом.

Первый, std::unordered_map имеет две перегрузки find - тот, который const, и тот, который нет.
Я бы осмелился сказать, что я не верю, что эта неконстантная версия find будет мутировать карту, но все же для компилятора, вызывающего метод non const из нескольких потоков, является гонка данных, а некоторые компиляторы фактически используют неопределенное поведение для неприятных оптимизаций.
так что сначала вам нужно убедиться, что, когда несколько потоков ссылаются на std::unordered_map::find, они делают это с версией const. что может быть достигнуто путем ссылки на карту с ссылкой на константу и последующим вызовом от find.

Во-вторых, вы пропустите часть, которую многие нитки могут вызывать на карте найти const, но другие потоки не могут вызывать метод non const на объекте! Я могу определенно представить, что многие потоки называют find, а некоторые звонят insert в то же время, вызывая гонку данных. предположим, что, например, insert заставляет внутренний буфер карты перераспределять, а другой поток выполняет итерацию, чтобы найти нужную пару.

решение для использования C++ 14 shared_mutex, которое имеет режим эксклюзивной/общей блокировки. при вызове потока find он блокирует блокировку в режиме общего доступа, когда поток вызывает insert, он блокирует его на эксклюзивной блокировке.

Если ваш компилятор не поддерживает shared_mutex, вы можете использовать объекты синхронизации на платформе, такие как pthread_rwlock_t на Linux и SRWLock на Windows.

Другая возможность - использовать блокировку без блокировки, такую ​​как библиотека, предоставляемая библиотекой нитевидных блоков Intel, или concurrent_map в среде выполнения параллелизма MSVC. сама реализация использует алгоритмы без блокировки, которые гарантируют, что доступ всегда будет потокобезопасным и быстрым в одно и то же время.