Зафиксирую в склерознике то, что довелось недавно делать. На случай, если когда-нибудь представится возможность рассказать поподробнее.
Специализированный mutex, который в сложившейся терминологии C++ной библиотеки можно было бы назвать как recursive_shared_timed_mutex.
Суть в том, что если нить держит shared-блокировку этого мьютекса, то эта же нить может взять новую shared-блокировку повторно. Нужно это для случаев, когда один и тот же мьютекс захватывается в рекурсивных вызовах.
При этом есть ограничение по времени ожидания захвата мьютекса. Нужно это для того, что если из-за ошибки программиста где-то все-таки дедлоки возникают, чтобы они не вешали намертво приложение, а была возможность хотя бы бросить исключение из-за истечения тайм-аута.
Реализация самая простая, без наворотов, на базе обычных C++ных mutex и condition_variable. В принципе, если текущая версия окажется слишком тормознутой, то можно будет упороться и наколхозить тоже самое на atomic-ах. Но пока в этом надобности не возникло.
Две специальные, заточенные под предметную область версионированные структуры данных.
В моем представлении версионированные структуры -- это такие, в которых каждый пользователь видит свою независимую версию этой самой структуры.
Чтобы было понятнее, давайте вообразим себе std::map<int, std::string>, с которым несколько нитей работают одновременно. Первая нить читает значения по ключам 0, 1, 2, 3, 4, 5, вторая нить читает значения по ключам 4, 5, 6, 7, 8, а третья нить изменяет значение для ключа 0, удаляет значение для ключа 5 и добавляет значения с ключами 9, 10 и 11.
Так вот фокус в том, что пока первая и вторая нить держат у себя "старую" ссылку на этот map, они не видят изменения, которые вносит третья нить. Происходит это потому, что первая и вторая нить работают с исходной версией map, а третья нить, как только начинает модификации, получает свою персональную новую версию, о которой первые две нити не знают.
Такой механизм работы означает, что третья нить не может просто так сохранить свои изменения. Требуется специальная операция commit, после успешного выполнения которой версия от нити №3 сможет заменить собой основную версию map.
При этом нити №1 и №2 все равно не будут видеть новую версию, поскольку они работают с map через "старую" ссылку. Чтобы перейти на актуальное содержимое map им нужно обновить эту ссылку у себя, т.е. явным образом обратиться к map с просьбой дать ссылку на последнюю актуальную версию.
Может оказаться так, что кроме нити №3 модификации в map сейчас вносит и нить №4. И свой commit четвертая нить может выполнить еще до того, как третья нить завершит свои модификации. В этом случае при commit-е нить №3 обнаружит, что актуальный map уже совсем другой.
Это все сильно напоминает работу с ветками в VCS: ты отпочковался от master-а (или trunk-а), сделал изменения в своей ветке, хочешь влить в master, а master-то уже ушел вперед. И нужно делать слияние (merging). Иногда оно происходит автоматически и безболезненно, а иногда приходится разбираться с конфликтами.
Так же и в версионированных контейнерах -- иногда нужно разбираться с конфликтами. И я не зря сказал выше, что контейнеры делались под специфику прикладной задачи. Эта специфика как раз и определяла, каким образом возникающие конфликты должны разруливаться в автоматическом режиме.
Один тип контейнера был вариацией на тему дерева поиска, но не простого, а чего-то больше похожего на префиксное дерево.
Второй же контейнер изначально был вектором, но из него пришлось сделать нечто, что допускает нумерацию элементов последовательно возрастающими числовыми индексами. Причем в чем-то идеологически версионированный вектор оказалось придумать даже сложнее, чем версионированное дерево: один затык был в том, как поступать с текущим размером контейнера, т.к. в параллельно существующих версиях эти размеры могли отличаться, а второй затык был в организации итерации по содержимому вектора. Все это не то чтобы сложно, но пришлось покурить бамбук и порассматривать ситуацию с разных точек зрения, чтобы затем прийти к варианту, который выглядел бы более-менее логично.
