Указатель опасности

В многопоточной вычислительной среде указатели опасностей являются одним из подходов к решению проблем, возникающих при динамическом управлении памятью узлов в без блокировок структуре данных . Эти проблемы обычно возникают только в средах, где нет автоматической сборки мусора . ^[1]

Любая структура данных без блокировок, использующая примитив сравнения и замены, должна решать проблему ABA . Например, в стеке без блокировок, представленном как навязчиво связанный список, один поток может пытаться извлечь элемент из начала стека (A → B → C). Он запоминает второе сверху значение «B», а затем выполняет compare_and_swap(target=&head, newvalue=B, expected=A). К сожалению, в середине этой операции другой поток мог выполнить два извлечения, а затем поместить A обратно на вершину, в результате чего образовался стек (A → C). Операция сравнения и замены успешно заменяет `head` на `B`, и в результате стек теперь содержит мусор (указатель на освобожденный элемент "B").

Более того, любой алгоритм без блокировок, содержащий код вида

    Node* currentNode = this->head;  // assume the load from "this->head" is atomic
    Node* nextNode = currentNode->next;  // assume this load is also atomic

страдает еще одной серьезной проблемой — отсутствием автоматической сборки мусора. Между этими двумя строками возможно, что другой поток может извлечь узел, на который указывает this->head и освободить ее, то есть доступ к памяти через currentNode во второй строке читается освобожденная память (которая на самом деле может уже использоваться каким-то другим потоком для совершенно другой цели).

Указатели опасностей могут использоваться для решения обеих этих проблем. В системе указателей опасностей каждый поток хранит список указателей опасностей, указывающий, к каким узлам поток обращается в данный момент. (Во многих системах этот «список», вероятно, может быть ограничен только одним ^[1]^[2] или два элемента.) Узлы в списке указателей опасности не должны изменяться или освобождаться каким-либо другим потоком.

Каждый поток чтения имеет общий указатель с одним записывающим/множественным чтением, называемый «указателем опасности». Когда поток чтения присваивает адрес карты своему указателю опасности, он, по сути, объявляет другим потокам (писателям): «Я читаю эту карту. Вы можете заменить ее, если хотите, но не меняйте ее содержимое и, конечно же, не меняйте ее. держи свой deleteруки прочь от этого».
— Андрей Александреску и Мэджид Майкл, Структуры данных без блокировки с указателями на опасность ^[2]

Когда поток хочет удалить узел, он помещает его в список узлов, «которые будут освобождены позже», но фактически не освобождает память узла до тех пор, пока ни один из других потоков не содержит указатель опасностей. Эту ручную сборку мусора можно выполнить с помощью выделенного потока сборки мусора (если список «подлежащего освобождению позже» является общим для всех потоков); в качестве альтернативы очистка списка «подлежащего освобождению» может выполняться каждым рабочим потоком как часть такой операции, как «pop» (в этом случае каждый рабочий поток может нести ответственность за свой собственный список «подлежащего освобождению»).

В 2002 году Мэгед Майкл из IBM подал заявку на получение патента США на метод указателя опасности. ^[3] но заявка была отклонена в 2010 году.

Альтернативой указателям опасности является подсчет ссылок . ^[1]

См. также

Ссылки

^ Jump up to: ^а ^б ^с Энтони Уильямс. Параллелизм C++ в действии: практическая многопоточность. Manning: Shelter Island, 2012. См., в частности, главу 7.2, «Примеры структур данных без блокировок».
^ Jump up to: ^а ^б Андрей Александреску и Магед Майкл (2004). «Блокировочные структуры данных с указателями на опасность» . Доктор Добб . (статья, ориентированная на C++)
^ Заявка США 20040107227 Мэджид М. Майкл, «Метод эффективной реализации динамических структур данных без блокировок с безопасным восстановлением памяти». Подано 3 декабря 2002 г.

Магед Майкл (2004). «Указатели опасностей: безопасное восстановление памяти для объектов без блокировки» (PDF) . Транзакции IEEE в параллельных и распределенных системах . 15 (8): 491–504. CiteSeerX 10.1.1.130.8984 . дои : 10.1109/TPDS.2004.8 . S2CID 8373852 . Архивировано из оригинала (PDF) 4 ноября 2017 г.

Внешние ссылки

Параллельные строительные блоки — реализация C++ указателя опасности (называемого «SMR») и других структур данных без блокировок. Также имеет интерфейсы Java.
Concurrency Kit. Архивировано 1 июня 2014 г. на Wayback Machine . Реализация Hazard Pointer на языке C и структуры данных без блокировки.
Atomic Ptr Plus — библиотека C/C++, имеющая реализацию указателя опасности.
Сдвиг в параллелизме и модель памяти C++ . В приложениях содержится реализация C++ для Windows.
libcds — библиотека C++ контейнеров без блокировок и реализация указателя опасностей.

[Williams12-1] Jump up to: ^а ^б ^с Энтони Уильямс. Параллелизм C++ в действии: практическая многопоточность. Manning: Shelter Island, 2012. См., в частности, главу 7.2, «Примеры структур данных без блокировок».

[Alexandrescu04-2] Jump up to: ^а ^б Андрей Александреску и Магед Майкл (2004). «Блокировочные структуры данных с указателями на опасность» . Доктор Добб . (статья, ориентированная на C++)

[USPTO-3] Заявка США 20040107227 Мэджид М. Майкл, «Метод эффективной реализации динамических структур данных без блокировок с безопасным восстановлением памяти». Подано 3 декабря 2002 г.

[1]

[2]

[3]