Примитивы синхронизации

Примитивы синхронизации — это программные механизмы, обеспечивающие координацию доступа нескольких потоков (или процессов) к общим ресурсам (критическим секциям) и предотвращающие состояния гонки (race condition), взаимные блокировки (deadlock) и другие проблемы параллельного выполнения. Они являются фундаментальными строительными блоками операционных систем, языков программирования и библиотек для многопоточного программирования.

Основные проблемы параллельного доступа

При одновременном выполнении нескольких потоков, обращающихся к разделяемым данным, возникает ряд проблем:

• Состояние гонки (Race condition): Ситуация, при которой результат выполнения программы зависит от порядка и времени выполнения потоков. Например, два потока одновременно пытаются увеличить счётчик: оба читают одно и то же значение, прибавляют единицу и записывают. В результате счётчик увеличивается на 1, а не на 2, так как одна операция перезаписывает результат другой.
• Взаимная блокировка (Deadlock): Ситуация, при которой каждый из двух или более потоков ожидает освобождения ресурса, удерживаемого другим потоком. В результате все потоки оказываются в состоянии вечного ожидания.
• Неопределённость (Indeterminacy): Невозможность предсказать, в каком порядке выполнятся инструкции разных потоков, что приводит к непредсказуемости поведения программы.

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

Классификация примитивов синхронизации

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

По механизму ожидания

• Примитивы с активным ожиданием (Spinlock): Поток, не сумевший захватить ресурс, выполняет цикл, постоянно проверяя его доступность. Эффективен только при очень коротких критических секциях, так как тратит процессорное время на ожидание. Используется в ядрах операционных систем и в системах реального времени.
• Примитивы с блокировкой (Blocking): Поток, не сумевший захватить ресурс, переводится операционной системой в состояние ожидания (sleep) и не потребляет процессорное время. При освобождении ресурса ОС пробуждает один или несколько ожидающих потоков. К этому классу относятся мьютексы, семафоры, условные переменные.

По типу ресурса

• Бинарные (Mutual Exclusion, Mutex): Позволяют только одному потоку владеть ресурсом в каждый момент времени. Реализуют принцип взаимного исключения.
• Счётные (Counting): Позволяют нескольким потокам (до определённого предела) одновременно владеть ресурсом. Пример — семафор с произвольным счётчиком.

Основные виды примитивов синхронизации

Мьютекс (Mutex, Mutual Exclusion)

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

• Операции: lock() (захватить) и unlock() (освободить). Поток, захвативший мьютекс, должен обязательно его освободить после завершения работы с разделяемым ресурсом, иначе возникнет взаимная блокировка.
• Рекурсивный мьютекс: Позволяет одному и тому же потоку захватывать мьютекс несколько раз (например, при рекурсивных вызовах функций). Каждый захват должен быть сбалансирован освобождением.
• Пример: В операционной системе Linux мьютексы используются для защиты структур данных ядра (например, списков процессов).

Семафор (Semaphore)

Семафор — примитив синхронизации, предложенный Эдсгером Дейкстрой в 1965 году. Он представляет собой целочисленный счётчик, который может быть увеличен (операция signal() или V()) и уменьшен (операция wait() или P()). Если счётчик равен нулю, поток, выполняющий wait(), блокируется.

• Бинарный семафор: Может принимать значения 0 или 1. По сути, является аналогом мьютекса, но не имеет понятия «владелец» — любой поток может освободить семафор, захваченный другим потоком.
• Счётный семафор: Позволяет ограничить количество потоков, одновременно работающих с ресурсом. Например, пул соединений с базой данных: семафор с начальным значением, равным числу соединений, блокирует потоки, когда все соединения заняты.
• Пример: В классической задаче «производитель-потребитель» семафоры используются для синхронизации доступа к буферу ограниченной ёмкости.

Условная переменная (Condition Variable)

Условная переменная — примитив, позволяющий потоку ожидать наступления определённого условия, связанного с состоянием разделяемых данных. Она всегда используется в паре с мьютексом.

• Операции: wait() (ожидание), signal() (уведомление одного ожидающего потока), broadcast() (уведомление всех ожидающих потоков).
• Механизм: Поток, ожидающий выполнения условия, сначала захватывает мьютекс, проверяет условие, и если оно ложно, вызывает wait(). Эта операция атомарно освобождает мьютекс и переводит поток в состояние ожидания. Когда другой поток изменяет состояние данных и вызывает signal() или broadcast(), один или все ожидающие потоки пробуждаются, повторно захватывают мьютекс и проверяют условие.
• Пример: В задаче «читатели-писатели» условные переменные позволяют читателям ждать, пока писатель закончит запись, и наоборот.

