Реализуются хорошо известные структуры данных. Очередь основана на Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Que Algorithms Майкла Скотта и Магеда Майкла, стек основан на Systems программировании: справляется с параллелизмом R. K. Treiber и spsc_queue считается «folklore» и реализуется в нескольких проектах с открытым исходным кодом, включая ядро linux. Все структуры данных подробно обсуждаются в «Искусство многопроцессорного программирования» Herlihy & Shavit.

boost::lockfree::queue и boost::lockfree::stack классы - это узлы на основе данных, на основе связанного списка. Управление памятью без блокировки структур данных является нетривиальной проблемой, потому что нам нужно избегать того, чтобы одна нить освободила внутренний узел, в то время как другая нить все еще использует его. boost.lockfree использует простой подход, не возвращающий никакой памяти в операционную систему. Вместо этого они поддерживают свободный список, чтобы повторно использовать их позже. Это делается по двум причинам: во-первых, в зависимости от реализации распространителя памяти, освобождающего память, может блокироваться (так что реализация больше не будет беззамочной), а во-вторых, большинство алгоритмов воспламенения памяти запатентованы.

Проблема ABA является общей проблемой при реализации беззамочных структур данных. Проблема возникает при обновлении атомной переменной с помощью операции compare_exchange: если значение A было прочитано, нить 1 меняет его, чтобы сказать C и пытается обновить переменную, она использует compare_exchange для записи C, только если текущее значение A. Это может быть проблемой, если в то время поток 2 меняет значение от A до B и обратно к A, потому что ниша 1 не наблюдает изменения состояния. Общий способ избежать проблемы ABA состоит в том, чтобы связать счетчик версии с значением и изменить оба атомарно.

boost.lockfree использует tagged_ptr класс помощников, который связывает указатель с интегралом. Для этого обычно требуется двупроводная compare_exchange, которая не доступна на всех платформах. IA32 не предоставил cmpxchg8b opcode перед процессором пентиума, и он также отсутствует во многих архитектурах RISC, таких как PPC. Ранние процессоры X86-64 также не предоставляли инструкции cmpxchg16b. На 64-битных платформах можно работать над этим вопросом, ведь часто используется не полное 64-битное адресное пространство. На X86_64, например, для адреса используется только 48бит, поэтому мы можем использовать оставшиеся 16бит для профилактики ABA. Подробности просим ознакомиться с реализацией boost::lockfree::detail::tagged_ptr класс.

Для беззамкнутых операций на 32-битных платформах без двойной проводки compare_exchange мы поддерживаем третий подход: с помощью массива фиксированного размера для хранения внутренних узлов мы можем избежать использования 32-битных указателей, но вместо этого достаточно 16-битных индексов в массиве. Однако это возможно только для фиксированных структур данных, которые имеют верхнюю часть внутренних узлов.

boost.lockfree структуры данных имеют базовую поддержку Boost.Interprocess. Единственная проблема заключается в блокировании эмуляции безблокированных атомов, которые в текущей реализации не гарантированы быть интерпроцесс-безопасными.