Без блокировки, постоянное время обновления параллельных древовидных структур данных?

20

В последнее время я немного читал литературу и нашел довольно интересные структуры данных.

Я исследовал различные методы уменьшения времени обновления до худшем случае [1-7].О(1)

Недавно я начал изучать структуры данных без блокировок для поддержки эффективного параллельного доступа.

Использовались ли какие-либо из этих методов обновления времени худшем случае при реализации структур данных без блокировки?О(1)

Я спрашиваю, потому что; мне они кажутся очевидным практическим продолжением этого «теоретического усовершенствования».


  1. Тарьян, Роберт Эндре. «Обновление сбалансированного дерева поиска в O (1) вращениях». Письма обработки информации 16, нет. 5 (1983): 253 - 257.

  2. Дрисколл Дж. Р., Н. Сарнак, Д. Д. Слеатор и Р. Э. Тарьян. «Обеспечение устойчивости структур данных». В материалах восемнадцатого ежегодного симпозиума ACM по теории вычислений, 109–121. STOC '86. Нью-Йорк, штат Нью-Йорк, США: ACM, 1986.

  3. Левкопулос С. и Марк Х. Овермарс. «Сбалансированное дерево поиска с O (1) наихудшим временем обновления». Acta Inf. 26, нет 3 (ноябрь 1988 г.): 269–277.

  4. Флейшер, Рудольф. Простое сбалансированное дерево поиска с O (1) наихудшим временем обновления

  5. Дитц, Пол Ф. и Раджив Раман. «Дерево поиска пальца с постоянным временем обновления». Письма обработки информации 52, нет. 3 (1994): 147 - 154.

  6. Лагогианнис, Джордж, Христос Макрис, Яннис Панагис, Спирос Сиутас и Костас Цихлас. «Новые динамически сбалансированные поисковые деревья с наихудшим постоянным временем обновления». J. Autom. Lang. Гребень. 8, нет. 4 (июль 2003 г.): 607–632.

  7. Бродал, Герт Штелтинг, Джордж Лагогианнис, Христос Макрис, Афанасиос Цакалидис и Костас Цихлас. «Оптимальные деревья поиска пальцев в указателе». J. Comput. Сист. Sci. 67, нет. 2 (сентябрь 2003 г.): 381–418.

В
источник
2
Пожалуйста, рассмотрите возможность добавления ссылок на документы в качестве любезности людям, которые хотят исследовать вашу проблему.
Рафаэль
3
Хорошо, добавлено в ссылки на соответствующие статьи.
АТ
1
Я предлагаю сделать репост на cstheory.SE (со ссылкой здесь), если вы не получили полезного ответа в ближайшее время.
Джефф
До этого я пользовался практической библиотекой структур данных без блокировки . Они имеют некоторую поддержку структур данных дерева без блокировки. Может быть, есть то, что вы ищете.
Реза

Ответы:

4

О(1)

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

Свобода блокировок обычно проще всего, когда ваши структуры данных неизменны ( чисто функциональны ). Вы просто сохраняете глобальный указатель на текущую версию структуры данных. Читателям не нужно ничего блокировать. Модификации структуры данных осуществляются путем замены глобального указателя на одну неизменную структуру данных на другую.

Например: если у вас чисто функционально сбалансированное дерево, вы:

  1. Запишите текущий глобальный указатель на корень дерева.
  2. Создайте новое дерево, которое вставляет или удаляет узел. (Это логарифмическое по времени и пространству число узлов, находящихся в настоящее время в дереве, и включает создание новых узлов от точки модификации до корня и просто наведение всего нового на старые части предыдущей версии структуры данных. )
  3. Атомно сравнить и поменять местами глобальный указатель на корень. (Обратите внимание, что это может не сработать, если между записью старого корневого указателя и сейчас произошла другая модификация. Если это произойдет, вернитесь к шагу 1 и повторите попытку. Это так называемое «оптимистическое управление параллелизмом».)

Обратите внимание, что наиболее важной частью является то, что я сказал выше о необходимости поддерживать инварианты представления. Обычно недостаточно иметь алгоритм, который атомарно вносит изменения в середине дерева. Почему? Например: у вас может быть поток чтения, который находится в процессе предварительного обхода дерева. Если вы модифицируете узел, который является предком узла, который они в данный момент читают, то вы лишите законной силы предварительные условия, которые, по их мнению, были применены. Читатель должен уметь работать со структурой данных в точности так, как это было до внесения изменений, или точно так же, как и после внесения изменений. Не что-то среднее.

О(Lограмм(N))О(N)

Блуждающая логика
источник
Я думаю, что активные методы ожидания, например, с использованием сравнения и замены, обычно называются «без блокировки», поэтому есть некоторые выходы, даже в изменяемой настройке.
Рафаэль
Я не знаком с термином активное ожидание (и Google не помогает). (Если вы говорите о работе Когана и Петранка, то здесь показано, как превратить алгоритмы без блокировок в без ожидания.) Я добавил редактирование о том, как вы можете работать с изменчивостью для свободы блокировок в целом.
Блуждающая логика
Под «активным ожиданием» я подразумеваю что-то вроде while ( !P ) { noOp(); } doWork();где noOpможет быть sleepили подобное.
Рафаэль
В части « Правка» вы упомянули технику освобождения изменяемых структур данных. Как указано, мы копируем всю структуру данных, создаем моды для копии, а затем используем примитив CAS. Однако как сделать Copyшаг атомарным? Кажется, это еще одна сложная проблема atomic snapshot.
hengxin
@hengxin: воспринимайте примитив CAS как оператор публикации. До публикации структуры данных доступ к ней имеет только поток, выполняющий изменения. После публикации структуры данных она неизменна. Шаг копирования не должен быть атомарным, потому что единственное, что может копировать поток - это опубликованная версия, которая является неизменной. Если два потока одновременно пытаются изменить, они оба копируют одну и ту же неизменную структуру данных, изменяют свои локальные копии, и затем одна из операций CAS завершается успешно, а другая - не выполняется. Тот, который терпит неудачу, должен переписать и обновить.
Блуждающая логика