Ну, вы уже определили один я, как правило, предложить - одновременное skiplist, но отсутствие других, чем выше три, я думаю, простой связанный список с пошаговым узлом мьютексами будет работать другие специфические требования:
Каждый узел содержит один элемент (или ссылку) и один простой мьютекс. Я буду использовать Java здесь, потому что это помогает избежать условий гонки вокруг восстановления узла.
Поиск в списке состоит из итерации по узлам с головы, нет необходимости получать блокировки (хотя вам необходимо обеспечить видимость между потоками в какой-то момент - вы можете выбрать, как часто это происходит - один раз за поиск может быть достаточно хорошим).
Чтобы добавить элемент, выполните поиск до тех пор, пока вы не найдете непосредственные предшественники и узлы-преемники для значения, которое вы хотите вставить, заблокируйте мьютекс, связанный с предыдущим узлом, снова проверьте узел-преемник (он может быть изменен из под вами), затем сплайсируйте новый узел.
Исключение работает аналогично - найдите узел-предшественник для узла, который вы хотите удалить, заблокируйте узел-предшественник, убедитесь, что он все еще является предшественником, и вытащите его из дерева.
Эта структура сортируется (насколько это правильно - я этого не доказал!).
Эта структура, очевидно, позволяет использовать несколько считывателей (по какой-либо причине считыватели никогда не блокируются) и несколько авторов, хотя авторы, пытающиеся манипулировать одной и той же частью списка (например, два вставки потоков, имеющие одну и ту же точку сращивания), будут ждать друг друга.
Структура кажется относительно легкой для рассуждения о том, что она основана на одном связанном списке, с довольно простой структурой блокировки и несколькими простыми инвариантами. Однако я не потратил больше нескольких минут на рассуждения о его правильности. Вы можете сделать еще проще рассуждать, ценой производительности, сделав политику блокировки более тяжелой - для вставки и удаления блокируйте каждый узел во время итерации, а затем заблокируйте преемника перед тем, как разблокировать предыдущий узел - таким образом вы будете оба узла заблокированы, когда вы найдете точку сращивания или удаления, поэтому не требуется «двойная проверка, обратный путь».
Вы можете полностью избавиться от замков и использовать список без блокировки при сохранении вашего состояния «должно быть отсортировано», но я не думал об этом в глубину - как минимум, я подозреваю, что он будет быть «сложнее рассуждать».
В C++ структура более активна, поскольку вы не можете полагаться на GC, чтобы поддерживать узлы вокруг, пока читатели могут смотреть на них, поэтому простая стратегия, позволяющая читателям перемещаться в блокировке - свободный способ не летает, если вы хотите удалить узлы. Вы можете настроить его, заставляя читателей блокировать каждый посещенный узел, но это отстойно как для производительности (очевидной), так и для параллелизма (потому что, хотя вы можете иметь несколько читателей и писателей каким-то основным способом, они никогда не смогут переходить друг к другу, поэтому практический параллелизм сильно ограничен).
Альтернативой может быть использование rwlocks в каждом узле, считыватели только считывают блокировки и вставляют/удаляют, считывая блокировки, чтобы найти позицию для работы, а затем перейти на запись. Валюта, по крайней мере, улучшена, поскольку читатели могут проходить через читателей, но авторы все еще блокируют читателей (так что все читатели, которые выполняют итерацию в позиции до того узла, на котором запускается операция записи, не смогут пропустить этот узел до завершения операции).
Теперь, все, что сказало (whew!), Я должен упомянуть, что другое, что «легко рассуждать» об этой структуре кажется почти уступающим параллельному списку пропуска любым материальным способом, за исключением, возможно, немного меньшего использования памяти (может быть). В частности, в нем нет поведения поиска журнала (N). Он не полностью блокирован (в некоторых случаях авторы могут ждать авторов). Я даже не уверен, что гораздо проще рассуждать о том, насколько параллелизм идет, хотя базовая структура проста.
Я думаю, что если бы вы действительно хотели, вы могли бы расширить этот тип блокировки «за узел» до чего-то вроде rb-дерева, если хотите, но это нелегко. В частности, вам нужно найти какой-то узел для блокировки до любых поворотов дерева, которые «достаточно высоки», что вы можете быть уверены, что любой поток, который хочет выполнить модификацию, которая повлияет на правильность вашего вращения, также попытается заблокировать тот же узел. В связанном списке это «узел предшественника» - в AVL или RB-дереве это не так просто.
@Juliet: Проблема с использованием неизменяемой структуры данных заключается в том, что для моего приложения это по существу то же самое, что и использование нескольких считывателей и одного писателя (с точки зрения производительности). Поскольку, если два автора (с неизменной структурой) вставляют один узел, то один из них должен перезапускаться в любом случае, с новым деревом, созданным конкурирующим автором, который первым внес свои изменения. – thr
Существует множество стратегий для решения этой проблемы. В вселенной MapReduce у нас есть одна большая проблема, которая может быть разделена на подвыборы. Например, предположим, что мы хотим найти первые 1000 000 простых чисел, используя пробное подразделение. Мы могли бы запустить 100 дочерних потоков, где первая нить проверяет число 1-999, вторую проверку потоков 1000-1999, следующие тесты 2000-3999 и т. Д. По мере завершения каждого потока он передает результаты в другой поток, который объединяет все отдельные результаты в один результат. – Juliet
Если вы не можете разделить проблему на подзадачи, также работает следующее: основной поток содержит вашу структуру данных. Мастер-поток предоставляет два свойства: Insert и Query, где эти методы изменяют или возвращают структуру данных в ее текущем состоянии соответственно. Детские потоки могут вызывать методы в основном потоке для обновления или запроса структуры данных. Поверхность этой стратегии - это атомарные обновления (и, если они реализованы правильно, транзакционные), и потоки не могут перезаписывать друг друга. Недостатком является то, что дочерние потоки не имеют доступа к структуре данных в режиме реального времени. – Juliet