В многопоточной вычислительной среде указатели опасностей являются одним из подходов к решению проблем, возникающих при динамическом управлении памятью узлов в структуре данных без блокировок . Эти проблемы обычно возникают только в средах, где нет автоматической сборки мусора . [1]
Любая структура данных без блокировок, использующая примитив сравнения и замены, должна решать проблему ABA . Например, в стеке без блокировок, представленном как навязчиво связанный список, один поток может пытаться извлечь элемент из начала стека (A → B → C). Он запоминает второе сверху значение «B» и затем выполняет . К сожалению, в середине этой операции другой поток мог выполнить два извлечения, а затем поместить A обратно на вершину, в результате чего образовался стек (A → C). Операция сравнения и замены успешно заменяет `head` на `B`, и в результате стек теперь содержит мусор (указатель на освобожденный элемент "B").compare_and_swap(target=&head, newvalue=B, expected=A)
Более того, любой алгоритм без блокировок, содержащий код вида
Узел * currentNode = this -> head ; // предположим, что загрузка из "this->head" является атомарной Node * nextNode = currentNode -> next ; // предположим, что эта загрузка также атомарна страдает еще одной серьезной проблемой — отсутствием автоматической сборки мусора. Между этими двумя строками возможно, что другой поток может извлечь узел, на который указывает, this->headи освободить его, а это означает, что доступ к памяти currentNodeво второй строке считывает освобожденную память (которая на самом деле может уже использоваться каким-либо другим потоком для совершенно другая цель).
Указатели опасностей могут использоваться для решения обеих этих проблем. В системе указателей опасностей каждый поток хранит список указателей опасностей, указывающий, к каким узлам поток обращается в данный момент. (Во многих системах этот «список», вероятно, может быть ограничен только одним [1] [2] или двумя элементами.) Узлы в списке указателей опасности не должны изменяться или освобождаться каким-либо другим потоком.
Каждый поток чтения имеет общий указатель с одним записывающим/множественным чтением, называемый «указателем опасности». Когда поток чтения присваивает адрес карты своему указателю опасности, он, по сути, объявляет другим потокам (писателям): «Я читаю эту карту. Вы можете заменить ее, если хотите, но не меняйте ее содержимое и, конечно же, не меняйте ее. держи свои
deleteруки подальше от этого».- Андрей Александреску и Мэджид Майкл, Структуры данных без блокировки с указателями на опасность [2]
Когда поток хочет удалить узел, он помещает его в список узлов, «которые будут освобождены позже», но фактически не освобождает память узла до тех пор, пока ни один из других потоков не содержит указатель опасностей. Эту ручную сборку мусора можно выполнить выделенным потоком сборки мусора (если список «подлежащего освобождению позже» является общим для всех потоков); в качестве альтернативы очистка списка «подлежащего освобождению» может выполняться каждым рабочим потоком как часть такой операции, как «pop» (в этом случае каждый рабочий поток может нести ответственность за свой собственный список «подлежащего освобождению»).
В 2002 году Мэджид Майкл из IBM подал заявку на получение патента США на метод указателя опасности [3] , но в 2010 году от этой заявки отказались.
Альтернативой указателям опасности является подсчет ссылок . [1]