Проблема критической секции¶

Проблема критической секции (англ. critical section problem) — фундаментальная задача синхронизации параллельных процессов, заключающаяся в обеспечении взаимного исключения при доступе к общим ресурсам в многозадачных и многопоточных вычислительных системах. Суть проблемы состоит в том, что несколько процессов или потоков, выполняющихся одновременно, могут обращаться к одному и тому же разделяемому ресурсу (например, переменной, файлу, устройству ввода-вывода), что приводит к состоянию гонки (race condition) — непредсказуемому поведению программы, повреждению данных или сбоям. Критическая секция — это участок кода, в котором производится обращение к разделяемому ресурсу, и который должен выполняться атомарно, то есть без прерывания другими процессами. Решение проблемы критической секции требует соблюдения трёх основных условий: взаимного исключения (mutual exclusion), прогресса (progress) и ограниченного ожидания (bounded waiting).

¶Определение и контекст

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

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

¶Условия корректного решения

Для того чтобы решение проблемы критической секции считалось корректным, оно должно удовлетворять трём условиям:

¶Взаимное исключение (Mutual Exclusion)

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

¶Прогресс (Progress)

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

¶Ограниченное ожидание (Bounded Waiting)

Должно существовать ограничение на количество раз, которое другие процессы могут войти в критическую секцию после того, как данный процесс выразил желание войти, до того, как он сам войдёт. Это предотвращает «голодание» (starvation) процесса.

¶Классификация решений

Решения проблемы критической секции делятся на два основных класса: программные и аппаратные.

¶Программные решения

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

• Алгоритм Петерсона (1981 год) — один из первых корректных алгоритмов для двух процессов, использующий два флага и переменную turn. Он удовлетворяет всем трём условиям, но не масштабируется на произвольное число процессов.
• Алгоритм Деккера (1960-е годы) — также для двух процессов, основан на чередовании и флагах. Более сложен, чем алгоритм Петерсона, но также корректен.
• Алгоритм булочной (Bakery algorithm) Лесли Лампорта (1974 год) — обобщение для произвольного числа процессов, основанное на выдаче номеров (как в очереди в булочной). Процесс выбирает номер, который больше всех существующих, и ждёт, пока все процессы с меньшими номерами не завершат свои критические секции. Алгоритм гарантирует взаимное исключение и ограниченное ожидание, но требует атомарного чтения и записи.

¶Аппаратные решения

Аппаратные решения используют специальные машинные инструкции, которые выполняются атомарно. Наиболее распространённые:

• Test-and-Set (TAS) — атомарная инструкция, которая устанавливает значение переменной в 1 и возвращает её предыдущее значение. Используется для реализации спин-блокировок (spinlock). Однако базовый вариант TAS не гарантирует ограниченного ожидания.
• Compare-and-Swap (CAS) — атомарная инструкция, сравнивающая значение переменной с ожидаемым и, при совпадении, заменяет его на новое. Лежит в основе многих современных механизмов синхронизации, включая блокировки и неблокирующие структуры данных.
• Load-Link/Store-Conditional (LL/SC) — пара инструкций, используемая в архитектурах MIPS, ARM, PowerPC. Позволяет реализовать CAS без проблем с ложными срабатываниями.

¶Механизмы синхронизации

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

¶Семафоры

Семафор — это целочисленная переменная, над которой определены две атомарные операции: P (proberen, «попробовать») и V (verhogen, «увеличить»). Семафоры, предложенные Дейкстрой, позволяют реализовать взаимное исключение (двоичный семафор) и синхронизацию доступа к ограниченному числу ресурсов (счётный семафор). Недостатком семафоров является возможность ошибок программиста (например, забытая операция V).

¶Мьютексы (Mutex)

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

¶Мониторы

Монитор — высокоуровневый механизм синхронизации, впервые реализованный в языке Concurrent Pascal (1974 год). Монитор объединяет данные, процедуры и условие синхронизации в единый модуль. Только один процесс может одновременно выполнять процедуру монитора. Для организации ожидания используются условные переменные (condition variables) с операциями wait и signal. Мониторы используются в языках Java (synchronized), C# (lock) и других.

¶Блокировки чтения-записи (Read-Write Locks)

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

¶Примеры и применение

Проблема критической секции возникает в широком круге задач:

• Многопоточные серверы — при обработке запросов несколькими потоками необходимо синхронизировать доступ к общим структурам данных (очередям, кэшам, счётчикам).
• Операционные системы — при планировании процессов, управлении памятью и файловыми системами. Например, ядро Linux использует спин-блокировки и мьютексы для защиты критических секций.
• Базы данных — транзакции должны быть изолированы друг от друга, что реализуется через блокировки на уровне записей или таблиц.
• Встраиваемые системы — в реальном времени, где требуется гарантированное время отклика, используются специальные протоколы синхронизации (например, протокол наследования приоритетов).

¶Критика и ограничения

Традиционные решения проблемы критической секции имеют ряд недостатков:

• Производительность — блокировки могут приводить к простою процессов (особенно спин-блокировки), что снижает эффективность использования процессора.
• Deadlock — взаимная блокировка, когда два или более процессов ждут освобождения ресурсов, удерживаемых друг другом.
• Priority inversion — инверсия приоритетов, когда высокоприоритетный процесс ожидает блокировки, удерживаемой низкоприоритетным, что может нарушить требования реального времени.
• Масштабируемость — с ростом числа процессов/потоков накладные расходы на синхронизацию растут, что ограничивает производительность многопроцессорных систем.

В ответ на эти ограничения были разработаны альтернативные подходы: неблокирующие алгоритмы (lock-free и wait-free), транзакционная память (Transactional Memory) и асинхронное программирование. Например, в языках Go и Erlang используется модель акторов, где процессы не разделяют память, а общаются через сообщения, что полностью устраняет проблему критической секции на уровне приложения.

¶Интересные факты

• Эдсгер Дейкстра в 1968 году опубликовал статью «Cooperating Sequential Processes», в которой впервые систематически изложил проблему критической секции и предложил семафоры.
• Алгоритм Петерсона был назван в честь американского учёного Гэри Л. Петерсона, который опубликовал его в 1981 году. Однако аналогичный алгоритм был независимо открыт советским математиком Михаилом Рабиновичем в 1970-х годах.
• Проблема критической секции является частным случаем более общей проблемы взаимного исключения, которая в теории распределённых систем решается с помощью алгоритмов консенсуса (например, алгоритм Рикарта — Агравалы).

¶Источники

• Дейкстра Э. W. «Cooperating Sequential Processes» (1968)
• Петерсон Г. Л. «Myths About the Mutual Exclusion Problem» (1981)
• Лампорт Л. «A New Solution of Dijkstra's Concurrent Programming Problem» (1974)
• Танебаум Э., Бос Х. «Современные операционные системы» (4-е издание, 2015)
• Столлингс У. «Операционные системы: внутренняя структура и принципы проектирования» (9-е издание, 2017)