Задача 3. Medium-graining ≡

Условие

Задание: Блокировки средней огранки.

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

Итераторы при перемещении захватывают узел, на котором находятся, для чтения указателя на соседний узел. Когда это происходит, гарантируется, что ref_count соседнего узла не будет равен нулю и, как следствие, будет удалён.

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

Удаление из дерева производится аналогично: необходимо заблокировать все мутируемые узлы. Порядок применяется как правило parent-then-clild. При этом, поиск вершины на замену лучше делать методом hand-over-hand с блокировкой на запись, чтобы исключить гонку при переходе от read lock к wite lock (требуется разблокировка).

Вставки в связномм списке аналогична, удалению, а в дереве — тривиальна.

Балансировка может проводиться каскадомс операции поворота с независимыми блокировками. Однако, переходить к повороту следиет, убедившись после блокировок, что родитель, на которого мы перешли, остался родителем.

Литература

• Kessels — On-the-fly optimization of data structures  — основополагающая работа, предлагающая алгоритм балансировки на лету.
• Nurmi, Soislon-Soininen at al Relaxed avl trees, main-memory databases and concurrency  — улучшение алгоритма с поддержкой удаления, но только для внешних (хранящих данные в листьях) деревьев
• Larsen: AVL Trees with Relaxed Balance  — Доказательство сходимости за O(nlog(k+n)), где k — количество конкурентных мутаций
• Coarse-Grained, Fine-Grained, and Lock-Free Concurrency Approaches for SelfBalancing B-Tree  — обзор разных подходов к блокировкам классического B-дерева, оригинальное исследование-диссертация

Формат входных данных

Отправьте ссылку на конкретный коммит в репозитории на Github, например

https://github.com/klenin/cats-main/commit/dce22c8348808959881ed7d6852c520a41e47c9a

В качестве среды разработки укажите Answer text.

Примеры тестов

0

1