Это просто для повышения квалификации параллелизма ...
Представьте, что у меня есть структура данных дерева B + в памяти - несколько элементов на узел, только конечные узлы содержат элементы, конечные узлы также образуют связанный список для простого последовательного доступа. Вставки и удаления в основном влияют только на конечный узел, но могут привести к разделению или слиянию узлов в процессе, который может распространиться на корень.
У меня однопотоковая реализация, и обновления следуют своего рода подходу предварительного планирования. Рекурсия повышает уровень дерева с конечного уровня до тех пор, пока необходимо изменить узлы, создавая связанный список (связывающий локальную переменную в разных рекурсиях), который описывает необходимые изменения. Когда он знает, что нужно, он может проверить, может ли он выделить все необходимые узлы, и применить все необходимые изменения (или нет), ссылаясь на этот план, прежде чем выпадать из рекурсии.
Эта реализация также «поддерживает» итераторы в обновлениях, поэтому итераторы не аннулируются при вставке / удалении, пока не будет удален конкретный элемент, на который они указывают. Вставки / удаления внутри одного и того же узла приводят к обновлению итераторов, указывающих на этот узел.
Проблема в том, что мне нужно сделать его многопоточным, поддерживающим потенциально много читателей и писателей одновременно.
Я хочу, чтобы несколько читателей могли читать и писать одновременно, при условии, что в результате отсутствует риск повреждения. Поэтому для чтения я вообще не хочу взаимоисключающий доступ, даже к одному узлу. Для записи я хочу заблокировать минимальное количество узлов, необходимых для изменения. И я хочу избежать тупика, конечно.
К счастью, это не то, что мне на самом деле нужно делать, но, поскольку я пренебрегал своими навыками параллелизма, это похоже на хороший мысленный эксперимент.
Это, очевидно, похоже на проблемы, с которыми приходится сталкиваться базам данных и файловым системам, поэтому я предполагаю, что я мог бы получить некоторые ссылки на такие вещи, что было бы замечательно.
Итак - как бы я справился с синхронизацией потоков для этого? Я смутно вижу роль мьютексов и / или семафоров на узлах, но какие стратегии я бы использовал для работы с ними?