Concurrency and Consistency. Non-blocking, lock-free and async. Пост №6. Структура данных Queue: от наивного алгоритма к lock-free реализации

В прошлом посте мы закончили разбирать нашу синтетическую задачу про денежки и я обмолвился что есть примеры алгоритмов и структур данных в которых также используется механизм взаимопомощи потоков. У нас уже была заметка про Lock-Free Stack Трайбера и в нем такой механики нет, за ненадобностью.

А что насчет очередей? Фундаментальная структура данных, встречается практически везде. Существует ли у нее lock-free реализация? Этому вопросу я посвятил сегодняшнюю заметку.

Залетайте читать, внутри полноценный экскурс в очереди - от классики до реализаций из научной статьи Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms. С примерами на Golang.

Приятного чтения!