Concurrency and Consistency. Non-blocking, lock-free and async. Пост №7. Lock-free в реальном мире

Несколько постов подряд были сплошные харды, сложный кодан и отсылки к статьям. При этом я совсем не рассказывал о том где-же встречается всё то что мы рассматривали. Исправляюсь.

🔵 Рантайм языка Golang - очередь горутин
runq - это очередь готовых к выполнению горутин, привязанная к одному процессору (P). Её единственная задача: дать ответ на вопрос «что мне выполнять следующим?». И при этом:
- Отвечать как можно быстрее и дешевле
- С возможностью для простаивающих потоков подбирать чужую работу.

Эта очередь реализована через кольцевой буфер - структуру данных которая отлично работает в конкурентных сценариях и даже без мьютекса.

Ссылка на код в runtime2.go

🔵 Рантайм языка Golang - GC и Lock-free Stack
С помощью этого стека GC коллекционирует указатели на объекты для дальнейшего очищения. Интересный момент - элементом стека является не конкретная ссылка или указатель а буфер из 256 элементов. По сути вставка в стек идет батчами.

Код в golang/go

🔵 Рантайм языка Golang - Lock-Free Deque в sync.Pool
Популярный примитив для контроля аллокаций использует под капотом lock-free структуру данных

Код в golang/go

🔵 Apache Cassandra - Atomic Btree Partition
AtomicBTreePartition - структура, хранящая строки одного ключа партицирования в memtable. Само дерево неизменяемо, обновление строит новую версию с разделением пути (path copying), а затем подменяет ссылку через AtomicReferenceFieldUpdater.compareAndSet.

Код в apache/cassandra

🔵 Linux - lock-free linked list
Структура данных используется в планировщике, RCU, низкоуровневых функциях реализующих Symmetric MultiProcessing, упоминается в реализации сетевых примитивов.

Код в torvalds/linux

—————

На этом всё, надеюсь мне удалось продемонстрировать что lock-free это не просто теория, а очень даже практика😊

Дальше по плану разбор наивысшей гарантии неблокирующей синхронизации - Wait-Free