WikiSort.ru - Не сортированное

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Реализация

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

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

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

Примечания

Ссылки

• неблокирующие алгоритмы, Dmitry Vyukov — введение в неблокирующие алгоритмы, описания гарантий, примеры.
• Concurrent Data Structures (libcds) — С++-библиотека 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-сервер (рус.) - видео лекция

Для улучшения этой статьи желательно: Проверить достоверность указанной в статье информации. Проставив сноски, внести более точные указания на источники.