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

Hazard pointer

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

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

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

    Узел* currentNode = это->голова;  // предполагаем, что загрузка из this-> head атомарна    Узел* nextNode = currentNode->следующий;  // предполагаем, что эта нагрузка также является атомарной

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

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

Каждый поток чтения владеет общим указателем с одним / несколькими читателями, который называется «указатель опасности». Когда поток чтения назначает адрес карты своему указателю опасности, он в основном объявляет другим потокам (авторам): «Я читаю эту карту. Вы можете заменить ее, если хотите, но не меняйте ее содержимое и, конечно, Держите ваши Удалитьруки прочь. "

— Андрей Александреску и Магед Майкл, Lock-Free Data Structures with Hazard Pointers[2]

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

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

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

Смотрите также

Рекомендации

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

внешняя ссылка