DHP – это вариант алгоритма Hazard Pointer с неограниченным числом hazard pointer'ов для потока. Текущая реализация (libcds 2.1.0) предполагает, что массив retired data (данных, готовых для удаления) один для всех потоков, то есть все потоки добавляют в него данные и по достижении некоторого предела вызывается основная процедура алгоритма HP – scan(), которая проходит по массиву retired ptr и физически удаляет те данные, которые не объявлены как hazard pointer. Очевидно, что scan() не должна приостанавливать работу всех остальных потоков; с другой стороны, пока scan() работает, массив retired ptr недоступен для изменений, то есть потоки не должны в него добавлять данные.

Эта коллизия разрешается в libcds 2.1.0 следующим образом: имеется циклический список массивов retired ptr, один из которых является текущим. По заполнении текущего массива вызывается scan(), которая приватизирует текущий массив retired ptr и объявляет текущим следующий массив из списка. Таким образом, пока scan() работает с одним массивом retired ptr, остальные потоки добавляют retired data в другой массив, текущий. Размер циклического списка задается в конструкторе объекта DHP.

Такой алгоритм чреват ABA-проблемой, когда у нас число потоков много больше размера циклического списка.

Предлагается модифицировать DHP, объявив массив retired ptr приватным (thread local data) для каждого потока, работающего с DHP-based структурами данных. При этом надо учитывать:

• размер массива retired data должен изменяться динамически (он зависит от числа hazard ptr на момент вызова scan();

критерий увеличения размера: scan() не смогла удалить ни одного указателя из retired data).

• нагрузка на структуру данных может быть неравномерна: одни потоки — deleter thread – только удаляют данные из DHP-based структуры данных,

то есть активно работают с retired ptr array, другие потоки — updater thread – в основном добавляют/ ищут в структуре. Поэтому retired ptr array каждого потока должен иметь некий timestamp последнего применения scan() и последующий вызов scan() должен происходить не только по заполнении retired ptr array, но и по превышению этого timestamp на некоторую дельту.

Попутно следует упростить реализацию DHP, сократив иерархию структур.

Требование: API DHP-алгоритма измениться не должно.