Задача 4. Fine graining

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

Условие

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

В предыдущей версии блокировок мы столкнулись с рядом ботлнеков:

В списке перемещения блокируются вставкой и удалением. Кроме того, при конкурировании вставки/удаления с итерацией происходит backoff/retry.

В дереве, кроме того, удаление вершины требует подмены её листом, и потому фактически блокируется весь путь до листа. Таким образом, поддерево будет закрыто для любого поиска на продолжительное время. Проблема заключается в том, что конкурирующие вставки/удаления могут недопустимо изменить структуру дерева.

Здесь альтернативой было бы блокировать узел на чтение, а затем делать upgrade-to-write блокировке, однако такая операция невозможна в реализациях rwlock, ни поддерживаемых POIX/windows, ни, соответственно, shared_lock в с++.

Задание

Будем избавляться от конкуренции перемещения со вставкой/удалением. Внутренние узлы в дереве помечаются на удаление и удаляются лишь при балансировке по достижению положения листа. Удаление из листа происзодит так же легко, как и в списке, при этом, поскольку вставка производится только в лист, достаточно лишь блокировать удаляемый лист для избежания конкурении со вставкой и поворотом.

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

Мы хотим, чтобы перемещение не блокировалось удалением: для этого будем делать очистку памяти периодической сборкой мусора.

При достижении refcount = 0, узел отправляется во free_list (пургаторий), и далее освобождается выделенным тредом/таском. При этом, значение может достичь нуля несколько раз. В лекциях доказывается теорема, показывающая, что необходимо и достаточно двух проходов для удаления из консистентной структуры данных с подсчётом ссылок.

В учебных целях допускается создавать тред прямо в структуре данных.

free_list — односвязный список со ссылками на узлы на удаление. Один и тот-же узел может оказаться в списке несколько раз, поэтму перед освобождением памяти нужно обеспечить уникальность узла.

При вставке в список нужно захватывать блокировку. на +1 балл реализация lock-free, однако она требует существенной внимательности, ведь удаление в gc треде из такого списка будет конкурировать со вставкой из других тредов

Для вставки ранее помеченного на удаление ключа достаточно сделать delete-unmarking.

Те, кто пишет на языках с автоматической сборкой мусора, делают free-list для мемори-реза.

Литература

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

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

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

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

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

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

0.073s 0.013s 13