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

Ответ 1

Возможно, я ошибаюсь, но думаю, что этот вопрос неверен.

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

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

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

Ответ 2

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

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

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

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

Ответ 3

Согласно другому QnA на SO,

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

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

Ответ 4

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

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

• Скопировать данные
• Изменить данные
• Атомно проверить, что исходный объект не был изменен и обновил его
• В противном случае повторите с самого начала

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

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

Ответ 5

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

О вашем вопросе о том, безопасно ли внедрена ниже структура и удалить ее из контейнера без блокировки:

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.

Ответ 6

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

Ответ 7

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

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