Возможен ли двусвязный список без блокировки (ожидания)?

Question

Задаю этот вопрос с помощью тега C#, но если это возможно, то это должно быть возможно на любом языке.

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

Answer 1

Простой поиск в Google покажет множество документов с двусвязными списками без блокировки.

Однако они основаны на атомарном CAS (сравнить и поменять местами).

Я не знаю, насколько атомарны операции в C#, но согласно этому сайту

http://www.albahari.com/threading/part4.aspx

Операции C# гарантированно являются атомарными только для чтения и записи 32-битного поля.Никаких упоминаний о CAS.

Answer 2

Да, это возможно, вот моя реализация STL-подобного Двусвязный список без блокировки в С++.

Пример кода, который создает потоки для случайного выполнения операций над списком

Для работы без проблем ABA требуется 64-битное сравнение и замена.Этот список возможен только благодаря диспетчер памяти без блокировки.

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

Answer 3

Вот бумага который описывает двусвязный список без блокировки.

Мы представляем эффективную и практическую реализацию без блокировки параллельной Deque, которая имеет доступ к параллельной доступности и использует атомные примитивы, которые доступны в современных компьютерных системах.Ранее известные алгоритмы без блокировки дектов основаны либо на недоступных примитивах атомной синхронизации, только реализуют подмножество функциональности, либо не предназначены для непрерывных доступа.Наш алгоритм основан на двойном связанном списке, и требует только однослого сравнения и замены ...

У Росса Бенсины есть несколько действительно хороших ссылок, которые я только что нашел, на многочисленные статьи и примеры исходного кода для "Некоторые замечания по алгоритмам без блокировок и без ожидания".

Answer 4

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

Например, возьмем операцию добавления: если вы вставляете узел B между A и C, вам нужно установить B->next, B->prev, A->next и C->prev в одной атомарной операции.Interlocked с этим не справится.Предварительная настройка элементов B даже не помогает, потому что другой поток может решить сделать вставку, пока вы готовите «B».

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

Answer 5

Прочтите сноску: они планируют удалить ConcurrentLinkedList из версии 4.0 до окончательного выпуска VS2010.

Answer 6

Ну, вы даже не спросили, как это сделать.Но если вы можете выполнить атомарный CAS на C#, это вполне возможно.

На самом деле я сейчас как раз работаю над реализацией двусвязного списка ожидания бесплатного ожидания на C++.

Вот документ, описывающий это.http://www.cse.chalmers.se/~tsigas/papers/Haakan-Thesis.pdf

И презентация, которая также может дать вам некоторые подсказки.http://www.ida.liu.se/~chrke/courses/MULTI/slides/Lock-Free_DoublyLinkedList.pdf

Answer 7

Можно написать алгоритмы без блокировок для все копируемые структуры данных на большинстве архитектур [1].Но сложно написать эффективные.

Я написал выполнение принадлежащий двусвязный список без блокировки, созданный Хоканом Сунделлом и Филиппасом Цигасом для .Net.Обратите внимание, что он не поддерживает атомарный PopLeft из-за своей концепции.

[1]: Морис Херлихи:Результаты невозможности и универсальности для синхронизации без ожидания (1988).

Answer 8

Кстати, в .NET 4.0 добавлен ConcurrentLinkedList, потокобезопасный двусвязный список в пространстве имен System.Collections.Concurrent.Вы можете прочитать документация или Сообщение блога описывая это.

Answer 9

Я бы сказал, что ответ очень глубоко квалифицированный: «да, это так». возможный, но тяжело».Чтобы реализовать то, о чем вы просите, вам в основном понадобится что-то, что скомпилирует операции вместе, чтобы гарантировать отсутствие коллизий;по существу, было бы очень сложно создать общую реализацию для этой цели, и она все равно будет иметь некоторые существенные ограничения.Вероятно, было бы проще создать конкретную реализацию, адаптированную к конкретным потребностям, и даже в этом случае это ни в коем случае не было бы «простым».