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

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

История

Необходимость в синхронизации возникла с появлением первых многопоточных и многопроцессорных систем в 1960-х годах. Одним из первых решений стал семафор, предложенный Эдсгером Дейкстрой в 1965 году для операционной системы THE. Дейкстра ввёл понятия атомарных операций P (proberen — «проверить») и V (verhogen — «увеличить»), которые позволяли блокировать и освобождать ресурсы. В 1970-х годах были разработаны мьютексы (mutual exclusion locks) как более простая альтернатива семафорам для защиты критических секций. В 1980-х годах появились условные переменные (condition variables), позволяющие потокам ожидать наступления определённого состояния. С развитием многопроцессорных архитектур и языков программирования (например, Java, C++11) примитивы синхронизации стали стандартной частью библиотек. В 1990-х годах были предложены блокировки с чтением-записью (read-write locks), оптимизирующие доступ при преобладании операций чтения. В современных системах активно используются атомарные операции (например, compare-and-swap), реализуемые на уровне процессора.

Классификация

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

По типу блокировки

• Активные блокировки (spinlocks): поток непрерывно проверяет условие в цикле, не переходя в состояние ожидания. Эффективны при коротких периодах ожидания, но потребляют ресурсы процессора.
• Пассивные блокировки (sleeping locks): поток приостанавливается операционной системой до освобождения ресурса. Экономят процессорное время, но требуют переключения контекста.

По уровню реализации

• Аппаратные примитивы: реализуются на уровне процессора (например, инструкции LOCK в x86, LDREX/STREX в ARM). Обеспечивают атомарность операций.
• Программные примитивы: реализуются в операционной системе или библиотеках (мьютексы, семафоры, условные переменные).

По области применения

• Блокировки: мьютексы, спинлоки, блокировки с чтением-записью.
• Сигнальные примитивы: семафоры, условные переменные, барьеры.
• Атомарные операции: compare-and-swap (CAS), fetch-and-add, test-and-set.

Основные виды примитивов

Мьютекс (mutex)

Мьютекс (от mutual exclusion — «взаимное исключение») — простейший примитив, позволяющий только одному потоку одновременно владеть ресурсом. Поток, захвативший мьютекс, выполняет критическую секцию, после чего освобождает его. Если другой поток пытается захватить занятый мьютекс, он блокируется до освобождения. Мьютексы могут быть рекурсивными (один поток может захватывать один и тот же мьютекс несколько раз) и нерекурсивными. В операционных системах (например, Linux, Windows) мьютексы реализуются через системные вызовы.

Семафор

Семафор — целочисленная переменная, поддерживающая две атомарные операции: P (уменьшение) и V (увеличение). Если значение семафора равно нулю, операция P блокирует поток до тех пор, пока другой поток не выполнит V. Семафоры бывают двоичными (значения 0 или 1, аналогично мьютексу) и счётными (позволяют ограничить доступ к ресурсу с несколькими экземплярами, например, пул соединений). Семафоры широко использовались в ранних UNIX-системах (System V IPC).

Условная переменная (condition variable)

Условная переменная используется вместе с мьютексом для ожидания определённого состояния. Поток, владеющий мьютексом, может вызвать wait, который атомарно освобождает мьютекс и блокирует поток. Когда другой поток изменяет состояние и вызывает signal или broadcast, ожидающий поток пробуждается и повторно захватывает мьютекс. Условные переменные реализованы в библиотеках pthreads (POSIX) и C++11.

Блокировка с чтением-записью (read-write lock)

Блокировка с чтением-записью позволяет нескольким потокам одновременно читать данные, но только одному — записывать. Это повышает производительность в сценариях, где чтение преобладает над записью. В русскоязычной литературе также называется «мьютексом с разделением» или «rwlock». Реализации есть в POSIX (pthread_rwlock_t) и Windows (SRWLock).

Барьер (barrier)

Барьер — примитив, который заставляет потоки ожидать, пока все участники не достигнут определённой точки выполнения. Используется для синхронизации фаз параллельных вычислений, например, в алгоритмах сортировки или численных методах. В стандарте C++20 барьер реализован как std::barrier.

Атомарные операции

Атомарные операции — неделимые операции над памятью, выполняемые без прерываний. Наиболее распространённая — compare-and-swap (CAS): она сравнивает значение в памяти с ожидаемым и, если они совпадают, заменяет его на новое. CAS используется для построения неблокирующих структур данных (lock-free). Другие атомарные операции: fetch-and-add (увеличивает значение и возвращает старое), test-and-set (устанавливает флаг и возвращает предыдущее значение). В процессорах x86 атомарность обеспечивается префиксом LOCK, в ARM — инструкциями LDREX/STREX.

Применение

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

• Операционные системы: управление доступом к файловой системе, сетевым сокетам, драйверам устройств. Например, в ядре Linux используются спинлоки для защиты критических секций в обработчиках прерываний.
• Многопоточное программирование: защита разделяемых данных в веб-серверах, базах данных, игровых движках. В Java мьютексы реализуются через ключевое слово synchronized, в C++ — через std::mutex.
• Параллельные вычисления: синхронизация потоков в MPI-программах, OpenMP-циклах, CUDA-ядрах. Барьеры используются для синхронизации фаз расчёта.
• Базы данных: блокировки строк и таблиц для обеспечения изоляции транзакций (например, в PostgreSQL, MySQL).
• Встраиваемые системы: синхронизация задач в реальном времени (RTOS, например, FreeRTOS) с помощью семафоров и мьютексов.

Проблемы и критика

Использование примитивов синхронизации сопряжено с рядом сложностей:

• Взаимная блокировка (deadlock): два или более потоков ожидают освобождения ресурсов, удерживаемых друг другом. Для предотвращения применяются стратегии упорядочивания блокировок или использование тайм-аутов.
• Голодание (starvation): один поток не может получить доступ к ресурсу из-за постоянной активности других. Решается приоритетными блокировками или справедливыми семафорами.
• Инверсия приоритетов: низкоприоритетный поток удерживает ресурс, необходимый высокоприоритетному, что нарушает планирование. В реальном времени применяется протокол наследования приоритетов (например, в ОСРВ QNX).
• Снижение производительности: избыточное использование блокировок ведёт к простоям процессора и увеличению накладных расходов. Альтернативой являются неблокирующие структуры данных (lock-free) и транзакционная память (Transactional Memory).

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

• C++: std::mutex, std::lock_guard, std::unique_lock, std::condition_variable, std::atomic (C++11 и новее).
• Java: ключевое слово synchronized, классы ReentrantLock, Semaphore, CountDownLatch, CyclicBarrier.
• Python: модуль threading с классами Lock, RLock, Semaphore, Condition.
• Go: каналы (channels) и примитивы из пакета sync (Mutex, RWMutex, WaitGroup).
• C#: lock (синтаксический сахар для Monitor), Mutex, SemaphoreSlim, ReaderWriterLockSlim.

Источники

• Таненбаум Э., Бос Х. «Современные операционные системы» (4-е издание, 2015).
• Дейкстра Э. «Co-operating sequential processes» (1965).
• Херлихи М., Шавит Н. «The Art of Multiprocessor Programming» (2-е издание, 2020).
• Документация POSIX.1-2017 (раздел «Synchronization»).
• Стандарт ISO/IEC 14882:2020 (C++20) — раздел «Thread support library».
• Материалы курса «Operating Systems» (MIT 6.828, 2023).