Неблокирующая синхронизация — подход в параллельном программировании на симметрично-многопроцессорных системах, в котором отходят от традиционных примитивов блокировки, таких, как семафоры, мьютексы и события. Разделение доступа между потоками идёт за счёт атомарных операций и специальных, разработанных под конкретную задачу, механизмов блокировки.
Преимущество неблокирующих алгоритмов — в лучшей масштабируемости по количеству процессоров. К тому же, если ОС прервёт один из потоков фоновой задачей, остальные выполнят свою работу, не простаивая, а то и возьмут невыполненную работу на себя.
При создании многопоточных приложений часто возникает необходимость организовать совместный доступ к общему ресурсу. Традиционный подход позволяет предоставить последовательный доступ при помощи такого механизма синхронизации, как блокировки. Примитивы синхронизации, такие как мьютексы, семафоры и критические секции, позволяют написать участок кода, который гарантированно не будет выполняться одновременно при обращении из параллельных потоков — одновременный доступ к участку общей памяти может привести к повреждению содержимого. Попытка одного из потоков получить блокировку, которая уже занята другим потоком, приводит к приостановке выполнения первого потока до момента освобождения блокировки во втором потоке.
Простейший мьютекс[1] реализуется с помощью так называемого spinlock’а — пустого цикла с атомарными операциями. Более сложные примитивы, выстраивающие потоки в очередь, устроены с помощью затратной операции, именуемой «переключение контекста», и того же spinlock’а в ядре (KiDispatcherLock в Windows), который защищает очередь с приоритетами. Когда нагрузка на примитивы синхронизации невелика (пользовательский интерфейс выводит общий ход работы другого потока; один поток даёт задания на закачку через сеть, второй закачивает…), издержки от пустых циклов и переключений невелики.
Если же обрабатывают крупный массив данных на многоядерном процессоре, и взаимодействия между потоками становится больше. Обычные структуры данных, например дерево поиска, можно оградить мьютексом только целиком, и если потоки постоянно к нему обращаются, работа становится почти что последовательной. К тому же обычный персональный компьютер с ОС общего назначения выполняет и другие задачи — например, пользователь, ожидая выполнения, открыл браузер — и часть процессорного времени отдаётся ему, а вычислительные потоки приостанавливаются в случайные моменты. Неблокирующие алгоритмы гарантируют, что такие остановки одного из потоков не приведут к простою остальных. Особенно важно отсутствие простоев, если один из потоков выполняет высокоприоритетную задачу или задачу реального времени.
Неблокирующая синхронизация позволяет полностью избавиться от взаимных блокировок. Впрочем, в неблокирующих алгоритмах есть свои ошибки — зацикливание (livelock) и «гонки».