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

Фон

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

проблема

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

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

1 ответ

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

По любой операции (добавить, найти или удалить):

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

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

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

Источник
Другие вопросы по тегам