(Подробнее) Эффективная блокировка при вращении узлов в двоичном дереве с резьбой

Question

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

Это моя текущая схема, оранжевые и красные узлы либо перемещаются, либо изменяются при вращении и должны быть заблокированы, а зеленые узлы примыкают к любому узлу, на который влияет вращение, но сами по себе они не затрагиваются.

вращение двоичного дерева

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

Я думаю, что я ищу указатели (без каламбура) о том, как сделать это эффективно.

Answer 1

Посмотрите на неизменные двоичные деревья. Вы должны изменить немного больше узлов (каждый узел на корень), но это не меняет сложности вставки, которая log n в обоих направлениях. Действительно, это может даже улучшить производительность, потому что вам не нужен какой-либо код синхронизации.

Например, Эрик Липперт написал несколько постов об неизменных деревьях avl в C #. Последний был: Неизменяемость в C # Часть девятая: Академическая? Плюс моя реализация дерева AVL

Answer 2

Алгоритмы без блокировки, насколько я вижу, не имеют счетчиков ссылок, что затрудняет их общее использование; Вы не можете знать, является ли указатель на элемент действительным - возможно, этот элемент исчез.

Валуа 'справляется с этим с помощью некоторой экзотической схемы распределения памяти , которая на практике бесполезна .

Единственный способ увидеть сбалансированные деревья без блокировок - это использовать модифицированный MCAS, где вы также можете увеличивать / уменьшать, чтобы поддерживать счетчик ссылок. Я не посмотрел, можно ли таким образом изменить MCAS.

Answer 3

Я пытался сделать бинарные деревья доступными для чтения без блокировки, используя частичное копирование при записи. Я разместил незавершенную реализацию здесь http://groups.google.com/group/comp.programming.threads/msg/6c0775e9882516a2?hl=en&

Answer 4

Бумага Джона Валуа кратко описывает подход к реализации бинарного дерева поиска с использованием вспомогательных узлов. Я использую подход вспомогательного узла в моем проекте параллельной LinkedHashMap. Вероятно, вы можете найти много других статей о параллельных деревьях на CiteSeerX (бесценный ресурс). Я бы отказался от использования деревьев в качестве параллельного сбора данных, если это действительно не нужно, поскольку они имеют тенденцию иметь плохие характеристики параллелизма из-за перебалансировки. Часто более прагматичные подходы, такие как пропуск списков, работают лучше.

Answer 5

лучшее решение зависит от вашего приложения. Но если у вас есть база данных, хранящаяся в памяти, и вы хотите выполнять ее одновременное обновление и хотите иметь очень тонкую блокировку, вы также можете посмотреть на B-деревья, которые не требуют ротации узлов так часто, как бинарные деревья , Они также автоматически уравновешиваются, в отличие от бинарных деревьев, которые требуют большего количества вращений для поддержания балансировки (например, деревья Splay или AVL).

Если вы хотите иметь транзакционные модификации деревьев, вместо этого вы можете использовать функциональные B-деревья (которые Томас Данекер называет неизменными деревьями). Это своего рода двоичные деревья типа «копировать при записи», и единственное, что вам нужно для блокировки, - это корневой узел. Так что вам нужен только один замок. И на практике операции имеют ту же сложность, что и для двоичных деревьев, потому что все операции на функциональных двоичных деревьях - это O (log n), и вы тратите одинаковое логарифмическое время всякий раз, когда спускаетесь вниз по любому дереву.

Наличие одной блокировки на узел, скорее всего, не является правильным решением.

Answer 6

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

Вы можете получить баланс, сделав так, чтобы все N узлов совместно использовали одну блокировку. При вводе операции поворота найдите набор уникальных блокировок, используемых задействованными узлами. В большинстве случаев это будет только один замок.