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


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

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

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

Содержание

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

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

Без препятствий (англ. obstruction-free
Самая слабая из гарантий. Поток совершает прогресс, если не встречает препятствий со стороны других потоков. Алгоритм работает без препятствий, если поток, запущенный в любой момент (при условии, что выполнение всех препятствующих потоков приостановлено) завершит свою работу за детерминированное количество шагов. Синхронизация с помощью мьютексов не отвечает даже этому требованию: если поток остановится, захватив мьютекс, то остальные потоки, которым этот мьютекс нужен, будут простаивать.
Без блокировок (англ. lock-free
Для алгоритмов без блокировок гарантируется системный прогресс по крайней мере одного потока. Например поток, выполняющий операцию «сравнение с обменом» в цикле, теоретически может выполняться бесконечно, но каждая его итерация означает, что какой-то другой поток совершил прогресс, то есть система в целом совершает прогресс.
Без ожиданий (англ. wait-free
Самая строгая гарантия прогресса. Алгоритм работает без ожиданий, если каждая операция выполняется за детерминированное количество шагов, не зависящее от других потоков.

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

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

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

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

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

Реализация

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

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

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

Примечания

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

Ссылки



Wikimedia Foundation. 2010.

Смотреть что такое "Неблокирующая синхронизация" в других словарях:

  • Поток выполнения — Для термина «Поток» см. другие значения. Процесс с двумя потоками выполнения на одном процессоре Поток выполнения (анг …   Википедия

  • Параллельные вычислительные системы — Не следует путать с Распределённые вычисления. Параллельные вычислительные системы  это физические компьютерные, а также программные системы, реализующие тем или иным способом параллельную обработку данных на многих вычислительных узлах.[1]… …   Википедия

  • Распределённые вычисления — Не следует путать с Добровольные вычисления. См. также: Параллельные вычисления Распределённые вычисления способ решения трудоёмких вычислительных задач с использованием нескольких компьютеров, чаще всего объединённых в параллельную… …   Википедия

  • Message Passing Interface — Сюда перенаправляется запрос «OpenMPI». На эту тему нужна отдельная статья. Message Passing Interface (MPI, интерфейс передачи сообщений) программный интерфейс (API) для передачи информации, который позволяет обмениваться сообщениями между… …   Википедия

  • Nagios — Nagios …   Википедия

  • MPICH — MPICH2 Тип Программное обеспечение для обмена сообщениями между вычислительными процессами Написана на C, C++, Fortran, FreePascal Операционная система Universal Mac OS X, Linux, Unix, Windows Языки интерфейса …   Википедия

  • Zabbix — 1.1 alpha 6 running under GNU/Linux …   Википедия

  • OpenMP — (Open Multi Processing)  открытый стандарт для распараллеливания программ на языках Си, Си++ и Фортран. Описывает совокупность директив компилятора, библиотечных процедур и переменных окружения, которые предназначены для программирования… …   Википедия

  • Intelligent Platform Management Interface — IPMI (от англ. Intelligent Platform Management Interface)  интеллектуальный интерфейс управления платформой, предназначенный для автономного мониторинга и управления функциями, встроенными непосредственно в аппаратное и микропрограммное …   Википедия

  • Cacti — Cacti …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.