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