Задача 3. Medium-graining

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:8  

Условие

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

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

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

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

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

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

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

Литература

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

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

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

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

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

Стандартный вход Стандартный выход
1
0
1

0.066s 0.012s 13