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