| Входной файл: | Стандартный вход | Ограничение времени: | 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 | |
|