Эффективное параллельное дерево

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

Дерево должно поддерживать эти операции:

Добавление и удаление узлов
Сортировать ветки каждый раз, когда вставляется новый node
Итерация по всем узлам (без ConcurrentModificationException)
Поиск элемента по пути

Ответ 1

Взгляните на: Concurrent-Trees в коде Google для способа редактирования древовидных структур без блокировки.

Проект предоставляет параллельные деревья Radix и Suffix для Java. Они поддерживают одновременное чтение и запись, а чтение не блокируется. Он работает, применяя патчи к дереву атомарно. Хотя эти типы деревьев могут быть не такими, какие вы хотите, подход, использующий "исправление", как описано в TreeDesign, полезен для любого типа древовидная структура.

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

Ответ 2

Структура Java, которая наиболее близка к тому, что вам может понадобиться, это ConcurrentSkipListSet (или, возможно, ConcurrentSkipListMap).

Если вам нужен более индивидуальный подход, вы можете реализовать пользовательскую древовидную структуру, если у вас есть иерархическая блокировка чтения и записи. Ниже приведен аналогичный вопрос о том, как реализовать блокировку чтения и записи: fooobar.com/questions/531250/...

Ответ 3

Вы можете использовать блокировку чтения-записи в своей структуре таким образом, что несколько потоков могут считываться currenturrent, но только один поток за раз может изменить его. Если какой-либо поток пытается изменить структуру, он не сможет этого сделать, пока все читатели не прочитают свои чтения. Если поток хочет читать, это может быть только в том случае, если писатель еще не работает, или он находится на графике внесения некоторых изменений. Возможно, это поможет:

http://docs.oracle.com/javase/1.5.0/docs/api/java/util/concurrent/locks/ReentrantReadWriteLock.html

Ответ 4

Основная идея с блокировкой чтения/записи

Для всех методов записи используйте следующую идиому:

someWriteMethod(){
  writeLock.lock();
  // logic
  writeLock.unlock();
}

Для всех методов чтения используется аналогичный код:

someReadMethod(){
  readLock.lock();
  // logic
  readLock.unlock();
}

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

Обратите внимание, что если ваш код (замените логический комментарий выше) может вызвать исключение, убедитесь, что вы освободили блокировки перед выходом из метода в разделе finally.