Differences

This shows you the differences between two versions of the page.

--- projects:libcds:dhp_refactor [2015/12/10 13:38] – [Рефакторинг SMR-алгоритма cds::gc::DHP] khizmax
+++ projects:libcds:dhp_refactor [2015/12/17 12:59] (current) – khizmax
@@ Line 15: / Line 15: @@
 Такой алгоритм чреват ABA-проблемой, когда у нас число потоков много больше размера циклического списка.
-Предлагается модифицировать DHP, объявив массив retired ptr приватным (thread local data) для каждого потока, работающего с DHP-based структурами данных.
+Варианты решения:
+. Объявить массив retired ptr приватным (thread local data) для каждого потока, работающего с DHP-based структурами данных.
 При этом надо учитывать:
-  * размер массива retired data должен изменяться динамически (он зависит от числа hazard ptr на момент вызова ''scan()'';
+  * размер массива retired data должен изменяться динамически (он зависит от числа hazard ptr на момент вызова ''scan()''; критерий увеличения размера: ''scan()'' не смогла удалить ни одного указателя из retired data).
-критерий увеличения размера: ''scan()'' не смогла удалить ни одного указателя из retired data).
+  * нагрузка на структуру данных может быть неравномерна: одни потоки — deleter thread – только удаляют данные из DHP-based структуры данных, то есть активно работают с retired ptr array, другие потоки — updater thread – в основном добавляют/ ищут в структуре. Поэтому retired ptr array каждого потока должен иметь некий ''timestamp'' последнего применения ''scan()'' и последующий вызов ''scan()'' должен происходить не только по заполнении retired ptr array, но и по превышению этого ''timestamp'' на некоторую дельту.
-  * нагрузка на структуру данных может быть неравномерна: одни потоки — deleter thread – только удаляют данные из DHP-based структуры данных,
+Это решение плохо тем, что память используется нерационально: потоки, мало удаляющие из структуры данных, будут долго заполнять свой retired array, редко вызывать ''scan()''.
-то есть активно работают с retired ptr array, другие потоки — updater thread – в основном добавляют/ ищут в структуре.
-Поэтому retired ptr array каждого потока должен иметь некий ''timestamp'' последнего применения ''scan()'' и последующий вызов ''scan()'' должен
+. Retired array - один для всех потоков. Когда один из потоков при вызове ''retire_ptr()'' обнаруживает, что retired array полон, он приватизирует retired array и вызывает ''scan()''.
-происходить не только по заполнении retired ptr array, но и по превышению этого ''timestamp'' на некоторую дельту.
+При этом поток должен создать новый retired array, чтобы остальные потоки могли продолжить свою работу.
+Размер retired array в принципе не ограничен. Если ''scan()'' обнаруживает, что может удалить (delete), например, не более половины элементов из текущего retired array, она должна увеличить размер массива, то есть увеличить порог срабатывания следующего вызова ''scan()''. Получается, что, ради эффективности, "массив" retired array должен быть не массивом, а списком блоков. Блоки берутся из некоторого пула блоков, конечно, в lock-free манере. Следовательно, нужно решить ABA-проблему для этого пула.
 Попутно следует упростить реализацию DHP, сократив иерархию структур.
-**Требование**: API DHP-алгоритма измениться не должно.
+**Требование**: API (public interface and nested classes) DHP-алгоритма измениться не должно.