Двоичный семафор¶

Двоичный семафор — это простейшая форма семафора, используемая в параллельном программировании и операционных системах для синхронизации доступа к общим ресурсам. В отличие от счётного семафора, который может принимать произвольные неотрицательные целые значения, двоичный семафор принимает только два состояния: 0 (занят, ресурс недоступен) и 1 (свободен, ресурс доступен). По своей сути он эквивалентен логическому флагу, но с поддержкой атомарных операций, что делает его надёжным инструментом для предотвращения состояний гонки.

¶История

Концепция семафоров была предложена нидерландским учёным Эдсгером Дейкстрой в 1965 году. В своей работе «Co-operating sequential processes» Дейкстра впервые описал механизм синхронизации, основанный на целочисленной переменной. Двоичный семафор стал частным случаем общего семафора, где переменная может принимать только значения 0 и 1. Первоначально он использовался в операционной системе THE (Technische Hogeschool Eindhoven), разработанной Дейкстрой и его коллегами. Впоследствии двоичные семафоры были реализованы во многих операционных системах, включая Unix, Linux и Windows, а также в языках программирования с поддержкой многопоточности, таких как C, Java и Python.

¶Принцип работы

Двоичный семафор управляется двумя атомарными операциями: P (от нидерл. proberen — «попробовать») и V (от нидерл. verhogen — «увеличить»). В англоязычной литературе эти операции часто называют wait и signal или acquire и release.

• Операция P (wait, acquire): Если значение семафора равно 1, оно уменьшается до 0, и поток продолжает выполнение. Если значение равно 0, поток блокируется и помещается в очередь ожидания до тех пор, пока семафор не станет свободным.
• Операция V (signal, release): Если есть потоки, ожидающие в очереди, один из них разблокируется. Если очередь пуста, значение семафора увеличивается до 1.

Атомарность этих операций гарантируется аппаратно или с помощью механизмов операционной системы, таких как блокировки шины или инструкции типа test-and-set.

¶Отличие от мьютекса

Хотя двоичный семафор и мьютекс (mutex, от mutual exclusion) внешне схожи, между ними есть принципиальные различия:

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

¶Применение

¶Взаимное исключение

Двоичный семафор может использоваться для защиты критических секций кода. Перед входом в критическую секцию поток выполняет операцию P, а после выхода — V. Однако из-за отсутствия привязки к владельцу это менее надёжно, чем мьютекс: ошибка программиста может привести к тому, что другой поток случайно освободит семафор.

¶Синхронизация событий

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

1. Поток A выполняет P на семафоре (изначально 0) и блокируется.
2. Поток B выполняет задачу и затем выполняет V, разблокируя поток A.

Этот паттерн используется в архитектурах «производитель-потребитель» и в системах реального времени.

¶Реализация блокировок чтения-записи

Двоичные семафоры могут быть компонентами более сложных механизмов синхронизации, таких как блокировки чтения-записи (read-write locks). В таких системах один семафор управляет доступом на запись, а другой — на чтение.

¶Реализации в операционных системах

¶POSIX (Linux, Unix)

В стандарте POSIX определён тип sem_t и функции sem_wait (P) и sem_post (V). Для создания двоичного семафора начальное значение устанавливается в 1. Пример на C:

```c

¶include <semaphore.h>

sem_t sem; sem_init(&sem, 0, 1); // Двоичный семафор sem_wait(&sem); // Захват // Критическая секция sem_post(&sem); // Освобождение ```

¶Windows

В Windows семафоры создаются с помощью функции CreateSemaphore. Для двоичного семафора максимальное значение устанавливается в 1. Используются функции WaitForSingleObject (P) и ReleaseSemaphore (V).

¶Java

В Java двоичный семафор реализован классом java.util.concurrent.Semaphore с параметром permits = 1. Методы acquire() и release() соответствуют операциям P и V.

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

• Отсутствие владельца: Любой поток может освободить семафор, что может привести к некорректной работе программы.
• Инверсия приоритетов: Если высокоприоритетный поток ожидает семафор, удерживаемый низкоприоритетным, система может столкнуться с инверсией приоритетов. В отличие от мьютексов, двоичные семафоры не поддерживают наследование приоритетов.
• Взаимная блокировка (deadlock): Неправильное использование нескольких семафоров может привести к ситуации, когда потоки бесконечно ожидают друг друга.
• Голодание (starvation): В некоторых реализациях потоки с низким приоритетом могут никогда не получить доступ к семафору, если постоянно поступают запросы от высокоприоритетных потоков.

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

• В оригинальной работе Дейкстры семафоры назывались «P- и V-операциями» в честь нидерландских слов proberen и verhogen.
• Двоичные семафоры часто путают с мьютексами, но в системах реального времени, таких как VxWorks, они различаются строго: мьютекс имеет владельца, а семафор — нет.
• В языке Go примитивы синхронизации основаны на каналах, а не на семафорах, но двоичный семафор может быть эмулирован с помощью канала ёмкостью 1.

¶Критика

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

¶Источники

• Дейкстра, Э. «Co-operating sequential processes» (1965).
• Таненбаум, Э. «Современные операционные системы» (4-е издание, 2015).
• Stallings, W. «Operating Systems: Internals and Design Principles» (9-е издание, 2017).
• Документация POSIX.1-2008 (IEEE Std 1003.1).
• Документация Microsoft Windows API (CreateSemaphore, WaitForSingleObject, ReleaseSemaphore).