Задача 1. Однопоточная консистентность ≡

Условие

Задание: Консистентное дерево или список.

У каждого нода появляются поля deleted и ref_count для поддержки консистентных итераторов. В начале у узла всегда ref_count=2, а левый и правый sentinel никогда не удаляются. Итераторы на время указания на объект увеличивают ref_count.

Если при обратном уменьшении ref_count значение достигло нуля и выставлен флаг deleted, то узел полностью удаляется.

Итераторы не гарантируют, что ++-- вернётся на тот-же объект, однако все операции всегда приводят к консистентному состоянию.

При переходе на соседний нод, нужно проускать удалённые. Реализуется это либо через поле deleted, либо через проверку инварианта двусвязного списка node->next->prev == node

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

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

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

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

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

0

1

Задача 2. Coarse-grained list/tree ≡

Условие

Задание: Атомарное дерево или список с блокировками грубой огранки.

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

Итераторы захватывают весь контейнер на время выполнения какой-то операции. В то же время нет не обходимости держать блокировку всё время жизни итератора.

Кроме того, уже здесь мы будем использовать rwlock для возможности параллельного чтения.

Дополнительно можно проделать оптимизацию (+1 балл): вертикальное зонирование блокировок, где изменение refcount не блокируется чтением/изменением ссылок на смежные узлы. Тем не менее будьте бдительны: разделение одной блокировки на две даёт отенциальную возможность для гонок и атак! Нужно обязательно покрыть это тестами.

Как и ранее, гарантируется, что все операции всегда приводят к консистентному состоянию.

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

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

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

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

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

0

1

Задача 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

Задача 4. Fine graining ≡

Условие

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

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

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

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

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

Задание

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

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

• T1: Итератор считывает указатель (next/prev/parent) node
• T2: Происходит удаление узла. node->refcount = 1;
• T2: Итератор, державший узел, удаляется, или передвигается. node->refcount = 0;
• T2: delete node
• T1: node->ref_count++ // error!

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

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

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

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

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

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

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

Литература

• A Practical Concurrent Binary Search Tree  — Bronson's AVL tree
• реализация в libcds
• [gc] Jones R., Hosking A., Moss E. - The garbage collection handbook. The art of automatic memory management  — исчерпывающий сборник знаний в области сборки мусора
• 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

Задача 5. Spinlock-based rwlock ≡

Условие

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

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

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

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

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

0

1

Задача 6. Consistent access ≡

Условие

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

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

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

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

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

0

1

Задача 7. Durable writes ≡

Условие

Требуется написать программу, которая

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

Входные данные содержат

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

Выходные данные должны содержать

Ограничения

1 < N < 100

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

0

1