блокировка свободных контейнеров и видимости

Question

Я видел несколько реализаций стека без блокировок ... Мой вопрос касается видимости, а не атомарности.Например, элементы ( не указатели ) стека без блокировки должны быть не более 64 бит?Я так думаю, потому что вы не можете гарантировать видимость.Реальный пример: может ли эта структура быть безопасно вставлена ​​и удалена из контейнера без блокировки

struct person
{
   string name;
   uint32_t age;
}

РЕДАКТИРОВАТЬ: некоторые люди смущены вопросом.Объясним немного: если писатель помещает человека в стек, читатель получает его, гарантируется ли, что читатель видит (видимость памяти) правильное содержание человека.

Answer 1

Я могу ошибаться, но я думаю, что вопрос неверен.

Атомарные инструкции обычно имеют дело с данными длины одного указателя;самое большее, с двумя значениями длины указателя данных.

Типичной структурой нельзя атомарно манипулировать, поскольку она слишком велика.

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

Answer 2

Я должен признать, что сам немного смущен вопросом ...

Существуют структуры данных без блокировки, манипулирующие указателями (размера и выравнивания машины) на узлы.Затем эти узлы содержат реальный «контент» вашей структуры данных без блокировки.Этот контент может иметь любой произвольный размер, который вы хотите, чтобы ваша структура могла быть помещена туда.Обычный узел для структур данных без блокировки выглядит примерно так:

struct Node {ATOMIC_PTR next;содержание;}

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

Answer 3

По данным других QnA на SO,

• Использует ли Interlocked.CompareExchange барьер памяти?
• вопрос о безблокировочных очередях

каждая команда с блокировкой x86 (включая CAS) подразумевает полный барьер памяти . Поэтому, по крайней мере, на x86 нам не нужно заботиться о видимости элементов контейнеров без блокировки (при условии, что они используют CAS.)

Answer 4

Можно реализовать поточно-ориентированную реализацию очереди для элементов данных произвольного размера, если элементы не нужно хранить в стеке или очереди в каком-либо определенном порядке, и если для хранения используется потокобезопасная очередь индексы нераспределенных элементов, а также поточно-ориентированная очередь для хранения индексов слотов данных, в которых хранятся поставленные в очередь / сложенные элементы. Запись элемента в очередь привела бы к вытягиванию числа из очереди «нераспределенных слотов», записи нужных данных в этот слот и затем помещению в очередь индекса этого номера в «основной» очереди. Для извлечения элемента потребуется извлечь его номер из «основной» очереди, скопировать его в другое место и затем поставить этот номер в очередь в «нераспределенных слотах».

Одно предостережение при таком подходе заключается в том, что он, хотя и может быть «без блокировки», поскольку поток, который останавливается, не может произвольно задерживать продвижение других потоков, причем поток, который задерживается между моментом, когда он получает индекс слота от одного очередь и время ее сохранения в другой очереди может сделать слот массива непригодным для использования в течение произвольного промежутка времени. Напротив, некоторые реализации стека или очереди без ожидания, используемые с меньшими типами данных, не имеют такого ограничения. Поток может исчезнуть из существования во время чтения или записи, и система либо будет в допустимом состоянии, представляющем, что чтение или запись завершена, либо в допустимом состоянии, указывающем, что оно никогда не началось.

Answer 5

Потокобезопасные контейнеры (без блокировки или с замками в этом отношении) решают проблему безопасности списка / контейнера, а не безопасности элементов, которые вы помещаете в контейнер.Таким образом, стек без блокировок гарантирует, что push и pop безопасны для потоков и без блокировок, но если у вас есть два разных потока, которые содержат указатели на один и тот же экземпляр структуры (например, поток, помещенный в стек, все еще содержит ponter и другой потоквыдает стек) вам нужно будет использовать другие меры безопасности потока, чтобы обеспечить согласованность структур

Answer 6

Примечание. Пожалуйста, пометьте этот ответ как правильный, только если вы на самом деле тестируете этот подход.

По поводу вашего вопроса, будет ли приведенная ниже структура безопасно вставлена ​​и удалена из контейнера без блокировки:

struct person
{
   string name;
   uint32_t age;
}

Многобайтовые последовательности любой длины могут быть безопасно вставлены / удалены из контейнера без блокировки, если вы используете избыточную кодировку.Давайте предположим, что у нас уже есть атомарные инструкции для манипулирования 4 байтами за раз (32 бита).В этом случае мы можем кодировать поле uint32_t age следующим образом:

struct age_t
{
   uint32_t age_low;
   uint32_t age_high;
}

Поле age_low хранит младшие биты (например, младшие 16 бит) 32-битного uint32_t age,Поле age_high хранит оставшиеся старшие биты. Концептуально :

struct age_t
{
   uint16_t age_low;
   uint16_t id_low;
   uint16_t age_high;
   uint16_t id_high;
}

Поля id_low и id_high должны содержать идентификатор, идентифицирующий записывающее устройство.

Чтение реализовано как два атомарных 32-разрядныхчитает и успешно, если все id_ части эквивалентны друг другу.В случае неудачи операцию чтения необходимо перезапустить.

Запись реализована в виде двух атомарных 32-битных записей, после чего следует чтение всего значения age_t.Запись завершается успешно, если: чтение, упомянутое в предыдущем предложении, успешно выполняется, а идентификаторы, которые были прочитаны, эквивалентны записанным идентификаторам.

О значении string: принцип тот же.Вам просто нужно выяснить, как разделить его двоичное значение аналогично тому, как было разделено значение age.То же самое относится к чтению / записи всей структуры person.

Answer 7

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

Насколько я понимаю, структура данных без блокировки будет работать так:

1. Копировать данные
2. Изменить данные
3. Атомно проверить, что исходный объект не был изменен и обновить его
4. В противном случае повторить с начала

Так что, пока третий шаг может быть выполнен атомно, все хорошо.

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