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

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

Обоснование

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

Приостановка потока нежелательна по многим причинам. Очевидно что во время ожидания блокировки поток не может выполнять свою работу. Если заблокированный поток выполняет высокоприоритетную задачу или задачу реального времени, очень нежелательно такой поток блокировать. Другая проблема менее очевидна. Определенное взаимное влияние блокировок может приводить к ошибкам таким как взаимная блокировка, зацикливание, инверсия приоритета.

Реализация

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

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

Без ожиданий

Без блокировок

Без препятствий