Барьер (Barrier)

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

• Применение: Используется в параллельных алгоритмах, где необходимо синхронизировать фазы вычислений. Например, в алгоритмах численного моделирования, где на каждом шаге все потоки должны завершить вычисления, прежде чем начать обмен данными.

Атомарные операции (Atomic Operations)

Атомарные операции — неделимые операции, выполняемые за один такт процессора или с гарантией отсутствия прерываний со стороны других потоков. К ним относятся атомарное чтение, запись, инкремент, декремент, сравнение с обменом (Compare-and-Swap, CAS).

• Применение: Используются для построения lock-free (безблокировочных) структур данных и алгоритмов, которые не требуют блокировки потоков. Например, атомарный счётчик ссылок в умных указателях (shared_ptr).
• Аппаратная поддержка: Современные процессоры (x86, ARM) предоставляют инструкции для атомарных операций, такие как LOCK CMPXCHG (x86) или LDREX/STREX (ARM).

Применение в операционных системах

В операционных системах примитивы синхронизации реализованы на уровне ядра и доступны пользовательским программам через системные вызовы или библиотеки.

• Linux: В ядре Linux используются спинлоки, мьютексы, семафоры, условные переменные, а также специализированные примитивы, такие как rcu (Read-Copy-Update) для оптимизации операций чтения. В пользовательском пространстве примитивы предоставляются библиотекой pthreads (POSIX threads).
• Windows: В ядре Windows используются спинлоки, мьютексы, семафоры, события (Event, аналог условной переменной). В пользовательском пространстве — объекты синхронизации Win32 API (CriticalSection, Mutex, Semaphore, Event).

Проблемы и ограничения

• Взаимная блокировка (Deadlock): Возникает, если потоки захватывают ресурсы в разном порядке. Для предотвращения deadlock применяются правила упорядоченного захвата ресурсов (например, захват мьютексов в строго определённом порядке).
• Голодание (Starvation): Ситуация, при которой один или несколько потоков не могут получить доступ к ресурсу в течение длительного времени, в то время как другие потоки активно его используют. Может быть вызвано несправедливой реализацией примитива.
• Инверсия приоритетов (Priority Inversion): Ситуация, при которой низкоприоритетный поток удерживает ресурс, необходимый высокоприоритетному потоку, что приводит к тому, что высокоприоритетный поток вынужден ждать. Для решения этой проблемы в системах реального времени используется протокол наследования приоритетов (Priority Inheritance Protocol).
• Производительность: Использование примитивов синхронизации вносит накладные расходы (overhead) на выполнение операций захвата и освобождения. Чрезмерное использование синхронизации может снизить производительность многопоточной программы, делая её медленнее однопоточной.

Примеры в языках программирования

• C++: Стандартная библиотека C++11 предоставляет std::mutex, std::recursive_mutex, std::timed_mutex, std::shared_mutex, std::condition_variable, std::atomic.
• Java: В Java примитивы синхронизации реализованы в пакете java.util.concurrent: ReentrantLock, Semaphore, CountDownLatch, CyclicBarrier, Phaser, атомарные классы (AtomicInteger, AtomicReference).
• Python: Стандартная библиотека Python включает threading.Lock, threading.RLock, threading.Semaphore, threading.Condition, threading.Barrier.
• Go: Язык Go предоставляет каналы (channels) как основной механизм синхронизации, а также примитивы из пакета sync: Mutex, RWMutex, WaitGroup, Once, Cond.

Источники

• Таненбаум Э., Бос Х. Современные операционные системы. 4-е изд. — СПб.: Питер, 2015.
• Дейкстра Э. Взаимодействие последовательных процессов. 1965.
• Херлихи М., Шавит Н., Лучко Д. Искусство многопроцессорного программирования. — М.: ДМК Пресс, 2010.
• Керниган Б., Пайк Р. Язык программирования Go. — М.: Вильямс, 2016.
• Документация по стандартной библиотеке C++ (cppreference.com).
• Документация по Java Platform, Standard Edition (Oracle).