Перемещение значений между списками без блокировки - PullRequest
Новая
       67

Перемещение значений между списками без блокировки

0 голосов
/ 16 октября 2018

Фон

Я пытаюсь спроектировать и реализовать хэш-карту без блокировки, используя метод цепочки в C ++.Каждая ячейка хеш-таблицы должна содержать список без блокировки.Чтобы разрешить изменение размера, моя структура данных должна содержать два массива - маленький, который всегда доступен, и больший для изменения размера, когда меньшего больше не достаточно.Когда создается больший, я бы хотел, чтобы данные, хранящиеся в маленьком, передавались по одному большему, всякий раз, когда какой-либо поток что-то делает со структурой данных (добавляет элемент, ищет или удаляет один).Когда все данные передаются, больший массив перемещается вместо меньшего, а последний удаляется.Цикл повторяется всякий раз, когда необходимо увеличить массив.

Проблема

Как упоминалось ранее, каждый массив должен содержать списки в ячейках.Я пытаюсь найти способ передачи значения или узла из одного списка без блокировок в другой таким образом, чтобы значение оставалось видимым в любом (или обоих) списках.Это необходимо для того, чтобы поиск в хэш-карте не давал пользователю ложных негативов.Итак, мои вопросы:

  1. Возможна ли такая реализация списка без блокировки?
  2. Если да, то какова общая концепция такого списка и операции "перемещение узла / значения"?Я был бы благодарен за любой псевдокод, код C ++ или научную статью, описывающую его.

1 Ответ

0 голосов
/ 18 октября 2018

Чтобы иметь возможность изменять размер массива, сохраняя гарантии прогресса без блокировок, вам необходимо использовать дескрипторы операций.Как только изменение размера начнется, добавьте дескриптор, который содержит ссылки на старый и новый массивы.

В любой операции (добавление, поиск или удаление):

  • Операция добавления, поиск в старом массиве, если элемент уже существует, затем перед тем, как переместить элемент в новый массиввозвращение.Укажите с помощью дескриптора или специального нулевого значения, что элемент уже был перемещен, чтобы другие потоки не пытались переместить его снова
  • Поиск, поиск в старом массиве и перемещение элемента, как указано выше.
  • Удалить - Удалить тоже придется сначала искать старый массив.

Теперь проблема в том, что у вас будет поток, который должен проверить, что перемещение завершено, так что вы можетеудалите дескриптор и освободите старый массив.Чтобы сохранить блокировку, вам нужно, чтобы все активные потоки пытались выполнить эту проверку, поэтому это становится очень дорогим.

Вы можете посмотреть:

...