Синхронизация в операционных системах

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

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

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

Состояние гонки (Race condition)

Состояние гонки возникает, когда результат выполнения программы зависит от порядка, в котором потоки обращаются к общему ресурсу. Например, если два потока одновременно увеличивают значение переменной counter на 1, операция чтения, инкремента и записи может быть прервана, что приведёт к потере одного из увеличений. Классический пример — проблема «производитель-потребитель» (bounded buffer problem), где один поток записывает данные в буфер, а другой — читает, и требуется синхронизация, чтобы избежать переполнения или чтения пустого буфера.

Взаимная блокировка (Deadlock)

Взаимная блокировка — ситуация, при которой два или более потоков бесконечно ожидают освобождения ресурсов, удерживаемых друг другом. Для возникновения deadlock необходимо одновременное выполнение четырёх условий (условия Коффмана):

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

Голодание (Starvation)

Голодание — ситуация, когда один или несколько потоков не могут получить доступ к ресурсу в течение длительного времени, в то время как другие потоки получают его регулярно. Часто возникает из-за неправильной реализации приоритетов или алгоритмов планирования.

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

Для решения проблем синхронизации операционные системы предоставляют программные и аппаратные средства.

Семафоры (Semaphores)

Семафор — целочисленная переменная, над которой определены две атомарные операции: P (proberen — «проверить», также wait или acquire) и V (verhogen — «увеличить», также signal или release). Семафоры делятся на:

Двоичные (бинарные) — принимают значения 0 или 1, используются как мьютексы.
Счётные — принимают значения от 0 до N, позволяют управлять доступом к нескольким экземплярам ресурса.

Семафоры были предложены Эдсгером Дейкстрой в 1965 году и стали одним из первых механизмов синхронизации.

Мьютексы (Mutexes)

Мьютекс (mutual exclusion — взаимное исключение) — упрощённый вариант двоичного семафора, предназначенный для защиты критической секции. В отличие от семафора, мьютекс может быть освобождён только тем потоком, который его захватил. В современных ОС (Linux, Windows) мьютексы часто реализованы с использованием аппаратных инструкций (например, test-and-set или compare-and-swap) и поддерживают рекурсивный захват.

Мониторы (Monitors)

Монитор — высокоуровневая конструкция, объединяющая данные, процедуры и механизмы синхронизации. Включает в себя:

Взаимное исключение — только один поток может выполнять код монитора в данный момент.
Условные переменные — позволяют потокам ожидать определённого состояния (например, wait, signal, broadcast).

Мониторы впервые были реализованы в языке Concurrent Pascal (Ч. Хоар, 1974), а затем встроены в Java (синхронизированные методы и блоки).

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

Атомарные операции — неделимые аппаратные инструкции, выполняемые за один такт процессора без возможности прерывания. К ним относятся:

test-and-set (TAS) — проверка и установка значения.
compare-and-swap (CAS) — сравнение и обмен.
load-link/store-conditional (LL/SC) — загрузка с пометкой и условное сохранение.

На основе атомарных операций строятся спин-блокировки (spinlocks) и lock-free структуры данных.

Алгоритмы синхронизации

Помимо примитивов, существуют классические алгоритмы, решающие задачи синхронизации.

Алгоритм Петерсона (Peterson’s algorithm)

Алгоритм Петерсона (Г. Петерсон, 1981) — программное решение задачи взаимного исключения для двух потоков, не требующее аппаратной поддержки. Использует два флага (flag[0], flag[1]) и переменную turn. Несмотря на теоретическую значимость, на современных многоядерных процессорах с неупорядоченным выполнением инструкций алгоритм может давать сбои без специальных барьеров памяти.

Алгоритм пекарни (Bakery algorithm)

Алгоритм пекарни (Л. Лампорт, 1974) — обобщение алгоритма Петерсона для N потоков. Каждый поток получает «номерок» (как в пекарне), и доступ к критической секции предоставляется потоку с наименьшим номером. Алгоритм гарантирует взаимное исключение, отсутствие голодания и взаимных блокировок, но требует большого количества операций записи.

Проблема обедающих философов (Dining philosophers problem)

Классическая задача, сформулированная Э. Дейкстрой в 1965 году. Пять философов сидят за круглым столом, каждый имеет по одной вилке слева и справа. Для еды нужно две вилки. Задача демонстрирует проблемы deadlock и голодания. Решения включают использование семафоров, мониторов или асимметричных правил (например, чётные философы берут вилку слева, нечётные — справа).

Синхронизация в современных ОС

Linux

В ядре Linux используются:

Spinlocks — для кратковременной блокировки на многопроцессорных системах, когда ожидание не приводит к переключению контекста.
Mutexes — для долговременных блокировок, могут переводить поток в сон.
Read-write locks (rwlock) — разделяют доступ на чтение (множественный) и запись (исключительный).
Futex (fast userspace mutex) — гибридный механизм, работающий в пространстве пользователя и переходящий в ядро только при конфликте.

Windows

В Windows NT реализованы:

CRITICAL_SECTION — аналог мьютекса для потоков одного процесса, работает в пользовательском режиме.
Mutex — объект ядра, поддерживающий межпроцессную синхронизацию.
Semaphore — объект ядра для счётной синхронизации.
Event — объект для уведомления о наступлении события (ручной или автоматический сброс).
Slim Reader/Writer (SRW) Lock — лёгкая блокировка для чтения/записи, появившаяся в Windows Vista.

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

Инверсия приоритетов — ситуация, когда высокоприоритетный поток ожидает ресурса, удерживаемого низкоприоритетным, что может привести к нарушению реального времени. Решается протоколами наследования приоритета (priority inheritance) или потолка приоритета (priority ceiling).
Барьеры памяти (memory barriers) — инструкции, принудительно упорядочивающие операции чтения/записи, необходимые для корректной работы на архитектурах со слабой моделью памяти (ARM, PowerPC).

Применение

Синхронизация используется во всех областях, где требуется параллельная обработка:

Серверные приложения — обработка запросов в пуле потоков.
Базы данных — блокировки строк, таблиц, транзакции.
Графические интерфейсы — защита очередей сообщений.
Встраиваемые системы — синхронизация доступа к периферийным устройствам.
Научные вычисления — распределение данных между процессами MPI.

См. также

Источники

Таненбаум Э., Бос Х. «Современные операционные системы» (4-е издание). — СПб.: Питер, 2015.
Silberschatz A., Galvin P. B., Gagne G. «Operating System Concepts» (10th edition). — Wiley, 2018.
Лампорт Л. «The Bakery Algorithm» (1974).
Дейкстра Э. «Cooperating Sequential Processes» (1965).
Документация ядра Linux: «Linux Kernel Locking Mechanisms» (kernel.org).
Документация Microsoft: «Synchronization in Windows» (MSDN).

BFOmetr — база данных и аналитика по компаниям России.

На главную BFOmetr →