7.2. Примеры структур данных, свободных от блокировок

Для демонстрации некоторых приёмов проектирования структур данных, свободных от блокировок, мы рассмотрим реализации ряда простых структур.

Как уже отмечалось, структуры данных, свободные от блокировок, опираются на использование атомарных операций и связанные с ними гарантии упорядочения доступа к памяти, благодаря которым можно быть уверенным, что изменения данных становятся видны потокам в правильном порядке. Сначала мы будем использовать во всех атомарных операциях принимаемое по умолчанию упорядочение memory_order_seq_cst, потому что оно проще всего для понимания (напомним, что семантика memory_order_seq_cst устанавливает полное упорядочение всех операций). Но позже мы посмотрим, как ослабить некоторые ограничения с помощью семантик memory_order_acquire, memory_order_release и даже memory_order_relaxed. Хотя ни в одном примере мьютексы не используются напрямую, не стоит забывать, что отсутствие блокировок гарантируется только для типа std::atomic_flag. На некоторых платформах в казалось бы свободном от блокировок коде могут использоваться внутренние блокировки, скрытые в реализации стандартной библиотеки С++ (детали см. в главе 5). В этом случае простая структура данных с блокировками может оказаться предпочтительнее, но дело не только в этом; прежде чем выбирать ту или иную реализацию, нужно четко сформулировать требования, а затем подвергнуть профилированию различные решения, удовлетворяющие этим требованиям.

Итак, снова начнем с простейшей структуры данных — стека.