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

Question

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

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

Answer 1

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

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

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

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

Answer 2

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

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

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

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

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

Answer 3

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

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

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

Answer 4

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

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

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

Answer 5

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

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

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

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

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

Answer 8

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

Answer 9

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