Неблокирующая синхронизация

Неблокирующая синхронизация — подход в параллельном программировании на симметрично-многопроцессорных системах, в котором отходят от традиционных примитивов блокировки, таких, как семафоры, мьютексы и события. Разделение доступа между потоками идёт за счёт атомарных операций и специальных, разработанных под конкретную задачу, механизмов блокировки.

Преимущество неблокирующих алгоритмов — в лучшей масштабируемости по количеству процессоров. К тому же, если ОС прервёт один из потоков фоновой задачей, остальные выполнят свою работу, не простаивая, а то и возьмут невыполненную работу на себя.

Три уровня неблокирующей синхронизации

От самого слабого к самому сильному:

Без препятствий (англ. obstruction-free)

Самая слабая из гарантий. Поток совершает прогресс, если не встречает препятствий со стороны других потоков. Алгоритм работает без препятствий, если поток, запущенный в любой момент (при условии, что выполнение всех препятствующих потоков приостановлено), завершит свою работу за детерминированное количество шагов. Синхронизация с помощью мьютексов не отвечает даже этому требованию: если поток остановится, захватив мьютекс, то остальные потоки, которым этот мьютекс нужен, будут простаивать.

Без блокировок (англ. lock-free)

Для алгоритмов без блокировок гарантируется системный прогресс по крайней мере одного потока. Например, поток, выполняющий операцию «сравнение с обменом» в цикле, теоретически может выполняться бесконечно, но каждая его итерация означает, что какой-то другой поток совершил прогресс, то есть система в целом совершает прогресс.

Без ожиданий (англ. wait-free)

Самая строгая гарантия прогресса. Алгоритм работает без ожиданий, если каждая операция выполняется за определённое количество шагов, не зависящее от других потоков.

Причины и выгоды

При создании многопоточных приложений часто возникает необходимость организовать совместный доступ к общему ресурсу. Традиционный подход позволяет предоставить последовательный доступ при помощи такого механизма синхронизации, как блокировки. Примитивы синхронизации, такие как мьютексы, семафоры и критические секции, позволяют написать участок кода, который гарантированно не будет выполняться одновременно при обращении из параллельных потоков — одновременный доступ к участку общей памяти может привести к повреждению содержимого. Попытка одного из потоков получить блокировку, которая уже занята другим потоком, приводит к приостановке выполнения первого потока до момента освобождения блокировки во втором потоке.

Простейший мьютекс реализуется с помощью так называемого spinlock’а — пустого цикла с атомарными операциями. Более сложные примитивы, выстраивающие потоки в очередь, устроены с помощью затратной операции, именуемой «переключение контекста», и того же spinlock’а в ядре (KiDispatcherLock в Windows), который защищает очередь с приоритетами. Когда нагрузка на примитивы синхронизации невелика (пользовательский интерфейс выводит общий ход работы другого потока; один поток даёт задания на закачку через сеть, второй закачивает…), издержки от пустых циклов и переключений невелики.

Если же обрабатывают крупный массив данных на многоядерном процессоре, и взаимодействия между потоками становится больше. Обычные структуры данных, например дерево поиска, можно оградить мьютексом только целиком, и если потоки постоянно к нему обращаются, работа становится почти что последовательной. К тому же обычный персональный компьютер с ОС общего назначения выполняет и другие задачи — например, пользователь, ожидая выполнения, открыл браузер — и часть процессорного времени отдаётся ему, а вычислительные потоки приостанавливаются в случайные моменты. Неблокирующие алгоритмы гарантируют, что такие остановки одного из потоков не приведут к простою остальных. Особенно важно отсутствие простоев, если один из потоков выполняет высокоприоритетную задачу или задачу реального времени.

Неблокирующая синхронизация позволяет полностью избавиться от взаимных блокировок. Впрочем, в неблокирующих алгоритмах есть свои ошибки — зацикливание (livelock) и «гонки».

Реализация

Неблокирующие алгоритмы строятся на атомарных операциях, например, чтение-модификация-запись и самая значимая из них — сравнение с обменом (CAS). Реализация критической секции обычно основана на использовании одного из примитивов. До недавних пор все реализации неблокирующих алгоритмов приходилось делать на «низком» уровне аппаратных средств для обеспечения приемлемого быстродействия. Тем не менее, развитие механизмов транзакционной памяти предоставляют стандартные абстракции для написания эффективного неблокирующего кода.

Также разработаны базовые структуры данных, такие как стек, очередь, множество и хеш-таблица. Такие структуры позволяют упростить асинхронный обмен данными между потоками программы. Некоторые структуры данных достаточно простые и могут использоваться без специальных атомарных блокировок, например:

• последовательный доступ для всех операций чтения и/или записи циклический буфер, очередь.
• Чтение-копирование-обновление (RCU) с единственным писателем и любым количеством читателей (читатели получают доступ к данным без ожидания блокировки; писатели обычно работают без блокировок до тех пор, пока не понадобится освободить память).

Ссылки

• неблокирующие алгоритмы, Dmitry Vyukov — введение в неблокирующие алгоритмы, описания гарантий, примеры.
• Concurrent Data Structures (libcds) — C++-библиотека lock-free структур и сборщиков мусора (англ.)
• An Introduction to Lock-Free Programming, Jeff Preshing, 2012-06-12. Issue #29 of Hacker Monthly.  (англ.)
• Non-blocking Algorithms, Jakob Jenkov, 2015-03-30 (англ.)
• Константин Облаков, Практика Lock-free. RealTime-сервер (рус.) - видео лекция