Вставка списка, дизъюнктная параллель?

Question

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

К сожалению, все реализации, которые я проверил до сих пор, используют блокировку на основе списка, а не что-то вроде блокировки на основе узла.

Любая помощь людям?

РЕДАКТИРОВАТЬ 1: Спасибо всем за первоначальные ответы. Использование блокировки на основе узла означает, что для вставки после узла или удаления узла мне нужно заблокировать предыдущий и следующий узел. Теперь вполне возможно, что к тому времени, когда Поток 1 попытается заблокировать предыдущий узел, который был удален в Потоке 2. Как защититься от таких аварий?

Answer 1

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

Обновление, для РЕДАКТИРОВАНИЯ 1

Вы можете обойти эту проблему, имея несколько читателей для каждого списка, одну блокировку записи, ( rwlock ), где вы получаетепрочитайте «блокировку до получения блокировки на узел для вставок, но для удаления вам нужно получить единственную блокировку« записи ».Вы довольно легко избегаете ненужных проблем синхронизации для операций чтения / вставки, а удаление достаточно просто.(Предполагается, что delete гораздо реже, чем insert)

Answer 2

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

К сожалению, не так много широко известных реализаций. Возможно, вам придется свернуть свой собственный. Вот документация gcc о поддержке атомарных операций:

http://gcc.gnu.org/onlinedocs/gcc-4.1.2/gcc/Atomic-Builtins.html

Answer 3

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

Хуже того, вы получаете равные возможности тупиковой трапезы, которые вам нужно лечить.

Поэтому блокировка на основе списка проще, и поэтому вы видите больше оони.

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