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 revisionPrevious revision
Next revision
Previous revision
projects:libcds:dhp_refactor [2015/12/10 13:41] khizmaxprojects:libcds:dhp_refactor [2015/12/17 12:59] (current) 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