Итерация по вектору в одном потоке, в то время как другой потенциально может изменить ссылку
У меня есть вектор allow_list, который периодически обновляется в потоке, в то время как другой выполняет функцию, которая проверяет, находится ли в этом allow_list определенная строка через:
if (std::find(allow_list->begin(), allow_list->end(), target_string) != allow_list->end()){
allow = true;
}
Теперь другой поток может сделать что-то вроде этого
// Some operation to a vector called allow_list_updated
allow_list = allow_list_updated;
Должен ли я добавить сюда мьютекс для блокировки и разблокировки до и после этих операций? Моя интуиция подсказывает мне, что это «нормально» и не должно зависать и гореть, но мне это кажется неопределенным поведением.
find фактически является циклом, повторяющим вектор. AFAICT, вы настраиваете сценарий, в котором вы потенциально заменяете весь массив, управляемый allow_list, новым в середине цикла, делая недействительными все старые итераторы и освобождая память старого, к которому теперь недопустимые итераторы обращались. Кажется, что «разбить и сжечь» — это именно то, о чем идет речь.
Я смущен. Так что, если итераторы станут недействительными? Каждый раз, когда вызывается find, он вызывает begin() и end() для allow_list, и результат поиска будет основываться на allow_list.
find — это конструкция исходного кода C++. Это не машинная инструкция или атомарность. Это сокращение от цикла, который постоянно обновляет итератор и проверяет условие. Если у него есть 100 элементов для итерации, и как только он проходит первые 50, ваш другой поток отключает итераторы и уничтожает массив, БУМ! Это зависит от времени. То, что это не происходит в одном (или 200) прогоне, не означает, что этого не может произойти в следующем. Вот почему у нас есть контроль параллелизма.
@kiner_shah вот
@н.м. спасибо за пример, теперь понятно.
Ответы 2
когда вы обновляете вектор, все итераторы становятся недействительными. причина этого в том, что вектор может перераспределить содержимое в памяти. иногда это может работать, но в конечном итоге произойдет ошибка при доступе к перемещенному элементу. другая причина заключается в том, что если вы удаляете элементы, ваш итератор может указывать на границы или пропускать записи. поэтому вам определенно нужно выполнить некоторую блокировку в обоих потоках. какой тип блокировки зависит от остальной части вашего кода
я бы также рекомендовал либо std::swap , либо std::move вместо allow_list = allow_list_updated; в зависимости от того, можно ли отказаться от allow_list_updated после изменения; это намного быстрее. если вы часто обновляете этот список, вы, вероятно, захотите использовать std::swap и где-то хранить два списка в области видимости и просто .clear() и std::swap() при каждом их обновлении. это будет бороться с фрагментацией памяти. пример:
class updater
{
public:
std::vector<std::string> allowed;
std::vector<std::string> allowed_updated;
void update()
{
// @TODO: do your update to this->allowed_updated, use this->allowed_updated.reserve() if you know how many items there will be
std::swap(this->allowed, this->allowed_updated);
this->allowed_updated.clear();
}
};
Спасибо, не знал о функции подкачки, но безопасен ли этот поток? Allow_updated можно отбросить, меня волнует только сам allow_list.
Во внутренней реализации swap(move internal) используется как стандартом::vector, так и boost::vector. Таким образом, operator= на самом деле является std::swap для векторов. (старый вектор теперь мусор), что-то вроде: _M_move_assign(std::move(__x), __bool_constant<__move_storage>());
Во-первых, std::swap() не является атомарным. Во-вторых, он может проскользнуть между вызовами begin() и end() в другом потоке. В-третьих, вы очищаете вектор, который в данный момент повторяет другой поток.
У вас есть состояние гонки, и вам нужно заблокировать. Простое правило, если поток может читать переменную с неатомарной записью из другого, у вас есть гонка для этой переменной. Еще одна проблема, вам нужно заблокировать все вектора. Если у вас много прочтений и редких записей, std::shared_mutex может быть хорошей идеей. Если allow_list периодически обновляется только с краев, список будет лучшим вариантом для allow_list = allow_list_updated, так как чтобы поменять местами список, вам нужно поменять местами голову и хвост. Еще одним потенциальным преимуществом списка является отсутствие ложного обмена. Что бы вы ни делали, ваш контейнер и его защита должны быть одного класса.
При назначении предыдущее содержимое (общего) объекта уничтожается. Таким образом, все итераторы будут признаны недействительными, что приведет к приятному небольшому сбою. Чтобы проверить это, вы можете выполнить итерацию по контейнеру в одном потоке и реализовать «сон», в то время как другой поток манипулирует списком.