Метод опасных указателей

В отличие от метода неблокирующего подсчёта ссылок, данный метод основан на проверке списка опасных указателей. На вход алгоритма поступают указатели на второй элемент списка выбывших узлов и на вершину списка опасных указателей. Далее создаются копии полученных указателей, чтобы обеспечивать возможности прохода по спискам без потери полученных указателей. Далее происходит обход списка выбывших узлов, из каждого узла которого берётся указатель на данные и сравнивается со всеми опасными указателями списка опасных указателей. Если указатели совпадают, то совершается переход к следующему узлу списка выбывших узлов. В том случае, если ни один из опасных указателей не совпал с указателем на данные из списка выбывших узлов, то данные не используются ни одним читающим потоком и память из-под них может быть безопасно освобождена. Алгоритм завершается после обхода всех узлов, предварительно атомарно сбросив флаг запуска освобождения памяти. Данный алгоритм, также как и алгоритм освобождения памяти для метода неблокирующего подсчёта ссылок, является wait-free алгоритмом, так как не содержит операций вида CAS и будет выполнен за конечное число шагов, не зависимо ни от чего. Блок-схема алгоритма освобождения памяти для метода опасных указателей представлена на рис. 2.8.

Рис. 2.8. Блок-схема алгоритма освобождения памяти

для метода опасных указателей

2.4.4. Алгоритм добавления и удаления опасных указателей

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

В отличие от работы со списком опасных указателей с заранее известным числом читающих потоков, где можно создать необходимое количество элементов, а затем выдать каждому потоку указатель на свой элемент с опасным указателем, работа со списком опасных указателей с заранее неизвестным числом читающих потоков не позволяет провести аналогичные действия. Поэтому при создании нового читающего потока необходимо создать свой элемент списка опасных указателей, включающий в себя опасный указатель созданного потока, и добавить его в список опасных указателей. Однако необходимо обеспечить отсутствие конфликтов, так как сразу несколько потоков могут пытаться добавить элемент в список. Для этого будет использоваться операция CAS, которая будет добавлять элемент в начало списка только в том случае, если вершина списка не изменилась. После выполнения данного алгоритма поток получает указатель на свой элемент с опасным указателем в списке опасных указателей. Блок-схема алгоритма добавления опасных указателей представлена на рис. 2.9.

Рис. 2.9. Блок-схема алгоритма добавления опасных указателей

При завершении работы поток должен удалить свой элемент из списка опасных указателей. Для этого необходимо найти предшествующий элемент в списке опасных указателей, изменить его указатель на следующий элемент, а затем удалить свой. Однако при завершении нескольких потоков одновременно может произойти следующая ситуация: один из потоков останавливается на элементе, который в этот момент времени удаляется другим потоком. В результате мы получаем ошибку при обращении к несуществующему элементу. В случае небольшого количества читающих потоков можно не освобождать память при завершении, а обнулять указатель и освобождать память из-под всего списка непосредственно перед завершением работы программы, так как решение данной задачи средствами неблокирующего программирования на данный момент не представляется возможным. Это объясняется тем, что во время проверки следующего элемента, может быть удалён текущий, как и любой другой элемент списка. Для решения данной проблемы можно использовать спин-блокировку. В данной ситуации использование простейшей блокирующей синхронизации не приведёт ни к каким отрицательным последствием, так как единственным её предназначением будет обеспечение выполнения алгоритма удаления опасных указателей только одним читающим потоком. Для обеспечения безопасности флаг будет устанавливаться с помощью операции CAS только в том случае, если ни один поток не удаляет опасные указатели в текущей момент. После завершения флаг сбрасывается атомарно. В качестве входных данных необходимо передавать указатель на свой элемент с опасным указателем в списке опасных указателей. Блок-схема алгоритма удаления опасных указателей представлена на рис. 2.10.

Рис. 2.10. Блок-схема алгоритма удаления опасных указателей