нужен пруфлинк, на пальцах - это сильно избыточно, требует матрицы ячеек).
Принципиальным элементом большинства lock-free алгоритмов является допущение, что элемент данных может быть атомарно прочитан или изменён. На практике это приводит к тому, что большинство реализаций для нетривиальных данных используют размещение в отдельных блоках памяти (куча, Java-объекты) и манипулируют указателями. Такой подход вносит дополнительные расходы в виде дополнительных косвенных обращений к памяти и управления кучей, снижает эффективность использования кэшей. Представляет интерес разработка практически эффективных алгоритмов атомарного обновления многословных объектов с учётом применения как элементов различных lock-free структур данных (Hash-таблицы, очереди). Отдельное потенциально инетерсное направление - решение задачи на основе HTM-механизмов и оценка эффективности с учётом различных профилей нагрузки. |
Работы в области CRWW ведутся достаточно давно - первые статьи датированы 80-ми годами. Есть общие алгоритмы, которые обеспечивают lock-free mw/mr crww. На практике они довольно громоздкие и требуют значительных накладных расходов как по памяти, так и по скорости ( нужен пруфлинк, на пальцах - это сильно избыточно, требует матрицы ячеек).
В нашей конкретной задаче писатель всегда один, и достоверно известно, что пишет не с такой частотой, чтобы читатель постоянно натыкался на нечетные версии.
Для одной ячейки есть алгоритм seqlock(stampedlock), базирующийся на версионировании - writer, начав писать, увеличивает версию на 1; закончив - еще на 1. Читатель, увидев нечетную версию понимает, что писатель в процессе и уходит в цикл. К сожалению, он не lock-free. Если writer встанет, читатель зациклится.
Задача: защитить multi-word регистр seqlock-ом и сделать алгоритм lock-free.
Предлагаемое решение:
Задача-минимум: реализовать, формально доказать в терминах состояний.
Дальнейшие задачи:
). С теоретической точки зрения интересно получить доказательство на языке инвариантов и в терминах модели памяти, где набор возможных fences шире, чем полный барьер памяти.