Блокировка памяти с помощью указателей опасности

Указатели опасности - это метод безопасного восстановления памяти в коде без блокировки без сбора мусора.

Идея заключается в том, что перед доступом к объекту, который может быть удален одновременно, поток устанавливает свой указатель на опасность для указания на этот объект. Поток, который хочет удалить объект, сначала проверяет, установлены ли какие-либо указатели опасности для указания на этот объект. Если это так, удаление будет отложено, так что поток доступа не завершит чтение удаленных данных.

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

Таким образом, достаточно просто установить указатель опасности недостаточно, так как нить удаления уже проверила наш указатель опасности и решила, что наш поток не хочет получать доступ к объекту. Как я могу убедиться, установив указатель опасности, что объект, который я пытаюсь получить, не будет удален из-под моих рук?

Ответ 1

Авторитетный ответ

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

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

Что это означает для удаления нити

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

В этот момент node возможно удаляется в терминах Майкла. Для одновременных потоков нет доступа к нему (если они уже не указали на него указатель опасности).

Таким образом, как только a node возможно удален, безопасно удалять поток для перебора списка указателей опасности. Даже если удаление потока будет выгружено, параллельный поток больше не сможет получить доступ к node. После проверки того, что указатели опасности не установлены на node, удаляемая нить может безопасно перейти ко второй фазе удаления: фактическое освобождение.

Таким образом, порядок операций для удаления потока -

D-1. Remove the node from the data structure.
D-2. Iterate the list of hazard pointers.
D-3. If no hazards were found, delete the node.

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

Что это означает для потока (-ов) доступа

Установка указателя опасности недостаточно для обеспечения безопасного доступа к нему. В конце концов, node может быть удалено к моменту установки указателя опасности.

Единственный способ обеспечить безопасный доступ - это то, что мы можем гарантировать, что наш указатель опасности будет указывать на этот node непрерывно, с момента, когда node гарантированно будет доступен из корней объектов.

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

Таким образом, порядок операций для потока доступа

A-1. Obtain a pointer to the node by traversing the data structure.
A-2. Set the hazard pointer to point to the node.
A-3. Check that the node is still part of the data structure.
     That is, it has not been possibly removed in the meantime.
A-4. If the node is still valid, access it.

Потенциальные расы, влияющие на удаление нити

После удаления node (D-1) удаляемая нить может быть выгружена. Таким образом, одновременные потоки по-прежнему могут оптимистично установить на них свой указатель опасности (даже если им не разрешен доступ к нему) (A-2).

Следовательно, поток удаления может обнаружить ложную опасность, не позволяя ему сразу же удалить node, хотя ни один из других потоков не будет обращаться к node. Это просто задержит удаление node таким же образом, что и законная опасность.

Важным моментом является то, что node все равно будет удален.

Потенциальные расы, влияющие на поток доступа

Доступ к потоку может быть исключен путем удаления потока, прежде чем проверять, что node не был удален (A-3). В этом случае больше не разрешается обращаться к объекту.

Обратите внимание, что в случае, если преемственность происходит после A-2, было бы безопасно получить доступ к потоку доступа к node (поскольку на нем был указатель опасности, указывающий на node), но поскольку он невозможно, чтобы поток доступа различал этот случай, он должен терпеть неудачу ложно.

Важным моментом является то, что node будет доступен только когда он не был удален.

Ответ 2

Нить, которая хочет удалить объект, сначала проверит, установлены ли какие-либо указатели опасности для указания на этот объект.

Вот проблема. "delete" фактически является двухфазным:

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

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

другой поток устанавливает указатель опасности на я объекту, который в настоящий момент пытается удалить поток удаления

потому что не должно быть никакого способа, чтобы другой поток мог получить удаляемый объект.