связанный список

Question

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

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

EDIT: Спасибо за ответы людей. Пара вещей, которые я хотел бы добавить:

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

Answer 1

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

Interlocked Singly Linked Lists

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

Answer 2

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

Answer 3

Linked lists are inherently sequential data structures. Независимо от того, какой механизм вы используете для его реализации, интерфейс и ожидаемое поведение подразумевают последовательную логику.

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

Answer 4

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

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

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

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

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

1. Есть ли один или несколько считывателей?
2. Есть ли один или несколько авторов?
3. Единственный или дважды связанный список?
4. Некоторая идея вашего использования.

Answer 5

Что можно сказать о пропущенных списках? Посмотрите на реализацию java в «параллельном» пакете.