Стирает и вставляет в односвязную цепочку потокобезопасную?

Использование std :: forward_list есть ли какие-либо данные гонки при удалении и inserting? Например, у меня есть один поток, который ничего не делает, кроме добавления новых элементов в конце списка, и у меня есть другой поток, который идет (тот же) список и может стереть из него элементы.Стирает и вставляет в односвязную цепочку потокобезопасную?

Из того, что я знаю о связанных списках, каждый элемент содержит указатель на следующий элемент, поэтому, если я удалю последний элемент, в то же время, когда я вставляю новый элемент, это приведет к гонке данных или сделает эти контейнеры работают по-разному (или они справляются с этой возможностью)?

Если это гонка данных, есть ли (простой и быстрый) способ избежать этого? (Примечание: резьба, которая вставлена, является наиболее критической по скорости для этих двух.)

источник

2014-01-02 latreides

Если вам нужно спросить, хорошее эмпирическое правило: Нет, это не безопасно для потоков. Собственно, поцарапать первую часть, это всегда хорошее эмпирическое правило. – delnan

Предоставляет ли стандарт гарантии безопасности резьбы? Если нет, то не стоит полагаться на него, даже если он работает на вашем компиляторе сегодня. –

@MarkRansom: Да, стандарт делает гарантии безопасности потоков для контейнеров. Тем не менее, они довольно слабы, и их недостаточно, чтобы охватить вопрос пользователя в вопросе (см. Также мой ответ). –

Существуют гарантии безопасности потоков для стандартных контейнеров библиотеки C++, но они, как правило, не относятся к таким людям, которые будут рассматривать гарантии безопасности потоков (то есть, однако, ошибку людей, ожидающих неправильной вещи). Гарантии безопасности потоков стандартной библиотеки контейнеров примерно (соответствующий раздел 17.6.5.9 [res.on.data.races]):

Вы можете иметь столько читателей контейнера, как вы хотите. То, что точно соответствует читателю, немного тонко, но примерно соответствует пользователям функций-членов const, а также использует несколько членов, не относящихся к const, только для чтения данных (безопасность потоков данных чтения не относится ни к одному из контейнеров, т.е. 23.2.2 [container.requirements.dataraces] указывает, что элементы могут быть изменены без контейнеров, вводящих данные).
Если есть один писатель контейнера, других читателей или записей о контейнере в другом потоке не должно быть.

То есть, читает один конец контейнера и записи другого конца не поточно!На самом деле, даже если фактические изменения контейнера не влияют на читателя сразу, вам нужно всегда необходимо синхронизировать некоторую форму при передаче части данных из одного потока в другой поток. То есть, даже если вы можете гарантировать, что потребитель не будет erase() узлом производителя в настоящее время insert(), будет гонка данных.

источник

2014-01-02 16:51:56

В документации говорится, что она безопасна для доступа к любому из элементов при вставке и стирании (при условии, что это не элемент, который вы стираете), поскольку он никоим образом не изменяет их (фактически, все итераторы все остальные элементы по-прежнему действительны). Единственный мой конкретный прецедент, о котором я не могу найти твердую информацию. – latreides

@latreides: если ваша реализация дает гарантии, кроме тех, что я изложил выше, это можно сделать свободно. Однако одновременный доступ и изменение (как при изменении количества или местоположения объектов) в любой из стандартных контейнеров библиотеки могут вводить расы данных. 23.2.2 [container.requirements.dataraces] может быть тем, на что вы ссылаетесь: вы можете изменить _elements_, хранящиеся в контейнере без контейнера, вводящего расы данных (обратите внимание, что вам все равно необходимо убедиться, что доступ к элементу не годен). –

std контейнеры не предназначены для защиты потолка.

Вы должны тщательно защитить их для операций модификации.

источник

2014-01-02 16:43:57

Не совсем корректно, стандартные контейнеры библиотеки - это поточно- безопасный для одновременного доступа к чтению. Только при изменении контейнера, который вы должны доказать внешняя синхронизация. – Praetorian

, но если вы защитите операцию изменения, то доступ на чтение должен быть защищен. –

@StephaneRolland с доступом для чтения std :: forward_list безопасен, даже если контейнер изменен, пока вы используете итераторы, а не индексы. Для этого контейнера конкретно все итераторы, за исключением тех, которые специально изменены/стерты/и т. Д., Остаются в силе даже после модификации контейнера. – latreides

Нет, ни forward_list, ни любые другие контейнеры STL не являются потокобезопасными для записи. Вы должны обеспечить синхронизацию, чтобы никакие другие потоки не читали или не записывали в контейнер во время записи. Только одновременные чтения являются безопасными.

Самый простой способ сделать это - использовать мьютексы для блокировки доступа к контейнеру во время вставки. Для этого в переносном режиме требуется C++ 11 (std::mutex) или специфичные для платформы функции (mutexes in Windows, возможно, pthreads в Linux/Unix).

источник

2014-01-02 16:44:28 TypeIA

Мьютексы в Windows (которые не используют futexes) слишком медленны для этого варианта использования. В документации говорится, что std :: list и std :: forward_list являются потокобезопасными почти для каждой операции (например, вы можете удалить из списка и получить доступ к любому другому элементу списка без гонки данных), но я не могу найти информацию об этом конкретном случае. – latreides

@ latreides Вы должны признать, что это не безопасно. – TypeIA

@ latreides Не смотря на стандарт, если бы я должен был догадаться, я бы сказал, что из-за правил аннулирования итератора для 'forward_list' * почти * каждый случай будет потокобезопасным, за исключением того, о котором вы беспокоитесь. Поэтому вам придется прибегнуть к синхронизации. Если вы не заботитесь о переносимости, вы можете использовать «CRITICAL_SECTION» (если это не сценарий с несколькими процессами). Это довольно легкий вес, если нет фактического утверждения. – Praetorian

Если вы не используете версию STL, которая явно заявляет, что она защищена потоками, то нет, контейнеры не являются потокобезопасными.

Редко сделать потоки контейнеров общего назначения по умолчанию безопасными, так как это накладывает удар производительности на пользователей, которым не нужен поточный безопасный доступ к контейнеру, и это, безусловно, нормальный шаблон использования.

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

источник

2014-01-02 16:49:48 Sean

Существует ли контейнер std :: forward_list-like (который является частью стандарта), специально предназначенный для многопоточного доступа? – latreides

@latreides - no :-( – Sean

Стирает и вставляет в односвязную цепочку потокобезопасную?

ответ

Смежные вопросы