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

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

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

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

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

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

Дата добавления: 2015-11-14