Ответ 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 будет доступен только когда он не был удален.