Lock-free структуры данных рассматриваются как альтернатива мьютексам для исключения блокировок потоков, возникающих из-за работы планировщика ОС. В отличие от мьютексов, где вытеснение потока с захваченным ресурсом парализует систему, lock-free алгоритмы гарантируют прогресс всей системы.
В основе lock-free логики лежат три атомарные операции: безусловный обмен (Swap), условный обмен (CAS) и атомарная арифметика. Они позволяют изменять данные без риска прерывания между чтением и записью, что предотвращает потерю параллельности при конкуренции потоков.
Библиотека wxl использует аппаратные инструкции, включая барьеры памяти (std::atomic_thread_fence) для контроля порядка выполнения и команду паузы (core::cpu_pause) для оптимизации ресурсов процессора при ожидании в холостом цикле на архитектурах с поддержкой SMT.
Одним из примитивов библиотеки является core::atomic_trigger — легковесный флаг для координации событий. Он заменяет связку булевой переменной и мьютекса, гарантируя, что целевое действие будет выполнено ровно один раз потоком, выигравшим гонку за изменение состояния.
Также в wxl реализован интрузивный односвязный список с модификацией только головы. Такая структура стека не требует аллокаций в процессе работы и позволяет выполнять операцию push параллельно из множества потоков, затрачивая одну атомарную операцию на элемент при отсутствии конкуренции.
