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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Реализация

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

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

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

Примечания

1. ↑ На нескольких процессорах, в однопроцессорных ядрах несколько по-другому.

Ссылки

• неблокирующие алгоритмы — введение в неблокирующие алгоритмы, описания гарантий, примеры.
• неблокирующие контейнеры — описание, базовые принципы и реализация на C++0x.
• сборка мусора — алгоритмы сборки мусора для неблокирующих контейнеров, описание, базовые принципы и примеры на C++0x.
• lock-free readers-writers — неблокирующие контейнеры для частого чтения и редкой записи, сборка мусора (техника hazard pointers), реализация на C++0x.
• шаблон atomic anything — неблокирующая реализация любых атомарных модификаций с помощью операции сравнение с обменом.
• Concurrent Data Structures (libcds) — С++-библиотека lock-free структур и сборщиков мусора

Для улучшения этой статьи по информационным технологиям желательно?: Найти и оформить в виде сносок ссылки на авторитетные источники, подтверждающие написанное.