параллельный связанный список

Question

Я пытаюсь создать связанный список в C ++, который позволяет одновременный доступ.Ясно, что использование единой блокировки для этого списка крайне неэффективно, поскольку непересекающиеся области могут обновляться параллельно.Теперь, какие у меня есть варианты, кроме хранения блокировки на узел?

Кроме того, будет ли лучше в этом случае неблокирующая версия?Любые соответствующие ссылки, кто-нибудь?

РЕДАКТИРОВАТЬ : Спасибо за ответы людей.Несколько вещей, которые я хотел бы добавить:

1. Как насчет хранения N блокировок для каждого M узла вместо отношения 1: 1 блокировка: узел?Некоторые темы будут ждать, но это своего рода компромисс.Как вы думаете?
2. Если я собираюсь найти какой-то узел в этом связанном списке, похоже, что все мьютексы должны быть заблокированы.Это проблема, потому что блокировка и разблокировка всех мьютексов занимает много времени.У кого-нибудь есть лучшая альтернатива?
3. Я открыт для неблокирующих алгоритмов.Но как мне использовать CAS в старом добром C ++ без использования ассемблера?Я слышал, что у gcc есть некоторые атрибуты __sync, которые выполняют похожую работу, но не уверены.
4. С неблокирующим подходом, как вы находите в связанном списке?

Answer 1

Можно реализовать неблокирующий односвязный список, используя взаимосвязанные функции:

Списки с одиночной связью

Я не думаю, что возможно реализовать неблокирующий двусвязный список без блокировки сравнения и обмена (CAS), которая не является широко доступной.

Answer 2

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

Что ты пытаешься сделать? Это должно определить, какую структуру данных вы используете, а не знакомство с теми структурами данных, которые вам уже удобны.

Answer 3

Есть много разных способов сделать это, в зависимости от того, как вы собираетесь использовать список.

Во-первых, для списка одна блокировка мьютекса не обязательно является большой проблемой, потому чтосписки могут поддерживать соединение.Скажем, у вас есть список символов AF и другой список BCDE.Вам не нужно блокировать мьютекс, вставлять B, блокировать его снова, вставлять C и т. Д. Вы можете вставить BCDE сразу между A и F, установив следующий указатель A на B и следующий указатель E на F, образуя ABCDEF.Независимо от того, сколько элементов вы хотите вставить одновременно, вам нужен только один замок.Это верно даже для двусвязного списка.Таким образом, это не может быть узким местом в вашем приложении.

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

Предполагая, что у вас есть один писатель и несколько читателей, вы можете полностью избежать блокировок мьютекса, используя атомарные инструкции, если они доступны для вашей архитектуры.В GCC они доступны через встроенные функции __sync_ *, а в Visual C ++ они доступны через Interlocked *, но если вы застряли с компилятором, который не поддерживает их напрямую, вы все равно можете использовать их через встроенную сборку.Автор будет использовать атомарные инструкции для атомарной установки следующих указателей для исправления элементов в и из списка.

Надеюсь, это поможет вам начать работу.Чтобы получить глубокий ответ, я бы предложил задать еще один вопрос, включая:

1. Есть ли один / несколько читателей?
2. Есть ли один / несколько авторов?
3. Один или два связанных списка?
4. Какое-то представление о вашем сценарии использования.

Answer 4

А как насчет Пропуск списков?Посмотрите на реализацию Java в "параллельном" пакете.

Answer 5

Вы уверены, что эту проблему стоит решить? Возможно, было бы более полезно инкапсулировать фактическое конечное использование в класс, который обрабатывает блокировку нормального list и обеспечивает потокобезопасный интерфейс? Таким образом, вы не пытаетесь установить блокировку на слишком низком уровне (который, как вы и предполагали, решить не так просто).