Open Source & Linux Lab

It's better when it's simple

User Tools

Site Tools


projects:libcds:dhp_refactor

Differences

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

Link to this comparison view

Both sides previous revision Previous revision
Next revision
Previous revision
projects:libcds:dhp_refactor [2015/12/10 13:41]
khizmax
projects:libcds:dhp_refactor [2015/12/17 12:59]
khizmax
Line 15: Line 15:
 Такой алгоритм чреват ABA-проблемой,​ когда у нас число потоков много больше размера циклического списка. Такой алгоритм чреват ABA-проблемой,​ когда у нас число потоков много больше размера циклического списка.
  
-Предлагается модифицировать DHP, объявив массив retired ptr приватным (thread local data) для каждого потока,​ работающего с DHP-based структурами данных. ​+Варианты решения
 + 
 +1. Объявить массив retired ptr приватным (thread local data) для каждого потока,​ работающего с DHP-based структурами данных. ​
 При этом надо учитывать:​ При этом надо учитывать:​
   * размер массива retired data должен изменяться динамически (он зависит от числа hazard ptr на момент вызова ''​scan()'';​ критерий увеличения размера:​ ''​scan()''​ не смогла удалить ни одного указателя из retired data).   * размер массива 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''​ на некоторую дельту.   * нагрузка на структуру данных может быть неравномерна:​ одни потоки — deleter thread – только удаляют данные из DHP-based структуры данных,​ то есть активно работают с retired ptr array, другие потоки — updater thread – в основном добавляют/​ ищут в структуре. Поэтому retired ptr array каждого потока должен иметь некий ''​timestamp''​ последнего применения ''​scan()''​ и последующий вызов ''​scan()''​ должен происходить не только по заполнении retired ptr array, но и по превышению этого ''​timestamp''​ на некоторую дельту.
 +Это решение плохо тем, что память используется нерационально:​ потоки,​ мало удаляющие из структуры данных,​ будут долго заполнять свой retired array, редко вызывать ''​scan()''​.
 +
 +2. Retired array - один для всех потоков. Когда один из потоков при вызове ''​retire_ptr()''​ обнаруживает,​ что retired array полон, он приватизирует retired array и вызывает ''​scan()''​. ​
 +При этом поток должен создать новый retired array, чтобы остальные потоки могли продолжить свою работу.
 +Размер retired array в принципе не ограничен. Если ''​scan()''​ обнаруживает,​ что может удалить (delete), например,​ не более половины элементов из текущего retired array, она должна увеличить размер массива,​ то есть увеличить порог срабатывания следующего вызова ''​scan()''​. Получается,​ что, ради эффективности,​ "​массив"​ retired array должен быть не массивом,​ а списком блоков. Блоки берутся из некоторого пула блоков,​ конечно,​ в lock-free манере. Следовательно,​ нужно решить ABA-проблему для этого пула. ​
  
 Попутно следует упростить реализацию DHP, сократив иерархию структур. ​ Попутно следует упростить реализацию DHP, сократив иерархию структур. ​
  
 **Требование**:​ API (public interface and nested classes) DHP-алгоритма измениться не должно. **Требование**:​ API (public interface and nested classes) DHP-алгоритма измениться не должно.
projects/libcds/dhp_refactor.txt · Last modified: 2015/12/17 12:59 by khizmax