projects:libcds:dhp_refactor
Differences
This shows you the differences between two versions of the page.
Next revision | Previous revision | ||
projects:libcds:dhp_refactor [2015/12/10 13:36] – created khizmax | projects:libcds:dhp_refactor [2015/12/17 12:59] (current) – khizmax | ||
---|---|---|---|
Line 1: | Line 1: | ||
+ | ====== Рефакторинг SMR-алгоритма cds:: | ||
+ | |||
DHP – это вариант алгоритма Hazard Pointer с неограниченным числом hazard pointer' | DHP – это вариант алгоритма Hazard Pointer с неограниченным числом hazard pointer' | ||
Текущая реализация (libcds 2.1.0) предполагает, | Текущая реализация (libcds 2.1.0) предполагает, | ||
Line 13: | Line 15: | ||
Такой алгоритм чреват ABA-проблемой, | Такой алгоритм чреват ABA-проблемой, | ||
- | Предлагается модифицировать DHP, объявив массив retired ptr приватным (thread local data) для каждого потока, | + | Варианты решения: |
+ | |||
+ | 1. Объявить массив retired ptr приватным (thread local data) для каждого потока, | ||
При этом надо учитывать: | При этом надо учитывать: | ||
- | * размер массива retired data должен изменяться динамически (он зависит от числа hazard ptr на момент вызова '' | + | * размер массива retired data должен изменяться динамически (он зависит от числа hazard ptr на момент вызова '' |
- | критерий увеличения размера: | + | * нагрузка на структуру данных может быть неравномерна: |
- | * нагрузка на структуру данных может быть неравномерна: | + | Это решение плохо тем, что память используется нерационально: |
- | то есть активно работают с retired ptr array, другие потоки — updater thread – в основном добавляют/ | + | |
- | Поэтому retired ptr array каждого потока должен иметь некий '' | + | 2. Retired array - один для всех потоков. Когда один из потоков при вызове '' |
- | происходить не только по заполнении retired ptr array, но и по превышению этого '' | + | При этом поток должен создать новый retired array, чтобы остальные потоки могли продолжить свою работу. |
+ | Размер retired array в принципе не ограничен. Если '' | ||
Попутно следует упростить реализацию DHP, сократив иерархию структур. | Попутно следует упростить реализацию DHP, сократив иерархию структур. | ||
- | **Требование**: | + | **Требование**: |
projects/libcds/dhp_refactor.1449743786.txt.gz · Last modified: 2015/12/10 13:36 by khizmax